25 val Sigma_fun_space_not0 = result(); |
25 val Sigma_fun_space_not0 = result(); |
26 |
26 |
27 goal thy "!!A C. (ALL B:A. B eqpoll C) ==> (ALL B1:A. ALL B2:A. B1 eqpoll B2)"; |
27 goal thy "!!A C. (ALL B:A. B eqpoll C) ==> (ALL B1:A. ALL B2:A. B1 eqpoll B2)"; |
28 by (REPEAT (resolve_tac [ballI] 1)); |
28 by (REPEAT (resolve_tac [ballI] 1)); |
29 by (resolve_tac [bspec RS (bspec RSN (2, eqpoll_sym RSN (2, eqpoll_trans)))] 1 |
29 by (resolve_tac [bspec RS (bspec RSN (2, eqpoll_sym RSN (2, eqpoll_trans)))] 1 |
30 THEN REPEAT (atac 1)); |
30 THEN REPEAT (assume_tac 1)); |
31 val all_eqpoll_imp_pair_eqpoll = result(); |
31 val all_eqpoll_imp_pair_eqpoll = result(); |
32 |
32 |
33 goal thy "!!A. [| ALL a:A. if(a=b, P(a), Q(a)) = if(a=b, R(a), S(a)); b:A \ |
33 goal thy "!!A. [| ALL a:A. if(a=b, P(a), Q(a)) = if(a=b, R(a), S(a)); b:A \ |
34 \ |] ==> P(b)=R(b)"; |
34 \ |] ==> P(b)=R(b)"; |
35 by (dresolve_tac [bspec] 1 THEN (atac 1)); |
35 by (dresolve_tac [bspec] 1 THEN (assume_tac 1)); |
36 by (asm_full_simp_tac ZF_ss 1); |
36 by (asm_full_simp_tac ZF_ss 1); |
37 val if_eqE1 = result(); |
37 val if_eqE1 = result(); |
38 |
38 |
39 goal thy "!!A. ALL a:A. if(a=b, P(a), Q(a)) = if(a=b, R(a), S(a)) \ |
39 goal thy "!!A. ALL a:A. if(a=b, P(a), Q(a)) = if(a=b, R(a), S(a)) \ |
40 \ ==> ALL a:A. a~=b --> Q(a)=S(a)"; |
40 \ ==> ALL a:A. a~=b --> Q(a)=S(a)"; |
41 by (resolve_tac [ballI] 1); |
41 by (resolve_tac [ballI] 1); |
42 by (resolve_tac [impI] 1); |
42 by (resolve_tac [impI] 1); |
43 by (dresolve_tac [bspec] 1 THEN (atac 1)); |
43 by (dresolve_tac [bspec] 1 THEN (assume_tac 1)); |
44 by (asm_full_simp_tac ZF_ss 1); |
44 by (asm_full_simp_tac ZF_ss 1); |
45 val if_eqE2 = result(); |
45 val if_eqE2 = result(); |
46 |
46 |
47 goal thy "!!A. [| (lam x:A. f(x))=(lam x:A. g(x)); a:A |] ==> f(a)=g(a)"; |
47 goal thy "!!A. [| (lam x:A. f(x))=(lam x:A. g(x)); a:A |] ==> f(a)=g(a)"; |
48 by (fast_tac (ZF_cs addDs [subsetD] |
48 by (fast_tac (ZF_cs addDs [subsetD] |
63 by (REPEAT (hyp_subst_tac 1)); |
63 by (REPEAT (hyp_subst_tac 1)); |
64 by (asm_full_simp_tac ZF_ss 1); |
64 by (asm_full_simp_tac ZF_ss 1); |
65 by (resolve_tac [conjI] 1); |
65 by (resolve_tac [conjI] 1); |
66 by (dresolve_tac [nat_0I RSN (2, lam_eqE)] 2); |
66 by (dresolve_tac [nat_0I RSN (2, lam_eqE)] 2); |
67 by (asm_full_simp_tac AC_ss 2); |
67 by (asm_full_simp_tac AC_ss 2); |
68 by (resolve_tac [fun_extension] 1 THEN REPEAT (atac 1)); |
68 by (resolve_tac [fun_extension] 1 THEN REPEAT (assume_tac 1)); |
69 by (dresolve_tac [nat_succI RSN (2, lam_eqE)] 1 THEN (atac 1)); |
69 by (dresolve_tac [nat_succI RSN (2, lam_eqE)] 1 THEN (assume_tac 1)); |
70 by (asm_full_simp_tac (AC_ss addsimps [succ_not_0 RS if_not_P]) 1); |
70 by (asm_full_simp_tac (AC_ss addsimps [succ_not_0 RS if_not_P]) 1); |
71 by (fast_tac (AC_cs addSEs [diff_succ_succ RS (diff_0 RSN (2, trans)) RS subst] |
71 by (fast_tac (AC_cs addSEs [diff_succ_succ RS (diff_0 RSN (2, trans)) RS subst] |
72 addSIs [nat_0I]) 1); |
72 addSIs [nat_0I]) 1); |
73 val lemma = result(); |
73 val lemma = result(); |
74 |
74 |
85 (* AC6 ==> AC7 *) |
85 (* AC6 ==> AC7 *) |
86 (* ********************************************************************** *) |
86 (* ********************************************************************** *) |
87 |
87 |
88 goalw thy AC_defs "!!Z. AC6 ==> AC7"; |
88 goalw thy AC_defs "!!Z. AC6 ==> AC7"; |
89 by (fast_tac ZF_cs 1); |
89 by (fast_tac ZF_cs 1); |
90 result(); |
90 qed "AC6_AC7"; |
91 |
91 |
92 (* ********************************************************************** *) |
92 (* ********************************************************************** *) |
93 (* AC7 ==> AC6, Rubin & Rubin p. 12, Theorem 2.8 *) |
93 (* AC7 ==> AC6, Rubin & Rubin p. 12, Theorem 2.8 *) |
94 (* The case of the empty family of sets added in order to complete *) |
94 (* The case of the empty family of sets added in order to complete *) |
95 (* the proof. *) |
95 (* the proof. *) |
120 by (resolve_tac [impI] 1); |
120 by (resolve_tac [impI] 1); |
121 by (excluded_middle_tac "A=0" 1); |
121 by (excluded_middle_tac "A=0" 1); |
122 by (fast_tac (ZF_cs addSIs [not_emptyI, empty_fun]) 2); |
122 by (fast_tac (ZF_cs addSIs [not_emptyI, empty_fun]) 2); |
123 by (resolve_tac [lemma1] 1); |
123 by (resolve_tac [lemma1] 1); |
124 by (eresolve_tac [allE] 1); |
124 by (eresolve_tac [allE] 1); |
125 by (eresolve_tac [impE] 1 THEN (atac 2)); |
125 by (eresolve_tac [impE] 1 THEN (assume_tac 2)); |
126 by (fast_tac (AC_cs addSEs [RepFunE] |
126 by (fast_tac (AC_cs addSEs [RepFunE] |
127 addSIs [lemma2, all_eqpoll_imp_pair_eqpoll, |
127 addSIs [lemma2, all_eqpoll_imp_pair_eqpoll, |
128 Sigma_fun_space_eqpoll]) 1); |
128 Sigma_fun_space_eqpoll]) 1); |
129 result(); |
129 qed "AC7_AC6"; |
130 |
130 |
131 |
131 |
132 (* ********************************************************************** *) |
132 (* ********************************************************************** *) |
133 (* AC1 ==> AC8 *) |
133 (* AC1 ==> AC8 *) |
134 (* ********************************************************************** *) |
134 (* ********************************************************************** *) |
136 goalw thy [eqpoll_def] |
136 goalw thy [eqpoll_def] |
137 "!!A. ALL B:A. EX B1 B2. B=<B1,B2> & B1 eqpoll B2 \ |
137 "!!A. ALL B:A. EX B1 B2. B=<B1,B2> & B1 eqpoll B2 \ |
138 \ ==> 0 ~: { bij(fst(B),snd(B)). B:A }"; |
138 \ ==> 0 ~: { bij(fst(B),snd(B)). B:A }"; |
139 by (resolve_tac [notI] 1); |
139 by (resolve_tac [notI] 1); |
140 by (eresolve_tac [RepFunE] 1); |
140 by (eresolve_tac [RepFunE] 1); |
141 by (dresolve_tac [bspec] 1 THEN (atac 1)); |
141 by (dresolve_tac [bspec] 1 THEN (assume_tac 1)); |
142 by (REPEAT (eresolve_tac [exE,conjE] 1)); |
142 by (REPEAT (eresolve_tac [exE,conjE] 1)); |
143 by (hyp_subst_tac 1); |
143 by (hyp_subst_tac 1); |
144 by (asm_full_simp_tac AC_ss 1); |
144 by (asm_full_simp_tac AC_ss 1); |
145 by (fast_tac (AC_cs addSEs [sym RS equals0D]) 1); |
145 by (fast_tac (AC_cs addSEs [sym RS equals0D]) 1); |
146 val lemma1 = result(); |
146 val lemma1 = result(); |
147 |
147 |
148 goal thy "!!A. [| f: (PROD X:RepFun(A,p). X); D:A |] \ |
148 goal thy "!!A. [| f: (PROD X:RepFun(A,p). X); D:A |] \ |
149 \ ==> (lam x:A. f`p(x))`D : p(D)"; |
149 \ ==> (lam x:A. f`p(x))`D : p(D)"; |
150 by (resolve_tac [beta RS ssubst] 1 THEN (atac 1)); |
150 by (resolve_tac [beta RS ssubst] 1 THEN (assume_tac 1)); |
151 by (fast_tac (AC_cs addSEs [apply_type]) 1); |
151 by (fast_tac (AC_cs addSEs [apply_type]) 1); |
152 val lemma2 = result(); |
152 val lemma2 = result(); |
153 |
153 |
154 goalw thy AC_defs "!!Z. AC1 ==> AC8"; |
154 goalw thy AC_defs "!!Z. AC1 ==> AC8"; |
155 by (resolve_tac [allI] 1); |
155 by (resolve_tac [allI] 1); |
156 by (eresolve_tac [allE] 1); |
156 by (eresolve_tac [allE] 1); |
157 by (resolve_tac [impI] 1); |
157 by (resolve_tac [impI] 1); |
158 by (eresolve_tac [impE] 1); |
158 by (eresolve_tac [impE] 1); |
159 by (eresolve_tac [lemma1] 1); |
159 by (eresolve_tac [lemma1] 1); |
160 by (fast_tac (AC_cs addSEs [lemma2]) 1); |
160 by (fast_tac (AC_cs addSEs [lemma2]) 1); |
161 result(); |
161 qed "AC1_AC8"; |
162 |
162 |
163 |
163 |
164 (* ********************************************************************** *) |
164 (* ********************************************************************** *) |
165 (* AC8 ==> AC9 *) |
165 (* AC8 ==> AC9 *) |
166 (* - this proof replaces the following two from Rubin & Rubin: *) |
166 (* - this proof replaces the following two from Rubin & Rubin: *) |
181 by (resolve_tac [impI] 1); |
181 by (resolve_tac [impI] 1); |
182 by (eresolve_tac [allE] 1); |
182 by (eresolve_tac [allE] 1); |
183 by (eresolve_tac [impE] 1); |
183 by (eresolve_tac [impE] 1); |
184 by (eresolve_tac [lemma1] 1); |
184 by (eresolve_tac [lemma1] 1); |
185 by (fast_tac (AC_cs addSEs [lemma2]) 1); |
185 by (fast_tac (AC_cs addSEs [lemma2]) 1); |
186 result(); |
186 qed "AC8_AC9"; |
187 |
187 |
188 |
188 |
189 (* ********************************************************************** *) |
189 (* ********************************************************************** *) |
190 (* AC9 ==> AC1 *) |
190 (* AC9 ==> AC1 *) |
191 (* The idea of this proof comes from "Equivalents of the Axiom of Choice" *) |
191 (* The idea of this proof comes from "Equivalents of the Axiom of Choice" *) |
223 by (resolve_tac [fst_type] 1); |
223 by (resolve_tac [fst_type] 1); |
224 by (resolve_tac [consI1 RSN (2, apply_type)] 1); |
224 by (resolve_tac [consI1 RSN (2, apply_type)] 1); |
225 by (fast_tac (ZF_cs addSIs [fun_weaken_type, bij_is_fun]) 1); |
225 by (fast_tac (ZF_cs addSIs [fun_weaken_type, bij_is_fun]) 1); |
226 val lemma2 = result(); |
226 val lemma2 = result(); |
227 |
227 |
228 val prems = goalw thy AC_defs "!!Z. AC9 ==> AC1"; |
228 goalw thy AC_defs "!!Z. AC9 ==> AC1"; |
229 by (resolve_tac [allI] 1); |
229 by (resolve_tac [allI] 1); |
230 by (resolve_tac [impI] 1); |
230 by (resolve_tac [impI] 1); |
231 by (eresolve_tac [allE] 1); |
231 by (eresolve_tac [allE] 1); |
232 by (excluded_middle_tac "A=0" 1); |
232 by (excluded_middle_tac "A=0" 1); |
233 by (fast_tac (FOL_cs addSIs [empty_fun]) 2); |
233 by (fast_tac (FOL_cs addSIs [empty_fun]) 2); |
234 by (eresolve_tac [impE] 1); |
234 by (eresolve_tac [impE] 1); |
235 by (resolve_tac [lemma1] 1 THEN (REPEAT (atac 1))); |
235 by (resolve_tac [lemma1] 1 THEN (REPEAT (assume_tac 1))); |
236 by (fast_tac (AC_cs addSEs [lemma2]) 1); |
236 by (fast_tac (AC_cs addSEs [lemma2]) 1); |
237 result(); |
237 qed "AC9_AC1"; |