|
1459
|
1 |
(* Title: CCL/lfp
|
|
0
|
2 |
ID: $Id$
|
|
|
3 |
|
|
|
4 |
Modified version of
|
|
1459
|
5 |
Title: HOL/lfp.ML
|
|
|
6 |
Author: Lawrence C Paulson, Cambridge University Computer Laboratory
|
|
0
|
7 |
Copyright 1992 University of Cambridge
|
|
|
8 |
|
|
|
9 |
For lfp.thy. The Knaster-Tarski Theorem
|
|
|
10 |
*)
|
|
|
11 |
|
|
|
12 |
open Lfp;
|
|
|
13 |
|
|
|
14 |
(*** Proof of Knaster-Tarski Theorem ***)
|
|
|
15 |
|
|
|
16 |
(* lfp(f) is the greatest lower bound of {u. f(u) <= u} *)
|
|
|
17 |
|
|
|
18 |
val prems = goalw Lfp.thy [lfp_def] "[| f(A) <= A |] ==> lfp(f) <= A";
|
|
|
19 |
by (rtac (CollectI RS Inter_lower) 1);
|
|
|
20 |
by (resolve_tac prems 1);
|
|
757
|
21 |
qed "lfp_lowerbound";
|
|
0
|
22 |
|
|
|
23 |
val prems = goalw Lfp.thy [lfp_def]
|
|
|
24 |
"[| !!u. f(u) <= u ==> A<=u |] ==> A <= lfp(f)";
|
|
|
25 |
by (REPEAT (ares_tac ([Inter_greatest]@prems) 1));
|
|
|
26 |
by (etac CollectD 1);
|
|
757
|
27 |
qed "lfp_greatest";
|
|
0
|
28 |
|
|
|
29 |
val [mono] = goal Lfp.thy "mono(f) ==> f(lfp(f)) <= lfp(f)";
|
|
|
30 |
by (EVERY1 [rtac lfp_greatest, rtac subset_trans,
|
|
1459
|
31 |
rtac (mono RS monoD), rtac lfp_lowerbound, atac, atac]);
|
|
757
|
32 |
qed "lfp_lemma2";
|
|
0
|
33 |
|
|
|
34 |
val [mono] = goal Lfp.thy "mono(f) ==> lfp(f) <= f(lfp(f))";
|
|
|
35 |
by (EVERY1 [rtac lfp_lowerbound, rtac (mono RS monoD),
|
|
1459
|
36 |
rtac lfp_lemma2, rtac mono]);
|
|
757
|
37 |
qed "lfp_lemma3";
|
|
0
|
38 |
|
|
|
39 |
val [mono] = goal Lfp.thy "mono(f) ==> lfp(f) = f(lfp(f))";
|
|
|
40 |
by (REPEAT (resolve_tac [equalityI,lfp_lemma2,lfp_lemma3,mono] 1));
|
|
757
|
41 |
qed "lfp_Tarski";
|
|
0
|
42 |
|
|
|
43 |
|
|
|
44 |
(*** General induction rule for least fixed points ***)
|
|
|
45 |
|
|
|
46 |
val [lfp,mono,indhyp] = goal Lfp.thy
|
|
1459
|
47 |
"[| a: lfp(f); mono(f); \
|
|
3837
|
48 |
\ !!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x) \
|
|
0
|
49 |
\ |] ==> P(a)";
|
|
|
50 |
by (res_inst_tac [("a","a")] (Int_lower2 RS subsetD RS CollectD) 1);
|
|
|
51 |
by (rtac (lfp RSN (2, lfp_lowerbound RS subsetD)) 1);
|
|
|
52 |
by (EVERY1 [rtac Int_greatest, rtac subset_trans,
|
|
1459
|
53 |
rtac (Int_lower1 RS (mono RS monoD)),
|
|
|
54 |
rtac (mono RS lfp_lemma2),
|
|
|
55 |
rtac (CollectI RS subsetI), rtac indhyp, atac]);
|
|
757
|
56 |
qed "induct";
|
|
0
|
57 |
|
|
|
58 |
(** Definition forms of lfp_Tarski and induct, to control unfolding **)
|
|
|
59 |
|
|
|
60 |
val [rew,mono] = goal Lfp.thy "[| h==lfp(f); mono(f) |] ==> h = f(h)";
|
|
|
61 |
by (rewtac rew);
|
|
|
62 |
by (rtac (mono RS lfp_Tarski) 1);
|
|
757
|
63 |
qed "def_lfp_Tarski";
|
|
0
|
64 |
|
|
|
65 |
val rew::prems = goal Lfp.thy
|
|
1459
|
66 |
"[| A == lfp(f); a:A; mono(f); \
|
|
3837
|
67 |
\ !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x) \
|
|
0
|
68 |
\ |] ==> P(a)";
|
|
1459
|
69 |
by (EVERY1 [rtac induct, (*backtracking to force correct induction*)
|
|
|
70 |
REPEAT1 o (ares_tac (map (rewrite_rule [rew]) prems))]);
|
|
757
|
71 |
qed "def_induct";
|
|
0
|
72 |
|
|
|
73 |
(*Monotonicity of lfp!*)
|
|
|
74 |
val prems = goal Lfp.thy
|
|
|
75 |
"[| mono(g); !!Z. f(Z)<=g(Z) |] ==> lfp(f) <= lfp(g)";
|
|
|
76 |
by (rtac lfp_lowerbound 1);
|
|
|
77 |
by (rtac subset_trans 1);
|
|
|
78 |
by (resolve_tac prems 1);
|
|
|
79 |
by (rtac lfp_lemma2 1);
|
|
|
80 |
by (resolve_tac prems 1);
|
|
757
|
81 |
qed "lfp_mono";
|
|
0
|
82 |
|