src/HOL/Library/Complete_Partial_Order2.thy
author wenzelm
Fri May 27 20:23:55 2016 +0200 (2016-05-27)
changeset 63170 eae6549dbea2
parent 63092 a949b2a5f51d
child 63243 1bc6816fd525
permissions -rw-r--r--
tuned proofs, to allow unfold_abs_def;
wenzelm@62858
     1
(*  Title:      HOL/Library/Complete_Partial_Order2.thy
Andreas@62652
     2
    Author:     Andreas Lochbihler, ETH Zurich
Andreas@62652
     3
*)
Andreas@62652
     4
wenzelm@62837
     5
section \<open>Formalisation of chain-complete partial orders, continuity and admissibility\<close>
Andreas@62652
     6
Andreas@62652
     7
theory Complete_Partial_Order2 imports 
Andreas@62652
     8
  Main
Andreas@62652
     9
  "~~/src/HOL/Library/Lattice_Syntax"
Andreas@62652
    10
begin
Andreas@62652
    11
Andreas@62652
    12
context begin interpretation lifting_syntax .
Andreas@62652
    13
Andreas@62652
    14
lemma chain_transfer [transfer_rule]:
Andreas@62652
    15
  "((A ===> A ===> op =) ===> rel_set A ===> op =) Complete_Partial_Order.chain Complete_Partial_Order.chain"
Andreas@62652
    16
unfolding chain_def[abs_def] by transfer_prover
Andreas@62652
    17
Andreas@62652
    18
end
Andreas@62652
    19
Andreas@62652
    20
lemma linorder_chain [simp, intro!]:
Andreas@62652
    21
  fixes Y :: "_ :: linorder set"
Andreas@62652
    22
  shows "Complete_Partial_Order.chain op \<le> Y"
Andreas@62652
    23
by(auto intro: chainI)
Andreas@62652
    24
Andreas@62652
    25
lemma fun_lub_apply: "\<And>Sup. fun_lub Sup Y x = Sup ((\<lambda>f. f x) ` Y)"
Andreas@62652
    26
by(simp add: fun_lub_def image_def)
Andreas@62652
    27
Andreas@62652
    28
lemma fun_lub_empty [simp]: "fun_lub lub {} = (\<lambda>_. lub {})"
Andreas@62652
    29
by(rule ext)(simp add: fun_lub_apply)
Andreas@62652
    30
Andreas@62652
    31
lemma chain_fun_ordD: 
Andreas@62652
    32
  assumes "Complete_Partial_Order.chain (fun_ord le) Y"
Andreas@62652
    33
  shows "Complete_Partial_Order.chain le ((\<lambda>f. f x) ` Y)"
Andreas@62652
    34
by(rule chainI)(auto dest: chainD[OF assms] simp add: fun_ord_def)
Andreas@62652
    35
Andreas@62652
    36
lemma chain_Diff:
Andreas@62652
    37
  "Complete_Partial_Order.chain ord A
Andreas@62652
    38
  \<Longrightarrow> Complete_Partial_Order.chain ord (A - B)"
Andreas@62652
    39
by(erule chain_subset) blast
Andreas@62652
    40
Andreas@62652
    41
lemma chain_rel_prodD1:
Andreas@62652
    42
  "Complete_Partial_Order.chain (rel_prod orda ordb) Y
Andreas@62652
    43
  \<Longrightarrow> Complete_Partial_Order.chain orda (fst ` Y)"
Andreas@62652
    44
by(auto 4 3 simp add: chain_def)
Andreas@62652
    45
Andreas@62652
    46
lemma chain_rel_prodD2:
Andreas@62652
    47
  "Complete_Partial_Order.chain (rel_prod orda ordb) Y
Andreas@62652
    48
  \<Longrightarrow> Complete_Partial_Order.chain ordb (snd ` Y)"
Andreas@62652
    49
by(auto 4 3 simp add: chain_def)
Andreas@62652
    50
Andreas@62652
    51
Andreas@62652
    52
context ccpo begin
Andreas@62652
    53
Andreas@62652
    54
lemma ccpo_fun: "class.ccpo (fun_lub Sup) (fun_ord op \<le>) (mk_less (fun_ord op \<le>))"
Andreas@62652
    55
  by standard (auto 4 3 simp add: mk_less_def fun_ord_def fun_lub_apply
Andreas@62652
    56
    intro: order.trans antisym chain_imageI ccpo_Sup_upper ccpo_Sup_least)
Andreas@62652
    57
Andreas@62652
    58
lemma ccpo_Sup_below_iff: "Complete_Partial_Order.chain op \<le> Y \<Longrightarrow> Sup Y \<le> x \<longleftrightarrow> (\<forall>y\<in>Y. y \<le> x)"
Andreas@62652
    59
by(fast intro: order_trans[OF ccpo_Sup_upper] ccpo_Sup_least)
Andreas@62652
    60
Andreas@62652
    61
lemma Sup_minus_bot: 
Andreas@62652
    62
  assumes chain: "Complete_Partial_Order.chain op \<le> A"
Andreas@62652
    63
  shows "\<Squnion>(A - {\<Squnion>{}}) = \<Squnion>A"
Andreas@62652
    64
apply(rule antisym)
Andreas@62652
    65
 apply(blast intro: ccpo_Sup_least chain_Diff[OF chain] ccpo_Sup_upper[OF chain])
Andreas@62652
    66
apply(rule ccpo_Sup_least[OF chain])
Andreas@62652
    67
apply(case_tac "x = \<Squnion>{}")
Andreas@62652
    68
by(blast intro: ccpo_Sup_least chain_empty ccpo_Sup_upper[OF chain_Diff[OF chain]])+
Andreas@62652
    69
Andreas@62652
    70
lemma mono_lub:
Andreas@62652
    71
  fixes le_b (infix "\<sqsubseteq>" 60)
Andreas@62652
    72
  assumes chain: "Complete_Partial_Order.chain (fun_ord op \<le>) Y"
Andreas@62652
    73
  and mono: "\<And>f. f \<in> Y \<Longrightarrow> monotone le_b op \<le> f"
Andreas@62652
    74
  shows "monotone op \<sqsubseteq> op \<le> (fun_lub Sup Y)"
Andreas@62652
    75
proof(rule monotoneI)
Andreas@62652
    76
  fix x y
Andreas@62652
    77
  assume "x \<sqsubseteq> y"
Andreas@62652
    78
Andreas@62652
    79
  have chain'': "\<And>x. Complete_Partial_Order.chain op \<le> ((\<lambda>f. f x) ` Y)"
Andreas@62652
    80
    using chain by(rule chain_imageI)(simp add: fun_ord_def)
Andreas@62652
    81
  then show "fun_lub Sup Y x \<le> fun_lub Sup Y y" unfolding fun_lub_apply
Andreas@62652
    82
  proof(rule ccpo_Sup_least)
Andreas@62652
    83
    fix x'
Andreas@62652
    84
    assume "x' \<in> (\<lambda>f. f x) ` Y"
Andreas@62652
    85
    then obtain f where "f \<in> Y" "x' = f x" by blast
wenzelm@62837
    86
    note \<open>x' = f x\<close> also
wenzelm@62837
    87
    from \<open>f \<in> Y\<close> \<open>x \<sqsubseteq> y\<close> have "f x \<le> f y" by(blast dest: mono monotoneD)
Andreas@62652
    88
    also have "\<dots> \<le> \<Squnion>((\<lambda>f. f y) ` Y)" using chain''
wenzelm@62837
    89
      by(rule ccpo_Sup_upper)(simp add: \<open>f \<in> Y\<close>)
Andreas@62652
    90
    finally show "x' \<le> \<Squnion>((\<lambda>f. f y) ` Y)" .
Andreas@62652
    91
  qed
Andreas@62652
    92
qed
Andreas@62652
    93
Andreas@62652
    94
context
Andreas@62652
    95
  fixes le_b (infix "\<sqsubseteq>" 60) and Y f
Andreas@62652
    96
  assumes chain: "Complete_Partial_Order.chain le_b Y" 
Andreas@62652
    97
  and mono1: "\<And>y. y \<in> Y \<Longrightarrow> monotone le_b op \<le> (\<lambda>x. f x y)"
Andreas@62652
    98
  and mono2: "\<And>x a b. \<lbrakk> x \<in> Y; a \<sqsubseteq> b; a \<in> Y; b \<in> Y \<rbrakk> \<Longrightarrow> f x a \<le> f x b"
Andreas@62652
    99
begin
Andreas@62652
   100
Andreas@62652
   101
lemma Sup_mono: 
Andreas@62652
   102
  assumes le: "x \<sqsubseteq> y" and x: "x \<in> Y" and y: "y \<in> Y"
Andreas@62652
   103
  shows "\<Squnion>(f x ` Y) \<le> \<Squnion>(f y ` Y)" (is "_ \<le> ?rhs")
Andreas@62652
   104
proof(rule ccpo_Sup_least)
Andreas@62652
   105
  from chain show chain': "Complete_Partial_Order.chain op \<le> (f x ` Y)" when "x \<in> Y" for x
Andreas@62652
   106
    by(rule chain_imageI) (insert that, auto dest: mono2)
Andreas@62652
   107
Andreas@62652
   108
  fix x'
Andreas@62652
   109
  assume "x' \<in> f x ` Y"
Andreas@62652
   110
  then obtain y' where "y' \<in> Y" "x' = f x y'" by blast note this(2)
