src/HOL/Gfp.ML
author nipkow
Wed Aug 18 11:09:40 2004 +0200 (2004-08-18)
changeset 15140 322485b816ac
parent 14169 0590de71a016
permissions -rw-r--r--
import -> imports
wenzelm@9422
     1
(*  Title:      HOL/Gfp.ML
clasohm@923
     2
    ID:         $Id$
clasohm@1465
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@923
     4
    Copyright   1993  University of Cambridge
clasohm@923
     5
paulson@5148
     6
The Knaster-Tarski Theorem for greatest fixed points.
clasohm@923
     7
*)
clasohm@923
     8
clasohm@923
     9
(*** Proof of Knaster-Tarski Theorem using gfp ***)
clasohm@923
    10
skalberg@14169
    11
val gfp_def = thm "gfp_def";
skalberg@14169
    12
clasohm@923
    13
(* gfp(f) is the least upper bound of {u. u <= f(u)} *)
clasohm@923
    14
paulson@5148
    15
Goalw [gfp_def] "[| X <= f(X) |] ==> X <= gfp(f)";
paulson@5148
    16
by (etac (CollectI RS Union_upper) 1);
clasohm@923
    17
qed "gfp_upperbound";
clasohm@923
    18
paulson@10067
    19
val prems = Goalw [gfp_def]
clasohm@923
    20
    "[| !!u. u <= f(u) ==> u<=X |] ==> gfp(f) <= X";
clasohm@923
    21
by (REPEAT (ares_tac ([Union_least]@prems) 1));
clasohm@923
    22
by (etac CollectD 1);
clasohm@923
    23
qed "gfp_least";
clasohm@923
    24
paulson@5316
    25
Goal "mono(f) ==> gfp(f) <= f(gfp(f))";
clasohm@923
    26
by (EVERY1 [rtac gfp_least, rtac subset_trans, atac,
paulson@5316
    27
            etac monoD, rtac gfp_upperbound, atac]);
clasohm@923
    28
qed "gfp_lemma2";
clasohm@923
    29
paulson@5316
    30
Goal "mono(f) ==> f(gfp(f)) <= gfp(f)";
paulson@5316
    31
by (EVERY1 [rtac gfp_upperbound, rtac monoD, assume_tac,
paulson@5316
    32
            etac gfp_lemma2]);
clasohm@923
    33
qed "gfp_lemma3";
clasohm@923
    34
paulson@5316
    35
Goal "mono(f) ==> gfp(f) = f(gfp(f))";
paulson@5316
    36
by (REPEAT (ares_tac [equalityI,gfp_lemma2,gfp_lemma3] 1));
nipkow@10186
    37
qed "gfp_unfold";
clasohm@923
    38
clasohm@923
    39
(*** Coinduction rules for greatest fixed points ***)
clasohm@923
    40
clasohm@923
    41
(*weak version*)
paulson@5148
    42
Goal "[| a: X;  X <= f(X) |] ==> a : gfp(f)";
clasohm@923
    43
by (rtac (gfp_upperbound RS subsetD) 1);
paulson@5148
    44
by Auto_tac;
clasohm@923
    45
qed "weak_coinduct";
clasohm@923
    46
oheimb@11335
    47
Goal "!!X. [| a : X; g`X <= f (g`X) |] ==> g a : gfp f";
oheimb@11335
    48
by (etac (gfp_upperbound RS subsetD) 1);
oheimb@11335
    49
by (etac imageI 1);
oheimb@11335
    50
qed "weak_coinduct_image";
oheimb@11335
    51
paulson@10067
    52
Goal "[| X <= f(X Un gfp(f));  mono(f) |] ==>  \
clasohm@923
    53
\    X Un gfp(f) <= f(X Un gfp(f))";
paulson@10067
    54
by (blast_tac (claset() addDs [gfp_lemma2, mono_Un]) 1); 
clasohm@923
    55
qed "coinduct_lemma";
clasohm@923
    56
clasohm@923
    57
(*strong version, thanks to Coen & Frost*)
paulson@5148
    58
Goal "[| mono(f);  a: X;  X <= f(X Un gfp(f)) |] ==> a : gfp(f)";
clasohm@923
    59
by (rtac (coinduct_lemma RSN (2, weak_coinduct)) 1);
clasohm@923
    60
by (REPEAT (ares_tac [UnI1, Un_least] 1));
clasohm@923
    61
qed "coinduct";
clasohm@923
    62
paulson@10067
    63
Goal "[| mono(f);  a: gfp(f) |] ==> a: f(X Un gfp(f))";
paulson@10067
    64
by (blast_tac (claset() addDs [gfp_lemma2, mono_Un]) 1); 
clasohm@923
    65
