equal
deleted
inserted
replaced
22 (* j=|A| *) |
22 (* j=|A| *) |
23 lemma lepoll_imp_ex_le_eqpoll: |
23 lemma lepoll_imp_ex_le_eqpoll: |
24 "[| A \<lesssim> i; Ord(i) |] ==> \<exists>j. j le i & A \<approx> j" |
24 "[| A \<lesssim> i; Ord(i) |] ==> \<exists>j. j le i & A \<approx> j" |
25 by (blast intro!: lepoll_cardinal_le well_ord_Memrel |
25 by (blast intro!: lepoll_cardinal_le well_ord_Memrel |
26 well_ord_cardinal_eqpoll [THEN eqpoll_sym] |
26 well_ord_cardinal_eqpoll [THEN eqpoll_sym] |
27 dest: lepoll_well_ord); |
27 dest: lepoll_well_ord) |
28 |
28 |
29 (* j=|A| *) |
29 (* j=|A| *) |
30 lemma lesspoll_imp_ex_lt_eqpoll: |
30 lemma lesspoll_imp_ex_lt_eqpoll: |
31 "[| A \<prec> i; Ord(i) |] ==> \<exists>j. j<i & A \<approx> j" |
31 "[| A \<prec> i; Ord(i) |] ==> \<exists>j. j<i & A \<approx> j" |
32 by (unfold lesspoll_def, blast dest!: lepoll_imp_ex_le_eqpoll elim!: leE) |
32 by (unfold lesspoll_def, blast dest!: lepoll_imp_ex_le_eqpoll elim!: leE) |
85 |
85 |
86 (*Finally we reach this result. Surely there's a simpler proof, as sketched |
86 (*Finally we reach this result. Surely there's a simpler proof, as sketched |
87 above?*) |
87 above?*) |
88 lemma Un_lepoll_Inf_Ord: |
88 lemma Un_lepoll_Inf_Ord: |
89 "[| A \<lesssim> i; B \<lesssim> i; ~Finite(i); Ord(i) |] ==> A Un B \<lesssim> i" |
89 "[| A \<lesssim> i; B \<lesssim> i; ~Finite(i); Ord(i) |] ==> A Un B \<lesssim> i" |
90 apply (rule_tac A1 = "i" and C1 = "i" in ex_eqpoll_disjoint [THEN exE]) |
90 apply (rule_tac A1 = i and C1 = i in ex_eqpoll_disjoint [THEN exE]) |
91 apply (erule conjE) |
91 apply (erule conjE) |
92 apply (drule lepoll_trans) |
92 apply (drule lepoll_trans) |
93 apply (erule eqpoll_sym [THEN eqpoll_imp_lepoll]) |
93 apply (erule eqpoll_sym [THEN eqpoll_imp_lepoll]) |
94 apply (rule Un_lepoll_Un [THEN lepoll_trans], (assumption+)) |
94 apply (rule Un_lepoll_Un [THEN lepoll_trans], (assumption+)) |
95 apply (blast intro: eqpoll_refl Un_eqpoll_Inf_Ord eqpoll_imp_lepoll) |
95 apply (blast intro: eqpoll_refl Un_eqpoll_Inf_Ord eqpoll_imp_lepoll) |
142 done |
142 done |
143 |
143 |
144 lemma UN_fun_lepoll: |
144 lemma UN_fun_lepoll: |
145 "[| \<forall>b \<in> a. f`b \<lesssim> n & f`b \<subseteq> T; well_ord(T, R); |
145 "[| \<forall>b \<in> a. f`b \<lesssim> n & f`b \<subseteq> T; well_ord(T, R); |
146 ~Finite(a); Ord(a); n \<in> nat |] ==> (\<Union>b \<in> a. f`b) \<lesssim> a" |
146 ~Finite(a); Ord(a); n \<in> nat |] ==> (\<Union>b \<in> a. f`b) \<lesssim> a" |
147 by (blast intro: UN_fun_lepoll_lemma); |
147 by (blast intro: UN_fun_lepoll_lemma) |
148 |
148 |
149 lemma UN_lepoll: |
149 lemma UN_lepoll: |
150 "[| \<forall>b \<in> a. F(b) \<lesssim> n & F(b) \<subseteq> T; well_ord(T, R); |
150 "[| \<forall>b \<in> a. F(b) \<lesssim> n & F(b) \<subseteq> T; well_ord(T, R); |
151 ~Finite(a); Ord(a); n \<in> nat |] |
151 ~Finite(a); Ord(a); n \<in> nat |] |
152 ==> (\<Union>b \<in> a. F(b)) \<lesssim> a" |
152 ==> (\<Union>b \<in> a. F(b)) \<lesssim> a" |
162 apply (rule subsetI) |
162 apply (rule subsetI) |
163 apply (erule UN_E) |
163 apply (erule UN_E) |
164 apply (rule UN_I) |
164 apply (rule UN_I) |
165 apply (rule_tac P = "%z. x \<in> F (z) " in Least_in_Ord, (assumption+)) |
165 apply (rule_tac P = "%z. x \<in> F (z) " in Least_in_Ord, (assumption+)) |
166 apply (rule DiffI, best intro: Ord_in_Ord LeastI, clarify) |
166 apply (rule DiffI, best intro: Ord_in_Ord LeastI, clarify) |
167 apply (erule_tac P = "%z. x \<in> F (z) " and i = "c" in less_LeastE) |
167 apply (erule_tac P = "%z. x \<in> F (z) " and i = c in less_LeastE) |
168 apply (blast intro: Ord_Least ltI) |
168 apply (blast intro: Ord_Least ltI) |
169 done |
169 done |
170 |
170 |
171 lemma lepoll_imp_eqpoll_subset: |
171 lemma lepoll_imp_eqpoll_subset: |
172 "a \<lesssim> X ==> \<exists>Y. Y \<subseteq> X & a \<approx> Y" |
172 "a \<lesssim> X ==> \<exists>Y. Y \<subseteq> X & a \<approx> Y" |