src/HOL/Lattices.thy
changeset 44921 58eef4843641
parent 44919 482f1807976e
child 46553 50a7e97fe653
equal deleted inserted replaced
44920:4657b4c11138 44921:58eef4843641
   178   by (fact inf.commute)
   178   by (fact inf.commute)
   179 
   179 
   180 lemma inf_left_commute: "x \<sqinter> (y \<sqinter> z) = y \<sqinter> (x \<sqinter> z)"
   180 lemma inf_left_commute: "x \<sqinter> (y \<sqinter> z) = y \<sqinter> (x \<sqinter> z)"
   181   by (fact inf.left_commute)
   181   by (fact inf.left_commute)
   182 
   182 
   183 lemma inf_idem [simp]: "x \<sqinter> x = x"
   183 lemma inf_idem: "x \<sqinter> x = x"
   184   by (fact inf.idem)
   184   by (fact inf.idem) (* already simp *)
   185 
   185 
   186 lemma inf_left_idem [simp]: "x \<sqinter> (x \<sqinter> y) = x \<sqinter> y"
   186 lemma inf_left_idem [simp]: "x \<sqinter> (x \<sqinter> y) = x \<sqinter> y"
   187   by (fact inf.left_idem)
   187   by (fact inf.left_idem)
   188 
   188 
   189 lemma inf_absorb1: "x \<sqsubseteq> y \<Longrightarrow> x \<sqinter> y = x"
   189 lemma inf_absorb1: "x \<sqsubseteq> y \<Longrightarrow> x \<sqinter> y = x"
   217   by (fact sup.commute)
   217   by (fact sup.commute)
   218 
   218 
   219 lemma sup_left_commute: "x \<squnion> (y \<squnion> z) = y \<squnion> (x \<squnion> z)"
   219 lemma sup_left_commute: "x \<squnion> (y \<squnion> z) = y \<squnion> (x \<squnion> z)"
   220   by (fact sup.left_commute)
   220   by (fact sup.left_commute)
   221 
   221 
   222 lemma sup_idem [simp]: "x \<squnion> x = x"
   222 lemma sup_idem: "x \<squnion> x = x"
   223   by (fact sup.idem)
   223   by (fact sup.idem) (* already simp *)
   224 
   224 
   225 lemma sup_left_idem [simp]: "x \<squnion> (x \<squnion> y) = x \<squnion> y"
   225 lemma sup_left_idem [simp]: "x \<squnion> (x \<squnion> y) = x \<squnion> y"
   226   by (fact sup.left_idem)
   226   by (fact sup.left_idem)
   227 
   227 
   228 lemma sup_absorb1: "y \<sqsubseteq> x \<Longrightarrow> x \<squnion> y = x"
   228 lemma sup_absorb1: "y \<sqsubseteq> x \<Longrightarrow> x \<squnion> y = x"
   309 context semilattice_sup
   309 context semilattice_sup
   310 begin
   310 begin
   311 
   311 
   312 lemma less_supI1:
   312 lemma less_supI1:
   313   "x \<sqsubset> a \<Longrightarrow> x \<sqsubset> a \<squnion> b"
   313   "x \<sqsubset> a \<Longrightarrow> x \<sqsubset> a \<squnion> b"
   314 proof -
   314   using dual_semilattice
   315   interpret dual: semilattice_inf sup "op \<ge>" "op >"
   315   by (rule semilattice_inf.less_infI1)
   316     by (fact dual_semilattice)
       
   317   assume "x \<sqsubset> a"
       
   318   then show "x \<sqsubset> a \<squnion> b"
       
   319     by (fact dual.less_infI1)
       
   320 qed
       
   321 
   316 
   322 lemma less_supI2:
   317 lemma less_supI2:
   323   "x \<sqsubset> b \<Longrightarrow> x \<sqsubset> a \<squnion> b"
   318   "x \<sqsubset> b \<Longrightarrow> x \<sqsubset> a \<squnion> b"
   324 proof -
   319   using dual_semilattice
   325   interpret dual: semilattice_inf sup "op \<ge>" "op >"
   320   by (rule semilattice_inf.less_infI2)
   326     by (fact dual_semilattice)
       
   327   assume "x \<sqsubset> b"
       
   328   then show "x \<sqsubset> a \<squnion> b"
       
   329     by (fact dual.less_infI2)
       
   330 qed
       
   331 
   321 
   332 end
   322 end
   333 
   323 
   334 
   324 
   335 subsection {* Distributive lattices *}
   325 subsection {* Distributive lattices *}
   339 
   329 
   340 context distrib_lattice
   330 context distrib_lattice
   341 begin
   331 begin
   342 
   332 
   343 lemma sup_inf_distrib2:
   333 lemma sup_inf_distrib2:
   344  "(y \<sqinter> z) \<squnion> x = (y \<squnion> x) \<sqinter> (z \<squnion> x)"
   334   "(y \<sqinter> z) \<squnion> x = (y \<squnion> x) \<sqinter> (z \<squnion> x)"
   345 by(simp add: inf_sup_aci sup_inf_distrib1)
   335   by (simp add: sup_commute sup_inf_distrib1)
   346 
   336 
   347 lemma inf_sup_distrib1:
   337 lemma inf_sup_distrib1:
   348  "x \<sqinter> (y \<squnion> z) = (x \<sqinter> y) \<squnion> (x \<sqinter> z)"
   338   "x \<sqinter> (y \<squnion> z) = (x \<sqinter> y) \<squnion> (x \<sqinter> z)"
   349 by(rule distrib_imp2[OF sup_inf_distrib1])
   339   by (rule distrib_imp2 [OF sup_inf_distrib1])
   350 
   340 
   351 lemma inf_sup_distrib2:
   341 lemma inf_sup_distrib2:
   352  "(y \<squnion> z) \<sqinter> x = (y \<sqinter> x) \<squnion> (z \<sqinter> x)"
   342   "(y \<squnion> z) \<sqinter> x = (y \<sqinter> x) \<squnion> (z \<sqinter> x)"
   353 by(simp add: inf_sup_aci inf_sup_distrib1)
   343   by (simp add: inf_commute inf_sup_distrib1)
   354 
   344 
   355 lemma dual_distrib_lattice:
   345 lemma dual_distrib_lattice:
   356   "class.distrib_lattice sup (op \<ge>) (op >) inf"
   346   "class.distrib_lattice sup (op \<ge>) (op >) inf"
   357   by (rule class.distrib_lattice.intro, rule dual_lattice)
   347   by (rule class.distrib_lattice.intro, rule dual_lattice)
   358     (unfold_locales, fact inf_sup_distrib1)
   348     (unfold_locales, fact inf_sup_distrib1)
   508     by (simp add: sup_compl_top)
   498     by (simp add: sup_compl_top)
   509 qed
   499 qed
   510 
   500 
   511 lemma compl_sup [simp]:
   501 lemma compl_sup [simp]:
   512   "- (x \<squnion> y) = - x \<sqinter> - y"
   502   "- (x \<squnion> y) = - x \<sqinter> - y"
   513 proof -
   503   using dual_boolean_algebra
   514   interpret boolean_algebra "\<lambda>x y. x \<squnion> - y" uminus sup greater_eq greater inf \<top> \<bottom>
   504   by (rule boolean_algebra.compl_inf)
   515     by (rule dual_boolean_algebra)
       
   516   then show ?thesis by simp
       
   517 qed
       
   518 
   505 
   519 lemma compl_mono:
   506 lemma compl_mono:
   520   "x \<sqsubseteq> y \<Longrightarrow> - y \<sqsubseteq> - x"
   507   "x \<sqsubseteq> y \<Longrightarrow> - y \<sqsubseteq> - x"
   521 proof -
   508 proof -
   522   assume "x \<sqsubseteq> y"
   509   assume "x \<sqsubseteq> y"