115 "!!X. [| Finite(X); ~Finite(a); Ord(a) |] ==> X lesspoll a"; |
115 "!!X. [| Finite(X); ~Finite(a); Ord(a) |] ==> X lesspoll a"; |
116 by (rtac conjI 1); |
116 by (rtac conjI 1); |
117 by (dresolve_tac [nat_le_infinite_Ord RS le_imp_lepoll] 1 |
117 by (dresolve_tac [nat_le_infinite_Ord RS le_imp_lepoll] 1 |
118 THEN (assume_tac 1)); |
118 THEN (assume_tac 1)); |
119 by (rewtac Finite_def); |
119 by (rewtac Finite_def); |
120 by (fast_tac (!claset addSEs [eqpoll_sym RS eqpoll_trans]) 2); |
120 by (fast_tac (claset() addSEs [eqpoll_sym RS eqpoll_trans]) 2); |
121 by (rtac lepoll_trans 1 THEN (assume_tac 2)); |
121 by (rtac lepoll_trans 1 THEN (assume_tac 2)); |
122 by (fast_tac (!claset addSEs [Ord_nat RSN (2, ltI) RS leI RS le_imp_subset RS |
122 by (fast_tac (claset() addSEs [Ord_nat RSN (2, ltI) RS leI RS le_imp_subset RS |
123 subset_imp_lepoll RSN (2, eqpoll_imp_lepoll RS lepoll_trans)]) 1); |
123 subset_imp_lepoll RSN (2, eqpoll_imp_lepoll RS lepoll_trans)]) 1); |
124 qed "Finite_lesspoll_infinite_Ord"; |
124 qed "Finite_lesspoll_infinite_Ord"; |
125 |
125 |
126 goal thy "!!x. x:X ==> Union(X) = Union(X-{x}) Un x"; |
126 goal thy "!!x. x:X ==> Union(X) = Union(X-{x}) Un x"; |
127 by (Fast_tac 1); |
127 by (Fast_tac 1); |
128 qed "Union_eq_Un_Diff"; |
128 qed "Union_eq_Un_Diff"; |
129 |
129 |
130 goal thy "!!n. n:nat ==> ALL X. X eqpoll n --> (ALL x:X. Finite(x)) \ |
130 goal thy "!!n. n:nat ==> ALL X. X eqpoll n --> (ALL x:X. Finite(x)) \ |
131 \ --> Finite(Union(X))"; |
131 \ --> Finite(Union(X))"; |
132 by (etac nat_induct 1); |
132 by (etac nat_induct 1); |
133 by (fast_tac (!claset addSDs [eqpoll_imp_lepoll RS lepoll_0_is_0] |
133 by (fast_tac (claset() addSDs [eqpoll_imp_lepoll RS lepoll_0_is_0] |
134 addSIs [nat_0I RS nat_into_Finite] addss (!simpset)) 1); |
134 addSIs [nat_0I RS nat_into_Finite] addss (simpset())) 1); |
135 by (REPEAT (resolve_tac [allI, impI] 1)); |
135 by (REPEAT (resolve_tac [allI, impI] 1)); |
136 by (resolve_tac [eqpoll_succ_imp_not_empty RS not_emptyE] 1 THEN (assume_tac 1)); |
136 by (resolve_tac [eqpoll_succ_imp_not_empty RS not_emptyE] 1 THEN (assume_tac 1)); |
137 by (res_inst_tac [("P","%z. Finite(z)")] (Union_eq_Un_Diff RS ssubst) 1 |
137 by (res_inst_tac [("P","%z. Finite(z)")] (Union_eq_Un_Diff RS ssubst) 1 |
138 THEN (assume_tac 1)); |
138 THEN (assume_tac 1)); |
139 by (rtac Finite_Un 1); |
139 by (rtac Finite_Un 1); |
140 by (Fast_tac 2); |
140 by (Fast_tac 2); |
141 by (fast_tac (!claset addSIs [Diff_sing_eqpoll]) 1); |
141 by (fast_tac (claset() addSIs [Diff_sing_eqpoll]) 1); |
142 qed "Finite_Union_lemma"; |
142 qed "Finite_Union_lemma"; |
143 |
143 |
144 goal thy "!!X. [| ALL x:X. Finite(x); Finite(X) |] ==> Finite(Union(X))"; |
144 goal thy "!!X. [| ALL x:X. Finite(x); Finite(X) |] ==> Finite(Union(X))"; |
145 by (eresolve_tac [Finite_def RS def_imp_iff RS iffD1 RS bexE] 1); |
145 by (eresolve_tac [Finite_def RS def_imp_iff RS iffD1 RS bexE] 1); |
146 by (dtac Finite_Union_lemma 1); |
146 by (dtac Finite_Union_lemma 1); |
147 by (Fast_tac 1); |
147 by (Fast_tac 1); |
148 qed "Finite_Union"; |
148 qed "Finite_Union"; |
149 |
149 |
150 goalw thy [Finite_def] "!!x. [| x lepoll n; n:nat |] ==> Finite(x)"; |
150 goalw thy [Finite_def] "!!x. [| x lepoll n; n:nat |] ==> Finite(x)"; |
151 by (fast_tac (!claset |
151 by (fast_tac (claset() |
152 addEs [nat_into_Ord RSN (2, lepoll_imp_ex_le_eqpoll) RS exE, |
152 addEs [nat_into_Ord RSN (2, lepoll_imp_ex_le_eqpoll) RS exE, |
153 Ord_nat RSN (2, ltI) RSN (2, lt_trans1) RS ltD]) 1); |
153 Ord_nat RSN (2, ltI) RSN (2, lt_trans1) RS ltD]) 1); |
154 qed "lepoll_nat_num_imp_Finite"; |
154 qed "lepoll_nat_num_imp_Finite"; |
155 |
155 |
156 goal thy "!!X. [| ALL x:X. x lepoll n & x <= T; well_ord(T, R); X lepoll b; \ |
156 goal thy "!!X. [| ALL x:X. x lepoll n & x <= T; well_ord(T, R); X lepoll b; \ |
157 \ b<a; ~Finite(a); Card(a); n:nat |] \ |
157 \ b<a; ~Finite(a); Card(a); n:nat |] \ |
158 \ ==> Union(X) lesspoll a"; |
158 \ ==> Union(X) lesspoll a"; |
159 by (excluded_middle_tac "Finite(X)" 1); |
159 by (excluded_middle_tac "Finite(X)" 1); |
160 by (resolve_tac [Card_is_Ord RSN (3, Finite_lesspoll_infinite_Ord)] 2 |
160 by (resolve_tac [Card_is_Ord RSN (3, Finite_lesspoll_infinite_Ord)] 2 |
161 THEN (REPEAT (assume_tac 3))); |
161 THEN (REPEAT (assume_tac 3))); |
162 by (fast_tac (!claset addSEs [lepoll_nat_num_imp_Finite] |
162 by (fast_tac (claset() addSEs [lepoll_nat_num_imp_Finite] |
163 addSIs [Finite_Union]) 2); |
163 addSIs [Finite_Union]) 2); |
164 by (dresolve_tac [lt_Ord RSN (2, lepoll_imp_ex_le_eqpoll)] 1 THEN (assume_tac 1)); |
164 by (dresolve_tac [lt_Ord RSN (2, lepoll_imp_ex_le_eqpoll)] 1 THEN (assume_tac 1)); |
165 by (REPEAT (eresolve_tac [exE, conjE] 1)); |
165 by (REPEAT (eresolve_tac [exE, conjE] 1)); |
166 by (forward_tac [eqpoll_imp_lepoll RS lepoll_infinite] 1 THEN (assume_tac 1)); |
166 by (forward_tac [eqpoll_imp_lepoll RS lepoll_infinite] 1 THEN (assume_tac 1)); |
167 by (eresolve_tac [eqpoll_sym RS (eqpoll_def RS def_imp_iff RS iffD1) RS |
167 by (eresolve_tac [eqpoll_sym RS (eqpoll_def RS def_imp_iff RS iffD1) RS |
184 goal thy "A Un {a} = cons(a, A)"; |
184 goal thy "A Un {a} = cons(a, A)"; |
185 by (Fast_tac 1); |
185 by (Fast_tac 1); |
186 qed "Un_sing_eq_cons"; |
186 qed "Un_sing_eq_cons"; |
187 |
187 |
188 goal thy "!!A. A lepoll B ==> A Un {a} lepoll succ(B)"; |
188 goal thy "!!A. A lepoll B ==> A Un {a} lepoll succ(B)"; |
189 by (asm_simp_tac (!simpset addsimps [Un_sing_eq_cons, succ_def]) 1); |
189 by (asm_simp_tac (simpset() addsimps [Un_sing_eq_cons, succ_def]) 1); |
190 by (eresolve_tac [mem_not_refl RSN (2, cons_lepoll_cong)] 1); |
190 by (eresolve_tac [mem_not_refl RSN (2, cons_lepoll_cong)] 1); |
191 qed "Un_lepoll_succ"; |
191 qed "Un_lepoll_succ"; |
192 |
192 |
193 goal thy "!!a. Ord(a) ==> F(a) - (UN b<succ(a). F(b)) = 0"; |
193 goal thy "!!a. Ord(a) ==> F(a) - (UN b<succ(a). F(b)) = 0"; |
194 by (fast_tac (!claset addSIs [OUN_I, le_refl]) 1); |
194 by (fast_tac (claset() addSIs [OUN_I, le_refl]) 1); |
195 qed "Diff_UN_succ_empty"; |
195 qed "Diff_UN_succ_empty"; |
196 |
196 |
197 goal thy "!!a. Ord(a) ==> F(a) Un X - (UN b<succ(a). F(b)) <= X"; |
197 goal thy "!!a. Ord(a) ==> F(a) Un X - (UN b<succ(a). F(b)) <= X"; |
198 by (fast_tac (!claset addSIs [OUN_I, le_refl]) 1); |
198 by (fast_tac (claset() addSIs [OUN_I, le_refl]) 1); |
199 qed "Diff_UN_succ_subset"; |
199 qed "Diff_UN_succ_subset"; |
200 |
200 |
201 goal thy "!!x. Ord(x) ==> \ |
201 goal thy "!!x. Ord(x) ==> \ |
202 \ recfunAC16(f, g, x, a) - (UN i<x. recfunAC16(f, g, i, a)) lepoll 1"; |
202 \ recfunAC16(f, g, x, a) - (UN i<x. recfunAC16(f, g, i, a)) lepoll 1"; |
203 by (etac Ord_cases 1); |
203 by (etac Ord_cases 1); |
204 by (asm_simp_tac (!simpset addsimps [recfunAC16_0, |
204 by (asm_simp_tac (simpset() addsimps [recfunAC16_0, |
205 empty_subsetI RS subset_imp_lepoll]) 1); |
205 empty_subsetI RS subset_imp_lepoll]) 1); |
206 by (asm_simp_tac (!simpset addsimps [recfunAC16_Limit, |
206 by (asm_simp_tac (simpset() addsimps [recfunAC16_Limit, |
207 Diff_cancel, empty_subsetI RS subset_imp_lepoll]) 2); |
207 Diff_cancel, empty_subsetI RS subset_imp_lepoll]) 2); |
208 by (asm_simp_tac (!simpset addsimps [recfunAC16_succ]) 1); |
208 by (asm_simp_tac (simpset() addsimps [recfunAC16_succ]) 1); |
209 by (resolve_tac [conjI RS (expand_if RS iffD2)] 1); |
209 by (resolve_tac [conjI RS (expand_if RS iffD2)] 1); |
210 by (fast_tac (!claset addSIs [empty_subsetI RS subset_imp_lepoll] |
210 by (fast_tac (claset() addSIs [empty_subsetI RS subset_imp_lepoll] |
211 addSEs [Diff_UN_succ_empty RS ssubst]) 1); |
211 addSEs [Diff_UN_succ_empty RS ssubst]) 1); |
212 by (fast_tac (!claset addSEs [Diff_UN_succ_subset RS subset_imp_lepoll RS |
212 by (fast_tac (claset() addSEs [Diff_UN_succ_subset RS subset_imp_lepoll RS |
213 (singleton_eqpoll_1 RS eqpoll_imp_lepoll RSN (2, lepoll_trans))]) 1); |
213 (singleton_eqpoll_1 RS eqpoll_imp_lepoll RSN (2, lepoll_trans))]) 1); |
214 qed "recfunAC16_Diff_lepoll_1"; |
214 qed "recfunAC16_Diff_lepoll_1"; |
215 |
215 |
216 goal thy "!!z. [| z : F(x); Ord(x) |] \ |
216 goal thy "!!z. [| z : F(x); Ord(x) |] \ |
217 \ ==> z:F(LEAST i. z:F(i)) - (UN j<(LEAST i. z:F(i)). F(j))"; |
217 \ ==> z:F(LEAST i. z:F(i)) - (UN j<(LEAST i. z:F(i)). F(j))"; |
218 by (fast_tac (!claset addEs [less_LeastE] addSEs [OUN_E, LeastI]) 1); |
218 by (fast_tac (claset() addEs [less_LeastE] addSEs [OUN_E, LeastI]) 1); |
219 qed "in_Least_Diff"; |
219 qed "in_Least_Diff"; |
220 |
220 |
221 goal thy "!!w. [| (LEAST i. w:F(i)) = (LEAST i. z:F(i)); \ |
221 goal thy "!!w. [| (LEAST i. w:F(i)) = (LEAST i. z:F(i)); \ |
222 \ w:(UN i<a. F(i)); z:(UN i<a. F(i)) |] \ |
222 \ w:(UN i<a. F(i)); z:(UN i<a. F(i)) |] \ |
223 \ ==> EX b<a. w:(F(b) - (UN c<b. F(c))) & z:(F(b) - (UN c<b. F(c)))"; |
223 \ ==> EX b<a. w:(F(b) - (UN c<b. F(c))) & z:(F(b) - (UN c<b. F(c)))"; |
249 by (rtac ballI 1); |
249 by (rtac ballI 1); |
250 by (rtac ballI 1); |
250 by (rtac ballI 1); |
251 by (Asm_simp_tac 1); |
251 by (Asm_simp_tac 1); |
252 by (rtac impI 1); |
252 by (rtac impI 1); |
253 by (dtac Least_eq_imp_ex 1 THEN (REPEAT (assume_tac 1))); |
253 by (dtac Least_eq_imp_ex 1 THEN (REPEAT (assume_tac 1))); |
254 by (fast_tac (!claset addSEs [two_in_lepoll_1]) 1); |
254 by (fast_tac (claset() addSEs [two_in_lepoll_1]) 1); |
255 qed "UN_lepoll_index"; |
255 qed "UN_lepoll_index"; |
256 |
256 |
257 goal thy "!!y. Ord(y) ==> recfunAC16(f, fa, y, a) lepoll y"; |
257 goal thy "!!y. Ord(y) ==> recfunAC16(f, fa, y, a) lepoll y"; |
258 by (etac trans_induct 1); |
258 by (etac trans_induct 1); |
259 by (etac Ord_cases 1); |
259 by (etac Ord_cases 1); |
260 by (asm_simp_tac (!simpset addsimps [recfunAC16_0, lepoll_refl]) 1); |
260 by (asm_simp_tac (simpset() addsimps [recfunAC16_0, lepoll_refl]) 1); |
261 by (asm_simp_tac (!simpset addsimps [recfunAC16_succ]) 1); |
261 by (asm_simp_tac (simpset() addsimps [recfunAC16_succ]) 1); |
262 by (fast_tac (!claset addIs [conjI RS (expand_if RS iffD2)] |
262 by (fast_tac (claset() addIs [conjI RS (expand_if RS iffD2)] |
263 addSDs [succI1 RSN (2, bspec)] |
263 addSDs [succI1 RSN (2, bspec)] |
264 addSEs [subset_succI RS subset_imp_lepoll RSN (2, lepoll_trans), |
264 addSEs [subset_succI RS subset_imp_lepoll RSN (2, lepoll_trans), |
265 Un_lepoll_succ]) 1); |
265 Un_lepoll_succ]) 1); |
266 by (asm_simp_tac (!simpset addsimps [recfunAC16_Limit]) 1); |
266 by (asm_simp_tac (simpset() addsimps [recfunAC16_Limit]) 1); |
267 by (fast_tac (!claset addSEs [lt_Ord RS recfunAC16_Diff_lepoll_1] |
267 by (fast_tac (claset() addSEs [lt_Ord RS recfunAC16_Diff_lepoll_1] |
268 addSIs [UN_lepoll_index]) 1); |
268 addSIs [UN_lepoll_index]) 1); |
269 qed "recfunAC16_lepoll_index"; |
269 qed "recfunAC16_lepoll_index"; |
270 |
270 |
271 goal thy "!!y. [| recfunAC16(f,g,y,a) <= {X: Pow(A). X eqpoll n}; \ |
271 goal thy "!!y. [| recfunAC16(f,g,y,a) <= {X: Pow(A). X eqpoll n}; \ |
272 \ A eqpoll a; y<a; ~Finite(a); Card(a); n:nat |] \ |
272 \ A eqpoll a; y<a; ~Finite(a); Card(a); n:nat |] \ |
274 by (eresolve_tac [eqpoll_def RS def_imp_iff RS iffD1 RS exE] 1); |
274 by (eresolve_tac [eqpoll_def RS def_imp_iff RS iffD1 RS exE] 1); |
275 by (rtac Union_lesspoll 1 THEN (TRYALL assume_tac)); |
275 by (rtac Union_lesspoll 1 THEN (TRYALL assume_tac)); |
276 by (eresolve_tac [lt_Ord RS recfunAC16_lepoll_index] 3); |
276 by (eresolve_tac [lt_Ord RS recfunAC16_lepoll_index] 3); |
277 by (eresolve_tac [[bij_is_inj, Card_is_Ord RS well_ord_Memrel] MRS |
277 by (eresolve_tac [[bij_is_inj, Card_is_Ord RS well_ord_Memrel] MRS |
278 well_ord_rvimage] 2 THEN (assume_tac 2)); |
278 well_ord_rvimage] 2 THEN (assume_tac 2)); |
279 by (fast_tac (!claset addSEs [eqpoll_imp_lepoll]) 1); |
279 by (fast_tac (claset() addSEs [eqpoll_imp_lepoll]) 1); |
280 qed "Union_recfunAC16_lesspoll"; |
280 qed "Union_recfunAC16_lesspoll"; |
281 |
281 |
282 goal thy |
282 goal thy |
283 "!!a. [| recfunAC16(f, fa, y, a) <= {X: Pow(A) . X eqpoll succ(k #+ m)}; \ |
283 "!!a. [| recfunAC16(f, fa, y, a) <= {X: Pow(A) . X eqpoll succ(k #+ m)}; \ |
284 \ Card(a); ~ Finite(a); A eqpoll a; \ |
284 \ Card(a); ~ Finite(a); A eqpoll a; \ |
304 |
304 |
305 goal thy "!!x. [| x : Pow(A - B - fa`i); x eqpoll m; \ |
305 goal thy "!!x. [| x : Pow(A - B - fa`i); x eqpoll m; \ |
306 \ fa : bij(a, {x: Pow(A) . x eqpoll k}); i<a; k:nat; m:nat |] \ |
306 \ fa : bij(a, {x: Pow(A) . x eqpoll k}); i<a; k:nat; m:nat |] \ |
307 \ ==> fa ` i Un x : {x: Pow(A) . x eqpoll k #+ m}"; |
307 \ ==> fa ` i Un x : {x: Pow(A) . x eqpoll k #+ m}"; |
308 by (rtac CollectI 1); |
308 by (rtac CollectI 1); |
309 by (fast_tac (!claset addSIs [PowD RS (PowD RSN (2, Un_least RS PowI))] |
309 by (fast_tac (claset() addSIs [PowD RS (PowD RSN (2, Un_least RS PowI))] |
310 addSEs [ltD RSN (2, bij_is_fun RS apply_type RS CollectE)]) 1); |
310 addSEs [ltD RSN (2, bij_is_fun RS apply_type RS CollectE)]) 1); |
311 by (rtac disj_Un_eqpoll_nat_sum 1 |
311 by (rtac disj_Un_eqpoll_nat_sum 1 |
312 THEN (TRYALL assume_tac)); |
312 THEN (TRYALL assume_tac)); |
313 by (fast_tac (!claset addSIs [equals0I]) 1); |
313 by (fast_tac (claset() addSIs [equals0I]) 1); |
314 by (eresolve_tac [ltD RSN (2, bij_is_fun RS apply_type RS CollectE)] 1 |
314 by (eresolve_tac [ltD RSN (2, bij_is_fun RS apply_type RS CollectE)] 1 |
315 THEN (REPEAT (assume_tac 1))); |
315 THEN (REPEAT (assume_tac 1))); |
316 qed "Un_in_Collect"; |
316 qed "Un_in_Collect"; |
317 |
317 |
318 (* ********************************************************************** *) |
318 (* ********************************************************************** *) |
327 THEN (REPEAT (assume_tac 1))); |
327 THEN (REPEAT (assume_tac 1))); |
328 val lemma6 = result(); |
328 val lemma6 = result(); |
329 |
329 |
330 goal thy "!!j. [| F(j)<=X; (ALL x<a. x<j | P(x,j) --> Q(x,j)); succ(j)<a |] \ |
330 goal thy "!!j. [| F(j)<=X; (ALL x<a. x<j | P(x,j) --> Q(x,j)); succ(j)<a |] \ |
331 \ ==> P(j,j) --> F(j) <= X & (ALL x<a. x le j | P(x,j) --> Q(x,j))"; |
331 \ ==> P(j,j) --> F(j) <= X & (ALL x<a. x le j | P(x,j) --> Q(x,j))"; |
332 by (fast_tac (!claset addSEs [leE]) 1); |
332 by (fast_tac (claset() addSEs [leE]) 1); |
333 val lemma7 = result(); |
333 val lemma7 = result(); |
334 |
334 |
335 (* ********************************************************************** *) |
335 (* ********************************************************************** *) |
336 (* Lemmas needded to prove ex_next_set which means that for any successor *) |
336 (* Lemmas needded to prove ex_next_set which means that for any successor *) |
337 (* ordinal there is a set satisfying certain properties *) |
337 (* ordinal there is a set satisfying certain properties *) |
343 (nat_le_infinite_Ord RSN (2, lt_trans2)) RS |
343 (nat_le_infinite_Ord RSN (2, lt_trans2)) RS |
344 leI RS le_imp_lepoll RS |
344 leI RS le_imp_lepoll RS |
345 ((eqpoll_sym RS eqpoll_imp_lepoll) RSN (2, lepoll_trans)) RS |
345 ((eqpoll_sym RS eqpoll_imp_lepoll) RSN (2, lepoll_trans)) RS |
346 lepoll_imp_eqpoll_subset RS exE] 1 |
346 lepoll_imp_eqpoll_subset RS exE] 1 |
347 THEN REPEAT (assume_tac 1)); |
347 THEN REPEAT (assume_tac 1)); |
348 by (fast_tac (!claset addSEs [eqpoll_sym]) 1); |
348 by (fast_tac (claset() addSEs [eqpoll_sym]) 1); |
349 qed "ex_subset_eqpoll"; |
349 qed "ex_subset_eqpoll"; |
350 |
350 |
351 goal thy "!!A. [| A <= B Un C; A Int C = 0 |] ==> A <= B"; |
351 goal thy "!!A. [| A <= B Un C; A Int C = 0 |] ==> A <= B"; |
352 by (fast_tac (!claset addDs [equals0D]) 1); |
352 by (fast_tac (claset() addDs [equals0D]) 1); |
353 qed "subset_Un_disjoint"; |
353 qed "subset_Un_disjoint"; |
354 |
354 |
355 goal thy "!!F. [| X:Pow(A - Union(B) -C); T:B; F<=T |] ==> F Int X = 0"; |
355 goal thy "!!F. [| X:Pow(A - Union(B) -C); T:B; F<=T |] ==> F Int X = 0"; |
356 by (fast_tac (!claset addSIs [equals0I]) 1); |
356 by (fast_tac (claset() addSIs [equals0I]) 1); |
357 qed "Int_empty"; |
357 qed "Int_empty"; |
358 |
358 |
359 (* ********************************************************************** *) |
359 (* ********************************************************************** *) |
360 (* equipollent subset (and finite) is the whole set *) |
360 (* equipollent subset (and finite) is the whole set *) |
361 (* ********************************************************************** *) |
361 (* ********************************************************************** *) |
362 |
362 |
363 goal thy "!!A. [| A <= B; a : A; A - {a} = B - {a} |] ==> A = B"; |
363 goal thy "!!A. [| A <= B; a : A; A - {a} = B - {a} |] ==> A = B"; |
364 by (fast_tac (!claset addSEs [equalityE]) 1); |
364 by (fast_tac (claset() addSEs [equalityE]) 1); |
365 qed "Diffs_eq_imp_eq"; |
365 qed "Diffs_eq_imp_eq"; |
366 |
366 |
367 goal thy "!!A. m:nat ==> ALL A B. A <= B & m lepoll A & B lepoll m --> A=B"; |
367 goal thy "!!A. m:nat ==> ALL A B. A <= B & m lepoll A & B lepoll m --> A=B"; |
368 by (etac nat_induct 1); |
368 by (etac nat_induct 1); |
369 by (fast_tac (!claset addSDs [lepoll_0_is_0]) 1); |
369 by (fast_tac (claset() addSDs [lepoll_0_is_0]) 1); |
370 by (REPEAT (resolve_tac [allI, impI] 1)); |
370 by (REPEAT (resolve_tac [allI, impI] 1)); |
371 by (REPEAT (etac conjE 1)); |
371 by (REPEAT (etac conjE 1)); |
372 by (resolve_tac [succ_lepoll_imp_not_empty RS not_emptyE] 1 |
372 by (resolve_tac [succ_lepoll_imp_not_empty RS not_emptyE] 1 |
373 THEN (assume_tac 1)); |
373 THEN (assume_tac 1)); |
374 by (forward_tac [subsetD RS Diff_sing_lepoll] 1 |
374 by (forward_tac [subsetD RS Diff_sing_lepoll] 1 |
388 |
388 |
389 goal thy "!!f. [| f:bij(a, {Y:X. Y eqpoll succ(k)}); k:nat; f`b<=f`y; b<a; \ |
389 goal thy "!!f. [| f:bij(a, {Y:X. Y eqpoll succ(k)}); k:nat; f`b<=f`y; b<a; \ |
390 \ y<a |] ==> b=y"; |
390 \ y<a |] ==> b=y"; |
391 by (dtac subset_imp_eq 1); |
391 by (dtac subset_imp_eq 1); |
392 by (etac nat_succI 3); |
392 by (etac nat_succI 3); |
393 by (fast_tac (!claset addSEs [bij_is_fun RS (ltD RSN (2, apply_type)) RS |
393 by (fast_tac (claset() addSEs [bij_is_fun RS (ltD RSN (2, apply_type)) RS |
394 CollectE, eqpoll_sym RS eqpoll_imp_lepoll]) 1); |
394 CollectE, eqpoll_sym RS eqpoll_imp_lepoll]) 1); |
395 by (fast_tac (!claset addSEs [bij_is_fun RS (ltD RSN (2, apply_type)) RS |
395 by (fast_tac (claset() addSEs [bij_is_fun RS (ltD RSN (2, apply_type)) RS |
396 CollectE, eqpoll_imp_lepoll]) 1); |
396 CollectE, eqpoll_imp_lepoll]) 1); |
397 by (rewrite_goals_tac [bij_def, inj_def]); |
397 by (rewrite_goals_tac [bij_def, inj_def]); |
398 by (fast_tac (!claset addSDs [ltD]) 1); |
398 by (fast_tac (claset() addSDs [ltD]) 1); |
399 qed "bij_imp_arg_eq"; |
399 qed "bij_imp_arg_eq"; |
400 |
400 |
401 goal thy |
401 goal thy |
402 "!!a. [| recfunAC16(f, fa, y, a) <= {X: Pow(A) . X eqpoll succ(k #+ m)}; \ |
402 "!!a. [| recfunAC16(f, fa, y, a) <= {X: Pow(A) . X eqpoll succ(k #+ m)}; \ |
403 \ Card(a); ~ Finite(a); A eqpoll a; \ |
403 \ Card(a); ~ Finite(a); A eqpoll a; \ |
498 \ (EX! Y. Y:recfunAC16(f, fa, b, a) & fa ` x <= Y))"; |
498 \ (EX! Y. Y:recfunAC16(f, fa, b, a) & fa ` x <= Y))"; |
499 by (etac lt_induct 1); |
499 by (etac lt_induct 1); |
500 by (forward_tac [lt_Ord] 1); |
500 by (forward_tac [lt_Ord] 1); |
501 by (etac Ord_cases 1); |
501 by (etac Ord_cases 1); |
502 (* case 0 *) |
502 (* case 0 *) |
503 by (asm_simp_tac (!simpset addsimps [recfunAC16_0]) 1); |
503 by (asm_simp_tac (simpset() addsimps [recfunAC16_0]) 1); |
504 (* case Limit *) |
504 (* case Limit *) |
505 by (asm_simp_tac (!simpset addsimps [recfunAC16_Limit]) 2); |
505 by (asm_simp_tac (simpset() addsimps [recfunAC16_Limit]) 2); |
506 by (rtac lemma5 2 THEN (REPEAT (assume_tac 2))); |
506 by (rtac lemma5 2 THEN (REPEAT (assume_tac 2))); |
507 by (fast_tac (FOL_cs addSEs [recfunAC16_mono]) 2); |
507 by (fast_tac (FOL_cs addSEs [recfunAC16_mono]) 2); |
508 (* case succ *) |
508 (* case succ *) |
509 by (hyp_subst_tac 1); |
509 by (hyp_subst_tac 1); |
510 by (eresolve_tac [lemma6 RS conjE] 1 THEN (assume_tac 1)); |
510 by (eresolve_tac [lemma6 RS conjE] 1 THEN (assume_tac 1)); |
511 by (asm_simp_tac (!simpset addsimps [recfunAC16_succ]) 1); |
511 by (asm_simp_tac (simpset() addsimps [recfunAC16_succ]) 1); |
512 by (resolve_tac [conjI RS (expand_if RS iffD2)] 1); |
512 by (resolve_tac [conjI RS (expand_if RS iffD2)] 1); |
513 by (etac lemma7 1 THEN (REPEAT (assume_tac 1))); |
513 by (etac lemma7 1 THEN (REPEAT (assume_tac 1))); |
514 by (rtac impI 1); |
514 by (rtac impI 1); |
515 by (resolve_tac [ex_next_Ord RS oexE] 1 |
515 by (resolve_tac [ex_next_Ord RS oexE] 1 |
516 THEN REPEAT (ares_tac [le_refl RS lt_trans] 1)); |
516 THEN REPEAT (ares_tac [le_refl RS lt_trans] 1)); |
546 by (forward_tac [prem1] 1); |
546 by (forward_tac [prem1] 1); |
547 by (etac conjE 1); |
547 by (etac conjE 1); |
548 (** LEVEL 10 **) |
548 (** LEVEL 10 **) |
549 by (dresolve_tac [leI RS succ_leE RSN (2, ospec)] 1 THEN (assume_tac 1)); |
549 by (dresolve_tac [leI RS succ_leE RSN (2, ospec)] 1 THEN (assume_tac 1)); |
550 by (etac impE 1); |
550 by (etac impE 1); |
551 by (fast_tac (!claset addSEs [leI RS succ_leE RS lt_Ord RS le_refl]) 1); |
551 by (fast_tac (claset() addSEs [leI RS succ_leE RS lt_Ord RS le_refl]) 1); |
552 by (dresolve_tac [prem2 RSN (2, apply_equality)] 1); |
552 by (dresolve_tac [prem2 RSN (2, apply_equality)] 1); |
553 by (REPEAT (eresolve_tac [conjE, ex1E] 1)); |
553 by (REPEAT (eresolve_tac [conjE, ex1E] 1)); |
554 (** LEVEL 15 **) |
554 (** LEVEL 15 **) |
555 by (rtac ex1I 1); |
555 by (rtac ex1I 1); |
556 by (fast_tac (!claset addSIs [OUN_I]) 1); |
556 by (fast_tac (claset() addSIs [OUN_I]) 1); |
557 by (REPEAT (eresolve_tac [conjE, OUN_E] 1)); |
557 by (REPEAT (eresolve_tac [conjE, OUN_E] 1)); |
558 by (eresolve_tac [lt_Ord RSN (2, lt_Ord RS Ord_linear_le)] 1 THEN (assume_tac 1)); |
558 by (eresolve_tac [lt_Ord RSN (2, lt_Ord RS Ord_linear_le)] 1 THEN (assume_tac 1)); |
559 by (dresolve_tac [prem4 RS subsetD] 2 THEN (assume_tac 2)); |
559 by (dresolve_tac [prem4 RS subsetD] 2 THEN (assume_tac 2)); |
560 (** LEVEL 20 **) |
560 (** LEVEL 20 **) |
561 by (fast_tac FOL_cs 2); |
561 by (fast_tac FOL_cs 2); |