src/CCL/Gfp.ML
 author clasohm Mon Jan 29 13:58:15 1996 +0100 (1996-01-29) changeset 1459 d12da312eff4 parent 757 2ca12511676d child 2035 e329b36d9136 permissions -rw-r--r--
expanded tabs
 clasohm@1459 ` 1` ```(* Title: CCL/gfp ``` clasohm@0 ` 2` ``` ID: \$Id\$ ``` clasohm@0 ` 3` clasohm@0 ` 4` ```Modified version of ``` clasohm@1459 ` 5` ``` Title: HOL/gfp ``` clasohm@1459 ` 6` ``` Author: Lawrence C Paulson, Cambridge University Computer Laboratory ``` clasohm@0 ` 7` ``` Copyright 1993 University of Cambridge ``` clasohm@0 ` 8` clasohm@0 ` 9` ```For gfp.thy. The Knaster-Tarski Theorem for greatest fixed points. ``` clasohm@0 ` 10` ```*) ``` clasohm@0 ` 11` clasohm@0 ` 12` ```open Gfp; ``` clasohm@0 ` 13` clasohm@0 ` 14` ```(*** Proof of Knaster-Tarski Theorem using gfp ***) ``` clasohm@0 ` 15` clasohm@0 ` 16` ```(* gfp(f) is the least upper bound of {u. u <= f(u)} *) ``` clasohm@0 ` 17` clasohm@0 ` 18` ```val prems = goalw Gfp.thy [gfp_def] "[| A <= f(A) |] ==> A <= gfp(f)"; ``` clasohm@0 ` 19` ```by (rtac (CollectI RS Union_upper) 1); ``` clasohm@0 ` 20` ```by (resolve_tac prems 1); ``` clasohm@757 ` 21` ```qed "gfp_upperbound"; ``` clasohm@0 ` 22` clasohm@0 ` 23` ```val prems = goalw Gfp.thy [gfp_def] ``` clasohm@0 ` 24` ``` "[| !!u. u <= f(u) ==> u<=A |] ==> gfp(f) <= A"; ``` clasohm@0 ` 25` ```by (REPEAT (ares_tac ([Union_least]@prems) 1)); ``` clasohm@0 ` 26` ```by (etac CollectD 1); ``` clasohm@757 ` 27` ```qed "gfp_least"; ``` clasohm@0 ` 28` clasohm@0 ` 29` ```val [mono] = goal Gfp.thy "mono(f) ==> gfp(f) <= f(gfp(f))"; ``` clasohm@0 ` 30` ```by (EVERY1 [rtac gfp_least, rtac subset_trans, atac, ``` clasohm@1459 ` 31` ``` rtac (mono RS monoD), rtac gfp_upperbound, atac]); ``` clasohm@757 ` 32` ```qed "gfp_lemma2"; ``` clasohm@0 ` 33` clasohm@0 ` 34` ```val [mono] = goal Gfp.thy "mono(f) ==> f(gfp(f)) <= gfp(f)"; ``` clasohm@0 ` 35` ```by (EVERY1 [rtac gfp_upperbound, rtac (mono RS monoD), ``` clasohm@1459 ` 36` ``` rtac gfp_lemma2, rtac mono]); ``` clasohm@757 ` 37` ```qed "gfp_lemma3"; ``` clasohm@0 ` 38` clasohm@0 ` 39` ```val [mono] = goal Gfp.thy "mono(f) ==> gfp(f) = f(gfp(f))"; ``` clasohm@0 ` 40` ```by (REPEAT (resolve_tac [equalityI,gfp_lemma2,gfp_lemma3,mono] 1)); ``` clasohm@757 ` 41` ```qed "gfp_Tarski"; ``` clasohm@0 ` 42` clasohm@0 ` 43` ```(*** Coinduction rules for greatest fixed points ***) ``` clasohm@0 ` 44` clasohm@0 ` 45` ```(*weak version*) ``` clasohm@0 ` 46` ```val prems = goal Gfp.thy ``` clasohm@0 ` 47` ``` "[| a: A; A <= f(A) |] ==> a : gfp(f)"; ``` clasohm@0 ` 48` ```by (rtac (gfp_upperbound RS subsetD) 1); ``` clasohm@0 ` 49` ```by (REPEAT (ares_tac prems 1)); ``` clasohm@757 ` 50` ```qed "coinduct"; ``` clasohm@0 ` 51` clasohm@0 ` 52` ```val [prem,mono] = goal Gfp.thy ``` clasohm@0 ` 53` ``` "[| A <= f(A) Un gfp(f); mono(f) |] ==> \ ``` clasohm@0 ` 54` ```\ A Un gfp(f) <= f(A Un gfp(f))"; ``` clasohm@0 ` 55` ```by (rtac subset_trans 1); ``` clasohm@0 ` 56` ```by (rtac (mono RS mono_Un) 2); ``` clasohm@0 ` 57` ```by (rtac (mono RS gfp_Tarski RS subst) 1); ``` clasohm@0 ` 58` ```by (rtac (prem RS Un_least) 1); ``` clasohm@0 ` 59` ```by (rtac Un_upper2 1); ``` clasohm@757 ` 60` ```qed "coinduct2_lemma"; ``` clasohm@0 ` 61` clasohm@0 ` 62` ```(*strong version, thanks to Martin Coen*) ``` lcp@642 ` 63` ```val ainA::prems = goal Gfp.thy ``` clasohm@0 ` 64` ``` "[| a: A; A <= f(A) Un gfp(f); mono(f) |] ==> a : gfp(f)"; ``` lcp@642 ` 65` ```by (rtac coinduct 1); ``` lcp@642 ` 66` ```by (rtac (prems MRS coinduct2_lemma) 2); ``` lcp@642 ` 67` ```by (resolve_tac [ainA RS UnI1] 1); ``` clasohm@757 ` 68` ```qed "coinduct2"; ``` clasohm@0 ` 69` clasohm@0 ` 70` ```(*** Even Stronger version of coinduct [by Martin Coen] ``` clasohm@0 ` 71` ``` - instead of the condition A <= f(A) ``` clasohm@0 ` 72` ``` consider A <= (f(A) Un f(f(A)) ...) Un gfp(A) ***) ``` clasohm@0 ` 73` clasohm@0 ` 74` ```val [prem] = goal Gfp.thy "mono(f) ==> mono(%x.f(x) Un A Un B)"; ``` clasohm@0 ` 75` ```by (REPEAT (ares_tac [subset_refl, monoI, Un_mono, prem RS monoD] 1)); ``` clasohm@757 ` 76` ```qed "coinduct3_mono_lemma"; ``` clasohm@0 ` 77` clasohm@0 ` 78` ```val [prem,mono] = goal Gfp.thy ``` clasohm@0 ` 79` ``` "[| A <= f(lfp(%x.f(x) Un A Un gfp(f))); mono(f) |] ==> \ ``` clasohm@0 ` 80` ```\ lfp(%x.f(x) Un A Un gfp(f)) <= f(lfp(%x.f(x) Un A Un gfp(f)))"; ``` clasohm@0 ` 81` ```by (rtac subset_trans 1); ``` lcp@642 ` 82` ```by (rtac (mono RS coinduct3_mono_lemma RS lfp_lemma3) 1); ``` clasohm@0 ` 83` ```by (rtac (Un_least RS Un_least) 1); ``` lcp@642 ` 84` ```by (rtac subset_refl 1); ``` lcp@642 ` 85` ```by (rtac prem 1); ``` lcp@642 ` 86` ```by (rtac (mono RS gfp_Tarski RS equalityD1 RS subset_trans) 1); ``` clasohm@0 ` 87` ```by (rtac (mono RS monoD) 1); ``` clasohm@0 ` 88` ```by (rtac (mono RS coinduct3_mono_lemma RS lfp_Tarski RS ssubst) 1); ``` clasohm@0 ` 89` ```by (rtac Un_upper2 1); ``` clasohm@757 ` 90` ```qed "coinduct3_lemma"; ``` clasohm@0 ` 91` lcp@642 ` 92` ```val ainA::prems = goal Gfp.thy ``` clasohm@0 ` 93` ``` "[| a:A; A <= f(lfp(%x.f(x) Un A Un gfp(f))); mono(f) |] ==> a : gfp(f)"; ``` lcp@642 ` 94` ```by (rtac coinduct 1); ``` lcp@642 ` 95` ```by (rtac (prems MRS coinduct3_lemma) 2); ``` lcp@642 ` 96` ```by (resolve_tac (prems RL [coinduct3_mono_lemma RS lfp_Tarski RS ssubst]) 1); ``` lcp@642 ` 97` ```by (rtac (ainA RS UnI2 RS UnI1) 1); ``` clasohm@757 ` 98` ```qed "coinduct3"; ``` clasohm@0 ` 99` clasohm@0 ` 100` clasohm@0 ` 101` ```(** Definition forms of gfp_Tarski, to control unfolding **) ``` clasohm@0 ` 102` clasohm@0 ` 103` ```val [rew,mono] = goal Gfp.thy "[| h==gfp(f); mono(f) |] ==> h = f(h)"; ``` clasohm@0 ` 104` ```by (rewtac rew); ``` clasohm@0 ` 105` ```by (rtac (mono RS gfp_Tarski) 1); ``` clasohm@757 ` 106` ```qed "def_gfp_Tarski"; ``` clasohm@0 ` 107` clasohm@0 ` 108` ```val rew::prems = goal Gfp.thy ``` clasohm@0 ` 109` ``` "[| h==gfp(f); a:A; A <= f(A) |] ==> a: h"; ``` clasohm@0 ` 110` ```by (rewtac rew); ``` clasohm@0 ` 111` ```by (REPEAT (ares_tac (prems @ [coinduct]) 1)); ``` clasohm@757 ` 112` ```qed "def_coinduct"; ``` clasohm@0 ` 113` clasohm@0 ` 114` ```val rew::prems = goal Gfp.thy ``` clasohm@0 ` 115` ``` "[| h==gfp(f); a:A; A <= f(A) Un h; mono(f) |] ==> a: h"; ``` clasohm@0 ` 116` ```by (rewtac rew); ``` clasohm@0 ` 117` ```by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct2]) 1)); ``` clasohm@757 ` 118` ```qed "def_coinduct2"; ``` clasohm@0 ` 119` clasohm@0 ` 120` ```val rew::prems = goal Gfp.thy ``` clasohm@0 ` 121` ``` "[| h==gfp(f); a:A; A <= f(lfp(%x.f(x) Un A Un h)); mono(f) |] ==> a: h"; ``` clasohm@0 ` 122` ```by (rewtac rew); ``` clasohm@0 ` 123` ```by (REPEAT (ares_tac (map (rewrite_rule [rew]) prems @ [coinduct3]) 1)); ``` clasohm@757 ` 124` ```qed "def_coinduct3"; ``` clasohm@0 ` 125` clasohm@0 ` 126` ```(*Monotonicity of gfp!*) ``` clasohm@0 ` 127` ```val prems = goal Gfp.thy ``` clasohm@0 ` 128` ``` "[| mono(f); !!Z. f(Z)<=g(Z) |] ==> gfp(f) <= gfp(g)"; ``` clasohm@0 ` 129` ```by (rtac gfp_upperbound 1); ``` clasohm@0 ` 130` ```by (rtac subset_trans 1); ``` clasohm@0 ` 131` ```by (rtac gfp_lemma2 1); ``` clasohm@0 ` 132` ```by (resolve_tac prems 1); ``` clasohm@0 ` 133` ```by (resolve_tac prems 1); ``` clasohm@757 ` 134` ```qed "gfp_mono"; ```