theory "HOLCF-Meet" imports "~~/src/HOL/HOLCF/HOLCF" begin text {* This theory defines the $\sqcap$ operator on HOLCF domains, and introduces a type class for domains where all finite meets exist. *} subsubsection {* Towards meets: Lower bounds *} context po begin definition is_lb :: "'a set ⇒ 'a ⇒ bool" (infix ">|" 55) where "S >| x ⟷ (∀y∈S. x ⊑ y)" lemma is_lbI: "(!!x. x ∈ S ==> l ⊑ x) ==> S >| l" by (simp add: is_lb_def) lemma is_lbD: "[|S >| l; x ∈ S|] ==> l ⊑ x" by (simp add: is_lb_def) lemma is_lb_empty [simp]: "{} >| l" unfolding is_lb_def by fast lemma is_lb_insert [simp]: "(insert x A) >| y = (y ⊑ x ∧ A >| y)" unfolding is_lb_def by fast lemma is_lb_downward: "[|S >| l; y ⊑ l|] ==> S >| y" unfolding is_lb_def by (fast intro: below_trans) subsubsection {* Greatest lower bounds *} definition is_glb :: "'a set ⇒ 'a ⇒ bool" (infix ">>|" 55) where "S >>| x ⟷ S >| x ∧ (∀u. S >| u --> u ⊑ x)" definition glb :: "'a set ⇒ 'a" ("⨅_" [60]60) where "glb S = (THE x. S >>| x)" text {* Access to the definition as inference rule *} lemma is_glbD1: "S >>| x ==> S >| x" unfolding is_glb_def by fast lemma is_glbD2: "[|S >>| x; S >| u|] ==> u ⊑ x" unfolding is_glb_def by fast lemma (in po) is_glbI: "[|S >| x; !!u. S >| u ==> u ⊑ x|] ==> S >>| x" unfolding is_glb_def by fast lemma is_glb_above_iff: "S >>| x ==> u ⊑ x ⟷ S >| u" unfolding is_glb_def is_lb_def by (metis below_trans) text {* glbs are unique *} lemma is_glb_unique: "[|S >>| x; S >>| y|] ==> x = y" unfolding is_glb_def is_lb_def by (blast intro: below_antisym) text {* technical lemmas about @{term glb} and @{term is_glb} *} lemma is_glb_glb: "M >>| x ==> M >>| glb M" unfolding glb_def by (rule theI [OF _ is_glb_unique]) lemma glb_eqI: "M >>| l ==> glb M = l" by (rule is_glb_unique [OF is_glb_glb]) lemma is_glb_singleton: "{x} >>| x" by (simp add: is_glb_def) lemma glb_singleton [simp]: "glb {x} = x" by (rule is_glb_singleton [THEN glb_eqI]) lemma is_glb_bin: "x ⊑ y ==> {x, y} >>| x" by (simp add: is_glb_def) lemma glb_bin: "x ⊑ y ==> glb {x, y} = x" by (rule is_glb_bin [THEN glb_eqI]) lemma is_glb_maximal: "[|S >| x; x ∈ S|] ==> S >>| x" by (erule is_glbI, erule (1) is_lbD) lemma glb_maximal: "[|S >| x; x ∈ S|] ==> glb S = x" by (rule is_glb_maximal [THEN glb_eqI]) lemma glb_above: "S >>| z ⟹ x ⊑ glb S ⟷ S >| x" by (metis glb_eqI is_glb_above_iff) end lemma (in cpo) Meet_insert: "S >>| l ⟹ {x, l} >>| l2 ⟹ insert x S >>| l2" apply (rule is_glbI) apply (metis is_glb_above_iff is_glb_def is_lb_insert) by (metis is_glb_above_iff is_glb_def is_glb_singleton is_lb_insert) text {* Binary, hence finite meets. *} class Finite_Meet_cpo = cpo + assumes binary_meet_exists: "∃ l. l ⊑ x ∧ l ⊑ y ∧ (∀ z. z ⊑ x ⟶ z ⊑ y ⟶ z ⊑ l)" begin lemma binary_meet_exists': "∃l. {x, y} >>| l" using binary_meet_exists[of x y] unfolding is_glb_def is_lb_def by auto lemma finite_meet_exists: assumes "S ≠ {}" and "finite S" shows "∃x. S >>| x" using `S ≠ {}` apply (induct rule: finite_induct[OF `finite S`]) apply (erule notE, rule refl)[1] apply (case_tac "F = {}") apply (metis is_glb_singleton) apply (metis Meet_insert binary_meet_exists') done end definition meet :: "'a::cpo ⇒ 'a ⇒ 'a" (infix "⊓" 80) where "x ⊓ y = (if ∃ z. {x, y} >>| z then glb {x, y} else x)" lemma meet_def': "(x::'a::Finite_Meet_cpo) ⊓ y = glb {x, y}" unfolding meet_def by (metis binary_meet_exists') lemma meet_comm: "(x::'a::Finite_Meet_cpo) ⊓ y = y ⊓ x" unfolding meet_def' by (metis insert_commute) lemma meet_bot1[simp]: fixes y :: "'a :: {Finite_Meet_cpo,pcpo}" shows "(⊥ ⊓ y) = ⊥" unfolding meet_def' by (metis minimal po_class.glb_bin) lemma meet_bot2[simp]: fixes x :: "'a :: {Finite_Meet_cpo,pcpo}" shows "(x ⊓ ⊥) = ⊥" by (metis meet_bot1 meet_comm) lemma meet_below1[intro]: fixes x y :: "'a :: Finite_Meet_cpo" assumes "x ⊑ z" shows "(x ⊓ y) ⊑ z" unfolding meet_def' by (metis assms binary_meet_exists' below_trans glb_eqI is_glbD1 is_lb_insert) lemma meet_below2[intro]: fixes x y :: "'a :: Finite_Meet_cpo" assumes "y ⊑ z" shows "(x ⊓ y) ⊑ z" unfolding meet_def' by (metis assms binary_meet_exists' below_trans glb_eqI is_glbD1 is_lb_insert) lemma meet_above_iff: fixes x y z :: "'a :: Finite_Meet_cpo" shows "z ⊑ x ⊓ y ⟷ z ⊑ x ∧ z ⊑ y" proof- obtain g where "{x,y} >>| g" by (metis binary_meet_exists') thus ?thesis unfolding meet_def' by (simp add: glb_above) qed lemma below_meet[simp]: fixes x y :: "'a :: Finite_Meet_cpo" assumes "x ⊑ z" shows "(x ⊓ z) = x" by (metis assms glb_bin meet_def') lemma below_meet2[simp]: fixes x y :: "'a :: Finite_Meet_cpo" assumes "z ⊑ x" shows "(x ⊓ z) = z" by (metis assms below_meet meet_comm) lemma meet_aboveI: fixes x y z :: "'a :: Finite_Meet_cpo" shows "z ⊑ x ⟹ z ⊑ y ⟹ z ⊑ x ⊓ y" by (simp add: meet_above_iff) lemma is_meetI: fixes x y z :: "'a :: Finite_Meet_cpo" assumes "z ⊑ x" assumes "z ⊑ y" assumes "⋀ a. ⟦ a ⊑ x ; a ⊑ y ⟧ ⟹ a ⊑ z" shows "x ⊓ y = z" by (metis assms below_antisym meet_above_iff below_refl) lemma meet_assoc[simp]: "((x::'a::Finite_Meet_cpo) ⊓ y) ⊓ z = x ⊓ (y ⊓ z)" apply (rule is_meetI) apply (metis below_refl meet_above_iff) apply (metis below_refl meet_below2) apply (metis meet_above_iff) done lemma meet_self[simp]: "r ⊓ r = (r::'a::Finite_Meet_cpo)" by (metis below_refl is_meetI) lemma [simp]: "(r::'a::Finite_Meet_cpo) ⊓ (r ⊓ x) = r ⊓ x" by (metis below_refl is_meetI meet_below1) lemma meet_monofun1: fixes y :: "'a :: Finite_Meet_cpo" shows "monofun (λx. (x ⊓ y))" by (rule monofunI)(auto simp add: meet_above_iff) lemma chain_meet1: fixes y :: "'a :: Finite_Meet_cpo" assumes "chain Y" shows "chain (λ i. Y i ⊓ y)" by (rule chainI) (auto simp add: meet_above_iff intro: chainI chainE[OF assms]) class cont_binary_meet = Finite_Meet_cpo + assumes meet_cont': "chain Y ⟹ (⨆ i. Y i) ⊓ y = (⨆ i. Y i ⊓ y)" lemma meet_cont1: fixes y :: "'a :: cont_binary_meet" shows "cont (λx. (x ⊓ y))" by (rule contI2[OF meet_monofun1]) (simp add: meet_cont') lemma meet_cont2: fixes x :: "'a :: cont_binary_meet" shows "cont (λy. (x ⊓ y))" by (subst meet_comm, rule meet_cont1) lemma meet_cont[cont2cont,simp]:"cont f ⟹ cont g ⟹ cont (λx. (f x ⊓ (g x::'a::cont_binary_meet)))" apply (rule cont2cont_case_prod[where g = "λ x. (f x, g x)" and f = "λ p x y . x ⊓ y", simplified]) apply (rule meet_cont1) apply (rule meet_cont2) apply (metis cont2cont_Pair) done end