# HG changeset patch
# User berghofe
# Date 1160755816 -7200
# Node ID 5693e4471c2b22f9af6fce6fb701ced9d77b1f4f
# Parent  430b35c9cd27e92c77f186f2d31daaed716e0da6
Generalized gfp and lfp to arbitrary complete lattices.

diff -r 430b35c9cd27 -r 5693e4471c2b src/HOL/FixedPoint.thy
--- a/src/HOL/FixedPoint.thy	Fri Oct 13 18:08:48 2006 +0200
+++ b/src/HOL/FixedPoint.thy	Fri Oct 13 18:10:16 2006 +0200
@@ -1,6 +1,7 @@
 (*  Title:      HOL/FixedPoint.thy
     ID:         $Id$
     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
+    Author:     Stefan Berghofer, TU Muenchen
     Copyright   1992  University of Cambridge
 *)
 
@@ -10,53 +11,347 @@
 imports Product_Type
 begin
 
+subsection {* Complete lattices *}
+
+consts
+  Meet :: "'a::order set \<Rightarrow> 'a"
+  Join :: "'a::order set \<Rightarrow> 'a"
+
+defs Join_def: "Join A == Meet {b. \<forall>a \<in> A. a <= b}"
+
+axclass comp_lat < order
+  Meet_lower: "x \<in> A \<Longrightarrow> Meet A <= x"
+  Meet_greatest: "(\<And>x. x \<in> A \<Longrightarrow> z <= x) \<Longrightarrow> z <= Meet A"
+
+theorem Join_upper: "(x::'a::comp_lat) \<in> A \<Longrightarrow> x <= Join A"
+  by (auto simp: Join_def intro: Meet_greatest)
+
+theorem Join_least: "(\<And>x::'a::comp_lat. x \<in> A \<Longrightarrow> x <= z) \<Longrightarrow> Join A <= z"
+  by (auto simp: Join_def intro: Meet_lower)
+
+text {* A complete lattice is a lattice *}
+
+lemma is_meet_Meet: "is_meet (\<lambda>(x::'a::comp_lat) y. Meet {x, y})"
+  by (auto simp: is_meet_def intro: Meet_lower Meet_greatest)
+
+lemma is_join_Join: "is_join (\<lambda>(x::'a::comp_lat) y. Join {x, y})"
+  by (auto simp: is_join_def intro: Join_upper Join_least)
+
+instance comp_lat < lorder
+proof
+  from is_meet_Meet show "\<exists>m::'a\<Rightarrow>'a\<Rightarrow>'a. is_meet m" by iprover
+  from is_join_Join show "\<exists>j::'a\<Rightarrow>'a\<Rightarrow>'a. is_join j" by iprover
+qed
+
+lemma mono_join: "mono f \<Longrightarrow> join (f A) (f B) <= f (join A B)"
+  by (auto simp add: mono_def intro: join_imp_le join_left_le join_right_le)
+
+lemma mono_meet: "mono f \<Longrightarrow> f (meet A B) <= meet (f A) (f B)"
+  by (auto simp add: mono_def intro: meet_imp_le meet_left_le meet_right_le)
+
+
+subsection {* Some instances of the type class of complete lattices *}
+
+subsubsection {* Booleans *}
+
+instance bool :: ord ..
+
+defs
+  le_bool_def: "P <= Q == P \<longrightarrow> Q"
+  less_bool_def: "P < Q == (P::bool) <= Q \<and> P \<noteq> Q"
+
+theorem le_boolI: "(P \<Longrightarrow> Q) \<Longrightarrow> P <= Q"
+  by (simp add: le_bool_def)
+
+theorem le_boolI': "P \<longrightarrow> Q \<Longrightarrow> P <= Q"
+  by (simp add: le_bool_def)
+
+theorem le_boolE: "P <= Q \<Longrightarrow> P \<Longrightarrow> (Q \<Longrightarrow> R) \<Longrightarrow> R"
+  by (simp add: le_bool_def)
+
+theorem le_boolD: "P <= Q \<Longrightarrow> P \<longrightarrow> Q"
+  by (simp add: le_bool_def)
+
+instance bool :: order
+  apply intro_classes
+  apply (unfold le_bool_def less_bool_def)
+  apply iprover+
+  done
+
+defs Meet_bool_def: "Meet A == ALL x:A. x"
+
+instance bool :: comp_lat
+  apply intro_classes
+  apply (unfold Meet_bool_def)
+  apply (iprover intro!: le_boolI elim: ballE)
+  apply (iprover intro!: ballI le_boolI elim: ballE le_boolE)
+  done
+
+theorem meet_bool_eq: "meet P Q = (P \<and> Q)"
+  apply (rule order_antisym)
+  apply (rule le_boolI)
+  apply (rule conjI)
+  apply (rule le_boolE)
+  apply (rule meet_left_le)
+  apply assumption+
+  apply (rule le_boolE)
+  apply (rule meet_right_le)
+  apply assumption+
+  apply (rule meet_imp_le)
+  apply (rule le_boolI)
+  apply (erule conjunct1)
+  apply (rule le_boolI)
+  apply (erule conjunct2)
+  done
+
+theorem join_bool_eq: "join P Q = (P \<or> Q)"
+  apply (rule order_antisym)
+  apply (rule join_imp_le)
+  apply (rule le_boolI)
+  apply (erule disjI1)
+  apply (rule le_boolI)
+  apply (erule disjI2)
+  apply (rule le_boolI)
+  apply (erule disjE)
+  apply (rule le_boolE)
+  apply (rule join_left_le)
+  apply assumption+
+  apply (rule le_boolE)
+  apply (rule join_right_le)
+  apply assumption+
+  done
+
+theorem Join_bool_eq: "Join A = (EX x:A. x)"
+  apply (rule order_antisym)
+  apply (rule Join_least)
+  apply (rule le_boolI)
+  apply (erule bexI, assumption)
+  apply (rule le_boolI)
+  apply (erule bexE)
+  apply (rule le_boolE)
+  apply (rule Join_upper)
+  apply assumption+
+  done
+
+subsubsection {* Functions *}
+
+instance "fun" :: (type, ord) ord ..
+
+defs
+  le_fun_def: "f <= g == \<forall>x. f x <= g x"
+  less_fun_def: "f < g == (f::'a\<Rightarrow>'b::ord) <= g \<and> f \<noteq> g"
+
+theorem le_funI: "(\<And>x. f x <= g x) \<Longrightarrow> f <= g"
+  by (simp add: le_fun_def)
+
+theorem le_funE: "f <= g \<Longrightarrow> (f x <= g x \<Longrightarrow> P) \<Longrightarrow> P"
+  by (simp add: le_fun_def)
+
+theorem le_funD: "f <= g \<Longrightarrow> f x <= g x"
+  by (simp add: le_fun_def)
+
+text {*
+Handy introduction and elimination rules for @{text "\<le>"}
+on unary and binary predicates
+*}
+
+lemma predicate1I [intro]:
+  assumes PQ: "\<And>x. P x \<Longrightarrow> Q x"
+  shows "P \<le> Q"
+  apply (rule le_funI)
+  apply (rule le_boolI)
+  apply (rule PQ)
+  apply assumption
+  done
+
+lemma predicate1D [elim]: "P \<le> Q \<Longrightarrow> P x \<Longrightarrow> Q x"
+  apply (erule le_funE)
+  apply (erule le_boolE)
+  apply assumption+
+  done
+
+lemma predicate2I [intro]:
+  assumes PQ: "\<And>x y. P x y \<Longrightarrow> Q x y"
+  shows "P \<le> Q"
+  apply (rule le_funI)+
+  apply (rule le_boolI)
+  apply (rule PQ)
+  apply assumption
+  done
+
+lemma predicate2D [elim]: "P \<le> Q \<Longrightarrow> P x y \<Longrightarrow> Q x y"
+  apply (erule le_funE)+
+  apply (erule le_boolE)
+  apply assumption+
+  done
+
+instance "fun" :: (type, order) order
+  apply intro_classes
+  apply (rule le_funI)
+  apply (rule order_refl)
+  apply (rule le_funI)
+  apply (erule le_funE)+
+  apply (erule order_trans)
+  apply assumption
+  apply (rule ext)
+  apply (erule le_funE)+
+  apply (erule order_antisym)
+  apply assumption
+  apply (simp add: less_fun_def)
+  done
+
+defs Meet_fun_def: "Meet A == (\<lambda>x. Meet {y. EX f:A. y = f x})"
+
+instance "fun" :: (type, comp_lat) comp_lat
+  apply intro_classes
+  apply (unfold Meet_fun_def)
+  apply (rule le_funI)
+  apply (rule Meet_lower)
+  apply (rule CollectI)
+  apply (rule bexI)
+  apply (rule refl)
+  apply assumption
+  apply (rule le_funI)
+  apply (rule Meet_greatest)
+  apply (erule CollectE)
+  apply (erule bexE)
+  apply (iprover elim: le_funE)
+  done
+
+theorem meet_fun_eq: "meet f g = (\<lambda>x. meet (f x) (g x))"
+  apply (rule order_antisym)
+  apply (rule le_funI)
+  apply (rule meet_imp_le)
+  apply (rule le_funD [OF meet_left_le])
+  apply (rule le_funD [OF meet_right_le])
+  apply (rule meet_imp_le)
+  apply (rule le_funI)
+  apply (rule meet_left_le)
+  apply (rule le_funI)
+  apply (rule meet_right_le)
+  done
+
+theorem join_fun_eq: "join f g = (\<lambda>x. join (f x) (g x))"
+  apply (rule order_antisym)
+  apply (rule join_imp_le)
+  apply (rule le_funI)
+  apply (rule join_left_le)
+  apply (rule le_funI)
+  apply (rule join_right_le)
+  apply (rule le_funI)
+  apply (rule join_imp_le)
+  apply (rule le_funD [OF join_left_le])
+  apply (rule le_funD [OF join_right_le])
+  done
+
+theorem Join_fun_eq: "Join A = (\<lambda>x. Join {y::'a::comp_lat. EX f:A. y = f x})"
+  apply (rule order_antisym)
+  apply (rule Join_least)
+  apply (rule le_funI)
+  apply (rule Join_upper)
+  apply fast
+  apply (rule le_funI)
+  apply (rule Join_least)
+  apply (erule CollectE)
+  apply (erule bexE)
+  apply (drule le_funD [OF Join_upper])
+  apply simp
+  done
+
+subsubsection {* Sets *}
+
+defs Meet_set_def: "Meet S == \<Inter>S"
+
+instance set :: (type) comp_lat
+  by intro_classes (auto simp add: Meet_set_def)
+
+theorem meet_set_eq: "meet A B = A \<inter> B"
+  apply (rule subset_antisym)
+  apply (rule Int_greatest)
+  apply (rule meet_left_le)
+  apply (rule meet_right_le)
+  apply (rule meet_imp_le)
+  apply (rule Int_lower1)
+  apply (rule Int_lower2)
+  done
+
+theorem join_set_eq: "join A B = A \<union> B"
+  apply (rule subset_antisym)
+  apply (rule join_imp_le)
+  apply (rule Un_upper1)
+  apply (rule Un_upper2)
+  apply (rule Un_least)
+  apply (rule join_left_le)
+  apply (rule join_right_le)
+  done
+
+theorem Join_set_eq: "Join S = \<Union>S"
+  apply (rule subset_antisym)
+  apply (rule Join_least)
+  apply (erule Union_upper)
+  apply (rule Union_least)
+  apply (erule Join_upper)
+  done
+
+
+subsection {* Least and greatest fixed points *}
+
 constdefs
