author | lcp |
Thu, 24 Nov 1994 10:31:47 +0100 | |
changeset 738 | 3054a10ed5b5 |
parent 686 | be908d8d41ef |
child 760 | f0200e91b272 |
permissions | -rw-r--r-- |
0 | 1 |
(* Title: ZF/upair |
2 |
ID: $Id$ |
|
3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
4 |
Copyright 1991 University of Cambridge |
|
5 |
||
6 |
UNORDERED pairs in Zermelo-Fraenkel Set Theory |
|
7 |
||
8 |
Observe the order of dependence: |
|
9 |
Upair is defined in terms of Replace |
|
10 |
Un is defined in terms of Upair and Union (similarly for Int) |
|
11 |
cons is defined in terms of Upair and Un |
|
12 |
Ordered pairs and descriptions are defined using cons ("set notation") |
|
13 |
*) |
|
14 |
||
15 |
(*** Lemmas about power sets ***) |
|
16 |
||
17 |
val Pow_bottom = empty_subsetI RS PowI; (* 0 : Pow(B) *) |
|
18 |
val Pow_top = subset_refl RS PowI; (* A : Pow(A) *) |
|
19 |
val Pow_neq_0 = Pow_top RSN (2,equals0D); (* Pow(a)=0 ==> P *) |
|
20 |
||
21 |
||
22 |
(*** Unordered pairs - Upair ***) |
|
23 |
||
24 |
val pairing = prove_goalw ZF.thy [Upair_def] |
|
25 |
"c : Upair(a,b) <-> (c=a | c=b)" |
|
26 |
(fn _ => [ (fast_tac (lemmas_cs addEs [Pow_neq_0, sym RS Pow_neq_0]) 1) ]); |
|
27 |
||
28 |
val UpairI1 = prove_goal ZF.thy "a : Upair(a,b)" |
|
29 |
(fn _ => [ (rtac (refl RS disjI1 RS (pairing RS iffD2)) 1) ]); |
|
30 |
||
31 |
val UpairI2 = prove_goal ZF.thy "b : Upair(a,b)" |
|
32 |
(fn _ => [ (rtac (refl RS disjI2 RS (pairing RS iffD2)) 1) ]); |
|
33 |
||
34 |
val UpairE = prove_goal ZF.thy |
|
35 |
"[| a : Upair(b,c); a=b ==> P; a=c ==> P |] ==> P" |
|
36 |
(fn major::prems=> |
|
37 |
[ (rtac (major RS (pairing RS iffD1 RS disjE)) 1), |
|
38 |
(REPEAT (eresolve_tac prems 1)) ]); |
|
39 |
||
40 |
(*** Rules for binary union -- Un -- defined via Upair ***) |
|
41 |
||
42 |
val UnI1 = prove_goalw ZF.thy [Un_def] "c : A ==> c : A Un B" |
|
43 |
(fn [prem]=> [ (rtac (prem RS (UpairI1 RS UnionI)) 1) ]); |
|
44 |
||
45 |
val UnI2 = prove_goalw ZF.thy [Un_def] "c : B ==> c : A Un B" |
|
46 |
(fn [prem]=> [ (rtac (prem RS (UpairI2 RS UnionI)) 1) ]); |
|
47 |
||
48 |
val UnE = prove_goalw ZF.thy [Un_def] |
|
49 |
"[| c : A Un B; c:A ==> P; c:B ==> P |] ==> P" |
|
50 |
(fn major::prems=> |
|
51 |
[ (rtac (major RS UnionE) 1), |
|
52 |
(etac UpairE 1), |
|
53 |
(REPEAT (EVERY1 [resolve_tac prems, etac subst, assume_tac])) ]); |
|
54 |
||
572 | 55 |
(*Stronger version of the rule above*) |
56 |
val UnE' = prove_goal ZF.thy |
|
57 |
"[| c : A Un B; c:A ==> P; [| c:B; c~:A |] ==> P |] ==> P" |
|
58 |
(fn major::prems => |
|
59 |
[(rtac (major RS UnE) 1), |
|
60 |
(eresolve_tac prems 1), |
|
61 |
(rtac classical 1), |
|
62 |
(eresolve_tac prems 1), |
|
63 |
(swap_res_tac prems 1), |
|
64 |
(etac notnotD 1)]); |
|
65 |
||
0 | 66 |
val Un_iff = prove_goal ZF.thy "c : A Un B <-> (c:A | c:B)" |
67 |
(fn _ => [ (fast_tac (lemmas_cs addIs [UnI1,UnI2] addSEs [UnE]) 1) ]); |
|
68 |
||
69 |
(*Classical introduction rule: no commitment to A vs B*) |
|
37 | 70 |
val UnCI = prove_goal ZF.thy "(c ~: B ==> c : A) ==> c : A Un B" |
0 | 71 |
(fn [prem]=> |
72 |
[ (rtac (disjCI RS (Un_iff RS iffD2)) 1), |
|
73 |
(etac prem 1) ]); |
|
74 |
||
75 |
||
76 |
(*** Rules for small intersection -- Int -- defined via Upair ***) |
|
77 |
||
78 |
val IntI = prove_goalw ZF.thy [Int_def] |
|
79 |
"[| c : A; c : B |] ==> c : A Int B" |
|
80 |
(fn prems=> |
|
81 |
[ (REPEAT (resolve_tac (prems @ [UpairI1,InterI]) 1 |
|
82 |
ORELSE eresolve_tac [UpairE, ssubst] 1)) ]); |
|
83 |
||
84 |
val IntD1 = prove_goalw ZF.thy [Int_def] "c : A Int B ==> c : A" |
|
85 |
(fn [major]=> |
|
86 |
[ (rtac (UpairI1 RS (major RS InterD)) 1) ]); |
|
87 |
||
88 |
val IntD2 = prove_goalw ZF.thy [Int_def] "c : A Int B ==> c : B" |
|
89 |
(fn [major]=> |
|
90 |
[ (rtac (UpairI2 RS (major RS InterD)) 1) ]); |
|
91 |
||
92 |
val IntE = prove_goal ZF.thy |
|
93 |
"[| c : A Int B; [| c:A; c:B |] ==> P |] ==> P" |
|
94 |
(fn prems=> |
|
95 |
[ (resolve_tac prems 1), |
|
96 |
(REPEAT (resolve_tac (prems RL [IntD1,IntD2]) 1)) ]); |
|
97 |
||
98 |
val Int_iff = prove_goal ZF.thy "c : A Int B <-> (c:A & c:B)" |
|
99 |
(fn _ => [ (fast_tac (lemmas_cs addSIs [IntI] addSEs [IntE]) 1) ]); |
|
100 |
||
101 |
||
102 |
(*** Rules for set difference -- defined via Upair ***) |
|
103 |
||
104 |
val DiffI = prove_goalw ZF.thy [Diff_def] |
|
37 | 105 |
"[| c : A; c ~: B |] ==> c : A - B" |
0 | 106 |
(fn prems=> [ (REPEAT (resolve_tac (prems @ [CollectI]) 1)) ]); |
107 |
||
108 |
val DiffD1 = prove_goalw ZF.thy [Diff_def] |
|
109 |
"c : A - B ==> c : A" |
|
110 |
(fn [major]=> [ (rtac (major RS CollectD1) 1) ]); |
|
111 |
||
112 |
val DiffD2 = prove_goalw ZF.thy [Diff_def] |
|
485 | 113 |
"c : A - B ==> c ~: B" |
114 |
(fn [major]=> [ (rtac (major RS CollectD2) 1) ]); |
|
0 | 115 |
|
116 |
val DiffE = prove_goal ZF.thy |
|
37 | 117 |
"[| c : A - B; [| c:A; c~:B |] ==> P |] ==> P" |
0 | 118 |
(fn prems=> |
119 |
[ (resolve_tac prems 1), |
|
485 | 120 |
(REPEAT (ares_tac (prems RL [DiffD1, DiffD2]) 1)) ]); |
0 | 121 |
|
37 | 122 |
val Diff_iff = prove_goal ZF.thy "c : A-B <-> (c:A & c~:B)" |
0 | 123 |
(fn _ => [ (fast_tac (lemmas_cs addSIs [DiffI] addSEs [DiffE]) 1) ]); |
124 |
||
125 |
(*** Rules for cons -- defined via Un and Upair ***) |
|
126 |
||
127 |
val consI1 = prove_goalw ZF.thy [cons_def] "a : cons(a,B)" |
|
128 |
(fn _ => [ (rtac (UpairI1 RS UnI1) 1) ]); |
|
129 |
||
130 |
val consI2 = prove_goalw ZF.thy [cons_def] "a : B ==> a : cons(b,B)" |
|
131 |
(fn [prem]=> [ (rtac (prem RS UnI2) 1) ]); |
|
132 |
||
133 |
val consE = prove_goalw ZF.thy [cons_def] |
|
134 |
"[| a : cons(b,A); a=b ==> P; a:A ==> P |] ==> P" |
|
135 |
(fn major::prems=> |
|
136 |
[ (rtac (major RS UnE) 1), |
|
137 |
(REPEAT (eresolve_tac (prems @ [UpairE]) 1)) ]); |
|
138 |
||
572 | 139 |
(*Stronger version of the rule above*) |
140 |
val consE' = prove_goal ZF.thy |
|
141 |
"[| a : cons(b,A); a=b ==> P; [| a:A; a~=b |] ==> P |] ==> P" |
|
142 |
(fn major::prems => |
|
143 |
[(rtac (major RS consE) 1), |
|
144 |
(eresolve_tac prems 1), |
|
145 |
(rtac classical 1), |
|
146 |
(eresolve_tac prems 1), |
|
147 |
(swap_res_tac prems 1), |
|
148 |
(etac notnotD 1)]); |
|
149 |
||
0 | 150 |
val cons_iff = prove_goal ZF.thy "a : cons(b,A) <-> (a=b | a:A)" |
151 |
(fn _ => [ (fast_tac (lemmas_cs addIs [consI1,consI2] addSEs [consE]) 1) ]); |
|
152 |
||
153 |
(*Classical introduction rule*) |
|
37 | 154 |
val consCI = prove_goal ZF.thy "(a~:B ==> a=b) ==> a: cons(b,B)" |
0 | 155 |
(fn [prem]=> |
156 |
[ (rtac (disjCI RS (cons_iff RS iffD2)) 1), |
|
157 |
(etac prem 1) ]); |
|
158 |
||
159 |
(*** Singletons - using cons ***) |
|
160 |
||
161 |
val singletonI = prove_goal ZF.thy "a : {a}" |
|
162 |
(fn _=> [ (rtac consI1 1) ]); |
|
163 |
||
164 |
val singletonE = prove_goal ZF.thy "[| a: {b}; a=b ==> P |] ==> P" |
|
165 |
(fn major::prems=> |
|
166 |
[ (rtac (major RS consE) 1), |
|
167 |
(REPEAT (eresolve_tac (prems @ [emptyE]) 1)) ]); |
|
168 |
||
169 |
||
170 |
(*** Rules for Descriptions ***) |
|
171 |
||
172 |
val the_equality = prove_goalw ZF.thy [the_def] |
|
173 |
"[| P(a); !!x. P(x) ==> x=a |] ==> (THE x. P(x)) = a" |
|
738 | 174 |
(fn [pa,eq] => |
175 |
[ (fast_tac (lemmas_cs addSIs [singletonI,pa] addIs [equalityI] |
|
176 |
addEs [eq RS subst]) 1) ]); |
|
0 | 177 |
|
178 |
(* Only use this if you already know EX!x. P(x) *) |
|
179 |
val the_equality2 = prove_goal ZF.thy |
|
673 | 180 |
"!!P. [| EX! x. P(x); P(a) |] ==> (THE x. P(x)) = a" |
181 |
(fn _ => |
|
182 |
[ (deepen_tac (lemmas_cs addSIs [the_equality]) 1 1) ]); |
|
0 | 183 |
|
184 |
val theI = prove_goal ZF.thy "EX! x. P(x) ==> P(THE x. P(x))" |
|
185 |
(fn [major]=> |
|
186 |
[ (rtac (major RS ex1E) 1), |
|
187 |
(resolve_tac [major RS the_equality2 RS ssubst] 1), |
|
188 |
(REPEAT (assume_tac 1)) ]); |
|
189 |
||
686 | 190 |
(*Easier to apply than theI: conclusion has only one occurrence of P*) |
191 |
val theI2 = prove_goal ZF.thy |
|
192 |
"[| EX! x. P(x); !!x. P(x) ==> Q(x) |] ==> Q(THE x.P(x))" |
|
193 |
(fn prems => [ resolve_tac prems 1, |
|
194 |
rtac theI 1, |
|
195 |
resolve_tac prems 1 ]); |
|
196 |
||
435 | 197 |
(*the_cong is no longer necessary: if (ALL y.P(y)<->Q(y)) then |
198 |
(THE x.P(x)) rewrites to (THE x. Q(x)) *) |
|
199 |
||
200 |
(*If it's "undefined", it's zero!*) |
|
201 |
val the_0 = prove_goalw ZF.thy [the_def] |
|
202 |
"!!P. ~ (EX! x. P(x)) ==> (THE x. P(x))=0" |
|
203 |
(fn _ => |
|
485 | 204 |
[ (fast_tac (lemmas_cs addIs [equalityI] addSEs [ReplaceE]) 1) ]); |
435 | 205 |
|
0 | 206 |
|
207 |
(*** if -- a conditional expression for formulae ***) |
|
208 |
||
209 |
goalw ZF.thy [if_def] "if(True,a,b) = a"; |
|
210 |
by (fast_tac (lemmas_cs addIs [the_equality]) 1); |
|
211 |
val if_true = result(); |
|
212 |
||
213 |
goalw ZF.thy [if_def] "if(False,a,b) = b"; |
|
214 |
by (fast_tac (lemmas_cs addIs [the_equality]) 1); |
|
215 |
val if_false = result(); |
|
216 |
||
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
217 |
(*Never use with case splitting, or if P is known to be true or false*) |
0 | 218 |
val prems = goalw ZF.thy [if_def] |
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
219 |
"[| P<->Q; Q ==> a=c; ~Q ==> b=d |] ==> if(P,a,b) = if(Q,c,d)"; |
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
220 |
by (simp_tac (FOL_ss addsimps prems addcongs [conj_cong]) 1); |
0 | 221 |
val if_cong = result(); |
222 |
||
223 |
(*Not needed for rewriting, since P would rewrite to True anyway*) |
|
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
224 |
goalw ZF.thy [if_def] "!!P. P ==> if(P,a,b) = a"; |
0 | 225 |
by (fast_tac (lemmas_cs addSIs [the_equality]) 1); |
226 |
val if_P = result(); |
|
227 |
||
228 |
(*Not needed for rewriting, since P would rewrite to False anyway*) |
|
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
229 |
goalw ZF.thy [if_def] "!!P. ~P ==> if(P,a,b) = b"; |
0 | 230 |
by (fast_tac (lemmas_cs addSIs [the_equality]) 1); |
231 |
val if_not_P = result(); |
|
232 |
||
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
233 |
val if_ss = FOL_ss addsimps [if_true,if_false]; |
0 | 234 |
|
235 |
val expand_if = prove_goal ZF.thy |
|
236 |
"P(if(Q,x,y)) <-> ((Q --> P(x)) & (~Q --> P(y)))" |
|
437 | 237 |
(fn _=> [ (excluded_middle_tac "Q" 1), |
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
238 |
(asm_simp_tac if_ss 1), |
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
239 |
(asm_simp_tac if_ss 1) ]); |
0 | 240 |
|
241 |
val prems = goal ZF.thy |
|
242 |
"[| P ==> a: A; ~P ==> b: A |] ==> if(P,a,b): A"; |
|
437 | 243 |
by (excluded_middle_tac "P" 1); |
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
244 |
by (ALLGOALS (asm_simp_tac (if_ss addsimps prems))); |
0 | 245 |
val if_type = result(); |
246 |
||
247 |
||
248 |
(*** Foundation lemmas ***) |
|
249 |
||
437 | 250 |
(*was called mem_anti_sym*) |
673 | 251 |
val mem_asym = prove_goal ZF.thy "!!P. [| a:b; b:a |] ==> P" |
252 |
(fn _=> |
|
253 |
[ (res_inst_tac [("A1","{a,b}")] (foundation RS disjE) 1), |
|
0 | 254 |
(etac equals0D 1), |
255 |
(rtac consI1 1), |
|
673 | 256 |
(fast_tac (lemmas_cs addIs [consI1,consI2] |
0 | 257 |
addSEs [consE,equalityE]) 1) ]); |
258 |
||
437 | 259 |
(*was called mem_anti_refl*) |
260 |
val mem_irrefl = prove_goal ZF.thy "a:a ==> P" |
|
261 |
(fn [major]=> [ (rtac (major RS (major RS mem_asym)) 1) ]); |
|
0 | 262 |
|
437 | 263 |
val mem_not_refl = prove_goal ZF.thy "a ~: a" |
264 |
(K [ (rtac notI 1), (etac mem_irrefl 1) ]); |
|
0 | 265 |
|
435 | 266 |
(*Good for proving inequalities by rewriting*) |
267 |
val mem_imp_not_eq = prove_goal ZF.thy "!!a A. a:A ==> a ~= A" |
|
437 | 268 |
(fn _=> [ fast_tac (lemmas_cs addSEs [mem_irrefl]) 1 ]); |
435 | 269 |
|
0 | 270 |
(*** Rules for succ ***) |
271 |
||
272 |
val succI1 = prove_goalw ZF.thy [succ_def] "i : succ(i)" |
|
273 |
(fn _=> [ (rtac consI1 1) ]); |
|
274 |
||
275 |
val succI2 = prove_goalw ZF.thy [succ_def] |
|
276 |
"i : j ==> i : succ(j)" |
|
277 |
(fn [prem]=> [ (rtac (prem RS consI2) 1) ]); |
|
278 |
||
279 |
val succE = prove_goalw ZF.thy [succ_def] |
|
280 |
"[| i : succ(j); i=j ==> P; i:j ==> P |] ==> P" |
|
281 |
(fn major::prems=> |
|
282 |
[ (rtac (major RS consE) 1), |
|
283 |
(REPEAT (eresolve_tac prems 1)) ]); |
|
284 |
||
14
1c0926788772
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
6
diff
changeset
|
285 |
val succ_iff = prove_goal ZF.thy "i : succ(j) <-> i=j | i:j" |
1c0926788772
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
6
diff
changeset
|
286 |
(fn _ => [ (fast_tac (lemmas_cs addIs [succI1,succI2] addSEs [succE]) 1) ]); |
1c0926788772
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
6
diff
changeset
|
287 |
|
1c0926788772
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
6
diff
changeset
|
288 |
(*Classical introduction rule*) |
37 | 289 |
val succCI = prove_goal ZF.thy "(i~:j ==> i=j) ==> i: succ(j)" |
14
1c0926788772
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
6
diff
changeset
|
290 |
(fn [prem]=> |
1c0926788772
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
6
diff
changeset
|
291 |
[ (rtac (disjCI RS (succ_iff RS iffD2)) 1), |
1c0926788772
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
6
diff
changeset
|
292 |
(etac prem 1) ]); |
1c0926788772
ex/{bin.ML,comb.ML,prop.ML}: replaced NewSext by Syntax.simple_sext
lcp
parents:
6
diff
changeset
|
293 |
|
0 | 294 |
val succ_neq_0 = prove_goal ZF.thy "succ(n)=0 ==> P" |
295 |
(fn [major]=> |
|
296 |
[ (rtac (major RS equalityD1 RS subsetD RS emptyE) 1), |
|
297 |
(rtac succI1 1) ]); |
|
298 |
||
299 |
(*Useful for rewriting*) |
|
37 | 300 |
val succ_not_0 = prove_goal ZF.thy "succ(n) ~= 0" |
0 | 301 |
(fn _=> [ (rtac notI 1), (etac succ_neq_0 1) ]); |
302 |
||
303 |
(* succ(c) <= B ==> c : B *) |
|
304 |
val succ_subsetD = succI1 RSN (2,subsetD); |
|
305 |
||
673 | 306 |
val succ_inject = prove_goal ZF.thy "!!m n. succ(m) = succ(n) ==> m=n" |
307 |
(fn _ => |
|
308 |
[ (fast_tac (lemmas_cs addSEs [succE, equalityE, make_elim succ_subsetD] |
|
309 |
addEs [mem_asym]) 1) ]); |
|
0 | 310 |
|
311 |
val succ_inject_iff = prove_goal ZF.thy "succ(m) = succ(n) <-> m=n" |
|
312 |
(fn _=> [ (fast_tac (FOL_cs addSEs [succ_inject]) 1) ]); |
|
313 |
||
437 | 314 |
(*UpairI1/2 should become UpairCI; mem_irrefl as a hazE? *) |
0 | 315 |
val upair_cs = lemmas_cs |
316 |
addSIs [singletonI, DiffI, IntI, UnCI, consCI, succCI, UpairI1,UpairI2] |
|
317 |
addSEs [singletonE, DiffE, IntE, UnE, consE, succE, UpairE]; |
|
318 |