src/HOL/Gfp.ML
author nipkow
Fri, 24 Nov 2000 16:49:27 +0100
changeset 10519 ade64af4c57c
parent 10186 499637e8f2c6
child 11335 c150861633da
permissions -rw-r--r--
hide many names from Datatype_Universe.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
9422
4b6bc2b347e5 avoid referencing thy value;
wenzelm
parents: 5316
diff changeset
     1
(*  Title:      HOL/Gfp.ML
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     2
    ID:         $Id$
1465
5d7a7e439cec expanded tabs
clasohm
parents: 923
diff changeset
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     4
    Copyright   1993  University of Cambridge
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     5
5148
74919e8f221c More tidying and removal of "\!\!... from Goal commands
paulson
parents: 5069
diff changeset
     6
The Knaster-Tarski Theorem for greatest fixed points.
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     7
*)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     8
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
     9
(*** Proof of Knaster-Tarski Theorem using gfp ***)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    10
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    11
(* gfp(f) is the least upper bound of {u. u <= f(u)} *)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    12
5148
74919e8f221c More tidying and removal of "\!\!... from Goal commands
paulson
parents: 5069
diff changeset
    13
Goalw [gfp_def] "[| X <= f(X) |] ==> X <= gfp(f)";
74919e8f221c More tidying and removal of "\!\!... from Goal commands
paulson
parents: 5069
diff changeset
    14