-  lfp :: "['a set \<Rightarrow> 'a set] \<Rightarrow> 'a set"
-    "lfp(f) == Inter({u. f(u) \<subseteq> u})"    --{*least fixed point*}
+  lfp :: "(('a::comp_lat) => 'a) => 'a"
+  "lfp f == Meet {u. f u <= u}"    --{*least fixed point*}
 
-  gfp :: "['a set=>'a set] => 'a set"
-    "gfp(f) == Union({u. u \<subseteq> f(u)})"
+  gfp :: "(('a::comp_lat) => 'a) => 'a"
+  "gfp f == Join {u. u <= f u}"    --{*greatest fixed point*}
 
 
 subsection{*Proof of Knaster-Tarski Theorem using @{term lfp}*}
 
 
 text{*@{term "lfp f"} is the least upper bound of 
-      the set @{term "{u. f(u) \<subseteq> u}"} *}
+      the set @{term "{u. f(u) \<le> u}"} *}
+
+lemma lfp_lowerbound: "f A \<le> A ==> lfp f \<le> A"
+  by (auto simp add: lfp_def intro: Meet_lower)
+
+lemma lfp_greatest: "(!!u. f u \<le> u ==> A \<le> u) ==> A \<le> lfp f"
+  by (auto simp add: lfp_def intro: Meet_greatest)
 
