src/HOLCF/Algebraic.thy
changeset 29237 e90d9d51106b
parent 28611 983c1855a7af
child 29252 ea97aa6aeba2
equal deleted inserted replaced
29236:51526dd8da8e 29237:e90d9d51106b
     1 (*  Title:      HOLCF/Algebraic.thy
     1 (*  Title:      HOLCF/Algebraic.thy
     2     ID:         $Id$
       
     3     Author:     Brian Huffman
     2     Author:     Brian Huffman
     4 *)
     3 *)
     5 
     4 
     6 header {* Algebraic deflations *}
     5 header {* Algebraic deflations *}
     7 
     6 
   159 lemma pre_deflation_d_f:
   158 lemma pre_deflation_d_f:
   160   assumes "finite_deflation d"
   159   assumes "finite_deflation d"
   161   assumes f: "\<And>x. f\<cdot>x \<sqsubseteq> x"
   160   assumes f: "\<And>x. f\<cdot>x \<sqsubseteq> x"
   162   shows "pre_deflation (d oo f)"
   161   shows "pre_deflation (d oo f)"
   163 proof
   162 proof
   164   interpret d: finite_deflation [d] by fact
   163   interpret d: finite_deflation d by fact
   165   fix x
   164   fix x
   166   show "\<And>x. (d oo f)\<cdot>x \<sqsubseteq> x"
   165   show "\<And>x. (d oo f)\<cdot>x \<sqsubseteq> x"
   167     by (simp, rule trans_less [OF d.less f])
   166     by (simp, rule trans_less [OF d.less f])
   168   show "finite (range (\<lambda>x. (d oo f)\<cdot>x))"
   167   show "finite (range (\<lambda>x. (d oo f)\<cdot>x))"
   169     by (rule finite_subset [OF _ d.finite_range], auto)
   168     by (rule finite_subset [OF _ d.finite_range], auto)
   172 lemma eventual_iterate_oo_fixed_iff:
   171 lemma eventual_iterate_oo_fixed_iff:
   173   assumes "finite_deflation d"
   172   assumes "finite_deflation d"
   174   assumes f: "\<And>x. f\<cdot>x \<sqsubseteq> x"
   173   assumes f: "\<And>x. f\<cdot>x \<sqsubseteq> x"
   175   shows "eventual (\<lambda>n. iterate n\<cdot>(d oo f))\<cdot>x = x \<longleftrightarrow> d\<cdot>x = x \<and> f\<cdot>x = x"
   174   shows "eventual (\<lambda>n. iterate n\<cdot>(d oo f))\<cdot>x = x \<longleftrightarrow> d\<cdot>x = x \<and> f\<cdot>x = x"
   176 proof -
   175 proof -
   177   interpret d: finite_deflation [d] by fact
   176   interpret d: finite_deflation d by fact
   178   let ?e = "d oo f"
   177   let ?e = "d oo f"
   179   interpret e: pre_deflation ["d oo f"]
   178   interpret e: pre_deflation "d oo f"
   180     using `finite_deflation d` f
   179     using `finite_deflation d` f
   181     by (rule pre_deflation_d_f)
   180     by (rule pre_deflation_d_f)
   182   let ?g = "eventual (\<lambda>n. iterate n\<cdot>?e)"
   181   let ?g = "eventual (\<lambda>n. iterate n\<cdot>?e)"
   183   show ?thesis
   182   show ?thesis
   184     apply (subst e.d_fixed_iff)
   183     apply (subst e.d_fixed_iff)
   214 by (rule typedef_po [OF type_definition_fin_defl sq_le_fin_defl_def])
   213 by (rule typedef_po [OF type_definition_fin_defl sq_le_fin_defl_def])
   215 
   214 
   216 lemma finite_deflation_Rep_fin_defl: "finite_deflation (Rep_fin_defl d)"
   215 lemma finite_deflation_Rep_fin_defl: "finite_deflation (Rep_fin_defl d)"
   217 using Rep_fin_defl by simp
   216 using Rep_fin_defl by simp
   218 
   217 
   219 interpretation Rep_fin_defl: finite_deflation ["Rep_fin_defl d"]
   218 interpretation Rep_fin_defl!: finite_deflation "Rep_fin_defl d"
   220 by (rule finite_deflation_Rep_fin_defl)
   219 by (rule finite_deflation_Rep_fin_defl)
   221 
   220 
   222 lemma fin_defl_lessI:
   221 lemma fin_defl_lessI:
   223   "(\<And>x. Rep_fin_defl a\<cdot>x = x \<Longrightarrow> Rep_fin_defl b\<cdot>x = x) \<Longrightarrow> a \<sqsubseteq> b"
   222   "(\<And>x. Rep_fin_defl a\<cdot>x = x \<Longrightarrow> Rep_fin_defl b\<cdot>x = x) \<Longrightarrow> a \<sqsubseteq> b"
   224 unfolding sq_le_fin_defl_def
   223 unfolding sq_le_fin_defl_def
   319 apply (rule profinite_compact_eq_approx)
   318 apply (rule profinite_compact_eq_approx)
   320 apply (erule subst)
   319 apply (erule subst)
   321 apply (rule Rep_fin_defl.compact)
   320 apply (rule Rep_fin_defl.compact)
   322 done
   321 done
   323 
   322 
   324 interpretation fin_defl: basis_take [sq_le fd_take]
   323 interpretation fin_defl!: basis_take sq_le fd_take
   325 apply default
   324 apply default
   326 apply (rule fd_take_less)
   325 apply (rule fd_take_less)
   327 apply (rule fd_take_idem)
   326 apply (rule fd_take_idem)
   328 apply (erule fd_take_mono)
   327 apply (erule fd_take_mono)
   329 apply (rule fd_take_chain, simp)
   328 apply (rule fd_take_chain, simp)
   369 lemma Rep_alg_defl_principal:
   368 lemma Rep_alg_defl_principal:
   370   "Rep_alg_defl (alg_defl_principal t) = {u. u \<sqsubseteq> t}"
   369   "Rep_alg_defl (alg_defl_principal t) = {u. u \<sqsubseteq> t}"
   371 unfolding alg_defl_principal_def
   370 unfolding alg_defl_principal_def
   372 by (simp add: Abs_alg_defl_inverse sq_le.ideal_principal)
   371 by (simp add: Abs_alg_defl_inverse sq_le.ideal_principal)
   373 
   372 
   374 interpretation alg_defl:
   373 interpretation alg_defl!:
   375   ideal_completion [sq_le fd_take alg_defl_principal Rep_alg_defl]
   374   ideal_completion sq_le fd_take alg_defl_principal Rep_alg_defl
   376 apply default
   375 apply default
   377 apply (rule ideal_Rep_alg_defl)
   376 apply (rule ideal_Rep_alg_defl)
   378 apply (erule Rep_alg_defl_lub)
   377 apply (erule Rep_alg_defl_lub)
   379 apply (rule Rep_alg_defl_principal)
   378 apply (rule Rep_alg_defl_principal)
   380 apply (simp only: sq_le_alg_defl_def)
   379 apply (simp only: sq_le_alg_defl_def)
   460 apply (drule alg_defl.compact_imp_principal, clarify)
   459 apply (drule alg_defl.compact_imp_principal, clarify)
   461 apply (simp add: cast_alg_defl_principal)
   460 apply (simp add: cast_alg_defl_principal)
   462 apply (rule finite_deflation_Rep_fin_defl)
   461 apply (rule finite_deflation_Rep_fin_defl)
   463 done
   462 done
   464 
   463 
   465 interpretation cast: deflation ["cast\<cdot>d"]
   464 interpretation cast!: deflation "cast\<cdot>d"
   466 by (rule deflation_cast)
   465 by (rule deflation_cast)
   467 
   466 
   468 lemma "cast\<cdot>(\<Squnion>i. alg_defl_principal (Abs_fin_defl (approx i)))\<cdot>x = x"
   467 lemma "cast\<cdot>(\<Squnion>i. alg_defl_principal (Abs_fin_defl (approx i)))\<cdot>x = x"
   469 apply (subst contlub_cfun_arg)
   468 apply (subst contlub_cfun_arg)
   470 apply (rule chainI)
   469 apply (rule chainI)
   484 lemma
   483 lemma
   485   assumes "ep_pair e p"
   484   assumes "ep_pair e p"
   486   constrains e :: "'a::profinite \<rightarrow> 'b::profinite"
   485   constrains e :: "'a::profinite \<rightarrow> 'b::profinite"
   487   shows "\<exists>d. cast\<cdot>d = e oo p"
   486   shows "\<exists>d. cast\<cdot>d = e oo p"
   488 proof
   487 proof
   489   interpret ep_pair [e p] by fact
   488   interpret ep_pair e p by fact
   490   let ?a = "\<lambda>i. e oo approx i oo p"
   489   let ?a = "\<lambda>i. e oo approx i oo p"
   491   have a: "\<And>i. finite_deflation (?a i)"
   490   have a: "\<And>i. finite_deflation (?a i)"
   492     apply (rule finite_deflation_e_d_p)
   491     apply (rule finite_deflation_e_d_p)
   493     apply (rule finite_deflation_approx)
   492     apply (rule finite_deflation_approx)
   494     done
   493     done
   515   assumes d: "\<And>x. cast\<cdot>d\<cdot>x = e\<cdot>(p\<cdot>x)"
   514   assumes d: "\<And>x. cast\<cdot>d\<cdot>x = e\<cdot>(p\<cdot>x)"
   516   obtains a :: "nat \<Rightarrow> 'a \<rightarrow> 'a" where
   515   obtains a :: "nat \<Rightarrow> 'a \<rightarrow> 'a" where
   517     "\<And>i. finite_deflation (a i)"
   516     "\<And>i. finite_deflation (a i)"
   518     "(\<Squnion>i. a i) = ID"
   517     "(\<Squnion>i. a i) = ID"
   519 proof
   518 proof
   520   interpret ep_pair [e p] by fact
   519   interpret ep_pair e p by fact
   521   let ?a = "\<lambda>i. p oo cast\<cdot>(approx i\<cdot>d) oo e"
   520   let ?a = "\<lambda>i. p oo cast\<cdot>(approx i\<cdot>d) oo e"
   522   show "\<And>i. finite_deflation (?a i)"
   521   show "\<And>i. finite_deflation (?a i)"
   523     apply (rule finite_deflation_p_d_e)
   522     apply (rule finite_deflation_p_d_e)
   524     apply (rule finite_deflation_cast)
   523     apply (rule finite_deflation_cast)
   525     apply (rule compact_approx)
   524     apply (rule compact_approx)