src/HOL/Lfp.ML
 author nipkow Wed Aug 18 11:09:40 2004 +0200 (2004-08-18) changeset 15140 322485b816ac parent 14892 659707452f55 permissions -rw-r--r--
import -> imports
```     1 (*  Title:      HOL/Lfp.ML
```
```     2     ID:         \$Id\$
```
```     3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
```
```     4     Copyright   1992  University of Cambridge
```
```     5
```
```     6 The Knaster-Tarski Theorem.
```
```     7 *)
```
```     8
```
```     9 (*** Proof of Knaster-Tarski Theorem ***)
```
```    10
```
```    11 val lfp_def = thm "lfp_def";
```
```    12
```
```    13 (* lfp(f) is the greatest lower bound of {u. f(u) <= u} *)
```
```    14
```
```    15 Goalw [lfp_def] "f(A) <= A ==> lfp(f) <= A";
```
```    16 by (rtac (CollectI RS Inter_lower) 1);
```
```    17 by (assume_tac 1);
```
```    18 qed "lfp_lowerbound";
```
```    19
```
```    20 val prems = Goalw [lfp_def]
```
```    21     "[| !!u. f(u) <= u ==> A<=u |] ==> A <= lfp(f)";
```
```    22 by (REPEAT (ares_tac ([Inter_greatest]@prems) 1));
```
```    23 by (etac CollectD 1);
```
```    24 qed "lfp_greatest";
```
```    25
```
```    26 Goal "mono(f) ==> f(lfp(f)) <= lfp(f)";
```
```    27 by (EVERY1 [rtac lfp_greatest, rtac subset_trans,
```
```    28             etac monoD, rtac lfp_lowerbound, atac, atac]);
```
```    29 qed "lfp_lemma2";
```
```    30
```
```    31 Goal "mono(f) ==> lfp(f) <= f(lfp(f))";
```
```    32 by (EVERY1 [rtac lfp_lowerbound, rtac monoD, assume_tac,
```
```    33             etac lfp_lemma2]);
```
```    34 qed "lfp_lemma3";
```
```    35
```
```    36 Goal "mono(f) ==> lfp(f) = f(lfp(f))";
```
```    37 by (REPEAT (ares_tac [equalityI,lfp_lemma2,lfp_lemma3] 1));
```
```    38 qed "lfp_unfold";
```
```    39
```
```    40 (*** General induction rule for least fixed points ***)
```
```    41
```
```    42 val [lfp,mono,indhyp] = Goal
```
```    43     "[| a: lfp(f);  mono(f);                            \
```
```    44 \       !!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)   \
```
```    45 \    |] ==> P(a)";
```
```    46 by (res_inst_tac [("a","a")] (Int_lower2 RS subsetD RS CollectD) 1);
```
```    47 by (rtac (lfp RSN (2, lfp_lowerbound RS subsetD)) 1);
```
```    48 by (EVERY1 [rtac Int_greatest, rtac subset_trans,
```
```    49             rtac (Int_lower1 RS (mono RS monoD)),
```
```    50             rtac (mono RS lfp_lemma2),
```
```    51             rtac (CollectI RS subsetI), rtac indhyp, atac]);
```
```    52 qed "lfp_induct";
```
```    53
```
```    54 bind_thm ("lfp_induct2",
```
```    55   split_rule (read_instantiate [("a","(a,b)")] lfp_induct));
```
```    56
```
```    57
```
```    58 val major::prems = Goal
```
```    59  "[| mono f; !!S. P S ==> P(f S); !!M. !S:M. P S ==> P(Union M) |] ==> \
```
```    60 \ P(lfp f)";
```
```    61 by(subgoal_tac "lfp f = Union{S. S <= lfp f & P S}" 1);
```
```    62  by(etac ssubst 1);
```
```    63  by(simp_tac (simpset() addsimps prems) 1);
```
```    64 by(subgoal_tac "Union{S. S <= lfp f & P S} <= lfp f" 1);
```
```    65  by(Blast_tac 2);
```
```    66 by(rtac equalityI 1);
```
```    67  by(atac 2);
```
```    68 by(dtac (major RS monoD) 1);
```
```    69 by(cut_facts_tac [major RS lfp_unfold] 1);
```
```    70 by(Asm_full_simp_tac 1);
```
```    71 by(rtac lfp_lowerbound 1);
```
```    72 by(blast_tac (claset() addSIs prems) 1);
```
```    73 qed "lfp_ordinal_induct";
```
```    74
```
```    75
```
```    76 (** Definition forms of lfp_unfold and lfp_induct, to control unfolding **)
```
```    77
```
```    78 Goal "[| h==lfp(f);  mono(f) |] ==> h = f(h)";
```
```    79 by (auto_tac (claset() addSIs [lfp_unfold], simpset()));
```
```    80 qed "def_lfp_unfold";
```
```    81
```
```    82 val rew::prems = Goal
```
```    83     "[| A == lfp(f);  mono(f);   a:A;                   \
```
```    84 \       !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x)        \
```
```    85 \    |] ==> P(a)";
```
```    86 by (EVERY1 [rtac lfp_induct,        (*backtracking to force correct induction*)
```
```    87             REPEAT1 o (ares_tac (map (rewrite_rule [rew]) prems))]);
```
```    88 qed "def_lfp_induct";
```
```    89
```
```    90 (*Monotonicity of lfp!*)
```
```    91 val [prem] = Goal "[| !!Z. f(Z)<=g(Z) |] ==> lfp(f) <= lfp(g)";
```
```    92 by (rtac (lfp_lowerbound RS lfp_greatest) 1);
```
```    93 by (etac (prem RS subset_trans) 1);
```
```    94 qed "lfp_mono";
```