src/HOL/Inductive.thy
changeset 32705 04ce6bb14d85
parent 32701 5059a733a4b8
child 33934 25d6a8982e37
child 33959 2afc55e8ed27
equal deleted inserted replaced
32682:304a47739407 32705:04ce6bb14d85
    81   assumes lfp: "a: lfp(f)"
    81   assumes lfp: "a: lfp(f)"
    82       and mono: "mono(f)"
    82       and mono: "mono(f)"
    83       and indhyp: "!!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)"
    83       and indhyp: "!!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)"
    84   shows "P(a)"
    84   shows "P(a)"
    85   by (rule lfp_induct [THEN subsetD, THEN CollectD, OF mono _ lfp])
    85   by (rule lfp_induct [THEN subsetD, THEN CollectD, OF mono _ lfp])
    86     (auto simp: inf_set_eq intro: indhyp)
    86     (auto simp: intro: indhyp)
    87 
    87 
    88 lemma lfp_ordinal_induct:
    88 lemma lfp_ordinal_induct:
    89   fixes f :: "'a\<Colon>complete_lattice \<Rightarrow> 'a"
    89   fixes f :: "'a\<Colon>complete_lattice \<Rightarrow> 'a"
    90   assumes mono: "mono f"
    90   assumes mono: "mono f"
    91   and P_f: "\<And>S. P S \<Longrightarrow> P (f S)"
    91   and P_f: "\<And>S. P S \<Longrightarrow> P (f S)"
   182   apply assumption
   182   apply assumption
   183   done
   183   done
   184 
   184 
   185 text{*strong version, thanks to Coen and Frost*}
   185 text{*strong version, thanks to Coen and Frost*}
   186 lemma coinduct_set: "[| mono(f);  a: X;  X \<subseteq> f(X Un gfp(f)) |] ==> a : gfp(f)"
   186 lemma coinduct_set: "[| mono(f);  a: X;  X \<subseteq> f(X Un gfp(f)) |] ==> a : gfp(f)"
   187 by (blast intro: weak_coinduct [OF _ coinduct_lemma, simplified sup_set_eq])
   187 by (blast intro: weak_coinduct [OF _ coinduct_lemma])
   188 
   188 
   189 lemma coinduct: "[| mono(f); X \<le> f (sup X (gfp f)) |] ==> X \<le> gfp(f)"
   189 lemma coinduct: "[| mono(f); X \<le> f (sup X (gfp f)) |] ==> X \<le> gfp(f)"
   190   apply (rule order_trans)
   190   apply (rule order_trans)
   191   apply (rule sup_ge1)
   191   apply (rule sup_ge1)
   192   apply (erule gfp_upperbound [OF coinduct_lemma])
   192   apply (erule gfp_upperbound [OF coinduct_lemma])