58 intro: rtrancl_alt_subset_rtrancl rtrancl_subset_rtrancl_alt) |
58 intro: rtrancl_alt_subset_rtrancl rtrancl_subset_rtrancl_alt) |
59 |
59 |
60 |
60 |
61 definition |
61 definition |
62 rtran_closure_mem :: "[i=>o,i,i,i] => o" where |
62 rtran_closure_mem :: "[i=>o,i,i,i] => o" where |
63 --\<open>The property of belonging to @{text "rtran_closure(r)"}\<close> |
63 \<comment>\<open>The property of belonging to \<open>rtran_closure(r)\<close>\<close> |
64 "rtran_closure_mem(M,A,r,p) == |
64 "rtran_closure_mem(M,A,r,p) == |
65 \<exists>nnat[M]. \<exists>n[M]. \<exists>n'[M]. |
65 \<exists>nnat[M]. \<exists>n[M]. \<exists>n'[M]. |
66 omega(M,nnat) & n\<in>nnat & successor(M,n,n') & |
66 omega(M,nnat) & n\<in>nnat & successor(M,n,n') & |
67 (\<exists>f[M]. typed_function(M,n',A,f) & |
67 (\<exists>f[M]. typed_function(M,n',A,f) & |
68 (\<exists>x[M]. \<exists>y[M]. \<exists>zero[M]. pair(M,x,y,p) & empty(M,zero) & |
68 (\<exists>x[M]. \<exists>y[M]. \<exists>zero[M]. pair(M,x,y,p) & empty(M,zero) & |
138 |
138 |
139 lemma (in M_trancl) wellfounded_trancl_separation': |
139 lemma (in M_trancl) wellfounded_trancl_separation': |
140 "[| M(r); M(Z) |] ==> separation (M, \<lambda>x. \<exists>w[M]. w \<in> Z & <w,x> \<in> r^+)" |
140 "[| M(r); M(Z) |] ==> separation (M, \<lambda>x. \<exists>w[M]. w \<in> Z & <w,x> \<in> r^+)" |
141 by (insert wellfounded_trancl_separation [of r Z], simp) |
141 by (insert wellfounded_trancl_separation [of r Z], simp) |
142 |
142 |
143 text\<open>Alternative proof of @{text wf_on_trancl}; inspiration for the |
143 text\<open>Alternative proof of \<open>wf_on_trancl\<close>; inspiration for the |
144 relativized version. Original version is on theory WF.\<close> |
144 relativized version. Original version is on theory WF.\<close> |
145 lemma "[| wf[A](r); r-``A \<subseteq> A |] ==> wf[A](r^+)" |
145 lemma "[| wf[A](r); r-``A \<subseteq> A |] ==> wf[A](r^+)" |
146 apply (simp add: wf_on_def wf_def) |
146 apply (simp add: wf_on_def wf_def) |
147 apply (safe intro!: equalityI) |
147 apply (safe intro!: equalityI) |
148 apply (drule_tac x = "{x\<in>A. \<exists>w. \<langle>w,x\<rangle> \<in> r^+ & w \<in> Z}" in spec) |
148 apply (drule_tac x = "{x\<in>A. \<exists>w. \<langle>w,x\<rangle> \<in> r^+ & w \<in> Z}" in spec) |
198 apply (clarify, rule_tac x=x in rexI) |
198 apply (clarify, rule_tac x=x in rexI) |
199 apply (simp_all add: the_recfun_eq trans_trancl trancl_subset_times) |
199 apply (simp_all add: the_recfun_eq trans_trancl trancl_subset_times) |
200 done |
200 done |
201 |
201 |
202 |
202 |
203 text\<open>Assuming @{term r} is transitive simplifies the occurrences of @{text H}. |
203 text\<open>Assuming @{term r} is transitive simplifies the occurrences of \<open>H\<close>. |
204 The premise @{term "relation(r)"} is necessary |
204 The premise @{term "relation(r)"} is necessary |
205 before we can replace @{term "r^+"} by @{term r}.\<close> |
205 before we can replace @{term "r^+"} by @{term r}.\<close> |
206 theorem (in M_trancl) trans_wfrec_relativize: |
206 theorem (in M_trancl) trans_wfrec_relativize: |
207 "[|wf(r); trans(r); relation(r); M(r); M(a); |
207 "[|wf(r); trans(r); relation(r); M(r); M(a); |
208 wfrec_replacement(M,MH,r); relation2(M,MH,H); |
208 wfrec_replacement(M,MH,r); relation2(M,MH,H); |
236 done |
236 done |
237 |
237 |
238 |
238 |
239 subsection\<open>M is closed under well-founded recursion\<close> |
239 subsection\<open>M is closed under well-founded recursion\<close> |
240 |
240 |
241 text\<open>Lemma with the awkward premise mentioning @{text wfrec}.\<close> |
241 text\<open>Lemma with the awkward premise mentioning \<open>wfrec\<close>.\<close> |
242 lemma (in M_trancl) wfrec_closed_lemma [rule_format]: |
242 lemma (in M_trancl) wfrec_closed_lemma [rule_format]: |
243 "[|wf(r); M(r); |
243 "[|wf(r); M(r); |
244 strong_replacement(M, \<lambda>x y. y = \<langle>x, wfrec(r, x, H)\<rangle>); |
244 strong_replacement(M, \<lambda>x y. y = \<langle>x, wfrec(r, x, H)\<rangle>); |
245 \<forall>x[M]. \<forall>g[M]. function(g) \<longrightarrow> M(H(x,g)) |] |
245 \<forall>x[M]. \<forall>g[M]. function(g) \<longrightarrow> M(H(x,g)) |] |
246 ==> M(a) \<longrightarrow> M(wfrec(r,a,H))" |
246 ==> M(a) \<longrightarrow> M(wfrec(r,a,H))" |