src/CCL/Lfp.thy
author wenzelm
Sat May 15 22:15:57 2010 +0200 (2010-05-15)
changeset 36948 d2cdad45fd14
parent 32153 a0e57fb1b930
child 58889 5b7a9633cfa8
permissions -rw-r--r--
renamed Outer_Parse to Parse (in Scala);
wenzelm@17456
     1
(*  Title:      CCL/Lfp.thy
clasohm@1474
     2
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
clasohm@0
     3
    Copyright   1992  University of Cambridge
clasohm@0
     4
*)
clasohm@0
     5
wenzelm@17456
     6
header {* The Knaster-Tarski Theorem *}
wenzelm@17456
     7
wenzelm@17456
     8
theory Lfp
wenzelm@17456
     9
imports Set
wenzelm@17456
    10
begin
wenzelm@17456
    11
wenzelm@20140
    12
definition
wenzelm@21404
    13
  lfp :: "['a set=>'a set] => 'a set" where -- "least fixed point"
wenzelm@17456
    14
  "lfp(f) == Inter({u. f(u) <= u})"
wenzelm@17456
    15
wenzelm@20140
    16
(* lfp(f) is the greatest lower bound of {u. f(u) <= u} *)
wenzelm@20140
    17
wenzelm@20140
    18
lemma lfp_lowerbound: "[| f(A) <= A |] ==> lfp(f) <= A"
wenzelm@20140
    19
  unfolding lfp_def by blast
wenzelm@20140
    20
wenzelm@20140
    21
lemma lfp_greatest: "[| !!u. f(u) <= u ==> A<=u |] ==> A <= lfp(f)"
wenzelm@20140
    22
  unfolding lfp_def by blast
wenzelm@20140
    23
wenzelm@20140
    24
lemma lfp_lemma2: "mono(f) ==> f(lfp(f)) <= lfp(f)"
wenzelm@20140
    25
  by (rule lfp_greatest, rule subset_trans, drule monoD, rule lfp_lowerbound, assumption+)
wenzelm@20140
    26
wenzelm@20140
    27
lemma lfp_lemma3: "mono(f) ==> lfp(f) <= f(lfp(f))"
wenzelm@20140
    28
  by (rule lfp_lowerbound, frule monoD, drule lfp_lemma2, assumption+)
wenzelm@20140
    29
wenzelm@20140
    30
lemma lfp_Tarski: "mono(f) ==> lfp(f) = f(lfp(f))"
wenzelm@20140
    31
  by (rule equalityI lfp_lemma2 lfp_lemma3 | assumption)+
wenzelm@20140
    32
wenzelm@20140
    33
wenzelm@20140
    34
(*** General induction rule for least fixed points ***)
wenzelm@20140
    35
wenzelm@20140
    36
lemma induct:
wenzelm@20140
    37
  assumes lfp: "a: lfp(f)"
wenzelm@20140
    38
    and mono: "mono(f)"
wenzelm@20140
    39
    and indhyp: "!!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)"
wenzelm@20140
    40
  shows "P(a)"
wenzelm@20140
    41
  apply (rule_tac a = a in Int_lower2 [THEN subsetD, THEN CollectD])
wenzelm@20140
    42
  apply (rule lfp [THEN [2] lfp_lowerbound [THEN subsetD]])
wenzelm@20140
    43
  apply (rule Int_greatest, rule subset_trans, rule Int_lower1 [THEN mono [THEN monoD]],
wenzelm@20140
    44
    rule mono [THEN lfp_lemma2], rule CollectI [THEN subsetI], rule indhyp, assumption)
wenzelm@20140
    45
  done
wenzelm@20140
    46
wenzelm@20140
    47
(** Definition forms of lfp_Tarski and induct, to control unfolding **)
wenzelm@20140
    48
wenzelm@20140
    49
lemma def_lfp_Tarski: "[| h==lfp(f);  mono(f) |] ==> h = f(h)"
wenzelm@20140
    50
  apply unfold
wenzelm@20140
    51
  apply (drule lfp_Tarski)
wenzelm@20140
    52
  apply assumption
wenzelm@20140
    53
  done
wenzelm@20140
    54
wenzelm@20140
    55
lemma def_induct:
wenzelm@20140
    56
  "[| A == lfp(f);  a:A;  mono(f);                     
wenzelm@20140
    57
    !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x)         
wenzelm@20140
    58
  |] ==> P(a)"
wenzelm@20140
    59
  apply (rule induct [of concl: P a])
wenzelm@20140
    60
    apply simp
wenzelm@20140
    61
   apply assumption
wenzelm@20140
    62
  apply blast
wenzelm@20140
    63
  done
wenzelm@20140
    64
wenzelm@20140
    65
(*Monotonicity of lfp!*)
wenzelm@20140
    66
lemma lfp_mono: "[| mono(g);  !!Z. f(Z)<=g(Z) |] ==> lfp(f) <= lfp(g)"
wenzelm@20140
    67
  apply (rule lfp_lowerbound)
wenzelm@20140
    68
  apply (rule subset_trans)
wenzelm@20140
    69
   apply (erule meta_spec)
wenzelm@20140
    70
  apply (erule lfp_lemma2)
wenzelm@20140
    71
  done
wenzelm@17456
    72
clasohm@0
    73
end