src/ZF/Cardinal_AC.thy
changeset 69593 3dda49e08b9d
parent 67443 3abf6a722518
child 72797 402afc68f2f9
equal deleted inserted replaced
69592:a80d8ec6c998 69593:3dda49e08b9d
    14 lemma cardinal_eqpoll: "|A| \<approx> A"
    14 lemma cardinal_eqpoll: "|A| \<approx> A"
    15 apply (rule AC_well_ord [THEN exE])
    15 apply (rule AC_well_ord [THEN exE])
    16 apply (erule well_ord_cardinal_eqpoll)
    16 apply (erule well_ord_cardinal_eqpoll)
    17 done
    17 done
    18 
    18 
    19 text\<open>The theorem @{term "||A|| = |A|"}\<close>
    19 text\<open>The theorem \<^term>\<open>||A|| = |A|\<close>\<close>
    20 lemmas cardinal_idem = cardinal_eqpoll [THEN cardinal_cong, simp]
    20 lemmas cardinal_idem = cardinal_eqpoll [THEN cardinal_cong, simp]
    21 
    21 
    22 lemma cardinal_eqE: "|X| = |Y| ==> X \<approx> Y"
    22 lemma cardinal_eqE: "|X| = |Y| ==> X \<approx> Y"
    23 apply (rule AC_well_ord [THEN exE])
    23 apply (rule AC_well_ord [THEN exE])
    24 apply (rule AC_well_ord [THEN exE])
    24 apply (rule AC_well_ord [THEN exE])
   169   also have "... \<approx> K" 
   169   also have "... \<approx> K" 
   170     by (simp add: K InfCard_square_eq InfCard_is_Card Card_cardinal_eq)
   170     by (simp add: K InfCard_square_eq InfCard_is_Card Card_cardinal_eq)
   171   finally show "(\<Union>i\<in>K. X(i)) \<lesssim> K" .
   171   finally show "(\<Union>i\<in>K. X(i)) \<lesssim> K" .
   172 qed
   172 qed
   173 
   173 
   174 text\<open>The same again, using @{term csucc}\<close>
   174 text\<open>The same again, using \<^term>\<open>csucc\<close>\<close>
   175 lemma cardinal_UN_lt_csucc:
   175 lemma cardinal_UN_lt_csucc:
   176      "[| InfCard(K);  \<And>i. i\<in>K \<Longrightarrow> |X(i)| < csucc(K) |]
   176      "[| InfCard(K);  \<And>i. i\<in>K \<Longrightarrow> |X(i)| < csucc(K) |]
   177       ==> |\<Union>i\<in>K. X(i)| < csucc(K)"
   177       ==> |\<Union>i\<in>K. X(i)| < csucc(K)"
   178 by (simp add: Card_lt_csucc_iff cardinal_UN_le InfCard_is_Card Card_cardinal)
   178 by (simp add: Card_lt_csucc_iff cardinal_UN_le InfCard_is_Card Card_cardinal)
   179 
   179 
   190 
   190 
   191 
   191 
   192 subsection\<open>The Main Result for Infinite-Branching Datatypes\<close>
   192 subsection\<open>The Main Result for Infinite-Branching Datatypes\<close>
   193 
   193 
   194 text\<open>As above, but the index set need not be a cardinal. Work
   194 text\<open>As above, but the index set need not be a cardinal. Work
   195 backwards along the injection from @{term W} into @{term K}, given
   195 backwards along the injection from \<^term>\<open>W\<close> into \<^term>\<open>K\<close>, given
   196 that @{term"W\<noteq>0"}.\<close>
   196 that \<^term>\<open>W\<noteq>0\<close>.\<close>
   197 
   197 
   198 lemma inj_UN_subset:
   198 lemma inj_UN_subset:
   199   assumes f: "f \<in> inj(A,B)" and a: "a \<in> A"
   199   assumes f: "f \<in> inj(A,B)" and a: "a \<in> A"
   200   shows "(\<Union>x\<in>A. C(x)) \<subseteq> (\<Union>y\<in>B. C(if y \<in> range(f) then converse(f)`y else a))"
   200   shows "(\<Union>x\<in>A. C(x)) \<subseteq> (\<Union>y\<in>B. C(if y \<in> range(f) then converse(f)`y else a))"
   201 proof (rule UN_least)
   201 proof (rule UN_least)