src/ZF/WF.thy
changeset 76217 8655344f1cf6
parent 76216 9fc34f76b4e8
child 76419 f20865ad6319
equal deleted inserted replaced
76216:9fc34f76b4e8 76217:8655344f1cf6
    80 text\<open>If every non-empty subset of \<^term>\<open>A\<close> has an \<^term>\<open>r\<close>-minimal element
    80 text\<open>If every non-empty subset of \<^term>\<open>A\<close> has an \<^term>\<open>r\<close>-minimal element
    81    then we have \<^term>\<open>wf[A](r)\<close>.\<close>
    81    then we have \<^term>\<open>wf[A](r)\<close>.\<close>
    82 lemma wf_onI:
    82 lemma wf_onI:
    83  assumes prem: "\<And>Z u. \<lbrakk>Z<=A;  u \<in> Z;  \<forall>x\<in>Z. \<exists>y\<in>Z. \<langle>y,x\<rangle>:r\<rbrakk> \<Longrightarrow> False"
    83  assumes prem: "\<And>Z u. \<lbrakk>Z<=A;  u \<in> Z;  \<forall>x\<in>Z. \<exists>y\<in>Z. \<langle>y,x\<rangle>:r\<rbrakk> \<Longrightarrow> False"
    84  shows         "wf[A](r)"
    84  shows         "wf[A](r)"
    85 apply (unfold wf_on_def wf_def)
    85   unfolding wf_on_def wf_def
    86 apply (rule equals0I [THEN disjCI, THEN allI])
    86 apply (rule equals0I [THEN disjCI, THEN allI])
    87 apply (rule_tac Z = Z in prem, blast+)
    87 apply (rule_tac Z = Z in prem, blast+)
    88 done
    88 done
    89 
    89 
    90 text\<open>If \<^term>\<open>r\<close> allows well-founded induction over \<^term>\<open>A\<close>
    90 text\<open>If \<^term>\<open>r\<close> allows well-founded induction over \<^term>\<open>A\<close>
   285      "\<lbrakk>wf(r);  trans(r)\<rbrakk> \<Longrightarrow> is_recfun(r, a, H, the_recfun(r,a,H))"
   285      "\<lbrakk>wf(r);  trans(r)\<rbrakk> \<Longrightarrow> is_recfun(r, a, H, the_recfun(r,a,H))"
   286 apply (rule_tac a=a in wf_induct, assumption)
   286 apply (rule_tac a=a in wf_induct, assumption)
   287 apply (rename_tac a1)
   287 apply (rename_tac a1)
   288 apply (rule_tac f = "\<lambda>y\<in>r-``{a1}. wftrec (r,y,H)" in is_the_recfun)
   288 apply (rule_tac f = "\<lambda>y\<in>r-``{a1}. wftrec (r,y,H)" in is_the_recfun)
   289   apply typecheck
   289   apply typecheck
   290 apply (unfold is_recfun_def wftrec_def)
   290   unfolding is_recfun_def wftrec_def
   291   \<comment> \<open>Applying the substitution: must keep the quantified assumption!\<close>
   291   \<comment> \<open>Applying the substitution: must keep the quantified assumption!\<close>
   292 apply (rule lam_cong [OF refl])
   292 apply (rule lam_cong [OF refl])
   293 apply (drule underD)
   293 apply (drule underD)
   294 apply (fold is_recfun_def)
   294 apply (fold is_recfun_def)
   295 apply (rule_tac t = "\<lambda>z. H(x, z)" for x in subst_context)
   295 apply (rule_tac t = "\<lambda>z. H(x, z)" for x in subst_context)
   357 
   357 
   358 
   358 
   359 lemma wfrec_on:
   359 lemma wfrec_on:
   360  "\<lbrakk>wf[A](r);  a \<in> A\<rbrakk> \<Longrightarrow>
   360  "\<lbrakk>wf[A](r);  a \<in> A\<rbrakk> \<Longrightarrow>
   361          wfrec[A](r,a,H) = H(a, \<lambda>x\<in>(r-``{a}) \<inter> A. wfrec[A](r,x,H))"
   361          wfrec[A](r,a,H) = H(a, \<lambda>x\<in>(r-``{a}) \<inter> A. wfrec[A](r,x,H))"
   362 apply (unfold wf_on_def wfrec_on_def)
   362   unfolding wf_on_def wfrec_on_def
   363 apply (erule wfrec [THEN trans])
   363 apply (erule wfrec [THEN trans])
   364 apply (simp add: vimage_Int_square cons_subset_iff)
   364 apply (simp add: vimage_Int_square cons_subset_iff)
   365 done
   365 done
   366 
   366 
   367 text\<open>Minimal-element characterization of well-foundedness\<close>
   367 text\<open>Minimal-element characterization of well-foundedness\<close>