914 text {* Introduction rule: the usual definition of total order *} |
914 text {* Introduction rule: the usual definition of total order *} |
915 |
915 |
916 lemma (in weak_partial_order) weak_total_orderI: |
916 lemma (in weak_partial_order) weak_total_orderI: |
917 assumes total: "!!x y. [| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
917 assumes total: "!!x y. [| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
918 shows "weak_total_order L" |
918 shows "weak_total_order L" |
919 by unfold_locales (rule total) |
919 proof qed (rule total) |
920 |
920 |
921 text {* Total orders are lattices. *} |
921 text {* Total orders are lattices. *} |
922 |
922 |
923 interpretation weak_total_order < weak_lattice |
923 interpretation weak_total_order < weak_lattice |
924 proof unfold_locales |
924 proof |
925 fix x y |
925 fix x y |
926 assume L: "x \<in> carrier L" "y \<in> carrier L" |
926 assume L: "x \<in> carrier L" "y \<in> carrier L" |
927 show "EX s. least L s (Upper L {x, y})" |
927 show "EX s. least L s (Upper L {x, y})" |
928 proof - |
928 proof - |
929 note total L |
929 note total L |
978 assumes sup_exists: |
978 assumes sup_exists: |
979 "!!A. [| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
979 "!!A. [| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
980 and inf_exists: |
980 and inf_exists: |
981 "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
981 "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
982 shows "weak_complete_lattice L" |
982 shows "weak_complete_lattice L" |
983 by unfold_locales (auto intro: sup_exists inf_exists) |
983 proof qed (auto intro: sup_exists inf_exists) |
984 |
984 |
985 constdefs (structure L) |
985 constdefs (structure L) |
986 top :: "_ => 'a" ("\<top>\<index>") |
986 top :: "_ => 'a" ("\<top>\<index>") |
987 "\<top> == sup L (carrier L)" |
987 "\<top> == sup L (carrier L)" |
988 |
988 |
1104 assumes "a \<in> carrier L" "b \<in> carrier L" |
1104 assumes "a \<in> carrier L" "b \<in> carrier L" |
1105 and "a \<sqsubset> b" "b \<sqsubset> a" |
1105 and "a \<sqsubset> b" "b \<sqsubset> a" |
1106 shows "P" |
1106 shows "P" |
1107 using assms unfolding lless_eq by auto |
1107 using assms unfolding lless_eq by auto |
1108 |
1108 |
1109 lemma lless_trans [trans]: |
|
1110 assumes "a \<sqsubset> b" "b \<sqsubset> c" |
|
1111 and carr[simp]: "a \<in> carrier L" "b \<in> carrier L" "c \<in> carrier L" |
|
1112 shows "a \<sqsubset> c" |
|
1113 using assms unfolding lless_eq by (blast dest: le_trans intro: sym) |
|
1114 |
|
1115 end |
1109 end |
1116 |
1110 |
1117 |
1111 |
1118 text {* Least and greatest, as predicate *} |
1112 text {* Least and greatest, as predicate *} |
1119 |
1113 |
1131 locale upper_semilattice = partial_order + |
1125 locale upper_semilattice = partial_order + |
1132 assumes sup_of_two_exists: |
1126 assumes sup_of_two_exists: |
1133 "[| x \<in> carrier L; y \<in> carrier L |] ==> EX s. least L s (Upper L {x, y})" |
1127 "[| x \<in> carrier L; y \<in> carrier L |] ==> EX s. least L s (Upper L {x, y})" |
1134 |
1128 |
1135 interpretation upper_semilattice < weak_upper_semilattice |
1129 interpretation upper_semilattice < weak_upper_semilattice |
1136 by unfold_locales (rule sup_of_two_exists) |
1130 proof qed (rule sup_of_two_exists) |
1137 |
1131 |
1138 locale lower_semilattice = partial_order + |
1132 locale lower_semilattice = partial_order + |
1139 assumes inf_of_two_exists: |
1133 assumes inf_of_two_exists: |
1140 "[| x \<in> carrier L; y \<in> carrier L |] ==> EX s. greatest L s (Lower L {x, y})" |
1134 "[| x \<in> carrier L; y \<in> carrier L |] ==> EX s. greatest L s (Lower L {x, y})" |
1141 |
1135 |
1142 interpretation lower_semilattice < weak_lower_semilattice |
1136 interpretation lower_semilattice < weak_lower_semilattice |
1143 by unfold_locales (rule inf_of_two_exists) |
1137 proof qed (rule inf_of_two_exists) |
1144 |
1138 |
1145 locale lattice = upper_semilattice + lower_semilattice |
1139 locale lattice = upper_semilattice + lower_semilattice |
1146 |
1140 |
1147 |
1141 |
1148 text {* Supremum *} |
1142 text {* Supremum *} |
1186 |
1180 |
1187 |
1181 |
1188 text {* Total Orders *} |
1182 text {* Total Orders *} |
1189 |
1183 |
1190 locale total_order = partial_order + |
1184 locale total_order = partial_order + |
1191 assumes total: "[| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
1185 assumes total_order_total: "[| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
1192 |
1186 |
1193 interpretation total_order < weak_total_order |
1187 interpretation total_order < weak_total_order |
1194 by unfold_locales (rule total) |
1188 proof qed (rule total_order_total) |
1195 |
1189 |
1196 text {* Introduction rule: the usual definition of total order *} |
1190 text {* Introduction rule: the usual definition of total order *} |
1197 |
1191 |
1198 lemma (in partial_order) total_orderI: |
1192 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" |
1193 assumes total: "!!x y. [| x \<in> carrier L; y \<in> carrier L |] ==> x \<sqsubseteq> y | y \<sqsubseteq> x" |
1200 shows "total_order L" |
1194 shows "total_order L" |
1201 by unfold_locales (rule total) |
1195 proof qed (rule total) |
1202 |
1196 |
1203 text {* Total orders are lattices. *} |
1197 text {* Total orders are lattices. *} |
1204 |
1198 |
1205 interpretation total_order < lattice |
1199 interpretation total_order < lattice |
1206 by unfold_locales (auto intro: sup_of_two_exists inf_of_two_exists) |
1200 proof qed (auto intro: sup_of_two_exists inf_of_two_exists) |
1207 |
1201 |
1208 |
1202 |
1209 text {* Complete lattices *} |
1203 text {* Complete lattices *} |
1210 |
1204 |
1211 locale complete_lattice = lattice + |
1205 locale complete_lattice = lattice + |
1213 "[| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
1207 "[| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
1214 and inf_exists: |
1208 and inf_exists: |
1215 "[| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
1209 "[| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
1216 |
1210 |
1217 interpretation complete_lattice < weak_complete_lattice |
1211 interpretation complete_lattice < weak_complete_lattice |
1218 by unfold_locales (auto intro: sup_exists inf_exists) |
1212 proof qed (auto intro: sup_exists inf_exists) |
1219 |
1213 |
1220 text {* Introduction rule: the usual definition of complete lattice *} |
1214 text {* Introduction rule: the usual definition of complete lattice *} |
1221 |
1215 |
1222 lemma (in partial_order) complete_latticeI: |
1216 lemma (in partial_order) complete_latticeI: |
1223 assumes sup_exists: |
1217 assumes sup_exists: |
1224 "!!A. [| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
1218 "!!A. [| A \<subseteq> carrier L |] ==> EX s. least L s (Upper L A)" |
1225 and inf_exists: |
1219 and inf_exists: |
1226 "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
1220 "!!A. [| A \<subseteq> carrier L |] ==> EX i. greatest L i (Lower L A)" |
1227 shows "complete_lattice L" |
1221 shows "complete_lattice L" |
1228 by unfold_locales (auto intro: sup_exists inf_exists) |
1222 proof qed (auto intro: sup_exists inf_exists) |
1229 |
1223 |
1230 theorem (in partial_order) complete_lattice_criterion1: |
1224 theorem (in partial_order) complete_lattice_criterion1: |
1231 assumes top_exists: "EX g. greatest L g (carrier L)" |
1225 assumes top_exists: "EX g. greatest L g (carrier L)" |
1232 and inf_exists: |
1226 and inf_exists: |
1233 "!!A. [| A \<subseteq> carrier L; A ~= {} |] ==> EX i. greatest L i (Lower L A)" |
1227 "!!A. [| A \<subseteq> carrier L; A ~= {} |] ==> EX i. greatest L i (Lower L A)" |
1280 theorem powerset_is_complete_lattice: |
1274 theorem powerset_is_complete_lattice: |
1281 "complete_lattice (| carrier = Pow A, eq = op =, le = op \<subseteq> |)" |
1275 "complete_lattice (| carrier = Pow A, eq = op =, le = op \<subseteq> |)" |
1282 (is "complete_lattice ?L") |
1276 (is "complete_lattice ?L") |
1283 proof (rule partial_order.complete_latticeI) |
1277 proof (rule partial_order.complete_latticeI) |
1284 show "partial_order ?L" |
1278 show "partial_order ?L" |
1285 by unfold_locales auto |
1279 proof qed auto |
1286 next |
1280 next |
1287 fix B |
1281 fix B |
1288 assume B: "B \<subseteq> carrier ?L" |
1282 assume B: "B \<subseteq> carrier ?L" |
1289 show "EX s. least ?L s (Upper ?L B)" |
1283 show "EX s. least ?L s (Upper ?L B)" |
1290 proof |
1284 proof |