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