-lemma lfp_lowerbound: "f(A) \<subseteq> A ==> lfp(f) \<subseteq> A"
-by (auto simp add: lfp_def)
+lemma lfp_lemma2: "mono f ==> f (lfp f) \<le> lfp f"
+  by (iprover intro: lfp_greatest order_trans monoD lfp_lowerbound)
 
-lemma lfp_greatest: "[| !!u. f(u) \<subseteq> u ==> A\<subseteq>u |] ==> A \<subseteq> lfp(f)"
-by (auto simp add: lfp_def)
+lemma lfp_lemma3: "mono f ==> lfp f \<le> f (lfp f)"
+  by (iprover intro: lfp_lemma2 monoD lfp_lowerbound)
+
+lemma lfp_unfold: "mono f ==> lfp f = f (lfp f)"
+  by (iprover intro: order_antisym lfp_lemma2 lfp_lemma3)
 
-lemma lfp_lemma2: "mono(f) ==> f(lfp(f)) \<subseteq> lfp(f)"
-by (iprover intro: lfp_greatest subset_trans monoD lfp_lowerbound)
-
-lemma lfp_lemma3: "mono(f) ==> lfp(f) \<subseteq> f(lfp(f))"
-by (iprover intro: lfp_lemma2 monoD lfp_lowerbound)
+subsection{*General induction rules for least fixed points*}
 
