equal
deleted
inserted
replaced
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> |