src/HOL/Lfp.ML
author oheimb
Wed Jan 31 10:15:55 2001 +0100 (2001-01-31)
changeset 11008 f7333f055ef6
parent 10202 9e8b4bebc940
child 14169 0590de71a016
permissions -rw-r--r--
improved theory reference in comment
wenzelm@9422
     1
(*  Title:      HOL/Lfp.ML
clasohm@923
     2
    ID:         $Id$
clasohm@1465
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@923
     4
    Copyright   1992  University of Cambridge
clasohm@923
     5
wenzelm@9422
     6
The Knaster-Tarski Theorem.
clasohm@923
     7
*)
clasohm@923
     8
clasohm@923
     9
(*** Proof of Knaster-Tarski Theorem ***)
clasohm@923
    10
clasohm@923
    11
(* lfp(f) is the greatest lower bound of {u. f(u) <= u} *)
clasohm@923
    12
paulson@5316
    13
Goalw [lfp_def] "f(A) <= A ==> lfp(f) <= A";
clasohm@923
    14
by (rtac (CollectI RS Inter_lower) 1);
paulson@5316
    15
by (assume_tac 1);
clasohm@923
    16
qed "lfp_lowerbound";
clasohm@923
    17
paulson@5316
    18
val prems = Goalw [lfp_def]
clasohm@923
    19
    "[| !!u. f(u) <= u ==> A<=u |] ==> A <= lfp(f)";
clasohm@923
    20
by (REPEAT (ares_tac ([Inter_greatest]@prems) 1));
clasohm@923
    21
by (etac CollectD 1);
clasohm@923
    22
qed "lfp_greatest";
clasohm@923
    23
paulson@5316
    24
Goal "mono(f) ==> f(lfp(f)) <= lfp(f)";
clasohm@923
    25
by (EVERY1 [rtac lfp_greatest, rtac subset_trans,
paulson@5316
    26
            etac monoD, rtac lfp_lowerbound, atac, atac]);
clasohm@923
    27
qed "lfp_lemma2";
clasohm@923
    28
paulson@5316
    29
Goal "mono(f) ==> lfp(f) <= f(lfp(f))";
paulson@5316
    30
by (EVERY1 [rtac lfp_lowerbound, rtac monoD, assume_tac,
paulson@5316
    31
            etac lfp_lemma2]);
clasohm@923
    32
qed "lfp_lemma3";
clasohm@923
    33
paulson@5316
    34
Goal "mono(f) ==> lfp(f) = f(lfp(f))";
paulson@5316
    35
by (REPEAT (ares_tac [equalityI,lfp_lemma2,lfp_lemma3] 1));
nipkow@10186
    36
qed "lfp_unfold";
clasohm@923
    37
clasohm@923
    38
(*** General induction rule for least fixed points ***)
clasohm@923
    39
paulson@5316
    40
val [lfp,mono,indhyp] = Goal
clasohm@1465
    41
    "[| a: lfp(f);  mono(f);                            \
wenzelm@3842
    42
\       !!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)   \
clasohm@923
    43
\    |] ==> P(a)";
clasohm@923
    44
by (res_inst_tac [("a","a")] (Int_lower2 RS subsetD RS CollectD) 1);
clasohm@923
    45
by (rtac (lfp RSN (2, lfp_lowerbound RS subsetD)) 1);
clasohm@923
    46
by (EVERY1 [rtac Int_greatest, rtac subset_trans, 
clasohm@1465
    47
            rtac (Int_lower1 RS (mono RS monoD)),
clasohm@1465
    48
            rtac (mono RS lfp_lemma2),
clasohm@1465
    49
            rtac (CollectI RS subsetI), rtac indhyp, atac]);
nipkow@10202
    50
qed "lfp_induct";
clasohm@923
    51
nipkow@10202
    52
bind_thm ("lfp_induct2",
nipkow@10202
    53
  split_rule (read_instantiate [("a","(a,b)")] lfp_induct));
nipkow@1114
    54
nipkow@1125
    55
nipkow@10202
    56
(** Definition forms of lfp_unfold and lfp_induct, to control unfolding **)
clasohm@923
    57
paulson@10067
    58
Goal "[| h==lfp(f);  mono(f) |] ==> h = f(h)";
nipkow@10186
    59
by (auto_tac (claset() addSIs [lfp_unfold], simpset()));  
nipkow@10186
    60
qed "def_lfp_unfold";
clasohm@923
    61
paulson@5316
    62
val rew::prems = Goal
clasohm@1465
    63
    "[| A == lfp(f);  mono(f);   a:A;                   \
wenzelm@3842
    64
\       !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x)        \
clasohm@923
    65
\    |] ==> P(a)";
nipkow@10202
    66
by (EVERY1 [rtac lfp_induct,        (*backtracking to force correct induction*)
clasohm@1465
    67
            REPEAT1 o (ares_tac (map (rewrite_rule [rew]) prems))]);
nipkow@10202
    68
qed "def_lfp_induct";
clasohm@923
    69
clasohm@923
    70
(*Monotonicity of lfp!*)
paulson@5316
    71
val [prem] = Goal "[| !!Z. f(Z)<=g(Z) |] ==> lfp(f) <= lfp(g)";
clasohm@1465
    72
by (rtac (lfp_lowerbound RS lfp_greatest) 1);
clasohm@1465
    73
by (etac (prem RS subset_trans) 1);
clasohm@923
    74
qed "lfp_mono";