src/ZF/Constructible/WF_absolute.thy
changeset 13339 0f89104dd377
parent 13324 39d1b3a4c6f4
child 13348 374d05460db4
equal deleted inserted replaced
13338:20ca66539bef 13339:0f89104dd377
    19 
    19 
    20 lemma wfrank: "wf(r) ==> wfrank(r,a) = (\<Union>y \<in> r-``{a}. succ(wfrank(r,y)))"
    20 lemma wfrank: "wf(r) ==> wfrank(r,a) = (\<Union>y \<in> r-``{a}. succ(wfrank(r,y)))"
    21 by (subst wfrank_def [THEN def_wfrec], simp_all)
    21 by (subst wfrank_def [THEN def_wfrec], simp_all)
    22 
    22 
    23 lemma Ord_wfrank: "wf(r) ==> Ord(wfrank(r,a))"
    23 lemma Ord_wfrank: "wf(r) ==> Ord(wfrank(r,a))"
    24 apply (rule_tac a="a" in wf_induct, assumption)
    24 apply (rule_tac a=a in wf_induct, assumption)
    25 apply (subst wfrank, assumption)
    25 apply (subst wfrank, assumption)
    26 apply (rule Ord_succ [THEN Ord_UN], blast)
    26 apply (rule Ord_succ [THEN Ord_UN], blast)
    27 done
    27 done
    28 
    28 
    29 lemma wfrank_lt: "[|wf(r); <a,b> \<in> r|] ==> wfrank(r,a) < wfrank(r,b)"
    29 lemma wfrank_lt: "[|wf(r); <a,b> \<in> r|] ==> wfrank(r,a) < wfrank(r,b)"
    30 apply (rule_tac a1 = "b" in wfrank [THEN ssubst], assumption)
    30 apply (rule_tac a1 = b in wfrank [THEN ssubst], assumption)
    31 apply (rule UN_I [THEN ltI])
    31 apply (rule UN_I [THEN ltI])
    32 apply (simp add: Ord_wfrank vimage_iff)+
    32 apply (simp add: Ord_wfrank vimage_iff)+
    33 done
    33 done
    34 
    34 
    35 lemma Ord_wftype: "wf(r) ==> Ord(wftype(r))"
    35 lemma Ord_wftype: "wf(r) ==> Ord(wftype(r))"
   139           (\<exists>n[M]. n\<in>nat & 
   139           (\<exists>n[M]. n\<in>nat & 
   140            (\<exists>f[M]. f \<in> succ(n) -> A &
   140            (\<exists>f[M]. f \<in> succ(n) -> A &
   141             (\<exists>x[M]. \<exists>y[M]. p = <x,y> & f`0 = x & f`n = y) &
   141             (\<exists>x[M]. \<exists>y[M]. p = <x,y> & f`0 = x & f`n = y) &
   142                            (\<forall>i\<in>n. <f`i, f`succ(i)> \<in> r)))"
   142                            (\<forall>i\<in>n. <f`i, f`succ(i)> \<in> r)))"
   143 apply (simp add: rtran_closure_mem_def typed_apply_abs
   143 apply (simp add: rtran_closure_mem_def typed_apply_abs
   144                  Ord_succ_mem_iff nat_0_le [THEN ltD])
   144                  Ord_succ_mem_iff nat_0_le [THEN ltD], blast) 
   145 apply (blast intro: elim:); 
       
   146 done
   145 done
   147 
   146 
   148 locale M_trancl = M_axioms +
   147 locale M_trancl = M_axioms +
   149   assumes rtrancl_separation:
   148   assumes rtrancl_separation:
   150 	 "[| M(r); M(A) |] ==> separation (M, rtran_closure_mem(M,A,r))"
   149 	 "[| M(r); M(A) |] ==> separation (M, rtran_closure_mem(M,A,r))"
   157 
   156 
   158 lemma (in M_trancl) rtran_closure_rtrancl:
   157 lemma (in M_trancl) rtran_closure_rtrancl:
   159      "M(r) ==> rtran_closure(M,r,rtrancl(r))"
   158      "M(r) ==> rtran_closure(M,r,rtrancl(r))"
   160 apply (simp add: rtran_closure_def rtran_closure_mem_iff 
   159 apply (simp add: rtran_closure_def rtran_closure_mem_iff 
   161                  rtrancl_alt_eq_rtrancl [symmetric] rtrancl_alt_def)
   160                  rtrancl_alt_eq_rtrancl [symmetric] rtrancl_alt_def)
   162 apply (auto simp add: nat_0_le [THEN ltD] apply_funtype); 
   161 apply (auto simp add: nat_0_le [THEN ltD] apply_funtype) 
   163 done
   162 done
   164 
   163 
   165 lemma (in M_trancl) rtrancl_closed [intro,simp]:
   164 lemma (in M_trancl) rtrancl_closed [intro,simp]:
   166      "M(r) ==> M(rtrancl(r))"
   165      "M(r) ==> M(rtrancl(r))"
   167 apply (insert rtrancl_separation [of r "field(r)"])
   166 apply (insert rtrancl_separation [of r "field(r)"])
   175  txt{*Proving the right-to-left implication*}
   174  txt{*Proving the right-to-left implication*}
   176  prefer 2 apply (blast intro: rtran_closure_rtrancl)
   175  prefer 2 apply (blast intro: rtran_closure_rtrancl)
   177 apply (rule M_equalityI)
   176 apply (rule M_equalityI)
   178 apply (simp add: rtran_closure_def rtrancl_alt_eq_rtrancl [symmetric]
   177 apply (simp add: rtran_closure_def rtrancl_alt_eq_rtrancl [symmetric]
   179                  rtrancl_alt_def rtran_closure_mem_iff)
   178                  rtrancl_alt_def rtran_closure_mem_iff)
   180 apply (auto simp add: nat_0_le [THEN ltD] apply_funtype); 
   179 apply (auto simp add: nat_0_le [THEN ltD] apply_funtype) 
   181 done
   180 done
   182 
   181 
   183 lemma (in M_trancl) trancl_closed [intro,simp]:
   182 lemma (in M_trancl) trancl_closed [intro,simp]:
   184      "M(r) ==> M(trancl(r))"
   183      "M(r) ==> M(trancl(r))"
   185 by (simp add: trancl_def comp_closed rtrancl_closed)
   184 by (simp add: trancl_def comp_closed rtrancl_closed)
   233 rank function.*}
   232 rank function.*}
   234 
   233 
   235 
   234 
   236 (*NEEDS RELATIVIZATION*)
   235 (*NEEDS RELATIVIZATION*)
   237 locale M_wfrank = M_trancl +
   236 locale M_wfrank = M_trancl +
   238   assumes wfrank_separation':
   237   assumes wfrank_separation:
   239      "M(r) ==>
   238      "M(r) ==>
   240 	separation
   239       separation (M, \<lambda>x. 
   241 	   (M, \<lambda>x. ~ (\<exists>f[M]. is_recfun(r^+, x, %x f. range(f), f)))"
   240          ~ (\<exists>f[M]. M_is_recfun(M, r^+, x, %mm x f y. y = range(f), f)))"
   242  and wfrank_strong_replacement':
   241  and wfrank_strong_replacement':
   243      "M(r) ==>
   242      "M(r) ==>
   244       strong_replacement(M, \<lambda>x z. \<exists>y[M]. \<exists>f[M]. 
   243       strong_replacement(M, \<lambda>x z. \<exists>y[M]. \<exists>f[M]. 
   245 		  pair(M,x,y,z) & is_recfun(r^+, x, %x f. range(f), f) &
   244 		  pair(M,x,y,z) & is_recfun(r^+, x, %x f. range(f), f) &
   246 		  y = range(f))"
   245 		  y = range(f))"
   247  and Ord_wfrank_separation:
   246  and Ord_wfrank_separation:
   248      "M(r) ==>
   247      "M(r) ==>
   249       separation (M, \<lambda>x. ~ (\<forall>f. M(f) \<longrightarrow>
   248       separation (M, \<lambda>x. ~ (\<forall>f. M(f) \<longrightarrow>
   250                        is_recfun(r^+, x, \<lambda>x. range, f) \<longrightarrow> Ord(range(f))))"
   249                        is_recfun(r^+, x, \<lambda>x. range, f) \<longrightarrow> Ord(range(f))))" 
       
   250 
       
   251 lemma (in M_wfrank) wfrank_separation':
       
   252      "M(r) ==>
       
   253       separation
       
   254 	   (M, \<lambda>x. ~ (\<exists>f[M]. is_recfun(r^+, x, %x f. range(f), f)))"
       
   255 apply (insert wfrank_separation [of r])
       
   256 apply (simp add: is_recfun_iff_M [of concl: _ _ "%x. range", THEN iff_sym])
       
   257 done
   251 
   258 
   252 text{*This function, defined using replacement, is a rank function for
   259 text{*This function, defined using replacement, is a rank function for
   253 well-founded relations within the class M.*}
   260 well-founded relations within the class M.*}
   254 constdefs
   261 constdefs
   255  wellfoundedrank :: "[i=>o,i,i] => i"
   262  wellfoundedrank :: "[i=>o,i,i] => i"