src/HOL/Algebra/Lattice.thy
changeset 32960 69916a850301
parent 30363 9b8d9b6ef803
child 33657 a4179bf442d1
equal deleted inserted replaced
32959:23a8c5ac35f8 32960:69916a850301
   531     next
   531     next
   532       fix y
   532       fix y
   533       assume y: "y \<in> Upper L (insert x A)"
   533       assume y: "y \<in> Upper L (insert x A)"
   534       show "s \<sqsubseteq> y"
   534       show "s \<sqsubseteq> y"
   535       proof (rule least_le [OF least_s], rule Upper_memI)
   535       proof (rule least_le [OF least_s], rule Upper_memI)
   536 	fix z
   536         fix z
   537 	assume z: "z \<in> {a, x}"
   537         assume z: "z \<in> {a, x}"
   538 	then show "z \<sqsubseteq> y"
   538         then show "z \<sqsubseteq> y"
   539 	proof
   539         proof
   540           have y': "y \<in> Upper L A"
   540           have y': "y \<in> Upper L A"
   541             apply (rule subsetD [where A = "Upper L (insert x A)"])
   541             apply (rule subsetD [where A = "Upper L (insert x A)"])
   542              apply (rule Upper_antimono)
   542              apply (rule Upper_antimono)
   543 	     apply blast
   543              apply blast
   544 	    apply (rule y)
   544             apply (rule y)
   545             done
   545             done
   546           assume "z = a"
   546           assume "z = a"
   547           with y' least_a show ?thesis by (fast dest: least_le)
   547           with y' least_a show ?thesis by (fast dest: least_le)
   548 	next
   548         next
   549 	  assume "z \<in> {x}"  (* FIXME "z = x"; declare specific elim rule for "insert x {}" (!?) *)
   549           assume "z \<in> {x}"  (* FIXME "z = x"; declare specific elim rule for "insert x {}" (!?) *)
   550           with y L show ?thesis by blast
   550           with y L show ?thesis by blast
   551 	qed
   551         qed
   552       qed (rule Upper_closed [THEN subsetD, OF y])
   552       qed (rule Upper_closed [THEN subsetD, OF y])
   553     next
   553     next
   554       from L show "insert x A \<subseteq> carrier L" by simp
   554       from L show "insert x A \<subseteq> carrier L" by simp
   555       from least_s show "s \<in> carrier L" by simp
   555       from least_s show "s \<in> carrier L" by simp
   556     qed
   556     qed
   567   show ?case
   567   show ?case
   568   proof (cases "A = {}")
   568   proof (cases "A = {}")
   569     case True
   569     case True
   570     with insert show ?thesis
   570     with insert show ?thesis
   571       by simp (simp add: least_cong [OF weak_sup_of_singleton]
   571       by simp (simp add: least_cong [OF weak_sup_of_singleton]
   572 	sup_of_singleton_closed sup_of_singletonI)
   572         sup_of_singleton_closed sup_of_singletonI)
   573 	(* The above step is hairy; least_cong can make simp loop.
   573         (* The above step is hairy; least_cong can make simp loop.
   574 	Would want special version of simp to apply least_cong. *)
   574         Would want special version of simp to apply least_cong. *)
   575   next
   575   next
   576     case False
   576     case False
   577     with insert have "least L (\<Squnion>A) (Upper L A)" by simp
   577     with insert have "least L (\<Squnion>A) (Upper L A)" by simp
   578     with _ show ?thesis
   578     with _ show ?thesis
   579       by (rule sup_insertI) (simp_all add: insert [simplified])
   579       by (rule sup_insertI) (simp_all add: insert [simplified])
   772     next
   772     next
   773       fix y
   773       fix y
   774       assume y: "y \<in> Lower L (insert x A)"
   774       assume y: "y \<in> Lower L (insert x A)"
   775       show "y \<sqsubseteq> i"
   775       show "y \<sqsubseteq> i"
   776       proof (rule greatest_le [OF greatest_i], rule Lower_memI)
   776       proof (rule greatest_le [OF greatest_i], rule Lower_memI)
   777 	fix z
   777         fix z
   778 	assume z: "z \<in> {a, x}"
   778         assume z: "z \<in> {a, x}"
   779 	then show "y \<sqsubseteq> z"
   779         then show "y \<sqsubseteq> z"
   780 	proof
   780         proof
   781           have y': "y \<in> Lower L A"
   781           have y': "y \<in> Lower L A"
   782             apply (rule subsetD [where A = "Lower L (insert x A)"])
   782             apply (rule subsetD [where A = "Lower L (insert x A)"])
   783             apply (rule Lower_antimono)
   783             apply (rule Lower_antimono)
   784 	     apply blast
   784              apply blast
   785 	    apply (rule y)
   785             apply (rule y)
   786             done
   786             done
   787           assume "z = a"
   787           assume "z = a"
   788           with y' greatest_a show ?thesis by (fast dest: greatest_le)
   788           with y' greatest_a show ?thesis by (fast dest: greatest_le)
   789 	next
   789         next
   790           assume "z \<in> {x}"
   790           assume "z \<in> {x}"
   791           with y L show ?thesis by blast
   791           with y L show ?thesis by blast
   792 	qed
   792         qed
   793       qed (rule Lower_closed [THEN subsetD, OF y])
   793       qed (rule Lower_closed [THEN subsetD, OF y])
   794     next
   794     next
   795       from L show "insert x A \<subseteq> carrier L" by simp
   795       from L show "insert x A \<subseteq> carrier L" by simp
   796       from greatest_i show "i \<in> carrier L" by simp
   796       from greatest_i show "i \<in> carrier L" by simp
   797     qed
   797     qed
   807   show ?case
   807   show ?case
   808   proof (cases "A = {}")
   808   proof (cases "A = {}")
   809     case True
   809     case True
   810     with insert show ?thesis
   810     with insert show ?thesis
   811       by simp (simp add: greatest_cong [OF weak_inf_of_singleton]
   811       by simp (simp add: greatest_cong [OF weak_inf_of_singleton]
   812 	inf_of_singleton_closed inf_of_singletonI)
   812         inf_of_singleton_closed inf_of_singletonI)
   813   next
   813   next
   814     case False
   814     case False
   815     from insert show ?thesis
   815     from insert show ?thesis
   816     proof (rule_tac inf_insertI)
   816     proof (rule_tac inf_insertI)
   817       from False insert show "greatest L (\<Sqinter>A) (Lower L A)" by simp
   817       from False insert show "greatest L (\<Sqinter>A) (Lower L A)" by simp
  1289   assume B: "B \<subseteq> carrier ?L"
  1289   assume B: "B \<subseteq> carrier ?L"
  1290   show "EX i. greatest ?L i (Lower ?L B)"
  1290   show "EX i. greatest ?L i (Lower ?L B)"
  1291   proof
  1291   proof
  1292     from B show "greatest ?L (\<Inter> B \<inter> A) (Lower ?L B)"
  1292     from B show "greatest ?L (\<Inter> B \<inter> A) (Lower ?L B)"
  1293       txt {* @{term "\<Inter> B"} is not the infimum of @{term B}:
  1293       txt {* @{term "\<Inter> B"} is not the infimum of @{term B}:
  1294 	@{term "\<Inter> {} = UNIV"} which is in general bigger than @{term "A"}! *}
  1294         @{term "\<Inter> {} = UNIV"} which is in general bigger than @{term "A"}! *}
  1295       by (fastsimp intro!: greatest_LowerI simp: Lower_def)
  1295       by (fastsimp intro!: greatest_LowerI simp: Lower_def)
  1296   qed
  1296   qed
  1297 qed
  1297 qed
  1298 
  1298 
  1299 text {* An other example, that of the lattice of subgroups of a group,
  1299 text {* An other example, that of the lattice of subgroups of a group,