src/HOL/Algebra/Lattice.thy
changeset 23463 9953ff53cc64
parent 23350 50c5b0912a0c
child 24087 eb025d149a34
equal deleted inserted replaced
23462:11728d83794c 23463:9953ff53cc64
   255 	assume z: "z \<in> {a, x}"
   255 	assume z: "z \<in> {a, x}"
   256 	then show "z \<sqsubseteq> y"
   256 	then show "z \<sqsubseteq> y"
   257 	proof
   257 	proof
   258           have y': "y \<in> Upper L A"
   258           have y': "y \<in> Upper L A"
   259             apply (rule subsetD [where A = "Upper L (insert x A)"])
   259             apply (rule subsetD [where A = "Upper L (insert x A)"])
   260             apply (rule Upper_antimono) apply clarify apply assumption
   260              apply (rule Upper_antimono)
       
   261 	     apply blast
       
   262 	    apply (rule y)
   261             done
   263             done
   262           assume "z = a"
   264           assume "z = a"
   263           with y' least_a show ?thesis by (fast dest: least_le)
   265           with y' least_a show ?thesis by (fast dest: least_le)
   264 	next
   266 	next
   265 	  assume "z \<in> {x}"  (* FIXME "z = x"; declare specific elim rule for "insert x {}" (!?) *)
   267 	  assume "z \<in> {x}"  (* FIXME "z = x"; declare specific elim rule for "insert x {}" (!?) *)
   297           assume z: "z \<in> {a, x}"
   299           assume z: "z \<in> {a, x}"
   298           then show "z \<sqsubseteq> y"
   300           then show "z \<sqsubseteq> y"
   299           proof
   301           proof
   300             have y': "y \<in> Upper L A"
   302             have y': "y \<in> Upper L A"
   301 	      apply (rule subsetD [where A = "Upper L (insert x A)"])
   303 	      apply (rule subsetD [where A = "Upper L (insert x A)"])
   302 	      apply (rule Upper_antimono) apply clarify apply assumption
   304 	      apply (rule Upper_antimono)
       
   305 	       apply blast
       
   306 	      apply (rule y)
   303 	      done
   307 	      done
   304             assume "z = a"
   308             assume "z = a"
   305             with y' least_a show ?thesis by (fast dest: least_le)
   309             with y' least_a show ?thesis by (fast dest: least_le)
   306 	  next
   310 	  next
   307             assume "z \<in> {x}"
   311             assume "z \<in> {x}"
   481 	assume z: "z \<in> {a, x}"
   485 	assume z: "z \<in> {a, x}"
   482 	then show "y \<sqsubseteq> z"
   486 	then show "y \<sqsubseteq> z"
   483 	proof
   487 	proof
   484           have y': "y \<in> Lower L A"
   488           have y': "y \<in> Lower L A"
   485             apply (rule subsetD [where A = "Lower L (insert x A)"])
   489             apply (rule subsetD [where A = "Lower L (insert x A)"])
   486             apply (rule Lower_antimono) apply clarify apply assumption
   490             apply (rule Lower_antimono)
       
   491 	     apply blast
       
   492 	    apply (rule y)
   487             done
   493             done
   488           assume "z = a"
   494           assume "z = a"
   489           with y' greatest_a show ?thesis by (fast dest: greatest_le)
   495           with y' greatest_a show ?thesis by (fast dest: greatest_le)
   490 	next
   496 	next
   491           assume "z \<in> {x}"
   497           assume "z \<in> {x}"
   523           assume z: "z \<in> {a, x}"
   529           assume z: "z \<in> {a, x}"
   524           then show "y \<sqsubseteq> z"
   530           then show "y \<sqsubseteq> z"
   525           proof
   531           proof
   526             have y': "y \<in> Lower L A"
   532             have y': "y \<in> Lower L A"
   527 	      apply (rule subsetD [where A = "Lower L (insert x A)"])
   533 	      apply (rule subsetD [where A = "Lower L (insert x A)"])
   528 	      apply (rule Lower_antimono) apply clarify apply assumption
   534 	      apply (rule Lower_antimono)
       
   535 	       apply blast
       
   536 	      apply (rule y)
   529 	      done
   537 	      done
   530             assume "z = a"
   538             assume "z = a"
   531             with y' greatest_a show ?thesis by (fast dest: greatest_le)
   539             with y' greatest_a show ?thesis by (fast dest: greatest_le)
   532 	  next
   540 	  next
   533             assume "z \<in> {x}"
   541             assume "z \<in> {x}"
   697           by (rule_tac greatest_LowerI) auto
   705           by (rule_tac greatest_LowerI) auto
   698       }
   706       }
   699       ultimately show ?thesis by blast
   707       ultimately show ?thesis by blast
   700     qed
   708     qed
   701   qed
   709   qed
   702 qed (assumption | rule total_order_axioms.intro)+
   710 qed (rule total total_order_axioms.intro)+
   703 
   711 
   704 
   712 
   705 subsection {* Complete lattices *}
   713 subsection {* Complete lattices *}
   706 
   714 
   707 locale complete_lattice = lattice +
   715 locale complete_lattice = lattice +
   719     "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)"
   727     "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)"
   720   shows "complete_lattice L"
   728   shows "complete_lattice L"
   721 proof intro_locales
   729 proof intro_locales
   722   show "lattice_axioms L"
   730   show "lattice_axioms L"
   723     by (rule lattice_axioms.intro) (blast intro: sup_exists inf_exists)+
   731     by (rule lattice_axioms.intro) (blast intro: sup_exists inf_exists)+
   724 qed (assumption | rule complete_lattice_axioms.intro)+
   732 qed (rule complete_lattice_axioms.intro sup_exists inf_exists | assumption)+
   725 
   733 
   726 constdefs (structure L)
   734 constdefs (structure L)
   727   top :: "_ => 'a" ("\<top>\<index>")
   735   top :: "_ => 'a" ("\<top>\<index>")
   728   "\<top> == sup L (carrier L)"
   736   "\<top> == sup L (carrier L)"
   729 
   737