src/ZF/OrdQuant.thy
author wenzelm
Fri Feb 18 16:22:27 2011 +0100 (2011-02-18)
changeset 41777 1f7cbe39d425
parent 38715 6513ea67d95d
child 42455 6702c984bf5a
permissions -rw-r--r--
more precise headers;
     1 (*  Title:      ZF/OrdQuant.thy
     2     Authors:    Krzysztof Grabczewski and L C Paulson
     3 *)
     4 
     5 header {*Special quantifiers*}
     6 
     7 theory OrdQuant imports Ordinal begin
     8 
     9 subsection {*Quantifiers and union operator for ordinals*}
    10 
    11 definition
    12   (* Ordinal Quantifiers *)
    13   oall :: "[i, i => o] => o"  where
    14     "oall(A, P) == ALL x. x<A --> P(x)"
    15 
    16 definition
    17   oex :: "[i, i => o] => o"  where
    18     "oex(A, P)  == EX x. x<A & P(x)"
    19 
    20 definition
    21   (* Ordinal Union *)
    22   OUnion :: "[i, i => i] => i"  where
    23     "OUnion(i,B) == {z: \<Union>x\<in>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"  == "CONST oall(a, %x. P)"
    32   "EX x<a. P"   == "CONST oex(a, %x. P)"
    33   "UN x<a. B"   == "CONST 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 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)
    43 
    44 
    45 subsubsection {*simplification of the new quantifiers*}
    46 
    47 
    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))"
    52 by (simp add: oall_def)
    53 
    54 lemma [simp]: "~(EX x<0. P(x))"
    55 by (simp add: oex_def)
    56 
    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
    61 
    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
    66 
    67 subsubsection {*Union over ordinals*}
    68 
    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)
    72 
    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 )
    76 
    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
    83 
    84 lemma Limit_OUN_eq: "Limit(i) ==> (\<Union>x<i. x) = i"
    85 by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)
    86 
    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)
    91 
    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)
    96 
    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)
   100 
   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))"
   104 by (simp add: OUnion_def)
   105 
   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))"
   109 by (simp add: OUnion_def)
   110 
   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)
   115 
   116 subsubsection {*universal quantifier for ordinals*}
   117 
   118 lemma oallI [intro!]:
   119     "[| !!x. x<A ==> P(x) |] ==> ALL x<A. P(x)"
   120 by (simp add: oall_def)
   121 
   122 lemma ospec: "[| ALL x<A. P(x);  x<A |] ==> P(x)"
   123 by (simp add: oall_def)
   124 
   125 lemma oallE:
   126     "[| ALL x<A. P(x);  P(x) ==> Q;  ~x<A ==> Q |] ==> Q"
   127 by (simp add: oall_def, blast)
   128 
   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)
   132 
   133 
   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
   137 
   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))"
   142 by (simp add: oall_def)
   143 
   144 
   145 subsubsection {*existential quantifier for ordinals*}
   146 
   147 lemma oexI [intro]:
   148     "[| P(x);  x<A |] ==> EX x<A. P(x)"
   149 apply (simp add: oex_def, blast)
   150 done
   151 
   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
   157 
   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
   162 
   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))"
   166 apply (simp add: oex_def cong add: conj_cong)
   167 done
   168 
   169 
   170 subsubsection {*Rules for Ordinal-Indexed Unions*}
   171 
   172 lemma OUN_I [intro]: "[| a<i;  b: B(a) |] ==> b: (\<Union>z<i. B(z))"
   173 by (unfold OUnion_def lt_def, blast)
   174 
   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
   179 
   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)
   182 
   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)
   186 
   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
   193 
   194 
   195 subsection {*Quantification over a class*}
   196 
   197 definition
   198   "rall"     :: "[i=>o, i=>o] => o"  where
   199     "rall(M, P) == ALL x. M(x) --> P(x)"
   200 
   201 definition
   202   "rex"      :: "[i=>o, i=>o] => o"  where
   203     "rex(M, P) == EX x. M(x) & P(x)"
   204 
   205 syntax
   206   "_rall"     :: "[pttrn, i=>o, o] => o"        ("(3ALL _[_]./ _)" 10)
   207   "_rex"      :: "[pttrn, i=>o, o] => o"        ("(3EX _[_]./ _)" 10)
   208 
   209 syntax (xsymbols)
   210   "_rall"     :: "[pttrn, i=>o, o] => o"        ("(3\<forall>_[_]./ _)" 10)
   211   "_rex"      :: "[pttrn, i=>o, o] => o"        ("(3\<exists>_[_]./ _)" 10)
   212 syntax (HTML output)
   213   "_rall"     :: "[pttrn, i=>o, o] => o"        ("(3\<forall>_[_]./ _)" 10)
   214   "_rex"      :: "[pttrn, i=>o, o] => o"        ("(3\<exists>_[_]./ _)" 10)
   215 
   216 translations
   217   "ALL x[M]. P"  == "CONST rall(M, %x. P)"
   218   "EX x[M]. P"   == "CONST rex(M, %x. P)"
   219 
   220 
   221 subsubsection{*Relativized universal quantifier*}
   222 
   223 lemma rallI [intro!]: "[| !!x. M(x) ==> P(x) |] ==> ALL x[M]. P(x)"
   224 by (simp add: rall_def)
   225 
   226 lemma rspec: "[| ALL x[M]. P(x); M(x) |] ==> P(x)"
   227 by (simp add: rall_def)
   228 
   229 (*Instantiates x first: better for automatic theorem proving?*)
   230 lemma rev_rallE [elim]:
   231     "[| ALL x[M]. P(x);  ~ M(x) ==> Q;  P(x) ==> Q |] ==> Q"
   232 by (simp add: rall_def, blast)
   233 
   234 lemma rallE: "[| ALL x[M]. P(x);  P(x) ==> Q;  ~ M(x) ==> Q |] ==> Q"
   235 by blast
   236 
   237 (*Trival rewrite rule;   (ALL x[M].P)<->P holds only if A is nonempty!*)
   238 lemma rall_triv [simp]: "(ALL x[M]. P) <-> ((EX x. M(x)) --> P)"
   239 by (simp add: rall_def)
   240 
   241 (*Congruence rule for rewriting*)
   242 lemma rall_cong [cong]:
   243     "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (ALL x[M]. P(x)) <-> (ALL x[M]. P'(x))"
   244 by (simp add: rall_def)
   245 
   246 
   247 subsubsection{*Relativized existential quantifier*}
   248 
   249 lemma rexI [intro]: "[| P(x); M(x) |] ==> EX x[M]. P(x)"
   250 by (simp add: rex_def, blast)
   251 
   252 (*The best argument order when there is only one M(x)*)
   253 lemma rev_rexI: "[| M(x);  P(x) |] ==> EX x[M]. P(x)"
   254 by blast
   255 
   256 (*Not of the general form for such rules; ~EX has become ALL~ *)
   257 lemma rexCI: "[| ALL x[M]. ~P(x) ==> P(a); M(a) |] ==> EX x[M]. P(x)"
   258 by blast
   259 
   260 lemma rexE [elim!]: "[| EX x[M]. P(x);  !!x. [| M(x); P(x) |] ==> Q |] ==> Q"
   261 by (simp add: rex_def, blast)
   262 
   263 (*We do not even have (EX x[M]. True) <-> True unless A is nonempty!!*)
   264 lemma rex_triv [simp]: "(EX x[M]. P) <-> ((EX x. M(x)) & P)"
   265 by (simp add: rex_def)
   266 
   267 lemma rex_cong [cong]:
   268     "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (EX x[M]. P(x)) <-> (EX x[M]. P'(x))"
   269 by (simp add: rex_def cong: conj_cong)
   270 
   271 lemma rall_is_ball [simp]: "(\<forall>x[%z. z\<in>A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
   272 by blast
   273 
   274 lemma rex_is_bex [simp]: "(\<exists>x[%z. z\<in>A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
   275 by blast
   276 
   277 lemma atomize_rall: "(!!x. M(x) ==> P(x)) == Trueprop (ALL x[M]. P(x))";
   278 by (simp add: rall_def atomize_all atomize_imp)
   279 
   280 declare atomize_rall [symmetric, rulify]
   281 
   282 lemma rall_simps1:
   283      "(ALL x[M]. P(x) & Q)   <-> (ALL x[M]. P(x)) & ((ALL x[M]. False) | Q)"
   284      "(ALL x[M]. P(x) | Q)   <-> ((ALL x[M]. P(x)) | Q)"
   285      "(ALL x[M]. P(x) --> Q) <-> ((EX x[M]. P(x)) --> Q)"
   286      "(~(ALL x[M]. P(x))) <-> (EX x[M]. ~P(x))"
   287 by blast+
   288 
   289 lemma rall_simps2:
   290      "(ALL x[M]. P & Q(x))   <-> ((ALL x[M]. False) | P) & (ALL x[M]. Q(x))"
   291      "(ALL x[M]. P | Q(x))   <-> (P | (ALL x[M]. Q(x)))"
   292      "(ALL x[M]. P --> Q(x)) <-> (P --> (ALL x[M]. Q(x)))"
   293 by blast+
   294 
   295 lemmas rall_simps [simp] = rall_simps1 rall_simps2
   296 
   297 lemma rall_conj_distrib:
   298     "(ALL x[M]. P(x) & Q(x)) <-> ((ALL x[M]. P(x)) & (ALL x[M]. Q(x)))"
   299 by blast
   300 
   301 lemma rex_simps1:
   302      "(EX x[M]. P(x) & Q) <-> ((EX x[M]. P(x)) & Q)"
   303      "(EX x[M]. P(x) | Q) <-> (EX x[M]. P(x)) | ((EX x[M]. True) & Q)"
   304      "(EX x[M]. P(x) --> Q) <-> ((ALL x[M]. P(x)) --> ((EX x[M]. True) & Q))"
   305      "(~(EX x[M]. P(x))) <-> (ALL x[M]. ~P(x))"
   306 by blast+
   307 
   308 lemma rex_simps2:
   309      "(EX x[M]. P & Q(x)) <-> (P & (EX x[M]. Q(x)))"
   310      "(EX x[M]. P | Q(x)) <-> ((EX x[M]. True) & P) | (EX x[M]. Q(x))"
   311      "(EX x[M]. P --> Q(x)) <-> (((ALL x[M]. False) | P) --> (EX x[M]. Q(x)))"
   312 by blast+
   313 
   314 lemmas rex_simps [simp] = rex_simps1 rex_simps2
   315 
   316 lemma rex_disj_distrib:
   317     "(EX x[M]. P(x) | Q(x)) <-> ((EX x[M]. P(x)) | (EX x[M]. Q(x)))"
   318 by blast
   319 
   320 
   321 subsubsection{*One-point rule for bounded quantifiers*}
   322 
   323 lemma rex_triv_one_point1 [simp]: "(EX x[M]. x=a) <-> ( M(a))"
   324 by blast
   325 
   326 lemma rex_triv_one_point2 [simp]: "(EX x[M]. a=x) <-> ( M(a))"
   327 by blast
   328 
   329 lemma rex_one_point1 [simp]: "(EX x[M]. x=a & P(x)) <-> ( M(a) & P(a))"
   330 by blast
   331 
   332 lemma rex_one_point2 [simp]: "(EX x[M]. a=x & P(x)) <-> ( M(a) & P(a))"
   333 by blast
   334 
   335 lemma rall_one_point1 [simp]: "(ALL x[M]. x=a --> P(x)) <-> ( M(a) --> P(a))"
   336 by blast
   337 
   338 lemma rall_one_point2 [simp]: "(ALL x[M]. a=x --> P(x)) <-> ( M(a) --> P(a))"
   339 by blast
   340 
   341 
   342 subsubsection{*Sets as Classes*}
   343 
   344 definition
   345   setclass :: "[i,i] => o"       ("##_" [40] 40)  where
   346    "setclass(A) == %x. x : A"
   347 
   348 lemma setclass_iff [simp]: "setclass(A,x) <-> x : A"
   349 by (simp add: setclass_def)
   350 
   351 lemma rall_setclass_is_ball [simp]: "(\<forall>x[##A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
   352 by auto
   353 
   354 lemma rex_setclass_is_bex [simp]: "(\<exists>x[##A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
   355 by auto
   356 
   357 
   358 ML
   359 {*
   360 val Ord_atomize =
   361     atomize ([("OrdQuant.oall", [@{thm ospec}]),("OrdQuant.rall", [@{thm rspec}])]@
   362                  ZF_conn_pairs,
   363              ZF_mem_pairs);
   364 *}
   365 declaration {* fn _ =>
   366   Simplifier.map_ss (fn ss => ss setmksimps (K (map mk_eq o Ord_atomize o gen_all)))
   367 *}
   368 
   369 text {* Setting up the one-point-rule simproc *}
   370 
   371 ML {*
   372 local
   373 
   374 val unfold_rex_tac = unfold_tac [@{thm rex_def}];
   375 fun prove_rex_tac ss = unfold_rex_tac ss THEN Quantifier1.prove_one_point_ex_tac;
   376 val rearrange_bex = Quantifier1.rearrange_bex prove_rex_tac;
   377 
   378 val unfold_rall_tac = unfold_tac [@{thm rall_def}];
   379 fun prove_rall_tac ss = unfold_rall_tac ss THEN Quantifier1.prove_one_point_all_tac;
   380 val rearrange_ball = Quantifier1.rearrange_ball prove_rall_tac;
   381 
   382 in
   383 
   384 val defREX_regroup = Simplifier.simproc_global @{theory}
   385   "defined REX" ["EX x[M]. P(x) & Q(x)"] rearrange_bex;
   386 val defRALL_regroup = Simplifier.simproc_global @{theory}
   387   "defined RALL" ["ALL x[M]. P(x) --> Q(x)"] rearrange_ball;
   388 
   389 end;
   390 
   391 Addsimprocs [defRALL_regroup,defREX_regroup];
   392 *}
   393 
   394 end