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