-lemma lfp_unfold: "mono(f) ==> lfp(f) = f(lfp(f))"
-by (iprover intro: equalityI lfp_lemma2 lfp_lemma3)
+theorem lfp_induct:
+  assumes mono: "mono f" and ind: "f (meet (lfp f) P) <= P"
+  shows "lfp f <= P"
+proof -
+  have "meet (lfp f) P <= lfp f" by (rule meet_left_le)
+  with mono have "f (meet (lfp f) P) <= f (lfp f)" ..
+  also from mono have "f (lfp f) = lfp f" by (rule lfp_unfold [symmetric])
+  finally have "f (meet (lfp f) P) <= lfp f" .
+  from this and ind have "f (meet (lfp f) P) <= meet (lfp f) P" by (rule meet_imp_le)
+  hence "lfp f <= meet (lfp f) P" by (rule lfp_lowerbound)
+  also have "meet (lfp f) P <= P" by (rule meet_right_le)
+  finally show ?thesis .
+qed
 
-subsection{*General induction rules for greatest fixed points*}
-
-lemma lfp_induct: 
+lemma lfp_induct_set:
   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)
- apply (rule subset_trans [OF Int_lower1 [THEN mono [THEN monoD]]
-                              mono [THEN lfp_lemma2]]) 
-apply (blast intro: indhyp) 
-done
+  by (rule lfp_induct [THEN subsetD, THEN CollectD, OF mono _ lfp])
+    (auto simp: meet_set_eq intro: indhyp)
 
 
 text{*Version of induction for binary relations*}
