equal
deleted
inserted
replaced
60 !!B. ALL x:A. (ALL y. <y,x>: r --> y:B) --> x:B ==> A<=B *) |
60 !!B. ALL x:A. (ALL y. <y,x>: r --> y:B) --> x:B ==> A<=B *) |
61 val [prem] = goal WF.thy |
61 val [prem] = goal WF.thy |
62 "[| !!y B. [| ALL x:A. (ALL y:A. <y,x>:r --> y:B) --> x:B; y:A \ |
62 "[| !!y B. [| ALL x:A. (ALL y:A. <y,x>:r --> y:B) --> x:B; y:A \ |
63 \ |] ==> y:B |] \ |
63 \ |] ==> y:B |] \ |
64 \ ==> wf[A](r)"; |
64 \ ==> wf[A](r)"; |
65 br wf_onI 1; |
65 by (rtac wf_onI 1); |
66 by (res_inst_tac [ ("c", "u") ] (prem RS DiffE) 1); |
66 by (res_inst_tac [ ("c", "u") ] (prem RS DiffE) 1); |
67 by (contr_tac 3); |
67 by (contr_tac 3); |
68 by (fast_tac ZF_cs 2); |
68 by (fast_tac ZF_cs 2); |
69 by (fast_tac ZF_cs 1); |
69 by (fast_tac ZF_cs 1); |
70 val wf_onI2 = result(); |
70 val wf_onI2 = result(); |
129 val [subs,indhyp] = goal WF.thy |
129 val [subs,indhyp] = goal WF.thy |
130 "[| field(r)<=A; \ |
130 "[| field(r)<=A; \ |
131 \ !!y B. [| ALL x:A. (ALL y:A. <y,x>:r --> y:B) --> x:B; y:A \ |
131 \ !!y B. [| ALL x:A. (ALL y:A. <y,x>:r --> y:B) --> x:B; y:A \ |
132 \ |] ==> y:B |] \ |
132 \ |] ==> y:B |] \ |
133 \ ==> wf(r)"; |
133 \ ==> wf(r)"; |
134 br ([wf_onI2, subs] MRS (wf_on_subset_A RS wf_on_field_imp_wf)) 1; |
134 by (rtac ([wf_onI2, subs] MRS (wf_on_subset_A RS wf_on_field_imp_wf)) 1); |
135 by (REPEAT (ares_tac [indhyp] 1)); |
135 by (REPEAT (ares_tac [indhyp] 1)); |
136 val wfI2 = result(); |
136 val wfI2 = result(); |
137 |
137 |
138 |
138 |
139 (*** Properties of well-founded relations ***) |
139 (*** Properties of well-founded relations ***) |
146 goal WF.thy "!!r. [| wf(r); <a,x>:r; <x,a>:r |] ==> P"; |
146 goal WF.thy "!!r. [| wf(r); <a,x>:r; <x,a>:r |] ==> P"; |
147 by (subgoal_tac "ALL x. <a,x>:r --> <x,a>:r --> P" 1); |
147 by (subgoal_tac "ALL x. <a,x>:r --> <x,a>:r --> P" 1); |
148 by (wf_ind_tac "a" [] 2); |
148 by (wf_ind_tac "a" [] 2); |
149 by (fast_tac ZF_cs 2); |
149 by (fast_tac ZF_cs 2); |
150 by (fast_tac FOL_cs 1); |
150 by (fast_tac FOL_cs 1); |
151 val wf_anti_sym = result(); |
151 val wf_asym = result(); |
152 |
152 |
153 goal WF.thy "!!r. [| wf[A](r); a: A |] ==> <a,a> ~: r"; |
153 goal WF.thy "!!r. [| wf[A](r); a: A |] ==> <a,a> ~: r"; |
154 by (wf_on_ind_tac "a" [] 1); |
154 by (wf_on_ind_tac "a" [] 1); |
155 by (fast_tac ZF_cs 1); |
155 by (fast_tac ZF_cs 1); |
156 val wf_on_not_refl = result(); |
156 val wf_on_not_refl = result(); |
158 goal WF.thy "!!r. [| wf[A](r); <a,b>:r; <b,a>:r; a:A; b:A |] ==> P"; |
158 goal WF.thy "!!r. [| wf[A](r); <a,b>:r; <b,a>:r; a:A; b:A |] ==> P"; |
159 by (subgoal_tac "ALL y:A. <a,y>:r --> <y,a>:r --> P" 1); |
159 by (subgoal_tac "ALL y:A. <a,y>:r --> <y,a>:r --> P" 1); |
160 by (wf_on_ind_tac "a" [] 2); |
160 by (wf_on_ind_tac "a" [] 2); |
161 by (fast_tac ZF_cs 2); |
161 by (fast_tac ZF_cs 2); |
162 by (fast_tac ZF_cs 1); |
162 by (fast_tac ZF_cs 1); |
163 val wf_on_anti_sym = result(); |
163 val wf_on_asym = result(); |
164 |
164 |
165 (*Needed to prove well_ordI. Could also reason that wf[A](r) means |
165 (*Needed to prove well_ordI. Could also reason that wf[A](r) means |
166 wf(r Int A*A); thus wf( (r Int A*A)^+ ) and use wf_not_refl *) |
166 wf(r Int A*A); thus wf( (r Int A*A)^+ ) and use wf_not_refl *) |
167 goal WF.thy |
167 goal WF.thy |
168 "!!r. [| wf[A](r); <a,b>:r; <b,c>:r; <c,a>:r; a:A; b:A; c:A |] ==> P"; |
168 "!!r. [| wf[A](r); <a,b>:r; <b,c>:r; <c,a>:r; a:A; b:A; c:A |] ==> P"; |
178 val bchain_tac = EVERY' [rtac (bspec RS mp), assume_tac, assume_tac ]; |
178 val bchain_tac = EVERY' [rtac (bspec RS mp), assume_tac, assume_tac ]; |
179 |
179 |
180 (*transitive closure of a WF relation is WF provided A is downwards closed*) |
180 (*transitive closure of a WF relation is WF provided A is downwards closed*) |
181 val [wfr,subs] = goal WF.thy |
181 val [wfr,subs] = goal WF.thy |
182 "[| wf[A](r); r-``A <= A |] ==> wf[A](r^+)"; |
182 "[| wf[A](r); r-``A <= A |] ==> wf[A](r^+)"; |
183 br wf_onI2 1; |
183 by (rtac wf_onI2 1); |
184 by (bchain_tac 1); |
184 by (bchain_tac 1); |
185 by (eres_inst_tac [("a","y")] (wfr RS wf_on_induct) 1); |
185 by (eres_inst_tac [("a","y")] (wfr RS wf_on_induct) 1); |
186 by (rtac (impI RS ballI) 1); |
186 by (rtac (impI RS ballI) 1); |
187 by (etac tranclE 1); |
187 by (etac tranclE 1); |
188 by (etac (bspec RS mp) 1 THEN assume_tac 1); |
188 by (etac (bspec RS mp) 1 THEN assume_tac 1); |
192 by (best_tac ZF_cs 1); |
192 by (best_tac ZF_cs 1); |
193 val wf_on_trancl = result(); |
193 val wf_on_trancl = result(); |
194 |
194 |
195 goal WF.thy "!!r. wf(r) ==> wf(r^+)"; |
195 goal WF.thy "!!r. wf(r) ==> wf(r^+)"; |
196 by (asm_full_simp_tac (ZF_ss addsimps [wf_iff_wf_on_field]) 1); |
196 by (asm_full_simp_tac (ZF_ss addsimps [wf_iff_wf_on_field]) 1); |
197 br (trancl_type RS field_rel_subset RSN (2, wf_on_subset_A)) 1; |
197 by (rtac (trancl_type RS field_rel_subset RSN (2, wf_on_subset_A)) 1); |
198 be wf_on_trancl 1; |
198 by (etac wf_on_trancl 1); |
199 by (fast_tac ZF_cs 1); |
199 by (fast_tac ZF_cs 1); |
200 val wf_trancl = result(); |
200 val wf_trancl = result(); |
201 |
201 |
202 |
202 |
203 |
203 |
340 |
340 |
341 |
341 |
342 goalw WF.thy [wf_on_def, wfrec_on_def] |
342 goalw WF.thy [wf_on_def, wfrec_on_def] |
343 "!!A r. [| wf[A](r); a: A |] ==> \ |
343 "!!A r. [| wf[A](r); a: A |] ==> \ |
344 \ wfrec[A](r,a,H) = H(a, lam x: (r-``{a}) Int A. wfrec[A](r,x,H))"; |
344 \ wfrec[A](r,a,H) = H(a, lam x: (r-``{a}) Int A. wfrec[A](r,x,H))"; |
345 be (wfrec RS trans) 1; |
345 by (etac (wfrec RS trans) 1); |
346 by (asm_simp_tac (ZF_ss addsimps [vimage_Int_square, cons_subset_iff]) 1); |
346 by (asm_simp_tac (ZF_ss addsimps [vimage_Int_square, cons_subset_iff]) 1); |
347 val wfrec_on = result(); |
347 val wfrec_on = result(); |
348 |
348 |