by (etac (CollectI RS Union_upper) 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    15
qed "gfp_upperbound";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    16
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    17
val prems = Goalw [gfp_def]
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    18
    "[| !!u. u <= f(u) ==> u<=X |] ==> gfp(f) <= X";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    19
by (REPEAT (ares_tac ([Union_least]@prems) 1));
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    20
by (etac CollectD 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    21
qed "gfp_least";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    22
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    23
Goal "mono(f) ==> gfp(f) <= f(gfp(f))";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    24
by (EVERY1 [rtac gfp_least, rtac subset_trans, atac,
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    25
            etac monoD, rtac gfp_upperbound, atac]);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    26
qed "gfp_lemma2";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    27
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    28
Goal "mono(f) ==> f(gfp(f)) <= gfp(f)";
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    29
by (EVERY1 [rtac gfp_upperbound, rtac monoD, assume_tac,
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    30
            etac gfp_lemma2]);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    31
qed "gfp_lemma3";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    32
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    33
Goal "mono(f) ==> gfp(f) = f(gfp(f))";
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    34
by (REPEAT (ares_tac [equalityI,gfp_lemma2,gfp_lemma3] 1));
10186
499637e8f2c6 *** empty log message ***
nipkow
parents: 10067
diff changeset
    35
qed "gfp_unfold";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    36
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    37
(*** Coinduction rules for greatest fixed points ***)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    38
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    39
(*weak version*)
5148
74919e8f221c More tidying and removal of "\!\!... from Goal commands
paulson
parents: 5069
diff changeset
    40
Goal "[| a: X;  X <= f(X) |] ==> a : gfp(f)";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    41
by (rtac (gfp_upperbound RS subsetD) 1);
5148
74919e8f221c More tidying and removal of "\!\!... from Goal commands
paulson
parents: 5069
diff changeset
    42
by Auto_tac;
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    43
qed "weak_coinduct";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    44
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    45
Goal "[| X <= f(X Un gfp(f));  mono(f) |] ==>  \
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    46
\    X Un gfp(f) <= f(X Un gfp(f))";
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    47
by (blast_tac (claset() addDs [gfp_lemma2, mono_Un]) 1); 
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    48
qed "coinduct_lemma";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    49
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    50
(*strong version, thanks to Coen & Frost*)
5148
74919e8f221c More tidying and removal of "\!\!... from Goal commands
paulson
parents: 5069
diff changeset
    51
Goal "[| mono(f);  a: X;  X <= f(X Un gfp(f)) |] ==> a : gfp(f)";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    52
by (rtac (coinduct_lemma RSN (2, weak_coinduct)) 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    53
by (REPEAT (ares_tac [UnI1, Un_least] 1));
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    54
qed "coinduct";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    55
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    56
Goal "[| mono(f);  a: gfp(f) |] ==> a: f(X Un gfp(f))";
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    57
by (blast_tac (claset() addDs [gfp_lemma2, mono_Un]) 1); 
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    58
qed "gfp_fun_UnI2";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    59
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    60
(***  Even Stronger version of coinduct  [by Martin Coen]
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    61
         - instead of the condition  X <= f(X)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    62
                           consider  X <= (f(X) Un f(f(X)) ...) Un gfp(X) ***)
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    63
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    64
Goal "mono(f) ==> mono(%x. f(x) Un X Un B)";
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    65
by (REPEAT (ares_tac [subset_refl, monoI, Un_mono] 1 ORELSE etac monoD 1));
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    66
qed "coinduct3_mono_lemma";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    67
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    68
Goal "[| X <= f(lfp(%x. f(x) Un X Un gfp(f)));  mono(f) |] ==> \
3842
b55686a7b22c fixed dots;
wenzelm
parents: 2036
diff changeset
    69
\    lfp(%x. f(x) Un X Un gfp(f)) <= f(lfp(%x. f(x) Un X Un gfp(f)))";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    70
by (rtac subset_trans 1);
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    71
by (etac (coinduct3_mono_lemma RS lfp_lemma3) 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    72
by (rtac (Un_least RS Un_least) 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    73
by (rtac subset_refl 1);
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    74
by (assume_tac 1); 
10186
499637e8f2c6 *** empty log message ***
nipkow
parents: 10067
diff changeset
    75
by (rtac (gfp_unfold RS equalityD1 RS subset_trans) 1);
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    76
by (assume_tac 1);
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    77
by (rtac monoD 1 THEN assume_tac 1);
10186
499637e8f2c6 *** empty log message ***
nipkow
parents: 10067
diff changeset
    78
by (stac (coinduct3_mono_lemma RS lfp_unfold) 1);
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    79
by Auto_tac;  
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    80
qed "coinduct3_lemma";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    81
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    82
Goal
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    83
  "[| mono(f);  a:X;  X <= f(lfp(%x. f(x) Un X Un gfp(f))) |] ==> a : gfp(f)";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    84
by (rtac (coinduct3_lemma RSN (2,weak_coinduct)) 1);
10186
499637e8f2c6 *** empty log message ***
nipkow
parents: 10067
diff changeset
    85
by (resolve_tac [coinduct3_mono_lemma RS lfp_unfold RS ssubst] 1);
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
    86
by Auto_tac;
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    87
qed "coinduct3";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    88
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    89
10186
499637e8f2c6 *** empty log message ***
nipkow
parents: 10067
diff changeset
    90
(** Definition forms of gfp_unfold and coinduct, to control unfolding **)
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    91
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    92
Goal "[| A==gfp(f);  mono(f) |] ==> A = f(A)";
10186
499637e8f2c6 *** empty log message ***
nipkow
parents: 10067
diff changeset
    93
by (auto_tac (claset() addSIs [gfp_unfold], simpset()));  
499637e8f2c6 *** empty log message ***
nipkow
parents: 10067
diff changeset
    94
qed "def_gfp_unfold";
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    95
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    96
Goal "[| A==gfp(f);  mono(f);  a:X;  X <= f(X Un A) |] ==> a: A";
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
    97
by (auto_tac (claset() addSIs [coinduct], simpset()));  
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    98
qed "def_coinduct";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
    99
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   100
(*The version used in the induction/coinduction package*)
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
   101
val prems = Goal
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   102
    "[| A == gfp(%w. Collect(P(w)));  mono(%w. Collect(P(w)));  \
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   103
\       a: X;  !!z. z: X ==> P (X Un A) z |] ==> \
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   104
\    a : A";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   105
by (rtac def_coinduct 1);
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   106
by (REPEAT (ares_tac (prems @ [subsetI,CollectI]) 1));
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   107
qed "def_Collect_coinduct";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   108
10067
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
   109
Goal "[| A==gfp(f); mono(f);  a:X;  X <= f(lfp(%x. f(x) Un X Un A)) |] \
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
   110
\     ==> a: A";
ab03cfd6be3a tidied, removing obsolete "goal" commands
paulson
parents: 9422
diff changeset
   111
by (auto_tac (claset() addSIs [coinduct3], simpset()));  
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   112
qed "def_coinduct3";
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   113
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   114
(*Monotonicity of gfp!*)
5316
7a8975451a89 even more tidying of Goal commands
paulson
parents: 5148
diff changeset
   115
val [prem] = Goal "[| !!Z. f(Z)<=g(Z) |] ==> gfp(f) <= gfp(g)";
1465
5d7a7e439cec expanded tabs
clasohm
parents: 923
diff changeset
   116
by (rtac (gfp_upperbound RS gfp_least) 1);
5d7a7e439cec expanded tabs
clasohm
parents: 923
diff changeset
   117
by (etac (prem RSN (2,subset_trans)) 1);
923
ff1574a81019 new version of HOL with curried function application
clasohm
parents:
diff changeset
   118
qed "gfp_mono";