src/ZF/OrdQuant.thy
author wenzelm
Tue Sep 01 22:32:58 2015 +0200 (2015-09-01)
changeset 61076 bdc1e2f0a86a
parent 60822 4f58f3662e7d
child 61378 3e04c9ca001a
permissions -rw-r--r--
eliminated \<Colon>;
     1 (*  Title:      ZF/OrdQuant.thy
     2     Authors:    Krzysztof Grabczewski and L C Paulson
     3 *)
     4 
     5 section \<open>Special quantifiers\<close>
     6 
     7 theory OrdQuant imports Ordinal begin
     8 
     9 subsection \<open>Quantifiers and union operator for ordinals\<close>
    10 
    11 definition
    12   (* Ordinal Quantifiers *)
    13   oall :: "[i, i => o] => o"  where
    14     "oall(A, P) == \<forall>x. x<A \<longrightarrow> P(x)"
    15 
    16 definition
    17   oex :: "[i, i => o] => o"  where
    18     "oex(A, P)  == \<exists>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 \<open>simplification of the new quantifiers\<close>
    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]: "(\<forall>x<0. P(x))"
    52 by (simp add: oall_def)
    53 
    54 lemma [simp]: "~(\<exists>x<0. P(x))"
    55 by (simp add: oex_def)
    56 
    57 lemma [simp]: "(\<forall>x<succ(i). P(x)) <-> (Ord(i) \<longrightarrow> P(i) & (\<forall>x<i. P(x)))"
    58 apply (simp add: oall_def le_iff)
    59 apply (blast intro: lt_Ord2)
    60 done
    61 
    62 lemma [simp]: "(\<exists>x<succ(i). P(x)) <-> (Ord(i) & (P(i) | (\<exists>x<i. P(x))))"
    63 apply (simp add: oex_def le_iff)
    64 apply (blast intro: lt_Ord2)
    65 done
    66 
    67 subsubsection \<open>Union over ordinals\<close>
    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 of this theorem: consider that @{term"(\<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 lemma OUN_least_le:
    93      "[| Ord(i);  !!x. x<A ==> b(x) \<le> i |] ==> (\<Union>x<A. b(x)) \<le> i"
    94 by (simp add: OUnion_def UN_least_le ltI Ord_0_le)
    95 
    96 lemma le_implies_OUN_le_OUN:
    97      "[| !!x. x<A ==> c(x) \<le> d(x) |] ==> (\<Union>x<A. c(x)) \<le> (\<Union>x<A. d(x))"
    98 by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)
    99 
   100 lemma OUN_UN_eq:
   101      "(!!x. x \<in> A ==> Ord(B(x)))
   102       ==> (\<Union>z < (\<Union>x\<in>A. B(x)). C(z)) = (\<Union>x\<in>A. \<Union>z < B(x). C(z))"
   103 by (simp add: OUnion_def)
   104 
   105 lemma OUN_Union_eq:
   106      "(!!x. x \<in> X ==> Ord(x))
   107       ==> (\<Union>z < \<Union>(X). C(z)) = (\<Union>x\<in>X. \<Union>z < x. C(z))"
   108 by (simp add: OUnion_def)
   109 
   110 (*So that rule_format will get rid of this quantifier...*)
   111 lemma atomize_oall [symmetric, rulify]:
   112      "(!!x. x<A ==> P(x)) == Trueprop (\<forall>x<A. P(x))"
   113 by (simp add: oall_def atomize_all atomize_imp)
   114 
   115 subsubsection \<open>universal quantifier for ordinals\<close>
   116 
   117 lemma oallI [intro!]:
   118     "[| !!x. x<A ==> P(x) |] ==> \<forall>x<A. P(x)"
   119 by (simp add: oall_def)
   120 
   121 lemma ospec: "[| \<forall>x<A. P(x);  x<A |] ==> P(x)"
   122 by (simp add: oall_def)
   123 
   124 lemma oallE:
   125     "[| \<forall>x<A. P(x);  P(x) ==> Q;  ~x<A ==> Q |] ==> Q"
   126 by (simp add: oall_def, blast)
   127 
   128 lemma rev_oallE [elim]:
   129     "[| \<forall>x<A. P(x);  ~x<A ==> Q;  P(x) ==> Q |] ==> Q"
   130 by (simp add: oall_def, blast)
   131 
   132 
   133 (*Trival rewrite rule.  @{term"(\<forall>x<a.P)<->P"} holds only if a is not 0!*)
   134 lemma oall_simp [simp]: "(\<forall>x<a. True) <-> True"
   135 by blast
   136 
   137 (*Congruence rule for rewriting*)
   138 lemma oall_cong [cong]:
   139     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
   140      ==> oall(a, %x. P(x)) <-> oall(a', %x. P'(x))"
   141 by (simp add: oall_def)
   142 
   143 
   144 subsubsection \<open>existential quantifier for ordinals\<close>
   145 
   146 lemma oexI [intro]:
   147     "[| P(x);  x<A |] ==> \<exists>x<A. P(x)"
   148 apply (simp add: oex_def, blast)
   149 done
   150 
   151 (*Not of the general form for such rules... *)
   152 lemma oexCI:
   153    "[| \<forall>x<A. ~P(x) ==> P(a);  a<A |] ==> \<exists>x<A. P(x)"
   154 apply (simp add: oex_def, blast)
   155 done
   156 
   157 lemma oexE [elim!]:
   158     "[| \<exists>x<A. P(x);  !!x. [| x<A; P(x) |] ==> Q |] ==> Q"
   159 apply (simp add: oex_def, blast)
   160 done
   161 
   162 lemma oex_cong [cong]:
   163     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
   164      ==> oex(a, %x. P(x)) <-> oex(a', %x. P'(x))"
   165 apply (simp add: oex_def cong add: conj_cong)
   166 done
   167 
   168 
   169 subsubsection \<open>Rules for Ordinal-Indexed Unions\<close>
   170 
   171 lemma OUN_I [intro]: "[| a<i;  b \<in> B(a) |] ==> b: (\<Union>z<i. B(z))"
   172 by (unfold OUnion_def lt_def, blast)
   173 
   174 lemma OUN_E [elim!]:
   175     "[| b \<in> (\<Union>z<i. B(z));  !!a.[| b \<in> B(a);  a<i |] ==> R |] ==> R"
   176 apply (unfold OUnion_def lt_def, blast)
   177 done
   178 
   179 lemma OUN_iff: "b \<in> (\<Union>x<i. B(x)) <-> (\<exists>x<i. b \<in> B(x))"
   180 by (unfold OUnion_def oex_def lt_def, blast)
   181 
   182 lemma OUN_cong [cong]:
   183     "[| i=j;  !!x. x<j ==> C(x)=D(x) |] ==> (\<Union>x<i. C(x)) = (\<Union>x<j. D(x))"
   184 by (simp add: OUnion_def lt_def OUN_iff)
   185 
   186 lemma lt_induct:
   187     "[| i<k;  !!x.[| x<k;  \<forall>y<x. P(y) |] ==> P(x) |]  ==>  P(i)"
   188 apply (simp add: lt_def oall_def)
   189 apply (erule conjE)
   190 apply (erule Ord_induct, assumption, blast)
   191 done
   192 
   193 
   194 subsection \<open>Quantification over a class\<close>
   195 
   196 definition
   197   "rall"     :: "[i=>o, i=>o] => o"  where
   198     "rall(M, P) == \<forall>x. M(x) \<longrightarrow> P(x)"
   199 
   200 definition
   201   "rex"      :: "[i=>o, i=>o] => o"  where
   202     "rex(M, P) == \<exists>x. M(x) & P(x)"
   203 
   204 syntax
   205   "_rall"     :: "[pttrn, i=>o, o] => o"        ("(3ALL _[_]./ _)" 10)
   206   "_rex"      :: "[pttrn, i=>o, o] => o"        ("(3EX _[_]./ _)" 10)
   207 
   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)
   214 
   215 translations
   216   "ALL x[M]. P"  == "CONST rall(M, %x. P)"
   217   "EX x[M]. P"   == "CONST rex(M, %x. P)"
   218 
   219 
   220 subsubsection\<open>Relativized universal quantifier\<close>
   221 
   222 lemma rallI [intro!]: "[| !!x. M(x) ==> P(x) |] ==> \<forall>x[M]. P(x)"
   223 by (simp add: rall_def)
   224 
   225 lemma rspec: "[| \<forall>x[M]. P(x); M(x) |] ==> P(x)"
   226 by (simp add: rall_def)
   227 
   228 (*Instantiates x first: better for automatic theorem proving?*)
   229 lemma rev_rallE [elim]:
   230     "[| \<forall>x[M]. P(x);  ~ M(x) ==> Q;  P(x) ==> Q |] ==> Q"
   231 by (simp add: rall_def, blast)
   232 
   233 lemma rallE: "[| \<forall>x[M]. P(x);  P(x) ==> Q;  ~ M(x) ==> Q |] ==> Q"
   234 by blast
   235 
   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)"
   238 by (simp add: rall_def)
   239 
   240 (*Congruence rule for rewriting*)
   241 lemma rall_cong [cong]:
   242     "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (\<forall>x[M]. P(x)) <-> (\<forall>x[M]. P'(x))"
   243 by (simp add: rall_def)
   244 
   245 
   246 subsubsection\<open>Relativized existential quantifier\<close>
   247 
   248 lemma rexI [intro]: "[| P(x); M(x) |] ==> \<exists>x[M]. P(x)"
   249 by (simp add: rex_def, blast)
   250 
   251 (*The best argument order when there is only one M(x)*)
   252 lemma rev_rexI: "[| M(x);  P(x) |] ==> \<exists>x[M]. P(x)"
   253 by blast
   254 
   255 (*Not of the general form for such rules... *)
   256 lemma rexCI: "[| \<forall>x[M]. ~P(x) ==> P(a); M(a) |] ==> \<exists>x[M]. P(x)"
   257 by blast
   258 
   259 lemma rexE [elim!]: "[| \<exists>x[M]. P(x);  !!x. [| M(x); P(x) |] ==> Q |] ==> Q"
   260 by (simp add: rex_def, blast)
   261 
   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)"
   264 by (simp add: rex_def)
   265 
   266 lemma rex_cong [cong]:
   267     "(!!x. M(x) ==> P(x) <-> P'(x)) ==> (\<exists>x[M]. P(x)) <-> (\<exists>x[M]. P'(x))"
   268 by (simp add: rex_def cong: conj_cong)
   269 
   270 lemma rall_is_ball [simp]: "(\<forall>x[%z. z\<in>A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
   271 by blast
   272 
   273 lemma rex_is_bex [simp]: "(\<exists>x[%z. z\<in>A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
   274 by blast
   275 
   276 lemma atomize_rall: "(!!x. M(x) ==> P(x)) == Trueprop (\<forall>x[M]. P(x))"
   277 by (simp add: rall_def atomize_all atomize_imp)
   278 
   279 declare atomize_rall [symmetric, rulify]
   280 
   281 lemma rall_simps1:
   282      "(\<forall>x[M]. P(x) & Q)   <-> (\<forall>x[M]. P(x)) & ((\<forall>x[M]. False) | Q)"
   283      "(\<forall>x[M]. P(x) | Q)   <-> ((\<forall>x[M]. P(x)) | Q)"
   284      "(\<forall>x[M]. P(x) \<longrightarrow> Q) <-> ((\<exists>x[M]. P(x)) \<longrightarrow> Q)"
   285      "(~(\<forall>x[M]. P(x))) <-> (\<exists>x[M]. ~P(x))"
   286 by blast+
   287 
   288 lemma rall_simps2:
   289      "(\<forall>x[M]. P & Q(x))   <-> ((\<forall>x[M]. False) | P) & (\<forall>x[M]. Q(x))"
   290      "(\<forall>x[M]. P | Q(x))   <-> (P | (\<forall>x[M]. Q(x)))"
   291      "(\<forall>x[M]. P \<longrightarrow> Q(x)) <-> (P \<longrightarrow> (\<forall>x[M]. Q(x)))"
   292 by blast+
   293 
   294 lemmas rall_simps [simp] = rall_simps1 rall_simps2
   295 
   296 lemma rall_conj_distrib:
   297     "(\<forall>x[M]. P(x) & Q(x)) <-> ((\<forall>x[M]. P(x)) & (\<forall>x[M]. Q(x)))"
   298 by blast
   299 
   300 lemma rex_simps1:
   301      "(\<exists>x[M]. P(x) & Q) <-> ((\<exists>x[M]. P(x)) & Q)"
   302      "(\<exists>x[M]. P(x) | Q) <-> (\<exists>x[M]. P(x)) | ((\<exists>x[M]. True) & Q)"
   303      "(\<exists>x[M]. P(x) \<longrightarrow> Q) <-> ((\<forall>x[M]. P(x)) \<longrightarrow> ((\<exists>x[M]. True) & Q))"
   304      "(~(\<exists>x[M]. P(x))) <-> (\<forall>x[M]. ~P(x))"
   305 by blast+
   306 
   307 lemma rex_simps2:
   308      "(\<exists>x[M]. P & Q(x)) <-> (P & (\<exists>x[M]. Q(x)))"
   309      "(\<exists>x[M]. P | Q(x)) <-> ((\<exists>x[M]. True) & P) | (\<exists>x[M]. Q(x))"
   310      "(\<exists>x[M]. P \<longrightarrow> Q(x)) <-> (((\<forall>x[M]. False) | P) \<longrightarrow> (\<exists>x[M]. Q(x)))"
   311 by blast+
   312 
   313 lemmas rex_simps [simp] = rex_simps1 rex_simps2
   314 
   315 lemma rex_disj_distrib:
   316     "(\<exists>x[M]. P(x) | Q(x)) <-> ((\<exists>x[M]. P(x)) | (\<exists>x[M]. Q(x)))"
   317 by blast
   318 
   319 
   320 subsubsection\<open>One-point rule for bounded quantifiers\<close>
   321 
   322 lemma rex_triv_one_point1 [simp]: "(\<exists>x[M]. x=a) <-> ( M(a))"
   323 by blast
   324 
   325 lemma rex_triv_one_point2 [simp]: "(\<exists>x[M]. a=x) <-> ( M(a))"
   326 by blast
   327 
   328 lemma rex_one_point1 [simp]: "(\<exists>x[M]. x=a & P(x)) <-> ( M(a) & P(a))"
   329 by blast
   330 
   331 lemma rex_one_point2 [simp]: "(\<exists>x[M]. a=x & P(x)) <-> ( M(a) & P(a))"
   332 by blast
   333 
   334 lemma rall_one_point1 [simp]: "(\<forall>x[M]. x=a \<longrightarrow> P(x)) <-> ( M(a) \<longrightarrow> P(a))"
   335 by blast
   336 
   337 lemma rall_one_point2 [simp]: "(\<forall>x[M]. a=x \<longrightarrow> P(x)) <-> ( M(a) \<longrightarrow> P(a))"
   338 by blast
   339 
   340 
   341 subsubsection\<open>Sets as Classes\<close>
   342 
   343 definition
   344   setclass :: "[i,i] => o"       ("##_" [40] 40)  where
   345    "setclass(A) == %x. x \<in> A"
   346 
   347 lemma setclass_iff [simp]: "setclass(A,x) <-> x \<in> A"
   348 by (simp add: setclass_def)
   349 
   350 lemma rall_setclass_is_ball [simp]: "(\<forall>x[##A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
   351 by auto
   352 
   353 lemma rex_setclass_is_bex [simp]: "(\<exists>x[##A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
   354 by auto
   355 
   356 
   357 ML
   358 \<open>
   359 val Ord_atomize =
   360   atomize ([(@{const_name oall}, @{thms ospec}), (@{const_name rall}, @{thms rspec})] @
   361     ZF_conn_pairs, ZF_mem_pairs);
   362 \<close>
   363 declaration \<open>fn _ =>
   364   Simplifier.map_ss (Simplifier.set_mksimps (fn ctxt =>
   365     map mk_eq o Ord_atomize o Variable.gen_all ctxt))
   366 \<close>
   367 
   368 text \<open>Setting up the one-point-rule simproc\<close>
   369 
   370 simproc_setup defined_rex ("\<exists>x[M]. P(x) & Q(x)") = \<open>
   371   fn _ => Quantifier1.rearrange_bex
   372     (fn ctxt =>
   373       unfold_tac ctxt @{thms rex_def} THEN
   374       Quantifier1.prove_one_point_ex_tac ctxt)
   375 \<close>
   376 
   377 simproc_setup defined_rall ("\<forall>x[M]. P(x) \<longrightarrow> Q(x)") = \<open>
   378   fn _ => Quantifier1.rearrange_ball
   379     (fn ctxt =>
   380       unfold_tac ctxt @{thms rall_def} THEN
   381       Quantifier1.prove_one_point_all_tac ctxt)
   382 \<close>
   383 
   384 end