-lemmas lfp_induct2 =  lfp_induct [of "(a,b)", split_format (complete)]
+lemmas lfp_induct2 =  lfp_induct_set [of "(a,b)", split_format (complete)]
 
 
 lemma lfp_ordinal_induct: 
@@ -82,36 +377,42 @@
 by (auto intro!: lfp_unfold)
 
 lemma def_lfp_induct: 
+    "[| A == lfp(f); mono(f);
+        f (meet A P) \<le> P
+     |] ==> A \<le> P"
+  by (blast intro: lfp_induct)
+
+lemma def_lfp_induct_set: 
     "[| A == lfp(f);  mono(f);   a:A;                    
         !!x. [| x: f(A Int {x. P(x)}) |] ==> P(x)         
      |] ==> P(a)"
-by (blast intro: lfp_induct)
+  by (blast intro: lfp_induct_set)
 
 (*Monotonicity of lfp!*)
-lemma lfp_mono: "[| !!Z. f(Z)\<subseteq>g(Z) |] ==> lfp(f) \<subseteq> lfp(g)"
-by (rule lfp_lowerbound [THEN lfp_greatest], blast)
+lemma lfp_mono: "(!!Z. f Z \<le> g Z) ==> lfp f \<le> lfp g"
+  by (rule lfp_lowerbound [THEN lfp_greatest], blast intro: order_trans)
 
 
 subsection{*Proof of Knaster-Tarski Theorem using @{term gfp}*}
 
 
 text{*@{term "gfp f"} is the greatest lower bound of 
-      the set @{term "{u. u \<subseteq> f(u)}"} *}
+      the set @{term "{u. u \<le> f(u)}"} *}
 
-lemma gfp_upperbound: "[| X \<subseteq> f(X) |] ==> X \<subseteq> gfp(f)"
-by (auto simp add: gfp_def)
+lemma gfp_upperbound: "X \<le> f X ==> X \<le> gfp f"
+  by (auto simp add: gfp_def intro: Join_upper)
 
-lemma gfp_least: "[| !!u. u \<subseteq> f(u) ==> u\<subseteq>X |] ==> gfp(f) \<subseteq> X"
-by (auto simp add: gfp_def)
+lemma gfp_least: "(!!u. u \<le> f u ==> u \<le> X) ==> gfp f \<le> X"
+  by (auto simp add: gfp_def intro: Join_least)
 
-lemma gfp_lemma2: "mono(f) ==> gfp(f) \<subseteq> f(gfp(f))"
-by (iprover intro: gfp_least subset_trans monoD gfp_upperbound)
+lemma gfp_lemma2: "mono f ==> gfp f \<le> f (gfp f)"
+  by (iprover intro: gfp_least order_trans monoD gfp_upperbound)
 
-lemma gfp_lemma3: "mono(f) ==> f(gfp(f)) \<subseteq> gfp(f)"
-by (iprover intro: gfp_lemma2 monoD gfp_upperbound)
+lemma gfp_lemma3: "mono f ==> f (gfp f) \<le> gfp f"
+  by (iprover intro: gfp_lemma2 monoD gfp_upperbound)
 
-lemma gfp_unfold: "mono(f) ==> gfp(f) = f(gfp(f))"
-by (iprover intro: equalityI gfp_lemma2 gfp_lemma3)
+lemma gfp_unfold: "mono f ==> gfp f = f (gfp f)"
+  by (iprover intro: order_antisym gfp_lemma2 gfp_lemma3)
 
 subsection{*Coinduction rules for greatest fixed points*}
 
@@ -125,12 +426,28 @@
 done
 
 lemma coinduct_lemma:
-     "[| X \<subseteq> f(X Un gfp(f));  mono(f) |] ==> X Un gfp(f) \<subseteq> f(X Un gfp(f))"
-by (blast dest: gfp_lemma2 mono_Un)
+     "[| X \<le> f (join X (gfp f));  mono f |] ==> join X (gfp f) \<le> f (join X (gfp f))"
+  apply (frule gfp_lemma2)
+  apply (drule mono_join)
+  apply (rule join_imp_le)
+  apply assumption
+  apply (rule order_trans)
+  apply (rule order_trans)
+  apply assumption
+  apply (rule join_right_le)
+  apply assumption
+  done
 
 text{*strong version, thanks to Coen and Frost*}
