1 (* Title: CCL/gfp |
1 (* Title: CCL/Gfp.ML |
2 ID: $Id$ |
2 ID: $Id$ |
3 |
|
4 Modified version of |
|
5 Title: HOL/gfp |
|
6 Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
|
7 Copyright 1993 University of Cambridge |
|
8 |
|
9 For gfp.thy. The Knaster-Tarski Theorem for greatest fixed points. |
|
10 *) |
3 *) |
11 |
|
12 open Gfp; |
|
13 |
4 |
14 (*** Proof of Knaster-Tarski Theorem using gfp ***) |
5 (*** Proof of Knaster-Tarski Theorem using gfp ***) |
15 |
6 |
16 (* gfp(f) is the least upper bound of {u. u <= f(u)} *) |
7 (* gfp(f) is the least upper bound of {u. u <= f(u)} *) |
17 |
8 |
18 val prems = goalw Gfp.thy [gfp_def] "[| A <= f(A) |] ==> A <= gfp(f)"; |
9 val prems = goalw (the_context ()) [gfp_def] "[| A <= f(A) |] ==> A <= gfp(f)"; |
19 by (rtac (CollectI RS Union_upper) 1); |
10 by (rtac (CollectI RS Union_upper) 1); |
20 by (resolve_tac prems 1); |
11 by (resolve_tac prems 1); |
21 qed "gfp_upperbound"; |
12 qed "gfp_upperbound"; |
22 |
13 |
23 val prems = goalw Gfp.thy [gfp_def] |
14 val prems = goalw (the_context ()) [gfp_def] |
24 "[| !!u. u <= f(u) ==> u<=A |] ==> gfp(f) <= A"; |
15 "[| !!u. u <= f(u) ==> u<=A |] ==> gfp(f) <= A"; |
25 by (REPEAT (ares_tac ([Union_least]@prems) 1)); |
16 by (REPEAT (ares_tac ([Union_least]@prems) 1)); |
26 by (etac CollectD 1); |
17 by (etac CollectD 1); |
27 qed "gfp_least"; |
18 qed "gfp_least"; |
28 |
19 |
29 val [mono] = goal Gfp.thy "mono(f) ==> gfp(f) <= f(gfp(f))"; |
20 val [mono] = goal (the_context ()) "mono(f) ==> gfp(f) <= f(gfp(f))"; |
30 by (EVERY1 [rtac gfp_least, rtac subset_trans, atac, |
21 by (EVERY1 [rtac gfp_least, rtac subset_trans, atac, |
31 rtac (mono RS monoD), rtac gfp_upperbound, atac]); |
22 rtac (mono RS monoD), rtac gfp_upperbound, atac]); |
32 qed "gfp_lemma2"; |
23 qed "gfp_lemma2"; |
33 |
24 |
34 val [mono] = goal Gfp.thy "mono(f) ==> f(gfp(f)) <= gfp(f)"; |
25 val [mono] = goal (the_context ()) "mono(f) ==> f(gfp(f)) <= gfp(f)"; |
35 by (EVERY1 [rtac gfp_upperbound, rtac (mono RS monoD), |
26 by (EVERY1 [rtac gfp_upperbound, rtac (mono RS monoD), |
36 rtac gfp_lemma2, rtac mono]); |
27 rtac gfp_lemma2, rtac mono]); |
37 qed "gfp_lemma3"; |
28 qed "gfp_lemma3"; |
38 |
29 |
39 val [mono] = goal Gfp.thy "mono(f) ==> gfp(f) = f(gfp(f))"; |
30 val [mono] = goal (the_context ()) "mono(f) ==> gfp(f) = f(gfp(f))"; |
40 by (REPEAT (resolve_tac [equalityI,gfp_lemma2,gfp_lemma3,mono] 1)); |
31 by (REPEAT (resolve_tac [equalityI,gfp_lemma2,gfp_lemma3,mono] 1)); |
41 qed "gfp_Tarski"; |
32 qed "gfp_Tarski"; |
42 |
33 |
43 (*** Coinduction rules for greatest fixed points ***) |
34 (*** Coinduction rules for greatest fixed points ***) |
44 |
35 |
45 (*weak version*) |
36 (*weak version*) |
46 val prems = goal Gfp.thy |
37 val prems = goal (the_context ()) |
47 "[| a: A; A <= f(A) |] ==> a : gfp(f)"; |
38 "[| a: A; A <= f(A) |] ==> a : gfp(f)"; |
48 by (rtac (gfp_upperbound RS subsetD) 1); |
39 by (rtac (gfp_upperbound RS subsetD) 1); |
49 by (REPEAT (ares_tac prems 1)); |
40 by (REPEAT (ares_tac prems 1)); |
50 qed "coinduct"; |
41 qed "coinduct"; |
51 |
42 |
52 val [prem,mono] = goal Gfp.thy |
43 val [prem,mono] = goal (the_context ()) |
53 "[| A <= f(A) Un gfp(f); mono(f) |] ==> \ |
44 "[| A <= f(A) Un gfp(f); mono(f) |] ==> \ |
54 \ A Un gfp(f) <= f(A Un gfp(f))"; |
45 \ A Un gfp(f) <= f(A Un gfp(f))"; |
55 by (rtac subset_trans 1); |
46 by (rtac subset_trans 1); |
56 by (rtac (mono RS mono_Un) 2); |
47 by (rtac (mono RS mono_Un) 2); |
57 by (rtac (mono RS gfp_Tarski RS subst) 1); |
48 by (rtac (mono RS gfp_Tarski RS subst) 1); |
58 by (rtac (prem RS Un_least) 1); |
49 by (rtac (prem RS Un_least) 1); |
59 by (rtac Un_upper2 1); |
50 by (rtac Un_upper2 1); |
60 qed "coinduct2_lemma"; |
51 qed "coinduct2_lemma"; |
61 |
52 |
62 (*strong version, thanks to Martin Coen*) |
53 (*strong version, thanks to Martin Coen*) |
63 val ainA::prems = goal Gfp.thy |
54 val ainA::prems = goal (the_context ()) |
64 "[| a: A; A <= f(A) Un gfp(f); mono(f) |] ==> a : gfp(f)"; |
55 "[| a: A; A <= f(A) Un gfp(f); mono(f) |] ==> a : gfp(f)"; |
65 by (rtac coinduct 1); |
56 by (rtac coinduct 1); |
66 by (rtac (prems MRS coinduct2_lemma) 2); |
57 by (rtac (prems MRS coinduct2_lemma) 2); |
67 by (resolve_tac [ainA RS UnI1] 1); |
58 by (resolve_tac [ainA RS UnI1] 1); |
68 qed "coinduct2"; |
59 qed "coinduct2"; |
69 |
60 |
70 (*** Even Stronger version of coinduct [by Martin Coen] |
61 (*** Even Stronger version of coinduct [by Martin Coen] |
71 - instead of the condition A <= f(A) |
62 - instead of the condition A <= f(A) |
72 consider A <= (f(A) Un f(f(A)) ...) Un gfp(A) ***) |
63 consider A <= (f(A) Un f(f(A)) ...) Un gfp(A) ***) |
73 |
64 |
74 val [prem] = goal Gfp.thy "mono(f) ==> mono(%x. f(x) Un A Un B)"; |
65 val [prem] = goal (the_context ()) "mono(f) ==> mono(%x. f(x) Un A Un B)"; |
75 by (REPEAT (ares_tac [subset_refl, monoI, Un_mono, prem RS monoD] 1)); |
66 by (REPEAT (ares_tac [subset_refl, monoI, Un_mono, prem RS monoD] 1)); |
76 qed "coinduct3_mono_lemma"; |
67 qed "coinduct3_mono_lemma"; |
77 |
68 |
78 val [prem,mono] = goal Gfp.thy |
69 val [prem,mono] = goal (the_context ()) |
79 "[| A <= f(lfp(%x. f(x) Un A Un gfp(f))); mono(f) |] ==> \ |
70 "[| A <= f(lfp(%x. f(x) Un A Un gfp(f))); mono(f) |] ==> \ |
80 \ lfp(%x. f(x) Un A Un gfp(f)) <= f(lfp(%x. f(x) Un A Un gfp(f)))"; |
71 \ lfp(%x. f(x) Un A Un gfp(f)) <= f(lfp(%x. f(x) Un A Un gfp(f)))"; |
81 by (rtac subset_trans 1); |
72 by (rtac subset_trans 1); |
82 by (rtac (mono RS coinduct3_mono_lemma RS lfp_lemma3) 1); |
73 by (rtac (mono RS coinduct3_mono_lemma RS lfp_lemma3) 1); |
83 by (rtac (Un_least RS Un_least) 1); |
74 by (rtac (Un_least RS Un_least) 1); |
87 by (rtac (mono RS monoD) 1); |
78 by (rtac (mono RS monoD) 1); |
88 by (stac (mono RS coinduct3_mono_lemma RS lfp_Tarski) 1); |
79 by (stac (mono RS coinduct3_mono_lemma RS lfp_Tarski) 1); |
89 by (rtac Un_upper2 1); |
80 by (rtac Un_upper2 1); |
90 qed "coinduct3_lemma"; |
81 qed "coinduct3_lemma"; |
91 |
82 |
92 val ainA::prems = goal Gfp.thy |
83 val ainA::prems = goal (the_context ()) |
93 "[| a:A; A <= f(lfp(%x. f(x) Un A Un gfp(f))); mono(f) |] ==> a : gfp(f)"; |
84 "[| a:A; A <= f(lfp(%x. f(x) Un A Un gfp(f))); mono(f) |] ==> a : gfp(f)"; |
94 by (rtac coinduct 1); |
85 by (rtac coinduct 1); |
95 by (rtac (prems MRS coinduct3_lemma) 2); |
86 by (rtac (prems MRS coinduct3_lemma) 2); |
96 by (resolve_tac (prems RL [coinduct3_mono_lemma RS lfp_Tarski RS ssubst]) 1); |
87 by (resolve_tac (prems RL [coinduct3_mono_lemma RS lfp_Tarski RS ssubst]) 1); |
97 by (rtac (ainA RS UnI2 RS UnI1) 1); |
88 by (rtac (ainA RS UnI2 RS UnI1) 1); |
98 qed "coinduct3"; |
89 qed "coinduct3"; |
99 |
90 |
100 |
91 |
101 (** Definition forms of gfp_Tarski, to control unfolding **) |
92 (** Definition forms of gfp_Tarski, to control unfolding **) |
102 |
93 |
103 val [rew,mono] = goal Gfp.thy "[| h==gfp(f); mono(f) |] ==> h = f(h)"; |
94 val [rew,mono] = goal (the_context ()) "[| h==gfp(f); mono(f) |] ==> h = f(h)"; |
104 by (rewtac rew); |
95 by (rewtac rew); |
105 by (rtac (mono RS gfp_Tarski) 1); |
96 by (rtac (mono RS gfp_Tarski) 1); |
106 qed "def_gfp_Tarski"; |
97 qed "def_gfp_Tarski"; |
107 |
98 |
108 val rew::prems = goal Gfp.thy |
99 val rew::prems = goal (the_context ()) |
109 "[| h==gfp(f); a:A; A <= f(A) |] ==> a: h"; |
100 "[| h==gfp(f); a:A; A <= f(A) |] ==> a: h"; |
110 by (rewtac rew); |
101 by (rewtac rew); |
111 by (REPEAT (ares_tac (prems @ [coinduct]) 1)); |
102 by (REPEAT (ares_tac (prems @ [coinduct]) 1)); |
112 qed "def_coinduct"; |
103 qed "def_coinduct"; |
113 |
104 |
114 val rew::prems = goal Gfp.thy |
105 val rew::prems = goal (the_context ()) |
115 "[| h==gfp(f); a:A; A <= f(A) Un h; mono(f) |] ==> a: h"; |
106 "[| h==gfp(f); a:A; A <= f(A) Un h; mono(f) |] ==> a: h"; |
116 by (rewtac rew); |
107 by (rewtac rew); |
117 by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct2]) 1)); |
108 by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct2]) 1)); |
118 qed "def_coinduct2"; |
109 qed "def_coinduct2"; |
119 |
110 |
120 val rew::prems = goal Gfp.thy |
111 val rew::prems = goal (the_context ()) |
121 "[| h==gfp(f); a:A; A <= f(lfp(%x. f(x) Un A Un h)); mono(f) |] ==> a: h"; |
112 "[| h==gfp(f); a:A; A <= f(lfp(%x. f(x) Un A Un h)); mono(f) |] ==> a: h"; |
122 by (rewtac rew); |
113 by (rewtac rew); |
123 by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct3]) 1)); |
114 by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct3]) 1)); |
124 qed "def_coinduct3"; |
115 qed "def_coinduct3"; |
125 |
116 |
126 (*Monotonicity of gfp!*) |
117 (*Monotonicity of gfp!*) |
127 val prems = goal Gfp.thy |
118 val prems = goal (the_context ()) |
128 "[| mono(f); !!Z. f(Z)<=g(Z) |] ==> gfp(f) <= gfp(g)"; |
119 "[| mono(f); !!Z. f(Z)<=g(Z) |] ==> gfp(f) <= gfp(g)"; |
129 by (rtac gfp_upperbound 1); |
120 by (rtac gfp_upperbound 1); |
130 by (rtac subset_trans 1); |
121 by (rtac subset_trans 1); |
131 by (rtac gfp_lemma2 1); |
122 by (rtac gfp_lemma2 1); |
132 by (resolve_tac prems 1); |
123 by (resolve_tac prems 1); |