17 the connection between cardinals and: |
17 the connection between cardinals and: |
18 \begin{itemize} |
18 \begin{itemize} |
19 \item standard set-theoretic constructions: products, |
19 \item standard set-theoretic constructions: products, |
20 sums, unions, lists, powersets, set-of finite sets operator; |
20 sums, unions, lists, powersets, set-of finite sets operator; |
21 \item finiteness and infiniteness (in particular, with the numeric cardinal operator |
21 \item finiteness and infiniteness (in particular, with the numeric cardinal operator |
22 for finite sets, @{text "card"}, from the theory @{text "Finite_Sets.thy"}). |
22 for finite sets, \<open>card\<close>, from the theory \<open>Finite_Sets.thy\<close>). |
23 \end{itemize} |
23 \end{itemize} |
24 % |
24 % |
25 On the way, we define the canonical $\omega$ cardinal and finite cardinals. We also |
25 On the way, we define the canonical $\omega$ cardinal and finite cardinals. We also |
26 define (again, up to order isomorphism) the successor of a cardinal, and show that |
26 define (again, up to order isomorphism) the successor of a cardinal, and show that |
27 any cardinal admits a successor. |
27 any cardinal admits a successor. |
35 |
35 |
36 |
36 |
37 subsection \<open>Cardinal orders\<close> |
37 subsection \<open>Cardinal orders\<close> |
38 |
38 |
39 text\<open>A cardinal order in our setting shall be a well-order {\em minim} w.r.t. the |
39 text\<open>A cardinal order in our setting shall be a well-order {\em minim} w.r.t. the |
40 order-embedding relation, @{text "\<le>o"} (which is the same as being {\em minimal} w.r.t. the |
40 order-embedding relation, \<open>\<le>o\<close> (which is the same as being {\em minimal} w.r.t. the |
41 strict order-embedding relation, @{text "<o"}), among all the well-orders on its field.\<close> |
41 strict order-embedding relation, \<open><o\<close>), among all the well-orders on its field.\<close> |
42 |
42 |
43 definition card_order_on :: "'a set \<Rightarrow> 'a rel \<Rightarrow> bool" |
43 definition card_order_on :: "'a set \<Rightarrow> 'a rel \<Rightarrow> bool" |
44 where |
44 where |
45 "card_order_on A r \<equiv> well_order_on A r \<and> (\<forall>r'. well_order_on A r' \<longrightarrow> r \<le>o r')" |
45 "card_order_on A r \<equiv> well_order_on A r \<and> (\<forall>r'. well_order_on A r' \<longrightarrow> r \<le>o r')" |
46 |
46 |
57 unfolding card_order_on_def using well_order_on_Field by blast |
57 unfolding card_order_on_def using well_order_on_Field by blast |
58 |
58 |
59 text\<open>The existence of a cardinal relation on any given set (which will mean |
59 text\<open>The existence of a cardinal relation on any given set (which will mean |
60 that any set has a cardinal) follows from two facts: |
60 that any set has a cardinal) follows from two facts: |
61 \begin{itemize} |
61 \begin{itemize} |
62 \item Zermelo's theorem (proved in @{text "Zorn.thy"} as theorem @{text "well_order_on"}), |
62 \item Zermelo's theorem (proved in \<open>Zorn.thy\<close> as theorem \<open>well_order_on\<close>), |
63 which states that on any given set there exists a well-order; |
63 which states that on any given set there exists a well-order; |
64 \item The well-founded-ness of @{text "<o"}, ensuring that then there exists a minimal |
64 \item The well-founded-ness of \<open><o\<close>, ensuring that then there exists a minimal |
65 such well-order, i.e., a cardinal order. |
65 such well-order, i.e., a cardinal order. |
66 \end{itemize} |
66 \end{itemize} |
67 \<close> |
67 \<close> |
68 |
68 |
69 theorem card_order_on: "\<exists>r. card_order_on A r" |
69 theorem card_order_on: "\<exists>r. card_order_on A r" |
346 subsection \<open>Cardinals versus set operations on arbitrary sets\<close> |
346 subsection \<open>Cardinals versus set operations on arbitrary sets\<close> |
347 |
347 |
348 text\<open>Here we embark in a long journey of simple results showing |
348 text\<open>Here we embark in a long journey of simple results showing |
349 that the standard set-theoretic operations are well-behaved w.r.t. the notion of |
349 that the standard set-theoretic operations are well-behaved w.r.t. the notion of |
350 cardinal -- essentially, this means that they preserve the ``cardinal identity" |
350 cardinal -- essentially, this means that they preserve the ``cardinal identity" |
351 @{text "=o"} and are monotonic w.r.t. @{text "\<le>o"}. |
351 \<open>=o\<close> and are monotonic w.r.t. \<open>\<le>o\<close>. |
352 \<close> |
352 \<close> |
353 |
353 |
354 lemma card_of_empty: "|{}| \<le>o |A|" |
354 lemma card_of_empty: "|{}| \<le>o |A|" |
355 using card_of_ordLeq inj_on_id by blast |
355 using card_of_ordLeq inj_on_id by blast |
356 |
356 |
821 |
821 |
822 subsection \<open>Cardinals versus set operations involving infinite sets\<close> |
822 subsection \<open>Cardinals versus set operations involving infinite sets\<close> |
823 |
823 |
824 text\<open>Here we show that, for infinite sets, most set-theoretic constructions |
824 text\<open>Here we show that, for infinite sets, most set-theoretic constructions |
825 do not increase the cardinality. The cornerstone for this is |
825 do not increase the cardinality. The cornerstone for this is |
826 theorem @{text "Card_order_Times_same_infinite"}, which states that self-product |
826 theorem \<open>Card_order_Times_same_infinite\<close>, which states that self-product |
827 does not increase cardinality -- the proof of this fact adapts a standard |
827 does not increase cardinality -- the proof of this fact adapts a standard |
828 set-theoretic argument, as presented, e.g., in the proof of theorem 1.5.11 |
828 set-theoretic argument, as presented, e.g., in the proof of theorem 1.5.11 |
829 at page 47 in @{cite "card-book"}. Then everything else follows fairly easily.\<close> |
829 at page 47 in @{cite "card-book"}. Then everything else follows fairly easily.\<close> |
830 |
830 |
831 lemma infinite_iff_card_of_nat: |
831 lemma infinite_iff_card_of_nat: |
1142 |
1142 |
1143 subsection \<open>The cardinal $\omega$ and the finite cardinals\<close> |
1143 subsection \<open>The cardinal $\omega$ and the finite cardinals\<close> |
1144 |
1144 |
1145 text\<open>The cardinal $\omega$, of natural numbers, shall be the standard non-strict |
1145 text\<open>The cardinal $\omega$, of natural numbers, shall be the standard non-strict |
1146 order relation on |
1146 order relation on |
1147 @{text "nat"}, that we abbreviate by @{text "natLeq"}. The finite cardinals |
1147 \<open>nat\<close>, that we abbreviate by \<open>natLeq\<close>. The finite cardinals |
1148 shall be the restrictions of these relations to the numbers smaller than |
1148 shall be the restrictions of these relations to the numbers smaller than |
1149 fixed numbers @{text "n"}, that we abbreviate by @{text "natLeq_on n"}.\<close> |
1149 fixed numbers \<open>n\<close>, that we abbreviate by \<open>natLeq_on n\<close>.\<close> |
1150 |
1150 |
1151 definition "(natLeq::(nat * nat) set) \<equiv> {(x,y). x \<le> y}" |
1151 definition "(natLeq::(nat * nat) set) \<equiv> {(x,y). x \<le> y}" |
1152 definition "(natLess::(nat * nat) set) \<equiv> {(x,y). x < y}" |
1152 definition "(natLess::(nat * nat) set) \<equiv> {(x,y). x < y}" |
1153 |
1153 |
1154 abbreviation natLeq_on :: "nat \<Rightarrow> (nat * nat) set" |
1154 abbreviation natLeq_on :: "nat \<Rightarrow> (nat * nat) set" |
1258 card_of_Well_order natLeq_Well_order by blast |
1258 card_of_Well_order natLeq_Well_order by blast |
1259 |
1259 |
1260 |
1260 |
1261 subsection \<open>The successor of a cardinal\<close> |
1261 subsection \<open>The successor of a cardinal\<close> |
1262 |
1262 |
1263 text\<open>First we define @{text "isCardSuc r r'"}, the notion of @{text "r'"} |
1263 text\<open>First we define \<open>isCardSuc r r'\<close>, the notion of \<open>r'\<close> |
1264 being a successor cardinal of @{text "r"}. Although the definition does |
1264 being a successor cardinal of \<open>r\<close>. Although the definition does |
1265 not require @{text "r"} to be a cardinal, only this case will be meaningful.\<close> |
1265 not require \<open>r\<close> to be a cardinal, only this case will be meaningful.\<close> |
1266 |
1266 |
1267 definition isCardSuc :: "'a rel \<Rightarrow> 'a set rel \<Rightarrow> bool" |
1267 definition isCardSuc :: "'a rel \<Rightarrow> 'a set rel \<Rightarrow> bool" |
1268 where |
1268 where |
1269 "isCardSuc r r' \<equiv> |
1269 "isCardSuc r r' \<equiv> |
1270 Card_order r' \<and> r <o r' \<and> |
1270 Card_order r' \<and> r <o r' \<and> |
1271 (\<forall>(r''::'a set rel). Card_order r'' \<and> r <o r'' \<longrightarrow> r' \<le>o r'')" |
1271 (\<forall>(r''::'a set rel). Card_order r'' \<and> r <o r'' \<longrightarrow> r' \<le>o r'')" |
1272 |
1272 |
1273 text\<open>Now we introduce the cardinal-successor operator @{text "cardSuc"}, |
1273 text\<open>Now we introduce the cardinal-successor operator \<open>cardSuc\<close>, |
1274 by picking {\em some} cardinal-order relation fulfilling @{text "isCardSuc"}. |
1274 by picking {\em some} cardinal-order relation fulfilling \<open>isCardSuc\<close>. |
1275 Again, the picked item shall be proved unique up to order-isomorphism.\<close> |
1275 Again, the picked item shall be proved unique up to order-isomorphism.\<close> |
1276 |
1276 |
1277 definition cardSuc :: "'a rel \<Rightarrow> 'a set rel" |
1277 definition cardSuc :: "'a rel \<Rightarrow> 'a set rel" |
1278 where |
1278 where |
1279 "cardSuc r \<equiv> SOME r'. isCardSuc r r'" |
1279 "cardSuc r \<equiv> SOME r'. isCardSuc r r'" |
1310 |
1310 |
1311 lemma cardSuc_ordLeq: |
1311 lemma cardSuc_ordLeq: |
1312 "Card_order r \<Longrightarrow> r \<le>o cardSuc r" |
1312 "Card_order r \<Longrightarrow> r \<le>o cardSuc r" |
1313 using cardSuc_greater ordLeq_iff_ordLess_or_ordIso by blast |
1313 using cardSuc_greater ordLeq_iff_ordLess_or_ordIso by blast |
1314 |
1314 |
1315 text\<open>The minimality property of @{text "cardSuc"} originally present in its definition |
1315 text\<open>The minimality property of \<open>cardSuc\<close> originally present in its definition |
1316 is local to the type @{text "'a set rel"}, i.e., that of @{text "cardSuc r"}:\<close> |
1316 is local to the type \<open>'a set rel\<close>, i.e., that of \<open>cardSuc r\<close>:\<close> |
1317 |
1317 |
1318 lemma cardSuc_least_aux: |
1318 lemma cardSuc_least_aux: |
1319 "\<lbrakk>Card_order (r::'a rel); Card_order (r'::'a set rel); r <o r'\<rbrakk> \<Longrightarrow> cardSuc r \<le>o r'" |
1319 "\<lbrakk>Card_order (r::'a rel); Card_order (r'::'a set rel); r <o r'\<rbrakk> \<Longrightarrow> cardSuc r \<le>o r'" |
1320 using cardSuc_isCardSuc unfolding isCardSuc_def by blast |
1320 using cardSuc_isCardSuc unfolding isCardSuc_def by blast |
1321 |
1321 |