1461
|
1 |
(* Title: ZF/AC/AC16_lemmas.ML
|
1196
|
2 |
ID: $Id$
|
1461
|
3 |
Author: Krzysztof Grabczewski
|
1196
|
4 |
|
|
5 |
Lemmas used in the proofs concerning AC16
|
|
6 |
*)
|
|
7 |
|
|
8 |
open AC16_lemmas;
|
|
9 |
|
|
10 |
goal thy "!!a. a~:A ==> cons(a,A)-{a}=A";
|
2496
|
11 |
by (Fast_tac 1);
|
3731
|
12 |
qed "cons_Diff_eq";
|
1196
|
13 |
|
|
14 |
goalw thy [lepoll_def] "1 lepoll X <-> (EX x. x:X)";
|
1206
|
15 |
by (rtac iffI 1);
|
4091
|
16 |
by (fast_tac (claset() addIs [inj_is_fun RS apply_type]) 1);
|
1206
|
17 |
by (etac exE 1);
|
1196
|
18 |
by (res_inst_tac [("x","lam a:1. x")] exI 1);
|
4091
|
19 |
by (fast_tac (claset() addSIs [lam_injective]) 1);
|
3731
|
20 |
qed "nat_1_lepoll_iff";
|
1196
|
21 |
|
|
22 |
goal thy "X eqpoll 1 <-> (EX x. X={x})";
|
1206
|
23 |
by (rtac iffI 1);
|
|
24 |
by (etac eqpollE 1);
|
1196
|
25 |
by (dresolve_tac [nat_1_lepoll_iff RS iffD1] 1);
|
4091
|
26 |
by (fast_tac (claset() addSIs [lepoll_1_is_sing]) 1);
|
|
27 |
by (fast_tac (claset() addSIs [singleton_eqpoll_1]) 1);
|
3731
|
28 |
qed "eqpoll_1_iff_singleton";
|
1196
|
29 |
|
|
30 |
goalw thy [succ_def]
|
|
31 |
"!!x. [| x eqpoll n; y~:x |] ==> cons(y,x) eqpoll succ(n)";
|
4091
|
32 |
by (fast_tac (claset() addSEs [cons_eqpoll_cong, mem_irrefl]) 1);
|
3731
|
33 |
qed "cons_eqpoll_succ";
|
1196
|
34 |
|
|
35 |
goal thy "{Y:Pow(X). Y eqpoll 1} = {{x}. x:X}";
|
1206
|
36 |
by (rtac equalityI 1);
|
|
37 |
by (rtac subsetI 1);
|
|
38 |
by (etac CollectE 1);
|
1196
|
39 |
by (dresolve_tac [eqpoll_1_iff_singleton RS iffD1] 1);
|
4091
|
40 |
by (fast_tac (claset() addSIs [RepFunI]) 1);
|
1206
|
41 |
by (rtac subsetI 1);
|
|
42 |
by (etac RepFunE 1);
|
|
43 |
by (rtac CollectI 1);
|
2469
|
44 |
by (Fast_tac 1);
|
4091
|
45 |
by (fast_tac (claset() addSIs [singleton_eqpoll_1]) 1);
|
3731
|
46 |
qed "subsets_eqpoll_1_eq";
|
1196
|
47 |
|
|
48 |
goalw thy [eqpoll_def, bij_def] "X eqpoll {{x}. x:X}";
|
|
49 |
by (res_inst_tac [("x","lam x:X. {x}")] exI 1);
|
1206
|
50 |
by (rtac IntI 1);
|
1196
|
51 |
by (rewrite_goals_tac [inj_def, surj_def]);
|
2469
|
52 |
by (Asm_full_simp_tac 1);
|
4091
|
53 |
by (fast_tac (claset() addSIs [lam_type, RepFunI]
|
1461
|
54 |
addIs [singleton_eq_iff RS iffD1]) 1);
|
2469
|
55 |
by (Asm_full_simp_tac 1);
|
4091
|
56 |
by (fast_tac (claset() addSIs [lam_type]) 1);
|
3731
|
57 |
qed "eqpoll_RepFun_sing";
|
1196
|
58 |
|
|
59 |
goal thy "{Y:Pow(X). Y eqpoll 1} eqpoll X";
|
|
60 |
by (resolve_tac [subsets_eqpoll_1_eq RS ssubst] 1);
|
|
61 |
by (resolve_tac [eqpoll_RepFun_sing RS eqpoll_sym] 1);
|
3731
|
62 |
qed "subsets_eqpoll_1_eqpoll";
|
1196
|
63 |
|
|
64 |
goal thy "!!x. [| InfCard(x); y:Pow(x); y eqpoll succ(z) |] \
|
1461
|
65 |
\ ==> (LEAST i. i:y) : y";
|
1196
|
66 |
by (eresolve_tac [eqpoll_sym RS eqpoll_imp_lepoll RS
|
1461
|
67 |
succ_lepoll_imp_not_empty RS not_emptyE] 1);
|
4091
|
68 |
by (fast_tac (claset() addIs [LeastI]
|
1461
|
69 |
addSDs [InfCard_is_Card RS Card_is_Ord, PowD RS subsetD]
|
|
70 |
addEs [Ord_in_Ord]) 1);
|
3731
|
71 |
qed "InfCard_Least_in";
|
1196
|
72 |
|
|
73 |
goalw thy [lepoll_def] "!!i. [| InfCard(x); n:nat |] ==> \
|
1461
|
74 |
\ {y:Pow(x). y eqpoll succ(succ(n))} lepoll \
|
|
75 |
\ x*{y:Pow(x). y eqpoll succ(n)}";
|
1196
|
76 |
by (res_inst_tac [("x","lam y:{y:Pow(x). y eqpoll succ(succ(n))}. \
|
1461
|
77 |
\ <LEAST i. i:y, y-{LEAST i. i:y}>")] exI 1);
|
1196
|
78 |
by (res_inst_tac [("d","%z. cons(fst(z),snd(z))")] lam_injective 1);
|
1206
|
79 |
by (rtac SigmaI 1);
|
|
80 |
by (etac CollectE 1);
|
2469
|
81 |
by (Asm_full_simp_tac 3);
|
1206
|
82 |
by (rtac equalityI 3);
|
2469
|
83 |
by (Fast_tac 4);
|
1206
|
84 |
by (rtac subsetI 3);
|
|
85 |
by (etac consE 3);
|
2469
|
86 |
by (Fast_tac 4);
|
1206
|
87 |
by (rtac CollectI 2);
|
2469
|
88 |
by (Fast_tac 2);
|
1196
|
89 |
by (resolve_tac [PowD RS subsetD] 1 THEN (assume_tac 1));
|
4091
|
90 |
by (REPEAT (fast_tac (claset() addSIs [Diff_sing_eqpoll]
|
1461
|
91 |
addIs [InfCard_Least_in]) 1));
|
3731
|
92 |
qed "subsets_lepoll_lemma1";
|
1196
|
93 |
|
|
94 |
val prems = goal thy "(!!y. y:z ==> Ord(y)) ==> z <= succ(Union(z))";
|
1206
|
95 |
by (rtac subsetI 1);
|
1196
|
96 |
by (res_inst_tac [("Q","ALL y:z. y<=x")] (excluded_middle RS disjE) 1);
|
2496
|
97 |
by (Fast_tac 2);
|
1206
|
98 |
by (etac swap 1);
|
|
99 |
by (rtac ballI 1);
|
|
100 |
by (rtac Ord_linear_le 1);
|
|
101 |
by (dtac le_imp_subset 3 THEN (assume_tac 3));
|
4091
|
102 |
by (fast_tac (claset() addDs prems) 1);
|
|
103 |
by (fast_tac (claset() addDs prems) 1);
|
|
104 |
by (fast_tac (claset() addSEs [leE,ltE]) 1);
|
3731
|
105 |
qed "set_of_Ord_succ_Union";
|
1196
|
106 |
|
|
107 |
goal thy "!!i. j<=i ==> i ~: j";
|
4091
|
108 |
by (fast_tac (claset() addSEs [mem_irrefl]) 1);
|
3731
|
109 |
qed "subset_not_mem";
|
1196
|
110 |
|
|
111 |
val prems = goal thy "(!!y. y:z ==> Ord(y)) ==> succ(Union(z)) ~: z";
|
|
112 |
by (resolve_tac [set_of_Ord_succ_Union RS subset_not_mem] 1);
|
|
113 |
by (eresolve_tac prems 1);
|
3731
|
114 |
qed "succ_Union_not_mem";
|
1196
|
115 |
|
|
116 |
goal thy "Union(cons(succ(Union(z)),z)) = succ(Union(z))";
|
2496
|
117 |
by (Fast_tac 1);
|
3731
|
118 |
qed "Union_cons_eq_succ_Union";
|
1196
|
119 |
|
|
120 |
goal thy "!!i. [| Ord(i); Ord(j) |] ==> i Un j = i | i Un j = j";
|
4091
|
121 |
by (fast_tac (claset() addSDs [le_imp_subset] addEs [Ord_linear_le]) 1);
|
3731
|
122 |
qed "Un_Ord_disj";
|
1196
|
123 |
|
|
124 |
goal thy "!!X. x:X ==> Union(X) = x Un Union(X-{x})";
|
2496
|
125 |
by (Fast_tac 1);
|
3731
|
126 |
qed "Union_eq_Un";
|
1196
|
127 |
|
|
128 |
goal thy "!!n. n:nat ==> \
|
1461
|
129 |
\ ALL z. (ALL y:z. Ord(y)) & z eqpoll n & z~=0 --> Union(z) : z";
|
1206
|
130 |
by (etac nat_induct 1);
|
4091
|
131 |
by (fast_tac (claset() addSDs [eqpoll_imp_lepoll RS lepoll_0_is_0]) 1);
|
1196
|
132 |
by (REPEAT (resolve_tac [allI, impI] 1));
|
1206
|
133 |
by (etac natE 1);
|
4091
|
134 |
by (fast_tac (claset() addSDs [eqpoll_1_iff_singleton RS iffD1]
|
1461
|
135 |
addSIs [Union_singleton]) 1);
|
1196
|
136 |
by (hyp_subst_tac 1);
|
|
137 |
by (REPEAT (eresolve_tac [conjE, not_emptyE] 1));
|
|
138 |
by (eres_inst_tac [("x","z-{xb}")] allE 1);
|
1206
|
139 |
by (etac impE 1);
|
4091
|
140 |
by (fast_tac (claset() addSEs [Diff_sing_eqpoll,
|
1461
|
141 |
Diff_sing_eqpoll RS eqpoll_succ_imp_not_empty]) 1);
|
1196
|
142 |
by (resolve_tac [Union_eq_Un RSN (2, subst_elem)] 1 THEN (assume_tac 2));
|
|
143 |
by (forward_tac [bspec] 1 THEN (assume_tac 1));
|
|
144 |
by (dresolve_tac [Diff_subset RS subsetD RSN (2, bspec)] 1 THEN (assume_tac 1));
|
1206
|
145 |
by (dtac Un_Ord_disj 1 THEN (assume_tac 1));
|
|
146 |
by (etac DiffE 1);
|
|
147 |
by (etac disjE 1);
|
|
148 |
by (etac subst_elem 1 THEN (assume_tac 1));
|
|
149 |
by (rtac subst_elem 1 THEN (TRYALL assume_tac));
|
3731
|
150 |
qed "Union_in_lemma";
|
1196
|
151 |
|
|
152 |
goal thy "!!z. [| ALL x:z. Ord(x); z eqpoll n; z~=0; n:nat |] \
|
1461
|
153 |
\ ==> Union(z) : z";
|
1206
|
154 |
by (dtac Union_in_lemma 1);
|
1196
|
155 |
by (fast_tac FOL_cs 1);
|
3731
|
156 |
qed "Union_in";
|
1196
|
157 |
|
|
158 |
goal thy "!!x. [| InfCard(x); z:Pow(x); z eqpoll n; n:nat |] \
|
1461
|
159 |
\ ==> succ(Union(z)) : x";
|
1196
|
160 |
by (resolve_tac [Limit_has_succ RS ltE] 1 THEN (assume_tac 3));
|
1206
|
161 |
by (etac InfCard_is_Limit 1);
|
1196
|
162 |
by (excluded_middle_tac "z=0" 1);
|
4091
|
163 |
by (fast_tac (claset() addSIs [InfCard_is_Limit RS Limit_has_0]
|
|
164 |
addss (simpset())) 2);
|
1196
|
165 |
by (resolve_tac
|
1461
|
166 |
[PowD RS subsetD RS (InfCard_is_Card RS Card_is_Ord RSN (2, ltI))] 1
|
|
167 |
THEN (TRYALL assume_tac));
|
4091
|
168 |
by (fast_tac (claset() addSIs [Union_in]
|
2469
|
169 |
addSEs [PowD RS subsetD RSN
|
|
170 |
(2, InfCard_is_Card RS Card_is_Ord RS Ord_in_Ord)]) 1);
|
3731
|
171 |
qed "succ_Union_in_x";
|
1196
|
172 |
|
|
173 |
goalw thy [lepoll_def] "!!X. [| InfCard(x); n:nat |] ==> \
|
1461
|
174 |
\ {y:Pow(x). y eqpoll succ(n)} lepoll \
|
|
175 |
\ {y:Pow(x). y eqpoll succ(succ(n))}";
|
1196
|
176 |
by (res_inst_tac [("x","lam z:{y:Pow(x). y eqpoll succ(n)}. \
|
1461
|
177 |
\ cons(succ(Union(z)), z)")] exI 1);
|
1196
|
178 |
by (res_inst_tac [("d","%z. z-{Union(z)}")] lam_injective 1);
|
|
179 |
by (resolve_tac [Union_cons_eq_succ_Union RS ssubst] 2);
|
1206
|
180 |
by (rtac cons_Diff_eq 2);
|
4091
|
181 |
by (fast_tac (claset() addSDs [InfCard_is_Card RS Card_is_Ord]
|
1461
|
182 |
addEs [Ord_in_Ord] addSIs [succ_Union_not_mem]) 2);
|
1206
|
183 |
by (rtac CollectI 1);
|
4091
|
184 |
by (fast_tac (claset() addSEs [cons_eqpoll_succ]
|
1196
|
185 |
addSIs [succ_Union_not_mem]
|
|
186 |
addSDs [InfCard_is_Card RS Card_is_Ord]
|
|
187 |
addEs [Ord_in_Ord]) 2);
|
4091
|
188 |
by (fast_tac (claset() addSIs [succ_Union_in_x, nat_succI]) 1);
|
3731
|
189 |
qed "succ_lepoll_succ_succ";
|
1196
|
190 |
|
|
191 |
goal thy "!!X. [| InfCard(X); n:nat |] \
|
1461
|
192 |
\ ==> {Y:Pow(X). Y eqpoll succ(n)} eqpoll X";
|
1206
|
193 |
by (etac nat_induct 1);
|
|
194 |
by (rtac subsets_eqpoll_1_eqpoll 1);
|
|
195 |
by (rtac eqpollI 1);
|
1196
|
196 |
by (resolve_tac [subsets_lepoll_lemma1 RS lepoll_trans] 1
|
1461
|
197 |
THEN (REPEAT (assume_tac 1)));
|
1196
|
198 |
by (resolve_tac [InfCard_is_Card RS Card_is_Ord RS well_ord_Memrel RS
|
1461
|
199 |
well_ord_InfCard_square_eq RS eqpoll_imp_lepoll
|
|
200 |
RSN (2, lepoll_trans)] 1 THEN (assume_tac 2));
|
1196
|
201 |
by (resolve_tac [InfCard_is_Card RS Card_cardinal_eq RS ssubst] 2
|
1461
|
202 |
THEN (REPEAT (assume_tac 2)));
|
1196
|
203 |
by (eresolve_tac [eqpoll_refl RS prod_eqpoll_cong RS eqpoll_imp_lepoll] 1);
|
4091
|
204 |
by (fast_tac (claset() addEs [eqpoll_sym RS eqpoll_imp_lepoll RS lepoll_trans]
|
1461
|
205 |
addSIs [succ_lepoll_succ_succ]) 1);
|
3731
|
206 |
qed "subsets_eqpoll_X";
|
1196
|
207 |
|
|
208 |
goalw thy [surj_def] "!!f. [| f:surj(A,B); y<=B |] \
|
1461
|
209 |
\ ==> f``(converse(f)``y) = y";
|
4091
|
210 |
by (fast_tac (claset() addDs [apply_equality2]
|
2496
|
211 |
addEs [apply_iff RS iffD2]) 1);
|
3731
|
212 |
qed "image_vimage_eq";
|
1196
|
213 |
|
|
214 |
goal thy "!!f. [| f:inj(A,B); y<=A |] ==> converse(f)``(f``y) = y";
|
4091
|
215 |
by (fast_tac (claset() addSEs [inj_is_fun RS apply_Pair]
|
1461
|
216 |
addDs [inj_equality]) 1);
|
3731
|
217 |
qed "vimage_image_eq";
|
1196
|
218 |
|
|
219 |
goalw thy [eqpoll_def] "!!A B. A eqpoll B \
|
1461
|
220 |
\ ==> {Y:Pow(A). Y eqpoll n} eqpoll {Y:Pow(B). Y eqpoll n}";
|
1206
|
221 |
by (etac exE 1);
|
1196
|
222 |
by (res_inst_tac [("x","lam X:{Y:Pow(A). EX f. f : bij(Y, n)}. f``X")] exI 1);
|
|
223 |
by (res_inst_tac [("d","%Z. converse(f)``Z")] lam_bijective 1);
|
4091
|
224 |
by (fast_tac (claset()
|
1461
|
225 |
addSIs [bij_is_inj RS restrict_bij RS bij_converse_bij RS comp_bij]
|
1196
|
226 |
addSEs [bij_is_fun RS fun_is_rel RS image_subset RS PowI]) 1);
|
4091
|
227 |
by (fast_tac (claset() addSIs [bij_converse_bij RS bij_is_inj RS restrict_bij
|
1461
|
228 |
RS bij_converse_bij RS comp_bij]
|
1196
|
229 |
addSEs [bij_converse_bij RS bij_is_fun RS fun_is_rel
|
1461
|
230 |
RS image_subset RS PowI]) 1);
|
4091
|
231 |
by (fast_tac (claset() addSEs [bij_is_inj RS vimage_image_eq]) 1);
|
|
232 |
by (fast_tac (claset() addSEs [bij_is_surj RS image_vimage_eq]) 1);
|
3731
|
233 |
qed "subsets_eqpoll";
|
1196
|
234 |
|
|
235 |
goalw thy [WO2_def] "!!X. WO2 ==> EX a. Card(a) & X eqpoll a";
|
|
236 |
by (REPEAT (eresolve_tac [allE,exE,conjE] 1));
|
4091
|
237 |
by (fast_tac (claset() addSEs [well_ord_Memrel RS well_ord_cardinal_eqpoll RS
|
1461
|
238 |
(eqpoll_sym RSN (2, eqpoll_trans)) RS eqpoll_sym]
|
|
239 |
addSIs [Card_cardinal]) 1);
|
3731
|
240 |
qed "WO2_imp_ex_Card";
|
1196
|
241 |
|
|
242 |
goal thy "!!X. [| X lepoll Y; ~Finite(X) |] ==> ~Finite(Y)";
|
|
243 |
by (fast_tac (empty_cs addEs [notE, lepoll_Finite] addSIs [notI]) 1);
|
3731
|
244 |
qed "lepoll_infinite";
|
1196
|
245 |
|
|
246 |
goalw thy [InfCard_def] "!!X. [| ~Finite(X); Card(X) |] ==> InfCard(X)";
|
4091
|
247 |
by (fast_tac (claset() addSEs [Card_is_Ord RS nat_le_infinite_Ord]) 1);
|
3731
|
248 |
qed "infinite_Card_is_InfCard";
|
1196
|
249 |
|
|
250 |
goal thy "!!X n. [| WO2; n:nat; ~Finite(X) |] \
|
1461
|
251 |
\ ==> {Y:Pow(X). Y eqpoll succ(n)} eqpoll X";
|
1206
|
252 |
by (dtac WO2_imp_ex_Card 1);
|
1196
|
253 |
by (REPEAT (eresolve_tac [allE,exE,conjE] 1));
|
|
254 |
by (forward_tac [eqpoll_imp_lepoll RS lepoll_infinite] 1 THEN (assume_tac 1));
|
1206
|
255 |
by (dtac infinite_Card_is_InfCard 1 THEN (assume_tac 1));
|
1196
|
256 |
by (resolve_tac [eqpoll_trans RS eqpoll_trans] 1);
|
1206
|
257 |
by (etac subsets_eqpoll 1);
|
|
258 |
by (etac subsets_eqpoll_X 1 THEN (assume_tac 1));
|
|
259 |
by (etac eqpoll_sym 1);
|
3731
|
260 |
qed "WO2_infinite_subsets_eqpoll_X";
|
1196
|
261 |
|
|
262 |
goal thy "!!X. well_ord(X,R) ==> EX a. Card(a) & X eqpoll a";
|
4091
|
263 |
by (fast_tac (claset() addSEs [well_ord_cardinal_eqpoll RS eqpoll_sym]
|
1461
|
264 |
addSIs [Card_cardinal]) 1);
|
3731
|
265 |
qed "well_ord_imp_ex_Card";
|
1196
|
266 |
|
|
267 |
goal thy "!!X n. [| well_ord(X,R); n:nat; ~Finite(X) |] \
|
1461
|
268 |
\ ==> {Y:Pow(X). Y eqpoll succ(n)} eqpoll X";
|
1206
|
269 |
by (dtac well_ord_imp_ex_Card 1);
|
1196
|
270 |
by (REPEAT (eresolve_tac [allE,exE,conjE] 1));
|
|
271 |
by (forward_tac [eqpoll_imp_lepoll RS lepoll_infinite] 1 THEN (assume_tac 1));
|
1206
|
272 |
by (dtac infinite_Card_is_InfCard 1 THEN (assume_tac 1));
|
1196
|
273 |
by (resolve_tac [eqpoll_trans RS eqpoll_trans] 1);
|
1206
|
274 |
by (etac subsets_eqpoll 1);
|
|
275 |
by (etac subsets_eqpoll_X 1 THEN (assume_tac 1));
|
|
276 |
by (etac eqpoll_sym 1);
|
3731
|
277 |
qed "well_ord_infinite_subsets_eqpoll_X";
|
1196
|
278 |
|