diff -r ddca85598c65 -r efac889fccbc src/HOL/Algebra/Lattice.thy --- a/src/HOL/Algebra/Lattice.thy Sat Oct 10 16:21:34 2015 +0200 +++ b/src/HOL/Algebra/Lattice.thy Sat Oct 10 16:26:23 2015 +0200 @@ -9,9 +9,9 @@ imports Congruence begin -section {* Orders and Lattices *} +section \Orders and Lattices\ -subsection {* Partial Orders *} +subsection \Partial Orders\ record 'a gorder = "'a eq_object" + le :: "['a, 'a] => bool" (infixl "\\" 50) @@ -32,7 +32,7 @@ where "x \\<^bsub>L\<^esub> y \ x \\<^bsub>L\<^esub> y & x .\\<^bsub>L\<^esub> y" -subsubsection {* The order relation *} +subsubsection \The order relation\ context weak_partial_order begin @@ -103,7 +103,7 @@ using assms unfolding lless_def by (blast dest: le_trans intro: sym) -subsubsection {* Upper and lower bounds of a set *} +subsubsection \Upper and lower bounds of a set\ definition Upper :: "[_, 'a set] => 'a set" @@ -276,7 +276,7 @@ qed -subsubsection {* Least and greatest, as predicate *} +subsubsection \Least and greatest, as predicate\ definition least :: "[_, 'a, 'a set] => bool" @@ -286,8 +286,8 @@ greatest :: "[_, 'a, 'a set] => bool" where "greatest L g A \ A \ carrier L & g \ A & (ALL x : A. x \\<^bsub>L\<^esub> g)" -text (in weak_partial_order) {* Could weaken these to @{term "l \ carrier L \ l - .\ A"} and @{term "g \ carrier L \ g .\ A"}. *} +text (in weak_partial_order) \Could weaken these to @{term "l \ carrier L \ l + .\ A"} and @{term "g \ carrier L \ g .\ A"}.\ lemma least_closed [intro, simp]: "least L l A ==> l \ carrier L" @@ -310,8 +310,8 @@ "[| x .= x'; x \ carrier L; x' \ carrier L; is_closed A |] ==> least L x A = least L x' A" by (unfold least_def) (auto dest: sym) -text (in weak_partial_order) {* @{const least} is not congruent in the second parameter for - @{term "A {.=} A'"} *} +text (in weak_partial_order) \@{const least} is not congruent in the second parameter for + @{term "A {.=} A'"}\ lemma (in weak_partial_order) least_Upper_cong_l: assumes "x .= x'" @@ -367,8 +367,8 @@ greatest L x A = greatest L x' A" by (unfold greatest_def) (auto dest: sym) -text (in weak_partial_order) {* @{const greatest} is not congruent in the second parameter for - @{term "A {.=} A'"} *} +text (in weak_partial_order) \@{const greatest} is not congruent in the second parameter for + @{term "A {.=} A'"}\ lemma (in weak_partial_order) greatest_Lower_cong_l: assumes "x .= x'" @@ -402,7 +402,7 @@ shows "[| greatest L i (Lower L A); x \ A; A \ carrier L |] ==> i \ x" by (unfold greatest_def) blast -text {* Supremum and infimum *} +text \Supremum and infimum\ definition sup :: "[_, 'a set] => 'a" ("\\_" [90] 90) @@ -421,7 +421,7 @@ where "x \\<^bsub>L\<^esub> y = \\<^bsub>L\<^esub>{x, y}" -subsection {* Lattices *} +subsection \Lattices\ locale weak_upper_semilattice = weak_partial_order + assumes sup_of_two_exists: @@ -434,7 +434,7 @@ locale weak_lattice = weak_upper_semilattice + weak_lower_semilattice -subsubsection {* Supremum *} +subsubsection \Supremum\ lemma (in weak_upper_semilattice) joinI: "[| !!l. least L l (Upper L {x, y}) ==> P l; x \ carrier L; y \ carrier L |] @@ -507,7 +507,7 @@ unfolding sup_def by (rule someI2) (auto intro: sup_of_singletonI) -text {* Condition on @{text A}: supremum exists. *} +text \Condition on @{text A}: supremum exists.\ lemma (in weak_upper_semilattice) sup_insertI: "[| !!s. least L s (Upper L (insert x A)) ==> P s; @@ -638,7 +638,7 @@ assumes L: "x \ carrier L" "y \ carrier L" "z \ carrier L" shows "x \ (y \ z) .= \{x, y, z}" proof (rule finite_sup_insertI) - -- {* The textbook argument in Jacobson I, p 457 *} + -- \The textbook argument in Jacobson I, p 457\ fix s assume sup: "least L s (Upper L {x, y, z})" show "x \ (y \ z) .= s" @@ -652,7 +652,7 @@ qed (simp_all add: L least_closed [OF sup]) qed (simp_all add: L) -text {* Commutativity holds for @{text "="}. *} +text \Commutativity holds for @{text "="}.\ lemma join_comm: fixes L (structure) @@ -673,7 +673,7 @@ qed -subsubsection {* Infimum *} +subsubsection \Infimum\ lemma (in weak_lower_semilattice) meetI: "[| !!i. greatest L i (Lower L {x, y}) ==> P i; @@ -747,7 +747,7 @@ unfolding inf_def by (rule someI2) (auto intro: inf_of_singletonI) -text {* Condition on @{text A}: infimum exists. *} +text \Condition on @{text A}: infimum exists.\ lemma (in weak_lower_semilattice) inf_insertI: "[| !!i. greatest L i (Lower L (insert x A)) ==> P i; @@ -879,7 +879,7 @@ assumes L: "x \ carrier L" "y \ carrier L" "z \ carrier L" shows "x \ (y \ z) .= \{x, y, z}" proof (rule finite_inf_insertI) - txt {* The textbook argument in Jacobson I, p 457 *} + txt \The textbook argument in Jacobson I, p 457\ fix i assume inf: "greatest L i (Lower L {x, y, z})" show "x \ (y \ z) .= i" @@ -911,19 +911,19 @@ qed -subsection {* Total Orders *} +subsection \Total Orders\ locale weak_total_order = weak_partial_order + assumes total: "[| x \ carrier L; y \ carrier L |] ==> x \ y | y \ x" -text {* Introduction rule: the usual definition of total order *} +text \Introduction rule: the usual definition of total order\ lemma (in weak_partial_order) weak_total_orderI: assumes total: "!!x y. [| x \ carrier L; y \ carrier L |] ==> x \ y | y \ x" shows "weak_total_order L" by standard (rule total) -text {* Total orders are lattices. *} +text \Total orders are lattices.\ sublocale weak_total_order < weak: weak_lattice proof @@ -969,7 +969,7 @@ qed -subsection {* Complete Lattices *} +subsection \Complete Lattices\ locale weak_complete_lattice = weak_lattice + assumes sup_exists: @@ -977,7 +977,7 @@ and inf_exists: "[| A \ carrier L |] ==> EX i. greatest L i (Lower L A)" -text {* Introduction rule: the usual definition of complete lattice *} +text \Introduction rule: the usual definition of complete lattice\ lemma (in weak_partial_order) weak_complete_latticeI: assumes sup_exists: @@ -1034,7 +1034,7 @@ "\ \ carrier L" by (unfold bottom_def) simp -text {* Jacobson: Theorem 8.1 *} +text \Jacobson: Theorem 8.1\ lemma Lower_empty [simp]: "Lower L {} = carrier L" @@ -1090,7 +1090,7 @@ (* TODO: prove dual version *) -subsection {* Orders and Lattices where @{text eq} is the Equality *} +subsection \Orders and Lattices where @{text eq} is the Equality\ locale partial_order = weak_partial_order + assumes eq_is_equal: "op .= = op =" @@ -1115,7 +1115,7 @@ end -text {* Least and greatest, as predicate *} +text \Least and greatest, as predicate\ lemma (in partial_order) least_unique: "[| least L x A; least L y A |] ==> x = y" @@ -1126,7 +1126,7 @@ using weak_greatest_unique unfolding eq_is_equal . -text {* Lattices *} +text \Lattices\ locale upper_semilattice = partial_order + assumes sup_of_two_exists: @@ -1145,7 +1145,7 @@ locale lattice = upper_semilattice + lower_semilattice -text {* Supremum *} +text \Supremum\ declare (in partial_order) weak_sup_of_singleton [simp del] @@ -1164,7 +1164,7 @@ using weak_join_assoc L unfolding eq_is_equal . -text {* Infimum *} +text \Infimum\ declare (in partial_order) weak_inf_of_singleton [simp del] @@ -1172,7 +1172,7 @@ "x \ carrier L ==> \{x} = x" using weak_inf_of_singleton unfolding eq_is_equal . -text {* Condition on @{text A}: infimum exists. *} +text \Condition on @{text A}: infimum exists.\ lemma (in lower_semilattice) meet_assoc_lemma: assumes L: "x \ carrier L" "y \ carrier L" "z \ carrier L" @@ -1185,7 +1185,7 @@ using weak_meet_assoc L unfolding eq_is_equal . -text {* Total Orders *} +text \Total Orders\ locale total_order = partial_order + assumes total_order_total: "[| x \ carrier L; y \ carrier L |] ==> x \ y | y \ x" @@ -1193,20 +1193,20 @@ sublocale total_order < weak: weak_total_order by standard (rule total_order_total) -text {* Introduction rule: the usual definition of total order *} +text \Introduction rule: the usual definition of total order\ lemma (in partial_order) total_orderI: assumes total: "!!x y. [| x \ carrier L; y \ carrier L |] ==> x \ y | y \ x" shows "total_order L" by standard (rule total) -text {* Total orders are lattices. *} +text \Total orders are lattices.\ sublocale total_order < weak: lattice by standard (auto intro: sup_of_two_exists inf_of_two_exists) -text {* Complete lattices *} +text \Complete lattices\ locale complete_lattice = lattice + assumes sup_exists: @@ -1217,7 +1217,7 @@ sublocale complete_lattice < weak: weak_complete_lattice by standard (auto intro: sup_exists inf_exists) -text {* Introduction rule: the usual definition of complete lattice *} +text \Introduction rule: the usual definition of complete lattice\ lemma (in partial_order) complete_latticeI: assumes sup_exists: @@ -1273,9 +1273,9 @@ (* TODO: prove dual version *) -subsection {* Examples *} +subsection \Examples\ -subsubsection {* The Powerset of a Set is a Complete Lattice *} +subsubsection \The Powerset of a Set is a Complete Lattice\ theorem powerset_is_complete_lattice: "complete_lattice \carrier = Pow A, eq = op =, le = op \\" @@ -1293,13 +1293,13 @@ fix B assume "B \ carrier ?L" then have "greatest ?L (\B \ A) (Lower ?L B)" - txt {* @{term "\B"} is not the infimum of @{term B}: - @{term "\{} = UNIV"} which is in general bigger than @{term "A"}! *} + txt \@{term "\B"} is not the infimum of @{term B}: + @{term "\{} = UNIV"} which is in general bigger than @{term "A"}!\ by (fastforce intro!: greatest_LowerI simp: Lower_def) then show "EX i. greatest ?L i (Lower ?L B)" .. qed -text {* An other example, that of the lattice of subgroups of a group, - can be found in Group theory (Section~\ref{sec:subgroup-lattice}). *} +text \An other example, that of the lattice of subgroups of a group, + can be found in Group theory (Section~\ref{sec:subgroup-lattice}).\ end