src/ZF/AC/WO2_AC16.ML
changeset 4091 771b1f6422a8
parent 3731 71366483323b
child 4152 451104c223e2
equal deleted inserted replaced
4090:9f1eaab75e8c 4091:771b1f6422a8
   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
   172 by (hyp_subst_tac 1);
   172 by (hyp_subst_tac 1);
   173 by (rtac lepoll_lesspoll_lesspoll 1);
   173 by (rtac lepoll_lesspoll_lesspoll 1);
   174 by (eresolve_tac [lt_trans1 RSN (2, lt_Card_imp_lesspoll)] 1
   174 by (eresolve_tac [lt_trans1 RSN (2, lt_Card_imp_lesspoll)] 1
   175         THEN REPEAT (assume_tac 1));
   175         THEN REPEAT (assume_tac 1));
   176 by (rtac UN_lepoll 1
   176 by (rtac UN_lepoll 1
   177         THEN (TRYALL (fast_tac (!claset addSEs [lt_Ord]))));
   177         THEN (TRYALL (fast_tac (claset() addSEs [lt_Ord]))));
   178 qed "Union_lesspoll";
   178 qed "Union_lesspoll";
   179 
   179 
   180 (* ********************************************************************** *)
   180 (* ********************************************************************** *)
   181 (* recfunAC16_lepoll_index                                                *)
   181 (* recfunAC16_lepoll_index                                                *)
   182 (* ********************************************************************** *)
   182 (* ********************************************************************** *)
   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)))";
   230 by (eresolve_tac [lt_Ord RSN (2, Least_le) RS lt_trans1] 1
   230 by (eresolve_tac [lt_Ord RSN (2, Least_le) RS lt_trans1] 1
   231         THEN (REPEAT (assume_tac 1)));
   231         THEN (REPEAT (assume_tac 1)));
   232 qed "Least_eq_imp_ex";
   232 qed "Least_eq_imp_ex";
   233 
   233 
   234 goal thy "!!A. [| A lepoll 1; a:A; b:A |] ==> a=b";
   234 goal thy "!!A. [| A lepoll 1; a:A; b:A |] ==> a=b";
   235 by (fast_tac (!claset addSDs [lepoll_1_is_sing]) 1);
   235 by (fast_tac (claset() addSDs [lepoll_1_is_sing]) 1);
   236 qed "two_in_lepoll_1";
   236 qed "two_in_lepoll_1";
   237 
   237 
   238 goal thy "!!a. [| ALL i<a. F(i)-(UN j<i. F(j)) lepoll 1; Limit(a) |]  \
   238 goal thy "!!a. [| ALL i<a. F(i)-(UN j<i. F(j)) lepoll 1; Limit(a) |]  \
   239 \       ==> (UN x<a. F(x)) lepoll a";
   239 \       ==> (UN x<a. F(x)) lepoll a";
   240 by (resolve_tac [lepoll_def RS (def_imp_iff RS iffD2)] 1);
   240 by (resolve_tac [lepoll_def RS (def_imp_iff RS iffD2)] 1);
   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;  \
   465 \       L : X; P(j, L) & (ALL x<a. P(x, L) --> (ALL xa:F(j). ~P(x, xa))) |]  \
   465 \       L : X; P(j, L) & (ALL x<a. P(x, L) --> (ALL xa:F(j). ~P(x, xa))) |]  \
   466 \       ==> F(j) Un {L} <= X &  \
   466 \       ==> F(j) Un {L} <= X &  \
   467 \       (ALL x<a. x le j | (EX xa: (F(j) Un {L}). P(x, xa)) -->  \
   467 \       (ALL x<a. x le j | (EX xa: (F(j) Un {L}). P(x, xa)) -->  \
   468 \               (EX! Y. Y: (F(j) Un {L}) & P(x, Y)))";
   468 \               (EX! Y. Y: (F(j) Un {L}) & P(x, Y)))";
   469 by (rtac conjI 1);
   469 by (rtac conjI 1);
   470 by (fast_tac (!claset addSIs [singleton_subsetI]) 1);
   470 by (fast_tac (claset() addSIs [singleton_subsetI]) 1);
   471 by (rtac oallI 1);
   471 by (rtac oallI 1);
   472 by (etac oallE 1 THEN (contr_tac 2));
   472 by (etac oallE 1 THEN (contr_tac 2));
   473 by (rtac impI 1);
   473 by (rtac impI 1);
   474 by (etac disjE 1);
   474 by (etac disjE 1);
   475 by (etac leE 1);
   475 by (etac leE 1);
   478 by (etac ex1_in_Un_sing 1);
   478 by (etac ex1_in_Un_sing 1);
   479 by (Fast_tac 1);
   479 by (Fast_tac 1);
   480 by (Deepen_tac 2 1);
   480 by (Deepen_tac 2 1);
   481 by (etac bexE 1);
   481 by (etac bexE 1);
   482 by (etac UnE 1);
   482 by (etac UnE 1);
   483 by (fast_tac (!claset delrules [ex_ex1I] addSIs [ex1_in_Un_sing]) 1);
   483 by (fast_tac (claset() delrules [ex_ex1I] addSIs [ex1_in_Un_sing]) 1);
   484 by (Deepen_tac 2 1);
   484 by (Deepen_tac 2 1);
   485 val lemma8 = result();
   485 val lemma8 = result();
   486 
   486 
   487 (* ********************************************************************** *)
   487 (* ********************************************************************** *)
   488 (* The main part of the proof: inductive proof of the property of T_gamma *)
   488 (* The main part of the proof: inductive proof of the property of T_gamma *)
   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);