6 Functions in Zermelo-Fraenkel Set Theory |
6 Functions in Zermelo-Fraenkel Set Theory |
7 *) |
7 *) |
8 |
8 |
9 (*** The Pi operator -- dependent function space ***) |
9 (*** The Pi operator -- dependent function space ***) |
10 |
10 |
11 goalw ZF.thy [Pi_def] |
11 Goalw [Pi_def] |
12 "f: Pi(A,B) <-> function(f) & f<=Sigma(A,B) & A<=domain(f)"; |
12 "f: Pi(A,B) <-> function(f) & f<=Sigma(A,B) & A<=domain(f)"; |
13 by (Blast_tac 1); |
13 by (Blast_tac 1); |
14 qed "Pi_iff"; |
14 qed "Pi_iff"; |
15 |
15 |
16 (*For upward compatibility with the former definition*) |
16 (*For upward compatibility with the former definition*) |
17 goalw ZF.thy [Pi_def, function_def] |
17 Goalw [Pi_def, function_def] |
18 "f: Pi(A,B) <-> f<=Sigma(A,B) & (ALL x:A. EX! y. <x,y>: f)"; |
18 "f: Pi(A,B) <-> f<=Sigma(A,B) & (ALL x:A. EX! y. <x,y>: f)"; |
19 by (Blast_tac 1); |
19 by (Blast_tac 1); |
20 qed "Pi_iff_old"; |
20 qed "Pi_iff_old"; |
21 |
21 |
22 goal ZF.thy "!!f. f: Pi(A,B) ==> function(f)"; |
22 Goal "f: Pi(A,B) ==> function(f)"; |
23 by (asm_full_simp_tac (FOL_ss addsimps [Pi_iff]) 1); |
23 by (asm_full_simp_tac (FOL_ss addsimps [Pi_iff]) 1); |
24 qed "fun_is_function"; |
24 qed "fun_is_function"; |
25 |
25 |
26 (**Two "destruct" rules for Pi **) |
26 (**Two "destruct" rules for Pi **) |
27 |
27 |
28 val [major] = goalw ZF.thy [Pi_def] "f: Pi(A,B) ==> f <= Sigma(A,B)"; |
28 Goalw [Pi_def] "f: Pi(A,B) ==> f <= Sigma(A,B)"; |
29 by (rtac (major RS CollectD1 RS PowD) 1); |
29 by (Blast_tac 1); |
30 qed "fun_is_rel"; |
30 qed "fun_is_rel"; |
31 |
31 |
32 goal ZF.thy "!!f. [| f: Pi(A,B); a:A |] ==> EX! y. <a,y>: f"; |
32 Goal "[| f: Pi(A,B); a:A |] ==> EX! y. <a,y>: f"; |
33 by (blast_tac (claset() addSDs [Pi_iff_old RS iffD1]) 1); |
33 by (blast_tac (claset() addSDs [Pi_iff_old RS iffD1]) 1); |
34 qed "fun_unique_Pair"; |
34 qed "fun_unique_Pair"; |
35 |
35 |
36 val prems = goalw ZF.thy [Pi_def] |
36 val prems = Goalw [Pi_def] |
37 "[| A=A'; !!x. x:A' ==> B(x)=B'(x) |] ==> Pi(A,B) = Pi(A',B')"; |
37 "[| A=A'; !!x. x:A' ==> B(x)=B'(x) |] ==> Pi(A,B) = Pi(A',B')"; |
38 by (simp_tac (FOL_ss addsimps prems addcongs [Sigma_cong]) 1); |
38 by (simp_tac (FOL_ss addsimps prems addcongs [Sigma_cong]) 1); |
39 qed "Pi_cong"; |
39 qed "Pi_cong"; |
40 |
40 |
41 (*Sigma_cong, Pi_cong NOT given to Addcongs: they cause |
41 (*Sigma_cong, Pi_cong NOT given to Addcongs: they cause |
42 flex-flex pairs and the "Check your prover" error. Most |
42 flex-flex pairs and the "Check your prover" error. Most |
43 Sigmas and Pis are abbreviated as * or -> *) |
43 Sigmas and Pis are abbreviated as * or -> *) |
44 |
44 |
45 (*Weakening one function type to another; see also Pi_type*) |
45 (*Weakening one function type to another; see also Pi_type*) |
46 goalw ZF.thy [Pi_def] "!!f. [| f: A->B; B<=D |] ==> f: A->D"; |
46 Goalw [Pi_def] "[| f: A->B; B<=D |] ==> f: A->D"; |
47 by (Best_tac 1); |
47 by (Best_tac 1); |
48 qed "fun_weaken_type"; |
48 qed "fun_weaken_type"; |
49 |
49 |
50 (*Empty function spaces*) |
50 (*Empty function spaces*) |
51 goalw ZF.thy [Pi_def, function_def] "Pi(0,A) = {0}"; |
51 Goalw [Pi_def, function_def] "Pi(0,A) = {0}"; |
52 by (Blast_tac 1); |
52 by (Blast_tac 1); |
53 qed "Pi_empty1"; |
53 qed "Pi_empty1"; |
54 |
54 |
55 goalw ZF.thy [Pi_def] "!!A a. a:A ==> A->0 = 0"; |
55 Goalw [Pi_def] "a:A ==> A->0 = 0"; |
56 by (Blast_tac 1); |
56 by (Blast_tac 1); |
57 qed "Pi_empty2"; |
57 qed "Pi_empty2"; |
58 |
58 |
59 (*The empty function*) |
59 (*The empty function*) |
60 goalw ZF.thy [Pi_def, function_def] "0: Pi(0,B)"; |
60 Goalw [Pi_def, function_def] "0: Pi(0,B)"; |
61 by (Blast_tac 1); |
61 by (Blast_tac 1); |
62 qed "empty_fun"; |
62 qed "empty_fun"; |
63 |
63 |
64 (*The singleton function*) |
64 (*The singleton function*) |
65 goalw ZF.thy [Pi_def, function_def] "{<a,b>} : {a} -> {b}"; |
65 Goalw [Pi_def, function_def] "{<a,b>} : {a} -> {b}"; |
66 by (Blast_tac 1); |
66 by (Blast_tac 1); |
67 qed "singleton_fun"; |
67 qed "singleton_fun"; |
68 |
68 |
69 Addsimps [empty_fun, singleton_fun]; |
69 Addsimps [empty_fun, singleton_fun]; |
70 |
70 |
71 (*** Function Application ***) |
71 (*** Function Application ***) |
72 |
72 |
73 goalw ZF.thy [Pi_def, function_def] |
73 Goalw [Pi_def, function_def] |
74 "!!a b f. [| <a,b>: f; <a,c>: f; f: Pi(A,B) |] ==> b=c"; |
74 "[| <a,b>: f; <a,c>: f; f: Pi(A,B) |] ==> b=c"; |
75 by (Blast_tac 1); |
75 by (Blast_tac 1); |
76 qed "apply_equality2"; |
76 qed "apply_equality2"; |
77 |
77 |
78 goalw ZF.thy [apply_def, function_def] |
78 Goalw [apply_def, function_def] |
79 "!!a b f. [| <a,b>: f; function(f) |] ==> f`a = b"; |
79 "[| <a,b>: f; function(f) |] ==> f`a = b"; |
80 by (blast_tac (claset() addIs [the_equality]) 1); |
80 by (blast_tac (claset() addIs [the_equality]) 1); |
81 qed "function_apply_equality"; |
81 qed "function_apply_equality"; |
82 |
82 |
83 goalw ZF.thy [Pi_def] "!!a b f. [| <a,b>: f; f: Pi(A,B) |] ==> f`a = b"; |
83 Goalw [Pi_def] "[| <a,b>: f; f: Pi(A,B) |] ==> f`a = b"; |
84 by (blast_tac (claset() addIs [function_apply_equality]) 1); |
84 by (blast_tac (claset() addIs [function_apply_equality]) 1); |
85 qed "apply_equality"; |
85 qed "apply_equality"; |
86 |
86 |
87 (*Applying a function outside its domain yields 0*) |
87 (*Applying a function outside its domain yields 0*) |
88 goalw ZF.thy [apply_def] |
88 Goalw [apply_def] |
89 "!!a. a ~: domain(f) ==> f`a = 0"; |
89 "a ~: domain(f) ==> f`a = 0"; |
90 by (rtac the_0 1); |
90 by (rtac the_0 1); |
91 by (Blast_tac 1); |
91 by (Blast_tac 1); |
92 qed "apply_0"; |
92 qed "apply_0"; |
93 |
93 |
94 goal ZF.thy "!!f. [| f: Pi(A,B); c: f |] ==> EX x:A. c = <x,f`x>"; |
94 Goal "[| f: Pi(A,B); c: f |] ==> EX x:A. c = <x,f`x>"; |
95 by (forward_tac [fun_is_rel] 1); |
95 by (forward_tac [fun_is_rel] 1); |
96 by (blast_tac (claset() addDs [apply_equality]) 1); |
96 by (blast_tac (claset() addDs [apply_equality]) 1); |
97 qed "Pi_memberD"; |
97 qed "Pi_memberD"; |
98 |
98 |
99 goal ZF.thy "!!f. [| f: Pi(A,B); a:A |] ==> <a,f`a>: f"; |
99 Goal "[| f: Pi(A,B); a:A |] ==> <a,f`a>: f"; |
100 by (rtac (fun_unique_Pair RS ex1E) 1); |
100 by (rtac (fun_unique_Pair RS ex1E) 1); |
101 by (resolve_tac [apply_equality RS ssubst] 3); |
101 by (resolve_tac [apply_equality RS ssubst] 3); |
102 by (REPEAT (assume_tac 1)); |
102 by (REPEAT (assume_tac 1)); |
103 qed "apply_Pair"; |
103 qed "apply_Pair"; |
104 |
104 |
105 (*Conclusion is flexible -- use res_inst_tac or else apply_funtype below!*) |
105 (*Conclusion is flexible -- use res_inst_tac or else apply_funtype below!*) |
106 goal ZF.thy "!!f. [| f: Pi(A,B); a:A |] ==> f`a : B(a)"; |
106 Goal "[| f: Pi(A,B); a:A |] ==> f`a : B(a)"; |
107 by (rtac (fun_is_rel RS subsetD RS SigmaE2) 1); |
107 by (rtac (fun_is_rel RS subsetD RS SigmaE2) 1); |
108 by (REPEAT (ares_tac [apply_Pair] 1)); |
108 by (REPEAT (ares_tac [apply_Pair] 1)); |
109 qed "apply_type"; |
109 qed "apply_type"; |
110 |
110 |
111 (*This version is acceptable to the simplifier*) |
111 (*This version is acceptable to the simplifier*) |
112 goal ZF.thy "!!f. [| f: A->B; a:A |] ==> f`a : B"; |
112 Goal "[| f: A->B; a:A |] ==> f`a : B"; |
113 by (REPEAT (ares_tac [apply_type] 1)); |
113 by (REPEAT (ares_tac [apply_type] 1)); |
114 qed "apply_funtype"; |
114 qed "apply_funtype"; |
115 |
115 |
116 val [major] = goal ZF.thy |
116 Goal "f: Pi(A,B) ==> <a,b>: f <-> a:A & f`a = b"; |
117 "f: Pi(A,B) ==> <a,b>: f <-> a:A & f`a = b"; |
117 by (forward_tac [fun_is_rel] 1); |
118 by (cut_facts_tac [major RS fun_is_rel] 1); |
118 by (blast_tac (claset() addSIs [apply_Pair, apply_equality]) 1); |
119 by (blast_tac (claset() addSIs [major RS apply_Pair, |
|
120 major RSN (2,apply_equality)]) 1); |
|
121 qed "apply_iff"; |
119 qed "apply_iff"; |
122 |
120 |
123 (*Refining one Pi type to another*) |
121 (*Refining one Pi type to another*) |
124 val pi_prem::prems = goal ZF.thy |
122 val pi_prem::prems = Goal |
125 "[| f: Pi(A,C); !!x. x:A ==> f`x : B(x) |] ==> f : Pi(A,B)"; |
123 "[| f: Pi(A,C); !!x. x:A ==> f`x : B(x) |] ==> f : Pi(A,B)"; |
126 by (cut_facts_tac [pi_prem] 1); |
124 by (cut_facts_tac [pi_prem] 1); |
127 by (asm_full_simp_tac (FOL_ss addsimps [Pi_iff]) 1); |
125 by (asm_full_simp_tac (FOL_ss addsimps [Pi_iff]) 1); |
128 by (blast_tac (claset() addIs prems addSDs [pi_prem RS Pi_memberD]) 1); |
126 by (blast_tac (claset() addIs prems addSDs [pi_prem RS Pi_memberD]) 1); |
129 qed "Pi_type"; |
127 qed "Pi_type"; |
130 |
128 |
131 |
129 |
132 (** Elimination of membership in a function **) |
130 (** Elimination of membership in a function **) |
133 |
131 |
134 goal ZF.thy "!!a A. [| <a,b> : f; f: Pi(A,B) |] ==> a : A"; |
132 Goal "[| <a,b> : f; f: Pi(A,B) |] ==> a : A"; |
135 by (REPEAT (ares_tac [fun_is_rel RS subsetD RS SigmaD1] 1)); |
133 by (REPEAT (ares_tac [fun_is_rel RS subsetD RS SigmaD1] 1)); |
136 qed "domain_type"; |
134 qed "domain_type"; |
137 |
135 |
138 goal ZF.thy "!!b B a. [| <a,b> : f; f: Pi(A,B) |] ==> b : B(a)"; |
136 Goal "[| <a,b> : f; f: Pi(A,B) |] ==> b : B(a)"; |
139 by (etac (fun_is_rel RS subsetD RS SigmaD2) 1); |
137 by (etac (fun_is_rel RS subsetD RS SigmaD2) 1); |
140 by (assume_tac 1); |
138 by (assume_tac 1); |
141 qed "range_type"; |
139 qed "range_type"; |
142 |
140 |
143 val prems = goal ZF.thy |
141 val prems = Goal |
144 "[| <a,b>: f; f: Pi(A,B); \ |
142 "[| <a,b>: f; f: Pi(A,B); \ |
145 \ [| a:A; b:B(a); f`a = b |] ==> P \ |
143 \ [| a:A; b:B(a); f`a = b |] ==> P \ |
146 \ |] ==> P"; |
144 \ |] ==> P"; |
147 by (cut_facts_tac prems 1); |
145 by (cut_facts_tac prems 1); |
148 by (resolve_tac prems 1); |
146 by (resolve_tac prems 1); |
149 by (REPEAT (eresolve_tac [asm_rl,domain_type,range_type,apply_equality] 1)); |
147 by (REPEAT (eresolve_tac [asm_rl,domain_type,range_type,apply_equality] 1)); |
150 qed "Pair_mem_PiE"; |
148 qed "Pair_mem_PiE"; |
151 |
149 |
152 (*** Lambda Abstraction ***) |
150 (*** Lambda Abstraction ***) |
153 |
151 |
154 goalw ZF.thy [lam_def] "!!A b. a:A ==> <a,b(a)> : (lam x:A. b(x))"; |
152 Goalw [lam_def] "a:A ==> <a,b(a)> : (lam x:A. b(x))"; |
155 by (etac RepFunI 1); |
153 by (etac RepFunI 1); |
156 qed "lamI"; |
154 qed "lamI"; |
157 |
155 |
158 val major::prems = goalw ZF.thy [lam_def] |
156 val major::prems = Goalw [lam_def] |
159 "[| p: (lam x:A. b(x)); !!x.[| x:A; p=<x,b(x)> |] ==> P \ |
157 "[| p: (lam x:A. b(x)); !!x.[| x:A; p=<x,b(x)> |] ==> P \ |
160 \ |] ==> P"; |
158 \ |] ==> P"; |
161 by (rtac (major RS RepFunE) 1); |
159 by (rtac (major RS RepFunE) 1); |
162 by (REPEAT (ares_tac prems 1)); |
160 by (REPEAT (ares_tac prems 1)); |
163 qed "lamE"; |
161 qed "lamE"; |
164 |
162 |
165 goal ZF.thy "!!a b c. [| <a,c>: (lam x:A. b(x)) |] ==> c = b(a)"; |
163 Goal "[| <a,c>: (lam x:A. b(x)) |] ==> c = b(a)"; |
166 by (REPEAT (eresolve_tac [asm_rl,lamE,Pair_inject,ssubst] 1)); |
164 by (REPEAT (eresolve_tac [asm_rl,lamE,Pair_inject,ssubst] 1)); |
167 qed "lamD"; |
165 qed "lamD"; |
168 |
166 |
169 val prems = goalw ZF.thy [lam_def, Pi_def, function_def] |
167 val prems = Goalw [lam_def, Pi_def, function_def] |
170 "[| !!x. x:A ==> b(x): B(x) |] ==> (lam x:A. b(x)) : Pi(A,B)"; |
168 "[| !!x. x:A ==> b(x): B(x) |] ==> (lam x:A. b(x)) : Pi(A,B)"; |
171 by (blast_tac (claset() addIs prems) 1); |
169 by (blast_tac (claset() addIs prems) 1); |
172 qed "lam_type"; |
170 qed "lam_type"; |
173 |
171 |
174 goal ZF.thy "(lam x:A. b(x)) : A -> {b(x). x:A}"; |
172 Goal "(lam x:A. b(x)) : A -> {b(x). x:A}"; |
175 by (REPEAT (ares_tac [refl,lam_type,RepFunI] 1)); |
173 by (REPEAT (ares_tac [refl,lam_type,RepFunI] 1)); |
176 qed "lam_funtype"; |
174 qed "lam_funtype"; |
177 |
175 |
178 goal ZF.thy "!!a A. a : A ==> (lam x:A. b(x)) ` a = b(a)"; |
176 Goal "a : A ==> (lam x:A. b(x)) ` a = b(a)"; |
179 by (REPEAT (ares_tac [apply_equality,lam_funtype,lamI] 1)); |
177 by (REPEAT (ares_tac [apply_equality,lam_funtype,lamI] 1)); |
180 qed "beta"; |
178 qed "beta"; |
181 |
179 |
182 goalw ZF.thy [lam_def] "(lam x:0. b(x)) = 0"; |
180 Goalw [lam_def] "(lam x:0. b(x)) = 0"; |
183 by (Simp_tac 1); |
181 by (Simp_tac 1); |
184 qed "lam_empty"; |
182 qed "lam_empty"; |
185 |
183 |
186 Goalw [lam_def] "domain(Lambda(A,b)) = A"; |
184 Goalw [lam_def] "domain(Lambda(A,b)) = A"; |
187 by (Blast_tac 1); |
185 by (Blast_tac 1); |
188 qed "domain_lam"; |
186 qed "domain_lam"; |
189 |
187 |
190 Addsimps [beta, lam_empty, domain_lam]; |
188 Addsimps [beta, lam_empty, domain_lam]; |
191 |
189 |
192 (*congruence rule for lambda abstraction*) |
190 (*congruence rule for lambda abstraction*) |
193 val prems = goalw ZF.thy [lam_def] |
191 val prems = Goalw [lam_def] |
194 "[| A=A'; !!x. x:A' ==> b(x)=b'(x) |] ==> Lambda(A,b) = Lambda(A',b')"; |
192 "[| A=A'; !!x. x:A' ==> b(x)=b'(x) |] ==> Lambda(A,b) = Lambda(A',b')"; |
195 by (simp_tac (FOL_ss addsimps prems addcongs [RepFun_cong]) 1); |
193 by (simp_tac (FOL_ss addsimps prems addcongs [RepFun_cong]) 1); |
196 qed "lam_cong"; |
194 qed "lam_cong"; |
197 |
195 |
198 Addcongs [lam_cong]; |
196 Addcongs [lam_cong]; |
199 |
197 |
200 val [major] = goal ZF.thy |
198 val [major] = Goal |
201 "(!!x. x:A ==> EX! y. Q(x,y)) ==> EX f. ALL x:A. Q(x, f`x)"; |
199 "(!!x. x:A ==> EX! y. Q(x,y)) ==> EX f. ALL x:A. Q(x, f`x)"; |
202 by (res_inst_tac [("x", "lam x: A. THE y. Q(x,y)")] exI 1); |
200 by (res_inst_tac [("x", "lam x: A. THE y. Q(x,y)")] exI 1); |
203 by (rtac ballI 1); |
201 by (rtac ballI 1); |
204 by (stac beta 1); |
202 by (stac beta 1); |
205 by (assume_tac 1); |
203 by (assume_tac 1); |
208 |
206 |
209 |
207 |
210 (** Extensionality **) |
208 (** Extensionality **) |
211 |
209 |
212 (*Semi-extensionality!*) |
210 (*Semi-extensionality!*) |
213 val prems = goal ZF.thy |
211 val prems = Goal |
214 "[| f : Pi(A,B); g: Pi(C,D); A<=C; \ |
212 "[| f : Pi(A,B); g: Pi(C,D); A<=C; \ |
215 \ !!x. x:A ==> f`x = g`x |] ==> f<=g"; |
213 \ !!x. x:A ==> f`x = g`x |] ==> f<=g"; |
216 by (rtac subsetI 1); |
214 by (rtac subsetI 1); |
217 by (eresolve_tac (prems RL [Pi_memberD RS bexE]) 1); |
215 by (eresolve_tac (prems RL [Pi_memberD RS bexE]) 1); |
218 by (etac ssubst 1); |
216 by (etac ssubst 1); |
219 by (resolve_tac (prems RL [ssubst]) 1); |
217 by (resolve_tac (prems RL [ssubst]) 1); |
220 by (REPEAT (ares_tac (prems@[apply_Pair,subsetD]) 1)); |
218 by (REPEAT (ares_tac (prems@[apply_Pair,subsetD]) 1)); |
221 qed "fun_subset"; |
219 qed "fun_subset"; |
222 |
220 |
223 val prems = goal ZF.thy |
221 val prems = Goal |
224 "[| f : Pi(A,B); g: Pi(A,D); \ |
222 "[| f : Pi(A,B); g: Pi(A,D); \ |
225 \ !!x. x:A ==> f`x = g`x |] ==> f=g"; |
223 \ !!x. x:A ==> f`x = g`x |] ==> f=g"; |
226 by (REPEAT (ares_tac (prems @ (prems RL [sym]) @ |
224 by (REPEAT (ares_tac (prems @ (prems RL [sym]) @ |
227 [subset_refl,equalityI,fun_subset]) 1)); |
225 [subset_refl,equalityI,fun_subset]) 1)); |
228 qed "fun_extension"; |
226 qed "fun_extension"; |
229 |
227 |
230 goal ZF.thy "!!f A B. f : Pi(A,B) ==> (lam x:A. f`x) = f"; |
228 Goal "f : Pi(A,B) ==> (lam x:A. f`x) = f"; |
231 by (rtac fun_extension 1); |
229 by (rtac fun_extension 1); |
232 by (REPEAT (ares_tac [lam_type,apply_type,beta] 1)); |
230 by (REPEAT (ares_tac [lam_type,apply_type,beta] 1)); |
233 qed "eta"; |
231 qed "eta"; |
234 |
232 |
235 Addsimps [eta]; |
233 Addsimps [eta]; |
236 |
234 |
237 val fun_extension_iff = prove_goal ZF.thy |
235 Goal "[| f:Pi(A,B); g:Pi(A,C) |] ==> (ALL a:A. f`a = g`a) <-> f=g"; |
238 "!!z. [| f:Pi(A,B); g:Pi(A,C) |] ==> (ALL a:A. f`a = g`a) <-> f=g" |
236 by (blast_tac (claset() addIs [fun_extension]) 1); |
239 (fn _=> [ (blast_tac (claset() addIs [fun_extension]) 1) ]); |
237 qed "fun_extension_iff"; |
240 |
238 |
241 (*thanks to Mark Staples*) |
239 (*thanks to Mark Staples*) |
242 val fun_subset_eq = prove_goal ZF.thy |
240 val fun_subset_eq = prove_goal thy |
243 "!!z. [| f:Pi(A,B); g:Pi(A,C) |] ==> f <= g <-> (f = g)" |
241 "!!f. [| f:Pi(A,B); g:Pi(A,C) |] ==> f <= g <-> (f = g)" |
244 (fn _=> |
242 (fn _=> |
245 [ (rtac iffI 1), (asm_full_simp_tac ZF_ss 2), |
243 [ (rtac iffI 1), (asm_full_simp_tac ZF_ss 2), |
246 (rtac fun_extension 1), (REPEAT (atac 1)), |
244 (rtac fun_extension 1), (REPEAT (atac 1)), |
247 (dtac (apply_Pair RSN (2,subsetD)) 1), (REPEAT (atac 1)), |
245 (dtac (apply_Pair RSN (2,subsetD)) 1), (REPEAT (atac 1)), |
248 (rtac (apply_equality RS sym) 1), (REPEAT (atac 1)) ]); |
246 (rtac (apply_equality RS sym) 1), (REPEAT (atac 1)) ]); |
249 |
247 |
250 |
248 |
251 (*Every element of Pi(A,B) may be expressed as a lambda abstraction!*) |
249 (*Every element of Pi(A,B) may be expressed as a lambda abstraction!*) |
252 val prems = goal ZF.thy |
250 val prems = Goal |
253 "[| f: Pi(A,B); \ |
251 "[| f: Pi(A,B); \ |
254 \ !!b. [| ALL x:A. b(x):B(x); f = (lam x:A. b(x)) |] ==> P \ |
252 \ !!b. [| ALL x:A. b(x):B(x); f = (lam x:A. b(x)) |] ==> P \ |
255 \ |] ==> P"; |
253 \ |] ==> P"; |
256 by (resolve_tac prems 1); |
254 by (resolve_tac prems 1); |
257 by (rtac (eta RS sym) 2); |
255 by (rtac (eta RS sym) 2); |
259 qed "Pi_lamE"; |
257 qed "Pi_lamE"; |
260 |
258 |
261 |
259 |
262 (** Images of functions **) |
260 (** Images of functions **) |
263 |
261 |
264 goalw ZF.thy [lam_def] "!!C A. C <= A ==> (lam x:A. b(x)) `` C = {b(x). x:C}"; |
262 Goalw [lam_def] "C <= A ==> (lam x:A. b(x)) `` C = {b(x). x:C}"; |
265 by (Blast_tac 1); |
263 by (Blast_tac 1); |
266 qed "image_lam"; |
264 qed "image_lam"; |
267 |
265 |
268 goal ZF.thy "!!C A. [| f : Pi(A,B); C <= A |] ==> f``C = {f`x. x:C}"; |
266 Goal "[| f : Pi(A,B); C <= A |] ==> f``C = {f`x. x:C}"; |
269 by (etac (eta RS subst) 1); |
267 by (etac (eta RS subst) 1); |
270 by (asm_full_simp_tac (FOL_ss addsimps [beta, image_lam, subset_iff] |
268 by (asm_full_simp_tac (simpset() addsimps [image_lam, subset_iff]) 1); |
271 addcongs [RepFun_cong]) 1); |
|
272 qed "image_fun"; |
269 qed "image_fun"; |
273 |
270 |
274 Goal "[| f: Pi(A,B); x: A |] ==> f `` cons(x,y) = cons(f`x, f``y)"; |
271 Goal "[| f: Pi(A,B); x: A |] ==> f `` cons(x,y) = cons(f`x, f``y)"; |
275 by (blast_tac (claset() addDs [apply_equality, apply_Pair]) 1); |
272 by (blast_tac (claset() addDs [apply_equality, apply_Pair]) 1); |
276 qed "Pi_image_cons"; |
273 qed "Pi_image_cons"; |
277 |
274 |
278 |
275 |
279 (*** properties of "restrict" ***) |
276 (*** properties of "restrict" ***) |
280 |
277 |
281 goalw ZF.thy [restrict_def,lam_def] |
278 Goalw [restrict_def,lam_def] |
282 "!!f A. [| f: Pi(C,B); A<=C |] ==> restrict(f,A) <= f"; |
279 "[| f: Pi(C,B); A<=C |] ==> restrict(f,A) <= f"; |
283 by (blast_tac (claset() addIs [apply_Pair]) 1); |
280 by (blast_tac (claset() addIs [apply_Pair]) 1); |
284 qed "restrict_subset"; |
281 qed "restrict_subset"; |
285 |
282 |
286 val prems = goalw ZF.thy [restrict_def] |
283 val prems = Goalw [restrict_def] |
287 "[| !!x. x:A ==> f`x: B(x) |] ==> restrict(f,A) : Pi(A,B)"; |
284 "[| !!x. x:A ==> f`x: B(x) |] ==> restrict(f,A) : Pi(A,B)"; |
288 by (rtac lam_type 1); |
285 by (rtac lam_type 1); |
289 by (eresolve_tac prems 1); |
286 by (eresolve_tac prems 1); |
290 qed "restrict_type"; |
287 qed "restrict_type"; |
291 |
288 |
292 val [pi,subs] = goal ZF.thy |
289 Goal "[| f: Pi(C,B); A<=C |] ==> restrict(f,A) : Pi(A,B)"; |
293 "[| f: Pi(C,B); A<=C |] ==> restrict(f,A) : Pi(A,B)"; |
290 by (blast_tac (claset() addIs [apply_type, restrict_type]) 1); |
294 by (rtac (pi RS apply_type RS restrict_type) 1); |
|
295 by (etac (subs RS subsetD) 1); |
|
296 qed "restrict_type2"; |
291 qed "restrict_type2"; |
297 |
292 |
298 goalw ZF.thy [restrict_def] "!!a A. a : A ==> restrict(f,A) ` a = f`a"; |
293 Goalw [restrict_def] "a : A ==> restrict(f,A) ` a = f`a"; |
299 by (etac beta 1); |
294 by (etac beta 1); |
300 qed "restrict"; |
295 qed "restrict"; |
301 |
296 |
302 goalw ZF.thy [restrict_def] "restrict(f,0) = 0"; |
297 Goalw [restrict_def] "restrict(f,0) = 0"; |
303 by (Simp_tac 1); |
298 by (Simp_tac 1); |
304 qed "restrict_empty"; |
299 qed "restrict_empty"; |
305 |
300 |
306 Addsimps [restrict, restrict_empty]; |
301 Addsimps [restrict, restrict_empty]; |
307 |
302 |
308 (*NOT SAFE as a congruence rule for the simplifier! Can cause it to fail!*) |
303 (*NOT SAFE as a congruence rule for the simplifier! Can cause it to fail!*) |
309 val prems = goalw ZF.thy [restrict_def] |
304 val prems = Goalw [restrict_def] |
310 "[| A=B; !!x. x:B ==> f`x=g`x |] ==> restrict(f,A) = restrict(g,B)"; |
305 "[| A=B; !!x. x:B ==> f`x=g`x |] ==> restrict(f,A) = restrict(g,B)"; |
311 by (REPEAT (ares_tac (prems@[lam_cong]) 1)); |
306 by (REPEAT (ares_tac (prems@[lam_cong]) 1)); |
312 qed "restrict_eqI"; |
307 qed "restrict_eqI"; |
313 |
308 |
314 goalw ZF.thy [restrict_def, lam_def] "domain(restrict(f,C)) = C"; |
309 Goalw [restrict_def, lam_def] "domain(restrict(f,C)) = C"; |
315 by (Blast_tac 1); |
310 by (Blast_tac 1); |
316 qed "domain_restrict"; |
311 qed "domain_restrict"; |
317 |
312 |
318 val [prem] = goalw ZF.thy [restrict_def] |
313 Goalw [restrict_def] |
319 "A<=C ==> restrict(lam x:C. b(x), A) = (lam x:A. b(x))"; |
314 "A<=C ==> restrict(lam x:C. b(x), A) = (lam x:A. b(x))"; |
320 by (rtac (refl RS lam_cong) 1); |
315 by (rtac (refl RS lam_cong) 1); |
321 by (etac (prem RS subsetD RS beta) 1); (*easier than calling simp_tac*) |
316 by (set_mp_tac 1); |
|
317 by (Asm_simp_tac 1); |
322 qed "restrict_lam_eq"; |
318 qed "restrict_lam_eq"; |
323 |
319 |
324 |
320 |
325 |
321 |
326 (*** Unions of functions ***) |
322 (*** Unions of functions ***) |
327 |
323 |
328 (** The Union of a set of COMPATIBLE functions is a function **) |
324 (** The Union of a set of COMPATIBLE functions is a function **) |
329 |
325 |
330 goalw ZF.thy [function_def] |
326 Goalw [function_def] |
331 "!!S. [| ALL x:S. function(x); \ |
327 "[| ALL x:S. function(x); \ |
332 \ ALL x:S. ALL y:S. x<=y | y<=x |] ==> \ |
328 \ ALL x:S. ALL y:S. x<=y | y<=x |] ==> \ |
333 \ function(Union(S))"; |
329 \ function(Union(S))"; |
334 by (fast_tac (ZF_cs addSDs [bspec RS bspec]) 1); |
330 by (fast_tac (ZF_cs addSDs [bspec RS bspec]) 1); |
335 (*by (Blast_tac 1); takes too long...*) |
331 (*by (Blast_tac 1); takes too long...*) |
336 qed "function_Union"; |
332 qed "function_Union"; |
337 |
333 |
338 goalw ZF.thy [Pi_def] |
334 Goalw [Pi_def] |
339 "!!S. [| ALL f:S. EX C D. f:C->D; \ |
335 "[| ALL f:S. EX C D. f:C->D; \ |
340 \ ALL f:S. ALL y:S. f<=y | y<=f |] ==> \ |
336 \ ALL f:S. ALL y:S. f<=y | y<=f |] ==> \ |
341 \ Union(S) : domain(Union(S)) -> range(Union(S))"; |
337 \ Union(S) : domain(Union(S)) -> range(Union(S))"; |
342 by (blast_tac (subset_cs addSIs [rel_Union, function_Union]) 1); |
338 by (blast_tac (subset_cs addSIs [rel_Union, function_Union]) 1); |
343 qed "fun_Union"; |
339 qed "fun_Union"; |
344 |
340 |
347 |
343 |
348 val Un_rls = [Un_subset_iff, domain_Un_eq, SUM_Un_distrib1, prod_Un_distrib2, |
344 val Un_rls = [Un_subset_iff, domain_Un_eq, SUM_Un_distrib1, prod_Un_distrib2, |
349 Un_upper1 RSN (2, subset_trans), |
345 Un_upper1 RSN (2, subset_trans), |
350 Un_upper2 RSN (2, subset_trans)]; |
346 Un_upper2 RSN (2, subset_trans)]; |
351 |
347 |
352 goal ZF.thy "!!f. [| f: A->B; g: C->D; A Int C = 0 |] \ |
348 Goal "[| f: A->B; g: C->D; A Int C = 0 |] \ |
353 \ ==> (f Un g) : (A Un C) -> (B Un D)"; |
349 \ ==> (f Un g) : (A Un C) -> (B Un D)"; |
354 (*Prove the product and domain subgoals using distributive laws*) |
350 (*Prove the product and domain subgoals using distributive laws*) |
355 by (asm_full_simp_tac (simpset() addsimps [Pi_iff,extension]@Un_rls) 1); |
351 by (asm_full_simp_tac (simpset() addsimps [Pi_iff,extension]@Un_rls) 1); |
356 by (rewtac function_def); |
352 by (rewtac function_def); |
357 by (Blast_tac 1); |
353 by (Blast_tac 1); |
358 qed "fun_disjoint_Un"; |
354 qed "fun_disjoint_Un"; |
359 |
355 |
360 goal ZF.thy |
356 Goal "[| a:A; f: A->B; g: C->D; A Int C = 0 |] ==> \ |
361 "!!f g a. [| a:A; f: A->B; g: C->D; A Int C = 0 |] ==> \ |
|
362 \ (f Un g)`a = f`a"; |
357 \ (f Un g)`a = f`a"; |
363 by (rtac (apply_Pair RS UnI1 RS apply_equality) 1); |
358 by (rtac (apply_Pair RS UnI1 RS apply_equality) 1); |
364 by (REPEAT (ares_tac [fun_disjoint_Un] 1)); |
359 by (REPEAT (ares_tac [fun_disjoint_Un] 1)); |
365 qed "fun_disjoint_apply1"; |
360 qed "fun_disjoint_apply1"; |
366 |
361 |
367 goal ZF.thy |
362 Goal "[| c:C; f: A->B; g: C->D; A Int C = 0 |] ==> \ |
368 "!!f g c. [| c:C; f: A->B; g: C->D; A Int C = 0 |] ==> \ |
|
369 \ (f Un g)`c = g`c"; |
363 \ (f Un g)`c = g`c"; |
370 by (rtac (apply_Pair RS UnI2 RS apply_equality) 1); |
364 by (rtac (apply_Pair RS UnI2 RS apply_equality) 1); |
371 by (REPEAT (ares_tac [fun_disjoint_Un] 1)); |
365 by (REPEAT (ares_tac [fun_disjoint_Un] 1)); |
372 qed "fun_disjoint_apply2"; |
366 qed "fun_disjoint_apply2"; |
373 |
367 |
374 (** Domain and range of a function/relation **) |
368 (** Domain and range of a function/relation **) |
375 |
369 |
376 goalw ZF.thy [Pi_def] "!!f. f : Pi(A,B) ==> domain(f)=A"; |
370 Goalw [Pi_def] "f : Pi(A,B) ==> domain(f)=A"; |
377 by (Blast_tac 1); |
371 by (Blast_tac 1); |
378 qed "domain_of_fun"; |
372 qed "domain_of_fun"; |
379 |
373 |
380 goal ZF.thy "!!f. [| f : Pi(A,B); a: A |] ==> f`a : range(f)"; |
374 Goal "[| f : Pi(A,B); a: A |] ==> f`a : range(f)"; |
381 by (etac (apply_Pair RS rangeI) 1); |
375 by (etac (apply_Pair RS rangeI) 1); |
382 by (assume_tac 1); |
376 by (assume_tac 1); |
383 qed "apply_rangeI"; |
377 qed "apply_rangeI"; |
384 |
378 |
385 val [major] = goal ZF.thy "f : Pi(A,B) ==> f : A->range(f)"; |
379 Goal "f : Pi(A,B) ==> f : A->range(f)"; |
386 by (rtac (major RS Pi_type) 1); |
380 by (REPEAT (ares_tac [Pi_type, apply_rangeI] 1)); |
387 by (etac (major RS apply_rangeI) 1); |
|
388 qed "range_of_fun"; |
381 qed "range_of_fun"; |
389 |
382 |
390 (*** Extensions of functions ***) |
383 (*** Extensions of functions ***) |
391 |
384 |
392 Goal "[| f: A->B; c~:A |] ==> cons(<c,b>,f) : cons(c,A) -> cons(b,B)"; |
385 Goal "[| f: A->B; c~:A |] ==> cons(<c,b>,f) : cons(c,A) -> cons(b,B)"; |