1(* Title: CCL/Lfp.thy 2 Author: Lawrence C Paulson, Cambridge University Computer Laboratory 3 Copyright 1992 University of Cambridge 4*) 5 6section \<open>The Knaster-Tarski Theorem\<close> 7 8theory Lfp 9imports Set 10begin 11 12definition 13 lfp :: "['a set\<Rightarrow>'a set] \<Rightarrow> 'a set" where \<comment> \<open>least fixed point\<close> 14 "lfp(f) == Inter({u. f(u) <= u})" 15 16(* lfp(f) is the greatest lower bound of {u. f(u) <= u} *) 17 18lemma lfp_lowerbound: "f(A) <= A \<Longrightarrow> lfp(f) <= A" 19 unfolding lfp_def by blast 20 21lemma lfp_greatest: "(\<And>u. f(u) <= u \<Longrightarrow> A<=u) \<Longrightarrow> A <= lfp(f)" 22 unfolding lfp_def by blast 23 24lemma lfp_lemma2: "mono(f) \<Longrightarrow> f(lfp(f)) <= lfp(f)" 25 by (rule lfp_greatest, rule subset_trans, drule monoD, rule lfp_lowerbound, assumption+) 26 27lemma lfp_lemma3: "mono(f) \<Longrightarrow> lfp(f) <= f(lfp(f))" 28 by (rule lfp_lowerbound, frule monoD, drule lfp_lemma2, assumption+) 29 30lemma lfp_Tarski: "mono(f) \<Longrightarrow> lfp(f) = f(lfp(f))" 31 by (rule equalityI lfp_lemma2 lfp_lemma3 | assumption)+ 32 33 34(*** General induction rule for least fixed points ***) 35 36lemma induct: 37 assumes lfp: "a: lfp(f)" 38 and mono: "mono(f)" 39 and indhyp: "\<And>x. \<lbrakk>x: f(lfp(f) Int {x. P(x)})\<rbrakk> \<Longrightarrow> P(x)" 40 shows "P(a)" 41 apply (rule_tac a = a in Int_lower2 [THEN subsetD, THEN CollectD]) 42 apply (rule lfp [THEN [2] lfp_lowerbound [THEN subsetD]]) 43 apply (rule Int_greatest, rule subset_trans, rule Int_lower1 [THEN mono [THEN monoD]], 44 rule mono [THEN lfp_lemma2], rule CollectI [THEN subsetI], rule indhyp, assumption) 45 done 46 47(** Definition forms of lfp_Tarski and induct, to control unfolding **) 48 49lemma def_lfp_Tarski: "\<lbrakk>h == lfp(f); mono(f)\<rbrakk> \<Longrightarrow> h = f(h)" 50 apply unfold 51 apply (drule lfp_Tarski) 52 apply assumption 53 done 54 55lemma def_induct: "\<lbrakk>A == lfp(f); a:A; mono(f); \<And>x. x: f(A Int {x. P(x)}) \<Longrightarrow> P(x)\<rbrakk> \<Longrightarrow> P(a)" 56 apply (rule induct [of concl: P a]) 57 apply simp 58 apply assumption 59 apply blast 60 done 61 62(*Monotonicity of lfp!*) 63lemma lfp_mono: "\<lbrakk>mono(g); \<And>Z. f(Z) <= g(Z)\<rbrakk> \<Longrightarrow> lfp(f) <= lfp(g)" 64 apply (rule lfp_lowerbound) 65 apply (rule subset_trans) 66 apply (erule meta_spec) 67 apply (erule lfp_lemma2) 68 done 69 70end 71