src/HOL/Library/Complete_Partial_Order2.thy
changeset 66244 4c999b5d78e2
parent 65366 10ca63a18e56
child 67399 eab6ce8368fa
equal deleted inserted replaced
66243:453f9cabddb5 66244:4c999b5d78e2
   902   admissible_leI[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
   902   admissible_leI[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
   903   ccpo.admissible_not_below[THEN admissible_subst, OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
   903   ccpo.admissible_not_below[THEN admissible_subst, OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
   904 
   904 
   905 end
   905 end
   906 
   906 
       
   907 setup \<open>Sign.map_naming (Name_Space.mandatory_path "ccpo")\<close>
   907 
   908 
   908 inductive compact :: "('a set \<Rightarrow> 'a) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> 'a \<Rightarrow> bool"
   909 inductive compact :: "('a set \<Rightarrow> 'a) \<Rightarrow> ('a \<Rightarrow> 'a \<Rightarrow> bool) \<Rightarrow> 'a \<Rightarrow> bool"
   909   for lub ord x 
   910   for lub ord x 
   910 where compact:
   911 where compact:
   911   "\<lbrakk> ccpo.admissible lub ord (\<lambda>y. \<not> ord x y);
   912   "\<lbrakk> ccpo.admissible lub ord (\<lambda>y. \<not> ord x y);
   912      ccpo.admissible lub ord (\<lambda>y. x \<noteq> y) \<rbrakk>
   913      ccpo.admissible lub ord (\<lambda>y. x \<noteq> y) \<rbrakk>
   913   \<Longrightarrow> compact lub ord x"
   914   \<Longrightarrow> compact lub ord x"
   914 
   915 
   915 hide_fact (open) compact
   916 setup \<open>Sign.map_naming Name_Space.parent_path\<close>
   916 
   917 
   917 context ccpo begin
   918 context ccpo begin
   918 
   919 
   919 lemma compactI:
   920 lemma compactI:
   920   assumes "ccpo.admissible Sup op \<le> (\<lambda>y. \<not> x \<le> y)"
   921   assumes "ccpo.admissible Sup op \<le> (\<lambda>y. \<not> x \<le> y)"
   921   shows "compact Sup op \<le> x"
   922   shows "ccpo.compact Sup op \<le> x"
   922 using assms
   923 using assms
   923 proof(rule compact.intros)
   924 proof(rule ccpo.compact.intros)
   924   have neq: "(\<lambda>y. x \<noteq> y) = (\<lambda>y. \<not> x \<le> y \<or> \<not> y \<le> x)" by(auto)
   925   have neq: "(\<lambda>y. x \<noteq> y) = (\<lambda>y. \<not> x \<le> y \<or> \<not> y \<le> x)" by(auto)
   925   show "ccpo.admissible Sup op \<le> (\<lambda>y. x \<noteq> y)"
   926   show "ccpo.admissible Sup op \<le> (\<lambda>y. x \<noteq> y)"
   926     by(subst neq)(rule admissible_disj admissible_not_below assms)+
   927     by(subst neq)(rule admissible_disj admissible_not_below assms)+
   927 qed
   928 qed
   928 
   929 
   929 lemma compact_bot:
   930 lemma compact_bot:
   930   assumes "x = Sup {}"
   931   assumes "x = Sup {}"
   931   shows "compact Sup op \<le> x"
   932   shows "ccpo.compact Sup op \<le> x"
   932 proof(rule compactI)
   933 proof(rule compactI)
   933   show "ccpo.admissible Sup op \<le> (\<lambda>y. \<not> x \<le> y)" using assms
   934   show "ccpo.admissible Sup op \<le> (\<lambda>y. \<not> x \<le> y)" using assms
   934     by(auto intro!: ccpo.admissibleI intro: ccpo_Sup_least chain_empty)
   935     by(auto intro!: ccpo.admissibleI intro: ccpo_Sup_least chain_empty)
   935 qed
   936 qed
   936 
   937 
   937 end
   938 end
   938 
   939 
   939 lemma admissible_compact_neq' [THEN admissible_subst, cont_intro, simp]:
   940 lemma admissible_compact_neq' [THEN admissible_subst, cont_intro, simp]:
   940   shows admissible_compact_neq: "compact lub ord k \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. k \<noteq> x)"
   941   shows admissible_compact_neq: "ccpo.compact lub ord k \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. k \<noteq> x)"
   941 by(simp add: compact.simps)
   942 by(simp add: ccpo.compact.simps)
   942 
   943 
   943 lemma admissible_neq_compact' [THEN admissible_subst, cont_intro, simp]:
   944 lemma admissible_neq_compact' [THEN admissible_subst, cont_intro, simp]:
   944   shows admissible_neq_compact: "compact lub ord k \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. x \<noteq> k)"
   945   shows admissible_neq_compact: "ccpo.compact lub ord k \<Longrightarrow> ccpo.admissible lub ord (\<lambda>x. x \<noteq> k)"
   945 by(subst eq_commute)(rule admissible_compact_neq)
   946 by(subst eq_commute)(rule admissible_compact_neq)
   946 
   947 
   947 context partial_function_definitions begin
   948 context partial_function_definitions begin
   948 
   949 
   949 lemmas [cont_intro, simp] = ccpo.compact_bot[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
   950 lemmas [cont_intro, simp] = ccpo.compact_bot[OF Partial_Function.ccpo[OF partial_function_definitions_axioms]]
  1726 
  1727 
  1727 lemma map_option_mono [partial_function_mono]:
  1728 lemma map_option_mono [partial_function_mono]:
  1728   "mono_option B \<Longrightarrow> mono_option (\<lambda>f. map_option g (B f))"
  1729   "mono_option B \<Longrightarrow> mono_option (\<lambda>f. map_option g (B f))"
  1729 unfolding map_conv_bind_option by(rule bind_mono) simp_all
  1730 unfolding map_conv_bind_option by(rule bind_mono) simp_all
  1730 
  1731 
  1731 lemma compact_flat_lub [cont_intro]: "compact (flat_lub x) (flat_ord x) y"
  1732 lemma compact_flat_lub [cont_intro]: "ccpo.compact (flat_lub x) (flat_ord x) y"
  1732 using flat_interpretation[THEN ccpo]
  1733 using flat_interpretation[THEN ccpo]
  1733 proof(rule ccpo.compactI[OF _ ccpo.admissibleI])
  1734 proof(rule ccpo.compactI[OF _ ccpo.admissibleI])
  1734   fix A
  1735   fix A
  1735   assume chain: "Complete_Partial_Order.chain (flat_ord x) A"
  1736   assume chain: "Complete_Partial_Order.chain (flat_ord x) A"
  1736     and A: "A \<noteq> {}"
  1737     and A: "A \<noteq> {}"