author | paulson |
Thu, 21 Mar 1996 13:02:26 +0100 | |
changeset 1601 | 0ef6ea27ab15 |
parent 1461 | 6bcb44e4d6e5 |
child 2469 | b50b8c0eec01 |
permissions | -rw-r--r-- |
1461 | 1 |
(* Title: ZF/QPair.ML |
0 | 2 |
ID: $Id$ |
1461 | 3 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
0 | 4 |
Copyright 1993 University of Cambridge |
5 |
||
744 | 6 |
For QPair.thy. |
0 | 7 |
|
8 |
Quine-inspired ordered pairs and disjoint sums, for non-well-founded data |
|
9 |
structures in ZF. Does not precisely follow Quine's construction. Thanks |
|
10 |
to Thomas Forster for suggesting this approach! |
|
11 |
||
12 |
W. V. Quine, On Ordered Pairs and Relations, in Selected Logic Papers, |
|
13 |
1966. |
|
14 |
||
15 |
Many proofs are borrowed from pair.ML and sum.ML |
|
16 |
||
17 |
Do we EVER have rank(a) < rank(<a;b>) ? Perhaps if the latter rank |
|
18 |
is not a limit ordinal? |
|
19 |
*) |
|
20 |
||
21 |
open QPair; |
|
22 |
||
23 |
(**** Quine ordered pairing ****) |
|
24 |
||
25 |
(** Lemmas for showing that <a;b> uniquely determines a and b **) |
|
26 |
||
1096 | 27 |
qed_goalw "QPair_iff" thy [QPair_def] |
0 | 28 |
"<a;b> = <c;d> <-> a=c & b=d" |
29 |
(fn _=> [rtac sum_equal_iff 1]); |
|
30 |
||
782
200a16083201
added bind_thm for theorems defined by "standard ..."
clasohm
parents:
760
diff
changeset
|
31 |
bind_thm ("QPair_inject", (QPair_iff RS iffD1 RS conjE)); |
0 | 32 |
|
1096 | 33 |
qed_goal "QPair_inject1" thy "<a;b> = <c;d> ==> a=c" |
0 | 34 |
(fn [major]=> |
35 |
[ (rtac (major RS QPair_inject) 1), (assume_tac 1) ]); |
|
36 |
||
1096 | 37 |
qed_goal "QPair_inject2" thy "<a;b> = <c;d> ==> b=d" |
0 | 38 |
(fn [major]=> |
39 |
[ (rtac (major RS QPair_inject) 1), (assume_tac 1) ]); |
|
40 |
||
41 |
||
42 |
(*** QSigma: Disjoint union of a family of sets |
|
43 |
Generalizes Cartesian product ***) |
|
44 |
||
1096 | 45 |
qed_goalw "QSigmaI" thy [QSigma_def] |
0 | 46 |
"[| a:A; b:B(a) |] ==> <a;b> : QSigma(A,B)" |
47 |
(fn prems=> [ (REPEAT (resolve_tac (prems@[singletonI,UN_I]) 1)) ]); |
|
48 |
||
49 |
(*The general elimination rule*) |
|
1096 | 50 |
qed_goalw "QSigmaE" thy [QSigma_def] |
0 | 51 |
"[| c: QSigma(A,B); \ |
52 |
\ !!x y.[| x:A; y:B(x); c=<x;y> |] ==> P \ |
|
53 |
\ |] ==> P" |
|
54 |
(fn major::prems=> |
|
55 |
[ (cut_facts_tac [major] 1), |
|
56 |
(REPEAT (eresolve_tac [UN_E, singletonE] 1 ORELSE ares_tac prems 1)) ]); |
|
57 |
||
58 |
(** Elimination rules for <a;b>:A*B -- introducing no eigenvariables **) |
|
59 |
||
60 |
val QSigmaE2 = |
|
61 |
rule_by_tactic (REPEAT_FIRST (etac QPair_inject ORELSE' bound_hyp_subst_tac) |
|
1461 | 62 |
THEN prune_params_tac) |
0 | 63 |
(read_instantiate [("c","<a;b>")] QSigmaE); |
64 |
||
1096 | 65 |
qed_goal "QSigmaD1" thy "<a;b> : QSigma(A,B) ==> a : A" |
0 | 66 |
(fn [major]=> |
67 |
[ (rtac (major RS QSigmaE2) 1), (assume_tac 1) ]); |
|
68 |
||
1096 | 69 |
qed_goal "QSigmaD2" thy "<a;b> : QSigma(A,B) ==> b : B(a)" |
0 | 70 |
(fn [major]=> |
71 |
[ (rtac (major RS QSigmaE2) 1), (assume_tac 1) ]); |
|
72 |
||
744 | 73 |
val qpair_cs = ZF_cs addSIs [QSigmaI] addSEs [QSigmaE2, QSigmaE, QPair_inject]; |
74 |
||
75 |
||
1096 | 76 |
qed_goalw "QSigma_cong" thy [QSigma_def] |
0 | 77 |
"[| A=A'; !!x. x:A' ==> B(x)=B'(x) |] ==> \ |
78 |
\ QSigma(A,B) = QSigma(A',B')" |
|
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
79 |
(fn prems=> [ (simp_tac (ZF_ss addsimps prems) 1) ]); |
0 | 80 |
|
1096 | 81 |
qed_goal "QSigma_empty1" thy "QSigma(0,B) = 0" |
82 |
(fn _ => [ (fast_tac (qpair_cs addIs [equalityI]) 1) ]); |
|
83 |
||
84 |
qed_goal "QSigma_empty2" thy "A <*> 0 = 0" |
|
744 | 85 |
(fn _ => [ (fast_tac (qpair_cs addIs [equalityI]) 1) ]); |
0 | 86 |
|
1096 | 87 |
|
88 |
(*** Projections: qfst, qsnd ***) |
|
89 |
||
90 |
qed_goalw "qfst_conv" thy [qfst_def] "qfst(<a;b>) = a" |
|
91 |
(fn _=> |
|
92 |
[ (fast_tac (qpair_cs addIs [the_equality]) 1) ]); |
|
93 |
||
94 |
qed_goalw "qsnd_conv" thy [qsnd_def] "qsnd(<a;b>) = b" |
|
95 |
(fn _=> |
|
96 |
[ (fast_tac (qpair_cs addIs [the_equality]) 1) ]); |
|
97 |
||
98 |
val qpair_ss = ZF_ss addsimps [qfst_conv,qsnd_conv]; |
|
99 |
||
100 |
qed_goal "qfst_type" thy |
|
101 |
"!!p. p:QSigma(A,B) ==> qfst(p) : A" |
|
102 |
(fn _=> [ (fast_tac (qpair_cs addss qpair_ss) 1) ]); |
|
103 |
||
104 |
qed_goal "qsnd_type" thy |
|
105 |
"!!p. p:QSigma(A,B) ==> qsnd(p) : B(qfst(p))" |
|
106 |
(fn _=> [ (fast_tac (qpair_cs addss qpair_ss) 1) ]); |
|
107 |
||
108 |
goal thy "!!a A B. a: QSigma(A,B) ==> <qfst(a); qsnd(a)> = a"; |
|
109 |
by (etac QSigmaE 1); |
|
110 |
by (asm_simp_tac qpair_ss 1); |
|
111 |
qed "QPair_qfst_qsnd_eq"; |
|
0 | 112 |
|
113 |
||
114 |
(*** Eliminator - qsplit ***) |
|
115 |
||
1096 | 116 |
(*A META-equality, so that it applies to higher types as well...*) |
117 |
qed_goalw "qsplit" thy [qsplit_def] |
|
118 |
"qsplit(%x y.c(x,y), <a;b>) == c(a,b)" |
|
119 |
(fn _ => [ (simp_tac qpair_ss 1), |
|
120 |
(rtac reflexive_thm 1) ]); |
|
0 | 121 |
|
1096 | 122 |
qed_goal "qsplit_type" thy |
0 | 123 |
"[| p:QSigma(A,B); \ |
124 |
\ !!x y.[| x:A; y:B(x) |] ==> c(x,y):C(<x;y>) \ |
|
125 |
\ |] ==> qsplit(%x y.c(x,y), p) : C(p)" |
|
126 |
(fn major::prems=> |
|
127 |
[ (rtac (major RS QSigmaE) 1), |
|
1096 | 128 |
(asm_simp_tac (qpair_ss addsimps (qsplit::prems)) 1) ]); |
129 |
||
130 |
goalw thy [qsplit_def] |
|
131 |
"!!u. u: A<*>B ==> \ |
|
132 |
\ R(qsplit(c,u)) <-> (ALL x:A. ALL y:B. u = <x;y> --> R(c(x,y)))"; |
|
133 |
by (etac QSigmaE 1); |
|
134 |
by (asm_simp_tac qpair_ss 1); |
|
135 |
by (fast_tac qpair_cs 1); |
|
136 |
qed "expand_qsplit"; |
|
137 |
||
138 |
||
139 |
(*** qsplit for predicates: result type o ***) |
|
140 |
||
141 |
goalw thy [qsplit_def] "!!R a b. R(a,b) ==> qsplit(R, <a;b>)"; |
|
142 |
by (asm_simp_tac qpair_ss 1); |
|
143 |
qed "qsplitI"; |
|
144 |
||
145 |
val major::sigma::prems = goalw thy [qsplit_def] |
|
1461 | 146 |
"[| qsplit(R,z); z:QSigma(A,B); \ |
147 |
\ !!x y. [| z = <x;y>; R(x,y) |] ==> P \ |
|
1096 | 148 |
\ |] ==> P"; |
149 |
by (rtac (sigma RS QSigmaE) 1); |
|
150 |
by (cut_facts_tac [major] 1); |
|
151 |
by (asm_full_simp_tac (qpair_ss addsimps prems) 1); |
|
152 |
qed "qsplitE"; |
|
153 |
||
154 |
goalw thy [qsplit_def] "!!R a b. qsplit(R,<a;b>) ==> R(a,b)"; |
|
155 |
by (asm_full_simp_tac qpair_ss 1); |
|
156 |
qed "qsplitD"; |
|
0 | 157 |
|
158 |
||
159 |
(*** qconverse ***) |
|
160 |
||
1096 | 161 |
qed_goalw "qconverseI" thy [qconverse_def] |
0 | 162 |
"!!a b r. <a;b>:r ==> <b;a>:qconverse(r)" |
163 |
(fn _ => [ (fast_tac qpair_cs 1) ]); |
|
164 |
||
1096 | 165 |
qed_goalw "qconverseD" thy [qconverse_def] |
0 | 166 |
"!!a b r. <a;b> : qconverse(r) ==> <b;a> : r" |
167 |
(fn _ => [ (fast_tac qpair_cs 1) ]); |
|
168 |
||
1096 | 169 |
qed_goalw "qconverseE" thy [qconverse_def] |
0 | 170 |
"[| yx : qconverse(r); \ |
171 |
\ !!x y. [| yx=<y;x>; <x;y>:r |] ==> P \ |
|
172 |
\ |] ==> P" |
|
173 |
(fn [major,minor]=> |
|
174 |
[ (rtac (major RS ReplaceE) 1), |
|
175 |
(REPEAT (eresolve_tac [exE, conjE, minor] 1)), |
|
176 |
(hyp_subst_tac 1), |
|
177 |
(assume_tac 1) ]); |
|
178 |
||
179 |
val qconverse_cs = qpair_cs addSIs [qconverseI] |
|
1461 | 180 |
addSEs [qconverseD,qconverseE]; |
0 | 181 |
|
1096 | 182 |
qed_goal "qconverse_qconverse" thy |
0 | 183 |
"!!A B r. r<=QSigma(A,B) ==> qconverse(qconverse(r)) = r" |
184 |
(fn _ => [ (fast_tac (qconverse_cs addSIs [equalityI]) 1) ]); |
|
185 |
||
1096 | 186 |
qed_goal "qconverse_type" thy |
0 | 187 |
"!!A B r. r <= A <*> B ==> qconverse(r) <= B <*> A" |
188 |
(fn _ => [ (fast_tac qconverse_cs 1) ]); |
|
189 |
||
1096 | 190 |
qed_goal "qconverse_prod" thy "qconverse(A <*> B) = B <*> A" |
0 | 191 |
(fn _ => [ (fast_tac (qconverse_cs addSIs [equalityI]) 1) ]); |
192 |
||
1096 | 193 |
qed_goal "qconverse_empty" thy "qconverse(0) = 0" |
194 |
(fn _ => [ (fast_tac (qconverse_cs addSIs [equalityI]) 1) ]); |
|
0 | 195 |
|
196 |
||
197 |
(**** The Quine-inspired notion of disjoint sum ****) |
|
198 |
||
199 |
val qsum_defs = [qsum_def,QInl_def,QInr_def,qcase_def]; |
|
200 |
||
201 |
(** Introduction rules for the injections **) |
|
202 |
||
1096 | 203 |
goalw thy qsum_defs "!!a A B. a : A ==> QInl(a) : A <+> B"; |
0 | 204 |
by (REPEAT (ares_tac [UnI1,QSigmaI,singletonI] 1)); |
760 | 205 |
qed "QInlI"; |
0 | 206 |
|
1096 | 207 |
goalw thy qsum_defs "!!b A B. b : B ==> QInr(b) : A <+> B"; |
0 | 208 |
by (REPEAT (ares_tac [UnI2,QSigmaI,singletonI] 1)); |
760 | 209 |
qed "QInrI"; |
0 | 210 |
|
211 |
(** Elimination rules **) |
|
212 |
||
1096 | 213 |
val major::prems = goalw thy qsum_defs |
0 | 214 |
"[| u: A <+> B; \ |
215 |
\ !!x. [| x:A; u=QInl(x) |] ==> P; \ |
|
216 |
\ !!y. [| y:B; u=QInr(y) |] ==> P \ |
|
217 |
\ |] ==> P"; |
|
218 |
by (rtac (major RS UnE) 1); |
|
219 |
by (REPEAT (rtac refl 1 |
|
220 |
ORELSE eresolve_tac (prems@[QSigmaE,singletonE,ssubst]) 1)); |
|
760 | 221 |
qed "qsumE"; |
0 | 222 |
|
223 |
(** Injection and freeness equivalences, for rewriting **) |
|
224 |
||
1096 | 225 |
goalw thy qsum_defs "QInl(a)=QInl(b) <-> a=b"; |
55 | 226 |
by (simp_tac (ZF_ss addsimps [QPair_iff]) 1); |
760 | 227 |
qed "QInl_iff"; |
0 | 228 |
|
1096 | 229 |
goalw thy qsum_defs "QInr(a)=QInr(b) <-> a=b"; |
55 | 230 |
by (simp_tac (ZF_ss addsimps [QPair_iff]) 1); |
760 | 231 |
qed "QInr_iff"; |
0 | 232 |
|
1096 | 233 |
goalw thy qsum_defs "QInl(a)=QInr(b) <-> False"; |
55 | 234 |
by (simp_tac (ZF_ss addsimps [QPair_iff, one_not_0 RS not_sym]) 1); |
760 | 235 |
qed "QInl_QInr_iff"; |
0 | 236 |
|
1096 | 237 |
goalw thy qsum_defs "QInr(b)=QInl(a) <-> False"; |
55 | 238 |
by (simp_tac (ZF_ss addsimps [QPair_iff, one_not_0]) 1); |
760 | 239 |
qed "QInr_QInl_iff"; |
0 | 240 |
|
55 | 241 |
(*Injection and freeness rules*) |
242 |
||
782
200a16083201
added bind_thm for theorems defined by "standard ..."
clasohm
parents:
760
diff
changeset
|
243 |
bind_thm ("QInl_inject", (QInl_iff RS iffD1)); |
200a16083201
added bind_thm for theorems defined by "standard ..."
clasohm
parents:
760
diff
changeset
|
244 |
bind_thm ("QInr_inject", (QInr_iff RS iffD1)); |
200a16083201
added bind_thm for theorems defined by "standard ..."
clasohm
parents:
760
diff
changeset
|
245 |
bind_thm ("QInl_neq_QInr", (QInl_QInr_iff RS iffD1 RS FalseE)); |
200a16083201
added bind_thm for theorems defined by "standard ..."
clasohm
parents:
760
diff
changeset
|
246 |
bind_thm ("QInr_neq_QInl", (QInr_QInl_iff RS iffD1 RS FalseE)); |
55 | 247 |
|
0 | 248 |
val qsum_cs = |
744 | 249 |
qpair_cs addSIs [PartI, QInlI, QInrI] |
250 |
addSEs [PartE, qsumE, QInl_neq_QInr, QInr_neq_QInl] |
|
251 |
addSDs [QInl_inject, QInr_inject]; |
|
0 | 252 |
|
1096 | 253 |
goal thy "!!A B. QInl(a): A<+>B ==> a: A"; |
55 | 254 |
by (fast_tac qsum_cs 1); |
760 | 255 |
qed "QInlD"; |
55 | 256 |
|
1096 | 257 |
goal thy "!!A B. QInr(b): A<+>B ==> b: B"; |
55 | 258 |
by (fast_tac qsum_cs 1); |
760 | 259 |
qed "QInrD"; |
55 | 260 |
|
0 | 261 |
(** <+> is itself injective... who cares?? **) |
262 |
||
1096 | 263 |
goal thy |
0 | 264 |
"u: A <+> B <-> (EX x. x:A & u=QInl(x)) | (EX y. y:B & u=QInr(y))"; |
265 |
by (fast_tac qsum_cs 1); |
|
760 | 266 |
qed "qsum_iff"; |
0 | 267 |
|
1096 | 268 |
goal thy "A <+> B <= C <+> D <-> A<=C & B<=D"; |
0 | 269 |
by (fast_tac qsum_cs 1); |
760 | 270 |
qed "qsum_subset_iff"; |
0 | 271 |
|
1096 | 272 |
goal thy "A <+> B = C <+> D <-> A=C & B=D"; |
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
273 |
by (simp_tac (ZF_ss addsimps [extension,qsum_subset_iff]) 1); |
0 | 274 |
by (fast_tac ZF_cs 1); |
760 | 275 |
qed "qsum_equal_iff"; |
0 | 276 |
|
277 |
(*** Eliminator -- qcase ***) |
|
278 |
||
1096 | 279 |
goalw thy qsum_defs "qcase(c, d, QInl(a)) = c(a)"; |
280 |
by (simp_tac (ZF_ss addsimps [qsplit, cond_0]) 1); |
|
760 | 281 |
qed "qcase_QInl"; |
0 | 282 |
|
1096 | 283 |
goalw thy qsum_defs "qcase(c, d, QInr(b)) = d(b)"; |
284 |
by (simp_tac (ZF_ss addsimps [qsplit, cond_1]) 1); |
|
760 | 285 |
qed "qcase_QInr"; |
0 | 286 |
|
1096 | 287 |
val major::prems = goal thy |
0 | 288 |
"[| u: A <+> B; \ |
289 |
\ !!x. x: A ==> c(x): C(QInl(x)); \ |
|
290 |
\ !!y. y: B ==> d(y): C(QInr(y)) \ |
|
291 |
\ |] ==> qcase(c,d,u) : C(u)"; |
|
292 |
by (rtac (major RS qsumE) 1); |
|
293 |
by (ALLGOALS (etac ssubst)); |
|
6
8ce8c4d13d4d
Installation of new simplifier for ZF. Deleted all congruence rules not
lcp
parents:
0
diff
changeset
|
294 |
by (ALLGOALS (asm_simp_tac (ZF_ss addsimps |
1461 | 295 |
(prems@[qcase_QInl,qcase_QInr])))); |
760 | 296 |
qed "qcase_type"; |
0 | 297 |
|
298 |
(** Rules for the Part primitive **) |
|
299 |
||
1096 | 300 |
goal thy "Part(A <+> B,QInl) = {QInl(x). x: A}"; |
744 | 301 |
by (fast_tac (qsum_cs addIs [equalityI]) 1); |
760 | 302 |
qed "Part_QInl"; |
0 | 303 |
|
1096 | 304 |
goal thy "Part(A <+> B,QInr) = {QInr(y). y: B}"; |
744 | 305 |
by (fast_tac (qsum_cs addIs [equalityI]) 1); |
760 | 306 |
qed "Part_QInr"; |
0 | 307 |
|
1096 | 308 |
goal thy "Part(A <+> B, %x.QInr(h(x))) = {QInr(y). y: Part(B,h)}"; |
744 | 309 |
by (fast_tac (qsum_cs addIs [equalityI]) 1); |
760 | 310 |
qed "Part_QInr2"; |
0 | 311 |
|
1096 | 312 |
goal thy "!!A B C. C <= A <+> B ==> Part(C,QInl) Un Part(C,QInr) = C"; |
744 | 313 |
by (fast_tac (qsum_cs addIs [equalityI]) 1); |
760 | 314 |
qed "Part_qsum_equality"; |