919 text {* Introduction rule: the usual definition of total order *} |
919 text {* Introduction rule: the usual definition of total order *} |
920 |
920 |
921 lemma (in weak_partial_order) weak_total_orderI: |
921 lemma (in weak_partial_order) weak_total_orderI: |
922 assumes total: "!!x y. [| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
922 assumes total: "!!x y. [| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
923 shows "weak_total_order L" |
923 shows "weak_total_order L" |
924 by default (rule total) |
924 by standard (rule total) |
925 |
925 |
926 text {* Total orders are lattices. *} |
926 text {* Total orders are lattices. *} |
927 |
927 |
928 sublocale weak_total_order < weak: weak_lattice |
928 sublocale weak_total_order < weak: weak_lattice |
929 proof |
929 proof |
983 assumes sup_exists: |
983 assumes sup_exists: |
984 "!!A. [| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
984 "!!A. [| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
985 and inf_exists: |
985 and inf_exists: |
986 "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
986 "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
987 shows "weak_complete_lattice L" |
987 shows "weak_complete_lattice L" |
988 by default (auto intro: sup_exists inf_exists) |
988 by standard (auto intro: sup_exists inf_exists) |
989 |
989 |
990 definition |
990 definition |
991 top :: "_ => 'a" ("\<top>\<index>") |
991 top :: "_ => 'a" ("\<top>\<index>") |
992 where "\<top>\<^bsub>L\<^esub> = sup L (carrier L)" |
992 where "\<top>\<^bsub>L\<^esub> = sup L (carrier L)" |
993 |
993 |
1131 locale upper_semilattice = partial_order + |
1131 locale upper_semilattice = partial_order + |
1132 assumes sup_of_two_exists: |
1132 assumes sup_of_two_exists: |
1133 "[| x \<in> carrier L; y \<in> carrier L |] ==> EX s. least L s (Upper L {x, y})" |
1133 "[| x \<in> carrier L; y \<in> carrier L |] ==> EX s. least L s (Upper L {x, y})" |
1134 |
1134 |
1135 sublocale upper_semilattice < weak: weak_upper_semilattice |
1135 sublocale upper_semilattice < weak: weak_upper_semilattice |
1136 by default (rule sup_of_two_exists) |
1136 by standard (rule sup_of_two_exists) |
1137 |
1137 |
1138 locale lower_semilattice = partial_order + |
1138 locale lower_semilattice = partial_order + |
1139 assumes inf_of_two_exists: |
1139 assumes inf_of_two_exists: |
1140 "[| x \<in> carrier L; y \<in> carrier L |] ==> EX s. greatest L s (Lower L {x, y})" |
1140 "[| x \<in> carrier L; y \<in> carrier L |] ==> EX s. greatest L s (Lower L {x, y})" |
1141 |
1141 |
1142 sublocale lower_semilattice < weak: weak_lower_semilattice |
1142 sublocale lower_semilattice < weak: weak_lower_semilattice |
1143 by default (rule inf_of_two_exists) |
1143 by standard (rule inf_of_two_exists) |
1144 |
1144 |
1145 locale lattice = upper_semilattice + lower_semilattice |
1145 locale lattice = upper_semilattice + lower_semilattice |
1146 |
1146 |
1147 |
1147 |
1148 text {* Supremum *} |
1148 text {* Supremum *} |
1189 |
1189 |
1190 locale total_order = partial_order + |
1190 locale total_order = partial_order + |
1191 assumes total_order_total: "[| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
1191 assumes total_order_total: "[| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
1192 |
1192 |
1193 sublocale total_order < weak: weak_total_order |
1193 sublocale total_order < weak: weak_total_order |
1194 by default (rule total_order_total) |
1194 by standard (rule total_order_total) |
1195 |
1195 |
1196 text {* Introduction rule: the usual definition of total order *} |
1196 text {* Introduction rule: the usual definition of total order *} |
1197 |
1197 |
1198 lemma (in partial_order) total_orderI: |
1198 lemma (in partial_order) total_orderI: |
1199 assumes total: "!!x y. [| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
1199 assumes total: "!!x y. [| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
1200 shows "total_order L" |
1200 shows "total_order L" |
1201 by default (rule total) |
1201 by standard (rule total) |
1202 |
1202 |
1203 text {* Total orders are lattices. *} |
1203 text {* Total orders are lattices. *} |
1204 |
1204 |
1205 sublocale total_order < weak: lattice |
1205 sublocale total_order < weak: lattice |
1206 by default (auto intro: sup_of_two_exists inf_of_two_exists) |
1206 by standard (auto intro: sup_of_two_exists inf_of_two_exists) |
1207 |
1207 |
1208 |
1208 |
1209 text {* Complete lattices *} |
1209 text {* Complete lattices *} |
1210 |
1210 |
1211 locale complete_lattice = lattice + |
1211 locale complete_lattice = lattice + |
1213 "[| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
1213 "[| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
1214 and inf_exists: |
1214 and inf_exists: |
1215 "[| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
1215 "[| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
1216 |
1216 |
1217 sublocale complete_lattice < weak: weak_complete_lattice |
1217 sublocale complete_lattice < weak: weak_complete_lattice |
1218 by default (auto intro: sup_exists inf_exists) |
1218 by standard (auto intro: sup_exists inf_exists) |
1219 |
1219 |
1220 text {* Introduction rule: the usual definition of complete lattice *} |
1220 text {* Introduction rule: the usual definition of complete lattice *} |
1221 |
1221 |
1222 lemma (in partial_order) complete_latticeI: |
1222 lemma (in partial_order) complete_latticeI: |
1223 assumes sup_exists: |
1223 assumes sup_exists: |
1224 "!!A. [| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
1224 "!!A. [| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
1225 and inf_exists: |
1225 and inf_exists: |
1226 "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
1226 "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
1227 shows "complete_lattice L" |
1227 shows "complete_lattice L" |
1228 by default (auto intro: sup_exists inf_exists) |
1228 by standard (auto intro: sup_exists inf_exists) |
1229 |
1229 |
1230 theorem (in partial_order) complete_lattice_criterion1: |
1230 theorem (in partial_order) complete_lattice_criterion1: |
1231 assumes top_exists: "EX g. greatest L g (carrier L)" |
1231 assumes top_exists: "EX g. greatest L g (carrier L)" |
1232 and inf_exists: |
1232 and inf_exists: |
1233 "!!A. [| A \<subseteq> carrier L; A ~= {} |] ==> EX i. greatest L i (Lower L A)" |
1233 "!!A. [| A \<subseteq> carrier L; A ~= {} |] ==> EX i. greatest L i (Lower L A)" |
1280 theorem powerset_is_complete_lattice: |
1280 theorem powerset_is_complete_lattice: |
1281 "complete_lattice \<lparr>carrier = Pow A, eq = op =, le = op \<subseteq>\<rparr>" |
1281 "complete_lattice \<lparr>carrier = Pow A, eq = op =, le = op \<subseteq>\<rparr>" |
1282 (is "complete_lattice ?L") |
1282 (is "complete_lattice ?L") |
1283 proof (rule partial_order.complete_latticeI) |
1283 proof (rule partial_order.complete_latticeI) |
1284 show "partial_order ?L" |
1284 show "partial_order ?L" |
1285 by default auto |
1285 by standard auto |
1286 next |
1286 next |
1287 fix B |
1287 fix B |
1288 assume "B \<subseteq> carrier ?L" |
1288 assume "B \<subseteq> carrier ?L" |
1289 then have "least ?L (\<Union>B) (Upper ?L B)" |
1289 then have "least ?L (\<Union>B) (Upper ?L B)" |
1290 by (fastforce intro!: least_UpperI simp: Upper_def) |
1290 by (fastforce intro!: least_UpperI simp: Upper_def) |