src/CCL/Gfp.ML
author wenzelm
Sat Sep 17 17:35:26 2005 +0200 (2005-09-17)
changeset 17456 bcf7544875b2
parent 3837 d7f033c74b38
permissions -rw-r--r--
converted to Isar theory format;
wenzelm@17456
     1
(*  Title:      CCL/Gfp.ML
clasohm@0
     2
    ID:         $Id$
clasohm@0
     3
*)
clasohm@0
     4
clasohm@0
     5
(*** Proof of Knaster-Tarski Theorem using gfp ***)
clasohm@0
     6
clasohm@0
     7
(* gfp(f) is the least upper bound of {u. u <= f(u)} *)
clasohm@0
     8
wenzelm@17456
     9
val prems = goalw (the_context ()) [gfp_def] "[| A <= f(A) |] ==> A <= gfp(f)";
clasohm@0
    10
by (rtac (CollectI RS Union_upper) 1);
clasohm@0
    11
by (resolve_tac prems 1);
clasohm@757
    12
qed "gfp_upperbound";
clasohm@0
    13
wenzelm@17456
    14
val prems = goalw (the_context ()) [gfp_def]
clasohm@0
    15
    "[| !!u. u <= f(u) ==> u<=A |] ==> gfp(f) <= A";
clasohm@0
    16
by (REPEAT (ares_tac ([Union_least]@prems) 1));
clasohm@0
    17
by (etac CollectD 1);
clasohm@757
    18
qed "gfp_least";
clasohm@0
    19
wenzelm@17456
    20
val [mono] = goal (the_context ()) "mono(f) ==> gfp(f) <= f(gfp(f))";
clasohm@0
    21
by (EVERY1 [rtac gfp_least, rtac subset_trans, atac,
clasohm@1459
    22
            rtac (mono RS monoD), rtac gfp_upperbound, atac]);
clasohm@757
    23
qed "gfp_lemma2";
clasohm@0
    24
wenzelm@17456
    25
val [mono] = goal (the_context ()) "mono(f) ==> f(gfp(f)) <= gfp(f)";
clasohm@0
    26
by (EVERY1 [rtac gfp_upperbound, rtac (mono RS monoD), 
clasohm@1459
    27
            rtac gfp_lemma2, rtac mono]);
clasohm@757
    28
qed "gfp_lemma3";
clasohm@0
    29
wenzelm@17456
    30
val [mono] = goal (the_context ()) "mono(f) ==> gfp(f) = f(gfp(f))";
clasohm@0
    31
by (REPEAT (resolve_tac [equalityI,gfp_lemma2,gfp_lemma3,mono] 1));
clasohm@757
    32
qed "gfp_Tarski";
clasohm@0
    33
clasohm@0
    34
(*** Coinduction rules for greatest fixed points ***)
clasohm@0
    35
clasohm@0
    36
(*weak version*)
wenzelm@17456
    37
val prems = goal (the_context ())
clasohm@0
    38
    "[| a: A;  A <= f(A) |] ==> a : gfp(f)";
clasohm@0
    39
by (rtac (gfp_upperbound RS subsetD) 1);
clasohm@0
    40
by (REPEAT (ares_tac prems 1));
clasohm@757
    41
qed "coinduct";
clasohm@0
    42
wenzelm@17456
    43
val [prem,mono] = goal (the_context ())
clasohm@0
    44
    "[| A <= f(A) Un gfp(f);  mono(f) |] ==>  \
clasohm@0
    45
\    A Un gfp(f) <= f(A Un gfp(f))";
clasohm@0
    46
by (rtac subset_trans 1);
clasohm@0
    47
by (rtac (mono RS mono_Un) 2);
clasohm@0
    48
by (rtac (mono RS gfp_Tarski RS subst) 1);
clasohm@0
    49
by (rtac (prem RS Un_least) 1);
clasohm@0
    50
by (rtac Un_upper2 1);
clasohm@757
    51
qed "coinduct2_lemma";
clasohm@0
    52
clasohm@0
    53
(*strong version, thanks to Martin Coen*)
wenzelm@17456
    54
val ainA::prems = goal (the_context ())
clasohm@0
    55
    "[| a: A;  A <= f(A) Un gfp(f);  mono(f) |] ==> a : gfp(f)";
lcp@642
    56
by (rtac coinduct 1);
lcp@642
    57
by (rtac (prems MRS coinduct2_lemma) 2);
lcp@642
    58
by (resolve_tac [ainA RS UnI1] 1);
clasohm@757
    59
qed "coinduct2";
clasohm@0
    60
clasohm@0
    61
(***  Even Stronger version of coinduct  [by Martin Coen]
clasohm@0
    62
         - instead of the condition  A <= f(A)
clasohm@0
    63
                           consider  A <= (f(A) Un f(f(A)) ...) Un gfp(A) ***)