wenzelm@62837
   111
  also from mono1[OF \<open>y' \<in> Y\<close>] le have "\<dots> \<le> f y y'" by(rule monotoneD)
Andreas@62652
   112
  also have "\<dots> \<le> ?rhs" using chain'[OF y]
wenzelm@62837
   113
    by (auto intro!: ccpo_Sup_upper simp add: \<open>y' \<in> Y\<close>)
Andreas@62652
   114
  finally show "x' \<le> ?rhs" .
Andreas@62652
   115
qed(rule x)
Andreas@62652
   116
Andreas@62652
   117
lemma diag_Sup: "\<Squnion>((\<lambda>x. \<Squnion>(f x ` Y)) ` Y) = \<Squnion>((\<lambda>x. f x x) ` Y)" (is "?lhs = ?rhs")
Andreas@62652
   118
proof(rule antisym)
Andreas@62652
   119
  have chain1: "Complete_Partial_Order.chain op \<le> ((\<lambda>x. \<Squnion>(f x ` Y)) ` Y)"
Andreas@62652
   120
    using chain by(rule chain_imageI)(rule Sup_mono)
Andreas@62652
   121
  have chain2: "\<And>y'. y' \<in> Y \<Longrightarrow> Complete_Partial_Order.chain op \<le> (f y' ` Y)" using chain
Andreas@62652
   122
    by(rule chain_imageI)(auto dest: mono2)
Andreas@62652
   123
  have chain3: "Complete_Partial_Order.chain op \<le> ((\<lambda>x. f x x) ` Y)"
Andreas@62652
   124
    using chain by(rule chain_imageI)(auto intro: monotoneD[OF mono1] mono2 order.trans)
Andreas@62652
   125
Andreas@62652
   126
  show "?lhs \<le> ?rhs" using chain1
Andreas@62652
   127
  proof(rule ccpo_Sup_least)
Andreas@62652
   128
    fix x'
Andreas@62652
   129
    assume "x' \<in> (\<lambda>x. \<Squnion>(f x ` Y)) ` Y"
Andreas@62652
   130
    then obtain y' where "y' \<in> Y" "x' = \<Squnion>(f y' ` Y)" by blast note this(2)
wenzelm@62837
   131
    also have "\<dots> \<le> ?rhs" using chain2[OF \<open>y' \<in> Y\<close>]
Andreas@62652
   132
    proof(rule ccpo_Sup_least)
Andreas@62652
   133
      fix x
Andreas@62652
   134
      assume "x \<in> f y' ` Y"
Andreas@62652
   135
      then obtain y where "y \<in> Y" and x: "x = f y' y" by blast
wenzelm@63040
   136
      define y'' where "y'' = (if y \<sqsubseteq> y' then y' else y)"
wenzelm@62837
   137
      from chain \<open>y \<in> Y\<close> \<open>y' \<in> Y\<close> have "y \<sqsubseteq> y' \<or> y' \<sqsubseteq> y" by(rule chainD)
wenzelm@62837
   138
      hence "f y' y \<le> f y'' y''" using \<open>y \<in> Y\<close> \<open>y' \<in> Y\<close>
Andreas@62652
   139
        by(auto simp add: y''_def intro: mono2 monotoneD[OF mono1])
wenzelm@62837
   140
      also from \<open>y \<in> Y\<close> \<open>y' \<in> Y\<close> have "y'' \<in> Y" by(simp add: y''_def)
wenzelm@62837
   141
      from chain3 have "f y'' y'' \<le> ?rhs" by(rule ccpo_Sup_upper)(simp add: \<open>y'' \<in> Y\<close>)
Andreas@62652
   142
      finally show "x \<le> ?rhs" by(simp add: x)
Andreas@62652
   143
    qed
Andreas@62652
   144
    finally show "x' \<le> ?rhs" .
Andreas@62652
   145
  qed
Andreas@62652
   146
Andreas@62652
   147
  show "?rhs \<le> ?lhs" using chain3
Andreas@62652
   148
  proof(rule ccpo_Sup_least)
Andreas@62652
   149
    fix y
Andreas@62652
   150
    assume "y \<in> (\<lambda>x. f x x) ` Y"
Andreas@62652
   151
    then obtain x where "x \<in> Y" and "y = f x x" by blast note this(2)
wenzelm@62837
   152
    also from chain2[OF \<open>x \<in> Y\<close>] have "\<dots> \<le> \<Squnion>(f x ` Y)"
wenzelm@62837
   153
      by(rule ccpo_Sup_upper)(simp add: \<open>x \<in> Y\<close>)
wenzelm@62837
   154
    also have "\<dots> \<le> ?lhs" by(rule ccpo_Sup_upper[OF chain1])(simp add: \<open>x \<in> Y\<close>)
Andreas@62652
   155
    finally show "y \<le> ?lhs" .
Andreas@62652
   156
  qed
Andreas@62652
   157
qed
Andreas@62652
   158
Andreas@62652
   159
end
Andreas@62652
   160
Andreas@62652
   161
lemma Sup_image_mono_le:
Andreas@62652
   162
  fixes le_b (infix "\<sqsubseteq>" 60) and Sup_b ("\<Or>_" [900] 900)
Andreas@62652
   163
  assumes ccpo: "class.ccpo Sup_b op \<sqsubseteq> lt_b"
Andreas@62652
   164
  assumes chain: "Complete_Partial_Order.chain op \<sqsubseteq> Y"
Andreas@62652
   165
  and mono: "\<And>x y. \<lbrakk> x \<sqsubseteq> y; x \<in> Y \<rbrakk> \<Longrightarrow> f x \<le> f y"
Andreas@62652
   166
  shows "Sup (f ` Y) \<le> f (\<Or>Y)"
Andreas@62652
   167
proof(rule ccpo_Sup_least)
Andreas@62652
   168
  show "Complete_Partial_Order.chain op \<le> (f ` Y)"
Andreas@62652
   169
    using chain by(rule chain_imageI)(rule mono)
Andreas@62652
   170
Andreas@62652
   171
  fix x
Andreas@62652
   172
  assume "x \<in> f ` Y"
Andreas@62652
   173
  then obtain y where "y \<in> Y" and "x = f y" by blast note this(2)
wenzelm@62837
   174
  also have "y \<sqsubseteq> \<Or>Y" using ccpo chain \<open>y \<in> Y\<close> by(rule ccpo.ccpo_Sup_upper)
wenzelm@62837
   175
  hence "f y \<le> f (\<Or>Y)" using \<open>y \<in> Y\<close> by(rule mono)
Andreas@62652
   176
  finally show "x \<le> \<dots>" .
Andreas@62652
   177
qed
Andreas@62652
   178
Andreas@62652
   179
lemma swap_Sup:
Andreas@62652
   180
  fixes le_b (infix "\<sqsubseteq>" 60)
Andreas@62652
   181
  assumes Y: "Complete_Partial_Order.chain op \<sqsubseteq> Y"
Andreas@62652
   182
  and Z: "Complete_Partial_Order.chain (fun_ord op \<le>) Z"
Andreas@62652
   183
  and mono: "\<And>f. f \<in> Z \<Longrightarrow> monotone op \<sqsubseteq> op \<le> f"
Andreas@62652
   184
  shows "\<Squnion>((\<lambda>x. \<Squnion>(x ` Y)) ` Z) = \<Squnion>((\<lambda>x. \<Squnion>((\<lambda>f. f x) ` Z)) ` Y)"
Andreas@62652
   185
  (is "?lhs = ?rhs")
Andreas@62652
   186
proof(cases "Y = {}")
Andreas@62652
   187
  case True
Andreas@62652
   188
  then show ?thesis
Andreas@62652
   189
    by (simp add: image_constant_conv cong del: strong_SUP_cong)
Andreas@62652
   190
next
Andreas@62652
   191
  case False
Andreas@62652
   192
  have chain1: "\<And>f. f \<in> Z \<Longrightarrow> Complete_Partial_Order.chain op \<le> (f ` Y)"
Andreas@62652
   193
    by(rule chain_imageI[OF Y])(rule monotoneD[OF mono])
Andreas@62652
   194
  have chain2: "Complete_Partial_Order.chain op \<le> ((\<lambda>x. \<Squnion>(x ` Y)) ` Z)" using Z
Andreas@62652
   195
  proof(rule chain_imageI)
Andreas@62652
   196
    fix f g
Andreas@62652
   197
    assume "f \<in> Z" "g \<in> Z"
Andreas@62652
   198
      and "fun_ord op \<le> f g"
wenzelm@62837
   199
    from chain1[OF \<open>f \<in> Z\<close>] show "\<Squnion>(f ` Y) \<le> \<Squnion>(g ` Y)"
Andreas@62652
   200
    proof(rule ccpo_Sup_least)
Andreas@62652
   201
      fix x
Andreas@62652
   202
      assume "x \<in> f ` Y"
Andreas@62652
   203
      then obtain y where "y \<in> Y" "x = f y" by blast note this(2)
wenzelm@62837
   204
      also have "\<dots> \<le> g y" using \<open>fun_ord op \<le> f g\<close> by(simp add: fun_ord_def)
wenzelm@62837
   205
      also have "\<dots> \<le> \<Squnion>(g ` Y)" using chain1[OF \<open>g \<in> Z\<close>]
wenzelm@62837
   206
        by(rule ccpo_Sup_upper)(simp add: \<open>y \<in> Y\<close>)
Andreas@62652
   207
      finally show "x \<le> \<Squnion>(g ` Y)" .
Andreas@62652
   208
    qed
Andreas@62652
   209
  qed
Andreas@62652
   210
  have chain3: "\<And>x. Complete_Partial_Order.chain op \<le> ((\<lambda>f. f x) ` Z)"
Andreas@62652
   211
    using Z by(rule chain_imageI)(simp add: fun_ord_def)
Andreas@62652
   212
  have chain4: "Complete_Partial_Order.chain op \<le> ((\<lambda>x. \<Squnion>((\<lambda>f. f x) ` Z)) ` Y)"
Andreas@62652
   213
    using Y
Andreas@62652
   214
  proof(rule chain_imageI)
Andreas@62652
   215
    fix f x y
Andreas@62652
   216
    assume "x \<sqsubseteq> y"
Andreas@62652
   217
    show "\<Squnion>((\<lambda>f. f x) ` Z) \<le> \<Squnion>((\<lambda>f. f y) ` Z)" (is "_ \<le> ?rhs") using chain3
Andreas@62652
   218
    proof(rule ccpo_Sup_least)
Andreas@62652
   219
      fix x'
Andreas@62652
   220
      assume "x' \<in> (\<lambda>f. f x) ` Z"
Andreas@62652
   221
      then obtain f where "f \<in> Z" "x' = f x" by blast note this(2)
wenzelm@62837
   222
      also have "f x \<le> f y" using \<open>f \<in> Z\<close> \<open>x \<sqsubseteq> y\<close> by(rule monotoneD[OF mono])
Andreas@62652
   223
      also have "f y \<le> ?rhs" using chain3
wenzelm@62837
   224
        by(rule ccpo_Sup_upper)(simp add: \<open>f \<in> Z\<close>)
Andreas@62652
   225
      finally show "x' \<le> ?rhs" .
Andreas@62652
   226
    qed
Andreas@62652
   227
  qed
Andreas@62652
   228
Andreas@62652
   229
  from chain2 have "?lhs \<le> ?rhs"
Andreas@62652
   230
  proof(rule ccpo_Sup_least)
Andreas@62652
   231
    fix x
Andreas@62652
   232
    assume "x \<in> (\<lambda>x. \<Squnion>(x ` Y)) ` Z"
Andreas@62652
   233
    then obtain f where "f \<in> Z" "x = \<Squnion>(f ` Y)" by blast note this(2)
wenzelm@62837
   234
    also have "\<dots> \<le> ?rhs" using chain1[OF \<open>f \<in> Z\<close>]
Andreas@62652
   235
    proof(rule ccpo_Sup_least)
Andreas@62652
   236
      fix x'
Andreas@62652
   237
      assume "x' \<in> f ` Y"
Andreas@62652
   238
      then obtain y where "y \<in> Y" "x' = f y" by blast note this(2)
Andreas@62652
   239
      also have "f y \<le> \<Squnion>((\<lambda>f. f y) ` Z)" using chain3
wenzelm@62837
   240
        by(rule ccpo_Sup_upper)(simp add: \<open>f \<in> Z\<close>)
wenzelm@62837
   241
      also have "\<dots> \<le> ?rhs" using chain4 by(rule ccpo_Sup_upper)(simp add: \<open>y \<in> Y\<close>)
Andreas@62652
   242
      finally show "x' \<le> ?rhs" .
Andreas@62652
   243
    qed
Andreas@62652
   244
    finally show "x \<le> ?rhs" .
Andreas@62652
   245
  qed
Andreas@62652
   246
  moreover
Andreas@62652
   247
  have "?rhs \<le> ?lhs" using chain4
Andreas@62652
   248
  proof(rule ccpo_Sup_least)
Andreas@62652
   249
    fix x
Andreas@62652
   250
    assume "x \<in> (\<lambda>x. \<Squnion>((\<lambda>f. f x) ` Z)) ` Y"
Andreas@62652
   251
    then obtain y where "y \<in> Y" "x = \<Squnion>((\<lambda>f. f y) ` Z)" by blast note this(2)
Andreas@62652
   252
    also have "\<dots> \<le> ?lhs" using chain3
Andreas@62652
   253
    proof(rule ccpo_Sup_least)
Andreas@62652
   254
      fix x'
Andreas@62652
   255
      assume "x' \<in> (\<lambda>f. f y) ` Z"
Andreas@62652
   256
      then obtain f where "f \<in> Z" "x' = f y" by blast note this(2)
wenzelm@62837
   257
      also have "f y \<le> \<Squnion>(f ` Y)" using chain1[OF \<open>f \<in> Z\<close>]
wenzelm@62837
   258
        by(rule ccpo_Sup_upper)(simp add: \<open>y \<in> Y\<close>)
Andreas@62652
   259
      also have "\<dots> \<le> ?lhs" using chain2
wenzelm@62837
   260
        by(rule ccpo_Sup_upper)(simp add: \<open>f \<in> Z\<close>)
Andreas@62652
   261
      finally show "x' \<le> ?lhs" .
Andreas@62652
   262
    qed
Andreas@62652
   263
    finally show "x \<le> ?lhs" .
Andreas@62652
   264
  qed
Andreas@62652
   265
  ultimately show "?lhs = ?rhs" by(rule antisym)
Andreas@62652
   266
qed
Andreas@62652
   267
Andreas@62652
   268
lemma fixp_mono:
Andreas@62652
   269
  assumes fg: "fun_ord op \<le> f g"
Andreas@62652
   270
  and f: "monotone op \<le> op \<le> f"
Andreas@62652
   271
  and g: "monotone op \<le> op \<le> g"
Andreas@62652
   272
  shows "ccpo_class.fixp f \<le> ccpo_class.fixp g"
Andreas@62652
   273
unfolding fixp_def
Andreas@62652
   274
proof(rule ccpo_Sup_least)
Andreas@62652
   275
  fix x
Andreas@62652
   276
  assume "x \<in> ccpo_class.iterates f"
Andreas@62652
   277
  thus "x \<le> \<Squnion>ccpo_class.iterates g"
Andreas@62652
   278
  proof induction
Andreas@62652
   279
    case (step x)
Andreas@62652
   280
    from f step.IH have "f x \<le> f (\<Squnion>ccpo_class.iterates g)" by(rule monotoneD)
Andreas@62652
   281
    also have "\<dots> \<le> g (\<Squnion>ccpo_class.iterates g)" using fg by(simp add: fun_ord_def)
Andreas@62652
   282
    also have "\<dots> = \<Squnion>ccpo_class.iterates g" by(fold fixp_def fixp_unfold[OF g]) simp
Andreas@62652
   283
    finally show ?case .
Andreas@62652
   284
  qed(blast intro: ccpo_Sup_least)
Andreas@62652
   285
qed(rule chain_iterates[OF f])
Andreas@62652
   286
Andreas@62652
   287
context fixes ordb :: "'b \<Rightarrow> 'b \<Rightarrow> bool" (infix "\<sqsubseteq>" 60) begin
Andreas@62652
   288
Andreas@62652
   289
lemma iterates_mono:
Andreas@62652
   290
  assumes f: "f \<in> ccpo.iterates (fun_lub Sup) (fun_ord op \<le>) F"
Andreas@62652
   291
  and mono: "\<And>f. monotone op \<sqsubseteq> op \<le> f \<Longrightarrow> monotone op \<sqsubseteq> op \<le> (F f)"
Andreas@62652
   292
  shows "monotone op \<sqsubseteq> op \<le> f"
Andreas@62652
   293
using f
Andreas@62652
   294
by(induction rule: ccpo.iterates.induct[OF ccpo_fun, consumes 1, case_names step Sup])(blast intro: mono mono_lub)+
Andreas@62652
   295
Andreas@62652
   296
lemma fixp_preserves_mono:
Andreas@62652
   297
  assumes mono: "\<And>x. monotone (fun_ord op \<le>) op \<le> (\<lambda>f. F f x)"
Andreas@62652
   298
  and mono2: "\<And>f. monotone op \<sqsubseteq> op \<le> f \<Longrightarrow> monotone op \<sqsubseteq> op \<le> (F f)"
Andreas@62652
   299
  shows "monotone op \<sqsubseteq> op \<le> (ccpo.fixp (fun_lub Sup) (fun_ord op \<le>) F)"
Andreas@62652
   300
  (is "monotone _ _ ?fixp")
Andreas@62652
   301
proof(rule monotoneI)
Andreas@62652
   302
  have mono: "monotone (fun_ord op \<le>) (fun_ord op \<le>) F"
Andreas@62652
   303
    by(rule monotoneI)(auto simp add: fun_ord_def intro: monotoneD[OF mono])
Andreas@62652
   304
  let ?iter = "ccpo.iterates (fun_lub Sup) (fun_ord op \<le>) F"
Andreas@62652
   305
  have chain: "\<And>x. Complete_Partial_Order.chain op \<le> ((\<lambda>f. f x) ` ?iter)"
Andreas@62652
   306
    by(rule chain_imageI[OF ccpo.chain_iterates[OF ccpo_fun mono]])(simp add: fun_ord_def)
Andreas@62652
   307
Andreas@62652
   308
  fix x y
Andreas@62652
   309
  assume "x \<sqsubseteq> y"
Andreas@62652
   310
  show "?fixp x \<le> ?fixp y"
wenzelm@63170
   311
    apply (simp only: ccpo.fixp_def[OF ccpo_fun] fun_lub_apply)
wenzelm@63170
   312
    using chain
Andreas@62652
   313
  proof(rule ccpo_Sup_least)
Andreas@62652
   314
    fix x'
Andreas@62652
   315
    assume "x' \<in> (\<lambda>f. f x) ` ?iter"
Andreas@62652
   316
    then obtain f where "f \<in> ?iter" "x' = f x" by blast note this(2)
Andreas@62652
   317
    also have "f x \<le> f y"
wenzelm@62837
   318
      by(rule monotoneD[OF iterates_mono[OF \<open>f \<in> ?iter\<close> mono2]])(blast intro: \<open>x \<sqsubseteq> y\<close>)+
Andreas@62652
   319
    also have "f y \<le> \<Squnion>((\<lambda>f. f y) ` ?iter)" using chain
wenzelm@62837
   320
      by(rule ccpo_Sup_upper)(simp add: \<open>f \<in> ?iter\<close>)
Andreas@62652
   321
    finally show "x' \<le> \<dots>" .
Andreas@62652
   322
  qed
Andreas@62652
   323
qed
Andreas@62652
   324
Andreas@62652
   325
end
Andreas@62652
   326
Andreas@62652
   327
end
Andreas@62652
   328
Andreas@62652
   329
lemma monotone2monotone:
Andreas@62652
   330
  assumes 2: "\<And>x. monotone ordb ordc (\<lambda>y. f x y)"
Andreas@62652
   331
  and t: "monotone orda ordb (\<lambda>x. t x)"
Andreas@62652
   332
  and 1: "\<And>y. monotone orda ordc (\<lambda>x. f x y)"
Andreas@62652
   333
  and trans: "transp ordc"
Andreas@62652
   334
  shows "monotone orda ordc (\<lambda>x. f x (t x))"
Andreas@62652
   335
by(blast intro: monotoneI transpD[OF trans] monotoneD[OF t] monotoneD[OF 2] monotoneD[OF 1])
Andreas@62652
   336
wenzelm@62837
   337
subsection \<open>Continuity\<close>
Andreas@62652
   338
Andreas@62652
   339
definition cont :: "('a set \<Rightarrow> 'a) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> ('b set \<Rightarrow> 'b) \<Rightarrow> ('b \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> bool"
Andreas@62652
   340
where
Andreas@62652
   341
  "cont luba orda lubb ordb f \<longleftrightarrow> 
Andreas@62652
   342
  (\<forall>Y. Complete_Partial_Order.chain orda Y \<longrightarrow> Y \<noteq> {} \<longrightarrow> f (luba Y) = lubb (f ` Y))"
Andreas@62652
   343
Andreas@62652
   344
definition mcont :: "('a set \<Rightarrow> 'a) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> ('b set \<Rightarrow> 'b) \<Rightarrow> ('b \<Rightarrow> 'b \<Rightarrow> bool) \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> bool"
Andreas@62652
   345
where
Andreas@62652
   346
  "mcont luba orda lubb ordb f \<longleftrightarrow>
Andreas@62652
   347
   monotone orda ordb f \<and> cont luba orda lubb ordb f"
Andreas@62652
   348
wenzelm@62837
   349
subsubsection \<open>Theorem collection \<open>cont_intro\<close>\<close>
Andreas@62652
   350
Andreas@62652
   351
named_theorems cont_intro "continuity and admissibility intro rules"
wenzelm@62837
   352
ML \<open>
Andreas@62652
   353
(* apply cont_intro rules as intro and try to solve 
Andreas@62652
   354
   the remaining of the emerging subgoals with simp *)
Andreas@62652
   355
fun cont_intro_tac ctxt =
Andreas@62652
   356
  REPEAT_ALL_NEW (resolve_tac ctxt (rev (Named_Theorems.get ctxt @{named_theorems cont_intro})))
Andreas@62652
   357
  THEN_ALL_NEW (SOLVED' (simp_tac ctxt))
Andreas@62652
   358
Andreas@62652
   359
fun cont_intro_simproc ctxt ct =
Andreas@62652
   360
  let
Andreas@62652
   361
    fun mk_stmt t = t
Andreas@62652
   362
      |> HOLogic.mk_Trueprop
Andreas@62652
   363
      |> Thm.cterm_of ctxt
Andreas@62652
   364
      |> Goal.init
Andreas@62652
   365
    fun mk_thm t =
Andreas@62652
   366
      case SINGLE (cont_intro_tac ctxt 1) (mk_stmt t) of
Andreas@62652
   367
        SOME thm => SOME (Goal.finish ctxt thm RS @{thm Eq_TrueI})
Andreas@62652
   368
      | NONE => NONE
Andreas@62652
   369
  in
Andreas@62652
   370
    case Thm.term_of ct of
Andreas@62652
   371
      t as Const (@{const_name ccpo.admissible}, _) $ _ $ _ $ _ => mk_thm t
Andreas@62652
   372
    | t as Const (@{const_name mcont}, _) $ _ $ _ $ _ $ _ $ _ => mk_thm t
Andreas@62652
   373
    | t as Const (@{const_name monotone}, _) $ _ $ _ $ _ => mk_thm t
Andreas@62652
   374
    | _ => NONE
Andreas@62652
   375
  end
Andreas@62652
   376
  handle THM _ => NONE 
Andreas@62652
   377
  | TYPE _ => NONE
wenzelm@62837
   378
\<close>
Andreas@62652
   379
Andreas@62652
   380
simproc_setup "cont_intro"
Andreas@62652
   381
  ( "ccpo.admissible lub ord P"
Andreas@62652
   382
  | "mcont lub ord lub' ord' f"
Andreas@62652
   383
  | "monotone ord ord' f"
wenzelm@62837
   384
  ) = \<open>K cont_intro_simproc\<close>
Andreas@62652
   385
Andreas@62652
   386
lemmas [cont_intro] =
Andreas@62652
   387
  call_mono
Andreas@62652
   388
  let_mono
Andreas@62652
   389
  if_mono
Andreas@62652
   390
  option.const_mono
Andreas@62652
   391
  tailrec.const_mono
Andreas@62652
   392
  bind_mono
Andreas@62652
   393
Andreas@62652
   394
declare if_mono[simp]
Andreas@62652
   395
Andreas@62652
   396
lemma monotone_id' [cont_intro]: "monotone ord ord (\<lambda>x. x)"
Andreas@62652
   397
by(simp add: monotone_def)
Andreas@62652
   398
Andreas@62652
   399
lemma monotone_applyI:
Andreas@62652
   400
  "monotone orda ordb F \<Longrightarrow> monotone (fun_ord orda) ordb (\<lambda>f. F (f x))"
Andreas@62652
   401
by(rule monotoneI)(auto simp add: fun_ord_def dest: monotoneD)
Andreas@62652
   402
Andreas@62652
   403
lemma monotone_if_fun [partial_function_mono]:
Andreas@62652
   404
  "\<lbrakk> monotone (fun_ord orda) (fun_ord ordb) F; monotone (fun_ord orda) (fun_ord ordb) G \<rbrakk>
Andreas@62652
   405
  \<Longrightarrow> monotone (fun_ord orda) (fun_ord ordb) (\<lambda>f n. if c n then F f n else G f n)"
Andreas@62652
   406
by(simp add: monotone_def fun_ord_def)
Andreas@62652
   407
Andreas@62652
   408
lemma monotone_fun_apply_fun [partial_function_mono]: 
Andreas@62652
   409
  "monotone (fun_ord (fun_ord ord)) (fun_ord ord) (\<lambda>f n. f t (g n))"
Andreas@62652
   410
by(rule monotoneI)(simp add: fun_ord_def)
Andreas@62652
   411
Andreas@62652
   412
lemma monotone_fun_ord_apply: 
Andreas@62652
   413
  "monotone orda (fun_ord ordb) f \<longleftrightarrow> (\<forall>x. monotone orda ordb (\<lambda>y. f y x))"
Andreas@62652
   414
by(auto simp add: monotone_def fun_ord_def)
Andreas@62652
   415
Andreas@62652
   416
context preorder begin
Andreas@62652
   417
Andreas@62652
   418
lemma transp_le [simp, cont_intro]: "transp op \<le>"
Andreas@62652
   419
by(rule transpI)(rule order_trans)
Andreas@62652
   420
Andreas@62652
   421
lemma monotone_const [simp, cont_intro]: "monotone ord op \<le> (\<lambda>_. c)"
Andreas@62652
   422
by(rule monotoneI) simp
Andreas@62652
   423
Andreas@62652
   424
end
Andreas@62652
   425
Andreas@62652
   426
lemma transp_le [cont_intro, simp]:
Andreas@62652
   427
  "class.preorder ord (mk_less ord) \<Longrightarrow> transp ord"
Andreas@62652
   428
by(rule preorder.transp_le)
Andreas@62652
   429
Andreas@62652
   430
context partial_function_definitions begin
Andreas@62652
   431
Andreas@62652
   432
declare const_mono [cont_intro, simp]
Andreas@62652
   433
Andreas@62652
   434
lemma transp_le [cont_intro, simp]: "transp leq"
Andreas@62652
   435
by(rule transpI)(rule leq_trans)
Andreas@62652
   436
Andreas@62652
   437
lemma preorder [cont_intro, simp]: "class.preorder leq (mk_less leq)"
Andreas@62652
   438
by(unfold_locales)(auto simp add: mk_less_def intro: leq_refl leq_trans)
Andreas@62652
   439
Andreas@62652
   440
declare ccpo[cont_intro, simp]
Andreas@62652
   441
Andreas@62652
   442
end
Andreas@62652
   443
Andreas@62652
   444
lemma contI [intro?]:
Andreas@62652
   445
  "(\<And>Y. \<lbrakk> Complete_Partial_Order.chain orda Y; Y \<noteq> {} \<rbrakk> \<Longrightarrow> f (luba Y) = lubb (f ` Y)) 
Andreas@62652
   446
  \<Longrightarrow> cont luba orda lubb ordb f"
Andreas@62652
   447
unfolding cont_def by blast
Andreas@62652
   448
Andreas@62652
   449
lemma contD:
Andreas@62652
   450
  "\<lbrakk> cont luba orda lubb ordb f; Complete_Partial_Order.chain orda Y; Y \<noteq> {} \<rbrakk> 
Andreas@62652
   451
  \<Longrightarrow> f (luba Y) = lubb (f ` Y)"
Andreas@62652
   452
unfolding cont_def by blast
Andreas@62652
   453
Andreas@62652
   454
lemma cont_id [simp, cont_intro]: "\<And>Sup. cont Sup ord Sup ord id"
Andreas@62652
   455
by(rule contI) simp
Andreas@62652
   456
Andreas@62652
   457
lemma cont_id' [simp, cont_intro]: "\<And>Sup. cont Sup ord Sup ord (\<lambda>x. x)"
Andreas@62652
   458
using cont_id[unfolded id_def] .
Andreas@62652
   459
Andreas@62652
   460
lemma cont_applyI [cont_intro]:
Andreas@62652
   461
  assumes cont: "cont luba orda lubb ordb g"
Andreas@62652
   462
  shows "cont (fun_lub luba) (fun_ord orda) lubb ordb (\<lambda>f. g (f x))"
Andreas@62652
   463
by(rule contI)(drule chain_fun_ordD[where x=x], simp add: fun_lub_apply image_image contD[OF cont])
Andreas@62652
   464
Andreas@62652
   465
lemma call_cont: "cont (fun_lub lub) (fun_ord ord) lub ord (\<lambda>f. f t)"
Andreas@62652
   466
by(simp add: cont_def fun_lub_apply)
Andreas@62652
   467
Andreas@62652
   468
lemma cont_if [cont_intro]:
Andreas@62652
   469
  "\<lbrakk> cont luba orda lubb ordb f; cont luba orda lubb ordb g \<rbrakk>
Andreas@62652
   470
  \<Longrightarrow> cont luba orda lubb ordb (\<lambda>x. if c then f x else g x)"
Andreas@62652
   471
by(cases c) simp_all
Andreas@62652
   472
Andreas@62652
   473
lemma mcontI [intro?]:
Andreas@62652
   474
   "\<lbrakk> monotone orda ordb f; cont luba orda lubb ordb f \<rbrakk> \<Longrightarrow> mcont luba orda lubb ordb f"
Andreas@62652
   475
by(simp add: mcont_def)
Andreas@62652
   476
Andreas@62652
   477
lemma mcont_mono: "mcont luba orda lubb ordb f \<Longrightarrow> monotone orda ordb f"
Andreas@62652
   478
by(simp add: mcont_def)
Andreas@62652
   479
Andreas@62652
   480
lemma mcont_cont [simp]: "mcont luba orda lubb ordb f \<Longrightarrow> cont luba orda lubb ordb f"
Andreas@62652
   481
by(simp add: mcont_def)
Andreas@62652
   482
Andreas@62652
   483
lemma mcont_monoD:
Andreas@62652
   484
  "\<lbrakk> mcont luba orda lubb ordb f; orda x y \<rbrakk> \<Longrightarrow> ordb (f x) (f y)"
Andreas@62652
   485
by(auto simp add: mcont_def dest: monotoneD)
Andreas@62652
   486
Andreas@62652
   487
lemma mcont_contD:
Andreas@62652
   488
  "\<lbrakk> mcont luba orda lubb ordb f; Complete_Partial_Order.chain orda Y; Y \<noteq> {} \<rbrakk>
Andreas@62652
   489
  \<Longrightarrow> f (luba Y) = lubb (f ` Y)"
Andreas@62652
   490
by(auto simp add: mcont_def dest: contD)
Andreas@62652
   491
Andreas@62652
   492
lemma mcont_call [cont_intro, simp]:
Andreas@62652
   493
  "mcont (fun_lub lub) (fun_ord ord) lub ord (\<lambda>f. f t)"
Andreas@62652
   494
by(simp add: mcont_def call_mono call_cont)
Andreas@62652
   495
Andreas@62652
   496
lemma mcont_id' [cont_intro, simp]: "mcont lub ord lub ord (\<lambda>x. x)"
Andreas@62652
   497
by(simp add: mcont_def monotone_id')
Andreas@62652
   498
Andreas@62652
   499
lemma mcont_applyI:
Andreas@62652
   500
  "mcont luba orda lubb ordb (\<lambda>x. F x) \<Longrightarrow> mcont (fun_lub luba) (fun_ord orda) lubb ordb (\<lambda>f. F (f x))"
Andreas@62652
   501
by(simp add: mcont_def monotone_applyI cont_applyI)
Andreas@62652
   502
Andreas@62652
   503
lemma mcont_if [cont_intro, simp]:
Andreas@62652
   504
  "\<lbrakk> mcont luba orda lubb ordb (\<lambda>x. f x); mcont luba orda lubb ordb (\<lambda>x. g x) \<rbrakk>
Andreas@62652
   505
  \<Longrightarrow> mcont luba orda lubb ordb (\<lambda>x. if c then f x else g x)"
Andreas@62652
   506
by(simp add: mcont_def cont_if)
Andreas@62652
   507
Andreas@62652
   508
lemma cont_fun_lub_apply: 
Andreas@62652
   509
  "cont luba orda (fun_lub lubb) (fun_ord ordb) f \<longleftrightarrow> (\<forall>x. cont luba orda lubb ordb (\<lambda>y. f y x))"
Andreas@62652
   510
by(simp add: cont_def fun_lub_def fun_eq_iff)(auto simp add: image_def)
Andreas@62652
   511
Andreas@62652
   512
lemma mcont_fun_lub_apply: 
Andreas@62652
   513
  "mcont luba orda (fun_lub lubb) (fun_ord ordb) f \<longleftrightarrow> (\<forall>x. mcont luba orda lubb ordb (\<lambda>y. f y x))"
Andreas@62652
   514
by(auto simp add: monotone_fun_ord_apply cont_fun_lub_apply mcont_def)
Andreas@62652
   515
Andreas@62652
   516
context ccpo begin
Andreas@62652
   517
Andreas@62652
   518
lemma cont_const [simp, cont_intro]: "cont luba orda Sup op \<le> (\<lambda>x. c)"
Andreas@62652
   519
by (rule contI) (simp add: image_constant_conv cong del: strong_SUP_cong)
Andreas@62652
   520
Andreas@62652
   521
lemma mcont_const [cont_intro, simp]:
Andreas@62652
   522
  "mcont luba orda Sup op \<le> (\<lambda>x. c)"
Andreas@62652
   523
by(simp add: mcont_def)
Andreas@62652
   524
Andreas@62652
   525
lemma cont_apply:
Andreas@62652
   526
  assumes 2: "\<And>x. cont lubb ordb Sup op \<le> (\<lambda>y. f x y)"
Andreas@62652
   527
  and t: "cont luba orda lubb ordb (\<lambda>x. t x)"
Andreas@62652
   528
  and 1: "\<And>y. cont luba orda Sup op \<le> (\<lambda>x. f x y)"
Andreas@62652
   529
  and mono: "monotone orda ordb (\<lambda>x. t x)"
Andreas@62652
   530
  and mono2: "\<And>x. monotone ordb op \<le> (\<lambda>y. f x y)"
Andreas@62652
   531
  and mono1: "\<And>y. monotone orda op \<le> (\<lambda>x. f x y)"
Andreas@62652
   532
  shows "cont luba orda Sup op \<le> (\<lambda>x. f x (t x))"
Andreas@62652
   533
proof
Andreas@62652
   534
  fix Y
Andreas@62652
   535
  assume chain: "Complete_Partial_Order.chain orda Y" and "Y \<noteq> {}"
Andreas@62652
   536
  moreover from chain have chain': "Complete_Partial_Order.chain ordb (t ` Y)"
Andreas@62652
   537
    by(rule chain_imageI)(rule monotoneD[OF mono])
Andreas@62652
   538
  ultimately show "f (luba Y) (t (luba Y)) = \<Squnion>((\<lambda>x. f x (t x)) ` Y)"
Andreas@62652
   539
    by(simp add: contD[OF 1] contD[OF t] contD[OF 2] image_image)
Andreas@62652
   540
      (rule diag_Sup[OF chain], auto intro: monotone2monotone[OF mono2 mono monotone_const transpI] monotoneD[OF mono1])
Andreas@62652
   541
qed
Andreas@62652
   542
Andreas@62652
   543
lemma mcont2mcont':
Andreas@62652
   544
  "\<lbrakk> \<And>x. mcont lub' ord' Sup op \<le> (\<lambda>y. f x y);
Andreas@62652
   545
     \<And>y. mcont lub ord Sup op \<le> (\<lambda>x. f x y);
Andreas@62652
   546
     mcont lub ord lub' ord' (\<lambda>y. t y) \<rbrakk>
Andreas@62652
   547
  \<Longrightarrow> mcont lub ord Sup op \<le> (\<lambda>x. f x (t x))"
Andreas@62652
   548
unfolding mcont_def by(blast intro: transp_le monotone2monotone cont_apply)
Andreas@62652
   549
Andreas@62652
   550
lemma mcont2mcont:
Andreas@62652
   551
  "\<lbrakk>mcont lub' ord' Sup op \<le> (\<lambda>x. f x); mcont lub ord lub' ord' (\<lambda>x. t x)\<rbrakk> 
Andreas@62652
   552
  \<Longrightarrow> mcont lub ord Sup op \<le> (\<lambda>x. f (t x))"
Andreas@62652
   553
by(rule mcont2mcont'[OF _ mcont_const]) 
Andreas@62652
   554
Andreas@62652
   555
context
Andreas@62652
   556
  fixes ord :: "'b \<Rightarrow> 'b \<Rightarrow> bool" (infix "\<sqsubseteq>" 60) 
Andreas@62652
   557
  and lub :: "'b set \<Rightarrow> 'b" ("\<Or>_" [900] 900)
Andreas@62652
   558
begin
Andreas@62652
   559
Andreas@62652
   560
lemma cont_fun_lub_Sup:
Andreas@62652
   561
  assumes chainM: "Complete_Partial_Order.chain (fun_ord op \<le>) M"
Andreas@62652
   562
  and mcont [rule_format]: "\<forall>f\<in>M. mcont lub op \<sqsubseteq> Sup op \<le> f"
Andreas@62652
   563
  shows "cont lub op \<sqsubseteq> Sup op \<le> (fun_lub Sup M)"
Andreas@62652
   564
proof(rule contI)
Andreas@62652
   565
  fix Y
Andreas@62652
   566
  assume chain: "Complete_Partial_Order.chain op \<sqsubseteq> Y"
Andreas@62652
   567
    and Y: "Y \<noteq> {}"
Andreas@62652
   568
  from swap_Sup[OF chain chainM mcont[THEN mcont_mono]]
Andreas@62652
   569
  show "fun_lub Sup M (\<Or>Y) = \<Squnion>(fun_lub Sup M ` Y)"
Andreas@62652
   570
    by(simp add: mcont_contD[OF mcont chain Y] fun_lub_apply cong: image_cong)
Andreas@62652
   571
qed
Andreas@62652
   572
Andreas@62652
   573
lemma mcont_fun_lub_Sup:
Andreas@62652
   574
  "\<lbrakk> Complete_Partial_Order.chain (fun_ord op \<le>) M;
Andreas@62652
   575
    \<forall>f\<in>M. mcont lub ord Sup op \<le> f \<rbrakk>
Andreas@62652
   576
  \<Longrightarrow> mcont lub op \<sqsubseteq> Sup op \<le> (fun_lub Sup M)"
Andreas@62652
   577
by(simp add: mcont_def cont_fun_lub_Sup mono_lub)
Andreas@62652
   578
Andreas@62652
   579
lemma iterates_mcont:
Andreas@62652
   580
  assumes f: "f \<in> ccpo.iterates (fun_lub Sup) (fun_ord op \<le>) F"
Andreas@62652
   581
  and mono: "\<And>f. mcont lub op \<sqsubseteq> Sup op \<le> f \<Longrightarrow> mcont lub op \<sqsubseteq> Sup op \<le> (F f)"
Andreas@62652
   582
  shows "mcont lub op \<sqsubseteq> Sup op \<le> f"
Andreas@62652
   583
using f
Andreas@62652
   584
by(induction rule: ccpo.iterates.induct[OF ccpo_fun, consumes 1, case_names step Sup])(blast intro: mono mcont_fun_lub_Sup)+
Andreas@62652
   585
Andreas@62652
   586
lemma fixp_preserves_mcont:
Andreas@62652
   587
  assumes mono: "\<And>x. monotone (fun_ord op \<le>) op \<le> (\<lambda>f. F f x)"
Andreas@62652
   588
  and mcont: "\<And>f. mcont lub op \<sqsubseteq> Sup op \<le> f \<Longrightarrow> mcont lub op \<sqsubseteq> Sup op \<le> (F f)"
Andreas@62652
   589
  shows "mcont lub op \<sqsubseteq> Sup op \<le> (ccpo.fixp (fun_lub Sup) (fun_ord op \<le>) F)"
Andreas@62652
   590
  (is "mcont _ _ _ _ ?fixp")
Andreas@62652
   591
unfolding mcont_def
Andreas@62652
   592
proof(intro conjI monotoneI contI)
Andreas@62652
   593
  have mono: "monotone (fun_ord op \<le>) (fun_ord op \<le>) F"
Andreas@62652
   594
    by(rule monotoneI)(auto simp add: fun_ord_def intro: monotoneD[OF mono])
Andreas@62652
   595
  let ?iter = "ccpo.iterates (fun_lub Sup) (fun_ord op \<le>) F"
Andreas@62652
   596
  have chain: "\<And>x. Complete_Partial_Order.chain op \<le> ((\<lambda>f. f x) ` ?iter)"
Andreas@62652
   597
    by(rule chain_imageI[OF ccpo.chain_iterates[OF ccpo_fun mono]])(simp add: fun_ord_def)
Andreas@62652
   598
Andreas@62652
   599
  {
Andreas@62652
   600
    fix x y
Andreas@62652
   601
    assume "x \<sqsubseteq> y"
Andreas@62652
   602
    show "?fixp x \<le> ?fixp y"
wenzelm@63170
   603
      apply (simp only: ccpo.fixp_def[OF ccpo_fun] fun_lub_apply)
wenzelm@63170
   604
      using chain
Andreas@62652
   605
    proof(rule ccpo_Sup_least)
Andreas@62652
   606
      fix x'
Andreas@62652
   607
      assume "x' \<in> (\<lambda>f. f x) ` ?iter"
Andreas@62652
   608
      then obtain f where "f \<in> ?iter" "x' = f x" by blast note this(2)
wenzelm@62837
   609
      also from _ \<open>x \<sqsubseteq> y\<close> have "f x \<le> f y"
wenzelm@62837
   610
        by(rule mcont_monoD[OF iterates_mcont[OF \<open>f \<in> ?iter\<close> mcont]])
Andreas@62652
   611
      also have "f y \<le> \<Squnion>((\<lambda>f. f y) ` ?iter)" using chain
wenzelm@62837
   612
        by(rule ccpo_Sup_upper)(simp add: \<open>f \<in> ?iter\<close>)
Andreas@62652
   613
      finally show "x' \<le> \<dots>" .
Andreas@62652
   614
    qed
Andreas@62652
   615
  next
Andreas@62652
   616
    fix Y
Andreas@62652
   617
    assume chain: "Complete_Partial_Order.chain op \<sqsubseteq> Y"
Andreas@62652
   618
      and Y: "Y \<noteq> {}"
Andreas@62652
   619
    { fix f
Andreas@62652
   620
      assume "f \<in> ?iter"
Andreas@62652
   621
      hence "f (\<Or>Y) = \<Squnion>(f ` Y)"
Andreas@62652
   622
        using mcont chain Y by(rule mcont_contD[OF iterates_mcont]) }
Andreas@62652
   623
    moreover have "\<Squnion>((\<lambda>f. \<Squnion>(f ` Y)) ` ?iter) = \<Squnion>((\<lambda>x. \<Squnion>((\<lambda>f. f x) ` ?iter)) ` Y)"
Andreas@62652
   624
      using chain ccpo.chain_iterates[OF ccpo_fun mono]
Andreas@62652
   625
      by(rule swap_Sup)(rule mcont_mono[OF iterates_mcont[OF _ mcont]])
Andreas@62652
   626
    ultimately show "?fixp (\<Or>Y) = \<Squnion>(?fixp ` Y)" unfolding ccpo.fixp_def[OF ccpo_fun]
Andreas@62652
   627
      by(simp add: fun_lub_apply cong: image_cong)
Andreas@62652
   628
  }
Andreas@62652
   629
qed
Andreas@62652
   630
Andreas@62652
   631
end
Andreas@62652
   632
Andreas@62652
   633
context
Andreas@62652
   634
  fixes F :: "'c \<Rightarrow> 'c" and U :: "'c \<Rightarrow> 'b \<Rightarrow> 'a" and C :: "('b \<Rightarrow> 'a) \<Rightarrow> 'c" and f
Andreas@62652
   635
  assumes mono: "\<And>x. monotone (fun_ord op \<le>) op \<le> (\<lambda>f. U (F (C f)) x)"
Andreas@62652
   636
  and eq: "f \<equiv> C (ccpo.fixp (fun_lub Sup) (fun_ord op \<le>) (\<lambda>f. U (F (C f))))"
Andreas@62652
   637
  and inverse: "\<And>f. U (C f) = f"
Andreas@62652
   638
begin
Andreas@62652
   639
Andreas@62652
   640
lemma fixp_preserves_mono_uc:
Andreas@62652
   641
  assumes mono2: "\<And>f. monotone ord op \<le> (U f) \<Longrightarrow> monotone ord op \<le> (U (F f))"
Andreas@62652
   642
  shows "monotone ord op \<le> (U f)"
Andreas@62652
   643
using fixp_preserves_mono[OF mono mono2] by(subst eq)(simp add: inverse)
Andreas@62652
   644
Andreas@62652
   645
lemma fixp_preserves_mcont_uc:
Andreas@62652
   646
  assumes mcont: "\<And>f. mcont lubb ordb Sup op \<le> (U f) \<Longrightarrow> mcont lubb ordb Sup op \<le> (U (F f))"
Andreas@62652
   647
  shows "mcont lubb ordb Sup op \<le> (U f)"
Andreas@62652
   648
using fixp_preserves_mcont[OF mono mcont] by(subst eq)(simp add: inverse)
Andreas@62652
   649
Andreas@62652
   650
end
Andreas@62652
   651
Andreas@62652
   652
lemmas fixp_preserves_mono1 = fixp_preserves_mono_uc[of "\<lambda>x. x" _ "\<lambda>x. x", OF _ _ refl]
Andreas@62652
   653
lemmas fixp_preserves_mono2 =
Andreas@62652
   654
  fixp_preserves_mono_uc[of "case_prod" _ "curry", unfolded case_prod_curry curry_case_prod, OF _ _ refl]
Andreas@62652
   655
lemmas fixp_preserves_mono3 =
Andreas@62652
   656
  fixp_preserves_mono_uc[of "\<lambda>f. case_prod (case_prod f)" _ "\<lambda>f. curry (curry f)", unfolded case_prod_curry curry_case_prod, OF _ _ refl]
Andreas@62652
   657
lemmas fixp_preserves_mono4 =
Andreas@62652
   658
  fixp_preserves_mono_uc[of "\<lambda>f. case_prod (case_prod (case_prod f))" _ "\<lambda>f. curry (curry (curry f))", unfolded case_prod_curry curry_case_prod, OF _ _ refl]
Andreas@62652
   659
Andreas@62652
   660
lemmas fixp_preserves_mcont1 = fixp_preserves_mcont_uc[of "\<lambda>x. x" _ "\<lambda>x. x", OF _ _ refl]
Andreas@62652
   661
lemmas fixp_preserves_mcont2 =
Andreas@62652
   662
  fixp_preserves_mcont_uc[of "case_prod" _ "curry", unfolded case_prod_curry curry_case_prod, OF _ _ refl]
Andreas@62652
   663
lemmas fixp_preserves_mcont3 =
Andreas@62652
   664
  fixp_preserves_mcont_uc[of "\<lambda>f. case_prod (case_prod f)" _ "\<lambda>f. curry (curry f)", unfolded case_prod_curry curry_case_prod, OF _ _ refl]
Andreas@62652
   665
lemmas fixp_preserves_mcont4 =
Andreas@62652
   666
  fixp_preserves_mcont_uc[of "\<lambda>f. case_prod (case_prod (case_prod f))" _ "\<lambda>f. curry (curry (curry f))", unfolded case_prod_curry curry_case_prod, OF _ _ refl]
Andreas@62652
   667
Andreas@62652
   668
end
Andreas@62652
   669
Andreas@62652
   670
lemma (in preorder) monotone_if_bot:
Andreas@62652
   671
  fixes bot
Andreas@62652
   672
  assumes mono: "\<And>x y. \<lbrakk> x \<le> y; \<not> (x \<le> bound) \<rbrakk> \<Longrightarrow> ord (f x) (f y)"
Andreas@62652
   673
  and bot: "\<And>x. \<not> x \<le> bound \<Longrightarrow> ord bot (f x)" "ord bot bot"
Andreas@62652
   674
  shows "monotone op \<le> ord (\<lambda>x. if x \<le> bound then bot else f x)"
Andreas@62652
   675
by(rule monotoneI)(auto intro: bot intro: mono order_trans)
Andreas@62652
   676
Andreas@62652
   677
lemma (in ccpo) mcont_if_bot:
Andreas@62652
   678
  fixes bot and lub ("\<Or>_" [900] 900) and ord (infix "\<sqsubseteq>" 60)
Andreas@62652
   679
  assumes ccpo: "class.ccpo lub op \<sqsubseteq> lt"
Andreas@62652
   680
  and mono: "\<And>x y. \<lbrakk> x \<le> y; \<not> x \<le> bound \<rbrakk> \<Longrightarrow> f x \<sqsubseteq> f y"
Andreas@62652
   681
  and cont: "\<And>Y. \<lbrakk> Complete_Partial_Order.chain op \<le> Y; Y \<noteq> {}; \<And>x. x \<in> Y \<Longrightarrow> \<not> x \<le> bound \<rbrakk> \<Longrightarrow> f (\<Squnion>Y) = \<Or>(f ` Y)"
Andreas@62652
   682
  and bot: "\<And>x. \<not> x \<le> bound \<Longrightarrow> bot \<sqsubseteq> f x"
Andreas@62652
   683
  shows "mcont Sup op \<le> lub op \<sqsubseteq> (\<lambda>x. if x \<le> bound then bot else f x)" (is "mcont _ _ _ _ ?g")
Andreas@62652
   684
proof(intro mcontI contI)
Andreas@62652
   685
  interpret c: ccpo lub "op \<sqsubseteq>" lt by(fact ccpo)
Andreas@62652
   686
  show "monotone op \<le> op \<sqsubseteq> ?g" by(rule monotone_if_bot)(simp_all add: mono bot)
Andreas@62652
   687
Andreas@62652
   688
  fix Y
Andreas@62652
   689
  assume chain: "Complete_Partial_Order.chain op \<le> Y" and Y: "Y \<noteq> {}"
Andreas@62652
   690
  show "?g (\<Squnion>Y) = \<Or>(?g ` Y)"
Andreas@62652
   691
  proof(cases "Y \<subseteq> {x. x \<le> bound}")
Andreas@62652
   692
    case True
Andreas@62652
   693
    hence "\<Squnion>Y \<le> bound" using chain by(auto intro: ccpo_Sup_least)
Andreas@62652
   694
    moreover have "Y \<inter> {x. \<not> x \<le> bound} = {}" using True by auto
Andreas@62652
   695
    ultimately show ?thesis using True Y
Andreas@62652
   696
      by (auto simp add: image_constant_conv cong del: c.strong_SUP_cong)
Andreas@62652
   697
  next
Andreas@62652
   698
    case False
Andreas@62652
   699
    let ?Y = "Y \<inter> {x. \<not> x \<le> bound}"
Andreas@62652
   700
    have chain': "Complete_Partial_Order.chain op \<le> ?Y"
Andreas@62652
   701
      using chain by(rule chain_subset) simp
Andreas@62652
   702
Andreas@62652
   703
    from False obtain y where ybound: "\<not> y \<le> bound" and y: "y \<in> Y" by blast
Andreas@62652
   704
    hence "\<not> \<Squnion>Y \<le> bound" by (metis ccpo_Sup_upper chain order.trans)
Andreas@62652
   705
    hence "?g (\<Squnion>Y) = f (\<Squnion>Y)" by simp
Andreas@62652
   706
    also have "\<Squnion>Y \<le> \<Squnion>?Y" using chain
Andreas@62652
   707
    proof(rule ccpo_Sup_least)
Andreas@62652
   708
      fix x
Andreas@62652
   709
      assume x: "x \<in> Y"
Andreas@62652
   710
      show "x \<le> \<Squnion>?Y"
Andreas@62652
   711
      proof(cases "x \<le> bound")
Andreas@62652
   712
        case True
Andreas@62652
   713
        with chainD[OF chain x y] have "x \<le> y" using ybound by(auto intro: order_trans)
Andreas@62652
   714
        thus ?thesis by(rule order_trans)(auto intro: ccpo_Sup_upper[OF chain'] simp add: y ybound)
Andreas@62652
   715
      qed(auto intro: ccpo_Sup_upper[OF chain'] simp add: x)
Andreas@62652
   716
    qed
Andreas@62652
   717
    hence "\<Squnion>Y = \<Squnion>?Y" by(rule antisym)(blast intro: ccpo_Sup_least[OF chain'] ccpo_Sup_upper[OF chain])
Andreas@62652
   718
    hence "f (\<Squnion>Y) = f (\<Squnion>?Y)" by simp
Andreas@62652
   719
    also have "f (\<Squnion>?Y) = \<Or>(f ` ?Y)" using chain' by(rule cont)(insert y ybound, auto)
Andreas@62652
   720
    also have "\<Or>(f ` ?Y) = \<Or>(?g ` Y)"
Andreas@62652
   721
    proof(cases "Y \<inter> {x. x \<le> bound} = {}")
Andreas@62652
   722
      case True
Andreas@62652
   723
      hence "f ` ?Y = ?g ` Y" by auto
Andreas@62652
   724
      thus ?thesis by(rule arg_cong)
Andreas@62652
   725
    next
Andreas@62652
   726
      case False
Andreas@62652
   727
      have chain'': "Complete_Partial_Order.chain op \<sqsubseteq> (insert bot (f ` ?Y))"
Andreas@62652
   728
        using chain by(auto intro!: chainI bot dest: chainD intro: mono)
Andreas@62652
   729
      hence chain''': "Complete_Partial_Order.chain op \<sqsubseteq> (f ` ?Y)" by(rule chain_subset) blast
Andreas@62652
   730
      have "bot \<sqsubseteq> \<Or>(f ` ?Y)" using y ybound by(blast intro: c.order_trans[OF bot] c.ccpo_Sup_upper[OF chain'''])
Andreas@62652
   731
      hence "\<Or>(insert bot (f ` ?Y)) \<sqsubseteq> \<Or>(f ` ?Y)" using chain''
Andreas@62652
   732
        by(auto intro: c.ccpo_Sup_least c.ccpo_Sup_upper[OF chain''']) 
Andreas@62652
   733
      with _ have "\<dots> = \<Or>(insert bot (f ` ?Y))"
Andreas@62652
   734
        by(rule c.antisym)(blast intro: c.ccpo_Sup_least[OF chain'''] c.ccpo_Sup_upper[OF chain''])
Andreas@62652
   735
      also have "insert bot (f ` ?Y) = ?g ` Y" using False by auto
Andreas@62652
   736
      finally show ?thesis .
Andreas@62652
   737
    qed
Andreas@62652
   738
    finally show ?thesis .
Andreas@62652
   739
  qed
Andreas@62652
   740
qed
Andreas@62652
   741
Andreas@62652
   742
context partial_function_definitions begin
Andreas@62652
   743
Andreas@62652
   744
lemma mcont_const [cont_intro, simp]:
Andreas@62652
   745
  "mcont luba orda lub leq (\<lambda>x. c)"
Andreas@62652
   746
by(rule ccpo.mcont_const)(rule Partial_Function.ccpo[OF partial_function_definitions_axioms])
Andreas@62652
   747
Andreas@62652
   748
lemmas [cont_intro, simp] =
Andreas@62652
   749
  ccpo.cont_const[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   750
Andreas@62652
   751
lemma mono2mono:
Andreas@62652
   752
  assumes "monotone ordb leq (\<lambda>y. f y)" "monotone orda ordb (\<lambda>x. t x)"
Andreas@62652
   753
  shows "monotone orda leq (\<lambda>x. f (t x))"
Andreas@62652
   754
using assms by(rule monotone2monotone) simp_all
Andreas@62652
   755
Andreas@62652
   756
lemmas mcont2mcont' = ccpo.mcont2mcont'[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   757
lemmas mcont2mcont = ccpo.mcont2mcont[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   758
Andreas@62652
   759
lemmas fixp_preserves_mono1 = ccpo.fixp_preserves_mono1[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   760
lemmas fixp_preserves_mono2 = ccpo.fixp_preserves_mono2[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   761
lemmas fixp_preserves_mono3 = ccpo.fixp_preserves_mono3[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   762
lemmas fixp_preserves_mono4 = ccpo.fixp_preserves_mono4[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   763
lemmas fixp_preserves_mcont1 = ccpo.fixp_preserves_mcont1[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   764
lemmas fixp_preserves_mcont2 = ccpo.fixp_preserves_mcont2[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   765
lemmas fixp_preserves_mcont3 = ccpo.fixp_preserves_mcont3[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   766
lemmas fixp_preserves_mcont4 = ccpo.fixp_preserves_mcont4[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   767
Andreas@62652
   768
lemma monotone_if_bot:
Andreas@62652
   769
  fixes bot
Andreas@62652
   770
  assumes g: "\<And>x. g x = (if leq x bound then bot else f x)"
Andreas@62652
   771
  and mono: "\<And>x y. \<lbrakk> leq x y; \<not> leq x bound \<rbrakk> \<Longrightarrow> ord (f x) (f y)"
Andreas@62652
   772
  and bot: "\<And>x. \<not> leq x bound \<Longrightarrow> ord bot (f x)" "ord bot bot"
Andreas@62652
   773
  shows "monotone leq ord g"
Andreas@62652
   774
unfolding g[abs_def] using preorder mono bot by(rule preorder.monotone_if_bot)
Andreas@62652
   775
Andreas@62652
   776
lemma mcont_if_bot:
Andreas@62652
   777
  fixes bot
Andreas@62652
   778
  assumes ccpo: "class.ccpo lub' ord (mk_less ord)"
Andreas@62652
   779
  and bot: "\<And>x. \<not> leq x bound \<Longrightarrow> ord bot (f x)"
Andreas@62652
   780
  and g: "\<And>x. g x = (if leq x bound then bot else f x)"
Andreas@62652
   781
  and mono: "\<And>x y. \<lbrakk> leq x y; \<not> leq x bound \<rbrakk> \<Longrightarrow> ord (f x) (f y)"
Andreas@62652
   782
  and cont: "\<And>Y. \<lbrakk> Complete_Partial_Order.chain leq Y; Y \<noteq> {}; \<And>x. x \<in> Y \<Longrightarrow> \<not> leq x bound \<rbrakk> \<Longrightarrow> f (lub Y) = lub' (f ` Y)"
Andreas@62652
   783
  shows "mcont lub leq lub' ord g"
Andreas@62652
   784
unfolding g[abs_def] using ccpo mono cont bot by(rule ccpo.mcont_if_bot[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]])
Andreas@62652
   785
Andreas@62652
   786
end
Andreas@62652
   787
wenzelm@62837
   788
subsection \<open>Admissibility\<close>
Andreas@62652
   789
Andreas@62652
   790
lemma admissible_subst:
Andreas@62652
   791
  assumes adm: "ccpo.admissible luba orda (\<lambda>x. P x)"
Andreas@62652
   792
  and mcont: "mcont lubb ordb luba orda f"
Andreas@62652
   793
  shows "ccpo.admissible lubb ordb (\<lambda>x. P (f x))"
Andreas@62652
   794
apply(rule ccpo.admissibleI)
Andreas@62652
   795
apply(frule (1) mcont_contD[OF mcont])
Andreas@62652
   796
apply(auto intro: ccpo.admissibleD[OF adm] chain_imageI dest: mcont_monoD[OF mcont])
Andreas@62652
   797
done
Andreas@62652
   798
Andreas@62652
   799
lemmas [simp, cont_intro] = 
Andreas@62652
   800
  admissible_all
Andreas@62652
   801
  admissible_ball
Andreas@62652
   802
  admissible_const
Andreas@62652
   803
  admissible_conj
Andreas@62652
   804
Andreas@62652
   805
lemma admissible_disj' [simp, cont_intro]:
Andreas@62652
   806
  "\<lbrakk> class.ccpo lub ord (mk_less ord); ccpo.admissible lub ord P; ccpo.admissible lub ord Q \<rbrakk>
Andreas@62652
   807
  \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. P x \<or> Q x)"
Andreas@62652
   808
by(rule ccpo.admissible_disj)
Andreas@62652
   809
Andreas@62652
   810
lemma admissible_imp' [cont_intro]:
Andreas@62652
   811
  "\<lbrakk> class.ccpo lub ord (mk_less ord);
Andreas@62652
   812
     ccpo.admissible lub ord (\<lambda>x. \<not> P x);
Andreas@62652
   813
     ccpo.admissible lub ord (\<lambda>x. Q x) \<rbrakk>
Andreas@62652
   814
  \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. P x \<longrightarrow> Q x)"
Andreas@62652
   815
unfolding imp_conv_disj by(rule ccpo.admissible_disj)
Andreas@62652
   816
Andreas@62652
   817
lemma admissible_imp [cont_intro]:
Andreas@62652
   818
  "(Q \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. P x))
Andreas@62652
   819
  \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. Q \<longrightarrow> P x)"
Andreas@62652
   820
by(rule ccpo.admissibleI)(auto dest: ccpo.admissibleD)
Andreas@62652
   821
Andreas@62652
   822
lemma admissible_not_mem' [THEN admissible_subst, cont_intro, simp]:
Andreas@62652
   823
  shows admissible_not_mem: "ccpo.admissible Union op \<subseteq> (\<lambda>A. x \<notin> A)"
Andreas@62652
   824
by(rule ccpo.admissibleI) auto
Andreas@62652
   825
Andreas@62652
   826
lemma admissible_eqI:
Andreas@62652
   827
  assumes f: "cont luba orda lub ord (\<lambda>x. f x)"
Andreas@62652
   828
  and g: "cont luba orda lub ord (\<lambda>x. g x)"
Andreas@62652
   829
  shows "ccpo.admissible luba orda (\<lambda>x. f x = g x)"
Andreas@62652
   830
apply(rule ccpo.admissibleI)
Andreas@62652
   831
apply(simp_all add: contD[OF f] contD[OF g] cong: image_cong)
Andreas@62652
   832
done
Andreas@62652
   833
Andreas@62652
   834
corollary admissible_eq_mcontI [cont_intro]:
Andreas@62652
   835
  "\<lbrakk> mcont luba orda lub ord (\<lambda>x. f x); 
Andreas@62652
   836
    mcont luba orda lub ord (\<lambda>x. g x) \<rbrakk>
Andreas@62652
   837
  \<Longrightarrow> ccpo.admissible luba orda (\<lambda>x. f x = g x)"
Andreas@62652
   838
by(rule admissible_eqI)(auto simp add: mcont_def)
Andreas@62652
   839
Andreas@62652
   840
lemma admissible_iff [cont_intro, simp]:
Andreas@62652
   841
  "\<lbrakk> ccpo.admissible lub ord (\<lambda>x. P x \<longrightarrow> Q x); ccpo.admissible lub ord (\<lambda>x. Q x \<longrightarrow> P x) \<rbrakk>
Andreas@62652
   842
  \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. P x \<longleftrightarrow> Q x)"
Andreas@62652
   843
by(subst iff_conv_conj_imp)(rule admissible_conj)
Andreas@62652
   844
Andreas@62652
   845
context ccpo begin
Andreas@62652
   846
Andreas@62652
   847
lemma admissible_leI:
Andreas@62652
   848
  assumes f: "mcont luba orda Sup op \<le> (\<lambda>x. f x)"
Andreas@62652
   849
  and g: "mcont luba orda Sup op \<le> (\<lambda>x. g x)"
Andreas@62652
   850
  shows "ccpo.admissible luba orda (\<lambda>x. f x \<le> g x)"
Andreas@62652
   851
proof(rule ccpo.admissibleI)
Andreas@62652
   852
  fix A
Andreas@62652
   853
  assume chain: "Complete_Partial_Order.chain orda A"
Andreas@62652
   854
    and le: "\<forall>x\<in>A. f x \<le> g x"
Andreas@62652
   855
    and False: "A \<noteq> {}"
Andreas@62652
   856
  have "f (luba A) = \<Squnion>(f ` A)" by(simp add: mcont_contD[OF f] chain False)
Andreas@62652
   857
  also have "\<dots> \<le> \<Squnion>(g ` A)"
Andreas@62652
   858
  proof(rule ccpo_Sup_least)
Andreas@62652
   859
    from chain show "Complete_Partial_Order.chain op \<le> (f ` A)"
Andreas@62652
   860
      by(rule chain_imageI)(rule mcont_monoD[OF f])
Andreas@62652
   861
    
Andreas@62652
   862
    fix x
Andreas@62652
   863
    assume "x \<in> f ` A"
Andreas@62652
   864
    then obtain y where "y \<in> A" "x = f y" by blast note this(2)
wenzelm@62837
   865
    also have "f y \<le> g y" using le \<open>y \<in> A\<close> by simp
Andreas@62652
   866
    also have "Complete_Partial_Order.chain op \<le> (g ` A)"
Andreas@62652
   867
      using chain by(rule chain_imageI)(rule mcont_monoD[OF g])
wenzelm@62837
   868
    hence "g y \<le> \<Squnion>(g ` A)" by(rule ccpo_Sup_upper)(simp add: \<open>y \<in> A\<close>)
Andreas@62652
   869
    finally show "x \<le> \<dots>" .
Andreas@62652
   870
  qed
Andreas@62652
   871
  also have "\<dots> = g (luba A)" by(simp add: mcont_contD[OF g] chain False)
Andreas@62652
   872
  finally show "f (luba A) \<le> g (luba A)" .
Andreas@62652
   873
qed
Andreas@62652
   874
Andreas@62652
   875
end
Andreas@62652
   876
Andreas@62652
   877
lemma admissible_leI:
Andreas@62652
   878
  fixes ord (infix "\<sqsubseteq>" 60) and lub ("\<Or>_" [900] 900)
Andreas@62652
   879
  assumes "class.ccpo lub op \<sqsubseteq> (mk_less op \<sqsubseteq>)"
Andreas@62652
   880
  and "mcont luba orda lub op \<sqsubseteq> (\<lambda>x. f x)"
Andreas@62652
   881
  and "mcont luba orda lub op \<sqsubseteq> (\<lambda>x. g x)"
Andreas@62652
   882
  shows "ccpo.admissible luba orda (\<lambda>x. f x \<sqsubseteq> g x)"
Andreas@62652
   883
using assms by(rule ccpo.admissible_leI)
Andreas@62652
   884
Andreas@62652
   885
declare ccpo_class.admissible_leI[cont_intro]
Andreas@62652
   886
Andreas@62652
   887
context ccpo begin
Andreas@62652
   888
Andreas@62652
   889
lemma admissible_not_below: "ccpo.admissible Sup op \<le> (\<lambda>x. \<not> op \<le> x y)"
Andreas@62652
   890
by(rule ccpo.admissibleI)(simp add: ccpo_Sup_below_iff)
Andreas@62652
   891
Andreas@62652
   892
end
Andreas@62652
   893
Andreas@62652
   894
lemma (in preorder) preorder [cont_intro, simp]: "class.preorder op \<le> (mk_less op \<le>)"
Andreas@62652
   895
by(unfold_locales)(auto simp add: mk_less_def intro: order_trans)
Andreas@62652
   896
Andreas@62652
   897
context partial_function_definitions begin
Andreas@62652
   898
Andreas@62652
   899
lemmas [cont_intro, simp] =
Andreas@62652
   900
  admissible_leI[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   901
  ccpo.admissible_not_below[THEN admissible_subst, OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   902
Andreas@62652
   903
end
Andreas@62652
   904
Andreas@62652
   905
Andreas@62652
   906
inductive compact :: "('a set \<Rightarrow> 'a) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> 'a \<Rightarrow> bool"
Andreas@62652
   907
  for lub ord x 
Andreas@62652
   908
where compact:
Andreas@62652
   909
  "\<lbrakk> ccpo.admissible lub ord (\<lambda>y. \<not> ord x y);
Andreas@62652
   910
     ccpo.admissible lub ord (\<lambda>y. x \<noteq> y) \<rbrakk>
Andreas@62652
   911
  \<Longrightarrow> compact lub ord x"
Andreas@62652
   912
Andreas@62652
   913
hide_fact (open) compact
Andreas@62652
   914
Andreas@62652
   915
context ccpo begin
Andreas@62652
   916
Andreas@62652
   917
lemma compactI:
Andreas@62652
   918
  assumes "ccpo.admissible Sup op \<le> (\<lambda>y. \<not> x \<le> y)"
Andreas@62652
   919
  shows "compact Sup op \<le> x"
Andreas@62652
   920
using assms
Andreas@62652
   921
proof(rule compact.intros)
Andreas@62652
   922
  have neq: "(\<lambda>y. x \<noteq> y) = (\<lambda>y. \<not> x \<le> y \<or> \<not> y \<le> x)" by(auto)
Andreas@62652
   923
  show "ccpo.admissible Sup op \<le> (\<lambda>y. x \<noteq> y)"
Andreas@62652
   924
    by(subst neq)(rule admissible_disj admissible_not_below assms)+
Andreas@62652
   925
qed
Andreas@62652
   926
Andreas@62652
   927
lemma compact_bot:
Andreas@62652
   928
  assumes "x = Sup {}"
Andreas@62652
   929
  shows "compact Sup op \<le> x"
Andreas@62652
   930
proof(rule compactI)
Andreas@62652
   931
  show "ccpo.admissible Sup op \<le> (\<lambda>y. \<not> x \<le> y)" using assms
Andreas@62652
   932
    by(auto intro!: ccpo.admissibleI intro: ccpo_Sup_least chain_empty)
Andreas@62652
   933
qed
Andreas@62652
   934
Andreas@62652
   935
end
Andreas@62652
   936
Andreas@62652
   937
lemma admissible_compact_neq' [THEN admissible_subst, cont_intro, simp]:
Andreas@62652
   938
  shows admissible_compact_neq: "compact lub ord k \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. k \<noteq> x)"
Andreas@62652
   939
by(simp add: compact.simps)
Andreas@62652
   940
Andreas@62652
   941
lemma admissible_neq_compact' [THEN admissible_subst, cont_intro, simp]:
Andreas@62652
   942
  shows admissible_neq_compact: "compact lub ord k \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. x \<noteq> k)"
Andreas@62652
   943
by(subst eq_commute)(rule admissible_compact_neq)
Andreas@62652
   944
Andreas@62652
   945
context partial_function_definitions begin
Andreas@62652
   946
Andreas@62652
   947
lemmas [cont_intro, simp] = ccpo.compact_bot[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
Andreas@62652
   948
Andreas@62652
   949
end
Andreas@62652
   950
Andreas@62652
   951
context ccpo begin
Andreas@62652
   952
Andreas@62652
   953
lemma fixp_strong_induct:
Andreas@62652
   954
  assumes [cont_intro]: "ccpo.admissible Sup op \<le> P"
Andreas@62652
   955
  and mono: "monotone op \<le> op \<le> f"
Andreas@62652
   956
  and bot: "P (\<Squnion>{})"
Andreas@62652
   957
  and step: "\<And>x. \<lbrakk> x \<le> ccpo_class.fixp f; P x \<rbrakk> \<Longrightarrow> P (f x)"
Andreas@62652
   958
  shows "P (ccpo_class.fixp f)"
Andreas@62652
   959
proof(rule fixp_induct[where P="\<lambda>x. x \<le> ccpo_class.fixp f \<and> P x", THEN conjunct2])
Andreas@62652
   960
  note [cont_intro] = admissible_leI
Andreas@62652
   961
  show "ccpo.admissible Sup op \<le> (\<lambda>x. x \<le> ccpo_class.fixp f \<and> P x)" by simp
Andreas@62652
   962
next
Andreas@62652
   963
  show "\<Squnion>{} \<le> ccpo_class.fixp f \<and> P (\<Squnion>{})"
Andreas@62652
   964
    by(auto simp add: bot intro: ccpo_Sup_least chain_empty)
Andreas@62652
   965
next
Andreas@62652
   966
  fix x
Andreas@62652
   967
  assume "x \<le> ccpo_class.fixp f \<and> P x"
Andreas@62652
   968
  thus "f x \<le> ccpo_class.fixp f \<and> P (f x)"
Andreas@62652
   969
    by(subst fixp_unfold[OF mono])(auto dest: monotoneD[OF mono] intro: step)
Andreas@62652
   970
qed(rule mono)
Andreas@62652
   971
Andreas@62652
   972
end
Andreas@62652
   973
Andreas@62652
   974
context partial_function_definitions begin
Andreas@62652
   975
Andreas@62652
   976
lemma fixp_strong_induct_uc:
Andreas@62652
   977
  fixes F :: "'c \<Rightarrow> 'c"
Andreas@62652
   978
    and U :: "'c \<Rightarrow> 'b \<Rightarrow> 'a"
Andreas@62652
   979
    and C :: "('b \<Rightarrow> 'a) \<Rightarrow> 'c"
Andreas@62652
   980
    and P :: "('b \<Rightarrow> 'a) \<Rightarrow> bool"
Andreas@62652
   981
  assumes mono: "\<And>x. mono_body (\<lambda>f. U (F (C f)) x)"
Andreas@62652
   982
    and eq: "f \<equiv> C (fixp_fun (\<lambda>f. U (F (C f))))"
Andreas@62652
   983
    and inverse: "\<And>f. U (C f) = f"
Andreas@62652
   984
    and adm: "ccpo.admissible lub_fun le_fun P"
Andreas@62652
   985
    and bot: "P (\<lambda>_. lub {})"
Andreas@62652
   986
    and step: "\<And>f'. \<lbrakk> P (U f'); le_fun (U f') (U f) \<rbrakk> \<Longrightarrow> P (U (F f'))"
Andreas@62652
   987
  shows "P (U f)"
Andreas@62652
   988
unfolding eq inverse
Andreas@62652
   989
apply (rule ccpo.fixp_strong_induct[OF ccpo adm])
Andreas@62652
   990
apply (insert mono, auto simp: monotone_def fun_ord_def bot fun_lub_def)[2]
Andreas@62652
   991
apply (rule_tac f'5="C x" in step)
Andreas@62652
   992
apply (simp_all add: inverse eq)
Andreas@62652
   993
done
Andreas@62652
   994
Andreas@62652
   995
end
Andreas@62652
   996
wenzelm@62837
   997
subsection \<open>@{term "op ="} as order\<close>
Andreas@62652
   998
Andreas@62652
   999
definition lub_singleton :: "('a set \<Rightarrow> 'a) \<Rightarrow> bool"
Andreas@62652
  1000
where "lub_singleton lub \<longleftrightarrow> (\<forall>a. lub {a} = a)"
Andreas@62652
  1001
Andreas@62652
  1002
definition the_Sup :: "'a set \<Rightarrow> 'a"
Andreas@62652
  1003
where "the_Sup A = (THE a. a \<in> A)"
Andreas@62652
  1004
Andreas@62652
  1005
lemma lub_singleton_the_Sup [cont_intro, simp]: "lub_singleton the_Sup"
Andreas@62652
  1006
by(simp add: lub_singleton_def the_Sup_def)
Andreas@62652
  1007
Andreas@62652
  1008
lemma (in ccpo) lub_singleton: "lub_singleton Sup"
Andreas@62652
  1009
by(simp add: lub_singleton_def)
Andreas@62652
  1010
Andreas@62652
  1011
lemma (in partial_function_definitions) lub_singleton [cont_intro, simp]: "lub_singleton lub"
Andreas@62652
  1012
by(rule ccpo.lub_singleton)(rule Partial_Function.ccpo[OF partial_function_definitions_axioms])
Andreas@62652
  1013
Andreas@62652
  1014
lemma preorder_eq [cont_intro, simp]:
Andreas@62652
  1015
  "class.preorder op = (mk_less op =)"
Andreas@62652
  1016
by(unfold_locales)(simp_all add: mk_less_def)
Andreas@62652
  1017
Andreas@62652
  1018
lemma monotone_eqI [cont_intro]:
Andreas@62652
  1019
  assumes "class.preorder ord (mk_less ord)"
Andreas@62652
  1020
  shows "monotone op = ord f"
Andreas@62652
  1021
proof -
Andreas@62652
  1022
  interpret preorder ord "mk_less ord" by fact
Andreas@62652
  1023
  show ?thesis by(simp add: monotone_def)
Andreas@62652
  1024
qed
Andreas@62652
  1025
Andreas@62652
  1026
lemma cont_eqI [cont_intro]: 
Andreas@62652
  1027
  fixes f :: "'a \<Rightarrow> 'b"
Andreas@62652
  1028
  assumes "lub_singleton lub"
Andreas@62652
  1029
  shows "cont the_Sup op = lub ord f"
Andreas@62652
  1030
proof(rule contI)
Andreas@62652
  1031
  fix Y :: "'a set"
Andreas@62652
  1032
  assume "Complete_Partial_Order.chain op = Y" "Y \<noteq> {}"
Andreas@62652
  1033
  then obtain a where "Y = {a}" by(auto simp add: chain_def)
Andreas@62652
  1034
  thus "f (the_Sup Y) = lub (f ` Y)" using assms
Andreas@62652
  1035
    by(simp add: the_Sup_def lub_singleton_def)
Andreas@62652
  1036
qed
Andreas@62652
  1037
Andreas@62652
  1038
lemma mcont_eqI [cont_intro, simp]:
Andreas@62652
  1039
  "\<lbrakk> class.preorder ord (mk_less ord); lub_singleton lub \<rbrakk>
Andreas@62652
  1040
  \<Longrightarrow> mcont the_Sup op = lub ord f"
Andreas@62652
  1041
by(simp add: mcont_def cont_eqI monotone_eqI)
Andreas@62652
  1042
wenzelm@62837
  1043
subsection \<open>ccpo for products\<close>
Andreas@62652
  1044
Andreas@62652
  1045
definition prod_lub :: "('a set \<Rightarrow> 'a) \<Rightarrow> ('b set \<Rightarrow> 'b) \<Rightarrow> ('a \<times> 'b) set \<Rightarrow> 'a \<times> 'b"
Andreas@62652
  1046
where "prod_lub Sup_a Sup_b Y = (Sup_a (fst ` Y), Sup_b (snd ` Y))"
Andreas@62652
  1047
Andreas@62652
  1048
lemma lub_singleton_prod_lub [cont_intro, simp]:
Andreas@62652
  1049
  "\<lbrakk> lub_singleton luba; lub_singleton lubb \<rbrakk> \<Longrightarrow> lub_singleton (prod_lub luba lubb)"
Andreas@62652
  1050
by(simp add: lub_singleton_def prod_lub_def)
Andreas@62652
  1051
Andreas@62652
  1052
lemma prod_lub_empty [simp]: "prod_lub luba lubb {} = (luba {}, lubb {})"
Andreas@62652
  1053
by(simp add: prod_lub_def)
Andreas@62652
  1054
Andreas@62652
  1055
lemma preorder_rel_prodI [cont_intro, simp]:
Andreas@62652
  1056
  assumes "class.preorder orda (mk_less orda)"
Andreas@62652
  1057
  and "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1058
  shows "class.preorder (rel_prod orda ordb) (mk_less (rel_prod orda ordb))"
Andreas@62652
  1059
proof -
Andreas@62652
  1060
  interpret a: preorder orda "mk_less orda" by fact
Andreas@62652
  1061
  interpret b: preorder ordb "mk_less ordb" by fact
Andreas@62652
  1062
  show ?thesis by(unfold_locales)(auto simp add: mk_less_def intro: a.order_trans b.order_trans)
Andreas@62652
  1063
qed
Andreas@62652
  1064
Andreas@62652
  1065
lemma order_rel_prodI:
Andreas@62652
  1066
  assumes a: "class.order orda (mk_less orda)"
Andreas@62652
  1067
  and b: "class.order ordb (mk_less ordb)"
Andreas@62652
  1068
  shows "class.order (rel_prod orda ordb) (mk_less (rel_prod orda ordb))"
Andreas@62652
  1069
  (is "class.order ?ord ?ord'")
Andreas@62652
  1070
proof(intro class.order.intro class.order_axioms.intro)
Andreas@62652
  1071
  interpret a: order orda "mk_less orda" by(fact a)
Andreas@62652
  1072
  interpret b: order ordb "mk_less ordb" by(fact b)
Andreas@62652
  1073
  show "class.preorder ?ord ?ord'" by(rule preorder_rel_prodI) unfold_locales
Andreas@62652
  1074
Andreas@62652
  1075
  fix x y
Andreas@62652
  1076
  assume "?ord x y" "?ord y x"
Andreas@62652
  1077
  thus "x = y" by(cases x y rule: prod.exhaust[case_product prod.exhaust]) auto
Andreas@62652
  1078
qed
Andreas@62652
  1079
Andreas@62652
  1080
lemma monotone_rel_prodI:
Andreas@62652
  1081
  assumes mono2: "\<And>a. monotone ordb ordc (\<lambda>b. f (a, b))"
Andreas@62652
  1082
  and mono1: "\<And>b. monotone orda ordc (\<lambda>a. f (a, b))"
Andreas@62652
  1083
  and a: "class.preorder orda (mk_less orda)"
Andreas@62652
  1084
  and b: "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1085
  and c: "class.preorder ordc (mk_less ordc)"
Andreas@62652
  1086
  shows "monotone (rel_prod orda ordb) ordc f"
Andreas@62652
  1087
proof -
Andreas@62652
  1088
  interpret a: preorder orda "mk_less orda" by(rule a)
Andreas@62652
  1089
  interpret b: preorder ordb "mk_less ordb" by(rule b)
Andreas@62652
  1090
  interpret c: preorder ordc "mk_less ordc" by(rule c)
Andreas@62652
  1091
  show ?thesis using mono2 mono1
Andreas@62652
  1092
    by(auto 7 2 simp add: monotone_def intro: c.order_trans)
Andreas@62652
  1093
qed
Andreas@62652
  1094
Andreas@62652
  1095
lemma monotone_rel_prodD1:
Andreas@62652
  1096
  assumes mono: "monotone (rel_prod orda ordb) ordc f"
Andreas@62652
  1097
  and preorder: "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1098
  shows "monotone orda ordc (\<lambda>a. f (a, b))"
Andreas@62652
  1099
proof -
Andreas@62652
  1100
  interpret preorder ordb "mk_less ordb" by(rule preorder)
Andreas@62652
  1101
  show ?thesis using mono by(simp add: monotone_def)
Andreas@62652
  1102
qed
Andreas@62652
  1103
Andreas@62652
  1104
lemma monotone_rel_prodD2:
Andreas@62652
  1105
  assumes mono: "monotone (rel_prod orda ordb) ordc f"
Andreas@62652
  1106
  and preorder: "class.preorder orda (mk_less orda)"
Andreas@62652
  1107
  shows "monotone ordb ordc (\<lambda>b. f (a, b))"
Andreas@62652
  1108
proof -
Andreas@62652
  1109
  interpret preorder orda "mk_less orda" by(rule preorder)
Andreas@62652
  1110
  show ?thesis using mono by(simp add: monotone_def)
Andreas@62652
  1111
qed
Andreas@62652
  1112
Andreas@62652
  1113
lemma monotone_case_prodI:
Andreas@62652
  1114
  "\<lbrakk> \<And>a. monotone ordb ordc (f a); \<And>b. monotone orda ordc (\<lambda>a. f a b);
Andreas@62652
  1115
    class.preorder orda (mk_less orda); class.preorder ordb (mk_less ordb);
Andreas@62652
  1116
    class.preorder ordc (mk_less ordc) \<rbrakk>
Andreas@62652
  1117
  \<Longrightarrow> monotone (rel_prod orda ordb) ordc (case_prod f)"
Andreas@62652
  1118
by(rule monotone_rel_prodI) simp_all
Andreas@62652
  1119
Andreas@62652
  1120
lemma monotone_case_prodD1:
Andreas@62652
  1121
  assumes mono: "monotone (rel_prod orda ordb) ordc (case_prod f)"
Andreas@62652
  1122
  and preorder: "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1123
  shows "monotone orda ordc (\<lambda>a. f a b)"
Andreas@62652
  1124
using monotone_rel_prodD1[OF assms] by simp
Andreas@62652
  1125
Andreas@62652
  1126
lemma monotone_case_prodD2:
Andreas@62652
  1127
  assumes mono: "monotone (rel_prod orda ordb) ordc (case_prod f)"
Andreas@62652
  1128
  and preorder: "class.preorder orda (mk_less orda)"
Andreas@62652
  1129
  shows "monotone ordb ordc (f a)"
Andreas@62652
  1130
using monotone_rel_prodD2[OF assms] by simp
Andreas@62652
  1131
Andreas@62652
  1132
context 
Andreas@62652
  1133
  fixes orda ordb ordc
Andreas@62652
  1134
  assumes a: "class.preorder orda (mk_less orda)"
Andreas@62652
  1135
  and b: "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1136
  and c: "class.preorder ordc (mk_less ordc)"
Andreas@62652
  1137
begin
Andreas@62652
  1138
Andreas@62652
  1139
lemma monotone_rel_prod_iff:
Andreas@62652
  1140
  "monotone (rel_prod orda ordb) ordc f \<longleftrightarrow>
Andreas@62652
  1141
   (\<forall>a. monotone ordb ordc (\<lambda>b. f (a, b))) \<and> 
Andreas@62652
  1142
   (\<forall>b. monotone orda ordc (\<lambda>a. f (a, b)))"
Andreas@62652
  1143
using a b c by(blast intro: monotone_rel_prodI dest: monotone_rel_prodD1 monotone_rel_prodD2)
Andreas@62652
  1144
Andreas@62652
  1145
lemma monotone_case_prod_iff [simp]:
Andreas@62652
  1146
  "monotone (rel_prod orda ordb) ordc (case_prod f) \<longleftrightarrow>
Andreas@62652
  1147
   (\<forall>a. monotone ordb ordc (f a)) \<and> (\<forall>b. monotone orda ordc (\<lambda>a. f a b))"
Andreas@62652
  1148
by(simp add: monotone_rel_prod_iff)
Andreas@62652
  1149
Andreas@62652
  1150
end
Andreas@62652
  1151
Andreas@62652
  1152
lemma monotone_case_prod_apply_iff:
Andreas@62652
  1153
  "monotone orda ordb (\<lambda>x. (case_prod f x) y) \<longleftrightarrow> monotone orda ordb (case_prod (\<lambda>a b. f a b y))"
Andreas@62652
  1154
by(simp add: monotone_def)
Andreas@62652
  1155
Andreas@62652
  1156
lemma monotone_case_prod_applyD:
Andreas@62652
  1157
  "monotone orda ordb (\<lambda>x. (case_prod f x) y)
Andreas@62652
  1158
  \<Longrightarrow> monotone orda ordb (case_prod (\<lambda>a b. f a b y))"
Andreas@62652
  1159
by(simp add: monotone_case_prod_apply_iff)
Andreas@62652
  1160
Andreas@62652
  1161
lemma monotone_case_prod_applyI:
Andreas@62652
  1162
  "monotone orda ordb (case_prod (\<lambda>a b. f a b y))
Andreas@62652
  1163
  \<Longrightarrow> monotone orda ordb (\<lambda>x. (case_prod f x) y)"
Andreas@62652
  1164
by(simp add: monotone_case_prod_apply_iff)
Andreas@62652
  1165
Andreas@62652
  1166
Andreas@62652
  1167
lemma cont_case_prod_apply_iff:
Andreas@62652
  1168
  "cont luba orda lubb ordb (\<lambda>x. (case_prod f x) y) \<longleftrightarrow> cont luba orda lubb ordb (case_prod (\<lambda>a b. f a b y))"
Andreas@62652
  1169
by(simp add: cont_def split_def)
Andreas@62652
  1170
Andreas@62652
  1171
lemma cont_case_prod_applyI:
Andreas@62652
  1172
  "cont luba orda lubb ordb (case_prod (\<lambda>a b. f a b y))
Andreas@62652
  1173
  \<Longrightarrow> cont luba orda lubb ordb (\<lambda>x. (case_prod f x) y)"
Andreas@62652
  1174
by(simp add: cont_case_prod_apply_iff)
Andreas@62652
  1175
Andreas@62652
  1176
lemma cont_case_prod_applyD:
Andreas@62652
  1177
  "cont luba orda lubb ordb (\<lambda>x. (case_prod f x) y)
Andreas@62652
  1178
  \<Longrightarrow> cont luba orda lubb ordb (case_prod (\<lambda>a b. f a b y))"
Andreas@62652
  1179
by(simp add: cont_case_prod_apply_iff)
Andreas@62652
  1180
Andreas@62652
  1181
lemma mcont_case_prod_apply_iff [simp]:
Andreas@62652
  1182
  "mcont luba orda lubb ordb (\<lambda>x. (case_prod f x) y) \<longleftrightarrow> 
Andreas@62652
  1183
   mcont luba orda lubb ordb (case_prod (\<lambda>a b. f a b y))"
Andreas@62652
  1184
by(simp add: mcont_def monotone_case_prod_apply_iff cont_case_prod_apply_iff)
Andreas@62652
  1185
Andreas@62652
  1186
lemma cont_prodD1: 
Andreas@62652
  1187
  assumes cont: "cont (prod_lub luba lubb) (rel_prod orda ordb) lubc ordc f"
Andreas@62652
  1188
  and "class.preorder orda (mk_less orda)"
Andreas@62652
  1189
  and luba: "lub_singleton luba"
Andreas@62652
  1190
  shows "cont lubb ordb lubc ordc (\<lambda>y. f (x, y))"
Andreas@62652
  1191
proof(rule contI)
Andreas@62652
  1192
  interpret preorder orda "mk_less orda" by fact
Andreas@62652
  1193
Andreas@62652
  1194
  fix Y :: "'b set"
Andreas@62652
  1195
  let ?Y = "{x} \<times> Y"
Andreas@62652
  1196
  assume "Complete_Partial_Order.chain ordb Y" "Y \<noteq> {}"
Andreas@62652
  1197
  hence "Complete_Partial_Order.chain (rel_prod orda ordb) ?Y" "?Y \<noteq> {}" 
Andreas@62652
  1198
    by(simp_all add: chain_def)
Andreas@62652
  1199
  with cont have "f (prod_lub luba lubb ?Y) = lubc (f ` ?Y)" by(rule contD)
Andreas@62652
  1200
  moreover have "f ` ?Y = (\<lambda>y. f (x, y)) ` Y" by auto
Andreas@62652
  1201
  ultimately show "f (x, lubb Y) = lubc ((\<lambda>y. f (x, y)) ` Y)" using luba
wenzelm@62837
  1202
    by(simp add: prod_lub_def \<open>Y \<noteq> {}\<close> lub_singleton_def)
Andreas@62652
  1203
qed
Andreas@62652
  1204
Andreas@62652
  1205
lemma cont_prodD2: 
Andreas@62652
  1206
  assumes cont: "cont (prod_lub luba lubb) (rel_prod orda ordb) lubc ordc f"
Andreas@62652
  1207
  and "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1208
  and lubb: "lub_singleton lubb"
Andreas@62652
  1209
  shows "cont luba orda lubc ordc (\<lambda>x. f (x, y))"
Andreas@62652
  1210
proof(rule contI)
Andreas@62652
  1211
  interpret preorder ordb "mk_less ordb" by fact
Andreas@62652
  1212
Andreas@62652
  1213
  fix Y
Andreas@62652
  1214
  assume Y: "Complete_Partial_Order.chain orda Y" "Y \<noteq> {}"
Andreas@62652
  1215
  let ?Y = "Y \<times> {y}"
Andreas@62652
  1216
  have "f (luba Y, y) = f (prod_lub luba lubb ?Y)"
Andreas@62652
  1217
    using lubb by(simp add: prod_lub_def Y lub_singleton_def)
Andreas@62652
  1218
  also from Y have "Complete_Partial_Order.chain (rel_prod orda ordb) ?Y" "?Y \<noteq> {}"
Andreas@62652
  1219
    by(simp_all add: chain_def)
Andreas@62652
  1220
  with cont have "f (prod_lub luba lubb ?Y) = lubc (f ` ?Y)" by(rule contD)
Andreas@62652
  1221
  also have "f ` ?Y = (\<lambda>x. f (x, y)) ` Y" by auto
Andreas@62652
  1222
  finally show "f (luba Y, y) = lubc \<dots>" .
Andreas@62652
  1223
qed
Andreas@62652
  1224
Andreas@62652
  1225
lemma cont_case_prodD1:
Andreas@62652
  1226
  assumes "cont (prod_lub luba lubb) (rel_prod orda ordb) lubc ordc (case_prod f)"
Andreas@62652
  1227
  and "class.preorder orda (mk_less orda)"
Andreas@62652
  1228
  and "lub_singleton luba"
Andreas@62652
  1229
  shows "cont lubb ordb lubc ordc (f x)"
Andreas@62652
  1230
using cont_prodD1[OF assms] by simp
Andreas@62652
  1231
Andreas@62652
  1232
lemma cont_case_prodD2:
Andreas@62652
  1233
  assumes "cont (prod_lub luba lubb) (rel_prod orda ordb) lubc ordc (case_prod f)"
Andreas@62652
  1234
  and "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1235
  and "lub_singleton lubb"
Andreas@62652
  1236
  shows "cont luba orda lubc ordc (\<lambda>x. f x y)"
Andreas@62652
  1237
using cont_prodD2[OF assms] by simp
Andreas@62652
  1238
Andreas@62652
  1239
context ccpo begin
Andreas@62652
  1240
Andreas@62652
  1241
lemma cont_prodI: 
Andreas@62652
  1242
  assumes mono: "monotone (rel_prod orda ordb) op \<le> f"
Andreas@62652
  1243
  and cont1: "\<And>x. cont lubb ordb Sup op \<le> (\<lambda>y. f (x, y))"
Andreas@62652
  1244
  and cont2: "\<And>y. cont luba orda Sup op \<le> (\<lambda>x. f (x, y))"
Andreas@62652
  1245
  and "class.preorder orda (mk_less orda)"
Andreas@62652
  1246
  and "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1247
  shows "cont (prod_lub luba lubb) (rel_prod orda ordb) Sup op \<le> f"
Andreas@62652
  1248
proof(rule contI)
Andreas@62652
  1249
  interpret a: preorder orda "mk_less orda" by fact 
Andreas@62652
  1250
  interpret b: preorder ordb "mk_less ordb" by fact
Andreas@62652
  1251
  
Andreas@62652
  1252
  fix Y
Andreas@62652
  1253
  assume chain: "Complete_Partial_Order.chain (rel_prod orda ordb) Y"
Andreas@62652
  1254
    and "Y \<noteq> {}"
Andreas@62652
  1255
  have "f (prod_lub luba lubb Y) = f (luba (fst ` Y), lubb (snd ` Y))"
Andreas@62652
  1256
    by(simp add: prod_lub_def)
Andreas@62652
  1257
  also from cont2 have "f (luba (fst ` Y), lubb (snd ` Y)) = \<Squnion>((\<lambda>x. f (x, lubb (snd ` Y))) ` fst ` Y)"
wenzelm@62837
  1258
    by(rule contD)(simp_all add: chain_rel_prodD1[OF chain] \<open>Y \<noteq> {}\<close>)
Andreas@62652
  1259
  also from cont1 have "\<And>x. f (x, lubb (snd ` Y)) = \<Squnion>((\<lambda>y. f (x, y)) ` snd ` Y)"
wenzelm@62837
  1260
    by(rule contD)(simp_all add: chain_rel_prodD2[OF chain] \<open>Y \<noteq> {}\<close>)
Andreas@62652
  1261
  hence "\<Squnion>((\<lambda>x. f (x, lubb (snd ` Y))) ` fst ` Y) = \<Squnion>((\<lambda>x. \<dots> x) ` fst ` Y)" by simp
Andreas@62652
  1262
  also have "\<dots> = \<Squnion>((\<lambda>x. f (fst x, snd x)) ` Y)"
Andreas@62652
  1263
    unfolding image_image split_def using chain
Andreas@62652
  1264
    apply(rule diag_Sup)
Andreas@62652
  1265
    using monotoneD[OF mono]
Andreas@62652
  1266
    by(auto intro: monotoneI)
Andreas@62652
  1267
  finally show "f (prod_lub luba lubb Y) = \<Squnion>(f ` Y)" by simp
Andreas@62652
  1268
qed
Andreas@62652
  1269
Andreas@62652
  1270
lemma cont_case_prodI:
Andreas@62652
  1271
  assumes "monotone (rel_prod orda ordb) op \<le> (case_prod f)"
Andreas@62652
  1272
  and "\<And>x. cont lubb ordb Sup op \<le> (\<lambda>y. f x y)"
Andreas@62652
  1273
  and "\<And>y. cont luba orda Sup op \<le> (\<lambda>x. f x y)"
Andreas@62652
  1274
  and "class.preorder orda (mk_less orda)"
Andreas@62652
  1275
  and "class.preorder ordb (mk_less ordb)"
Andreas@62652
  1276
  shows "cont (prod_lub luba lubb) (rel_prod orda ordb) Sup op \<le> (case_prod f)"
Andreas@62652
  1277
by(rule cont_prodI)(simp_all add: assms)
Andreas@62652
  1278
Andreas@62652
  1279
lemma cont_case_prod_iff:
Andreas@62652
  1280
  "\<lbrakk> monotone (rel_prod orda ordb) op \<le> (case_prod f);
Andreas@62652
  1281
     class.preorder orda (mk_less orda); lub_singleton luba;
Andreas@62652
  1282
     class.preorder ordb (mk_less ordb); lub_singleton lubb \<rbrakk>
Andreas@62652
  1283
  \<Longrightarrow> cont (prod_lub luba lubb) (rel_prod orda ordb) Sup op \<le> (case_prod f) \<longleftrightarrow>
Andreas@62652
  1284
   (\<forall>x. cont lubb ordb Sup op \<le> (\<lambda>y. f x y)) \<and> (\<forall>y. cont luba orda Sup op \<le> (\<lambda>x. f x y))"
Andreas@62652
  1285
by(blast dest: cont_case_prodD1 cont_case_prodD2 intro: cont_case_prodI)
Andreas@62652
  1286
Andreas@62652
  1287
end
Andreas@62652
  1288
Andreas@62652
  1289
context partial_function_definitions begin
Andreas@62652
  1290
Andreas@62652
  1291
lemma mono2mono2:
Andreas@62652
  1292
  assumes f: "monotone (rel_prod ordb ordc) leq (\<lambda>(x, y). f x y)"
Andreas@62652
  1293
  and t: "monotone orda ordb (\<lambda>x. t x)"
Andreas@62652
  1294
  and t': "monotone orda ordc (\<lambda>x. t' x)"
Andreas@62652
  1295
  shows "monotone orda leq (\<lambda>x. f (t x) (t' x))"
Andreas@62652
  1296
proof(rule monotoneI)
Andreas@62652
  1297
  fix x y
Andreas@62652
  1298
  assume "orda x y"
Andreas@62652
  1299
  hence "rel_prod ordb ordc (t x, t' x) (t y, t' y)"
Andreas@62652
  1300
    using t t' by(auto dest: monotoneD)
Andreas@62652
  1301
  from monotoneD[OF f this] show "leq (f (t x) (t' x)) (f (t y) (t' y))" by simp
Andreas@62652
  1302
qed
Andreas@62652
  1303
Andreas@62652
  1304
lemma cont_case_prodI [cont_intro]:
Andreas@62652
  1305
  "\<lbrakk> monotone (rel_prod orda ordb) leq (case_prod f);
Andreas@62652
  1306
    \<And>x. cont lubb ordb lub leq (\<lambda>y. f x y);
Andreas@62652
  1307
    \<And>y. cont luba orda lub leq (\<lambda>x. f x y);
Andreas@62652
  1308
    class.preorder orda (mk_less orda);
Andreas@62652
  1309
    class.preorder ordb (mk_less ordb) \<rbrakk>
Andreas@62652
  1310
  \<Longrightarrow> cont (prod_lub luba lubb) (rel_prod orda ordb) lub leq (case_prod f)"
Andreas@62652
  1311
by(rule ccpo.cont_case_prodI)(rule Partial_Function.ccpo[OF partial_function_definitions_axioms])
Andreas@62652
  1312
Andreas@62652
  1313
lemma cont_case_prod_iff:
Andreas@62652
  1314
  "\<lbrakk> monotone (rel_prod orda ordb) leq (case_prod f);
Andreas@62652
  1315
     class.preorder orda (mk_less orda); lub_singleton luba;
Andreas@62652
  1316
     class.preorder ordb (mk_less ordb); lub_singleton lubb \<rbrakk>
Andreas@62652
  1317
  \<Longrightarrow> cont (prod_lub luba lubb) (rel_prod orda ordb) lub leq (case_prod f) \<longleftrightarrow>
Andreas@62652
  1318
   (\<forall>x. cont lubb ordb lub leq (\<lambda>y. f x y)) \<and> (\<forall>y. cont luba orda lub leq (\<lambda>x. f x y))"
Andreas@62652
  1319
by(blast dest: cont_case_prodD1 cont_case_prodD2 intro: cont_case_prodI)
Andreas@62652
  1320
Andreas@62652
  1321
lemma mcont_case_prod_iff [simp]:
Andreas@62652
  1322
  "\<lbrakk> class.preorder orda (mk_less orda); lub_singleton luba;
Andreas@62652
  1323
     class.preorder ordb (mk_less ordb); lub_singleton lubb \<rbrakk>
Andreas@62652
  1324
  \<Longrightarrow> mcont (prod_lub luba lubb) (rel_prod orda ordb) lub leq (case_prod f) \<longleftrightarrow>
Andreas@62652
  1325
   (\<forall>x. mcont lubb ordb lub leq (\<lambda>y. f x y)) \<and> (\<forall>y. mcont luba orda lub leq (\<lambda>x. f x y))"
Andreas@62652
  1326
unfolding mcont_def by(auto simp add: cont_case_prod_iff)
Andreas@62652
  1327
Andreas@62652
  1328
end
Andreas@62652
  1329
Andreas@62652
  1330
lemma mono2mono_case_prod [cont_intro]:
Andreas@62652
  1331
  assumes "\<And>x y. monotone orda ordb (\<lambda>f. pair f x y)"
Andreas@62652
  1332
  shows "monotone orda ordb (\<lambda>f. case_prod (pair f) x)"
Andreas@62652
  1333
by(rule monotoneI)(auto split: prod.split dest: monotoneD[OF assms])
Andreas@62652
  1334
wenzelm@62837
  1335
subsection \<open>Complete lattices as ccpo\<close>
Andreas@62652
  1336
Andreas@62652
  1337
context complete_lattice begin
Andreas@62652
  1338
Andreas@62652
  1339
lemma complete_lattice_ccpo: "class.ccpo Sup op \<le> op <"
Andreas@62652
  1340
by(unfold_locales)(fast intro: Sup_upper Sup_least)+
Andreas@62652
  1341
Andreas@62652
  1342
lemma complete_lattice_ccpo': "class.ccpo Sup op \<le> (mk_less op \<le>)"
Andreas@62652
  1343
by(unfold_locales)(auto simp add: mk_less_def intro: Sup_upper Sup_least)
Andreas@62652
  1344
Andreas@62652
  1345
lemma complete_lattice_partial_function_definitions: 
Andreas@62652
  1346
  "partial_function_definitions op \<le> Sup"
Andreas@62652
  1347
by(unfold_locales)(auto intro: Sup_least Sup_upper)
Andreas@62652
  1348
Andreas@62652
  1349
lemma complete_lattice_partial_function_definitions_dual:
Andreas@62652
  1350
  "partial_function_definitions op \<ge> Inf"
Andreas@62652
  1351
by(unfold_locales)(auto intro: Inf_lower Inf_greatest)
Andreas@62652
  1352
Andreas@62652
  1353
lemmas [cont_intro, simp] =
Andreas@62652
  1354
  Partial_Function.ccpo[OF complete_lattice_partial_function_definitions]
Andreas@62652
  1355
  Partial_Function.ccpo[OF complete_lattice_partial_function_definitions_dual]
Andreas@62652
  1356
Andreas@62652
  1357
lemma mono2mono_inf:
Andreas@62652
  1358
  assumes f: "monotone ord op \<le> (\<lambda>x. f x)" 
Andreas@62652
  1359
  and g: "monotone ord op \<le> (\<lambda>x. g x)"
Andreas@62652
  1360
  shows "monotone ord op \<le> (\<lambda>x. f x \<sqinter> g x)"
Andreas@62652
  1361
by(auto 4 3 dest: monotoneD[OF f] monotoneD[OF g] intro: le_infI1 le_infI2 intro!: monotoneI)
Andreas@62652
  1362
Andreas@62652
  1363
lemma mcont_const [simp]: "mcont lub ord Sup op \<le> (\<lambda>_. c)"
Andreas@62652
  1364
by(rule ccpo.mcont_const[OF complete_lattice_ccpo])
Andreas@62652
  1365
Andreas@62652
  1366
lemma mono2mono_sup:
Andreas@62652
  1367
  assumes f: "monotone ord op \<le> (\<lambda>x. f x)"
Andreas@62652
  1368
  and g: "monotone ord op \<le> (\<lambda>x. g x)"
Andreas@62652
  1369
  shows "monotone ord op \<le> (\<lambda>x. f x \<squnion> g x)"
Andreas@62652
  1370
by(auto 4 3 intro!: monotoneI intro: sup.coboundedI1 sup.coboundedI2 dest: monotoneD[OF f] monotoneD[OF g])
Andreas@62652
  1371
Andreas@62652
  1372
lemma Sup_image_sup: 
Andreas@62652
  1373
  assumes "Y \<noteq> {}"
Andreas@62652
  1374
  shows "\<Squnion>(op \<squnion> x ` Y) = x \<squnion> \<Squnion>Y"
Andreas@62652
  1375
proof(rule Sup_eqI)
Andreas@62652
  1376
  fix y
Andreas@62652
  1377
  assume "y \<in> op \<squnion> x ` Y"
Andreas@62652
  1378
  then obtain z where "y = x \<squnion> z" and "z \<in> Y" by blast
wenzelm@62837
  1379
  from \<open>z \<in> Y\<close> have "z \<le> \<Squnion>Y" by(rule Sup_upper)
wenzelm@62837
  1380
  with _ show "y \<le> x \<squnion> \<Squnion>Y" unfolding \<open>y = x \<squnion> z\<close> by(rule sup_mono) simp
Andreas@62652
  1381
next
Andreas@62652
  1382
  fix y
Andreas@62652
  1383
  assume upper: "\<And>z. z \<in> op \<squnion> x ` Y \<Longrightarrow> z \<le> y"
Andreas@62652
  1384
  show "x \<squnion> \<Squnion>Y \<le> y" unfolding Sup_insert[symmetric]
Andreas@62652
  1385
  proof(rule Sup_least)
Andreas@62652
  1386
    fix z
Andreas@62652
  1387
    assume "z \<in> insert x Y"
Andreas@62652
  1388
    from assms obtain z' where "z' \<in> Y" by blast
Andreas@62652
  1389
    let ?z = "if z \<in> Y then x \<squnion> z else x \<squnion> z'"
wenzelm@62837
  1390
    have "z \<le> x \<squnion> ?z" using \<open>z' \<in> Y\<close> \<open>z \<in> insert x Y\<close> by auto
wenzelm@62837
  1391
    also have "\<dots> \<le> y" by(rule upper)(auto split: if_split_asm intro: \<open>z' \<in> Y\<close>)
Andreas@62652
  1392
    finally show "z \<le> y" .
Andreas@62652
  1393
  qed
Andreas@62652
  1394
qed
Andreas@62652
  1395
Andreas@62652
  1396
lemma mcont_sup1: "mcont Sup op \<le> Sup op \<le> (\<lambda>y. x \<squnion> y)"
Andreas@62652
  1397
by(auto 4 3 simp add: mcont_def sup.coboundedI1 sup.coboundedI2 intro!: monotoneI contI intro: Sup_image_sup[symmetric])
Andreas@62652
  1398
Andreas@62652
  1399
lemma mcont_sup2: "mcont Sup op \<le> Sup op \<le> (\<lambda>x. x \<squnion> y)"
Andreas@62652
  1400
by(subst sup_commute)(rule mcont_sup1)
Andreas@62652
  1401
Andreas@62652
  1402
lemma mcont2mcont_sup [cont_intro, simp]:
Andreas@62652
  1403
  "\<lbrakk> mcont lub ord Sup op \<le> (\<lambda>x. f x);
Andreas@62652
  1404
     mcont lub ord Sup op \<le> (\<lambda>x. g x) \<rbrakk>
Andreas@62652
  1405
  \<Longrightarrow> mcont lub ord Sup op \<le> (\<lambda>x. f x \<squnion> g x)"
Andreas@62652
  1406
by(best intro: ccpo.mcont2mcont'[OF complete_lattice_ccpo] mcont_sup1 mcont_sup2 ccpo.mcont_const[OF complete_lattice_ccpo])
Andreas@62652
  1407
Andreas@62652
  1408
end
Andreas@62652
  1409
Andreas@62652
  1410
lemmas [cont_intro] = admissible_leI[OF complete_lattice_ccpo']
Andreas@62652
  1411
Andreas@62652
  1412
context complete_distrib_lattice begin
Andreas@62652
  1413
Andreas@62652
  1414
lemma mcont_inf1: "mcont Sup op \<le> Sup op \<le> (\<lambda>y. x \<sqinter> y)"
Andreas@62652
  1415
by(auto intro: monotoneI contI simp add: le_infI2 inf_Sup mcont_def)
Andreas@62652
  1416
Andreas@62652
  1417
lemma mcont_inf2: "mcont Sup op \<le> Sup op \<le> (\<lambda>x. x \<sqinter> y)"
Andreas@62652
  1418
by(auto intro: monotoneI contI simp add: le_infI1 Sup_inf mcont_def)
Andreas@62652
  1419
Andreas@62652
  1420
lemma mcont2mcont_inf [cont_intro, simp]:
Andreas@62652
  1421
  "\<lbrakk> mcont lub ord Sup op \<le> (\<lambda>x. f x);
Andreas@62652
  1422
    mcont lub ord Sup op \<le> (\<lambda>x. g x) \<rbrakk>
Andreas@62652
  1423
  \<Longrightarrow> mcont lub ord Sup op \<le> (\<lambda>x. f x \<sqinter> g x)"
Andreas@62652
  1424
by(best intro: ccpo.mcont2mcont'[OF complete_lattice_ccpo] mcont_inf1 mcont_inf2 ccpo.mcont_const[OF complete_lattice_ccpo])
Andreas@62652
  1425
Andreas@62652
  1426
end
Andreas@62652
  1427
Andreas@62652
  1428
interpretation lfp: partial_function_definitions "op \<le> :: _ :: complete_lattice \<Rightarrow> _" Sup
Andreas@62652
  1429
by(rule complete_lattice_partial_function_definitions)
Andreas@62652
  1430
wenzelm@62837
  1431
declaration \<open>Partial_Function.init "lfp" @{term lfp.fixp_fun} @{term lfp.mono_body}
wenzelm@62837
  1432
  @{thm lfp.fixp_rule_uc} @{thm lfp.fixp_induct_uc} NONE\<close>
Andreas@62652
  1433
Andreas@62652
  1434
interpretation gfp: partial_function_definitions "op \<ge> :: _ :: complete_lattice \<Rightarrow> _" Inf
Andreas@62652
  1435
by(rule complete_lattice_partial_function_definitions_dual)
Andreas@62652
  1436
wenzelm@62837
  1437
declaration \<open>Partial_Function.init "gfp" @{term gfp.fixp_fun} @{term gfp.mono_body}
wenzelm@62837
  1438
  @{thm gfp.fixp_rule_uc} @{thm gfp.fixp_induct_uc} NONE\<close>
Andreas@62652
  1439
Andreas@62652
  1440
lemma insert_mono [partial_function_mono]:
Andreas@62652
  1441
   "monotone (fun_ord op \<subseteq>) op \<subseteq> A \<Longrightarrow> monotone (fun_ord op \<subseteq>) op \<subseteq> (\<lambda>y. insert x (A y))"
Andreas@62652
  1442
by(rule monotoneI)(auto simp add: fun_ord_def dest: monotoneD)
Andreas@62652
  1443
Andreas@62652
  1444
lemma mono2mono_insert [THEN lfp.mono2mono, cont_intro, simp]:
Andreas@62652
  1445
  shows monotone_insert: "monotone op \<subseteq> op \<subseteq> (insert x)"
Andreas@62652
  1446
by(rule monotoneI) blast
Andreas@62652
  1447
Andreas@62652
  1448
lemma mcont2mcont_insert[THEN lfp.mcont2mcont, cont_intro, simp]:
Andreas@62652
  1449
  shows mcont_insert: "mcont Union op \<subseteq> Union op \<subseteq> (insert x)"
Andreas@62652
  1450
by(blast intro: mcontI contI monotone_insert)
Andreas@62652
  1451
Andreas@62652
  1452
lemma mono2mono_image [THEN lfp.mono2mono, cont_intro, simp]:
Andreas@62652
  1453
  shows monotone_image: "monotone op \<subseteq> op \<subseteq> (op ` f)"
Andreas@62652
  1454
by(rule monotoneI) blast
Andreas@62652
  1455
Andreas@62652
  1456
lemma cont_image: "cont Union op \<subseteq> Union op \<subseteq> (op ` f)"
Andreas@62652
  1457
by(rule contI)(auto)
Andreas@62652
  1458
Andreas@62652
  1459
lemma mcont2mcont_image [THEN lfp.mcont2mcont, cont_intro, simp]:
Andreas@62652
  1460
  shows mcont_image: "mcont Union op \<subseteq> Union op \<subseteq> (op ` f)"
Andreas@62652
  1461
by(blast intro: mcontI monotone_image cont_image)
Andreas@62652
  1462
Andreas@62652
  1463
context complete_lattice begin
Andreas@62652
  1464
Andreas@62652
  1465
lemma monotone_Sup [cont_intro, simp]:
Andreas@62652
  1466
  "monotone ord op \<subseteq> f \<Longrightarrow> monotone ord op \<le> (\<lambda>x. \<Squnion>f x)"
Andreas@62652
  1467
by(blast intro: monotoneI Sup_least Sup_upper dest: monotoneD)
Andreas@62652
  1468
Andreas@62652
  1469
lemma cont_Sup:
Andreas@62652
  1470
  assumes "cont lub ord Union op \<subseteq> f"
Andreas@62652
  1471
  shows "cont lub ord Sup op \<le> (\<lambda>x. \<Squnion>f x)"
Andreas@62652
  1472
apply(rule contI)
Andreas@62652
  1473
apply(simp add: contD[OF assms])
Andreas@62652
  1474
apply(blast intro: Sup_least Sup_upper order_trans antisym)
Andreas@62652
  1475
done
Andreas@62652
  1476
Andreas@62652
  1477
lemma mcont_Sup: "mcont lub ord Union op \<subseteq> f \<Longrightarrow> mcont lub ord Sup op \<le> (\<lambda>x. \<Squnion>f x)"
Andreas@62652
  1478
unfolding mcont_def by(blast intro: monotone_Sup cont_Sup)
Andreas@62652
  1479
Andreas@62652
  1480
lemma monotone_SUP:
Andreas@62652
  1481
  "\<lbrakk> monotone ord op \<subseteq> f; \<And>y. monotone ord op \<le> (\<lambda>x. g x y) \<rbrakk> \<Longrightarrow> monotone ord op \<le> (\<lambda>x. \<Squnion>y\<in>f x. g x y)"
Andreas@62652
  1482
by(rule monotoneI)(blast dest: monotoneD intro: Sup_upper order_trans intro!: Sup_least)
Andreas@62652
  1483
Andreas@62652
  1484
lemma monotone_SUP2:
Andreas@62652
  1485
  "(\<And>y. y \<in> A \<Longrightarrow> monotone ord op \<le> (\<lambda>x. g x y)) \<Longrightarrow> monotone ord op \<le> (\<lambda>x. \<Squnion>y\<in>A. g x y)"
Andreas@62652
  1486
by(rule monotoneI)(blast intro: Sup_upper order_trans dest: monotoneD intro!: Sup_least)
Andreas@62652
  1487
Andreas@62652
  1488
lemma cont_SUP:
Andreas@62652
  1489
  assumes f: "mcont lub ord Union op \<subseteq> f"
Andreas@62652
  1490
  and g: "\<And>y. mcont lub ord Sup op \<le> (\<lambda>x. g x y)"
Andreas@62652
  1491
  shows "cont lub ord Sup op \<le> (\<lambda>x. \<Squnion>y\<in>f x. g x y)"
Andreas@62652
  1492
proof(rule contI)
Andreas@62652
  1493
  fix Y
Andreas@62652
  1494
  assume chain: "Complete_Partial_Order.chain ord Y"
Andreas@62652
  1495
    and Y: "Y \<noteq> {}"
Andreas@62652
  1496
  show "\<Squnion>(g (lub Y) ` f (lub Y)) = \<Squnion>((\<lambda>x. \<Squnion>(g x ` f x)) ` Y)" (is "?lhs = ?rhs")
Andreas@62652
  1497
  proof(rule antisym)
Andreas@62652
  1498
    show "?lhs \<le> ?rhs"
Andreas@62652
  1499
    proof(rule Sup_least)
Andreas@62652
  1500
      fix x
Andreas@62652
  1501
      assume "x \<in> g (lub Y) ` f (lub Y)"
Andreas@62652
  1502
      with mcont_contD[OF f chain Y] mcont_contD[OF g chain Y]
Andreas@62652
  1503
      obtain y z where "y \<in> Y" "z \<in> f y"
Andreas@62652
  1504
        and x: "x = \<Squnion>((\<lambda>x. g x z) ` Y)" by auto
Andreas@62652
  1505
      show "x \<le> ?rhs" unfolding x
Andreas@62652
  1506
      proof(rule Sup_least)
Andreas@62652
  1507
        fix u
Andreas@62652
  1508
        assume "u \<in> (\<lambda>x. g x z) ` Y"
Andreas@62652
  1509
        then obtain y' where "u = g y' z" "y' \<in> Y" by auto
wenzelm@62837
  1510
        from chain \<open>y \<in> Y\<close> \<open>y' \<in> Y\<close> have "ord y y' \<or> ord y' y" by(rule chainD)
Andreas@62652
  1511
        thus "u \<le> ?rhs"
Andreas@62652
  1512
        proof
wenzelm@62837
  1513
          note \<open>u = g y' z\<close> also
Andreas@62652
  1514
          assume "ord y y'"
Andreas@62652
  1515
          with f have "f y \<subseteq> f y'" by(rule mcont_monoD)
wenzelm@62837
  1516
          with \<open>z \<in> f y\<close>
Andreas@62652
  1517
          have "g y' z \<le> \<Squnion>(g y' ` f y')" by(auto intro: Sup_upper)
wenzelm@62837
  1518
          also have "\<dots> \<le> ?rhs" using \<open>y' \<in> Y\<close> by(auto intro: Sup_upper)
Andreas@62652
  1519
          finally show ?thesis .
Andreas@62652
  1520
        next
wenzelm@62837
  1521
          note \<open>u = g y' z\<close> also
Andreas@62652
  1522
          assume "ord y' y"
Andreas@62652
  1523
          with g have "g y' z \<le> g y z" by(rule mcont_monoD)
wenzelm@62837
  1524
          also have "\<dots> \<le> \<Squnion>(g y ` f y)" using \<open>z \<in> f y\<close>
Andreas@62652
  1525
            by(auto intro: Sup_upper)
wenzelm@62837
  1526
          also have "\<dots> \<le> ?rhs" using \<open>y \<in> Y\<close> by(auto intro: Sup_upper)
Andreas@62652
  1527
          finally show ?thesis .
Andreas@62652
  1528
        qed
Andreas@62652
  1529
      qed
Andreas@62652
  1530
    qed
Andreas@62652
  1531
  next
Andreas@62652
  1532
    show "?rhs \<le> ?lhs"
Andreas@62652
  1533
    proof(rule Sup_least)
Andreas@62652
  1534
      fix x
Andreas@62652
  1535
      assume "x \<in> (\<lambda>x. \<Squnion>(g x ` f x)) ` Y"
Andreas@62652
  1536
      then obtain y where x: "x = \<Squnion>(g y ` f y)" and "y \<in> Y" by auto
Andreas@62652
  1537
      show "x \<le> ?lhs" unfolding x
Andreas@62652
  1538
      proof(rule Sup_least)
Andreas@62652
  1539
        fix u
Andreas@62652
  1540
        assume "u \<in> g y ` f y"
Andreas@62652
  1541
        then obtain z where "u = g y z" "z \<in> f y" by auto
wenzelm@62837
  1542
        note \<open>u = g y z\<close>
Andreas@62652
  1543
        also have "g y z \<le> \<Squnion>((\<lambda>x. g x z) ` Y)"
wenzelm@62837
  1544
          using \<open>y \<in> Y\<close> by(auto intro: Sup_upper)
Andreas@62652
  1545
        also have "\<dots> = g (lub Y) z" by(simp add: mcont_contD[OF g chain Y])
wenzelm@62837
  1546
        also have "\<dots> \<le> ?lhs" using \<open>z \<in> f y\<close> \<open>y \<in> Y\<close>
Andreas@62652
  1547
          by(auto intro: Sup_upper simp add: mcont_contD[OF f chain Y])
Andreas@62652
  1548
        finally show "u \<le> ?lhs" .
Andreas@62652
  1549
      qed
Andreas@62652
  1550
    qed
Andreas@62652
  1551
  qed
Andreas@62652
  1552
qed
Andreas@62652
  1553
Andreas@62652
  1554
lemma mcont_SUP [cont_intro, simp]:
Andreas@62652
  1555
  "\<lbrakk> mcont lub ord Union op \<subseteq> f; \<And>y. mcont lub ord Sup op \<le> (\<lambda>x. g x y) \<rbrakk>
Andreas@62652
  1556
  \<Longrightarrow> mcont lub ord Sup op \<le> (\<lambda>x. \<Squnion>y\<in>f x. g x y)"
wenzelm@63092
  1557
by(blast intro: mcontI cont_SUP monotone_SUP mcont_mono)
Andreas@62652
  1558
Andreas@62652
  1559
end
Andreas@62652
  1560
Andreas@62652
  1561
lemma admissible_Ball [cont_intro, simp]:
Andreas@62652
  1562
  "\<lbrakk> \<And>x. ccpo.admissible lub ord (\<lambda>A. P A x);
Andreas@62652
  1563
     mcont lub ord Union op \<subseteq> f;
Andreas@62652
  1564
     class.ccpo lub ord (mk_less ord) \<rbrakk>
Andreas@62652
  1565
  \<Longrightarrow> ccpo.admissible lub ord (\<lambda>A. \<forall>x\<in>f A. P A x)"
Andreas@62652
  1566
unfolding Ball_def by simp
Andreas@62652
  1567
Andreas@62652
  1568
lemma admissible_Bex'[THEN admissible_subst, cont_intro, simp]:
Andreas@62652
  1569
  shows admissible_Bex: "ccpo.admissible Union op \<subseteq> (\<lambda>A. \<exists>x\<in>A. P x)"
Andreas@62652
  1570
by(rule ccpo.admissibleI)(auto)
Andreas@62652
  1571
wenzelm@62837
  1572
subsection \<open>Parallel fixpoint induction\<close>
Andreas@62652
  1573
Andreas@62652
  1574
context
Andreas@62652
  1575
  fixes luba :: "'a set \<Rightarrow> 'a"
Andreas@62652
  1576
  and orda :: "'a \<Rightarrow> 'a \<Rightarrow> bool"
Andreas@62652
  1577
  and lubb :: "'b set \<Rightarrow> 'b"
Andreas@62652
  1578
  and ordb :: "'b \<Rightarrow> 'b \<Rightarrow> bool"
Andreas@62652
  1579
  assumes a: "class.ccpo luba orda (mk_less orda)"
Andreas@62652
  1580
  and b: "class.ccpo lubb ordb (mk_less ordb)"
Andreas@62652
  1581
begin
Andreas@62652
  1582
Andreas@62652
  1583
interpretation a: ccpo luba orda "mk_less orda" by(rule a)
Andreas@62652
  1584
interpretation b: ccpo lubb ordb "mk_less ordb" by(rule b)
Andreas@62652
  1585
Andreas@62652
  1586
lemma ccpo_rel_prodI:
Andreas@62652
  1587
  "class.ccpo (prod_lub luba lubb) (rel_prod orda ordb) (mk_less (rel_prod orda ordb))"
Andreas@62652
  1588
  (is "class.ccpo ?lub ?ord ?ord'")
Andreas@62652
  1589
proof(intro class.ccpo.intro class.ccpo_axioms.intro)
Andreas@62652
  1590
  show "class.order ?ord ?ord'" by(rule order_rel_prodI) intro_locales
Andreas@62652
  1591
qed(auto 4 4 simp add: prod_lub_def intro: a.ccpo_Sup_upper b.ccpo_Sup_upper a.ccpo_Sup_least b.ccpo_Sup_least rev_image_eqI dest: chain_rel_prodD1 chain_rel_prodD2)
Andreas@62652
  1592
Andreas@62652
  1593
interpretation ab: ccpo "prod_lub luba lubb" "rel_prod orda ordb" "mk_less (rel_prod orda ordb)"
Andreas@62652
  1594
by(rule ccpo_rel_prodI)
Andreas@62652
  1595
Andreas@62652
  1596
lemma monotone_map_prod [simp]:
Andreas@62652
  1597
  "monotone (rel_prod orda ordb) (rel_prod ordc ordd) (map_prod f g) \<longleftrightarrow>
Andreas@62652
  1598
   monotone orda ordc f \<and> monotone ordb ordd g"
Andreas@62652
  1599
by(auto simp add: monotone_def)
Andreas@62652
  1600
Andreas@62652
  1601
lemma parallel_fixp_induct:
Andreas@62652
  1602
  assumes adm: "ccpo.admissible (prod_lub luba lubb) (rel_prod orda ordb) (\<lambda>x. P (fst x) (snd x))"
Andreas@62652
  1603
  and f: "monotone orda orda f"
Andreas@62652
  1604
  and g: "monotone ordb ordb g"
Andreas@62652
  1605
  and bot: "P (luba {}) (lubb {})"
Andreas@62652
  1606
  and step: "\<And>x y. P x y \<Longrightarrow> P (f x) (g y)"
Andreas@62652
  1607
  shows "P (ccpo.fixp luba orda f) (ccpo.fixp lubb ordb g)"
Andreas@62652
  1608
proof -
Andreas@62652
  1609
  let ?lub = "prod_lub luba lubb"
Andreas@62652
  1610
    and ?ord = "rel_prod orda ordb"
Andreas@62652
  1611
    and ?P = "\<lambda>(x, y). P x y"
Andreas@62652
  1612
  from adm have adm': "ccpo.admissible ?lub ?ord ?P" by(simp add: split_def)
Andreas@62652
  1613
  hence "?P (ccpo.fixp (prod_lub luba lubb) (rel_prod orda ordb) (map_prod f g))"
Andreas@62652
  1614
    by(rule ab.fixp_induct)(auto simp add: f g step bot)
Andreas@62652
  1615
  also have "ccpo.fixp (prod_lub luba lubb) (rel_prod orda ordb) (map_prod f g) = 
Andreas@62652
  1616
            (ccpo.fixp luba orda f, ccpo.fixp lubb ordb g)" (is "?lhs = (?rhs1, ?rhs2)")
Andreas@62652
  1617
  proof(rule ab.antisym)
Andreas@62652
  1618
    have "ccpo.admissible ?lub ?ord (\<lambda>xy. ?ord xy (?rhs1, ?rhs2))"
Andreas@62652
  1619
      by(rule admissible_leI[OF ccpo_rel_prodI])(auto simp add: prod_lub_def chain_empty intro: a.ccpo_Sup_least b.ccpo_Sup_least)
Andreas@62652
  1620
    thus "?ord ?lhs (?rhs1, ?rhs2)"
Andreas@62652
  1621
      by(rule ab.fixp_induct)(auto 4 3 dest: monotoneD[OF f] monotoneD[OF g] simp add: b.fixp_unfold[OF g, symmetric] a.fixp_unfold[OF f, symmetric] f g intro: a.ccpo_Sup_least b.ccpo_Sup_least chain_empty)
Andreas@62652
  1622
  next
Andreas@62652
  1623
    have "ccpo.admissible luba orda (\<lambda>x. orda x (fst ?lhs))"
Andreas@62652
  1624
      by(rule admissible_leI[OF a])(auto intro: a.ccpo_Sup_least simp add: chain_empty)
Andreas@62652
  1625
    hence "orda ?rhs1 (fst ?lhs)" using f
Andreas@62652
  1626
    proof(rule a.fixp_induct)
Andreas@62652
  1627
      fix x
Andreas@62652
  1628
      assume "orda x (fst ?lhs)"
Andreas@62652
  1629
      thus "orda (f x) (fst ?lhs)"
Andreas@62652
  1630
        by(subst ab.fixp_unfold)(auto simp add: f g dest: monotoneD[OF f])
Andreas@62652
  1631
    qed(auto intro: a.ccpo_Sup_least chain_empty)
Andreas@62652
  1632
    moreover
Andreas@62652
  1633
    have "ccpo.admissible lubb ordb (\<lambda>y. ordb y (snd ?lhs))"
Andreas@62652
  1634
      by(rule admissible_leI[OF b])(auto intro: b.ccpo_Sup_least simp add: chain_empty)
Andreas@62652
  1635
    hence "ordb ?rhs2 (snd ?lhs)" using g
Andreas@62652
  1636
    proof(rule b.fixp_induct)
Andreas@62652
  1637
      fix y
Andreas@62652
  1638
      assume "ordb y (snd ?lhs)"
Andreas@62652
  1639
      thus "ordb (g y) (snd ?lhs)"
Andreas@62652
  1640
        by(subst ab.fixp_unfold)(auto simp add: f g dest: monotoneD[OF g])
Andreas@62652
  1641
    qed(auto intro: b.ccpo_Sup_least chain_empty)
Andreas@62652
  1642
    ultimately show "?ord (?rhs1, ?rhs2) ?lhs"
Andreas@62652
  1643
      by(simp add: rel_prod_conv split_beta)
Andreas@62652
  1644
  qed
Andreas@62652
  1645
  finally show ?thesis by simp
Andreas@62652
  1646
qed
Andreas@62652
  1647
Andreas@62652
  1648
end
Andreas@62652
  1649
Andreas@62652
  1650
lemma parallel_fixp_induct_uc:
Andreas@62652
  1651
  assumes a: "partial_function_definitions orda luba"
Andreas@62652
  1652
  and b: "partial_function_definitions ordb lubb"
Andreas@62652
  1653
  and F: "\<And>x. monotone (fun_ord orda) orda (\<lambda>f. U1 (F (C1 f)) x)"
Andreas@62652
  1654
  and G: "\<And>y. monotone (fun_ord ordb) ordb (\<lambda>g. U2 (G (C2 g)) y)"
Andreas@62652
  1655
  and eq1: "f \<equiv> C1 (ccpo.fixp (fun_lub luba) (fun_ord orda) (\<lambda>f. U1 (F (C1 f))))"
Andreas@62652
  1656
  and eq2: "g \<equiv> C2 (ccpo.fixp (fun_lub lubb) (fun_ord ordb) (\<lambda>g. U2 (G (C2 g))))"
Andreas@62652
  1657
  and inverse: "\<And>f. U1 (C1 f) = f"
Andreas@62652
  1658
  and inverse2: "\<And>g. U2 (C2 g) = g"
Andreas@62652
  1659
  and adm: "ccpo.admissible (prod_lub (fun_lub luba) (fun_lub lubb)) (rel_prod (fun_ord orda) (fun_ord ordb)) (\<lambda>x. P (fst x) (snd x))"
Andreas@62652
  1660
  and bot: "P (\<lambda>_. luba {}) (\<lambda>_. lubb {})"
Andreas@62652
  1661
  and step: "\<And>f g. P (U1 f) (U2 g) \<Longrightarrow> P (U1 (F f)) (U2 (G g))"
Andreas@62652
  1662
  shows "P (U1 f) (U2 g)"
Andreas@62652
  1663
apply(unfold eq1 eq2 inverse inverse2)
Andreas@62652
  1664
apply(rule parallel_fixp_induct[OF partial_function_definitions.ccpo[OF a] partial_function_definitions.ccpo[OF b] adm])
Andreas@62652
  1665
using F apply(simp add: monotone_def fun_ord_def)
Andreas@62652
  1666
using G apply(simp add: monotone_def fun_ord_def)
Andreas@62652
  1667
apply(simp add: fun_lub_def bot)
Andreas@62652
  1668
apply(rule step, simp add: inverse inverse2)
Andreas@62652
  1669
done
Andreas@62652
  1670
Andreas@62652
  1671
lemmas parallel_fixp_induct_1_1 = parallel_fixp_induct_uc[
Andreas@62652
  1672
  of _ _ _ _ "\<lambda>x. x" _ "\<lambda>x. x" "\<lambda>x. x" _ "\<lambda>x. x",
Andreas@62652
  1673
  OF _ _ _ _ _ _ refl refl]
Andreas@62652
  1674
Andreas@62652
  1675
lemmas parallel_fixp_induct_2_2 = parallel_fixp_induct_uc[
Andreas@62652
  1676
  of _ _ _ _ "case_prod" _ "curry" "case_prod" _ "curry",
Andreas@62652
  1677
  where P="\<lambda>f g. P (curry f) (curry g)",
Andreas@62652
  1678
  unfolded case_prod_curry curry_case_prod curry_K,
Andreas@62652
  1679
  OF _ _ _ _ _ _ refl refl]
Andreas@62652
  1680
  for P
Andreas@62652
  1681
Andreas@62652
  1682
lemma monotone_fst: "monotone (rel_prod orda ordb) orda fst"
Andreas@62652
  1683
by(auto intro: monotoneI)
Andreas@62652
  1684
Andreas@62652
  1685
lemma mcont_fst: "mcont (prod_lub luba lubb) (rel_prod orda ordb) luba orda fst"
Andreas@62652
  1686
by(auto intro!: mcontI monotoneI contI simp add: prod_lub_def)
Andreas@62652
  1687
Andreas@62652
  1688
lemma mcont2mcont_fst [cont_intro, simp]:
Andreas@62652
  1689
  "mcont lub ord (prod_lub luba lubb) (rel_prod orda ordb) t
Andreas@62652
  1690
  \<Longrightarrow> mcont lub ord luba orda (\<lambda>x. fst (t x))"
Andreas@62652
  1691
by(auto intro!: mcontI monotoneI contI dest: mcont_monoD mcont_contD simp add: rel_prod_sel split_beta prod_lub_def image_image)
Andreas@62652
  1692
Andreas@62652
  1693
lemma monotone_snd: "monotone (rel_prod orda ordb) ordb snd"
Andreas@62652
  1694
by(auto intro: monotoneI)
Andreas@62652
  1695
Andreas@62652
  1696
lemma mcont_snd: "mcont (prod_lub luba lubb) (rel_prod orda ordb) lubb ordb snd"
Andreas@62652
  1697
by(auto intro!: mcontI monotoneI contI simp add: prod_lub_def)
Andreas@62652
  1698
Andreas@62652
  1699
lemma mcont2mcont_snd [cont_intro, simp]:
Andreas@62652
  1700
  "mcont lub ord (prod_lub luba lubb) (rel_prod orda ordb) t
Andreas@62652
  1701
  \<Longrightarrow> mcont lub ord lubb ordb (\<lambda>x. snd (t x))"
Andreas@62652
  1702
by(auto intro!: mcontI monotoneI contI dest: mcont_monoD mcont_contD simp add: rel_prod_sel split_beta prod_lub_def image_image)
Andreas@62652
  1703
Andreas@62652
  1704
context partial_function_definitions begin
Andreas@62652
  1705
text \<open>Specialised versions of @{thm [source] mcont_call} for admissibility proofs for parallel fixpoint inductions\<close>
Andreas@62652
  1706
lemmas mcont_call_fst [cont_intro] = mcont_call[THEN mcont2mcont, OF mcont_fst]
Andreas@62652
  1707
lemmas mcont_call_snd [cont_intro] = mcont_call[THEN mcont2mcont, OF mcont_snd]
Andreas@62652
  1708
end
Andreas@62652
  1709
Andreas@62652
  1710
end