30 (fn major::prems=> |
30 (fn major::prems=> |
31 [ (rtac (major RS allE) 1), |
31 [ (rtac (major RS allE) 1), |
32 (REPEAT (eresolve_tac (prems@[asm_rl,impCE]) 1)) ]); |
32 (REPEAT (eresolve_tac (prems@[asm_rl,impCE]) 1)) ]); |
33 |
33 |
34 (*Used in the datatype package*) |
34 (*Used in the datatype package*) |
35 qed_goal "rev_bspec" ZF.thy |
35 Goal "[| x: A; ALL x:A. P(x) |] ==> P(x)"; |
36 "!!x A P. [| x: A; ALL x:A. P(x) |] ==> P(x)" |
36 by (REPEAT (ares_tac [bspec] 1)) ; |
37 (fn _ => |
37 qed "rev_bspec"; |
38 [ REPEAT (ares_tac [bspec] 1) ]); |
|
39 |
38 |
40 (*Instantiates x first: better for automatic theorem proving?*) |
39 (*Instantiates x first: better for automatic theorem proving?*) |
41 qed_goal "rev_ballE" ZF.thy |
40 val major::prems= Goal |
42 "[| ALL x:A. P(x); x~:A ==> Q; P(x) ==> Q |] ==> Q" |
41 "[| ALL x:A. P(x); x~:A ==> Q; P(x) ==> Q |] ==> Q"; |
43 (fn major::prems=> |
42 by (rtac (major RS ballE) 1); |
44 [ (rtac (major RS ballE) 1), |
43 by (REPEAT (eresolve_tac prems 1)) ; |
45 (REPEAT (eresolve_tac prems 1)) ]); |
44 qed "rev_ballE"; |
46 |
45 |
47 AddSIs [ballI]; |
46 AddSIs [ballI]; |
48 AddEs [rev_ballE]; |
47 AddEs [rev_ballE]; |
49 AddXDs [bspec]; |
48 AddXDs [bspec]; |
50 |
49 |
51 (*Takes assumptions ALL x:A.P(x) and a:A; creates assumption P(a)*) |
50 (*Takes assumptions ALL x:A.P(x) and a:A; creates assumption P(a)*) |
52 val ball_tac = dtac bspec THEN' assume_tac; |
51 val ball_tac = dtac bspec THEN' assume_tac; |
53 |
52 |
54 (*Trival rewrite rule; (ALL x:A.P)<->P holds only if A is nonempty!*) |
53 (*Trival rewrite rule; (ALL x:A.P)<->P holds only if A is nonempty!*) |
55 qed_goal "ball_triv" ZF.thy "(ALL x:A. P) <-> ((EX x. x:A) --> P)" |
54 Goal "(ALL x:A. P) <-> ((EX x. x:A) --> P)"; |
56 (fn _=> [ simp_tac (simpset() addsimps [Ball_def]) 1 ]); |
55 by (simp_tac (simpset() addsimps [Ball_def]) 1) ; |
|
56 qed "ball_triv"; |
57 Addsimps [ball_triv]; |
57 Addsimps [ball_triv]; |
58 |
58 |
59 (*Congruence rule for rewriting*) |
59 (*Congruence rule for rewriting*) |
60 qed_goalw "ball_cong" ZF.thy [Ball_def] |
60 qed_goalw "ball_cong" ZF.thy [Ball_def] |
61 "[| A=A'; !!x. x:A' ==> P(x) <-> P'(x) |] ==> Ball(A,P) <-> Ball(A',P')" |
61 "[| A=A'; !!x. x:A' ==> P(x) <-> P'(x) |] ==> Ball(A,P) <-> Ball(A',P')" |
127 |
127 |
128 (*Takes assumptions A<=B; c:A and creates the assumption c:B *) |
128 (*Takes assumptions A<=B; c:A and creates the assumption c:B *) |
129 val set_mp_tac = dtac subsetD THEN' assume_tac; |
129 val set_mp_tac = dtac subsetD THEN' assume_tac; |
130 |
130 |
131 (*Sometimes useful with premises in this order*) |
131 (*Sometimes useful with premises in this order*) |
132 qed_goal "rev_subsetD" ZF.thy "!!A B c. [| c:A; A<=B |] ==> c:B" |
132 Goal "[| c:A; A<=B |] ==> c:B"; |
133 (fn _=> [ Blast_tac 1 ]); |
133 by (Blast_tac 1); |
|
134 qed "rev_subsetD"; |
134 |
135 |
135 (*Converts A<=B to x:A ==> x:B*) |
136 (*Converts A<=B to x:A ==> x:B*) |
136 fun impOfSubs th = th RSN (2, rev_subsetD); |
137 fun impOfSubs th = th RSN (2, rev_subsetD); |
137 |
138 |
138 qed_goal "contra_subsetD" ZF.thy "!!c. [| A <= B; c ~: B |] ==> c ~: A" |
139 Goal "[| A <= B; c ~: B |] ==> c ~: A"; |
139 (fn _=> [ Blast_tac 1 ]); |
140 by (Blast_tac 1); |
140 |
141 qed "contra_subsetD"; |
141 qed_goal "rev_contra_subsetD" ZF.thy "!!c. [| c ~: B; A <= B |] ==> c ~: A" |
142 |
142 (fn _=> [ Blast_tac 1 ]); |
143 Goal "[| c ~: B; A <= B |] ==> c ~: A"; |
143 |
144 by (Blast_tac 1); |
144 qed_goal "subset_refl" ZF.thy "A <= A" |
145 qed "rev_contra_subsetD"; |
145 (fn _=> [ Blast_tac 1 ]); |
146 |
|
147 Goal "A <= A"; |
|
148 by (Blast_tac 1); |
|
149 qed "subset_refl"; |
146 |
150 |
147 Addsimps [subset_refl]; |
151 Addsimps [subset_refl]; |
148 |
152 |
149 qed_goal "subset_trans" ZF.thy "!!A B C. [| A<=B; B<=C |] ==> A<=C" |
153 Goal "[| A<=B; B<=C |] ==> A<=C"; |
150 (fn _=> [ Blast_tac 1 ]); |
154 by (Blast_tac 1); |
|
155 qed "subset_trans"; |
151 |
156 |
152 (*Useful for proving A<=B by rewriting in some cases*) |
157 (*Useful for proving A<=B by rewriting in some cases*) |
153 qed_goalw "subset_iff" ZF.thy [subset_def,Ball_def] |
158 qed_goalw "subset_iff" ZF.thy [subset_def,Ball_def] |
154 "A<=B <-> (ALL x. x:A --> x:B)" |
159 "A<=B <-> (ALL x. x:A --> x:B)" |
155 (fn _=> [ (rtac iff_refl 1) ]); |
160 (fn _=> [ (rtac iff_refl 1) ]); |
156 |
161 |
157 |
162 |
158 (*** Rules for equality ***) |
163 (*** Rules for equality ***) |
159 |
164 |
160 (*Anti-symmetry of the subset relation*) |
165 (*Anti-symmetry of the subset relation*) |
161 qed_goal "equalityI" ZF.thy "[| A <= B; B <= A |] ==> A = B" |
166 Goal "[| A <= B; B <= A |] ==> A = B"; |
162 (fn prems=> [ (REPEAT (resolve_tac (prems@[conjI, extension RS iffD2]) 1)) ]); |
167 by (REPEAT (ares_tac [conjI, extension RS iffD2] 1)) ; |
|
168 qed "equalityI"; |
163 |
169 |
164 AddIs [equalityI]; |
170 AddIs [equalityI]; |
165 |
171 |
166 qed_goal "equality_iffI" ZF.thy "(!!x. x:A <-> x:B) ==> A = B" |
172 val [prem] = Goal "(!!x. x:A <-> x:B) ==> A = B"; |
167 (fn [prem] => |
173 by (rtac equalityI 1); |
168 [ (rtac equalityI 1), |
174 by (REPEAT (ares_tac [subsetI, prem RS iffD1, prem RS iffD2] 1)) ; |
169 (REPEAT (ares_tac [subsetI, prem RS iffD1, prem RS iffD2] 1)) ]); |
175 qed "equality_iffI"; |
170 |
176 |
171 bind_thm ("equalityD1", extension RS iffD1 RS conjunct1); |
177 bind_thm ("equalityD1", extension RS iffD1 RS conjunct1); |
172 bind_thm ("equalityD2", extension RS iffD1 RS conjunct2); |
178 bind_thm ("equalityD2", extension RS iffD1 RS conjunct2); |
173 |
179 |
174 qed_goal "equalityE" ZF.thy |
180 val prems = Goal "[| A = B; [| A<=B; B<=A |] ==> P |] ==> P"; |
175 "[| A = B; [| A<=B; B<=A |] ==> P |] ==> P" |
181 by (DEPTH_SOLVE (resolve_tac (prems@[equalityD1,equalityD2]) 1)) ; |
176 (fn prems=> |
182 qed "equalityE"; |
177 [ (DEPTH_SOLVE (resolve_tac (prems@[equalityD1,equalityD2]) 1)) ]); |
183 |
178 |
184 val major::prems= Goal |
179 qed_goal "equalityCE" ZF.thy |
185 "[| A = B; [| c:A; c:B |] ==> P; [| c~:A; c~:B |] ==> P |] ==> P"; |
180 "[| A = B; [| c:A; c:B |] ==> P; [| c~:A; c~:B |] ==> P |] ==> P" |
186 by (rtac (major RS equalityE) 1); |
181 (fn major::prems=> |
187 by (REPEAT (contr_tac 1 ORELSE eresolve_tac ([asm_rl,subsetCE]@prems) 1)) ; |
182 [ (rtac (major RS equalityE) 1), |
188 qed "equalityCE"; |
183 (REPEAT (contr_tac 1 ORELSE eresolve_tac ([asm_rl,subsetCE]@prems) 1)) ]); |
|
184 |
189 |
185 (*Lemma for creating induction formulae -- for "pattern matching" on p |
190 (*Lemma for creating induction formulae -- for "pattern matching" on p |
186 To make the induction hypotheses usable, apply "spec" or "bspec" to |
191 To make the induction hypotheses usable, apply "spec" or "bspec" to |
187 put universal quantifiers over the free variables in p. |
192 put universal quantifiers over the free variables in p. |
188 Would it be better to do subgoal_tac "ALL z. p = f(z) --> R(z)" ??*) |
193 Would it be better to do subgoal_tac "ALL z. p = f(z) --> R(z)" ??*) |
189 qed_goal "setup_induction" ZF.thy |
194 val prems = Goal "[| p: A; !!z. z: A ==> p=z --> R |] ==> R"; |
190 "[| p: A; !!z. z: A ==> p=z --> R |] ==> R" |
195 by (rtac mp 1); |
191 (fn prems=> |
196 by (REPEAT (resolve_tac (refl::prems) 1)) ; |
192 [ (rtac mp 1), |
197 qed "setup_induction"; |
193 (REPEAT (resolve_tac (refl::prems) 1)) ]); |
|
194 |
198 |
195 |
199 |
196 (*** Rules for Replace -- the derived form of replacement ***) |
200 (*** Rules for Replace -- the derived form of replacement ***) |
197 |
201 |
198 qed_goalw "Replace_iff" ZF.thy [Replace_def] |
202 qed_goalw "Replace_iff" ZF.thy [Replace_def] |
201 [ (rtac (replacement RS iff_trans) 1), |
205 [ (rtac (replacement RS iff_trans) 1), |
202 (REPEAT (ares_tac [refl,bex_cong,iffI,ballI,allI,conjI,impI,ex1I] 1 |
206 (REPEAT (ares_tac [refl,bex_cong,iffI,ballI,allI,conjI,impI,ex1I] 1 |
203 ORELSE eresolve_tac [conjE, spec RS mp, ex1_functional] 1)) ]); |
207 ORELSE eresolve_tac [conjE, spec RS mp, ex1_functional] 1)) ]); |
204 |
208 |
205 (*Introduction; there must be a unique y such that P(x,y), namely y=b. *) |
209 (*Introduction; there must be a unique y such that P(x,y), namely y=b. *) |
206 qed_goal "ReplaceI" ZF.thy |
210 val prems = Goal |
207 "[| P(x,b); x: A; !!y. P(x,y) ==> y=b |] ==> \ |
211 "[| P(x,b); x: A; !!y. P(x,y) ==> y=b |] ==> \ |
208 \ b : {y. x:A, P(x,y)}" |
212 \ b : {y. x:A, P(x,y)}"; |
209 (fn prems=> |
213 by (rtac (Replace_iff RS iffD2) 1); |
210 [ (rtac (Replace_iff RS iffD2) 1), |
214 by (REPEAT (ares_tac (prems@[bexI,conjI,allI,impI]) 1)) ; |
211 (REPEAT (ares_tac (prems@[bexI,conjI,allI,impI]) 1)) ]); |
215 qed "ReplaceI"; |
212 |
216 |
213 (*Elimination; may asssume there is a unique y such that P(x,y), namely y=b. *) |
217 (*Elimination; may asssume there is a unique y such that P(x,y), namely y=b. *) |
214 qed_goal "ReplaceE" ZF.thy |
218 val prems = Goal |
215 "[| b : {y. x:A, P(x,y)}; \ |
219 "[| b : {y. x:A, P(x,y)}; \ |
216 \ !!x. [| x: A; P(x,b); ALL y. P(x,y)-->y=b |] ==> R \ |
220 \ !!x. [| x: A; P(x,b); ALL y. P(x,y)-->y=b |] ==> R \ |
217 \ |] ==> R" |
221 \ |] ==> R"; |
218 (fn prems=> |
222 by (rtac (Replace_iff RS iffD1 RS bexE) 1); |
219 [ (rtac (Replace_iff RS iffD1 RS bexE) 1), |
223 by (etac conjE 2); |
220 (etac conjE 2), |
224 by (REPEAT (ares_tac prems 1)) ; |
221 (REPEAT (ares_tac prems 1)) ]); |
225 qed "ReplaceE"; |
222 |
226 |
223 (*As above but without the (generally useless) 3rd assumption*) |
227 (*As above but without the (generally useless) 3rd assumption*) |
224 qed_goal "ReplaceE2" ZF.thy |
228 val major::prems = Goal |
225 "[| b : {y. x:A, P(x,y)}; \ |
229 "[| b : {y. x:A, P(x,y)}; \ |
226 \ !!x. [| x: A; P(x,b) |] ==> R \ |
230 \ !!x. [| x: A; P(x,b) |] ==> R \ |
227 \ |] ==> R" |
231 \ |] ==> R"; |
228 (fn major::prems=> |
232 by (rtac (major RS ReplaceE) 1); |
229 [ (rtac (major RS ReplaceE) 1), |
233 by (REPEAT (ares_tac prems 1)) ; |
230 (REPEAT (ares_tac prems 1)) ]); |
234 qed "ReplaceE2"; |
231 |
235 |
232 AddIs [ReplaceI]; |
236 AddIs [ReplaceI]; |
233 AddSEs [ReplaceE2]; |
237 AddSEs [ReplaceE2]; |
234 |
238 |
235 qed_goal "Replace_cong" ZF.thy |
239 val prems = Goal |
236 "[| A=B; !!x y. x:B ==> P(x,y) <-> Q(x,y) |] ==> \ |
240 "[| A=B; !!x y. x:B ==> P(x,y) <-> Q(x,y) |] ==> \ |
237 \ Replace(A,P) = Replace(B,Q)" |
241 \ Replace(A,P) = Replace(B,Q)"; |
238 (fn prems=> |
242 by (rtac equalityI 1); |
239 let val substprems = prems RL [subst, ssubst] |
243 by (REPEAT |
240 and iffprems = prems RL [iffD1,iffD2] |
244 (eresolve_tac ((prems RL [subst, ssubst])@[asm_rl, ReplaceE, spec RS mp]) 1 ORELSE resolve_tac [subsetI, ReplaceI] 1 |
241 in [ (rtac equalityI 1), |
245 ORELSE (resolve_tac (prems RL [iffD1,iffD2]) 1 THEN assume_tac 2))); |
242 (REPEAT (eresolve_tac (substprems@[asm_rl, ReplaceE, spec RS mp]) 1 |
246 qed "Replace_cong"; |
243 ORELSE resolve_tac [subsetI, ReplaceI] 1 |
|
244 ORELSE (resolve_tac iffprems 1 THEN assume_tac 2))) ] |
|
245 end); |
|
246 |
247 |
247 Addcongs [Replace_cong]; |
248 Addcongs [Replace_cong]; |
248 |
249 |
249 (*** Rules for RepFun ***) |
250 (*** Rules for RepFun ***) |
250 |
251 |
251 qed_goalw "RepFunI" ZF.thy [RepFun_def] |
252 qed_goalw "RepFunI" ZF.thy [RepFun_def] |
252 "!!a A. a : A ==> f(a) : {f(x). x:A}" |
253 "!!a A. a : A ==> f(a) : {f(x). x:A}" |
253 (fn _ => [ (REPEAT (ares_tac [ReplaceI,refl] 1)) ]); |
254 (fn _ => [ (REPEAT (ares_tac [ReplaceI,refl] 1)) ]); |
254 |
255 |
255 (*Useful for coinduction proofs*) |
256 (*Useful for coinduction proofs*) |
256 qed_goal "RepFun_eqI" ZF.thy |
257 Goal "[| b=f(a); a : A |] ==> b : {f(x). x:A}"; |
257 "!!b a f. [| b=f(a); a : A |] ==> b : {f(x). x:A}" |
258 by (etac ssubst 1); |
258 (fn _ => [ etac ssubst 1, etac RepFunI 1 ]); |
259 by (etac RepFunI 1) ; |
|
260 qed "RepFun_eqI"; |
259 |
261 |
260 qed_goalw "RepFunE" ZF.thy [RepFun_def] |
262 qed_goalw "RepFunE" ZF.thy [RepFun_def] |
261 "[| b : {f(x). x:A}; \ |
263 "[| b : {f(x). x:A}; \ |
262 \ !!x.[| x:A; b=f(x) |] ==> P |] ==> \ |
264 \ !!x.[| x:A; b=f(x) |] ==> P |] ==> \ |
263 \ P" |
265 \ P" |
287 (*** Rules for Collect -- forming a subset by separation ***) |
289 (*** Rules for Collect -- forming a subset by separation ***) |
288 |
290 |
289 (*Separation is derivable from Replacement*) |
291 (*Separation is derivable from Replacement*) |
290 qed_goalw "separation" ZF.thy [Collect_def] |
292 qed_goalw "separation" ZF.thy [Collect_def] |
291 "a : {x:A. P(x)} <-> a:A & P(a)" |
293 "a : {x:A. P(x)} <-> a:A & P(a)" |
292 (fn _=> [Blast_tac 1]); |
294 (fn _=> [(Blast_tac 1)]); |
293 |
295 |
294 Addsimps [separation]; |
296 Addsimps [separation]; |
295 |
297 |
296 qed_goal "CollectI" ZF.thy |
298 Goal "[| a:A; P(a) |] ==> a : {x:A. P(x)}"; |
297 "!!P. [| a:A; P(a) |] ==> a : {x:A. P(x)}" |
299 by (Asm_simp_tac 1); |
298 (fn _=> [ Asm_simp_tac 1 ]); |
300 qed "CollectI"; |
299 |
301 |
300 qed_goal "CollectE" ZF.thy |
302 val prems = Goal |
301 "[| a : {x:A. P(x)}; [| a:A; P(a) |] ==> R |] ==> R" |
303 "[| a : {x:A. P(x)}; [| a:A; P(a) |] ==> R |] ==> R"; |
302 (fn prems=> |
304 by (rtac (separation RS iffD1 RS conjE) 1); |
303 [ (rtac (separation RS iffD1 RS conjE) 1), |
305 by (REPEAT (ares_tac prems 1)) ; |
304 (REPEAT (ares_tac prems 1)) ]); |
306 qed "CollectE"; |
305 |
307 |
306 qed_goal "CollectD1" ZF.thy "!!P. a : {x:A. P(x)} ==> a:A" |
308 Goal "a : {x:A. P(x)} ==> a:A"; |
307 (fn _=> [ (etac CollectE 1), (assume_tac 1) ]); |
309 by (etac CollectE 1); |
308 |
310 by (assume_tac 1) ; |
309 qed_goal "CollectD2" ZF.thy "!!P. a : {x:A. P(x)} ==> P(a)" |
311 qed "CollectD1"; |
310 (fn _=> [ (etac CollectE 1), (assume_tac 1) ]); |
312 |
|
313 Goal "a : {x:A. P(x)} ==> P(a)"; |
|
314 by (etac CollectE 1); |
|
315 by (assume_tac 1) ; |
|
316 qed "CollectD2"; |
311 |
317 |
312 qed_goalw "Collect_cong" ZF.thy [Collect_def] |
318 qed_goalw "Collect_cong" ZF.thy [Collect_def] |
313 "[| A=B; !!x. x:B ==> P(x) <-> Q(x) |] ==> Collect(A,P) = Collect(B,Q)" |
319 "[| A=B; !!x. x:B ==> P(x) <-> Q(x) |] ==> Collect(A,P) = Collect(B,Q)" |
314 (fn prems=> [ (simp_tac (simpset() addsimps prems) 1) ]); |
320 (fn prems=> [ (simp_tac (simpset() addsimps prems) 1) ]); |
315 |
321 |
320 (*** Rules for Unions ***) |
326 (*** Rules for Unions ***) |
321 |
327 |
322 Addsimps [Union_iff]; |
328 Addsimps [Union_iff]; |
323 |
329 |
324 (*The order of the premises presupposes that C is rigid; A may be flexible*) |
330 (*The order of the premises presupposes that C is rigid; A may be flexible*) |
325 qed_goal "UnionI" ZF.thy "!!C. [| B: C; A: B |] ==> A: Union(C)" |
331 Goal "[| B: C; A: B |] ==> A: Union(C)"; |
326 (fn _=> [ Simp_tac 1, Blast_tac 1 ]); |
332 by (Simp_tac 1); |
327 |
333 by (Blast_tac 1) ; |
328 qed_goal "UnionE" ZF.thy |
334 qed "UnionI"; |
329 "[| A : Union(C); !!B.[| A: B; B: C |] ==> R |] ==> R" |
335 |
330 (fn prems=> |
336 val prems = Goal "[| A : Union(C); !!B.[| A: B; B: C |] ==> R |] ==> R"; |
331 [ (resolve_tac [Union_iff RS iffD1 RS bexE] 1), |
337 by (resolve_tac [Union_iff RS iffD1 RS bexE] 1); |
332 (REPEAT (ares_tac prems 1)) ]); |
338 by (REPEAT (ares_tac prems 1)) ; |
|
339 qed "UnionE"; |
333 |
340 |
334 (*** Rules for Unions of families ***) |
341 (*** Rules for Unions of families ***) |
335 (* UN x:A. B(x) abbreviates Union({B(x). x:A}) *) |
342 (* UN x:A. B(x) abbreviates Union({B(x). x:A}) *) |
336 |
343 |
337 qed_goalw "UN_iff" ZF.thy [Bex_def] |
344 qed_goalw "UN_iff" ZF.thy [Bex_def] |
339 (fn _=> [ Simp_tac 1, Blast_tac 1 ]); |
346 (fn _=> [ Simp_tac 1, Blast_tac 1 ]); |
340 |
347 |
341 Addsimps [UN_iff]; |
348 Addsimps [UN_iff]; |
342 |
349 |
343 (*The order of the premises presupposes that A is rigid; b may be flexible*) |
350 (*The order of the premises presupposes that A is rigid; b may be flexible*) |
344 qed_goal "UN_I" ZF.thy "!!A B. [| a: A; b: B(a) |] ==> b: (UN x:A. B(x))" |
351 Goal "[| a: A; b: B(a) |] ==> b: (UN x:A. B(x))"; |
345 (fn _=> [ Simp_tac 1, Blast_tac 1 ]); |
352 by (Simp_tac 1); |
346 |
353 by (Blast_tac 1) ; |
347 qed_goal "UN_E" ZF.thy |
354 qed "UN_I"; |
348 "[| b : (UN x:A. B(x)); !!x.[| x: A; b: B(x) |] ==> R |] ==> R" |
355 |
349 (fn major::prems=> |
356 val major::prems= Goal |
350 [ (rtac (major RS UnionE) 1), |
357 "[| b : (UN x:A. B(x)); !!x.[| x: A; b: B(x) |] ==> R |] ==> R"; |
351 (REPEAT (eresolve_tac (prems@[asm_rl, RepFunE, subst]) 1)) ]); |
358 by (rtac (major RS UnionE) 1); |
352 |
359 by (REPEAT (eresolve_tac (prems@[asm_rl, RepFunE, subst]) 1)) ; |
353 qed_goal "UN_cong" ZF.thy |
360 qed "UN_E"; |
354 "[| A=B; !!x. x:B ==> C(x)=D(x) |] ==> (UN x:A. C(x)) = (UN x:B. D(x))" |
361 |
355 (fn prems=> [ (simp_tac (simpset() addsimps prems) 1) ]); |
362 val prems = Goal |
|
363 "[| A=B; !!x. x:B ==> C(x)=D(x) |] ==> (UN x:A. C(x)) = (UN x:B. D(x))"; |
|
364 by (simp_tac (simpset() addsimps prems) 1) ; |
|
365 qed "UN_cong"; |
356 |
366 |
357 (*No "Addcongs [UN_cong]" because UN is a combination of constants*) |
367 (*No "Addcongs [UN_cong]" because UN is a combination of constants*) |
358 |
368 |
359 (* UN_E appears before UnionE so that it is tried first, to avoid expensive |
369 (* UN_E appears before UnionE so that it is tried first, to avoid expensive |
360 calls to hyp_subst_tac. Cannot include UN_I as it is unsafe: would enlarge |
370 calls to hyp_subst_tac. Cannot include UN_I as it is unsafe: would enlarge |
370 qed_goalw "Inter_iff" ZF.thy [Inter_def,Ball_def] |
380 qed_goalw "Inter_iff" ZF.thy [Inter_def,Ball_def] |
371 "A : Inter(C) <-> (ALL x:C. A: x) & (EX x. x:C)" |
381 "A : Inter(C) <-> (ALL x:C. A: x) & (EX x. x:C)" |
372 (fn _=> [ Simp_tac 1, Blast_tac 1 ]); |
382 (fn _=> [ Simp_tac 1, Blast_tac 1 ]); |
373 |
383 |
374 (* Intersection is well-behaved only if the family is non-empty! *) |
384 (* Intersection is well-behaved only if the family is non-empty! *) |
375 qed_goal "InterI" ZF.thy |
385 val prems = Goal |
376 "[| !!x. x: C ==> A: x; EX c. c:C |] ==> A : Inter(C)" |
386 "[| !!x. x: C ==> A: x; EX c. c:C |] ==> A : Inter(C)"; |
377 (fn prems=> [ (simp_tac (simpset() addsimps [Inter_iff]) 1), |
387 by (simp_tac (simpset() addsimps [Inter_iff]) 1); |
378 blast_tac (claset() addIs prems) 1 ]); |
388 by (blast_tac (claset() addIs prems) 1) ; |
|
389 qed "InterI"; |
379 |
390 |
380 (*A "destruct" rule -- every B in C contains A as an element, but |
391 (*A "destruct" rule -- every B in C contains A as an element, but |
381 A:B can hold when B:C does not! This rule is analogous to "spec". *) |
392 A:B can hold when B:C does not! This rule is analogous to "spec". *) |
382 qed_goalw "InterD" ZF.thy [Inter_def] |
393 qed_goalw "InterD" ZF.thy [Inter_def] |
383 "!!C. [| A : Inter(C); B : C |] ==> A : B" |
394 "!!C. [| A : Inter(C); B : C |] ==> A : B" |
384 (fn _=> [ Blast_tac 1 ]); |
395 (fn _=> [(Blast_tac 1)]); |
385 |
396 |
386 (*"Classical" elimination rule -- does not require exhibiting B:C *) |
397 (*"Classical" elimination rule -- does not require exhibiting B:C *) |
387 qed_goalw "InterE" ZF.thy [Inter_def] |
398 qed_goalw "InterE" ZF.thy [Inter_def] |
388 "[| A : Inter(C); B~:C ==> R; A:B ==> R |] ==> R" |
399 "[| A : Inter(C); B~:C ==> R; A:B ==> R |] ==> R" |
389 (fn major::prems=> |
400 (fn major::prems=> |
398 |
409 |
399 qed_goalw "INT_iff" ZF.thy [Inter_def] |
410 qed_goalw "INT_iff" ZF.thy [Inter_def] |
400 "b : (INT x:A. B(x)) <-> (ALL x:A. b : B(x)) & (EX x. x:A)" |
411 "b : (INT x:A. B(x)) <-> (ALL x:A. b : B(x)) & (EX x. x:A)" |
401 (fn _=> [ Simp_tac 1, Best_tac 1 ]); |
412 (fn _=> [ Simp_tac 1, Best_tac 1 ]); |
402 |
413 |
403 qed_goal "INT_I" ZF.thy |
414 val prems = Goal |
404 "[| !!x. x: A ==> b: B(x); a: A |] ==> b: (INT x:A. B(x))" |
415 "[| !!x. x: A ==> b: B(x); a: A |] ==> b: (INT x:A. B(x))"; |
405 (fn prems=> [ blast_tac (claset() addIs prems) 1 ]); |
416 by (blast_tac (claset() addIs prems) 1); |
406 |
417 qed "INT_I"; |
407 qed_goal "INT_E" ZF.thy |
418 |
408 "[| b : (INT x:A. B(x)); a: A |] ==> b : B(a)" |
419 Goal "[| b : (INT x:A. B(x)); a: A |] ==> b : B(a)"; |
409 (fn [major,minor]=> |
420 by (Blast_tac 1); |
410 [ (rtac (major RS InterD) 1), |
421 qed "INT_E"; |
411 (rtac (minor RS RepFunI) 1) ]); |
422 |
412 |
423 val prems = Goal |
413 qed_goal "INT_cong" ZF.thy |
424 "[| A=B; !!x. x:B ==> C(x)=D(x) |] ==> (INT x:A. C(x)) = (INT x:B. D(x))"; |
414 "[| A=B; !!x. x:B ==> C(x)=D(x) |] ==> (INT x:A. C(x)) = (INT x:B. D(x))" |
425 by (simp_tac (simpset() addsimps prems) 1) ; |
415 (fn prems=> [ (simp_tac (simpset() addsimps prems) 1) ]); |
426 qed "INT_cong"; |
416 |
427 |
417 (*No "Addcongs [INT_cong]" because INT is a combination of constants*) |
428 (*No "Addcongs [INT_cong]" because INT is a combination of constants*) |
418 |
429 |
419 |
430 |
420 (*** Rules for Powersets ***) |
431 (*** Rules for Powersets ***) |
421 |
432 |
422 qed_goal "PowI" ZF.thy "A <= B ==> A : Pow(B)" |
433 Goal "A <= B ==> A : Pow(B)"; |
423 (fn [prem]=> [ (rtac (prem RS (Pow_iff RS iffD2)) 1) ]); |
434 by (etac (Pow_iff RS iffD2) 1) ; |
424 |
435 qed "PowI"; |
425 qed_goal "PowD" ZF.thy "A : Pow(B) ==> A<=B" |
436 |
426 (fn [major]=> [ (rtac (major RS (Pow_iff RS iffD1)) 1) ]); |
437 Goal "A : Pow(B) ==> A<=B"; |
|
438 by (etac (Pow_iff RS iffD1) 1) ; |
|
439 qed "PowD"; |
427 |
440 |
428 AddSIs [PowI]; |
441 AddSIs [PowI]; |
429 AddSDs [PowD]; |
442 AddSDs [PowD]; |
430 |
443 |
431 |
444 |
432 (*** Rules for the empty set ***) |
445 (*** Rules for the empty set ***) |
433 |
446 |
434 (*The set {x:0.False} is empty; by foundation it equals 0 |
447 (*The set {x:0.False} is empty; by foundation it equals 0 |
435 See Suppes, page 21.*) |
448 See Suppes, page 21.*) |
436 qed_goal "not_mem_empty" ZF.thy "a ~: 0" |
449 Goal "a ~: 0"; |
437 (fn _=> |
450 by (cut_facts_tac [foundation] 1); |
438 [ (cut_facts_tac [foundation] 1), |
451 by (best_tac (claset() addDs [equalityD2]) 1) ; |
439 (best_tac (claset() addDs [equalityD2]) 1) ]); |
452 qed "not_mem_empty"; |
440 |
453 |
441 bind_thm ("emptyE", not_mem_empty RS notE); |
454 bind_thm ("emptyE", not_mem_empty RS notE); |
442 |
455 |
443 Addsimps [not_mem_empty]; |
456 Addsimps [not_mem_empty]; |
444 AddSEs [emptyE]; |
457 AddSEs [emptyE]; |
445 |
458 |
446 qed_goal "empty_subsetI" ZF.thy "0 <= A" |
459 Goal "0 <= A"; |
447 (fn _=> [ Blast_tac 1 ]); |
460 by (Blast_tac 1); |
|
461 qed "empty_subsetI"; |
448 |
462 |
449 Addsimps [empty_subsetI]; |
463 Addsimps [empty_subsetI]; |
450 |
464 |
451 qed_goal "equals0I" ZF.thy "[| !!y. y:A ==> False |] ==> A=0" |
465 val prems = Goal "[| !!y. y:A ==> False |] ==> A=0"; |
452 (fn prems=> [ blast_tac (claset() addDs prems) 1 ]); |
466 by (blast_tac (claset() addDs prems) 1) ; |
453 |
467 qed "equals0I"; |
454 qed_goal "equals0D" ZF.thy "!!P. A=0 ==> a ~: A" |
468 |
455 (fn _=> [ Blast_tac 1 ]); |
469 Goal "A=0 ==> a ~: A"; |
|
470 by (Blast_tac 1); |
|
471 qed "equals0D"; |
456 |
472 |
457 AddDs [equals0D, sym RS equals0D]; |
473 AddDs [equals0D, sym RS equals0D]; |
458 |
474 |
459 qed_goal "not_emptyI" ZF.thy "!!A a. a:A ==> A ~= 0" |
475 Goal "a:A ==> A ~= 0"; |
460 (fn _=> [ Blast_tac 1 ]); |
476 by (Blast_tac 1); |
461 |
477 qed "not_emptyI"; |
462 qed_goal "not_emptyE" ZF.thy "[| A ~= 0; !!x. x:A ==> R |] ==> R" |
478 |
463 (fn [major,minor]=> |
479 val [major,minor]= Goal "[| A ~= 0; !!x. x:A ==> R |] ==> R"; |
464 [ rtac ([major, equals0I] MRS swap) 1, |
480 by (rtac ([major, equals0I] MRS swap) 1); |
465 swap_res_tac [minor] 1, |
481 by (swap_res_tac [minor] 1); |
466 assume_tac 1 ]); |
482 by (assume_tac 1) ; |
|
483 qed "not_emptyE"; |
467 |
484 |
468 |
485 |
469 (*** Cantor's Theorem: There is no surjection from a set to its powerset. ***) |
486 (*** Cantor's Theorem: There is no surjection from a set to its powerset. ***) |
470 |
487 |
471 val cantor_cs = FOL_cs (*precisely the rules needed for the proof*) |
488 val cantor_cs = FOL_cs (*precisely the rules needed for the proof*) |
472 addSIs [ballI, CollectI, PowI, subsetI] addIs [bexI] |
489 addSIs [ballI, CollectI, PowI, subsetI] addIs [bexI] |
473 addSEs [CollectE, equalityCE]; |
490 addSEs [CollectE, equalityCE]; |
474 |
491 |
475 (*The search is undirected; similar proof attempts may fail. |
492 (*The search is undirected; similar proof attempts may fail. |
476 b represents ANY map, such as (lam x:A.b(x)): A->Pow(A). *) |
493 b represents ANY map, such as (lam x:A.b(x)): A->Pow(A). *) |
477 qed_goal "cantor" ZF.thy "EX S: Pow(A). ALL x:A. b(x) ~= S" |
494 Goal "EX S: Pow(A). ALL x:A. b(x) ~= S"; |
478 (fn _ => [best_tac cantor_cs 1]); |
495 by (best_tac cantor_cs 1); |
|
496 qed "cantor"; |
479 |
497 |
480 (*Lemma for the inductive definition in Zorn.thy*) |
498 (*Lemma for the inductive definition in Zorn.thy*) |
481 qed_goal "Union_in_Pow" ZF.thy |
499 Goal "Y : Pow(Pow(A)) ==> Union(Y) : Pow(A)"; |
482 "!!Y. Y : Pow(Pow(A)) ==> Union(Y) : Pow(A)" |
500 by (Blast_tac 1); |
483 (fn _ => [Blast_tac 1]); |
501 qed "Union_in_Pow"; |
484 |
502 |
485 |
503 |
486 local |
504 local |
487 val (bspecT, bspec') = make_new_spec bspec |
505 val (bspecT, bspec') = make_new_spec bspec |
488 in |
506 in |