src/ZF/OrdQuant.thy
author wenzelm
Wed Sep 17 21:27:08 2008 +0200 (2008-09-17)
changeset 28262 aa7ca36d67fd
parent 26480 544cef16045b
child 32010 cb1a1c94b4cd
permissions -rw-r--r--
back to dynamic the_context(), because static @{theory} is invalidated if ML environment changes within the same code block;
     1 (*  Title:      ZF/AC/OrdQuant.thy
     2     ID:         $Id$
     3     Authors:    Krzysztof Grabczewski and L C Paulson
     4 *)
     5 
     6 header {*Special quantifiers*}
     7 
     8 theory OrdQuant imports Ordinal begin
     9 
    10 subsection {*Quantifiers and union operator for ordinals*}
    11 
    12 definition
    13   (* Ordinal Quantifiers *)
    14   oall :: "[i, i => o] => o"  where
    15     "oall(A, P) == ALL x. x<A --> P(x)"
    16 
    17 definition
    18   oex :: "[i, i => o] => o"  where
    19     "oex(A, P)  == EX x. x<A & P(x)"
    20 
    21 definition
    22   (* Ordinal Union *)
    23   OUnion :: "[i, i => i] => i"  where
    24     "OUnion(i,B) == {z: \<Union>x\<in>i. B(x). Ord(i)}"
    25 
    26 syntax
    27   "@oall"     :: "[idt, i, o] => o"        ("(3ALL _<_./ _)" 10)
    28   "@oex"      :: "[idt, i, o] => o"        ("(3EX _<_./ _)" 10)
    29   "@OUNION"   :: "[idt, i, i] => i"        ("(3UN _<_./ _)" 10)
    30 
    31 translations
    32   "ALL x<a. P"  == "CONST oall(a, %x. P)"
    33   "EX x<a. P"   == "CONST oex(a, %x. P)"
    34   "UN x<a. B"   == "CONST OUnion(a, %x. B)"
    35 
    36 syntax (xsymbols)
    37   "@oall"     :: "[idt, i, o] => o"        ("(3\<forall>_<_./ _)" 10)
    38   "@oex"      :: "[idt, i, o] => o"        ("(3\<exists>_<_./ _)" 10)
    39   "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
    40 syntax (HTML output)
    41   "@oall"     :: "[idt, i, o] => o"        ("(3\<forall>_<_./ _)" 10)
    42   "@oex"      :: "[idt, i, o] => o"        ("(3\<exists>_<_./ _)" 10)
    43   "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
    44 
    45 
    46 subsubsection {*simplification of the new quantifiers*}
    47 
    48 
    49 (*MOST IMPORTANT that this is added to the simpset BEFORE Ord_atomize
    50   is proved.  Ord_atomize would convert this rule to
    51     x < 0 ==> P(x) == True, which causes dire effects!*)
    52 lemma [simp]: "(ALL x<0. P(x))"
    53 by (simp add: oall_def)
    54 
    55 lemma [simp]: "~(EX x<0. P(x))"
    56 by (simp add: oex_def)
    57 
    58 lemma [simp]: "(ALL x<succ(i). P(x)) <-> (Ord(i) --> P(i) & (ALL x<i. P(x)))"
    59 apply (simp add: oall_def le_iff)
    60 apply (blast intro: lt_Ord2)
    61 done
    62 
    63 lemma [simp]: "(EX x<succ(i). P(x)) <-> (Ord(i) & (P(i) | (EX x<i. P(x))))"
    64 apply (simp add: oex_def le_iff)
    65 apply (blast intro: lt_Ord2)
    66 done
    67 
    68 subsubsection {*Union over ordinals*}
    69 
    70 lemma Ord_OUN [intro,simp]:
    71      "[| !!x. x<A ==> Ord(B(x)) |] ==> Ord(\<Union>x<A. B(x))"
    72 by (simp add: OUnion_def ltI Ord_UN)
    73 
    74 lemma OUN_upper_lt:
    75      "[| a<A;  i < b(a);  Ord(\<Union>x<A. b(x)) |] ==> i < (\<Union>x<A. b(x))"
    76 by (unfold OUnion_def lt_def, blast )
    77 
    78 lemma OUN_upper_le:
    79      "[| a<A;  i\<le>b(a);  Ord(\<Union>x<A. b(x)) |] ==> i \<le> (\<Union>x<A. b(x))"
    80 apply (unfold OUnion_def, auto)
    81 apply (rule UN_upper_le )
    82 apply (auto simp add: lt_def)
    83 done
    84 
    85 lemma Limit_OUN_eq: "Limit(i) ==> (\<Union>x<i. x) = i"
    86 by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)
    87 
    88 (* No < version; consider (\<Union>i\<in>nat.i)=nat *)
    89 lemma OUN_least:
    90      "(!!x. x<A ==> B(x) \<subseteq> C) ==> (\<Union>x<A. B(x)) \<subseteq> C"
    91 by (simp add: OUnion_def UN_least ltI)
    92 
    93 (* No < version; consider (\<Union>i\<in>nat.i)=nat *)
    94 lemma OUN_least_le:
    95      "[| Ord(i);  !!x. x<A ==> b(x) \<le> i |] ==> (\<Union>x<A. b(x)) \<le> i"
    96 by (simp add: OUnion_def UN_least_le ltI Ord_0_le)
    97 
    98 lemma le_implies_OUN_le_OUN:
    99      "[| !!x. x<A ==> c(x) \<le> d(x) |] ==> (\<Union>x<A. c(x)) \<le> (\<Union>x<A. d(x))"
   100 by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)
   101 
   102 lemma OUN_UN_eq:
   103      "(!!x. x:A ==> Ord(B(x)))
   104       ==> (\<Union>z < (\<Union>x\<in>A. B(x)). C(z)) = (\<Union>x\<in>A. \<Union>z < B(x). C(z))"
   105 by (simp add: OUnion_def)
   106 
   107 lemma OUN_Union_eq:
   108      "(!!x. x:X ==> Ord(x))
   109       ==> (\<Union>z < Union(X). C(z)) = (\<Union>x\<in>X. \<Union>z < x. C(z))"
   110 by (simp add: OUnion_def)
   111 
   112 (*So that rule_format will get rid of ALL x<A...*)
   113 lemma atomize_oall [symmetric, rulify]:
   114      "(!!x. x<A ==> P(x)) == Trueprop (ALL x<A. P(x))"
   115 by (simp add: oall_def atomize_all atomize_imp)
   116 
   117 subsubsection {*universal quantifier for ordinals*}
   118 
   119 lemma oallI [intro!]:
   120     "[| !!x. x<A ==> P(x) |] ==> ALL x<A. P(x)"
   121 by (simp add: oall_def)
   122 
   123 lemma ospec: "[| ALL x<A. P(x);  x<A |] ==> P(x)"
   124 by (simp add: oall_def)
   125 
   126 lemma oallE:
   127     "[| ALL x<A. P(x);  P(x) ==> Q;  ~x<A ==> Q |] ==> Q"
   128 by (simp add: oall_def, blast)
   129 
   130 lemma rev_oallE [elim]:
   131     "[| ALL x<A. P(x);  ~x<A ==> Q;  P(x) ==> Q |] ==> Q"
   132 by (simp add: oall_def, blast)
   133 
   134 
   135 (*Trival rewrite rule;   (ALL x<a.P)<->P holds only if a is not 0!*)
   136 lemma oall_simp [simp]: "(ALL x<a. True) <-> True"
   137 by blast
   138 
   139 (*Congruence rule for rewriting*)
   140 lemma oall_cong [cong]:
   141     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
   142      ==> oall(a, %x. P(x)) <-> oall(a', %x. P'(x))"
   143 by (simp add: oall_def)
   144 
   145 
   146 subsubsection {*existential quantifier for ordinals*}
   147 
   148 lemma oexI [intro]:
   149     "[| P(x);  x<A |] ==> EX x<A. P(x)"
   150 apply (simp add: oex_def, blast)
   151 done
   152 
   153 (*Not of the general form for such rules; ~EX has become ALL~ *)
   154 lemma oexCI:
   155    "[| ALL x<A. ~P(x) ==> P(a);  a<A |] ==> EX x<A. P(x)"
   156 apply (simp add: oex_def, blast)
   157 done
   158 
   159 lemma oexE [elim!]:
   160     "[| EX x<A. P(x);  !!x. [| x<A; P(x) |] ==> Q |] ==> Q"
   161 apply (simp add: oex_def, blast)
   162 done
   163 
   164 lemma oex_cong [cong]:
   165     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
   166      ==> oex(a, %x. P(x)) <-> oex(a', %x. P'(x))"
   167 apply (simp add: oex_def cong add: conj_cong)
   168 done
   169 
   170 
   171 subsubsection {*Rules for Ordinal-Indexed Unions*}
   172 
   173 lemma OUN_I [intro]: "[| a<i;  b: B(a) |] ==> b: (\<Union>z<i. B(z))"
   174 by (unfold OUnion_def lt_def, blast)
   175 
   176 lemma OUN_E [elim!]:
   177     "[| b : (\<Union>z<i. B(z));  !!a.[| b: B(a);  a<i |] ==> R |] ==> R"
   178 apply (unfold OUnion_def lt_def, blast)
   179 done
   180 
   181 lemma OUN_iff: "b : (\<Union>x<i. B(x)) <-> (EX x<i. b : B(x))"
   182 by (unfold OUnion_def oex_def lt_def, blast)
   183 
   184 lemma OUN_cong [cong]:
   185     "[| i=j;  !!x. x<j ==> C(x)=D(x) |] ==> (\<Union>x<i. C(x)) = (\<Union>x<j. D(x))"
   186 by (simp add: OUnion_def lt_def OUN_iff)
   187 
   188 lemma lt_induct:
   189     "[| i<k;  !!x.[| x<k;  ALL y<x. P(y) |] ==> P(x) |]  ==>  P(i)"
   190 apply (simp add: lt_def oall_def)
   191 apply (erule conjE)
   192 apply (erule Ord_induct, assumption, blast)
   193 done
   194 
   195 
   196 subsection {*Quantification over a class*}
   197 
   198 definition
   199   "rall"     :: "[i=>o, i=>o] => o"  where
   200     "rall(M, P) == ALL x. M(x) --> P(x)"
   201 
   202 definition
   203   "rex"      :: "[i=>o, i=>o] => o"  where
   204     "rex(M, P) == EX x. M(x) & P(x)"
   205 
   206 syntax
   207   "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3ALL _[_]./ _)" 10)
   208   "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3EX _[_]./ _)" 10)
   209 
   210 syntax (xsymbols)
   211   "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3\<forall>_[_]./ _)" 10)
   212   "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3\<exists>_[_]./ _)" 10)
   213 syntax (HTML output)
   214   "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3\<forall>_[_]./ _)" 10)
   215   "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3\<exists>_[_]./ _)" 10)
   216 
   217 translations
   218   "ALL x[M]. P"  == "CONST rall(M, %x. P)"
   219   "EX x[M]. P"   == "CONST rex(M, %x. P)"
   220 
   221 
   222 subsubsection{*Relativized universal quantifier*}
   223 
   224 lemma rallI [intro!]: "[| !!x. M(x) ==> P(x) |] ==> ALL x[M]. P(x)"
   225 by (simp add: rall_def)
   226 
   227 lemma rspec: "[| ALL x[M]. P(x); M(x) |] ==> P(x)"
   228 by (simp add: rall_def)
   229 
   230 (*Instantiates x first: better for automatic theorem proving?*)
   231 lemma rev_rallE [elim]:
   232     "[| ALL x[M]. P(x);  ~ M(x) ==> Q;  P(x) ==> Q |] ==> Q"
   233 by (simp add: rall_def, blast)
   234 
   235 lemma rallE: "[| ALL x[M]. P(x);  P(x) ==> Q;  ~ M(x) ==> Q |] ==> Q"
   236 by blast
   237 
   238 (*Trival rewrite rule;   (ALL x[M].P)<->P holds only if A is nonempty!*)
   239 lemma rall_triv [simp]: "(ALL x[M]. P) <-> ((EX x. M(x)) --> P)"
   240 by (simp add: rall_def)
   241 
   242 (*Congruence rule for rewriting*)
   243 lemma rall_cong [cong]:
   244     "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (ALL x[M]. P(x)) <-> (ALL x[M]. P'(x))"
   245 by (simp add: rall_def)
   246 
   247 
   248 subsubsection{*Relativized existential quantifier*}
   249 
   250 lemma rexI [intro]: "[| P(x); M(x) |] ==> EX x[M]. P(x)"
   251 by (simp add: rex_def, blast)
   252 
   253 (*The best argument order when there is only one M(x)*)
   254 lemma rev_rexI: "[| M(x);  P(x) |] ==> EX x[M]. P(x)"
   255 by blast
   256 
   257 (*Not of the general form for such rules; ~EX has become ALL~ *)
   258 lemma rexCI: "[| ALL x[M]. ~P(x) ==> P(a); M(a) |] ==> EX x[M]. P(x)"
   259 by blast
   260 
   261 lemma rexE [elim!]: "[| EX x[M]. P(x);  !!x. [| M(x); P(x) |] ==> Q |] ==> Q"
   262 by (simp add: rex_def, blast)
   263 
   264 (*We do not even have (EX x[M]. True) <-> True unless A is nonempty!!*)
   265 lemma rex_triv [simp]: "(EX x[M]. P) <-> ((EX x. M(x)) & P)"
   266 by (simp add: rex_def)
   267 
   268 lemma rex_cong [cong]:
   269     "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (EX x[M]. P(x)) <-> (EX x[M]. P'(x))"
   270 by (simp add: rex_def cong: conj_cong)
   271 
   272 lemma rall_is_ball [simp]: "(\<forall>x[%z. z\<in>A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
   273 by blast
   274 
   275 lemma rex_is_bex [simp]: "(\<exists>x[%z. z\<in>A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
   276 by blast
   277 
   278 lemma atomize_rall: "(!!x. M(x) ==> P(x)) == Trueprop (ALL x[M]. P(x))";
   279 by (simp add: rall_def atomize_all atomize_imp)
   280 
   281 declare atomize_rall [symmetric, rulify]
   282 
   283 lemma rall_simps1:
   284      "(ALL x[M]. P(x) & Q)   <-> (ALL x[M]. P(x)) & ((ALL x[M]. False) | Q)"
   285      "(ALL x[M]. P(x) | Q)   <-> ((ALL x[M]. P(x)) | Q)"
   286      "(ALL x[M]. P(x) --> Q) <-> ((EX x[M]. P(x)) --> Q)"
   287      "(~(ALL x[M]. P(x))) <-> (EX x[M]. ~P(x))"
   288 by blast+
   289 
   290 lemma rall_simps2:
   291      "(ALL x[M]. P & Q(x))   <-> ((ALL x[M]. False) | P) & (ALL x[M]. Q(x))"
   292      "(ALL x[M]. P | Q(x))   <-> (P | (ALL x[M]. Q(x)))"
   293      "(ALL x[M]. P --> Q(x)) <-> (P --> (ALL x[M]. Q(x)))"
   294 by blast+
   295 
   296 lemmas rall_simps [simp] = rall_simps1 rall_simps2
   297 
   298 lemma rall_conj_distrib:
   299     "(ALL x[M]. P(x) & Q(x)) <-> ((ALL x[M]. P(x)) & (ALL x[M]. Q(x)))"
   300 by blast
   301 
   302 lemma rex_simps1:
   303      "(EX x[M]. P(x) & Q) <-> ((EX x[M]. P(x)) & Q)"
   304      "(EX x[M]. P(x) | Q) <-> (EX x[M]. P(x)) | ((EX x[M]. True) & Q)"
   305      "(EX x[M]. P(x) --> Q) <-> ((ALL x[M]. P(x)) --> ((EX x[M]. True) & Q))"
   306      "(~(EX x[M]. P(x))) <-> (ALL x[M]. ~P(x))"
   307 by blast+
   308 
   309 lemma rex_simps2:
   310      "(EX x[M]. P & Q(x)) <-> (P & (EX x[M]. Q(x)))"
   311      "(EX x[M]. P | Q(x)) <-> ((EX x[M]. True) & P) | (EX x[M]. Q(x))"
   312      "(EX x[M]. P --> Q(x)) <-> (((ALL x[M]. False) | P) --> (EX x[M]. Q(x)))"
   313 by blast+
   314 
   315 lemmas rex_simps [simp] = rex_simps1 rex_simps2
   316 
   317 lemma rex_disj_distrib:
   318     "(EX x[M]. P(x) | Q(x)) <-> ((EX x[M]. P(x)) | (EX x[M]. Q(x)))"
   319 by blast
   320 
   321 
   322 subsubsection{*One-point rule for bounded quantifiers*}
   323 
   324 lemma rex_triv_one_point1 [simp]: "(EX x[M]. x=a) <-> ( M(a))"
   325 by blast
   326 
   327 lemma rex_triv_one_point2 [simp]: "(EX x[M]. a=x) <-> ( M(a))"
   328 by blast
   329 
   330 lemma rex_one_point1 [simp]: "(EX x[M]. x=a & P(x)) <-> ( M(a) & P(a))"
   331 by blast
   332 
   333 lemma rex_one_point2 [simp]: "(EX x[M]. a=x & P(x)) <-> ( M(a) & P(a))"
   334 by blast
   335 
   336 lemma rall_one_point1 [simp]: "(ALL x[M]. x=a --> P(x)) <-> ( M(a) --> P(a))"
   337 by blast
   338 
   339 lemma rall_one_point2 [simp]: "(ALL x[M]. a=x --> P(x)) <-> ( M(a) --> P(a))"
   340 by blast
   341 
   342 
   343 subsubsection{*Sets as Classes*}
   344 
   345 definition
   346   setclass :: "[i,i] => o"       ("##_" [40] 40)  where
   347    "setclass(A) == %x. x : A"
   348 
   349 lemma setclass_iff [simp]: "setclass(A,x) <-> x : A"
   350 by (simp add: setclass_def)
   351 
   352 lemma rall_setclass_is_ball [simp]: "(\<forall>x[##A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
   353 by auto
   354 
   355 lemma rex_setclass_is_bex [simp]: "(\<exists>x[##A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
   356 by auto
   357 
   358 
   359 ML
   360 {*
   361 val Ord_atomize =
   362     atomize ([("OrdQuant.oall", [@{thm ospec}]),("OrdQuant.rall", [@{thm rspec}])]@
   363                  ZF_conn_pairs,
   364              ZF_mem_pairs);
   365 *}
   366 declaration {* fn _ =>
   367   Simplifier.map_ss (fn ss => ss setmksimps (map mk_eq o Ord_atomize o gen_all))
   368 *}
   369 
   370 text {* Setting up the one-point-rule simproc *}
   371 
   372 ML {*
   373 local
   374 
   375 val unfold_rex_tac = unfold_tac [@{thm rex_def}];
   376 fun prove_rex_tac ss = unfold_rex_tac ss THEN Quantifier1.prove_one_point_ex_tac;
   377 val rearrange_bex = Quantifier1.rearrange_bex prove_rex_tac;
   378 
   379 val unfold_rall_tac = unfold_tac [@{thm rall_def}];
   380 fun prove_rall_tac ss = unfold_rall_tac ss THEN Quantifier1.prove_one_point_all_tac;
   381 val rearrange_ball = Quantifier1.rearrange_ball prove_rall_tac;
   382 
   383 in
   384 
   385 val defREX_regroup = Simplifier.simproc (the_context ())
   386   "defined REX" ["EX x[M]. P(x) & Q(x)"] rearrange_bex;
   387 val defRALL_regroup = Simplifier.simproc (the_context ())
   388   "defined RALL" ["ALL x[M]. P(x) --> Q(x)"] rearrange_ball;
   389 
   390 end;
   391 
   392 Addsimprocs [defRALL_regroup,defREX_regroup];
   393 *}
   394 
   395 end