src/CCL/Lfp.thy

--- a/src/CCL/Lfp.thy	Mon Jul 17 18:42:38 2006 +0200
+++ b/src/CCL/Lfp.thy	Tue Jul 18 02:22:38 2006 +0200
@@ -8,13 +8,67 @@
 
 theory Lfp
 imports Set
-uses "subset.ML" "equalities.ML" "mono.ML"
 begin
 
-constdefs
+definition
   lfp :: "['a set=>'a set] => 'a set"     (*least fixed point*)
   "lfp(f) == Inter({u. f(u) <= u})"
 
-ML {* use_legacy_bindings (the_context ()) *}
+(* lfp(f) is the greatest lower bound of {u. f(u) <= u} *)
+
+lemma lfp_lowerbound: "[| f(A) <= A |] ==> lfp(f) <= A"
+  unfolding lfp_def by blast
+
+lemma lfp_greatest: "[| !!u. f(u) <= u ==> A<=u |] ==> A <= lfp(f)"
+  unfolding lfp_def by blast
+
+lemma lfp_lemma2: "mono(f) ==> f(lfp(f)) <= lfp(f)"
+  by (rule lfp_greatest, rule subset_trans, drule monoD, rule lfp_lowerbound, assumption+)
+
+lemma lfp_lemma3: "mono(f) ==> lfp(f) <= f(lfp(f))"
+  by (rule lfp_lowerbound, frule monoD, drule lfp_lemma2, assumption+)
+
+lemma lfp_Tarski: "mono(f) ==> lfp(f) = f(lfp(f))"
+  by (rule equalityI lfp_lemma2 lfp_lemma3 | assumption)+
+
+
+(*** General induction rule for least fixed points ***)
+
+lemma induct:
+  assumes lfp: "a: lfp(f)"
+    and mono: "mono(f)"
+    and indhyp: "!!x. [| x: f(lfp(f) Int {x. P(x)}) |] ==> P(x)"
+  shows "P(a)"
+  apply (rule_tac a = a in Int_lower2 [THEN subsetD, THEN CollectD])
+  apply (rule lfp [THEN [2] lfp_lowerbound [THEN subsetD]])
+  apply (rule Int_greatest, rule subset_trans, rule Int_lower1 [THEN mono [THEN monoD]],
+    rule mono [THEN lfp_lemma2], rule CollectI [THEN subsetI], rule indhyp, assumption)
+  done
+
+(** Definition forms of lfp_Tarski and induct, to control unfolding **)
+
+lemma def_lfp_Tarski: "[| h==lfp(f);  mono(f) |] ==> h = f(h)"
+  apply unfold
+  apply (drule lfp_Tarski)
+  apply assumption
+  done
+
+lemma def_induct:
+  "[| A == lfp(f);  a:A;  mono(f);                     
+    !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x)         
+  |] ==> P(a)"
+  apply (rule induct [of concl: P a])
+    apply simp
+   apply assumption
+  apply blast
+  done
+
+(*Monotonicity of lfp!*)
+lemma lfp_mono: "[| mono(g);  !!Z. f(Z)<=g(Z) |] ==> lfp(f) <= lfp(g)"
+  apply (rule lfp_lowerbound)
+  apply (rule subset_trans)
+   apply (erule meta_spec)
+  apply (erule lfp_lemma2)
+  done
 
 end