src/HOL/BNF_Cardinal_Order_Relation.thy
changeset 61799 4cf66f21b764
parent 60758 d8d85a8172b5
child 61943 7fba644ed827
equal deleted inserted replaced
61798:27f3c10b0b50 61799:4cf66f21b764
    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