isabelle: src/CCL/Lfp.thy@9a1710a64412 (annotated)

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

author	wenzelm
	Fri, 10 Jan 2014 23:42:18 +0100
changeset 54985	9a1710a64412
parent 32153	a0e57fb1b930
child 58889	5b7a9633cfa8
permissions	-rw-r--r--