src/ZF/OrdQuant.thy
 author wenzelm Thu Dec 01 22:03:01 2005 +0100 (2005-12-01) changeset 18324 d1c4b1112e33 parent 17876 b9c92f384109 child 24893 b8ef7afe3a6b permissions -rw-r--r--
unfold_tac: static evaluation of simpset;
1 (*  Title:      ZF/AC/OrdQuant.thy
2     ID:         \$Id\$
3     Authors:    Krzysztof Grabczewski and L C Paulson
4 *)
8 theory OrdQuant imports Ordinal begin
10 subsection {*Quantifiers and union operator for ordinals*}
12 constdefs
14   (* Ordinal Quantifiers *)
15   oall :: "[i, i => o] => o"
16     "oall(A, P) == ALL x. x<A --> P(x)"
18   oex :: "[i, i => o] => o"
19     "oex(A, P)  == EX x. x<A & P(x)"
21   (* Ordinal Union *)
22   OUnion :: "[i, i => i] => i"
23     "OUnion(i,B) == {z: \<Union>x\<in>i. B(x). Ord(i)}"
25 syntax
26   "@oall"     :: "[idt, i, o] => o"        ("(3ALL _<_./ _)" 10)
27   "@oex"      :: "[idt, i, o] => o"        ("(3EX _<_./ _)" 10)
28   "@OUNION"   :: "[idt, i, i] => i"        ("(3UN _<_./ _)" 10)
30 translations
31   "ALL x<a. P"  == "oall(a, %x. P)"
32   "EX x<a. P"   == "oex(a, %x. P)"
33   "UN x<a. B"   == "OUnion(a, %x. B)"
35 syntax (xsymbols)
36   "@oall"     :: "[idt, i, o] => o"        ("(3\<forall>_<_./ _)" 10)
37   "@oex"      :: "[idt, i, o] => o"        ("(3\<exists>_<_./ _)" 10)
38   "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
39 syntax (HTML output)
40   "@oall"     :: "[idt, i, o] => o"        ("(3\<forall>_<_./ _)" 10)
41   "@oex"      :: "[idt, i, o] => o"        ("(3\<exists>_<_./ _)" 10)
42   "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
45 subsubsection {*simplification of the new quantifiers*}
48 (*MOST IMPORTANT that this is added to the simpset BEFORE Ord_atomize
49   is proved.  Ord_atomize would convert this rule to
50     x < 0 ==> P(x) == True, which causes dire effects!*)
51 lemma [simp]: "(ALL x<0. P(x))"
54 lemma [simp]: "~(EX x<0. P(x))"
57 lemma [simp]: "(ALL x<succ(i). P(x)) <-> (Ord(i) --> P(i) & (ALL x<i. P(x)))"
58 apply (simp add: oall_def le_iff)
59 apply (blast intro: lt_Ord2)
60 done
62 lemma [simp]: "(EX x<succ(i). P(x)) <-> (Ord(i) & (P(i) | (EX x<i. P(x))))"
63 apply (simp add: oex_def le_iff)
64 apply (blast intro: lt_Ord2)
65 done
67 subsubsection {*Union over ordinals*}
69 lemma Ord_OUN [intro,simp]:
70      "[| !!x. x<A ==> Ord(B(x)) |] ==> Ord(\<Union>x<A. B(x))"
71 by (simp add: OUnion_def ltI Ord_UN)
73 lemma OUN_upper_lt:
74      "[| a<A;  i < b(a);  Ord(\<Union>x<A. b(x)) |] ==> i < (\<Union>x<A. b(x))"
75 by (unfold OUnion_def lt_def, blast )
77 lemma OUN_upper_le:
78      "[| a<A;  i\<le>b(a);  Ord(\<Union>x<A. b(x)) |] ==> i \<le> (\<Union>x<A. b(x))"
79 apply (unfold OUnion_def, auto)
80 apply (rule UN_upper_le )
81 apply (auto simp add: lt_def)
82 done
84 lemma Limit_OUN_eq: "Limit(i) ==> (\<Union>x<i. x) = i"
85 by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)
87 (* No < version; consider (\<Union>i\<in>nat.i)=nat *)
88 lemma OUN_least:
89      "(!!x. x<A ==> B(x) \<subseteq> C) ==> (\<Union>x<A. B(x)) \<subseteq> C"
90 by (simp add: OUnion_def UN_least ltI)
92 (* No < version; consider (\<Union>i\<in>nat.i)=nat *)
93 lemma OUN_least_le:
94      "[| Ord(i);  !!x. x<A ==> b(x) \<le> i |] ==> (\<Union>x<A. b(x)) \<le> i"
95 by (simp add: OUnion_def UN_least_le ltI Ord_0_le)
97 lemma le_implies_OUN_le_OUN:
98      "[| !!x. x<A ==> c(x) \<le> d(x) |] ==> (\<Union>x<A. c(x)) \<le> (\<Union>x<A. d(x))"
99 by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)
101 lemma OUN_UN_eq:
102      "(!!x. x:A ==> Ord(B(x)))
103       ==> (\<Union>z < (\<Union>x\<in>A. B(x)). C(z)) = (\<Union>x\<in>A. \<Union>z < B(x). C(z))"
106 lemma OUN_Union_eq:
107      "(!!x. x:X ==> Ord(x))
108       ==> (\<Union>z < Union(X). C(z)) = (\<Union>x\<in>X. \<Union>z < x. C(z))"
111 (*So that rule_format will get rid of ALL x<A...*)
112 lemma atomize_oall [symmetric, rulify]:
113      "(!!x. x<A ==> P(x)) == Trueprop (ALL x<A. P(x))"
114 by (simp add: oall_def atomize_all atomize_imp)
116 subsubsection {*universal quantifier for ordinals*}
118 lemma oallI [intro!]:
119     "[| !!x. x<A ==> P(x) |] ==> ALL x<A. P(x)"
122 lemma ospec: "[| ALL x<A. P(x);  x<A |] ==> P(x)"
125 lemma oallE:
126     "[| ALL x<A. P(x);  P(x) ==> Q;  ~x<A ==> Q |] ==> Q"
127 by (simp add: oall_def, blast)
129 lemma rev_oallE [elim]:
130     "[| ALL x<A. P(x);  ~x<A ==> Q;  P(x) ==> Q |] ==> Q"
131 by (simp add: oall_def, blast)
134 (*Trival rewrite rule;   (ALL x<a.P)<->P holds only if a is not 0!*)
135 lemma oall_simp [simp]: "(ALL x<a. True) <-> True"
136 by blast
138 (*Congruence rule for rewriting*)
139 lemma oall_cong [cong]:
140     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
141      ==> oall(a, %x. P(x)) <-> oall(a', %x. P'(x))"
145 subsubsection {*existential quantifier for ordinals*}
147 lemma oexI [intro]:
148     "[| P(x);  x<A |] ==> EX x<A. P(x)"
149 apply (simp add: oex_def, blast)
150 done
152 (*Not of the general form for such rules; ~EX has become ALL~ *)
153 lemma oexCI:
154    "[| ALL x<A. ~P(x) ==> P(a);  a<A |] ==> EX x<A. P(x)"
155 apply (simp add: oex_def, blast)
156 done
158 lemma oexE [elim!]:
159     "[| EX x<A. P(x);  !!x. [| x<A; P(x) |] ==> Q |] ==> Q"
160 apply (simp add: oex_def, blast)
161 done
163 lemma oex_cong [cong]:
164     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
165      ==> oex(a, %x. P(x)) <-> oex(a', %x. P'(x))"
167 done
170 subsubsection {*Rules for Ordinal-Indexed Unions*}
172 lemma OUN_I [intro]: "[| a<i;  b: B(a) |] ==> b: (\<Union>z<i. B(z))"
173 by (unfold OUnion_def lt_def, blast)
175 lemma OUN_E [elim!]:
176     "[| b : (\<Union>z<i. B(z));  !!a.[| b: B(a);  a<i |] ==> R |] ==> R"
177 apply (unfold OUnion_def lt_def, blast)
178 done
180 lemma OUN_iff: "b : (\<Union>x<i. B(x)) <-> (EX x<i. b : B(x))"
181 by (unfold OUnion_def oex_def lt_def, blast)
183 lemma OUN_cong [cong]:
184     "[| i=j;  !!x. x<j ==> C(x)=D(x) |] ==> (\<Union>x<i. C(x)) = (\<Union>x<j. D(x))"
185 by (simp add: OUnion_def lt_def OUN_iff)
187 lemma lt_induct:
188     "[| i<k;  !!x.[| x<k;  ALL y<x. P(y) |] ==> P(x) |]  ==>  P(i)"
189 apply (simp add: lt_def oall_def)
190 apply (erule conjE)
191 apply (erule Ord_induct, assumption, blast)
192 done
195 subsection {*Quantification over a class*}
197 constdefs
198   "rall"     :: "[i=>o, i=>o] => o"
199     "rall(M, P) == ALL x. M(x) --> P(x)"
201   "rex"      :: "[i=>o, i=>o] => o"
202     "rex(M, P) == EX x. M(x) & P(x)"
204 syntax
205   "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3ALL _[_]./ _)" 10)
206   "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3EX _[_]./ _)" 10)
208 syntax (xsymbols)
209   "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3\<forall>_[_]./ _)" 10)
210   "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3\<exists>_[_]./ _)" 10)
211 syntax (HTML output)
212   "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3\<forall>_[_]./ _)" 10)
213   "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3\<exists>_[_]./ _)" 10)
215 translations
216   "ALL x[M]. P"  == "rall(M, %x. P)"
217   "EX x[M]. P"   == "rex(M, %x. P)"
220 subsubsection{*Relativized universal quantifier*}
222 lemma rallI [intro!]: "[| !!x. M(x) ==> P(x) |] ==> ALL x[M]. P(x)"
225 lemma rspec: "[| ALL x[M]. P(x); M(x) |] ==> P(x)"
228 (*Instantiates x first: better for automatic theorem proving?*)
229 lemma rev_rallE [elim]:
230     "[| ALL x[M]. P(x);  ~ M(x) ==> Q;  P(x) ==> Q |] ==> Q"
231 by (simp add: rall_def, blast)
233 lemma rallE: "[| ALL x[M]. P(x);  P(x) ==> Q;  ~ M(x) ==> Q |] ==> Q"
234 by blast
236 (*Trival rewrite rule;   (ALL x[M].P)<->P holds only if A is nonempty!*)
237 lemma rall_triv [simp]: "(ALL x[M]. P) <-> ((EX x. M(x)) --> P)"
240 (*Congruence rule for rewriting*)
241 lemma rall_cong [cong]:
242     "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (ALL x[M]. P(x)) <-> (ALL x[M]. P'(x))"
246 subsubsection{*Relativized existential quantifier*}
248 lemma rexI [intro]: "[| P(x); M(x) |] ==> EX x[M]. P(x)"
249 by (simp add: rex_def, blast)
251 (*The best argument order when there is only one M(x)*)
252 lemma rev_rexI: "[| M(x);  P(x) |] ==> EX x[M]. P(x)"
253 by blast
255 (*Not of the general form for such rules; ~EX has become ALL~ *)
256 lemma rexCI: "[| ALL x[M]. ~P(x) ==> P(a); M(a) |] ==> EX x[M]. P(x)"
257 by blast
259 lemma rexE [elim!]: "[| EX x[M]. P(x);  !!x. [| M(x); P(x) |] ==> Q |] ==> Q"
260 by (simp add: rex_def, blast)
262 (*We do not even have (EX x[M]. True) <-> True unless A is nonempty!!*)
263 lemma rex_triv [simp]: "(EX x[M]. P) <-> ((EX x. M(x)) & P)"
266 lemma rex_cong [cong]:
267     "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (EX x[M]. P(x)) <-> (EX x[M]. P'(x))"
268 by (simp add: rex_def cong: conj_cong)
270 lemma rall_is_ball [simp]: "(\<forall>x[%z. z\<in>A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
271 by blast
273 lemma rex_is_bex [simp]: "(\<exists>x[%z. z\<in>A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
274 by blast
276 lemma atomize_rall: "(!!x. M(x) ==> P(x)) == Trueprop (ALL x[M]. P(x))";
277 by (simp add: rall_def atomize_all atomize_imp)
279 declare atomize_rall [symmetric, rulify]
281 lemma rall_simps1:
282      "(ALL x[M]. P(x) & Q)   <-> (ALL x[M]. P(x)) & ((ALL x[M]. False) | Q)"
283      "(ALL x[M]. P(x) | Q)   <-> ((ALL x[M]. P(x)) | Q)"
284      "(ALL x[M]. P(x) --> Q) <-> ((EX x[M]. P(x)) --> Q)"
285      "(~(ALL x[M]. P(x))) <-> (EX x[M]. ~P(x))"
286 by blast+
288 lemma rall_simps2:
289      "(ALL x[M]. P & Q(x))   <-> ((ALL x[M]. False) | P) & (ALL x[M]. Q(x))"
290      "(ALL x[M]. P | Q(x))   <-> (P | (ALL x[M]. Q(x)))"
291      "(ALL x[M]. P --> Q(x)) <-> (P --> (ALL x[M]. Q(x)))"
292 by blast+
294 lemmas rall_simps [simp] = rall_simps1 rall_simps2
296 lemma rall_conj_distrib:
297     "(ALL x[M]. P(x) & Q(x)) <-> ((ALL x[M]. P(x)) & (ALL x[M]. Q(x)))"
298 by blast
300 lemma rex_simps1:
301      "(EX x[M]. P(x) & Q) <-> ((EX x[M]. P(x)) & Q)"
302      "(EX x[M]. P(x) | Q) <-> (EX x[M]. P(x)) | ((EX x[M]. True) & Q)"
303      "(EX x[M]. P(x) --> Q) <-> ((ALL x[M]. P(x)) --> ((EX x[M]. True) & Q))"
304      "(~(EX x[M]. P(x))) <-> (ALL x[M]. ~P(x))"
305 by blast+
307 lemma rex_simps2:
308      "(EX x[M]. P & Q(x)) <-> (P & (EX x[M]. Q(x)))"
309      "(EX x[M]. P | Q(x)) <-> ((EX x[M]. True) & P) | (EX x[M]. Q(x))"
310      "(EX x[M]. P --> Q(x)) <-> (((ALL x[M]. False) | P) --> (EX x[M]. Q(x)))"
311 by blast+
313 lemmas rex_simps [simp] = rex_simps1 rex_simps2
315 lemma rex_disj_distrib:
316     "(EX x[M]. P(x) | Q(x)) <-> ((EX x[M]. P(x)) | (EX x[M]. Q(x)))"
317 by blast
320 subsubsection{*One-point rule for bounded quantifiers*}
322 lemma rex_triv_one_point1 [simp]: "(EX x[M]. x=a) <-> ( M(a))"
323 by blast
325 lemma rex_triv_one_point2 [simp]: "(EX x[M]. a=x) <-> ( M(a))"
326 by blast
328 lemma rex_one_point1 [simp]: "(EX x[M]. x=a & P(x)) <-> ( M(a) & P(a))"
329 by blast
331 lemma rex_one_point2 [simp]: "(EX x[M]. a=x & P(x)) <-> ( M(a) & P(a))"
332 by blast
334 lemma rall_one_point1 [simp]: "(ALL x[M]. x=a --> P(x)) <-> ( M(a) --> P(a))"
335 by blast
337 lemma rall_one_point2 [simp]: "(ALL x[M]. a=x --> P(x)) <-> ( M(a) --> P(a))"
338 by blast
341 subsubsection{*Sets as Classes*}
343 constdefs setclass :: "[i,i] => o"       ("##_" [40] 40)
344    "setclass(A) == %x. x : A"
346 lemma setclass_iff [simp]: "setclass(A,x) <-> x : A"
349 lemma rall_setclass_is_ball [simp]: "(\<forall>x[##A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
350 by auto
352 lemma rex_setclass_is_bex [simp]: "(\<exists>x[##A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
353 by auto
356 ML
357 {*
358 val oall_def = thm "oall_def"
359 val oex_def = thm "oex_def"
360 val OUnion_def = thm "OUnion_def"
362 val oallI = thm "oallI";
363 val ospec = thm "ospec";
364 val oallE = thm "oallE";
365 val rev_oallE = thm "rev_oallE";
366 val oall_simp = thm "oall_simp";
367 val oall_cong = thm "oall_cong";
368 val oexI = thm "oexI";
369 val oexCI = thm "oexCI";
370 val oexE = thm "oexE";
371 val oex_cong = thm "oex_cong";
372 val OUN_I = thm "OUN_I";
373 val OUN_E = thm "OUN_E";
374 val OUN_iff = thm "OUN_iff";
375 val OUN_cong = thm "OUN_cong";
376 val lt_induct = thm "lt_induct";
378 val rall_def = thm "rall_def"
379 val rex_def = thm "rex_def"
381 val rallI = thm "rallI";
382 val rspec = thm "rspec";
383 val rallE = thm "rallE";
384 val rev_oallE = thm "rev_oallE";
385 val rall_cong = thm "rall_cong";
386 val rexI = thm "rexI";
387 val rexCI = thm "rexCI";
388 val rexE = thm "rexE";
389 val rex_cong = thm "rex_cong";
391 val Ord_atomize =
392     atomize ([("OrdQuant.oall", [ospec]),("OrdQuant.rall", [rspec])]@
393                  ZF_conn_pairs,
394              ZF_mem_pairs);
395 change_simpset (fn ss => ss setmksimps (map mk_eq o Ord_atomize o gen_all));
396 *}
398 text {* Setting up the one-point-rule simproc *}
400 ML_setup {*
401 local
403 val unfold_rex_tac = unfold_tac [rex_def];
404 fun prove_rex_tac ss = unfold_rex_tac ss THEN Quantifier1.prove_one_point_ex_tac;
405 val rearrange_bex = Quantifier1.rearrange_bex prove_rex_tac;
407 val unfold_rall_tac = unfold_tac [rall_def];
408 fun prove_rall_tac ss = unfold_rall_tac ss THEN Quantifier1.prove_one_point_all_tac;
409 val rearrange_ball = Quantifier1.rearrange_ball prove_rall_tac;
411 in
413 val defREX_regroup = Simplifier.simproc (the_context ())
414   "defined REX" ["EX x[M]. P(x) & Q(x)"] rearrange_bex;
415 val defRALL_regroup = Simplifier.simproc (the_context ())
416   "defined RALL" ["ALL x[M]. P(x) --> Q(x)"] rearrange_ball;
418 end;