qed "gfp_fun_UnI2";
clasohm@923
    66
clasohm@923
    67
(***  Even Stronger version of coinduct  [by Martin Coen]
clasohm@923
    68
         - instead of the condition  X <= f(X)
clasohm@923
    69
                           consider  X <= (f(X) Un f(f(X)) ...) Un gfp(X) ***)
clasohm@923
    70
paulson@5316
    71
Goal "mono(f) ==> mono(%x. f(x) Un X Un B)";
paulson@5316
    72
by (REPEAT (ares_tac [subset_refl, monoI, Un_mono] 1 ORELSE etac monoD 1));
clasohm@923
    73
qed "coinduct3_mono_lemma";
clasohm@923
    74
paulson@10067
    75
Goal "[| X <= f(lfp(%x. f(x) Un X Un gfp(f)));  mono(f) |] ==> \
wenzelm@3842
    76
\    lfp(%x. f(x) Un X Un gfp(f)) <= f(lfp(%x. f(x) Un X Un gfp(f)))";
clasohm@923
    77
by (rtac subset_trans 1);
paulson@10067
    78
by (etac (coinduct3_mono_lemma RS lfp_lemma3) 1);
clasohm@923
    79
by (rtac (Un_least RS Un_least) 1);
clasohm@923
    80
by (rtac subset_refl 1);
paulson@10067
    81
by (assume_tac 1); 
nipkow@10186
    82
by (rtac (gfp_unfold RS equalityD1 RS subset_trans) 1);
paulson@10067
    83
by (assume_tac 1);
paulson@10067
    84
by (rtac monoD 1 THEN assume_tac 1);
nipkow@10186
    85
by (stac (coinduct3_mono_lemma RS lfp_unfold) 1);
paulson@10067
    86
by Auto_tac;  
clasohm@923
    87
qed "coinduct3_lemma";
clasohm@923
    88
paulson@5316
    89
Goal
paulson@5316
    90
  "[| mono(f);  a:X;  X <= f(lfp(%x. f(x) Un X Un gfp(f))) |] ==> a : gfp(f)";
clasohm@923
    91
by (rtac (coinduct3_lemma RSN (2,weak_coinduct)) 1);
nipkow@10186
    92
by (resolve_tac [coinduct3_mono_lemma RS lfp_unfold RS ssubst] 1);
paulson@5316
    93
by Auto_tac;
clasohm@923
    94
qed "coinduct3";
clasohm@923
    95
clasohm@923
    96
nipkow@10186
    97
(** Definition forms of gfp_unfold and coinduct, to control unfolding **)
clasohm@923
    98
paulson@10067
    99
Goal "[| A==gfp(f);  mono(f) |] ==> A = f(A)";
nipkow@10186
   100
by (auto_tac (claset() addSIs [gfp_unfold], simpset()));  
nipkow@10186
   101
qed "def_gfp_unfold";
clasohm@923
   102
paulson@10067
   103
Goal "[| A==gfp(f);  mono(f);  a:X;  X <= f(X Un A) |] ==> a: A";
paulson@10067
   104
by (auto_tac (claset() addSIs [coinduct], simpset()));  
clasohm@923
   105
qed "def_coinduct";
clasohm@923
   106
clasohm@923
   107
(*The version used in the induction/coinduction package*)
paulson@5316
   108
val prems = Goal
clasohm@923
   109
    "[| A == gfp(%w. Collect(P(w)));  mono(%w. Collect(P(w)));  \
clasohm@923
   110
\       a: X;  !!z. z: X ==> P (X Un A) z |] ==> \
clasohm@923
   111
\    a : A";
clasohm@923
   112
by (rtac def_coinduct 1);
clasohm@923
   113
by (REPEAT (ares_tac (prems @ [subsetI,CollectI]) 1));
clasohm@923
   114
qed "def_Collect_coinduct";
clasohm@923
   115
paulson@10067
   116
Goal "[| A==gfp(f); mono(f);  a:X;  X <= f(lfp(%x. f(x) Un X Un A)) |] \
paulson@10067
   117
\     ==> a: A";
paulson@10067
   118
by (auto_tac (claset() addSIs [coinduct3], simpset()));  
clasohm@923
   119
qed "def_coinduct3";
clasohm@923
   120
clasohm@923
   121
(*Monotonicity of gfp!*)
paulson@5316
   122
val [prem] = Goal "[| !!Z. f(Z)<=g(Z) |] ==> gfp(f) <= gfp(g)";
clasohm@1465
   123
by (rtac (gfp_upperbound RS gfp_least) 1);
clasohm@1465
   124
by (etac (prem RSN (2,subset_trans)) 1);
clasohm@923
   125
qed "gfp_mono";