-lemma coinduct: "[| mono(f);  a: X;  X \<subseteq> f(X Un gfp(f)) |] ==> a : gfp(f)"
-by (blast intro: weak_coinduct [OF _ coinduct_lemma])
+lemma coinduct_set: "[| mono(f);  a: X;  X \<subseteq> f(X Un gfp(f)) |] ==> a : gfp(f)"
+by (blast intro: weak_coinduct [OF _ coinduct_lemma, simplified join_set_eq])
+
+lemma coinduct: "[| mono(f); X \<le> f (join X (gfp f)) |] ==> X \<le> gfp(f)"
+  apply (rule order_trans)
+  apply (rule join_left_le)
+  apply (erule gfp_upperbound [OF coinduct_lemma])
+  apply assumption
+  done
 
 lemma gfp_fun_UnI2: "[| mono(f);  a: gfp(f) |] ==> a: f(X Un gfp(f))"
 by (blast dest: gfp_lemma2 mono_Un)
@@ -169,15 +486,19 @@
 by (auto intro!: gfp_unfold)
 
 lemma def_coinduct:
+     "[| A==gfp(f);  mono(f);  X \<le> f(join X A) |] ==> X \<le> A"
+by (iprover intro!: coinduct)
+
+lemma def_coinduct_set:
      "[| A==gfp(f);  mono(f);  a:X;  X \<subseteq> f(X Un A) |] ==> a: A"
-by (auto intro!: coinduct)
+by (auto intro!: coinduct_set)
 
 (*The version used in the induction/coinduction package*)
 lemma def_Collect_coinduct:
     "[| A == gfp(%w. Collect(P(w)));  mono(%w. Collect(P(w)));   
         a: X;  !!z. z: X ==> P (X Un A) z |] ==>  
      a : A"
-apply (erule def_coinduct, auto) 
+apply (erule def_coinduct_set, auto) 
 done
 
 lemma def_coinduct3:
@@ -185,8 +506,8 @@
 by (auto intro!: coinduct3)
 
 text{*Monotonicity of @{term gfp}!*}
-lemma gfp_mono: "[| !!Z. f(Z)\<subseteq>g(Z) |] ==> gfp(f) \<subseteq> gfp(g)"
-by (rule gfp_upperbound [THEN gfp_least], blast)
+lemma gfp_mono: "(!!Z. f Z \<le> g Z) ==> gfp f \<le> gfp g"
+  by (rule gfp_upperbound [THEN gfp_least], blast intro: order_trans)
 
 
 ML
@@ -200,6 +521,7 @@
 val lfp_ordinal_induct = thm "lfp_ordinal_induct";
 val def_lfp_unfold = thm "def_lfp_unfold";
 val def_lfp_induct = thm "def_lfp_induct";
+val def_lfp_induct_set = thm "def_lfp_induct_set";
 val lfp_mono = thm "lfp_mono";
 val gfp_def = thm "gfp_def";
 val gfp_upperbound = thm "gfp_upperbound";
@@ -215,6 +537,16 @@
 val def_Collect_coinduct = thm "def_Collect_coinduct";
 val def_coinduct3 = thm "def_coinduct3";
 val gfp_mono = thm "gfp_mono";
+val le_funI = thm "le_funI";
+val le_boolI = thm "le_boolI";
+val le_boolI' = thm "le_boolI'";
+val meet_fun_eq = thm "meet_fun_eq";
+val meet_bool_eq = thm "meet_bool_eq";
+val le_funE = thm "le_funE";
+val le_boolE = thm "le_boolE";
+val le_boolD = thm "le_boolD";
+val le_bool_def = thm "le_bool_def";
+val le_fun_def = thm "le_fun_def";
 *}
 
 end