src/CCL/Gfp.ML
 author paulson Fri Feb 16 17:24:51 1996 +0100 (1996-02-16) changeset 1511 09354d37a5ab parent 1459 d12da312eff4 child 2035 e329b36d9136 permissions -rw-r--r--
Elimination of fully-functorial style.
Type tactic changed to a type abbrevation (from a datatype).
Constructor tactic and function apply deleted.
```     1 (*  Title:      CCL/gfp
```
```     2     ID:         \$Id\$
```
```     3
```
```     4 Modified version of
```
```     5     Title:      HOL/gfp
```
```     6     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
```
```     7     Copyright   1993  University of Cambridge
```
```     8
```
```     9 For gfp.thy.  The Knaster-Tarski Theorem for greatest fixed points.
```
```    10 *)
```
```    11
```
```    12 open Gfp;
```
```    13
```
```    14 (*** Proof of Knaster-Tarski Theorem using gfp ***)
```
```    15
```
```    16 (* gfp(f) is the least upper bound of {u. u <= f(u)} *)
```
```    17
```
```    18 val prems = goalw Gfp.thy [gfp_def] "[| A <= f(A) |] ==> A <= gfp(f)";
```
```    19 by (rtac (CollectI RS Union_upper) 1);
```
```    20 by (resolve_tac prems 1);
```
```    21 qed "gfp_upperbound";
```
```    22
```
```    23 val prems = goalw Gfp.thy [gfp_def]
```
```    24     "[| !!u. u <= f(u) ==> u<=A |] ==> gfp(f) <= A";
```
```    25 by (REPEAT (ares_tac ([Union_least]@prems) 1));
```
```    26 by (etac CollectD 1);
```
```    27 qed "gfp_least";
```
```    28
```
```    29 val [mono] = goal Gfp.thy "mono(f) ==> gfp(f) <= f(gfp(f))";
```
```    30 by (EVERY1 [rtac gfp_least, rtac subset_trans, atac,
```
```    31             rtac (mono RS monoD), rtac gfp_upperbound, atac]);
```
```    32 qed "gfp_lemma2";
```
```    33
```
```    34 val [mono] = goal Gfp.thy "mono(f) ==> f(gfp(f)) <= gfp(f)";
```
```    35 by (EVERY1 [rtac gfp_upperbound, rtac (mono RS monoD),
```
```    36             rtac gfp_lemma2, rtac mono]);
```
```    37 qed "gfp_lemma3";
```
```    38
```
```    39 val [mono] = goal Gfp.thy "mono(f) ==> gfp(f) = f(gfp(f))";
```
```    40 by (REPEAT (resolve_tac [equalityI,gfp_lemma2,gfp_lemma3,mono] 1));
```
```    41 qed "gfp_Tarski";
```
```    42
```
```    43 (*** Coinduction rules for greatest fixed points ***)
```
```    44
```
```    45 (*weak version*)
```
```    46 val prems = goal Gfp.thy
```
```    47     "[| a: A;  A <= f(A) |] ==> a : gfp(f)";
```
```    48 by (rtac (gfp_upperbound RS subsetD) 1);
```
```    49 by (REPEAT (ares_tac prems 1));
```
```    50 qed "coinduct";
```
```    51
```
```    52 val [prem,mono] = goal Gfp.thy
```
```    53     "[| A <= f(A) Un gfp(f);  mono(f) |] ==>  \
```
```    54 \    A Un gfp(f) <= f(A Un gfp(f))";
```
```    55 by (rtac subset_trans 1);
```
```    56 by (rtac (mono RS mono_Un) 2);
```
```    57 by (rtac (mono RS gfp_Tarski RS subst) 1);
```
```    58 by (rtac (prem RS Un_least) 1);
```
```    59 by (rtac Un_upper2 1);
```
```    60 qed "coinduct2_lemma";
```
```    61
```
```    62 (*strong version, thanks to Martin Coen*)
```
```    63 val ainA::prems = goal Gfp.thy
```
```    64     "[| a: A;  A <= f(A) Un gfp(f);  mono(f) |] ==> a : gfp(f)";
```
```    65 by (rtac coinduct 1);
```
```    66 by (rtac (prems MRS coinduct2_lemma) 2);
```
```    67 by (resolve_tac [ainA RS UnI1] 1);
```
```    68 qed "coinduct2";
```
```    69
```
```    70 (***  Even Stronger version of coinduct  [by Martin Coen]
```
```    71          - instead of the condition  A <= f(A)
```
```    72                            consider  A <= (f(A) Un f(f(A)) ...) Un gfp(A) ***)
```
```    73
```
```    74 val [prem] = goal Gfp.thy "mono(f) ==> mono(%x.f(x) Un A Un B)";
```
```    75 by (REPEAT (ares_tac [subset_refl, monoI, Un_mono, prem RS monoD] 1));
```
```    76 qed "coinduct3_mono_lemma";
```
```    77
```
```    78 val [prem,mono] = goal Gfp.thy
```
```    79     "[| A <= f(lfp(%x.f(x) Un A Un gfp(f)));  mono(f) |] ==> \
```
```    80 \    lfp(%x.f(x) Un A Un gfp(f)) <= f(lfp(%x.f(x) Un A Un gfp(f)))";
```
```    81 by (rtac subset_trans 1);
```
```    82 by (rtac (mono RS coinduct3_mono_lemma RS lfp_lemma3) 1);
```
```    83 by (rtac (Un_least RS Un_least) 1);
```
```    84 by (rtac subset_refl 1);
```
```    85 by (rtac prem 1);
```
```    86 by (rtac (mono RS gfp_Tarski RS equalityD1 RS subset_trans) 1);
```
```    87 by (rtac (mono RS monoD) 1);
```
```    88 by (rtac (mono RS coinduct3_mono_lemma RS lfp_Tarski RS ssubst) 1);
```
```    89 by (rtac Un_upper2 1);
```
```    90 qed "coinduct3_lemma";
```
```    91
```
```    92 val ainA::prems = goal Gfp.thy
```
```    93     "[| a:A;  A <= f(lfp(%x.f(x) Un A Un gfp(f))); mono(f) |] ==> a : gfp(f)";
```
```    94 by (rtac coinduct 1);
```
```    95 by (rtac (prems MRS coinduct3_lemma) 2);
```
```    96 by (resolve_tac (prems RL [coinduct3_mono_lemma RS lfp_Tarski RS ssubst]) 1);
```
```    97 by (rtac (ainA RS UnI2 RS UnI1) 1);
```
```    98 qed "coinduct3";
```
```    99
```
```   100
```
```   101 (** Definition forms of gfp_Tarski, to control unfolding **)
```
```   102
```
```   103 val [rew,mono] = goal Gfp.thy "[| h==gfp(f);  mono(f) |] ==> h = f(h)";
```
```   104 by (rewtac rew);
```
```   105 by (rtac (mono RS gfp_Tarski) 1);
```
```   106 qed "def_gfp_Tarski";
```
```   107
```
```   108 val rew::prems = goal Gfp.thy
```
```   109     "[| h==gfp(f);  a:A;  A <= f(A) |] ==> a: h";
```
```   110 by (rewtac rew);
```
```   111 by (REPEAT (ares_tac (prems @ [coinduct]) 1));
```
```   112 qed "def_coinduct";
```
```   113
```
```   114 val rew::prems = goal Gfp.thy
```
```   115     "[| h==gfp(f);  a:A;  A <= f(A) Un h; mono(f) |] ==> a: h";
```
```   116 by (rewtac rew);
```
```   117 by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct2]) 1));
```
```   118 qed "def_coinduct2";
```
```   119
```
```   120 val rew::prems = goal Gfp.thy
```
```   121     "[| h==gfp(f);  a:A;  A <= f(lfp(%x.f(x) Un A Un h)); mono(f) |] ==> a: h";
```
```   122 by (rewtac rew);
```
```   123 by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct3]) 1));
```
```   124 qed "def_coinduct3";
```
```   125
```
```   126 (*Monotonicity of gfp!*)
```
```   127 val prems = goal Gfp.thy
```
```   128     "[| mono(f);  !!Z. f(Z)<=g(Z) |] ==> gfp(f) <= gfp(g)";
```
```   129 by (rtac gfp_upperbound 1);
```
```   130 by (rtac subset_trans 1);
```
```   131 by (rtac gfp_lemma2 1);
```
```   132 by (resolve_tac prems 1);
```
```   133 by (resolve_tac prems 1);
```
```   134 qed "gfp_mono";
```