(* Title: HOL/HOLCF/Deflation.thy Author: Brian Huffman *) section ‹Continuous deflations and ep-pairs› theory Deflation imports Cfun begin default_sort cpo subsection ‹Continuous deflations› locale deflation = fixes d :: "'a → 'a" assumes idem: "⋀x. d⋅(d⋅x) = d⋅x" assumes below: "⋀x. d⋅x ⊑ x" begin lemma below_ID: "d ⊑ ID" by (rule cfun_belowI, simp add: below) text ‹The set of fixed points is the same as the range.› lemma fixes_eq_range: "{x. d⋅x = x} = range (λx. d⋅x)" by (auto simp add: eq_sym_conv idem) lemma range_eq_fixes: "range (λx. d⋅x) = {x. d⋅x = x}" by (auto simp add: eq_sym_conv idem) text ‹ The pointwise ordering on deflation functions coincides with the subset ordering of their sets of fixed-points. › lemma belowI: assumes f: "⋀x. d⋅x = x ⟹ f⋅x = x" shows "d ⊑ f" proof (rule cfun_belowI) fix x from below have "f⋅(d⋅x) ⊑ f⋅x" by (rule monofun_cfun_arg) also from idem have "f⋅(d⋅x) = d⋅x" by (rule f) finally show "d⋅x ⊑ f⋅x" . qed lemma belowD: "⟦f ⊑ d; f⋅x = x⟧ ⟹ d⋅x = x" proof (rule below_antisym) from below show "d⋅x ⊑ x" . next assume "f ⊑ d" hence "f⋅x ⊑ d⋅x" by (rule monofun_cfun_fun) also assume "f⋅x = x" finally show "x ⊑ d⋅x" . qed end lemma deflation_strict: "deflation d ⟹ d⋅⊥ = ⊥" by (rule deflation.below [THEN bottomI]) lemma adm_deflation: "adm (λd. deflation d)" by (simp add: deflation_def) lemma deflation_ID: "deflation ID" by (simp add: deflation.intro) lemma deflation_bottom: "deflation ⊥" by (simp add: deflation.intro) lemma deflation_below_iff: "⟦deflation p; deflation q⟧ ⟹ p ⊑ q ⟷ (∀x. p⋅x = x ⟶ q⋅x = x)" apply safe apply (simp add: deflation.belowD) apply (simp add: deflation.belowI) done text ‹ The composition of two deflations is equal to the lesser of the two (if they are comparable). › lemma deflation_below_comp1: assumes "deflation f" assumes "deflation g" shows "f ⊑ g ⟹ f⋅(g⋅x) = f⋅x" proof (rule below_antisym) interpret g: deflation g by fact from g.below show "f⋅(g⋅x) ⊑ f⋅x" by (rule monofun_cfun_arg) next interpret f: deflation f by fact assume "f ⊑ g" hence "f⋅x ⊑ g⋅x" by (rule monofun_cfun_fun) hence "f⋅(f⋅x) ⊑ f⋅(g⋅x)" by (rule monofun_cfun_arg) also have "f⋅(f⋅x) = f⋅x" by (rule f.idem) finally show "f⋅x ⊑ f⋅(g⋅x)" . qed lemma deflation_below_comp2: "⟦deflation f; deflation g; f ⊑ g⟧ ⟹ g⋅(f⋅x) = f⋅x" by (simp only: deflation.belowD deflation.idem) subsection ‹Deflations with finite range› lemma finite_range_imp_finite_fixes: "finite (range f) ⟹ finite {x. f x = x}" proof - have "{x. f x = x} ⊆ range f" by (clarify, erule subst, rule rangeI) moreover assume "finite (range f)" ultimately show "finite {x. f x = x}" by (rule finite_subset) qed locale finite_deflation = deflation + assumes finite_fixes: "finite {x. d⋅x = x}" begin lemma finite_range: "finite (range (λx. d⋅x))" by (simp add: range_eq_fixes finite_fixes) lemma finite_image: "finite ((λx. d⋅x) ` A)" by (rule finite_subset [OF image_mono [OF subset_UNIV] finite_range]) lemma compact: "compact (d⋅x)" proof (rule compactI2) fix Y :: "nat ⇒ 'a" assume Y: "chain Y" have "finite_chain (λi. d⋅(Y i))" proof (rule finite_range_imp_finch) show "chain (λi. d⋅(Y i))" using Y by simp have "range (λi. d⋅(Y i)) ⊆ range (λx. d⋅x)" by clarsimp thus "finite (range (λi. d⋅(Y i)))" using finite_range by (rule finite_subset) qed hence "∃j. (⨆i. d⋅(Y i)) = d⋅(Y j)" by (simp add: finite_chain_def maxinch_is_thelub Y) then obtain j where j: "(⨆i. d⋅(Y i)) = d⋅(Y j)" .. assume "d⋅x ⊑ (⨆i. Y i)" hence "d⋅(d⋅x) ⊑ d⋅(⨆i. Y i)" by (rule monofun_cfun_arg) hence "d⋅x ⊑ (⨆i. d⋅(Y i))" by (simp add: contlub_cfun_arg Y idem) hence "d⋅x ⊑ d⋅(Y j)" using j by simp hence "d⋅x ⊑ Y j" using below by (rule below_trans) thus "∃j. d⋅x ⊑ Y j" .. qed end lemma finite_deflation_intro: "deflation d ⟹ finite {x. d⋅x = x} ⟹ finite_deflation d" by (intro finite_deflation.intro finite_deflation_axioms.intro) lemma finite_deflation_imp_deflation: "finite_deflation d ⟹ deflation d" unfolding finite_deflation_def by simp lemma finite_deflation_bottom: "finite_deflation ⊥" by standard simp_all subsection ‹Continuous embedding-projection pairs› locale ep_pair = fixes e :: "'a → 'b" and p :: "'b → 'a" assumes e_inverse [simp]: "⋀x. p⋅(e⋅x) = x" and e_p_below: "⋀y. e⋅(p⋅y) ⊑ y" begin lemma e_below_iff [simp]: "e⋅x ⊑ e⋅y ⟷ x ⊑ y" proof assume "e⋅x ⊑ e⋅y" hence "p⋅(e⋅x) ⊑ p⋅(e⋅y)" by (rule monofun_cfun_arg) thus "x ⊑ y" by simp next assume "x ⊑ y" thus "e⋅x ⊑ e⋅y" by (rule monofun_cfun_arg) qed lemma e_eq_iff [simp]: "e⋅x = e⋅y ⟷ x = y" unfolding po_eq_conv e_below_iff .. lemma p_eq_iff: "⟦e⋅(p⋅x) = x; e⋅(p⋅y) = y⟧ ⟹ p⋅x = p⋅y ⟷ x = y" by (safe, erule subst, erule subst, simp) lemma p_inverse: "(∃x. y = e⋅x) = (e⋅(p⋅y) = y)" by (auto, rule exI, erule sym) lemma e_below_iff_below_p: "e⋅x ⊑ y ⟷ x ⊑ p⋅y" proof assume "e⋅x ⊑ y" then have "p⋅(e⋅x) ⊑ p⋅y" by (rule monofun_cfun_arg) then show "x ⊑ p⋅y" by simp next assume "x ⊑ p⋅y" then have "e⋅x ⊑ e⋅(p⋅y)" by (rule monofun_cfun_arg) then show "e⋅x ⊑ y" using e_p_below by (rule below_trans) qed lemma compact_e_rev: "compact (e⋅x) ⟹ compact x" proof - assume "compact (e⋅x)" hence "adm (λy. e⋅x \<notsqsubseteq> y)" by (rule compactD) hence "adm (λy. e⋅x \<notsqsubseteq> e⋅y)" by (rule adm_subst [OF cont_Rep_cfun2]) hence "adm (λy. x \<notsqsubseteq> y)" by simp thus "compact x" by (rule compactI) qed lemma compact_e: "compact x ⟹ compact (e⋅x)" proof - assume "compact x" hence "adm (λy. x \<notsqsubseteq> y)" by (rule compactD) hence "adm (λy. x \<notsqsubseteq> p⋅y)" by (rule adm_subst [OF cont_Rep_cfun2]) hence "adm (λy. e⋅x \<notsqsubseteq> y)" by (simp add: e_below_iff_below_p) thus "compact (e⋅x)" by (rule compactI) qed lemma compact_e_iff: "compact (e⋅x) ⟷ compact x" by (rule iffI [OF compact_e_rev compact_e]) text ‹Deflations from ep-pairs› lemma deflation_e_p: "deflation (e oo p)" by (simp add: deflation.intro e_p_below) lemma deflation_e_d_p: assumes "deflation d" shows "deflation (e oo d oo p)" proof interpret deflation d by fact fix x :: 'b show "(e oo d oo p)⋅((e oo d oo p)⋅x) = (e oo d oo p)⋅x" by (simp add: idem) show "(e oo d oo p)⋅x ⊑ x" by (simp add: e_below_iff_below_p below) qed lemma finite_deflation_e_d_p: assumes "finite_deflation d" shows "finite_deflation (e oo d oo p)" proof interpret finite_deflation d by fact fix x :: 'b show "(e oo d oo p)⋅((e oo d oo p)⋅x) = (e oo d oo p)⋅x" by (simp add: idem) show "(e oo d oo p)⋅x ⊑ x" by (simp add: e_below_iff_below_p below) have "finite ((λx. e⋅x) ` (λx. d⋅x) ` range (λx. p⋅x))" by (simp add: finite_image) hence "finite (range (λx. (e oo d oo p)⋅x))" by (simp add: image_image) thus "finite {x. (e oo d oo p)⋅x = x}" by (rule finite_range_imp_finite_fixes) qed lemma deflation_p_d_e: assumes "deflation d" assumes d: "⋀x. d⋅x ⊑ e⋅(p⋅x)" shows "deflation (p oo d oo e)" proof - interpret d: deflation d by fact { fix x have "d⋅(e⋅x) ⊑ e⋅x" by (rule d.below) hence "p⋅(d⋅(e⋅x)) ⊑ p⋅(e⋅x)" by (rule monofun_cfun_arg) hence "(p oo d oo e)⋅x ⊑ x" by simp } note p_d_e_below = this show ?thesis proof fix x show "(p oo d oo e)⋅x ⊑ x" by (rule p_d_e_below) next fix x show "(p oo d oo e)⋅((p oo d oo e)⋅x) = (p oo d oo e)⋅x" proof (rule below_antisym) show "(p oo d oo e)⋅((p oo d oo e)⋅x) ⊑ (p oo d oo e)⋅x" by (rule p_d_e_below) have "p⋅(d⋅(d⋅(d⋅(e⋅x)))) ⊑ p⋅(d⋅(e⋅(p⋅(d⋅(e⋅x)))))" by (intro monofun_cfun_arg d) hence "p⋅(d⋅(e⋅x)) ⊑ p⋅(d⋅(e⋅(p⋅(d⋅(e⋅x)))))" by (simp only: d.idem) thus "(p oo d oo e)⋅x ⊑ (p oo d oo e)⋅((p oo d oo e)⋅x)" by simp qed qed qed lemma finite_deflation_p_d_e: assumes "finite_deflation d" assumes d: "⋀x. d⋅x ⊑ e⋅(p⋅x)" shows "finite_deflation (p oo d oo e)" proof - interpret d: finite_deflation d by fact show ?thesis proof (rule finite_deflation_intro) have "deflation d" .. thus "deflation (p oo d oo e)" using d by (rule deflation_p_d_e) next have "finite ((λx. d⋅x) ` range (λx. e⋅x))" by (rule d.finite_image) hence "finite ((λx. p⋅x) ` (λx. d⋅x) ` range (λx. e⋅x))" by (rule finite_imageI) hence "finite (range (λx. (p oo d oo e)⋅x))" by (simp add: image_image) thus "finite {x. (p oo d oo e)⋅x = x}" by (rule finite_range_imp_finite_fixes) qed qed end subsection ‹Uniqueness of ep-pairs› lemma ep_pair_unique_e_lemma: assumes 1: "ep_pair e1 p" and 2: "ep_pair e2 p" shows "e1 ⊑ e2" proof (rule cfun_belowI) fix x have "e1⋅(p⋅(e2⋅x)) ⊑ e2⋅x" by (rule ep_pair.e_p_below [OF 1]) thus "e1⋅x ⊑ e2⋅x" by (simp only: ep_pair.e_inverse [OF 2]) qed lemma ep_pair_unique_e: "⟦ep_pair e1 p; ep_pair e2 p⟧ ⟹ e1 = e2" by (fast intro: below_antisym elim: ep_pair_unique_e_lemma) lemma ep_pair_unique_p_lemma: assumes 1: "ep_pair e p1" and 2: "ep_pair e p2" shows "p1 ⊑ p2" proof (rule cfun_belowI) fix x have "e⋅(p1⋅x) ⊑ x" by (rule ep_pair.e_p_below [OF 1]) hence "p2⋅(e⋅(p1⋅x)) ⊑ p2⋅x" by (rule monofun_cfun_arg) thus "p1⋅x ⊑ p2⋅x" by (simp only: ep_pair.e_inverse [OF 2]) qed lemma ep_pair_unique_p: "⟦ep_pair e p1; ep_pair e p2⟧ ⟹ p1 = p2" by (fast intro: below_antisym elim: ep_pair_unique_p_lemma) subsection ‹Composing ep-pairs› lemma ep_pair_ID_ID: "ep_pair ID ID" by standard simp_all lemma ep_pair_comp: assumes "ep_pair e1 p1" and "ep_pair e2 p2" shows "ep_pair (e2 oo e1) (p1 oo p2)" proof interpret ep1: ep_pair e1 p1 by fact interpret ep2: ep_pair e2 p2 by fact fix x y show "(p1 oo p2)⋅((e2 oo e1)⋅x) = x" by simp have "e1⋅(p1⋅(p2⋅y)) ⊑ p2⋅y" by (rule ep1.e_p_below) hence "e2⋅(e1⋅(p1⋅(p2⋅y))) ⊑ e2⋅(p2⋅y)" by (rule monofun_cfun_arg) also have "e2⋅(p2⋅y) ⊑ y" by (rule ep2.e_p_below) finally show "(e2 oo e1)⋅((p1 oo p2)⋅y) ⊑ y" by simp qed locale pcpo_ep_pair = ep_pair e p for e :: "'a::pcpo → 'b::pcpo" and p :: "'b::pcpo → 'a::pcpo" begin lemma e_strict [simp]: "e⋅⊥ = ⊥" proof - have "⊥ ⊑ p⋅⊥" by (rule minimal) hence "e⋅⊥ ⊑ e⋅(p⋅⊥)" by (rule monofun_cfun_arg) also have "e⋅(p⋅⊥) ⊑ ⊥" by (rule e_p_below) finally show "e⋅⊥ = ⊥" by simp qed lemma e_bottom_iff [simp]: "e⋅x = ⊥ ⟷ x = ⊥" by (rule e_eq_iff [where y="⊥", unfolded e_strict]) lemma e_defined: "x ≠ ⊥ ⟹ e⋅x ≠ ⊥" by simp lemma p_strict [simp]: "p⋅⊥ = ⊥" by (rule e_inverse [where x="⊥", unfolded e_strict]) lemmas stricts = e_strict p_strict end end