src/HOLCF/Pcpo.thy
author haftmann
Tue Jul 10 17:30:50 2007 +0200 (2007-07-10)
changeset 23709 fd31da8f752a
parent 22577 1a08fce38565
child 25131 2c8caac48ade
permissions -rw-r--r--
moved lfp_induct2 here
     1 (*  Title:      HOLCF/Pcpo.thy
     2     ID:         $Id$
     3     Author:     Franz Regensburger
     4 *)
     5 
     6 header {* Classes cpo and pcpo *}
     7 
     8 theory Pcpo
     9 imports Porder
    10 begin
    11 
    12 subsection {* Complete partial orders *}
    13 
    14 text {* The class cpo of chain complete partial orders *}
    15 
    16 axclass cpo < po
    17         -- {* class axiom: *}
    18   cpo:   "chain S \<Longrightarrow> \<exists>x. range S <<| x" 
    19 
    20 text {* in cpo's everthing equal to THE lub has lub properties for every chain *}
    21 
    22 lemma thelubE: "\<lbrakk>chain S; (\<Squnion>i. S i) = (l::'a::cpo)\<rbrakk> \<Longrightarrow> range S <<| l"
    23 by (blast dest: cpo intro: lubI)
    24 
    25 text {* Properties of the lub *}
    26 
    27 lemma is_ub_thelub: "chain (S::nat \<Rightarrow> 'a::cpo) \<Longrightarrow> S x \<sqsubseteq> (\<Squnion>i. S i)"
    28 by (blast dest: cpo intro: lubI [THEN is_ub_lub])
    29 
    30 lemma is_lub_thelub:
    31   "\<lbrakk>chain (S::nat \<Rightarrow> 'a::cpo); range S <| x\<rbrakk> \<Longrightarrow> (\<Squnion>i. S i) \<sqsubseteq> x"
    32 by (blast dest: cpo intro: lubI [THEN is_lub_lub])
    33 
    34 lemma lub_range_mono:
    35   "\<lbrakk>range X \<subseteq> range Y; chain Y; chain (X::nat \<Rightarrow> 'a::cpo)\<rbrakk>
    36     \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
    37 apply (erule is_lub_thelub)
    38 apply (rule ub_rangeI)
    39 apply (subgoal_tac "\<exists>j. X i = Y j")
    40 apply  clarsimp
    41 apply  (erule is_ub_thelub)
    42 apply auto
    43 done
    44 
    45 lemma lub_range_shift:
    46   "chain (Y::nat \<Rightarrow> 'a::cpo) \<Longrightarrow> (\<Squnion>i. Y (i + j)) = (\<Squnion>i. Y i)"
    47 apply (rule antisym_less)
    48 apply (rule lub_range_mono)
    49 apply    fast
    50 apply   assumption
    51 apply (erule chain_shift)
    52 apply (rule is_lub_thelub)
    53 apply assumption
    54 apply (rule ub_rangeI)
    55 apply (rule_tac y="Y (i + j)" in trans_less)
    56 apply (erule chain_mono3)
    57 apply (rule le_add1)
    58 apply (rule is_ub_thelub)
    59 apply (erule chain_shift)
    60 done
    61 
    62 lemma maxinch_is_thelub:
    63   "chain Y \<Longrightarrow> max_in_chain i Y = ((\<Squnion>i. Y i) = ((Y i)::'a::cpo))"
    64 apply (rule iffI)
    65 apply (fast intro!: thelubI lub_finch1)
    66 apply (unfold max_in_chain_def)
    67 apply (safe intro!: antisym_less)
    68 apply (fast elim!: chain_mono3)
    69 apply (drule sym)
    70 apply (force elim!: is_ub_thelub)
    71 done
    72 
    73 text {* the @{text "\<sqsubseteq>"} relation between two chains is preserved by their lubs *}
    74 
    75 lemma lub_mono:
    76   "\<lbrakk>chain (X::nat \<Rightarrow> 'a::cpo); chain Y; \<forall>k. X k \<sqsubseteq> Y k\<rbrakk> 
    77     \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
    78 apply (erule is_lub_thelub)
    79 apply (rule ub_rangeI)
    80 apply (rule trans_less)
    81 apply (erule spec)
    82 apply (erule is_ub_thelub)
    83 done
    84 
    85 text {* the = relation between two chains is preserved by their lubs *}
    86 
    87 lemma lub_equal:
    88   "\<lbrakk>chain (X::nat \<Rightarrow> 'a::cpo); chain Y; \<forall>k. X k = Y k\<rbrakk>
    89     \<Longrightarrow> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
    90 by (simp only: expand_fun_eq [symmetric])
    91 
    92 text {* more results about mono and = of lubs of chains *}
    93 
    94 lemma lub_mono2:
    95   "\<lbrakk>\<exists>j. \<forall>i>j. X i = Y i; chain (X::nat \<Rightarrow> 'a::cpo); chain Y\<rbrakk>
    96     \<Longrightarrow> (\<Squnion>i. X i) \<sqsubseteq> (\<Squnion>i. Y i)"
    97 apply (erule exE)
    98 apply (subgoal_tac "(\<Squnion>i. X (i + Suc j)) \<sqsubseteq> (\<Squnion>i. Y (i + Suc j))")
    99 apply (thin_tac "\<forall>i>j. X i = Y i")
   100 apply (simp only: lub_range_shift)
   101 apply simp
   102 done
   103 
   104 lemma lub_equal2:
   105   "\<lbrakk>\<exists>j. \<forall>i>j. X i = Y i; chain (X::nat \<Rightarrow> 'a::cpo); chain Y\<rbrakk>
   106     \<Longrightarrow> (\<Squnion>i. X i) = (\<Squnion>i. Y i)"
   107 by (blast intro: antisym_less lub_mono2 sym)
   108 
   109 lemma lub_mono3:
   110   "\<lbrakk>chain (Y::nat \<Rightarrow> 'a::cpo); chain X; \<forall>i. \<exists>j. Y i \<sqsubseteq> X j\<rbrakk>
   111     \<Longrightarrow> (\<Squnion>i. Y i) \<sqsubseteq> (\<Squnion>i. X i)"
   112 apply (erule is_lub_thelub)
   113 apply (rule ub_rangeI)
   114 apply (erule allE)
   115 apply (erule exE)
   116 apply (erule trans_less)
   117 apply (erule is_ub_thelub)
   118 done
   119 
   120 lemma ch2ch_lub:
   121   fixes Y :: "nat \<Rightarrow> nat \<Rightarrow> 'a::cpo"
   122   assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
   123   assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
   124   shows "chain (\<lambda>i. \<Squnion>j. Y i j)"
   125 apply (rule chainI)
   126 apply (rule lub_mono [rule_format, OF 2 2])
   127 apply (rule chainE [OF 1])
   128 done
   129 
   130 lemma diag_lub:
   131   fixes Y :: "nat \<Rightarrow> nat \<Rightarrow> 'a::cpo"
   132   assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
   133   assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
   134   shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>i. Y i i)"
   135 proof (rule antisym_less)
   136   have 3: "chain (\<lambda>i. Y i i)"
   137     apply (rule chainI)
   138     apply (rule trans_less)
   139     apply (rule chainE [OF 1])
   140     apply (rule chainE [OF 2])
   141     done
   142   have 4: "chain (\<lambda>i. \<Squnion>j. Y i j)"
   143     by (rule ch2ch_lub [OF 1 2])
   144   show "(\<Squnion>i. \<Squnion>j. Y i j) \<sqsubseteq> (\<Squnion>i. Y i i)"
   145     apply (rule is_lub_thelub [OF 4])
   146     apply (rule ub_rangeI)
   147     apply (rule lub_mono3 [rule_format, OF 2 3])
   148     apply (rule exI)
   149     apply (rule trans_less)
   150     apply (rule chain_mono3 [OF 1 le_maxI1])
   151     apply (rule chain_mono3 [OF 2 le_maxI2])
   152     done
   153   show "(\<Squnion>i. Y i i) \<sqsubseteq> (\<Squnion>i. \<Squnion>j. Y i j)"
   154     apply (rule lub_mono [rule_format, OF 3 4])
   155     apply (rule is_ub_thelub [OF 2])
   156     done
   157 qed
   158 
   159 lemma ex_lub:
   160   fixes Y :: "nat \<Rightarrow> nat \<Rightarrow> 'a::cpo"
   161   assumes 1: "\<And>j. chain (\<lambda>i. Y i j)"
   162   assumes 2: "\<And>i. chain (\<lambda>j. Y i j)"
   163   shows "(\<Squnion>i. \<Squnion>j. Y i j) = (\<Squnion>j. \<Squnion>i. Y i j)"
   164 by (simp add: diag_lub 1 2)
   165 
   166 
   167 subsection {* Pointed cpos *}
   168 
   169 text {* The class pcpo of pointed cpos *}
   170 
   171 axclass pcpo < cpo
   172   least: "\<exists>x. \<forall>y. x \<sqsubseteq> y"
   173 
   174 constdefs
   175   UU :: "'a::pcpo"
   176   "UU \<equiv> THE x. \<forall>y. x \<sqsubseteq> y"
   177 
   178 syntax (xsymbols)
   179   UU :: "'a::pcpo" ("\<bottom>")
   180 
   181 text {* derive the old rule minimal *}
   182  
   183 lemma UU_least: "\<forall>z. \<bottom> \<sqsubseteq> z"
   184 apply (unfold UU_def)
   185 apply (rule theI')
   186 apply (rule ex_ex1I)
   187 apply (rule least)
   188 apply (blast intro: antisym_less)
   189 done
   190 
   191 lemma minimal [iff]: "\<bottom> \<sqsubseteq> x"
   192 by (rule UU_least [THEN spec])
   193 
   194 lemma UU_reorient: "(\<bottom> = x) = (x = \<bottom>)"
   195 by auto
   196 
   197 ML_setup {*
   198 local
   199   val meta_UU_reorient = thm "UU_reorient" RS eq_reflection;
   200   fun reorient_proc sg _ (_ $ t $ u) =
   201     case u of
   202         Const("Pcpo.UU",_) => NONE
   203       | Const("HOL.zero", _) => NONE
   204       | Const("HOL.one", _) => NONE
   205       | Const("Numeral.number_of", _) $ _ => NONE
   206       | _ => SOME meta_UU_reorient;
   207 in
   208   val UU_reorient_simproc = 
   209     Simplifier.simproc @{theory} "UU_reorient_simproc" ["UU=x"] reorient_proc
   210 end;
   211 
   212 Addsimprocs [UU_reorient_simproc];
   213 *}
   214 
   215 text {* useful lemmas about @{term \<bottom>} *}
   216 
   217 lemma less_UU_iff [simp]: "(x \<sqsubseteq> \<bottom>) = (x = \<bottom>)"
   218 by (simp add: po_eq_conv)
   219 
   220 lemma eq_UU_iff: "(x = \<bottom>) = (x \<sqsubseteq> \<bottom>)"
   221 by simp
   222 
   223 lemma UU_I: "x \<sqsubseteq> \<bottom> \<Longrightarrow> x = \<bottom>"
   224 by (subst eq_UU_iff)
   225 
   226 lemma not_less2not_eq: "\<not> (x::'a::po) \<sqsubseteq> y \<Longrightarrow> x \<noteq> y"
   227 by auto
   228 
   229 lemma chain_UU_I: "\<lbrakk>chain Y; (\<Squnion>i. Y i) = \<bottom>\<rbrakk> \<Longrightarrow> \<forall>i. Y i = \<bottom>"
   230 apply (rule allI)
   231 apply (rule UU_I)
   232 apply (erule subst)
   233 apply (erule is_ub_thelub)
   234 done
   235 
   236 lemma chain_UU_I_inverse: "\<forall>i::nat. Y i = \<bottom> \<Longrightarrow> (\<Squnion>i. Y i) = \<bottom>"
   237 apply (rule lub_chain_maxelem)
   238 apply (erule spec)
   239 apply simp
   240 done
   241 
   242 lemma chain_UU_I_inverse2: "(\<Squnion>i. Y i) \<noteq> \<bottom> \<Longrightarrow> \<exists>i::nat. Y i \<noteq> \<bottom>"
   243 by (blast intro: chain_UU_I_inverse)
   244 
   245 lemma notUU_I: "\<lbrakk>x \<sqsubseteq> y; x \<noteq> \<bottom>\<rbrakk> \<Longrightarrow> y \<noteq> \<bottom>"
   246 by (blast intro: UU_I)
   247 
   248 lemma chain_mono2: "\<lbrakk>\<exists>j. Y j \<noteq> \<bottom>; chain Y\<rbrakk> \<Longrightarrow> \<exists>j. \<forall>i>j. Y i \<noteq> \<bottom>"
   249 by (blast dest: notUU_I chain_mono)
   250 
   251 subsection {* Chain-finite and flat cpos *}
   252 
   253 text {* further useful classes for HOLCF domains *}
   254 
   255 axclass chfin < po
   256   chfin: "\<forall>Y. chain Y \<longrightarrow> (\<exists>n. max_in_chain n Y)"
   257 
   258 axclass flat < pcpo
   259   ax_flat: "\<forall>x y. x \<sqsubseteq> y \<longrightarrow> (x = \<bottom>) \<or> (x = y)"
   260 
   261 text {* some properties for chfin and flat *}
   262 
   263 text {* chfin types are cpo *}
   264 
   265 lemma chfin_imp_cpo:
   266   "chain (S::nat \<Rightarrow> 'a::chfin) \<Longrightarrow> \<exists>x. range S <<| x"
   267 apply (frule chfin [rule_format])
   268 apply (blast intro: lub_finch1)
   269 done
   270 
   271 instance chfin < cpo
   272 by intro_classes (rule chfin_imp_cpo)
   273 
   274 text {* flat types are chfin *}
   275 
   276 lemma flat_imp_chfin: 
   277      "\<forall>Y::nat \<Rightarrow> 'a::flat. chain Y \<longrightarrow> (\<exists>n. max_in_chain n Y)"
   278 apply (unfold max_in_chain_def)
   279 apply clarify
   280 apply (case_tac "\<forall>i. Y i = \<bottom>")
   281 apply simp
   282 apply simp
   283 apply (erule exE)
   284 apply (rule_tac x="i" in exI)
   285 apply clarify
   286 apply (blast dest: chain_mono3 ax_flat [rule_format])
   287 done
   288 
   289 instance flat < chfin
   290 by intro_classes (rule flat_imp_chfin)
   291 
   292 text {* flat subclass of chfin; @{text adm_flat} not needed *}
   293 
   294 lemma flat_eq: "(a::'a::flat) \<noteq> \<bottom> \<Longrightarrow> a \<sqsubseteq> b = (a = b)"
   295 by (safe dest!: ax_flat [rule_format])
   296 
   297 lemma chfin2finch: "chain (Y::nat \<Rightarrow> 'a::chfin) \<Longrightarrow> finite_chain Y"
   298 by (simp add: chfin finite_chain_def)
   299 
   300 text {* lemmata for improved admissibility introdution rule *}
   301 
   302 lemma infinite_chain_adm_lemma:
   303   "\<lbrakk>chain Y; \<forall>i. P (Y i);  
   304     \<And>Y. \<lbrakk>chain Y; \<forall>i. P (Y i); \<not> finite_chain Y\<rbrakk> \<Longrightarrow> P (\<Squnion>i. Y i)\<rbrakk>
   305       \<Longrightarrow> P (\<Squnion>i. Y i)"
   306 apply (case_tac "finite_chain Y")
   307 prefer 2 apply fast
   308 apply (unfold finite_chain_def)
   309 apply safe
   310 apply (erule lub_finch1 [THEN thelubI, THEN ssubst])
   311 apply assumption
   312 apply (erule spec)
   313 done
   314 
   315 lemma increasing_chain_adm_lemma:
   316   "\<lbrakk>chain Y;  \<forall>i. P (Y i); \<And>Y. \<lbrakk>chain Y; \<forall>i. P (Y i);
   317     \<forall>i. \<exists>j>i. Y i \<noteq> Y j \<and> Y i \<sqsubseteq> Y j\<rbrakk> \<Longrightarrow> P (\<Squnion>i. Y i)\<rbrakk>
   318       \<Longrightarrow> P (\<Squnion>i. Y i)"
   319 apply (erule infinite_chain_adm_lemma)
   320 apply assumption
   321 apply (erule thin_rl)
   322 apply (unfold finite_chain_def)
   323 apply (unfold max_in_chain_def)
   324 apply (fast dest: le_imp_less_or_eq elim: chain_mono)
   325 done
   326 
   327 end