src/HOL/Gfp.ML
 author nipkow Wed Aug 18 11:09:40 2004 +0200 (2004-08-18) changeset 15140 322485b816ac parent 14169 0590de71a016 permissions -rw-r--r--
import -> imports
 wenzelm@9422 ` 1` ```(* Title: HOL/Gfp.ML ``` clasohm@923 ` 2` ``` ID: \$Id\$ ``` clasohm@1465 ` 3` ``` Author: Lawrence C Paulson, Cambridge University Computer Laboratory ``` clasohm@923 ` 4` ``` Copyright 1993 University of Cambridge ``` clasohm@923 ` 5` paulson@5148 ` 6` ```The Knaster-Tarski Theorem for greatest fixed points. ``` clasohm@923 ` 7` ```*) ``` clasohm@923 ` 8` clasohm@923 ` 9` ```(*** Proof of Knaster-Tarski Theorem using gfp ***) ``` clasohm@923 ` 10` skalberg@14169 ` 11` ```val gfp_def = thm "gfp_def"; ``` skalberg@14169 ` 12` clasohm@923 ` 13` ```(* gfp(f) is the least upper bound of {u. u <= f(u)} *) ``` clasohm@923 ` 14` paulson@5148 ` 15` ```Goalw [gfp_def] "[| X <= f(X) |] ==> X <= gfp(f)"; ``` paulson@5148 ` 16` ```by (etac (CollectI RS Union_upper) 1); ``` clasohm@923 ` 17` ```qed "gfp_upperbound"; ``` clasohm@923 ` 18` paulson@10067 ` 19` ```val prems = Goalw [gfp_def] ``` clasohm@923 ` 20` ``` "[| !!u. u <= f(u) ==> u<=X |] ==> gfp(f) <= X"; ``` clasohm@923 ` 21` ```by (REPEAT (ares_tac ([Union_least]@prems) 1)); ``` clasohm@923 ` 22` ```by (etac CollectD 1); ``` clasohm@923 ` 23` ```qed "gfp_least"; ``` clasohm@923 ` 24` paulson@5316 ` 25` ```Goal "mono(f) ==> gfp(f) <= f(gfp(f))"; ``` clasohm@923 ` 26` ```by (EVERY1 [rtac gfp_least, rtac subset_trans, atac, ``` paulson@5316 ` 27` ``` etac monoD, rtac gfp_upperbound, atac]); ``` clasohm@923 ` 28` ```qed "gfp_lemma2"; ``` clasohm@923 ` 29` paulson@5316 ` 30` ```Goal "mono(f) ==> f(gfp(f)) <= gfp(f)"; ``` paulson@5316 ` 31` ```by (EVERY1 [rtac gfp_upperbound, rtac monoD, assume_tac, ``` paulson@5316 ` 32` ``` etac gfp_lemma2]); ``` clasohm@923 ` 33` ```qed "gfp_lemma3"; ``` clasohm@923 ` 34` paulson@5316 ` 35` ```Goal "mono(f) ==> gfp(f) = f(gfp(f))"; ``` paulson@5316 ` 36` ```by (REPEAT (ares_tac [equalityI,gfp_lemma2,gfp_lemma3] 1)); ``` nipkow@10186 ` 37` ```qed "gfp_unfold"; ``` clasohm@923 ` 38` clasohm@923 ` 39` ```(*** Coinduction rules for greatest fixed points ***) ``` clasohm@923 ` 40` clasohm@923 ` 41` ```(*weak version*) ``` paulson@5148 ` 42` ```Goal "[| a: X; X <= f(X) |] ==> a : gfp(f)"; ``` clasohm@923 ` 43` ```by (rtac (gfp_upperbound RS subsetD) 1); ``` paulson@5148 ` 44` ```by Auto_tac; ``` clasohm@923 ` 45` ```qed "weak_coinduct"; ``` clasohm@923 ` 46` oheimb@11335 ` 47` ```Goal "!!X. [| a : X; g`X <= f (g`X) |] ==> g a : gfp f"; ``` oheimb@11335 ` 48` ```by (etac (gfp_upperbound RS subsetD) 1); ``` oheimb@11335 ` 49` ```by (etac imageI 1); ``` oheimb@11335 ` 50` ```qed "weak_coinduct_image"; ``` oheimb@11335 ` 51` paulson@10067 ` 52` ```Goal "[| X <= f(X Un gfp(f)); mono(f) |] ==> \ ``` clasohm@923 ` 53` ```\ X Un gfp(f) <= f(X Un gfp(f))"; ``` paulson@10067 ` 54` ```by (blast_tac (claset() addDs [gfp_lemma2, mono_Un]) 1); ``` clasohm@923 ` 55` ```qed "coinduct_lemma"; ``` clasohm@923 ` 56` clasohm@923 ` 57` ```(*strong version, thanks to Coen & Frost*) ``` paulson@5148 ` 58` ```Goal "[| mono(f); a: X; X <= f(X Un gfp(f)) |] ==> a : gfp(f)"; ``` clasohm@923 ` 59` ```by (rtac (coinduct_lemma RSN (2, weak_coinduct)) 1); ``` clasohm@923 ` 60` ```by (REPEAT (ares_tac [UnI1, Un_least] 1)); ``` clasohm@923 ` 61` ```qed "coinduct"; ``` clasohm@923 ` 62` paulson@10067 ` 63` ```Goal "[| mono(f); a: gfp(f) |] ==> a: f(X Un gfp(f))"; ``` paulson@10067 ` 64` ```by (blast_tac (claset() addDs [gfp_lemma2, mono_Un]) 1); ``` clasohm@923 ` 65` ```qed "gfp_fun_UnI2"; ``` clasohm@923 ` 66` clasohm@923 ` 67` ```(*** Even Stronger version of coinduct [by Martin Coen] ``` clasohm@923 ` 68` ``` - instead of the condition X <= f(X) ``` clasohm@923 ` 69` ``` consider X <= (f(X) Un f(f(X)) ...) Un gfp(X) ***) ``` clasohm@923 ` 70` paulson@5316 ` 71` ```Goal "mono(f) ==> mono(%x. f(x) Un X Un B)"; ``` paulson@5316 ` 72` ```by (REPEAT (ares_tac [subset_refl, monoI, Un_mono] 1 ORELSE etac monoD 1)); ``` clasohm@923 ` 73` ```qed "coinduct3_mono_lemma"; ``` clasohm@923 ` 74` paulson@10067 ` 75` ```Goal "[| X <= f(lfp(%x. f(x) Un X Un gfp(f))); mono(f) |] ==> \ ``` wenzelm@3842 ` 76` ```\ lfp(%x. f(x) Un X Un gfp(f)) <= f(lfp(%x. f(x) Un X Un gfp(f)))"; ``` clasohm@923 ` 77` ```by (rtac subset_trans 1); ``` paulson@10067 ` 78` ```by (etac (coinduct3_mono_lemma RS lfp_lemma3) 1); ``` clasohm@923 ` 79` ```by (rtac (Un_least RS Un_least) 1); ``` clasohm@923 ` 80` ```by (rtac subset_refl 1); ``` paulson@10067 ` 81` ```by (assume_tac 1); ``` nipkow@10186 ` 82` ```by (rtac (gfp_unfold RS equalityD1 RS subset_trans) 1); ``` paulson@10067 ` 83` ```by (assume_tac 1); ``` paulson@10067 ` 84` ```by (rtac monoD 1 THEN assume_tac 1); ``` nipkow@10186 ` 85` ```by (stac (coinduct3_mono_lemma RS lfp_unfold) 1); ``` paulson@10067 ` 86` ```by Auto_tac; ``` clasohm@923 ` 87` ```qed "coinduct3_lemma"; ``` clasohm@923 ` 88` paulson@5316 ` 89` ```Goal ``` paulson@5316 ` 90` ``` "[| mono(f); a:X; X <= f(lfp(%x. f(x) Un X Un gfp(f))) |] ==> a : gfp(f)"; ``` clasohm@923 ` 91` ```by (rtac (coinduct3_lemma RSN (2,weak_coinduct)) 1); ``` nipkow@10186 ` 92` ```by (resolve_tac [coinduct3_mono_lemma RS lfp_unfold RS ssubst] 1); ``` paulson@5316 ` 93` ```by Auto_tac; ``` clasohm@923 ` 94` ```qed "coinduct3"; ``` clasohm@923 ` 95` clasohm@923 ` 96` nipkow@10186 ` 97` ```(** Definition forms of gfp_unfold and coinduct, to control unfolding **) ``` clasohm@923 ` 98` paulson@10067 ` 99` ```Goal "[| A==gfp(f); mono(f) |] ==> A = f(A)"; ``` nipkow@10186 ` 100` ```by (auto_tac (claset() addSIs [gfp_unfold], simpset())); ``` nipkow@10186 ` 101` ```qed "def_gfp_unfold"; ``` clasohm@923 ` 102` paulson@10067 ` 103` ```Goal "[| A==gfp(f); mono(f); a:X; X <= f(X Un A) |] ==> a: A"; ``` paulson@10067 ` 104` ```by (auto_tac (claset() addSIs [coinduct], simpset())); ``` clasohm@923 ` 105` ```qed "def_coinduct"; ``` clasohm@923 ` 106` clasohm@923 ` 107` ```(*The version used in the induction/coinduction package*) ``` paulson@5316 ` 108` ```val prems = Goal ``` clasohm@923 ` 109` ``` "[| A == gfp(%w. Collect(P(w))); mono(%w. Collect(P(w))); \ ``` clasohm@923 ` 110` ```\ a: X; !!z. z: X ==> P (X Un A) z |] ==> \ ``` clasohm@923 ` 111` ```\ a : A"; ``` clasohm@923 ` 112` ```by (rtac def_coinduct 1); ``` clasohm@923 ` 113` ```by (REPEAT (ares_tac (prems @ [subsetI,CollectI]) 1)); ``` clasohm@923 ` 114` ```qed "def_Collect_coinduct"; ``` clasohm@923 ` 115` paulson@10067 ` 116` ```Goal "[| A==gfp(f); mono(f); a:X; X <= f(lfp(%x. f(x) Un X Un A)) |] \ ``` paulson@10067 ` 117` ```\ ==> a: A"; ``` paulson@10067 ` 118` ```by (auto_tac (claset() addSIs [coinduct3], simpset())); ``` clasohm@923 ` 119` ```qed "def_coinduct3"; ``` clasohm@923 ` 120` clasohm@923 ` 121` ```(*Monotonicity of gfp!*) ``` paulson@5316 ` 122` ```val [prem] = Goal "[| !!Z. f(Z)<=g(Z) |] ==> gfp(f) <= gfp(g)"; ``` clasohm@1465 ` 123` ```by (rtac (gfp_upperbound RS gfp_least) 1); ``` clasohm@1465 ` 124` ```by (etac (prem RSN (2,subset_trans)) 1); ``` clasohm@923 ` 125` ```qed "gfp_mono"; ```