src/HOL/Lfp.ML
 author oheimb Wed Jan 31 10:15:55 2001 +0100 (2001-01-31) changeset 11008 f7333f055ef6 parent 10202 9e8b4bebc940 child 14169 0590de71a016 permissions -rw-r--r--
improved theory reference in comment
1 (*  Title:      HOL/Lfp.ML
2     ID:         \$Id\$
3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
4     Copyright   1992  University of Cambridge
6 The Knaster-Tarski Theorem.
7 *)
9 (*** Proof of Knaster-Tarski Theorem ***)
11 (* lfp(f) is the greatest lower bound of {u. f(u) <= u} *)
13 Goalw [lfp_def] "f(A) <= A ==> lfp(f) <= A";
14 by (rtac (CollectI RS Inter_lower) 1);
15 by (assume_tac 1);
16 qed "lfp_lowerbound";
18 val prems = Goalw [lfp_def]
19     "[| !!u. f(u) <= u ==> A<=u |] ==> A <= lfp(f)";
20 by (REPEAT (ares_tac ([Inter_greatest]@prems) 1));
21 by (etac CollectD 1);
22 qed "lfp_greatest";
24 Goal "mono(f) ==> f(lfp(f)) <= lfp(f)";
25 by (EVERY1 [rtac lfp_greatest, rtac subset_trans,
26             etac monoD, rtac lfp_lowerbound, atac, atac]);
27 qed "lfp_lemma2";
29 Goal "mono(f) ==> lfp(f) <= f(lfp(f))";
30 by (EVERY1 [rtac lfp_lowerbound, rtac monoD, assume_tac,
31             etac lfp_lemma2]);
32 qed "lfp_lemma3";
34 Goal "mono(f) ==> lfp(f) = f(lfp(f))";
35 by (REPEAT (ares_tac [equalityI,lfp_lemma2,lfp_lemma3] 1));
36 qed "lfp_unfold";
38 (*** General induction rule for least fixed points ***)
40 val [lfp,mono,indhyp] = Goal
41     "[| a: lfp(f);  mono(f);                            \
42 \       !!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)   \
43 \    |] ==> P(a)";
44 by (res_inst_tac [("a","a")] (Int_lower2 RS subsetD RS CollectD) 1);
45 by (rtac (lfp RSN (2, lfp_lowerbound RS subsetD)) 1);
46 by (EVERY1 [rtac Int_greatest, rtac subset_trans,
47             rtac (Int_lower1 RS (mono RS monoD)),
48             rtac (mono RS lfp_lemma2),
49             rtac (CollectI RS subsetI), rtac indhyp, atac]);
50 qed "lfp_induct";
52 bind_thm ("lfp_induct2",
56 (** Definition forms of lfp_unfold and lfp_induct, to control unfolding **)
58 Goal "[| h==lfp(f);  mono(f) |] ==> h = f(h)";
59 by (auto_tac (claset() addSIs [lfp_unfold], simpset()));
60 qed "def_lfp_unfold";
62 val rew::prems = Goal
63     "[| A == lfp(f);  mono(f);   a:A;                   \
64 \       !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x)        \
65 \    |] ==> P(a)";
66 by (EVERY1 [rtac lfp_induct,        (*backtracking to force correct induction*)
67             REPEAT1 o (ares_tac (map (rewrite_rule [rew]) prems))]);
68 qed "def_lfp_induct";
70 (*Monotonicity of lfp!*)
71 val [prem] = Goal "[| !!Z. f(Z)<=g(Z) |] ==> lfp(f) <= lfp(g)";
72 by (rtac (lfp_lowerbound RS lfp_greatest) 1);
73 by (etac (prem RS subset_trans) 1);
74 qed "lfp_mono";