src/HOL/Complete_Lattice.thy
changeset 44845 5e51075cbd97
parent 44322 43b465f4c480
equal deleted inserted replaced
44844:f74a4175a3a8 44845:5e51075cbd97
    31   assumes Sup_upper: "x \<in> A \<Longrightarrow> x \<sqsubseteq> \<Squnion>A"
    31   assumes Sup_upper: "x \<in> A \<Longrightarrow> x \<sqsubseteq> \<Squnion>A"
    32      and Sup_least: "(\<And>x. x \<in> A \<Longrightarrow> x \<sqsubseteq> z) \<Longrightarrow> \<Squnion>A \<sqsubseteq> z"
    32      and Sup_least: "(\<And>x. x \<in> A \<Longrightarrow> x \<sqsubseteq> z) \<Longrightarrow> \<Squnion>A \<sqsubseteq> z"
    33 begin
    33 begin
    34 
    34 
    35 lemma dual_complete_lattice:
    35 lemma dual_complete_lattice:
    36   "class.complete_lattice Sup Inf (op \<ge>) (op >) sup inf \<top> \<bottom>"
    36   "class.complete_lattice Sup Inf sup (op \<ge>) (op >) inf \<top> \<bottom>"
    37   by (auto intro!: class.complete_lattice.intro dual_bounded_lattice)
    37   by (auto intro!: class.complete_lattice.intro dual_bounded_lattice)
    38     (unfold_locales, (fact bot_least top_greatest
    38     (unfold_locales, (fact bot_least top_greatest
    39         Sup_upper Sup_least Inf_lower Inf_greatest)+)
    39         Sup_upper Sup_least Inf_lower Inf_greatest)+)
    40 
    40 
    41 definition INFI :: "'b set \<Rightarrow> ('b \<Rightarrow> 'a) \<Rightarrow> 'a" where
    41 definition INFI :: "'b set \<Rightarrow> ('b \<Rightarrow> 'a) \<Rightarrow> 'a" where
    83 begin
    83 begin
    84 
    84 
    85 lemma INF_foundation_dual [no_atp]:
    85 lemma INF_foundation_dual [no_atp]:
    86   "complete_lattice.SUPR Inf = INFI"
    86   "complete_lattice.SUPR Inf = INFI"
    87 proof (rule ext)+
    87 proof (rule ext)+
    88   interpret dual: complete_lattice Sup Inf "op \<ge>" "op >" sup inf \<top> \<bottom>
    88   interpret dual: complete_lattice Sup Inf sup "op \<ge>" "op >" inf \<top> \<bottom>
    89     by (fact dual_complete_lattice)
    89     by (fact dual_complete_lattice)
    90   fix f :: "'b \<Rightarrow> 'a" and A
    90   fix f :: "'b \<Rightarrow> 'a" and A
    91   show "complete_lattice.SUPR Inf A f = (\<Sqinter>a\<in>A. f a)"
    91   show "complete_lattice.SUPR Inf A f = (\<Sqinter>a\<in>A. f a)"
    92     by (simp only: dual.SUP_def INF_def)
    92     by (simp only: dual.SUP_def INF_def)
    93 qed
    93 qed
    94 
    94 
    95 lemma SUP_foundation_dual [no_atp]:
    95 lemma SUP_foundation_dual [no_atp]:
    96   "complete_lattice.INFI Sup = SUPR"
    96   "complete_lattice.INFI Sup = SUPR"
    97 proof (rule ext)+
    97 proof (rule ext)+
    98   interpret dual: complete_lattice Sup Inf "op \<ge>" "op >" sup inf \<top> \<bottom>
    98   interpret dual: complete_lattice Sup Inf sup "op \<ge>" "op >" inf \<top> \<bottom>
    99     by (fact dual_complete_lattice)
    99     by (fact dual_complete_lattice)
   100   fix f :: "'b \<Rightarrow> 'a" and A
   100   fix f :: "'b \<Rightarrow> 'a" and A
   101   show "complete_lattice.INFI Sup A f = (\<Squnion>a\<in>A. f a)"
   101   show "complete_lattice.INFI Sup A f = (\<Squnion>a\<in>A. f a)"
   102     by (simp only: dual.INF_def SUP_def)
   102     by (simp only: dual.INF_def SUP_def)
   103 qed
   103 qed
   311 
   311 
   312 lemma Sup_bot_conv (*[simp]*) [no_atp]:
   312 lemma Sup_bot_conv (*[simp]*) [no_atp]:
   313   "\<Squnion>A = \<bottom> \<longleftrightarrow> (\<forall>x\<in>A. x = \<bottom>)" (is ?P)
   313   "\<Squnion>A = \<bottom> \<longleftrightarrow> (\<forall>x\<in>A. x = \<bottom>)" (is ?P)
   314   "\<bottom> = \<Squnion>A \<longleftrightarrow> (\<forall>x\<in>A. x = \<bottom>)" (is ?Q)
   314   "\<bottom> = \<Squnion>A \<longleftrightarrow> (\<forall>x\<in>A. x = \<bottom>)" (is ?Q)
   315 proof -
   315 proof -
   316   interpret dual: complete_lattice Sup Inf "op \<ge>" "op >" sup inf \<top> \<bottom>
   316   interpret dual: complete_lattice Sup Inf sup "op \<ge>" "op >" inf \<top> \<bottom>
   317     by (fact dual_complete_lattice)
   317     by (fact dual_complete_lattice)
   318   from dual.Inf_top_conv show ?P and ?Q by simp_all
   318   from dual.Inf_top_conv show ?P and ?Q by simp_all
   319 qed
   319 qed
   320 
   320 
   321 lemma SUP_bot_conv (*[simp]*):
   321 lemma SUP_bot_conv (*[simp]*):
   405 lemma inf_SUP:
   405 lemma inf_SUP:
   406   "a \<sqinter> (\<Squnion>b\<in>B. f b) = (\<Squnion>b\<in>B. a \<sqinter> f b)"
   406   "a \<sqinter> (\<Squnion>b\<in>B. f b) = (\<Squnion>b\<in>B. a \<sqinter> f b)"
   407   by (simp add: SUP_def inf_Sup image_image)
   407   by (simp add: SUP_def inf_Sup image_image)
   408 
   408 
   409 lemma dual_complete_distrib_lattice:
   409 lemma dual_complete_distrib_lattice:
   410   "class.complete_distrib_lattice Sup Inf (op \<ge>) (op >) sup inf \<top> \<bottom>"
   410   "class.complete_distrib_lattice Sup Inf sup (op \<ge>) (op >) inf \<top> \<bottom>"
   411   apply (rule class.complete_distrib_lattice.intro)
   411   apply (rule class.complete_distrib_lattice.intro)
   412   apply (fact dual_complete_lattice)
   412   apply (fact dual_complete_lattice)
   413   apply (rule class.complete_distrib_lattice_axioms.intro)
   413   apply (rule class.complete_distrib_lattice_axioms.intro)
   414   apply (simp_all only: INF_foundation_dual SUP_foundation_dual inf_Sup sup_Inf)
   414   apply (simp_all only: INF_foundation_dual SUP_foundation_dual inf_Sup sup_Inf)
   415   done
   415   done
   456 
   456 
   457 class complete_boolean_algebra = boolean_algebra + complete_distrib_lattice
   457 class complete_boolean_algebra = boolean_algebra + complete_distrib_lattice
   458 begin
   458 begin
   459 
   459 
   460 lemma dual_complete_boolean_algebra:
   460 lemma dual_complete_boolean_algebra:
   461   "class.complete_boolean_algebra Sup Inf (op \<ge>) (op >) sup inf \<top> \<bottom> (\<lambda>x y. x \<squnion> - y) uminus"
   461   "class.complete_boolean_algebra Sup Inf sup (op \<ge>) (op >) inf \<top> \<bottom> (\<lambda>x y. x \<squnion> - y) uminus"
   462   by (rule class.complete_boolean_algebra.intro, rule dual_complete_distrib_lattice, rule dual_boolean_algebra)
   462   by (rule class.complete_boolean_algebra.intro, rule dual_complete_distrib_lattice, rule dual_boolean_algebra)
   463 
   463 
   464 lemma uminus_Inf:
   464 lemma uminus_Inf:
   465   "- (\<Sqinter>A) = \<Squnion>(uminus ` A)"
   465   "- (\<Sqinter>A) = \<Squnion>(uminus ` A)"
   466 proof (rule antisym)
   466 proof (rule antisym)
   487 
   487 
   488 class complete_linorder = linorder + complete_lattice
   488 class complete_linorder = linorder + complete_lattice
   489 begin
   489 begin
   490 
   490 
   491 lemma dual_complete_linorder:
   491 lemma dual_complete_linorder:
   492   "class.complete_linorder Sup Inf (op \<ge>) (op >) sup inf \<top> \<bottom>"
   492   "class.complete_linorder Sup Inf sup (op \<ge>) (op >) inf \<top> \<bottom>"
   493   by (rule class.complete_linorder.intro, rule dual_complete_lattice, rule dual_linorder)
   493   by (rule class.complete_linorder.intro, rule dual_complete_lattice, rule dual_linorder)
   494 
   494 
   495 lemma Inf_less_iff (*[simp]*):
   495 lemma Inf_less_iff (*[simp]*):
   496   "\<Sqinter>S \<sqsubset> a \<longleftrightarrow> (\<exists>x\<in>S. x \<sqsubset> a)"
   496   "\<Sqinter>S \<sqsubset> a \<longleftrightarrow> (\<exists>x\<in>S. x \<sqsubset> a)"
   497   unfolding not_le [symmetric] le_Inf_iff by auto
   497   unfolding not_le [symmetric] le_Inf_iff by auto
   535   unfolding SUP_def Sup_eq_top_iff by auto
   535   unfolding SUP_def Sup_eq_top_iff by auto
   536 
   536 
   537 lemma Inf_eq_bot_iff (*[simp]*):
   537 lemma Inf_eq_bot_iff (*[simp]*):
   538   "\<Sqinter>A = \<bottom> \<longleftrightarrow> (\<forall>x>\<bottom>. \<exists>i\<in>A. i < x)"
   538   "\<Sqinter>A = \<bottom> \<longleftrightarrow> (\<forall>x>\<bottom>. \<exists>i\<in>A. i < x)"
   539 proof -
   539 proof -
   540   interpret dual: complete_linorder Sup Inf "op \<ge>" "op >" sup inf \<top> \<bottom>
   540   interpret dual: complete_linorder Sup Inf sup "op \<ge>" "op >" inf \<top> \<bottom>
   541     by (fact dual_complete_linorder)
   541     by (fact dual_complete_linorder)
   542   from dual.Sup_eq_top_iff show ?thesis .
   542   from dual.Sup_eq_top_iff show ?thesis .
   543 qed
   543 qed
   544 
   544 
   545 lemma INF_eq_bot_iff (*[simp]*):
   545 lemma INF_eq_bot_iff (*[simp]*):