src/ZF/OrdQuant.thy
 author paulson Thu Jul 04 16:59:54 2002 +0200 (2002-07-04) changeset 13298 b4f370679c65 parent 13289 53e201efdaa2 child 13302 98ce70e7d1f7 permissions -rw-r--r--
Constructible: some separation axioms
```     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 by (simp add: oall_def, blast)
```
```   124
```
```   125 lemma rev_oallE [elim]:
```
```   126     "[| ALL x<A. P(x);  ~x<A ==> Q;  P(x) ==> Q |] ==> Q"
```
```   127 by (simp add: oall_def, blast)
```
```   128
```
```   129
```
```   130 (*Trival rewrite rule;   (ALL x<a.P)<->P holds only if a is not 0!*)
```
```   131 lemma oall_simp [simp]: "(ALL x<a. True) <-> True"
```
```   132 by blast
```
```   133
```
```   134 (*Congruence rule for rewriting*)
```
```   135 lemma oall_cong [cong]:
```
```   136     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
```
```   137      ==> oall(a, %x. P(x)) <-> oall(a', %x. P'(x))"
```
```   138 by (simp add: oall_def)
```
```   139
```
```   140
```
```   141 (*** existential quantifier for ordinals ***)
```
```   142
```
```   143 lemma oexI [intro]:
```
```   144     "[| P(x);  x<A |] ==> EX x<A. P(x)"
```
```   145 apply (simp add: oex_def, blast)
```
```   146 done
```
```   147
```
```   148 (*Not of the general form for such rules; ~EX has become ALL~ *)
```
```   149 lemma oexCI:
```
```   150    "[| ALL x<A. ~P(x) ==> P(a);  a<A |] ==> EX x<A. P(x)"
```
```   151 apply (simp add: oex_def, blast)
```
```   152 done
```
```   153
```
```   154 lemma oexE [elim!]:
```
```   155     "[| EX x<A. P(x);  !!x. [| x<A; P(x) |] ==> Q |] ==> Q"
```
```   156 apply (simp add: oex_def, blast)
```
```   157 done
```
```   158
```
```   159 lemma oex_cong [cong]:
```
```   160     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |]
```
```   161      ==> oex(a, %x. P(x)) <-> oex(a', %x. P'(x))"
```
```   162 apply (simp add: oex_def cong add: conj_cong)
```
```   163 done
```
```   164
```
```   165
```
```   166 (*** Rules for Ordinal-Indexed Unions ***)
```
```   167
```
```   168 lemma OUN_I [intro]: "[| a<i;  b: B(a) |] ==> b: (UN z<i. B(z))"
```
```   169 by (unfold OUnion_def lt_def, blast)
```
```   170
```
```   171 lemma OUN_E [elim!]:
```
```   172     "[| b : (UN z<i. B(z));  !!a.[| b: B(a);  a<i |] ==> R |] ==> R"
```
```   173 apply (unfold OUnion_def lt_def, blast)
```
```   174 done
```
```   175
```
```   176 lemma OUN_iff: "b : (UN x<i. B(x)) <-> (EX x<i. b : B(x))"
```
```   177 by (unfold OUnion_def oex_def lt_def, blast)
```
```   178
```
```   179 lemma OUN_cong [cong]:
```
```   180     "[| i=j;  !!x. x<j ==> C(x)=D(x) |] ==> (UN x<i. C(x)) = (UN x<j. D(x))"
```
```   181 by (simp add: OUnion_def lt_def OUN_iff)
```
```   182
```
```   183 lemma lt_induct:
```
```   184     "[| i<k;  !!x.[| x<k;  ALL y<x. P(y) |] ==> P(x) |]  ==>  P(i)"
```
```   185 apply (simp add: lt_def oall_def)
```
```   186 apply (erule conjE)
```
```   187 apply (erule Ord_induct, assumption, blast)
```
```   188 done
```
```   189
```
```   190
```
```   191 subsection {*Quantification over a class*}
```
```   192
```
```   193 constdefs
```
```   194   "rall"     :: "[i=>o, i=>o] => o"
```
```   195     "rall(M, P) == ALL x. M(x) --> P(x)"
```
```   196
```
```   197   "rex"      :: "[i=>o, i=>o] => o"
```
```   198     "rex(M, P) == EX x. M(x) & P(x)"
```
```   199
```
```   200 syntax
```
```   201   "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3ALL _[_]./ _)" 10)
```
```   202   "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3EX _[_]./ _)" 10)
```
```   203
```
```   204 syntax (xsymbols)
```
```   205   "@rall"     :: "[pttrn, i=>o, o] => o"        ("(3\<forall>_[_]./ _)" 10)
```
```   206   "@rex"      :: "[pttrn, i=>o, o] => o"        ("(3\<exists>_[_]./ _)" 10)
```
```   207
```
```   208 translations
```
```   209   "ALL x[M]. P"  == "rall(M, %x. P)"
```
```   210   "EX x[M]. P"   == "rex(M, %x. P)"
```
```   211
```
```   212
```
```   213 subsubsection{*Relativized universal quantifier*}
```
```   214
```
```   215 lemma rallI [intro!]: "[| !!x. M(x) ==> P(x) |] ==> ALL x[M]. P(x)"
```
```   216 by (simp add: rall_def)
```
```   217
```
```   218 lemma rspec: "[| ALL x[M]. P(x); M(x) |] ==> P(x)"
```
```   219 by (simp add: rall_def)
```
```   220
```
```   221 (*Instantiates x first: better for automatic theorem proving?*)
```
```   222 lemma rev_rallE [elim]:
```
```   223     "[| ALL x[M]. P(x);  ~ M(x) ==> Q;  P(x) ==> Q |] ==> Q"
```
```   224 by (simp add: rall_def, blast)
```
```   225
```
```   226 lemma rallE: "[| ALL x[M]. P(x);  P(x) ==> Q;  ~ M(x) ==> Q |] ==> Q"
```
```   227 by blast
```
```   228
```
```   229 (*Trival rewrite rule;   (ALL x[M].P)<->P holds only if A is nonempty!*)
```
```   230 lemma rall_triv [simp]: "(ALL x[M]. P) <-> ((EX x. M(x)) --> P)"
```
```   231 by (simp add: rall_def)
```
```   232
```
```   233 (*Congruence rule for rewriting*)
```
```   234 lemma rall_cong [cong]:
```
```   235     "(!!x. M(x) ==> P(x) <-> P'(x))
```
```   236      ==> rall(M, %x. P(x)) <-> rall(M, %x. P'(x))"
```
```   237 by (simp add: rall_def)
```
```   238
```
```   239
```
```   240 subsubsection{*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 subsubsection{*One-point rule for bounded quantifiers*}
```
```   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 subsubsection{*Sets as Classes*}
```
```   337
```
```   338 constdefs setclass :: "[i,i] => o"       ("**_")
```
```   339    "setclass(A,x) == x : A"
```
```   340
```
```   341 declare setclass_def [simp]
```
```   342
```
```   343 lemma rall_setclass_is_ball [simp]: "(\<forall>x[**A]. P(x)) <-> (\<forall>x\<in>A. P(x))"
```
```   344 by auto
```
```   345
```
```   346 lemma rex_setclass_is_bex [simp]: "(\<exists>x[**A]. P(x)) <-> (\<exists>x\<in>A. P(x))"
```
```   347 by auto
```
```   348
```
```   349
```
```   350 ML
```
```   351 {*
```
```   352 val oall_def = thm "oall_def"
```
```   353 val oex_def = thm "oex_def"
```
```   354 val OUnion_def = thm "OUnion_def"
```
```   355
```
```   356 val oallI = thm "oallI";
```
```   357 val ospec = thm "ospec";
```
```   358 val oallE = thm "oallE";
```
```   359 val rev_oallE = thm "rev_oallE";
```
```   360 val oall_simp = thm "oall_simp";
```
```   361 val oall_cong = thm "oall_cong";
```
```   362 val oexI = thm "oexI";
```
```   363 val oexCI = thm "oexCI";
```
```   364 val oexE = thm "oexE";
```
```   365 val oex_cong = thm "oex_cong";
```
```   366 val OUN_I = thm "OUN_I";
```
```   367 val OUN_E = thm "OUN_E";
```
```   368 val OUN_iff = thm "OUN_iff";
```
```   369 val OUN_cong = thm "OUN_cong";
```
```   370 val lt_induct = thm "lt_induct";
```
```   371
```
```   372 val rall_def = thm "rall_def"
```
```   373 val rex_def = thm "rex_def"
```
```   374
```
```   375 val rallI = thm "rallI";
```
```   376 val rspec = thm "rspec";
```
```   377 val rallE = thm "rallE";
```
```   378 val rev_oallE = thm "rev_oallE";
```
```   379 val rall_cong = thm "rall_cong";
```
```   380 val rexI = thm "rexI";
```
```   381 val rexCI = thm "rexCI";
```
```   382 val rexE = thm "rexE";
```
```   383 val rex_cong = thm "rex_cong";
```
```   384
```
```   385 val Ord_atomize =
```
```   386     atomize ([("OrdQuant.oall", [ospec]),("OrdQuant.rall", [rspec])]@
```
```   387                  ZF_conn_pairs,
```
```   388              ZF_mem_pairs);
```
```   389 simpset_ref() := simpset() setmksimps (map mk_eq o Ord_atomize o gen_all);
```
```   390 *}
```
```   391
```
```   392 text{*Setting up the one-point-rule simproc*}
```
```   393 ML
```
```   394 {*
```
```   395
```
```   396 let
```
```   397 val ex_pattern = Thm.read_cterm (Theory.sign_of (the_context ()))
```
```   398                                 ("EX x[M]. P(x) & Q(x)", FOLogic.oT)
```
```   399
```
```   400 val prove_rex_tac = rewtac rex_def THEN
```
```   401                     Quantifier1.prove_one_point_ex_tac;
```
```   402
```
```   403 val rearrange_bex = Quantifier1.rearrange_bex prove_rex_tac;
```
```   404
```
```   405 val all_pattern = Thm.read_cterm (Theory.sign_of (the_context ()))
```
```   406                                  ("ALL x[M]. P(x) --> Q(x)", FOLogic.oT)
```
```   407
```
```   408 val prove_rall_tac = rewtac rall_def THEN
```
```   409                      Quantifier1.prove_one_point_all_tac;
```
```   410
```
```   411 val rearrange_ball = Quantifier1.rearrange_ball prove_rall_tac;
```
```   412
```
```   413 val defREX_regroup = mk_simproc "defined REX" [ex_pattern] rearrange_bex;
```
```   414 val defRALL_regroup = mk_simproc "defined RALL" [all_pattern] rearrange_ball;
```
```   415 in
```
```   416
```
```   417 Addsimprocs [defRALL_regroup,defREX_regroup]
```
```   418
```
```   419 end;
```
```   420 *}
```
```   421
```
```   422 end
```