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