equal
deleted
inserted
replaced
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) |