11 (*** Rules for the Part primitive ***) |
11 (*** Rules for the Part primitive ***) |
12 |
12 |
13 goalw Sum.thy [Part_def] |
13 goalw Sum.thy [Part_def] |
14 "a : Part(A,h) <-> a:A & (EX y. a=h(y))"; |
14 "a : Part(A,h) <-> a:A & (EX y. a=h(y))"; |
15 by (rtac separation 1); |
15 by (rtac separation 1); |
16 val Part_iff = result(); |
16 qed "Part_iff"; |
17 |
17 |
18 goalw Sum.thy [Part_def] |
18 goalw Sum.thy [Part_def] |
19 "!!a b A h. [| a : A; a=h(b) |] ==> a : Part(A,h)"; |
19 "!!a b A h. [| a : A; a=h(b) |] ==> a : Part(A,h)"; |
20 by (REPEAT (ares_tac [exI,CollectI] 1)); |
20 by (REPEAT (ares_tac [exI,CollectI] 1)); |
21 val Part_eqI = result(); |
21 qed "Part_eqI"; |
22 |
22 |
23 val PartI = refl RSN (2,Part_eqI); |
23 val PartI = refl RSN (2,Part_eqI); |
24 |
24 |
25 val major::prems = goalw Sum.thy [Part_def] |
25 val major::prems = goalw Sum.thy [Part_def] |
26 "[| a : Part(A,h); !!z. [| a : A; a=h(z) |] ==> P \ |
26 "[| a : Part(A,h); !!z. [| a : A; a=h(z) |] ==> P \ |
27 \ |] ==> P"; |
27 \ |] ==> P"; |
28 by (rtac (major RS CollectE) 1); |
28 by (rtac (major RS CollectE) 1); |
29 by (etac exE 1); |
29 by (etac exE 1); |
30 by (REPEAT (ares_tac prems 1)); |
30 by (REPEAT (ares_tac prems 1)); |
31 val PartE = result(); |
31 qed "PartE"; |
32 |
32 |
33 goalw Sum.thy [Part_def] "Part(A,h) <= A"; |
33 goalw Sum.thy [Part_def] "Part(A,h) <= A"; |
34 by (rtac Collect_subset 1); |
34 by (rtac Collect_subset 1); |
35 val Part_subset = result(); |
35 qed "Part_subset"; |
36 |
36 |
37 |
37 |
38 (*** Rules for Disjoint Sums ***) |
38 (*** Rules for Disjoint Sums ***) |
39 |
39 |
40 val sum_defs = [sum_def,Inl_def,Inr_def,case_def]; |
40 val sum_defs = [sum_def,Inl_def,Inr_def,case_def]; |
41 |
41 |
42 goalw Sum.thy (bool_def::sum_defs) "Sigma(bool,C) = C(0) + C(1)"; |
42 goalw Sum.thy (bool_def::sum_defs) "Sigma(bool,C) = C(0) + C(1)"; |
43 by (fast_tac eq_cs 1); |
43 by (fast_tac eq_cs 1); |
44 val Sigma_bool = result(); |
44 qed "Sigma_bool"; |
45 |
45 |
46 (** Introduction rules for the injections **) |
46 (** Introduction rules for the injections **) |
47 |
47 |
48 goalw Sum.thy sum_defs "!!a A B. a : A ==> Inl(a) : A+B"; |
48 goalw Sum.thy sum_defs "!!a A B. a : A ==> Inl(a) : A+B"; |
49 by (REPEAT (ares_tac [UnI1,SigmaI,singletonI] 1)); |
49 by (REPEAT (ares_tac [UnI1,SigmaI,singletonI] 1)); |
50 val InlI = result(); |
50 qed "InlI"; |
51 |
51 |
52 goalw Sum.thy sum_defs "!!b A B. b : B ==> Inr(b) : A+B"; |
52 goalw Sum.thy sum_defs "!!b A B. b : B ==> Inr(b) : A+B"; |
53 by (REPEAT (ares_tac [UnI2,SigmaI,singletonI] 1)); |
53 by (REPEAT (ares_tac [UnI2,SigmaI,singletonI] 1)); |
54 val InrI = result(); |
54 qed "InrI"; |
55 |
55 |
56 (** Elimination rules **) |
56 (** Elimination rules **) |
57 |
57 |
58 val major::prems = goalw Sum.thy sum_defs |
58 val major::prems = goalw Sum.thy sum_defs |
59 "[| u: A+B; \ |
59 "[| u: A+B; \ |
61 \ !!y. [| y:B; u=Inr(y) |] ==> P \ |
61 \ !!y. [| y:B; u=Inr(y) |] ==> P \ |
62 \ |] ==> P"; |
62 \ |] ==> P"; |
63 by (rtac (major RS UnE) 1); |
63 by (rtac (major RS UnE) 1); |
64 by (REPEAT (rtac refl 1 |
64 by (REPEAT (rtac refl 1 |
65 ORELSE eresolve_tac (prems@[SigmaE,singletonE,ssubst]) 1)); |
65 ORELSE eresolve_tac (prems@[SigmaE,singletonE,ssubst]) 1)); |
66 val sumE = result(); |
66 qed "sumE"; |
67 |
67 |
68 (** Injection and freeness equivalences, for rewriting **) |
68 (** Injection and freeness equivalences, for rewriting **) |
69 |
69 |
70 goalw Sum.thy sum_defs "Inl(a)=Inl(b) <-> a=b"; |
70 goalw Sum.thy sum_defs "Inl(a)=Inl(b) <-> a=b"; |
71 by (simp_tac ZF_ss 1); |
71 by (simp_tac ZF_ss 1); |
72 val Inl_iff = result(); |
72 qed "Inl_iff"; |
73 |
73 |
74 goalw Sum.thy sum_defs "Inr(a)=Inr(b) <-> a=b"; |
74 goalw Sum.thy sum_defs "Inr(a)=Inr(b) <-> a=b"; |
75 by (simp_tac ZF_ss 1); |
75 by (simp_tac ZF_ss 1); |
76 val Inr_iff = result(); |
76 qed "Inr_iff"; |
77 |
77 |
78 goalw Sum.thy sum_defs "Inl(a)=Inr(b) <-> False"; |
78 goalw Sum.thy sum_defs "Inl(a)=Inr(b) <-> False"; |
79 by (simp_tac (ZF_ss addsimps [one_not_0 RS not_sym]) 1); |
79 by (simp_tac (ZF_ss addsimps [one_not_0 RS not_sym]) 1); |
80 val Inl_Inr_iff = result(); |
80 qed "Inl_Inr_iff"; |
81 |
81 |
82 goalw Sum.thy sum_defs "Inr(b)=Inl(a) <-> False"; |
82 goalw Sum.thy sum_defs "Inr(b)=Inl(a) <-> False"; |
83 by (simp_tac (ZF_ss addsimps [one_not_0]) 1); |
83 by (simp_tac (ZF_ss addsimps [one_not_0]) 1); |
84 val Inr_Inl_iff = result(); |
84 qed "Inr_Inl_iff"; |
85 |
85 |
86 (*Injection and freeness rules*) |
86 (*Injection and freeness rules*) |
87 |
87 |
88 val Inl_inject = standard (Inl_iff RS iffD1); |
88 val Inl_inject = standard (Inl_iff RS iffD1); |
89 val Inr_inject = standard (Inr_iff RS iffD1); |
89 val Inr_inject = standard (Inr_iff RS iffD1); |
97 val sum_ss = ZF_ss addsimps [InlI, InrI, Inl_iff, Inr_iff, |
97 val sum_ss = ZF_ss addsimps [InlI, InrI, Inl_iff, Inr_iff, |
98 Inl_Inr_iff, Inr_Inl_iff]; |
98 Inl_Inr_iff, Inr_Inl_iff]; |
99 |
99 |
100 goal Sum.thy "!!A B. Inl(a): A+B ==> a: A"; |
100 goal Sum.thy "!!A B. Inl(a): A+B ==> a: A"; |
101 by (fast_tac sum_cs 1); |
101 by (fast_tac sum_cs 1); |
102 val InlD = result(); |
102 qed "InlD"; |
103 |
103 |
104 goal Sum.thy "!!A B. Inr(b): A+B ==> b: B"; |
104 goal Sum.thy "!!A B. Inr(b): A+B ==> b: B"; |
105 by (fast_tac sum_cs 1); |
105 by (fast_tac sum_cs 1); |
106 val InrD = result(); |
106 qed "InrD"; |
107 |
107 |
108 goal Sum.thy "u: A+B <-> (EX x. x:A & u=Inl(x)) | (EX y. y:B & u=Inr(y))"; |
108 goal Sum.thy "u: A+B <-> (EX x. x:A & u=Inl(x)) | (EX y. y:B & u=Inr(y))"; |
109 by (fast_tac sum_cs 1); |
109 by (fast_tac sum_cs 1); |
110 val sum_iff = result(); |
110 qed "sum_iff"; |
111 |
111 |
112 goal Sum.thy "A+B <= C+D <-> A<=C & B<=D"; |
112 goal Sum.thy "A+B <= C+D <-> A<=C & B<=D"; |
113 by (fast_tac sum_cs 1); |
113 by (fast_tac sum_cs 1); |
114 val sum_subset_iff = result(); |
114 qed "sum_subset_iff"; |
115 |
115 |
116 goal Sum.thy "A+B = C+D <-> A=C & B=D"; |
116 goal Sum.thy "A+B = C+D <-> A=C & B=D"; |
117 by (simp_tac (ZF_ss addsimps [extension,sum_subset_iff]) 1); |
117 by (simp_tac (ZF_ss addsimps [extension,sum_subset_iff]) 1); |
118 by (fast_tac ZF_cs 1); |
118 by (fast_tac ZF_cs 1); |
119 val sum_equal_iff = result(); |
119 qed "sum_equal_iff"; |
120 |
120 |
121 |
121 |
122 (*** Eliminator -- case ***) |
122 (*** Eliminator -- case ***) |
123 |
123 |
124 goalw Sum.thy sum_defs "case(c, d, Inl(a)) = c(a)"; |
124 goalw Sum.thy sum_defs "case(c, d, Inl(a)) = c(a)"; |
125 by (rtac (split RS trans) 1); |
125 by (rtac (split RS trans) 1); |
126 by (rtac cond_0 1); |
126 by (rtac cond_0 1); |
127 val case_Inl = result(); |
127 qed "case_Inl"; |
128 |
128 |
129 goalw Sum.thy sum_defs "case(c, d, Inr(b)) = d(b)"; |
129 goalw Sum.thy sum_defs "case(c, d, Inr(b)) = d(b)"; |
130 by (rtac (split RS trans) 1); |
130 by (rtac (split RS trans) 1); |
131 by (rtac cond_1 1); |
131 by (rtac cond_1 1); |
132 val case_Inr = result(); |
132 qed "case_Inr"; |
133 |
133 |
134 val major::prems = goal Sum.thy |
134 val major::prems = goal Sum.thy |
135 "[| u: A+B; \ |
135 "[| u: A+B; \ |
136 \ !!x. x: A ==> c(x): C(Inl(x)); \ |
136 \ !!x. x: A ==> c(x): C(Inl(x)); \ |
137 \ !!y. y: B ==> d(y): C(Inr(y)) \ |
137 \ !!y. y: B ==> d(y): C(Inr(y)) \ |
138 \ |] ==> case(c,d,u) : C(u)"; |
138 \ |] ==> case(c,d,u) : C(u)"; |
139 by (rtac (major RS sumE) 1); |
139 by (rtac (major RS sumE) 1); |
140 by (ALLGOALS (etac ssubst)); |
140 by (ALLGOALS (etac ssubst)); |
141 by (ALLGOALS (asm_simp_tac (ZF_ss addsimps |
141 by (ALLGOALS (asm_simp_tac (ZF_ss addsimps |
142 (prems@[case_Inl,case_Inr])))); |
142 (prems@[case_Inl,case_Inr])))); |
143 val case_type = result(); |
143 qed "case_type"; |
144 |
144 |
145 goal Sum.thy |
145 goal Sum.thy |
146 "!!u. u: A+B ==> \ |
146 "!!u. u: A+B ==> \ |
147 \ R(case(c,d,u)) <-> \ |
147 \ R(case(c,d,u)) <-> \ |
148 \ ((ALL x:A. u = Inl(x) --> R(c(x))) & \ |
148 \ ((ALL x:A. u = Inl(x) --> R(c(x))) & \ |
150 by (etac sumE 1); |
150 by (etac sumE 1); |
151 by (asm_simp_tac (ZF_ss addsimps [case_Inl]) 1); |
151 by (asm_simp_tac (ZF_ss addsimps [case_Inl]) 1); |
152 by (fast_tac sum_cs 1); |
152 by (fast_tac sum_cs 1); |
153 by (asm_simp_tac (ZF_ss addsimps [case_Inr]) 1); |
153 by (asm_simp_tac (ZF_ss addsimps [case_Inr]) 1); |
154 by (fast_tac sum_cs 1); |
154 by (fast_tac sum_cs 1); |
155 val expand_case = result(); |
155 qed "expand_case"; |
156 |
|
157 |
156 |
158 goal Sum.thy "!!A B h. A<=B ==> Part(A,h)<=Part(B,h)"; |
157 goal Sum.thy "!!A B h. A<=B ==> Part(A,h)<=Part(B,h)"; |
159 by (fast_tac sum_cs 1); |
158 by (fast_tac sum_cs 1); |
160 val Part_mono = result(); |
159 qed "Part_mono"; |
161 |
160 |
162 goal Sum.thy "Part(Collect(A,P), h) = Collect(Part(A,h), P)"; |
161 goal Sum.thy "Part(Collect(A,P), h) = Collect(Part(A,h), P)"; |
163 by (fast_tac (sum_cs addSIs [equalityI]) 1); |
162 by (fast_tac (sum_cs addSIs [equalityI]) 1); |
164 val Part_Collect = result(); |
163 qed "Part_Collect"; |
165 |
164 |
166 val Part_CollectE = |
165 val Part_CollectE = |
167 Part_Collect RS equalityD1 RS subsetD RS CollectE |> standard; |
166 Part_Collect RS equalityD1 RS subsetD RS CollectE |> standard; |
168 |
167 |
169 goal Sum.thy "Part(A+B,Inl) = {Inl(x). x: A}"; |
168 goal Sum.thy "Part(A+B,Inl) = {Inl(x). x: A}"; |
170 by (fast_tac (sum_cs addIs [equalityI]) 1); |
169 by (fast_tac (sum_cs addIs [equalityI]) 1); |
171 val Part_Inl = result(); |
170 qed "Part_Inl"; |
172 |
171 |
173 goal Sum.thy "Part(A+B,Inr) = {Inr(y). y: B}"; |
172 goal Sum.thy "Part(A+B,Inr) = {Inr(y). y: B}"; |
174 by (fast_tac (sum_cs addIs [equalityI]) 1); |
173 by (fast_tac (sum_cs addIs [equalityI]) 1); |
175 val Part_Inr = result(); |
174 qed "Part_Inr"; |
176 |
175 |
177 goalw Sum.thy [Part_def] "!!a. a : Part(A,h) ==> a : A"; |
176 goalw Sum.thy [Part_def] "!!a. a : Part(A,h) ==> a : A"; |
178 by (etac CollectD1 1); |
177 by (etac CollectD1 1); |
179 val PartD1 = result(); |
178 qed "PartD1"; |
180 |
179 |
181 goal Sum.thy "Part(A,%x.x) = A"; |
180 goal Sum.thy "Part(A,%x.x) = A"; |
182 by (fast_tac (sum_cs addIs [equalityI]) 1); |
181 by (fast_tac (sum_cs addIs [equalityI]) 1); |
183 val Part_id = result(); |
182 qed "Part_id"; |
184 |
183 |
185 goal Sum.thy "Part(A+B, %x.Inr(h(x))) = {Inr(y). y: Part(B,h)}"; |
184 goal Sum.thy "Part(A+B, %x.Inr(h(x))) = {Inr(y). y: Part(B,h)}"; |
186 by (fast_tac (sum_cs addIs [equalityI]) 1); |
185 by (fast_tac (sum_cs addIs [equalityI]) 1); |
187 val Part_Inr2 = result(); |
186 qed "Part_Inr2"; |
188 |
187 |
189 goal Sum.thy "!!A B C. C <= A+B ==> Part(C,Inl) Un Part(C,Inr) = C"; |
188 goal Sum.thy "!!A B C. C <= A+B ==> Part(C,Inl) Un Part(C,Inr) = C"; |
190 by (fast_tac (sum_cs addIs [equalityI]) 1); |
189 by (fast_tac (sum_cs addIs [equalityI]) 1); |
191 val Part_sum_equality = result(); |
190 qed "Part_sum_equality"; |