src/CCL/Lfp.thy
author haftmann
Tue, 10 Jul 2007 17:30:50 +0200
changeset 23709 fd31da8f752a
parent 21404 eb85850d3eb7
child 32153 a0e57fb1b930
permissions -rw-r--r--
moved lfp_induct2 here
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
     1
(*  Title:      CCL/Lfp.thy
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     2
    ID:         $Id$
1474
3f7d67927fe2 expanded tabs
clasohm
parents: 0
diff changeset
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     4
    Copyright   1992  University of Cambridge
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     5
*)
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
     6
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
     7
header {* The Knaster-Tarski Theorem *}
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
     8
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
     9
theory Lfp
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
    10
imports Set
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
    11
begin
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
    12
20140
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    13
definition
21404
eb85850d3eb7 more robust syntax for definition/abbreviation/notation;
wenzelm
parents: 20140
diff changeset
    14
  lfp :: "['a set=>'a set] => 'a set" where -- "least fixed point"
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
    15
  "lfp(f) == Inter({u. f(u) <= u})"
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
    16
20140
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    17
(* lfp(f) is the greatest lower bound of {u. f(u) <= u} *)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    18
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    19
lemma lfp_lowerbound: "[| f(A) <= A |] ==> lfp(f) <= A"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    20
  unfolding lfp_def by blast
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    21
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    22
lemma lfp_greatest: "[| !!u. f(u) <= u ==> A<=u |] ==> A <= lfp(f)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    23
  unfolding lfp_def by blast
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    24
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    25
lemma lfp_lemma2: "mono(f) ==> f(lfp(f)) <= lfp(f)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    26
  by (rule lfp_greatest, rule subset_trans, drule monoD, rule lfp_lowerbound, assumption+)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    27
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    28
lemma lfp_lemma3: "mono(f) ==> lfp(f) <= f(lfp(f))"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    29
  by (rule lfp_lowerbound, frule monoD, drule lfp_lemma2, assumption+)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    30
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    31
lemma lfp_Tarski: "mono(f) ==> lfp(f) = f(lfp(f))"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    32
  by (rule equalityI lfp_lemma2 lfp_lemma3 | assumption)+
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    33
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    34
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    35
(*** General induction rule for least fixed points ***)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    36
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    37
lemma induct:
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    38
  assumes lfp: "a: lfp(f)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    39
    and mono: "mono(f)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    40
    and indhyp: "!!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    41
  shows "P(a)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    42
  apply (rule_tac a = a in Int_lower2 [THEN subsetD, THEN CollectD])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    43
  apply (rule lfp [THEN [2] lfp_lowerbound [THEN subsetD]])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    44
  apply (rule Int_greatest, rule subset_trans, rule Int_lower1 [THEN mono [THEN monoD]],
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    45
    rule mono [THEN lfp_lemma2], rule CollectI [THEN subsetI], rule indhyp, assumption)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    46
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    47
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    48
(** Definition forms of lfp_Tarski and induct, to control unfolding **)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    49
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    50
lemma def_lfp_Tarski: "[| h==lfp(f);  mono(f) |] ==> h = f(h)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    51
  apply unfold
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    52
  apply (drule lfp_Tarski)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    53
  apply assumption
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    54
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    55
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    56
lemma def_induct:
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    57
  "[| A == lfp(f);  a:A;  mono(f);                     
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    58
    !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x)         
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    59
  |] ==> P(a)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    60
  apply (rule induct [of concl: P a])
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    61
    apply simp
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    62
   apply assumption
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    63
  apply blast
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    64
  done
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    65
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    66
(*Monotonicity of lfp!*)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    67
lemma lfp_mono: "[| mono(g);  !!Z. f(Z)<=g(Z) |] ==> lfp(f) <= lfp(g)"
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    68
  apply (rule lfp_lowerbound)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    69
  apply (rule subset_trans)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    70
   apply (erule meta_spec)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    71
  apply (erule lfp_lemma2)
98acc6d0fab6 removed obsolete ML files;
wenzelm
parents: 17456
diff changeset
    72
  done
17456
bcf7544875b2 converted to Isar theory format;
wenzelm
parents: 1474
diff changeset
    73
0
a5a9c433f639 Initial revision
clasohm
parents:
diff changeset
    74
end