clasohm@0
    64
wenzelm@17456
    65
val [prem] = goal (the_context ()) "mono(f) ==> mono(%x. f(x) Un A Un B)";
clasohm@0
    66
by (REPEAT (ares_tac [subset_refl, monoI, Un_mono, prem RS monoD] 1));
clasohm@757
    67
qed "coinduct3_mono_lemma";
clasohm@0
    68
wenzelm@17456
    69
val [prem,mono] = goal (the_context ())
wenzelm@3837
    70
    "[| A <= f(lfp(%x. f(x) Un A Un gfp(f)));  mono(f) |] ==> \
wenzelm@3837
    71
\    lfp(%x. f(x) Un A Un gfp(f)) <= f(lfp(%x. f(x) Un A Un gfp(f)))";
clasohm@0
    72
by (rtac subset_trans 1);
lcp@642
    73
by (rtac (mono RS coinduct3_mono_lemma RS lfp_lemma3) 1);
clasohm@0
    74
by (rtac (Un_least RS Un_least) 1);
lcp@642
    75
by (rtac subset_refl 1);
lcp@642
    76
by (rtac prem 1);
lcp@642
    77
by (rtac (mono RS gfp_Tarski RS equalityD1 RS subset_trans) 1);
clasohm@0
    78
by (rtac (mono RS monoD) 1);
paulson@2035
    79
by (stac (mono RS coinduct3_mono_lemma RS lfp_Tarski) 1);
clasohm@0
    80
by (rtac Un_upper2 1);
clasohm@757
    81
qed "coinduct3_lemma";
clasohm@0
    82
wenzelm@17456
    83
val ainA::prems = goal (the_context ())
wenzelm@3837
    84
    "[| a:A;  A <= f(lfp(%x. f(x) Un A Un gfp(f))); mono(f) |] ==> a : gfp(f)";
lcp@642
    85
by (rtac coinduct 1);
lcp@642
    86
by (rtac (prems MRS coinduct3_lemma) 2);
lcp@642
    87
by (resolve_tac (prems RL [coinduct3_mono_lemma RS lfp_Tarski RS ssubst]) 1);
lcp@642
    88
by (rtac (ainA RS UnI2 RS UnI1) 1);
clasohm@757
    89
qed "coinduct3";
clasohm@0
    90
clasohm@0
    91
clasohm@0
    92
(** Definition forms of gfp_Tarski, to control unfolding **)
clasohm@0
    93
wenzelm@17456
    94
val [rew,mono] = goal (the_context ()) "[| h==gfp(f);  mono(f) |] ==> h = f(h)";
clasohm@0
    95
by (rewtac rew);
clasohm@0
    96
by (rtac (mono RS gfp_Tarski) 1);
clasohm@757
    97
qed "def_gfp_Tarski";
clasohm@0
    98
wenzelm@17456
    99
val rew::prems = goal (the_context ())
clasohm@0
   100
    "[| h==gfp(f);  a:A;  A <= f(A) |] ==> a: h";
clasohm@0
   101
by (rewtac rew);
clasohm@0
   102
by (REPEAT (ares_tac (prems @ [coinduct]) 1));
clasohm@757
   103
qed "def_coinduct";
clasohm@0
   104
wenzelm@17456
   105
val rew::prems = goal (the_context ())
clasohm@0
   106
    "[| h==gfp(f);  a:A;  A <= f(A) Un h; mono(f) |] ==> a: h";
clasohm@0
   107
by (rewtac rew);
clasohm@0
   108
by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct2]) 1));
clasohm@757
   109
qed "def_coinduct2";
clasohm@0
   110
wenzelm@17456
   111
val rew::prems = goal (the_context ())
wenzelm@3837
   112
    "[| h==gfp(f);  a:A;  A <= f(lfp(%x. f(x) Un A Un h)); mono(f) |] ==> a: h";
clasohm@0
   113
by (rewtac rew);
clasohm@0
   114
by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct3]) 1));
clasohm@757
   115
qed "def_coinduct3";
clasohm@0
   116
clasohm@0
   117
(*Monotonicity of gfp!*)
wenzelm@17456
   118
val prems = goal (the_context ())
clasohm@0
   119
    "[| mono(f);  !!Z. f(Z)<=g(Z) |] ==> gfp(f) <= gfp(g)";
clasohm@0
   120
by (rtac gfp_upperbound 1);
clasohm@0
   121
by (rtac subset_trans 1);
clasohm@0
   122
by (rtac gfp_lemma2 1);
clasohm@0
   123
by (resolve_tac prems 1);
clasohm@0
   124
by (resolve_tac prems 1);
clasohm@757
   125
qed "gfp_mono";