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