136 val apply_recfun = result(); |
132 val apply_recfun = result(); |
137 |
133 |
138 (*eresolve_tac transD solves <a,b>:r using transitivity AT MOST ONCE |
134 (*eresolve_tac transD solves <a,b>:r using transitivity AT MOST ONCE |
139 spec RS mp instantiates induction hypotheses*) |
135 spec RS mp instantiates induction hypotheses*) |
140 fun indhyp_tac hyps = |
136 fun indhyp_tac hyps = |
141 ares_tac (TrueI::hyps) ORELSE' |
137 resolve_tac (TrueI::refl::hyps) ORELSE' |
142 (cut_facts_tac hyps THEN' |
138 (cut_facts_tac hyps THEN' |
143 DEPTH_SOLVE_1 o (ares_tac [TrueI, ballI] ORELSE' |
139 DEPTH_SOLVE_1 o (ares_tac [TrueI, ballI] ORELSE' |
144 eresolve_tac [underD, transD, spec RS mp])); |
140 eresolve_tac [underD, transD, spec RS mp])); |
145 |
141 |
146 (*** NOTE! some simplifications need a different auto_tac!! ***) |
142 (*** NOTE! some simplifications need a different solver!! ***) |
147 val wf_super_ss = wf_ss setauto indhyp_tac; |
143 val wf_super_ss = ZF_ss setsolver indhyp_tac; |
148 |
144 |
149 val prems = goalw WF.thy [is_recfun_def] |
145 val prems = goalw WF.thy [is_recfun_def] |
150 "[| wf(r); trans(r); is_recfun(r,a,H,f); is_recfun(r,b,H,g) |] ==> \ |
146 "[| wf(r); trans(r); is_recfun(r,a,H,f); is_recfun(r,b,H,g) |] ==> \ |
151 \ <x,a>:r --> <x,b>:r --> f`x=g`x"; |
147 \ <x,a>:r --> <x,b>:r --> f`x=g`x"; |
152 by (cut_facts_tac prems 1); |
148 by (cut_facts_tac prems 1); |
153 by (wf_ind_tac "x" prems 1); |
149 by (wf_ind_tac "x" prems 1); |
154 by (REPEAT (rtac impI 1 ORELSE etac ssubst 1)); |
150 by (REPEAT (rtac impI 1 ORELSE etac ssubst 1)); |
155 by (rewtac restrict_def); |
151 by (rewtac restrict_def); |
156 by (ASM_SIMP_TAC (wf_super_ss addrews [vimage_singleton_iff]) 1); |
152 by (asm_simp_tac (wf_super_ss addsimps [vimage_singleton_iff]) 1); |
157 val is_recfun_equal_lemma = result(); |
153 val is_recfun_equal_lemma = result(); |
158 val is_recfun_equal = standard (is_recfun_equal_lemma RS mp RS mp); |
154 val is_recfun_equal = standard (is_recfun_equal_lemma RS mp RS mp); |
159 |
155 |
160 val prems as [wfr,transr,recf,recg,_] = goal WF.thy |
156 val prems as [wfr,transr,recf,recg,_] = goal WF.thy |
161 "[| wf(r); trans(r); \ |
157 "[| wf(r); trans(r); \ |
163 \ restrict(f, r-``{b}) = g"; |
159 \ restrict(f, r-``{b}) = g"; |
164 by (cut_facts_tac prems 1); |
160 by (cut_facts_tac prems 1); |
165 by (rtac (consI1 RS restrict_type RS fun_extension) 1); |
161 by (rtac (consI1 RS restrict_type RS fun_extension) 1); |
166 by (etac is_recfun_type 1); |
162 by (etac is_recfun_type 1); |
167 by (ALLGOALS |
163 by (ALLGOALS |
168 (ASM_SIMP_TAC (wf_super_ss addrews |
164 (asm_simp_tac (wf_super_ss addsimps |
169 [ [wfr,transr,recf,recg] MRS is_recfun_equal ]))); |
165 [ [wfr,transr,recf,recg] MRS is_recfun_equal ]))); |
170 val is_recfun_cut = result(); |
166 val is_recfun_cut = result(); |
171 |
167 |
172 (*** Main Existence Lemma ***) |
168 (*** Main Existence Lemma ***) |
173 |
169 |
193 by (wf_ind_tac "a" prems 1); |
189 by (wf_ind_tac "a" prems 1); |
194 by (res_inst_tac [("f", "lam y: r-``{a1}. wftrec(r,y,H)")] is_the_recfun 1); |
190 by (res_inst_tac [("f", "lam y: r-``{a1}. wftrec(r,y,H)")] is_the_recfun 1); |
195 by (REPEAT (assume_tac 2)); |
191 by (REPEAT (assume_tac 2)); |
196 by (rewrite_goals_tac [is_recfun_def, wftrec_def]); |
192 by (rewrite_goals_tac [is_recfun_def, wftrec_def]); |
197 (*Applying the substitution: must keep the quantified assumption!!*) |
193 (*Applying the substitution: must keep the quantified assumption!!*) |
198 by (REPEAT (dtac underD 1 ORELSE resolve_tac [refl, lam_cong, H_cong] 1)); |
194 by (REPEAT (dtac underD 1 ORELSE resolve_tac [refl, lam_cong] 1)); |
199 by (fold_tac [is_recfun_def]); |
195 by (fold_tac [is_recfun_def]); |
200 by (rtac (consI1 RS restrict_type RSN (2,fun_extension)) 1); |
196 by (rtac (consI1 RS restrict_type RSN (2,fun_extension) RS subst_context) 1); |
201 by (rtac is_recfun_type 1); |
197 by (rtac is_recfun_type 1); |
202 by (ALLGOALS |
198 by (ALLGOALS |
203 (ASM_SIMP_TAC |
199 (asm_simp_tac |
204 (wf_super_ss addrews [underI RS beta, apply_recfun, is_recfun_cut]))); |
200 (wf_super_ss addsimps [underI RS beta, apply_recfun, is_recfun_cut]))); |
205 val unfold_the_recfun = result(); |
201 val unfold_the_recfun = result(); |
206 |
202 |
207 |
203 |
208 (*** Unfolding wftrec ***) |
204 (*** Unfolding wftrec ***) |
209 |
205 |
212 \ restrict(the_recfun(r,a,H), r-``{b}) = the_recfun(r,b,H)"; |
208 \ restrict(the_recfun(r,a,H), r-``{b}) = the_recfun(r,b,H)"; |
213 by (REPEAT (ares_tac (prems @ [is_recfun_cut, unfold_the_recfun]) 1)); |
209 by (REPEAT (ares_tac (prems @ [is_recfun_cut, unfold_the_recfun]) 1)); |
214 val the_recfun_cut = result(); |
210 val the_recfun_cut = result(); |
215 |
211 |
216 (*NOT SUITABLE FOR REWRITING since it is recursive!*) |
212 (*NOT SUITABLE FOR REWRITING since it is recursive!*) |
217 val prems = goalw WF.thy [wftrec_def] |
213 goalw WF.thy [wftrec_def] |
218 "[| wf(r); trans(r) |] ==> \ |
214 "!!r. [| wf(r); trans(r) |] ==> \ |
219 \ wftrec(r,a,H) = H(a, lam x: r-``{a}. wftrec(r,x,H))"; |
215 \ wftrec(r,a,H) = H(a, lam x: r-``{a}. wftrec(r,x,H))"; |
220 by (rtac (rewrite_rule [is_recfun_def] unfold_the_recfun RS ssubst) 1); |
216 by (rtac (rewrite_rule [is_recfun_def] unfold_the_recfun RS ssubst) 1); |
221 by (ALLGOALS (ASM_SIMP_TAC |
217 by (ALLGOALS (asm_simp_tac |
222 (wf_ss addrews (prems@[vimage_singleton_iff RS iff_sym, |
218 (ZF_ss addsimps [vimage_singleton_iff RS iff_sym, the_recfun_cut]))); |
223 the_recfun_cut])))); |
|
224 val wftrec = result(); |
219 val wftrec = result(); |
225 |
220 |
226 (** Removal of the premise trans(r) **) |
221 (** Removal of the premise trans(r) **) |
227 |
222 |
228 (*NOT SUITABLE FOR REWRITING since it is recursive!*) |
223 (*NOT SUITABLE FOR REWRITING since it is recursive!*) |
229 val [wfr] = goalw WF.thy [wfrec_def] |
224 val [wfr] = goalw WF.thy [wfrec_def] |
230 "wf(r) ==> wfrec(r,a,H) = H(a, lam x:r-``{a}. wfrec(r,x,H))"; |
225 "wf(r) ==> wfrec(r,a,H) = H(a, lam x:r-``{a}. wfrec(r,x,H))"; |
231 by (rtac (wfr RS wf_trancl RS wftrec RS ssubst) 1); |
226 by (rtac (wfr RS wf_trancl RS wftrec RS ssubst) 1); |
232 by (rtac trans_trancl 1); |
227 by (rtac trans_trancl 1); |
233 by (rtac (refl RS H_cong) 1); |
228 by (rtac (vimage_pair_mono RS restrict_lam_eq RS subst_context) 1); |
234 by (rtac (vimage_pair_mono RS restrict_lam_eq) 1); |
|
235 by (etac r_into_trancl 1); |
229 by (etac r_into_trancl 1); |
236 by (rtac subset_refl 1); |
230 by (rtac subset_refl 1); |
237 val wfrec = result(); |
231 val wfrec = result(); |
238 |
232 |
239 (*This form avoids giant explosions in proofs. NOTE USE OF == *) |
233 (*This form avoids giant explosions in proofs. NOTE USE OF == *) |
251 by (res_inst_tac [("a","a")] wf_induct2 1); |
245 by (res_inst_tac [("a","a")] wf_induct2 1); |
252 by (rtac (wfrec RS ssubst) 4); |
246 by (rtac (wfrec RS ssubst) 4); |
253 by (REPEAT (ares_tac (prems@[lam_type]) 1 |
247 by (REPEAT (ares_tac (prems@[lam_type]) 1 |
254 ORELSE eresolve_tac [spec RS mp, underD] 1)); |
248 ORELSE eresolve_tac [spec RS mp, underD] 1)); |
255 val wfrec_type = result(); |
249 val wfrec_type = result(); |
256 |
|
257 val prems = goalw WF.thy [wfrec_def,wftrec_def,the_recfun_def,is_recfun_def] |
|
258 "[| r=r'; !!x u. H(x,u)=H'(x,u); a=a' |] \ |
|
259 \ ==> wfrec(r,a,H)=wfrec(r',a',H')"; |
|
260 by (EVERY1 (map rtac (prems RL [subst]))); |
|
261 by (SIMP_TAC (wf_ss addrews (prems RL [sym])) 1); |
|
262 val wfrec_cong = result(); |
|