equal
deleted
inserted
replaced
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) |