src/ZF/Constructible/WF_absolute.thy
changeset 61798 27f3c10b0b50
parent 60770 240563fbf41d
child 67443 3abf6a722518
equal deleted inserted replaced
61797:458b4e3720ab 61798:27f3c10b0b50
    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))"