14 (* AC1 ==> AC2 *) |
14 (* AC1 ==> AC2 *) |
15 (* ********************************************************************** *) |
15 (* ********************************************************************** *) |
16 |
16 |
17 goal thy "!!B. [| B:A; f:(PROD X:A. X); 0~:A |] \ |
17 goal thy "!!B. [| B:A; f:(PROD X:A. X); 0~:A |] \ |
18 \ ==> {f`B} <= B Int {f`C. C:A}"; |
18 \ ==> {f`B} <= B Int {f`C. C:A}"; |
19 by (fast_tac (ZF_cs addSEs [apply_type]) 1); |
19 by (fast_tac (!claset addSEs [apply_type]) 1); |
20 val lemma1 = result(); |
20 val lemma1 = result(); |
21 |
21 |
22 goalw thy [pairwise_disjoint_def] |
22 goalw thy [pairwise_disjoint_def] |
23 "!!A. [| pairwise_disjoint(A); B:A; C:A; D:B; D:C |] ==> f`B = f`C"; |
23 "!!A. [| pairwise_disjoint(A); B:A; C:A; D:B; D:C |] ==> f`B = f`C"; |
24 by (fast_tac (ZF_cs addSEs [equals0D]) 1); |
24 by (fast_tac (!claset addSEs [equals0D]) 1); |
25 val lemma2 = result(); |
25 val lemma2 = result(); |
26 |
26 |
27 goalw thy AC_defs "!!Z. AC1 ==> AC2"; |
27 goalw thy AC_defs "!!Z. AC1 ==> AC2"; |
28 by (rtac allI 1); |
28 by (rtac allI 1); |
29 by (rtac impI 1); |
29 by (rtac impI 1); |
30 by (REPEAT (eresolve_tac [asm_rl,conjE,allE,exE,impE] 1)); |
30 by (REPEAT (eresolve_tac [asm_rl,conjE,allE,exE,impE] 1)); |
31 by (REPEAT (resolve_tac [exI,ballI,equalityI] 1)); |
31 by (REPEAT (resolve_tac [exI,ballI,equalityI] 1)); |
32 by (rtac lemma1 2 THEN (REPEAT (assume_tac 2))); |
32 by (rtac lemma1 2 THEN (REPEAT (assume_tac 2))); |
33 by (fast_tac (AC_cs addSEs [RepFunE, lemma2] addEs [apply_type]) 1); |
33 by (fast_tac (!claset addSEs [RepFunE, lemma2] addEs [apply_type]) 1); |
34 qed "AC1_AC2"; |
34 qed "AC1_AC2"; |
35 |
35 |
36 |
36 |
37 (* ********************************************************************** *) |
37 (* ********************************************************************** *) |
38 (* AC2 ==> AC1 *) |
38 (* AC2 ==> AC1 *) |
39 (* ********************************************************************** *) |
39 (* ********************************************************************** *) |
40 |
40 |
41 goal thy "!!A. 0~:A ==> 0 ~: {B*{B}. B:A}"; |
41 goal thy "!!A. 0~:A ==> 0 ~: {B*{B}. B:A}"; |
42 by (fast_tac (AC_cs addSDs [sym RS (Sigma_empty_iff RS iffD1)] |
42 by (fast_tac (!claset addSDs [sym RS (Sigma_empty_iff RS iffD1)] |
43 addSEs [RepFunE, equals0D]) 1); |
43 addSEs [RepFunE, equals0D]) 1); |
44 val lemma1 = result(); |
44 val lemma1 = result(); |
45 |
45 |
46 goal thy "!!A. [| X*{X} Int C = {y}; X:A |] \ |
46 goal thy "!!A. [| X*{X} Int C = {y}; X:A |] \ |
47 \ ==> (THE y. X*{X} Int C = {y}): X*A"; |
47 \ ==> (THE y. X*{X} Int C = {y}): X*A"; |
48 by (rtac subst_elem 1); |
48 by (rtac subst_elem 1); |
49 by (fast_tac (ZF_cs addSIs [the_equality] |
49 by (fast_tac (!claset addSIs [the_equality] |
50 addSEs [sym RS trans RS (singleton_eq_iff RS iffD1)]) 2); |
50 addSEs [sym RS trans RS (singleton_eq_iff RS iffD1)]) 2); |
51 by (fast_tac (AC_cs addSEs [equalityE, make_elim singleton_subsetD]) 1); |
51 by (fast_tac (!claset addSEs [equalityE, make_elim singleton_subsetD]) 1); |
52 val lemma2 = result(); |
52 val lemma2 = result(); |
53 |
53 |
54 goal thy "!!A. ALL D:{E*{E}. E:A}. EX y. D Int C = {y} \ |
54 goal thy "!!A. ALL D:{E*{E}. E:A}. EX y. D Int C = {y} \ |
55 \ ==> (lam x:A. fst(THE z. (x*{x} Int C = {z}))) : \ |
55 \ ==> (lam x:A. fst(THE z. (x*{x} Int C = {z}))) : \ |
56 \ (PROD X:A. X) "; |
56 \ (PROD X:A. X) "; |
57 by (fast_tac (FOL_cs addSEs [lemma2] |
57 by (fast_tac (!claset addSEs [lemma2] |
58 addSIs [lam_type, RepFunI, fst_type] |
58 addSIs [lam_type, RepFunI, fst_type] |
59 addSDs [bspec]) 1); |
59 addSDs [bspec]) 1); |
60 val lemma3 = result(); |
60 val lemma3 = result(); |
61 |
61 |
62 goalw thy (AC_defs@AC_aux_defs) "!!Z. AC2 ==> AC1"; |
62 goalw thy (AC_defs@AC_aux_defs) "!!Z. AC2 ==> AC1"; |
63 by (REPEAT (resolve_tac [allI, impI] 1)); |
63 by (REPEAT (resolve_tac [allI, impI] 1)); |
64 by (REPEAT (eresolve_tac [allE, impE] 1)); |
64 by (REPEAT (eresolve_tac [allE, impE] 1)); |
65 by (fast_tac (AC_cs addSEs [lemma3]) 2); |
65 by (fast_tac (!claset addSEs [lemma3]) 2); |
66 by (fast_tac (AC_cs addSIs [lemma1, equals0I]) 1); |
66 by (fast_tac (!claset addSIs [lemma1, equals0I]) 1); |
67 qed "AC2_AC1"; |
67 qed "AC2_AC1"; |
68 |
68 |
69 |
69 |
70 (* ********************************************************************** *) |
70 (* ********************************************************************** *) |
71 (* AC1 ==> AC4 *) |
71 (* AC1 ==> AC4 *) |
72 (* ********************************************************************** *) |
72 (* ********************************************************************** *) |
73 |
73 |
74 goal thy "!!R. 0 ~: {R``{x}. x:domain(R)}"; |
74 goal thy "!!R. 0 ~: {R``{x}. x:domain(R)}"; |
75 by (fast_tac (AC_cs addEs [sym RS equals0D]) 1); |
75 by (fast_tac (!claset addEs [sym RS equals0D]) 1); |
76 val lemma = result(); |
76 val lemma = result(); |
77 |
77 |
78 goalw thy AC_defs "!!Z. AC1 ==> AC4"; |
78 goalw thy AC_defs "!!Z. AC1 ==> AC4"; |
79 by (REPEAT (resolve_tac [allI, impI] 1)); |
79 by (REPEAT (resolve_tac [allI, impI] 1)); |
80 by (REPEAT (eresolve_tac [allE, lemma RSN (2, impE), exE] 1)); |
80 by (REPEAT (eresolve_tac [allE, lemma RSN (2, impE), exE] 1)); |
81 by (fast_tac (AC_cs addSIs [lam_type] addSEs [apply_type]) 1); |
81 by (fast_tac (!claset addSIs [lam_type] addSEs [apply_type]) 1); |
82 qed "AC1_AC4"; |
82 qed "AC1_AC4"; |
83 |
83 |
84 |
84 |
85 (* ********************************************************************** *) |
85 (* ********************************************************************** *) |
86 (* AC4 ==> AC3 *) |
86 (* AC4 ==> AC3 *) |
87 (* ********************************************************************** *) |
87 (* ********************************************************************** *) |
88 |
88 |
89 goal thy "!!f. f:A->B ==> (UN z:A. {z}*f`z) <= A*Union(B)"; |
89 goal thy "!!f. f:A->B ==> (UN z:A. {z}*f`z) <= A*Union(B)"; |
90 by (fast_tac (ZF_cs addSDs [apply_type]) 1); |
90 by (fast_tac (!claset addSDs [apply_type]) 1); |
91 val lemma1 = result(); |
91 val lemma1 = result(); |
92 |
92 |
93 goal thy "!!f. domain(UN z:A. {z}*f(z)) = {a:A. f(a)~=0}"; |
93 goal thy "!!f. domain(UN z:A. {z}*f(z)) = {a:A. f(a)~=0}"; |
94 by (fast_tac (ZF_cs addIs [equalityI] |
94 by (fast_tac (!claset addIs [equalityI] |
95 addSEs [not_emptyE] |
95 addSEs [not_emptyE] |
96 addSIs [not_emptyI] |
96 addSIs [not_emptyI] |
97 addDs [range_type]) 1); |
97 addDs [range_type]) 1); |
98 val lemma2 = result(); |
98 val lemma2 = result(); |
99 |
99 |
100 goal thy "!!f. x:A ==> (UN z:A. {z}*f(z))``{x} = f(x)"; |
100 goal thy "!!f. x:A ==> (UN z:A. {z}*f(z))``{x} = f(x)"; |
101 by (fast_tac (ZF_cs addIs [equalityI]) 1); |
101 by (fast_tac (!claset addIs [equalityI]) 1); |
102 val lemma3 = result(); |
102 val lemma3 = result(); |
103 |
103 |
104 goalw thy AC_defs "!!Z. AC4 ==> AC3"; |
104 goalw thy AC_defs "!!Z. AC4 ==> AC3"; |
105 by (REPEAT (resolve_tac [allI,ballI] 1)); |
105 by (REPEAT (resolve_tac [allI,ballI] 1)); |
106 by (REPEAT (eresolve_tac [allE,impE] 1)); |
106 by (REPEAT (eresolve_tac [allE,impE] 1)); |
107 by (etac lemma1 1); |
107 by (etac lemma1 1); |
108 by (asm_full_simp_tac (AC_ss addsimps [lemma2, lemma3] |
108 by (asm_full_simp_tac (!simpset addsimps [lemma2, lemma3] |
109 addcongs [Pi_cong]) 1); |
109 addcongs [Pi_cong]) 1); |
110 qed "AC4_AC3"; |
110 qed "AC4_AC3"; |
111 |
111 |
112 (* ********************************************************************** *) |
112 (* ********************************************************************** *) |
113 (* AC3 ==> AC1 *) |
113 (* AC3 ==> AC1 *) |
114 (* ********************************************************************** *) |
114 (* ********************************************************************** *) |
115 |
115 |
116 goal thy "!!A. b~:A ==> (PROD x:{a:A. id(A)`a~=b}. id(A)`x) = (PROD x:A. x)"; |
116 goal thy "!!A. b~:A ==> (PROD x:{a:A. id(A)`a~=b}. id(A)`x) = (PROD x:A. x)"; |
117 by (asm_full_simp_tac (AC_ss addsimps [id_def] addcongs [Pi_cong]) 1); |
117 by (asm_full_simp_tac (!simpset addsimps [id_def] addcongs [Pi_cong]) 1); |
118 by (res_inst_tac [("b","A")] subst_context 1); |
118 by (res_inst_tac [("b","A")] subst_context 1); |
119 by (fast_tac (AC_cs addSIs [equalityI]) 1); |
119 by (fast_tac (!claset addSIs [equalityI]) 1); |
120 val lemma = result(); |
120 val lemma = result(); |
121 |
121 |
122 goalw thy AC_defs "!!Z. AC3 ==> AC1"; |
122 goalw thy AC_defs "!!Z. AC3 ==> AC1"; |
123 by (REPEAT (resolve_tac [allI, impI] 1)); |
123 by (REPEAT (resolve_tac [allI, impI] 1)); |
124 by (REPEAT (eresolve_tac [allE, ballE] 1)); |
124 by (REPEAT (eresolve_tac [allE, ballE] 1)); |
125 by (fast_tac (AC_cs addSIs [id_type]) 2); |
125 by (fast_tac (!claset addSIs [id_type]) 2); |
126 by (fast_tac (AC_cs addEs [lemma RS subst]) 1); |
126 by (fast_tac (!claset addEs [lemma RS subst]) 1); |
127 qed "AC3_AC1"; |
127 qed "AC3_AC1"; |
128 |
128 |
129 (* ********************************************************************** *) |
129 (* ********************************************************************** *) |
130 (* AC4 ==> AC5 *) |
130 (* AC4 ==> AC5 *) |
131 (* ********************************************************************** *) |
131 (* ********************************************************************** *) |
135 by (REPEAT (eresolve_tac [allE,impE] 1)); |
135 by (REPEAT (eresolve_tac [allE,impE] 1)); |
136 by (eresolve_tac [fun_is_rel RS converse_type] 1); |
136 by (eresolve_tac [fun_is_rel RS converse_type] 1); |
137 by (etac exE 1); |
137 by (etac exE 1); |
138 by (rtac bexI 1); |
138 by (rtac bexI 1); |
139 by (rtac Pi_type 2 THEN (assume_tac 2)); |
139 by (rtac Pi_type 2 THEN (assume_tac 2)); |
140 by (fast_tac (ZF_cs addSDs [apply_type] |
140 by (fast_tac (!claset addSDs [apply_type] |
141 addSEs [fun_is_rel RS converse_type RS subsetD RS SigmaD2]) 2); |
141 addSEs [fun_is_rel RS converse_type RS subsetD RS SigmaD2]) 2); |
142 by (rtac ballI 1); |
142 by (rtac ballI 1); |
143 by (rtac apply_equality 1 THEN (assume_tac 2)); |
143 by (rtac apply_equality 1 THEN (assume_tac 2)); |
144 by (etac domainE 1); |
144 by (etac domainE 1); |
145 by (forward_tac [range_type] 1 THEN (assume_tac 1)); |
145 by (forward_tac [range_type] 1 THEN (assume_tac 1)); |
146 by (fast_tac (ZF_cs addDs [apply_equality]) 1); |
146 by (fast_tac (!claset addDs [apply_equality]) 1); |
147 qed "AC4_AC5"; |
147 qed "AC4_AC5"; |
148 |
148 |
149 |
149 |
150 (* ********************************************************************** *) |
150 (* ********************************************************************** *) |
151 (* AC5 ==> AC4, Rubin & Rubin, p. 11 *) |
151 (* AC5 ==> AC4, Rubin & Rubin, p. 11 *) |
152 (* ********************************************************************** *) |
152 (* ********************************************************************** *) |
153 |
153 |
154 goal thy "!!A. R <= A*B ==> (lam x:R. fst(x)) : R -> A"; |
154 goal thy "!!A. R <= A*B ==> (lam x:R. fst(x)) : R -> A"; |
155 by (fast_tac (ZF_cs addSIs [lam_type, fst_type]) 1); |
155 by (fast_tac (!claset addSIs [lam_type, fst_type]) 1); |
156 val lemma1 = result(); |
156 val lemma1 = result(); |
157 |
157 |
158 goalw thy [range_def] "!!A. R <= A*B ==> range(lam x:R. fst(x)) = domain(R)"; |
158 goalw thy [range_def] "!!A. R <= A*B ==> range(lam x:R. fst(x)) = domain(R)"; |
159 by (rtac equalityI 1); |
159 by (rtac equalityI 1); |
160 by (fast_tac (AC_cs addSEs [lamE] |
160 by (fast_tac (!claset addSEs [lamE] |
161 addEs [subst_elem] |
161 addEs [subst_elem] |
162 addSDs [Pair_fst_snd_eq]) 1); |
162 addSDs [Pair_fst_snd_eq]) 1); |
163 by (rtac subsetI 1); |
163 by (rtac subsetI 1); |
164 by (etac domainE 1); |
164 by (etac domainE 1); |
165 by (rtac domainI 1); |
165 by (rtac domainI 1); |
166 by (fast_tac (AC_cs addSEs [lamI RS subst_elem] addIs [fst_conv RS ssubst]) 1); |
166 by (fast_tac (!claset addSEs [lamI RS subst_elem] addIs [fst_conv RS ssubst]) 1); |
167 val lemma2 = result(); |
167 val lemma2 = result(); |
168 |
168 |
169 goal thy "!!A. [| EX f: A->C. P(f,domain(f)); A=B |] ==> EX f: B->C. P(f,B)"; |
169 goal thy "!!A. [| EX f: A->C. P(f,domain(f)); A=B |] ==> EX f: B->C. P(f,B)"; |
170 by (etac bexE 1); |
170 by (etac bexE 1); |
171 by (forward_tac [domain_of_fun] 1); |
171 by (forward_tac [domain_of_fun] 1); |
172 by (fast_tac ZF_cs 1); |
172 by (Fast_tac 1); |
173 val lemma3 = result(); |
173 val lemma3 = result(); |
174 |
174 |
175 goal thy "!!g. [| R <= A*B; g: C->R; ALL x:C. (lam z:R. fst(z))` (g`x) = x |] \ |
175 goal thy "!!g. [| R <= A*B; g: C->R; ALL x:C. (lam z:R. fst(z))` (g`x) = x |] \ |
176 \ ==> (lam x:C. snd(g`x)): (PROD x:C. R``{x})"; |
176 \ ==> (lam x:C. snd(g`x)): (PROD x:C. R``{x})"; |
177 by (rtac lam_type 1); |
177 by (rtac lam_type 1); |
178 by (dtac apply_type 1 THEN (assume_tac 1)); |
178 by (dtac apply_type 1 THEN (assume_tac 1)); |
179 by (dtac bspec 1 THEN (assume_tac 1)); |
179 by (dtac bspec 1 THEN (assume_tac 1)); |
180 by (rtac imageI 1); |
180 by (rtac imageI 1); |
181 by (resolve_tac [subsetD RS Pair_fst_snd_eq RSN (2, subst_elem)] 1 |
181 by (resolve_tac [subsetD RS Pair_fst_snd_eq RSN (2, subst_elem)] 1 |
182 THEN (REPEAT (assume_tac 1))); |
182 THEN (REPEAT (assume_tac 1))); |
183 by (asm_full_simp_tac AC_ss 1); |
183 by (Asm_full_simp_tac 1); |
184 val lemma4 = result(); |
184 val lemma4 = result(); |
185 |
185 |
186 goalw thy AC_defs "!!Z. AC5 ==> AC4"; |
186 goalw thy AC_defs "!!Z. AC5 ==> AC4"; |
187 by (REPEAT (resolve_tac [allI,impI] 1)); |
187 by (REPEAT (resolve_tac [allI,impI] 1)); |
188 by (REPEAT (eresolve_tac [allE,ballE] 1)); |
188 by (REPEAT (eresolve_tac [allE,ballE] 1)); |
189 by (eresolve_tac [lemma1 RSN (2, notE)] 2 THEN (assume_tac 2)); |
189 by (eresolve_tac [lemma1 RSN (2, notE)] 2 THEN (assume_tac 2)); |
190 by (dresolve_tac [lemma2 RSN (2, lemma3)] 1 THEN (assume_tac 1)); |
190 by (dresolve_tac [lemma2 RSN (2, lemma3)] 1 THEN (assume_tac 1)); |
191 by (fast_tac (AC_cs addSEs [lemma4]) 1); |
191 by (fast_tac (!claset addSEs [lemma4]) 1); |
192 qed "AC5_AC4"; |
192 qed "AC5_AC4"; |
193 |
193 |
194 |
194 |
195 (* ********************************************************************** *) |
195 (* ********************************************************************** *) |
196 (* AC1 <-> AC6 *) |
196 (* AC1 <-> AC6 *) |
197 (* ********************************************************************** *) |
197 (* ********************************************************************** *) |
198 |
198 |
199 goalw thy AC_defs "AC1 <-> AC6"; |
199 goalw thy AC_defs "AC1 <-> AC6"; |
200 by (fast_tac (ZF_cs addDs [equals0D] addSEs [not_emptyE]) 1); |
200 by (fast_tac (!claset addDs [equals0D] addSEs [not_emptyE]) 1); |
201 qed "AC1_iff_AC6"; |
201 qed "AC1_iff_AC6"; |
202 |
202 |