major cleanup: rewrote cpo proofs, removed obsolete lemmas, renamed some lemmas
authorhuffman
Wed Jun 08 01:40:39 2005 +0200 (2005-06-08)
changeset 163191ff2965cc2e7
parent 16318 45b12a01382f
child 16320 89917621becf
major cleanup: rewrote cpo proofs, removed obsolete lemmas, renamed some lemmas
src/HOLCF/Up.ML
src/HOLCF/Up.thy
     1.1 --- a/src/HOLCF/Up.ML	Wed Jun 08 00:59:46 2005 +0200
     1.2 +++ b/src/HOLCF/Up.ML	Wed Jun 08 01:40:39 2005 +0200
     1.3 @@ -4,59 +4,28 @@
     1.4  val Iup_def = thm "Iup_def";
     1.5  val Ifup_def = thm "Ifup_def";
     1.6  val less_up_def = thm "less_up_def";
     1.7 -val Abs_Up_inverse2 = thm "Abs_Up_inverse2";
     1.8 -val Exh_Up = thm "Exh_Up";
     1.9 -val inj_Abs_Up = thm "inj_Abs_Up";
    1.10 -val inj_Rep_Up = thm "inj_Rep_Up";
    1.11 -val inject_Iup = thm "inject_Iup";
    1.12 -val defined_Iup = thm "defined_Iup";
    1.13 -val upE = thm "upE";
    1.14  val Ifup1 = thm "Ifup1";
    1.15  val Ifup2 = thm "Ifup2";
    1.16 -val less_up1a = thm "less_up1a";
    1.17 -val less_up1b = thm "less_up1b";
    1.18 -val less_up1c = thm "less_up1c";
    1.19  val refl_less_up = thm "refl_less_up";
    1.20  val antisym_less_up = thm "antisym_less_up";
    1.21  val trans_less_up = thm "trans_less_up";
    1.22 -val inst_up_po = thm "inst_up_po";
    1.23  val minimal_up = thm "minimal_up";
    1.24 -val UU_up_def = thm "UU_up_def";
    1.25  val least_up = thm "least_up";
    1.26 -val less_up2b = thm "less_up2b";
    1.27 -val less_up2c = thm "less_up2c";
    1.28 -val monofun_Iup = thm "monofun_Iup";
    1.29 -val monofun_Ifup1 = thm "monofun_Ifup1";
    1.30  val monofun_Ifup2 = thm "monofun_Ifup2";
    1.31  val up_lemma1 = thm "up_lemma1";
    1.32 -val lub_up1a = thm "lub_up1a";
    1.33 -val lub_up1b = thm "lub_up1b";
    1.34 -val thelub_up1a = thm "thelub_up1a";
    1.35 -val thelub_up1b = thm "thelub_up1b";
    1.36  val cpo_up = thm "cpo_up";
    1.37  val up_def = thm "up_def";
    1.38  val fup_def = thm "fup_def";
    1.39  val inst_up_pcpo = thm "inst_up_pcpo";
    1.40 -val less_up3b = thm "less_up3b";
    1.41 -val defined_Iup2 = thm "defined_Iup2";
    1.42 -val contlub_Iup = thm "contlub_Iup";
    1.43  val cont_Iup = thm "cont_Iup";
    1.44 -val contlub_Ifup1 = thm "contlub_Ifup1";
    1.45 -val contlub_Ifup2 = thm "contlub_Ifup2";
    1.46  val cont_Ifup1 = thm "cont_Ifup1";
    1.47  val cont_Ifup2 = thm "cont_Ifup2";
    1.48  val Exh_Up1 = thm "Exh_Up1";
    1.49 -val inject_up = thm "inject_up";
    1.50 -val defined_up = thm "defined_up";
    1.51 +val up_inject = thm "up_inject";
    1.52 +val up_eq = thm "up_eq";
    1.53 +val up_defined = thm "up_defined";
    1.54 +val up_less = thm "up_less";
    1.55  val upE1 = thm "upE1";
    1.56  val fup1 = thm "fup1";
    1.57  val fup2 = thm "fup2";
    1.58 -val less_up4b = thm "less_up4b";
    1.59 -val less_up4c = thm "less_up4c";
    1.60 -val thelub_up2a = thm "thelub_up2a";
    1.61 -val thelub_up2b = thm "thelub_up2b";
    1.62 -val up_lemma2 = thm "up_lemma2";
    1.63 -val thelub_up2a_rev = thm "thelub_up2a_rev";
    1.64 -val thelub_up2b_rev = thm "thelub_up2b_rev";
    1.65 -val thelub_up3 = thm "thelub_up3";
    1.66  val fup3 = thm "fup3";
     2.1 --- a/src/HOLCF/Up.thy	Wed Jun 08 00:59:46 2005 +0200
     2.2 +++ b/src/HOLCF/Up.thy	Wed Jun 08 01:40:39 2005 +0200
     2.3 @@ -15,114 +15,79 @@
     2.4  
     2.5  subsection {* Definition of new type for lifting *}
     2.6  
     2.7 -typedef (Up) ('a) "u" = "UNIV :: (unit + 'a) set" ..
     2.8 +typedef (Up) 'a u = "UNIV :: 'a option set" ..
     2.9  
    2.10  consts
    2.11 -  Iup         :: "'a => ('a)u"
    2.12 -  Ifup        :: "('a->'b)=>('a)u => 'b::pcpo"
    2.13 +  Iup         :: "'a \<Rightarrow> 'a u"
    2.14 +  Ifup        :: "('a \<rightarrow> 'b::pcpo) \<Rightarrow> 'a u \<Rightarrow> 'b"
    2.15  
    2.16  defs
    2.17 -  Iup_def:     "Iup x == Abs_Up(Inr(x))"
    2.18 -  Ifup_def:    "Ifup(f)(x)== case Rep_Up(x) of Inl(y) => UU | Inr(z) => f$z"
    2.19 +  Iup_def:     "Iup x \<equiv> Abs_Up (Some x)"
    2.20 +  Ifup_def:    "Ifup f x \<equiv> case Rep_Up x of None \<Rightarrow> \<bottom> | Some z \<Rightarrow> f\<cdot>z"
    2.21  
    2.22  lemma Abs_Up_inverse2: "Rep_Up (Abs_Up y) = y"
    2.23  by (simp add: Up_def Abs_Up_inverse)
    2.24  
    2.25 -lemma Exh_Up: "z = Abs_Up(Inl ()) | (? x. z = Iup x)"
    2.26 +lemma Exh_Up: "z = Abs_Up None \<or> (\<exists>x. z = Iup x)"
    2.27  apply (unfold Iup_def)
    2.28  apply (rule Rep_Up_inverse [THEN subst])
    2.29 -apply (rule_tac s = "Rep_Up z" in sumE)
    2.30 -apply (rule disjI1)
    2.31 -apply (rule_tac f = "Abs_Up" in arg_cong)
    2.32 -apply (rule unit_eq [THEN subst])
    2.33 -apply assumption
    2.34 -apply (rule disjI2)
    2.35 -apply (rule exI)
    2.36 -apply (rule_tac f = "Abs_Up" in arg_cong)
    2.37 -apply assumption
    2.38 +apply (case_tac "Rep_Up z")
    2.39 +apply auto
    2.40  done
    2.41  
    2.42 -lemma inj_Abs_Up: "inj(Abs_Up)"
    2.43 +lemma inj_Abs_Up: "inj Abs_Up" (* worthless *)
    2.44  apply (rule inj_on_inverseI)
    2.45  apply (rule Abs_Up_inverse2)
    2.46  done
    2.47  
    2.48 -lemma inj_Rep_Up: "inj(Rep_Up)"
    2.49 +lemma inj_Rep_Up: "inj Rep_Up" (* worthless *)
    2.50  apply (rule inj_on_inverseI)
    2.51  apply (rule Rep_Up_inverse)
    2.52  done
    2.53  
    2.54 -lemma inject_Iup [dest!]: "Iup x=Iup y ==> x=y"
    2.55 -apply (unfold Iup_def)
    2.56 -apply (rule inj_Inr [THEN injD])
    2.57 -apply (rule inj_Abs_Up [THEN injD])
    2.58 -apply assumption
    2.59 -done
    2.60 +lemma Iup_eq [simp]: "(Iup x = Iup y) = (x = y)"
    2.61 +by (simp add: Iup_def Abs_Up_inject Up_def)
    2.62  
    2.63 -lemma defined_Iup: "Iup x~=Abs_Up(Inl ())"
    2.64 -apply (unfold Iup_def)
    2.65 -apply (rule notI)
    2.66 -apply (rule notE)
    2.67 -apply (rule Inl_not_Inr)
    2.68 -apply (rule sym)
    2.69 -apply (erule inj_Abs_Up [THEN injD])
    2.70 -done
    2.71 +lemma Iup_defined [simp]: "Iup x \<noteq> Abs_Up None"
    2.72 +by (simp add: Iup_def Abs_Up_inject Up_def)
    2.73  
    2.74 -lemma upE: "[| p=Abs_Up(Inl ()) ==> Q; !!x. p=Iup(x)==>Q|] ==>Q"
    2.75 -apply (rule Exh_Up [THEN disjE])
    2.76 -apply fast
    2.77 -apply (erule exE)
    2.78 -apply fast
    2.79 -done
    2.80 +lemma upE: "\<lbrakk>p = Abs_Up None \<Longrightarrow> Q; \<And>x. p = Iup x \<Longrightarrow> Q\<rbrakk> \<Longrightarrow> Q"
    2.81 +by (rule Exh_Up [THEN disjE], auto)
    2.82  
    2.83 -lemma Ifup1 [simp]: "Ifup(f)(Abs_Up(Inl ()))=UU"
    2.84 -apply (unfold Ifup_def)
    2.85 -apply (subst Abs_Up_inverse2)
    2.86 -apply (subst sum_case_Inl)
    2.87 -apply (rule refl)
    2.88 -done
    2.89 +lemma Ifup1 [simp]: "Ifup f (Abs_Up None) = \<bottom>"
    2.90 +by (simp add: Ifup_def Abs_Up_inverse2)
    2.91  
    2.92 -lemma Ifup2 [simp]: "Ifup(f)(Iup(x))=f$x"
    2.93 -apply (unfold Ifup_def Iup_def)
    2.94 -apply (subst Abs_Up_inverse2)
    2.95 -apply (subst sum_case_Inr)
    2.96 -apply (rule refl)
    2.97 -done
    2.98 +lemma Ifup2 [simp]: "Ifup f (Iup x) = f\<cdot>x"
    2.99 +by (simp add: Ifup_def Iup_def Abs_Up_inverse2)
   2.100  
   2.101  subsection {* Ordering on type @{typ "'a u"} *}
   2.102  
   2.103  instance u :: (sq_ord) sq_ord ..
   2.104  
   2.105  defs (overloaded)
   2.106 -  less_up_def: "(op <<) == (%x1 x2. case Rep_Up(x1) of                 
   2.107 -               Inl(y1) => True          
   2.108 -             | Inr(y2) => (case Rep_Up(x2) of Inl(z1) => False       
   2.109 -                                            | Inr(z2) => y2<<z2))"
   2.110 +  less_up_def: "(op \<sqsubseteq>) \<equiv> (\<lambda>x1 x2. case Rep_Up x1 of
   2.111 +               None \<Rightarrow> True
   2.112 +             | Some y1 \<Rightarrow> (case Rep_Up x2 of None \<Rightarrow> False
   2.113 +                                           | Some y2 \<Rightarrow> y1 \<sqsubseteq> y2))"
   2.114  
   2.115 -lemma less_up1a [iff]: 
   2.116 -        "Abs_Up(Inl ())<< z"
   2.117 +lemma minimal_up [iff]: "Abs_Up None \<sqsubseteq> z"
   2.118  by (simp add: less_up_def Abs_Up_inverse2)
   2.119  
   2.120 -lemma less_up1b [iff]: 
   2.121 -        "~(Iup x) << (Abs_Up(Inl ()))"
   2.122 +lemma not_Iup_less [iff]: "\<not> Iup x \<sqsubseteq> Abs_Up None"
   2.123  by (simp add: Iup_def less_up_def Abs_Up_inverse2)
   2.124  
   2.125 -lemma less_up1c [iff]: 
   2.126 -        "(Iup x) << (Iup y)=(x<<y)"
   2.127 +lemma Iup_less [iff]: "(Iup x \<sqsubseteq> Iup y) = (x \<sqsubseteq> y)"
   2.128  by (simp add: Iup_def less_up_def Abs_Up_inverse2)
   2.129  
   2.130  subsection {* Type @{typ "'a u"} is a partial order *}
   2.131  
   2.132 -lemma refl_less_up: "(p::'a u) << p"
   2.133 -apply (rule_tac p = "p" in upE)
   2.134 -apply auto
   2.135 -done
   2.136 +lemma refl_less_up: "(p::'a u) \<sqsubseteq> p"
   2.137 +by (rule_tac p = "p" in upE, auto)
   2.138  
   2.139 -lemma antisym_less_up: "[|(p1::'a u) << p2;p2 << p1|] ==> p1=p2"
   2.140 +lemma antisym_less_up: "\<lbrakk>(p1::'a u) \<sqsubseteq> p2; p2 \<sqsubseteq> p1\<rbrakk> \<Longrightarrow> p1 = p2"
   2.141  apply (rule_tac p = "p1" in upE)
   2.142 +apply (rule_tac p = "p2" in upE)
   2.143  apply simp
   2.144 -apply (rule_tac p = "p2" in upE)
   2.145 -apply (erule sym)
   2.146  apply simp
   2.147  apply (rule_tac p = "p2" in upE)
   2.148  apply simp
   2.149 @@ -131,210 +96,104 @@
   2.150  apply simp
   2.151  done
   2.152  
   2.153 -lemma trans_less_up: "[|(p1::'a u) << p2;p2 << p3|] ==> p1 << p3"
   2.154 +lemma trans_less_up: "\<lbrakk>(p1::'a u) \<sqsubseteq> p2; p2 \<sqsubseteq> p3\<rbrakk> \<Longrightarrow> p1 \<sqsubseteq> p3"
   2.155  apply (rule_tac p = "p1" in upE)
   2.156  apply simp
   2.157  apply (rule_tac p = "p2" in upE)
   2.158  apply simp
   2.159  apply (rule_tac p = "p3" in upE)
   2.160 -apply auto
   2.161 -apply (blast intro: trans_less)
   2.162 +apply simp
   2.163 +apply (auto elim: trans_less)
   2.164  done
   2.165  
   2.166  instance u :: (cpo) po
   2.167  by intro_classes
   2.168    (assumption | rule refl_less_up antisym_less_up trans_less_up)+
   2.169  
   2.170 -text {* for compatibility with old HOLCF-Version *}
   2.171 -lemma inst_up_po: "(op <<)=(%x1 x2. case Rep_Up(x1) of                 
   2.172 -                Inl(y1) => True  
   2.173 -              | Inr(y2) => (case Rep_Up(x2) of Inl(z1) => False  
   2.174 -                                             | Inr(z2) => y2<<z2))"
   2.175 -apply (fold less_up_def)
   2.176 -apply (rule refl)
   2.177 -done
   2.178 -
   2.179 -subsection {* Monotonicity of @{term Iup} and @{term Ifup} *}
   2.180 -
   2.181 -lemma monofun_Iup: "monofun(Iup)"
   2.182 -by (simp add: monofun_def)
   2.183 -
   2.184 -lemma monofun_Ifup1: "monofun(Ifup)"
   2.185 -apply (rule monofunI)
   2.186 -apply (rule less_fun [THEN iffD2, rule_format])
   2.187 -apply (rule_tac p = "xa" in upE)
   2.188 -apply simp
   2.189 -apply simp
   2.190 -apply (erule monofun_cfun_fun)
   2.191 -done
   2.192 -
   2.193 -lemma monofun_Ifup2: "monofun(Ifup(f))"
   2.194 -apply (rule monofunI)
   2.195 -apply (rule_tac p = "x" in upE)
   2.196 -apply simp
   2.197 -apply simp
   2.198 -apply (rule_tac p = "y" in upE)
   2.199 -apply simp
   2.200 -apply simp
   2.201 -apply (erule monofun_cfun_arg)
   2.202 -done
   2.203 -
   2.204  subsection {* Type @{typ "'a u"} is a cpo *}
   2.205  
   2.206 -text {* Some kind of surjectivity lemma *}
   2.207 -
   2.208 -lemma up_lemma1: "z=Iup(x) ==> Iup(Ifup(LAM x. x)(z)) = z"
   2.209 -by simp
   2.210 -
   2.211 -lemma lub_up1a: "[|chain(Y);EX i x. Y(i)=Iup(x)|]  
   2.212 -      ==> range(Y) <<| Iup(lub(range(%i.(Ifup (LAM x. x) (Y(i))))))"
   2.213 +lemma is_lub_Iup:
   2.214 +  "range S <<| x \<Longrightarrow> range (\<lambda>i. Iup (S i)) <<| Iup x"
   2.215  apply (rule is_lubI)
   2.216  apply (rule ub_rangeI)
   2.217 -apply (rule_tac p = "Y (i) " in upE)
   2.218 -apply (rule_tac s = "Abs_Up (Inl ())" and t = "Y (i) " in subst)
   2.219 -apply (erule sym)
   2.220 -apply (rule less_up1a)
   2.221 -apply (rule_tac t = "Y (i) " in up_lemma1 [THEN subst])
   2.222 -apply assumption
   2.223 -apply (rule less_up1c [THEN iffD2])
   2.224 -apply (rule is_ub_thelub)
   2.225 -apply (erule monofun_Ifup2 [THEN ch2ch_monofun])
   2.226 -apply (rule_tac p = "u" in upE)
   2.227 -apply (erule exE)
   2.228 -apply (erule exE)
   2.229 -apply (rule_tac P = "Y (i) <<Abs_Up (Inl ())" in notE)
   2.230 -apply (rule_tac s = "Iup (x) " and t = "Y (i) " in ssubst)
   2.231 -apply assumption
   2.232 -apply (rule less_up1b)
   2.233 -apply (erule subst)
   2.234 -apply (erule ub_rangeD)
   2.235 -apply (rule_tac t = "u" in up_lemma1 [THEN subst])
   2.236 -apply assumption
   2.237 -apply (rule less_up1c [THEN iffD2])
   2.238 -apply (rule is_lub_thelub)
   2.239 -apply (erule monofun_Ifup2 [THEN ch2ch_monofun])
   2.240 -apply (erule monofun_Ifup2 [THEN ub2ub_monofun])
   2.241 -done
   2.242 -
   2.243 -lemma lub_up1b: "[|chain(Y); ALL i x. Y(i)~=Iup(x)|] ==> range(Y) <<| Abs_Up (Inl ())"
   2.244 -apply (rule is_lubI)
   2.245 +apply (subst Iup_less)
   2.246 +apply (erule is_ub_lub)
   2.247 +apply (rule_tac p="u" in upE)
   2.248 +apply (drule ub_rangeD)
   2.249 +apply simp
   2.250 +apply simp
   2.251 +apply (erule is_lub_lub)
   2.252  apply (rule ub_rangeI)
   2.253 -apply (rule_tac p = "Y (i) " in upE)
   2.254 -apply (rule_tac s = "Abs_Up (Inl ())" and t = "Y (i) " in ssubst)
   2.255 -apply assumption
   2.256 -apply (rule refl_less)
   2.257 +apply (drule_tac i=i in ub_rangeD)
   2.258  apply simp
   2.259 -apply (rule less_up1a)
   2.260 -done
   2.261 -
   2.262 -lemmas thelub_up1a = lub_up1a [THEN thelubI, standard]
   2.263 -(*
   2.264 -[| chain ?Y1; EX i x. ?Y1 i = Iup x |] ==>
   2.265 - lub (range ?Y1) = Iup (lub (range (%i. Iup (LAM x. x) (?Y1 i))))
   2.266 -*)
   2.267 -
   2.268 -lemmas thelub_up1b = lub_up1b [THEN thelubI, standard]
   2.269 -(*
   2.270 -[| chain ?Y1; ! i x. ?Y1 i ~= Iup x |] ==>
   2.271 - lub (range ?Y1) = UU_up
   2.272 -*)
   2.273 -
   2.274 -text {* New versions where @{typ "'a"} does not have to be a pcpo *}
   2.275 -
   2.276 -lemma up_lemma1a: "EX x. z=Iup(x) ==> Iup(THE a. Iup a = z) = z"
   2.277 -apply (erule exE)
   2.278 -apply (rule theI)
   2.279 -apply (erule sym)
   2.280 -apply simp
   2.281 -apply (erule inject_Iup)
   2.282  done
   2.283  
   2.284  text {* Now some lemmas about chains of @{typ "'a u"} elements *}
   2.285  
   2.286 -lemma up_chain_lemma1:
   2.287 -  "[| chain Y; EX x. Y j = Iup x |] ==> EX x. Y (i + j) = Iup x"
   2.288 +lemma up_lemma1: "z \<noteq> Abs_Up None \<Longrightarrow> Iup (THE a. Iup a = z) = z"
   2.289 +by (rule_tac p="z" in upE, simp_all)
   2.290 +
   2.291 +lemma up_lemma2:
   2.292 +  "\<lbrakk>chain Y; Y j \<noteq> Abs_Up None\<rbrakk> \<Longrightarrow> Y (i + j) \<noteq> Abs_Up None"
   2.293 +apply (erule contrapos_nn)
   2.294  apply (drule_tac x="j" and y="i + j" in chain_mono3)
   2.295  apply (rule le_add2)
   2.296 -apply (rule_tac p="Y (i + j)" in upE)
   2.297 -apply auto
   2.298 +apply (rule_tac p="Y j" in upE)
   2.299 +apply assumption
   2.300 +apply simp
   2.301  done
   2.302  
   2.303 -lemma up_chain_lemma2:
   2.304 -  "[| chain Y; EX x. Y j = Iup x |] ==>
   2.305 -    Iup (THE a. Iup a = Y (i + j)) = Y (i + j)"
   2.306 -apply (drule_tac i=i in up_chain_lemma1)
   2.307 -apply assumption
   2.308 -apply (erule up_lemma1a)
   2.309 -done
   2.310 +lemma up_lemma3:
   2.311 +  "\<lbrakk>chain Y; Y j \<noteq> Abs_Up None\<rbrakk> \<Longrightarrow> Iup (THE a. Iup a = Y (i + j)) = Y (i + j)"
   2.312 +by (rule up_lemma1 [OF up_lemma2])
   2.313  
   2.314 -lemma up_chain_lemma3:
   2.315 -  "[| chain Y; EX x. Y j = Iup x |] ==> chain (%i. THE a. Iup a = Y (i + j))"
   2.316 +lemma up_lemma4:
   2.317 +  "\<lbrakk>chain Y; Y j \<noteq> Abs_Up None\<rbrakk> \<Longrightarrow> chain (\<lambda>i. THE a. Iup a = Y (i + j))"
   2.318  apply (rule chainI)
   2.319 -apply (rule less_up1c [THEN iffD1])
   2.320 -apply (simp only: up_chain_lemma2)
   2.321 +apply (rule Iup_less [THEN iffD1])
   2.322 +apply (subst up_lemma3, assumption+)+
   2.323  apply (simp add: chainE)
   2.324  done
   2.325  
   2.326 -lemma up_chain_lemma4:
   2.327 -  "[| chain Y; EX x. Y j = Iup x |] ==>
   2.328 -    (%i. Y (i + j)) = (%i. Iup (THE a. Iup a = Y (i + j)))"
   2.329 -apply (rule ext)
   2.330 -apply (rule up_chain_lemma2 [symmetric])
   2.331 -apply assumption+
   2.332 -done
   2.333 +lemma up_lemma5:
   2.334 +  "\<lbrakk>chain Y; Y j \<noteq> Abs_Up None\<rbrakk> \<Longrightarrow>
   2.335 +    (\<lambda>i. Y (i + j)) = (\<lambda>i. Iup (THE a. Iup a = Y (i + j)))"
   2.336 +by (rule ext, rule up_lemma3 [symmetric])
   2.337  
   2.338 -lemma is_lub_range_shift:
   2.339 -  "[| chain S; range (%i. S (i + j)) <<| x |] ==> range S <<| x"
   2.340 -apply (rule is_lubI)
   2.341 -apply (rule ub_rangeI)
   2.342 -apply (rule trans_less)
   2.343 -apply (erule chain_mono3)
   2.344 -apply (rule le_add1)
   2.345 -apply (erule is_ub_lub)
   2.346 -apply (erule is_lub_lub)
   2.347 -apply (rule ub_rangeI)
   2.348 -apply (erule ub_rangeD)
   2.349 +lemma up_lemma6:
   2.350 +  "\<lbrakk>chain Y; Y j \<noteq> Abs_Up None\<rbrakk>  
   2.351 +      \<Longrightarrow> range Y <<| Iup (\<Squnion>i. THE a. Iup a = Y(i + j))"
   2.352 +apply (rule_tac j1="j" in is_lub_range_shift [THEN iffD1])
   2.353 +apply assumption
   2.354 +apply (subst up_lemma5, assumption+)
   2.355 +apply (rule is_lub_Iup)
   2.356 +apply (rule thelubE [OF _ refl])
   2.357 +apply (rule up_lemma4, assumption+)
   2.358  done
   2.359  
   2.360 -lemma is_lub_Iup:
   2.361 -  "range S <<| x \<Longrightarrow> range (%i. Iup (S i)) <<| Iup x"
   2.362 -apply (rule is_lubI)
   2.363 -apply (rule ub_rangeI)
   2.364 -apply (subst less_up1c)
   2.365 -apply (erule is_ub_lub)
   2.366 -apply (rule_tac p=u in upE)
   2.367 -apply (drule ub_rangeD)
   2.368 -apply (simp only: less_up1b)
   2.369 -apply (simp only: less_up1c)
   2.370 -apply (erule is_lub_lub)
   2.371 -apply (rule ub_rangeI)
   2.372 -apply (drule_tac i=i in ub_rangeD)
   2.373 -apply (simp only: less_up1c)
   2.374 +lemma up_chain_cases:
   2.375 +  "chain Y \<Longrightarrow>
   2.376 +   (\<exists>A. chain A \<and> lub (range Y) = Iup (lub (range A)) \<and>
   2.377 +   (\<exists>j. \<forall>i. Y (i + j) = Iup (A i))) \<or> (Y = (\<lambda>i. Abs_Up None))"
   2.378 +apply (rule disjCI)
   2.379 +apply (simp add: expand_fun_eq)
   2.380 +apply (erule exE, rename_tac j)
   2.381 +apply (rule_tac x="\<lambda>i. THE a. Iup a = Y (i + j)" in exI)
   2.382 +apply (rule conjI)
   2.383 +apply (simp add: up_lemma4)
   2.384 +apply (rule conjI)
   2.385 +apply (simp add: up_lemma6 [THEN thelubI])
   2.386 +apply (rule_tac x=j in exI)
   2.387 +apply (simp add: up_lemma3)
   2.388  done
   2.389  
   2.390 -lemma lub_up1c: "[|chain(Y); EX x. Y(j)=Iup(x)|]  
   2.391 -      ==> range(Y) <<| Iup(lub(range(%i. THE a. Iup a = Y(i + j))))"
   2.392 -apply (rule_tac j=j in is_lub_range_shift)
   2.393 -apply assumption
   2.394 -apply (subst up_chain_lemma4)
   2.395 -apply assumption+
   2.396 -apply (rule is_lub_Iup)
   2.397 -apply (rule thelubE [OF _ refl])
   2.398 -apply (rule up_chain_lemma3)
   2.399 -apply assumption+
   2.400 -done
   2.401 -
   2.402 -lemmas thelub_up1c = lub_up1c [THEN thelubI, standard]
   2.403 -
   2.404 -lemma cpo_up: "chain(Y::nat=>('a)u) ==> EX x. range(Y) <<|x"
   2.405 -apply (case_tac "EX i x. Y i = Iup x")
   2.406 -apply (erule exE)
   2.407 -apply (rule exI)
   2.408 -apply (erule lub_up1c)
   2.409 -apply assumption
   2.410 -apply (rule exI)
   2.411 -apply (erule lub_up1b)
   2.412 -apply simp
   2.413 +lemma cpo_up: "chain (Y::nat \<Rightarrow> 'a u) \<Longrightarrow> \<exists>x. range Y <<| x"
   2.414 +apply (frule up_chain_cases, safe)
   2.415 +apply (rule_tac x="Iup (lub (range A))" in exI)
   2.416 +apply (erule_tac j1="j" in is_lub_range_shift [THEN iffD1])
   2.417 +apply (simp add: is_lub_Iup thelubE)
   2.418 +apply (rule_tac x="Abs_Up None" in exI)
   2.419 +apply (rule lub_const)
   2.420  done
   2.421  
   2.422  instance u :: (cpo) cpo
   2.423 @@ -342,13 +201,8 @@
   2.424  
   2.425  subsection {* Type @{typ "'a u"} is pointed *}
   2.426  
   2.427 -lemma minimal_up: "Abs_Up(Inl ()) << z"
   2.428 -by (rule less_up1a)
   2.429 -
   2.430 -lemmas UU_up_def = minimal_up [THEN minimal2UU, symmetric, standard]
   2.431 -
   2.432 -lemma least_up: "EX x::'a u. ALL y. x<<y"
   2.433 -apply (rule_tac x = "Abs_Up (Inl ())" in exI)
   2.434 +lemma least_up: "EX x::'a u. ALL y. x\<sqsubseteq>y"
   2.435 +apply (rule_tac x = "Abs_Up None" in exI)
   2.436  apply (rule minimal_up [THEN allI])
   2.437  done
   2.438  
   2.439 @@ -356,244 +210,106 @@
   2.440  by intro_classes (rule least_up)
   2.441  
   2.442  text {* for compatibility with old HOLCF-Version *}
   2.443 -lemma inst_up_pcpo: "UU = Abs_Up(Inl ())"
   2.444 -by (simp add: UU_def UU_up_def)
   2.445 +lemma inst_up_pcpo: "\<bottom> = Abs_Up None"
   2.446 +by (rule minimal_up [THEN UU_I, symmetric])
   2.447  
   2.448  text {* some lemmas restated for class pcpo *}
   2.449  
   2.450 -lemma less_up3b: "~ Iup(x) << UU"
   2.451 +lemma less_up3b: "~ Iup(x) \<sqsubseteq> \<bottom>"
   2.452  apply (subst inst_up_pcpo)
   2.453 -apply (rule less_up1b)
   2.454 +apply simp
   2.455  done
   2.456  
   2.457 -lemma defined_Iup2 [iff]: "Iup(x) ~= UU"
   2.458 +lemma defined_Iup2 [iff]: "Iup(x) ~= \<bottom>"
   2.459  apply (subst inst_up_pcpo)
   2.460 -apply (rule defined_Iup)
   2.461 +apply (rule Iup_defined)
   2.462  done
   2.463  
   2.464  subsection {* Continuity of @{term Iup} and @{term Ifup} *}
   2.465  
   2.466  text {* continuity for @{term Iup} *}
   2.467  
   2.468 -lemma cont_Iup [iff]: "cont(Iup)"
   2.469 +lemma cont_Iup: "cont Iup"
   2.470  apply (rule contI)
   2.471  apply (rule is_lub_Iup)
   2.472  apply (erule thelubE [OF _ refl])
   2.473  done
   2.474  
   2.475 -lemmas contlub_Iup = cont_Iup [THEN cont2contlub]
   2.476 -
   2.477  text {* continuity for @{term Ifup} *}
   2.478  
   2.479 -lemma contlub_Ifup1: "contlub(Ifup)"
   2.480 -apply (rule contlubI)
   2.481 -apply (rule trans)
   2.482 -apply (rule_tac [2] thelub_fun [symmetric])
   2.483 -apply (erule_tac [2] monofun_Ifup1 [THEN ch2ch_monofun])
   2.484 -apply (rule ext)
   2.485 -apply (rule_tac p = "x" in upE)
   2.486 -apply simp
   2.487 -apply (rule lub_const [THEN thelubI, symmetric])
   2.488 -apply simp
   2.489 -apply (erule contlub_cfun_fun)
   2.490 +lemma cont_Ifup1: "cont (\<lambda>f. Ifup f x)"
   2.491 +apply (rule contI)
   2.492 +apply (rule_tac p="x" in upE)
   2.493 +apply (simp add: lub_const)
   2.494 +apply (simp add: cont_cfun_fun)
   2.495  done
   2.496  
   2.497 -lemma contlub_Ifup2: "contlub(Ifup(f))"
   2.498 -apply (rule contlubI)
   2.499 -apply (case_tac "EX i x. Y i = Iup x")
   2.500 -apply (erule exE)
   2.501 -apply (subst thelub_up1c)
   2.502 -apply assumption
   2.503 -apply assumption
   2.504 -apply simp
   2.505 -prefer 2
   2.506 -apply (subst thelub_up1b)
   2.507 -apply assumption
   2.508 -apply simp
   2.509 -apply simp
   2.510 -apply (rule chain_UU_I_inverse [symmetric])
   2.511 -apply (rule allI)
   2.512 -apply (rule_tac p = "Y(i)" in upE)
   2.513 -apply simp
   2.514 +lemma monofun_Ifup2: "monofun (\<lambda>x. Ifup f x)"
   2.515 +apply (rule monofunI)
   2.516 +apply (rule_tac p="x" in upE)
   2.517  apply simp
   2.518 -apply (subst contlub_cfun_arg)
   2.519 -apply  (erule up_chain_lemma3)
   2.520 -apply  assumption
   2.521 -apply (rule trans)
   2.522 -prefer 2
   2.523 -apply (rule_tac j=i in lub_range_shift)
   2.524 -apply (erule monofun_Ifup2 [THEN ch2ch_monofun])
   2.525 -apply (rule lub_equal [rule_format])
   2.526 -apply (rule chain_monofun)
   2.527 -apply (erule up_chain_lemma3)
   2.528 -apply assumption
   2.529 -apply (rule monofun_Ifup2 [THEN ch2ch_monofun])
   2.530 -apply (erule chain_shift)
   2.531 -apply (drule_tac i=k in up_chain_lemma1)
   2.532 -apply assumption
   2.533 -apply clarify
   2.534 +apply (rule_tac p="y" in upE)
   2.535  apply simp
   2.536 -apply (subst the_equality)
   2.537 -apply (rule refl)
   2.538 -apply (erule inject_Iup)
   2.539 -apply (rule refl)
   2.540 +apply (simp add: monofun_cfun_arg)
   2.541  done
   2.542  
   2.543 -lemma cont_Ifup1: "cont(Ifup)"
   2.544 -apply (rule monocontlub2cont)
   2.545 -apply (rule monofun_Ifup1)
   2.546 -apply (rule contlub_Ifup1)
   2.547 -done
   2.548 -
   2.549 -lemma cont_Ifup2: "cont(Ifup(f))"
   2.550 -apply (rule monocontlub2cont)
   2.551 -apply (rule monofun_Ifup2)
   2.552 -apply (rule contlub_Ifup2)
   2.553 +lemma cont_Ifup2: "cont (\<lambda>x. Ifup f x)"
   2.554 +apply (rule contI)
   2.555 +apply (frule up_chain_cases, safe)
   2.556 +apply (rule_tac j1="j" in is_lub_range_shift [THEN iffD1])
   2.557 +apply (erule monofun_Ifup2 [THEN ch2ch_monofun])
   2.558 +apply (simp add: cont_cfun_arg)
   2.559 +apply (simp add: thelub_const lub_const)
   2.560  done
   2.561  
   2.562  subsection {* Continuous versions of constants *}
   2.563  
   2.564  constdefs  
   2.565 -        up  :: "'a -> ('a)u"
   2.566 -       "up  == (LAM x. Iup(x))"
   2.567 -        fup :: "('a->'c)-> ('a)u -> 'c::pcpo"
   2.568 -       "fup == (LAM f p. Ifup(f)(p))"
   2.569 +  up  :: "'a \<rightarrow> 'a u"
   2.570 +  "up \<equiv> \<Lambda> x. Iup x"
   2.571 +
   2.572 +  fup :: "('a \<rightarrow> 'b::pcpo) \<rightarrow> 'a u \<rightarrow> 'b"
   2.573 +  "fup \<equiv> \<Lambda> f p. Ifup f p"
   2.574  
   2.575  translations
   2.576 -"case l of up$x => t1" == "fup$(LAM x. t1)$l"
   2.577 +"case l of up\<cdot>x => t1" == "fup\<cdot>(LAM x. t1)\<cdot>l"
   2.578  
   2.579  text {* continuous versions of lemmas for @{typ "('a)u"} *}
   2.580  
   2.581 -lemma Exh_Up1: "z = UU | (EX x. z = up$x)"
   2.582 -apply (unfold up_def)
   2.583 -apply simp
   2.584 -apply (subst inst_up_pcpo)
   2.585 -apply (rule Exh_Up)
   2.586 -done
   2.587 -
   2.588 -lemma inject_up: "up$x=up$y ==> x=y"
   2.589 -apply (unfold up_def)
   2.590 -apply (rule inject_Iup)
   2.591 -apply auto
   2.592 -done
   2.593 -
   2.594 -lemma defined_up [simp]: " up$x ~= UU"
   2.595 -by (simp add: up_def)
   2.596 -
   2.597 -lemma upE1: 
   2.598 -        "[| p=UU ==> Q; !!x. p=up$x==>Q|] ==>Q"
   2.599 -apply (unfold up_def)
   2.600 -apply (rule upE)
   2.601 -apply (simp only: inst_up_pcpo)
   2.602 -apply fast
   2.603 -apply simp
   2.604 -done
   2.605 -
   2.606 -lemmas up_conts = cont_lemmas1 cont_Iup cont_Ifup1 cont_Ifup2 cont2cont_CF1L
   2.607 -
   2.608 -lemma fup1 [simp]: "fup$f$UU=UU"
   2.609 -apply (unfold up_def fup_def)
   2.610 -apply (subst inst_up_pcpo)
   2.611 -apply (subst beta_cfun)
   2.612 -apply (intro up_conts)
   2.613 -apply (subst beta_cfun)
   2.614 -apply (rule cont_Ifup2)
   2.615 -apply simp
   2.616 -done
   2.617 -
   2.618 -lemma fup2 [simp]: "fup$f$(up$x)=f$x"
   2.619 -apply (unfold up_def fup_def)
   2.620 -apply (simplesubst beta_cfun)
   2.621 -apply (rule cont_Iup)
   2.622 -apply (subst beta_cfun)
   2.623 -apply (intro up_conts)
   2.624 -apply (subst beta_cfun)
   2.625 -apply (rule cont_Ifup2)
   2.626 -apply simp
   2.627 +lemma Exh_Up1: "z = \<bottom> \<or> (\<exists>x. z = up\<cdot>x)"
   2.628 +apply (rule_tac p="z" in upE)
   2.629 +apply (simp add: inst_up_pcpo)
   2.630 +apply (simp add: up_def cont_Iup)
   2.631  done
   2.632  
   2.633 -lemma less_up4b: "~ up$x << UU"
   2.634 -by (simp add: up_def fup_def less_up3b)
   2.635 +lemma up_inject: "up\<cdot>x = up\<cdot>y \<Longrightarrow> x = y"
   2.636 +by (simp add: up_def cont_Iup)
   2.637  
   2.638 -lemma less_up4c: "(up$x << up$y) = (x<<y)"
   2.639 -by (simp add: up_def fup_def)
   2.640 +lemma up_eq: "(up\<cdot>x = up\<cdot>y) = (x = y)"
   2.641 +by (rule iffI, erule up_inject, simp)
   2.642 +
   2.643 +lemma up_defined [simp]: " up\<cdot>x \<noteq> \<bottom>"
   2.644 +by (simp add: up_def cont_Iup inst_up_pcpo)
   2.645  
   2.646 -lemma thelub_up2a: 
   2.647 -"[| chain(Y); EX i x. Y(i) = up$x |] ==> 
   2.648 -       lub(range(Y)) = up$(lub(range(%i. fup$(LAM x. x)$(Y i))))"
   2.649 -apply (unfold up_def fup_def)
   2.650 -apply (subst beta_cfun)
   2.651 -apply (rule cont_Iup)
   2.652 -apply (subst beta_cfun)
   2.653 -apply (intro up_conts)
   2.654 -apply (subst beta_cfun [THEN ext])
   2.655 -apply (rule cont_Ifup2)
   2.656 -apply (rule thelub_up1a)
   2.657 -apply assumption
   2.658 -apply (erule exE)
   2.659 -apply (erule exE)
   2.660 -apply (rule exI)
   2.661 -apply (rule exI)
   2.662 -apply (erule box_equals)
   2.663 -apply (rule refl)
   2.664 -apply simp
   2.665 -done
   2.666 +lemma not_up_less_UU [simp]: "\<not> up\<cdot>x \<sqsubseteq> \<bottom>"
   2.667 +by (simp add: eq_UU_iff [symmetric])
   2.668  
   2.669 -lemma thelub_up2b: 
   2.670 -"[| chain(Y); ! i x. Y(i) ~= up$x |] ==> lub(range(Y)) = UU"
   2.671 -apply (unfold up_def fup_def)
   2.672 -apply (subst inst_up_pcpo)
   2.673 -apply (erule thelub_up1b)
   2.674 -apply simp
   2.675 +lemma up_less: "(up\<cdot>x \<sqsubseteq> up\<cdot>y) = (x \<sqsubseteq> y)"
   2.676 +by (simp add: up_def cont_Iup)
   2.677 +
   2.678 +lemma upE1: "\<lbrakk>p = \<bottom> \<Longrightarrow> Q; \<And>x. p = up\<cdot>x \<Longrightarrow> Q\<rbrakk> \<Longrightarrow> Q"
   2.679 +apply (rule_tac p="p" in upE)
   2.680 +apply (simp add: inst_up_pcpo)
   2.681 +apply (simp add: up_def cont_Iup)
   2.682  done
   2.683  
   2.684 -lemma up_lemma2: "(EX x. z = up$x) = (z~=UU)"
   2.685 -apply (rule iffI)
   2.686 -apply (erule exE)
   2.687 -apply simp
   2.688 -apply (rule_tac p = "z" in upE1)
   2.689 -apply simp
   2.690 -apply (erule exI)
   2.691 -done
   2.692 -
   2.693 -lemma thelub_up2a_rev:
   2.694 -  "[| chain(Y); lub(range(Y)) = up$x |] ==> EX i x. Y(i) = up$x"
   2.695 -apply (rule exE)
   2.696 -apply (rule chain_UU_I_inverse2)
   2.697 -apply (rule up_lemma2 [THEN iffD1])
   2.698 -apply (erule exI)
   2.699 -apply (rule exI)
   2.700 -apply (rule up_lemma2 [THEN iffD2])
   2.701 -apply assumption
   2.702 -done
   2.703 -
   2.704 -lemma thelub_up2b_rev:
   2.705 -  "[| chain(Y); lub(range(Y)) = UU |] ==> ! i x.  Y(i) ~= up$x"
   2.706 -by (blast dest!: chain_UU_I [THEN spec] exI [THEN up_lemma2 [THEN iffD1]])
   2.707 +lemma fup1 [simp]: "fup\<cdot>f\<cdot>\<bottom> = \<bottom>"
   2.708 +by (simp add: fup_def cont_Ifup1 cont_Ifup2 inst_up_pcpo)
   2.709  
   2.710 -lemma thelub_up3: "chain(Y) ==> lub(range(Y)) = UU |  
   2.711 -                   lub(range(Y)) = up$(lub(range(%i. fup$(LAM x. x)$(Y i))))"
   2.712 -apply (rule disjE)
   2.713 -apply (rule_tac [2] disjI1)
   2.714 -apply (rule_tac [2] thelub_up2b)
   2.715 -prefer 2 apply (assumption)
   2.716 -prefer 2 apply (assumption)
   2.717 -apply (rule_tac [2] disjI2)
   2.718 -apply (rule_tac [2] thelub_up2a)
   2.719 -prefer 2 apply (assumption)
   2.720 -prefer 2 apply (assumption)
   2.721 -apply fast
   2.722 -done
   2.723 +lemma fup2 [simp]: "fup\<cdot>f\<cdot>(up\<cdot>x) = f\<cdot>x"
   2.724 +by (simp add: up_def fup_def cont_Iup cont_Ifup1 cont_Ifup2 )
   2.725  
   2.726 -lemma fup3: "fup$up$x=x"
   2.727 -apply (rule_tac p = "x" in upE1)
   2.728 -apply simp
   2.729 -apply simp
   2.730 -done
   2.731 -
   2.732 -text {* for backward compatibility *}
   2.733 -
   2.734 -lemmas less_up2b = less_up1b
   2.735 -lemmas less_up2c = less_up1c
   2.736 +lemma fup3: "fup\<cdot>up\<cdot>x = x"
   2.737 +by (rule_tac p=x in upE1, simp_all)
   2.738  
   2.739  end