src/HOL/Algebra/Lattice.thy
changeset 61169 4de9ff3ea29a
parent 60585 48fdff264eb2
child 61382 efac889fccbc
equal deleted inserted replaced
61168:dcdfb6355a05 61169:4de9ff3ea29a
   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)