src/HOL/Algebra/Lattice.thy
changeset 28823 dcbef866c9e2
parent 27717 21bbd410ba04
child 29237 e90d9d51106b
equal deleted inserted replaced
28822:7ca11ecbc4fb 28823:dcbef866c9e2
   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