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