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