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