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