src/ZF/OrdQuant.thy
author paulson
Wed May 22 17:25:40 2002 +0200 (2002-05-22)
changeset 13170 9e23faed6c97
parent 13169 394a6c649547
child 13172 03a5afa7b888
permissions -rw-r--r--
tidied
paulson@2469
     1
(*  Title:      ZF/AC/OrdQuant.thy
paulson@2469
     2
    ID:         $Id$
paulson@2469
     3
    Authors:    Krzysztof Grabczewski and L C Paulson
paulson@2469
     4
paulson@2469
     5
Quantifiers and union operator for ordinals. 
paulson@2469
     6
*)
paulson@2469
     7
paulson@12620
     8
theory OrdQuant = Ordinal:
paulson@2469
     9
paulson@12620
    10
constdefs
paulson@2469
    11
  
paulson@2469
    12
  (* Ordinal Quantifiers *)
paulson@12620
    13
  oall :: "[i, i => o] => o"
paulson@12620
    14
    "oall(A, P) == ALL x. x<A --> P(x)"
paulson@12620
    15
  
paulson@12620
    16
  oex :: "[i, i => o] => o"
paulson@12620
    17
    "oex(A, P)  == EX x. x<A & P(x)"
paulson@2469
    18
paulson@2469
    19
  (* Ordinal Union *)
paulson@12620
    20
  OUnion :: "[i, i => i] => i"
paulson@12620
    21
    "OUnion(i,B) == {z: UN x:i. B(x). Ord(i)}"
paulson@2469
    22
  
paulson@2469
    23
syntax
paulson@12620
    24
  "@oall"     :: "[idt, i, o] => o"        ("(3ALL _<_./ _)" 10)
paulson@12620
    25
  "@oex"      :: "[idt, i, o] => o"        ("(3EX _<_./ _)" 10)
paulson@12620
    26
  "@OUNION"   :: "[idt, i, i] => i"        ("(3UN _<_./ _)" 10)
paulson@2469
    27
paulson@2469
    28
translations
paulson@2469
    29
  "ALL x<a. P"  == "oall(a, %x. P)"
paulson@2469
    30
  "EX x<a. P"   == "oex(a, %x. P)"
paulson@2469
    31
  "UN x<a. B"   == "OUnion(a, %x. B)"
paulson@2469
    32
wenzelm@12114
    33
syntax (xsymbols)
paulson@12620
    34
  "@oall"     :: "[idt, i, o] => o"        ("(3\<forall>_<_./ _)" 10)
paulson@12620
    35
  "@oex"      :: "[idt, i, o] => o"        ("(3\<exists>_<_./ _)" 10)
paulson@12620
    36
  "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
paulson@12620
    37
paulson@12620
    38
paulson@12825
    39
(** simplification of the new quantifiers **)
paulson@12825
    40
paulson@12825
    41
paulson@13169
    42
(*MOST IMPORTANT that this is added to the simpset BEFORE Ord_atomize
paulson@13169
    43
  is proved.  Ord_atomize would convert this rule to 
paulson@12825
    44
    x < 0 ==> P(x) == True, which causes dire effects!*)
paulson@12825
    45
lemma [simp]: "(ALL x<0. P(x))"
paulson@12825
    46
by (simp add: oall_def) 
paulson@12825
    47
paulson@12825
    48
lemma [simp]: "~(EX x<0. P(x))"
paulson@12825
    49
by (simp add: oex_def) 
paulson@12825
    50
paulson@12825
    51
lemma [simp]: "(ALL x<succ(i). P(x)) <-> (Ord(i) --> P(i) & (ALL x<i. P(x)))"
paulson@12825
    52
apply (simp add: oall_def le_iff) 
paulson@12825
    53
apply (blast intro: lt_Ord2) 
paulson@12825
    54
done
paulson@12825
    55
paulson@12825
    56
lemma [simp]: "(EX x<succ(i). P(x)) <-> (Ord(i) & (P(i) | (EX x<i. P(x))))"
paulson@12825
    57
apply (simp add: oex_def le_iff) 
paulson@12825
    58
apply (blast intro: lt_Ord2) 
paulson@12825
    59
done
paulson@12825
    60
paulson@12667
    61
declare Ord_Un [intro,simp,TC]
paulson@12667
    62
declare Ord_UN [intro,simp,TC]
paulson@12667
    63
declare Ord_Union [intro,simp,TC]
paulson@12620
    64
paulson@13118
    65
(** Now some very basic ZF theorems **)
paulson@13118
    66
paulson@13118
    67
lemma [simp]: "((P-->Q) <-> (P-->R)) <-> (P --> (Q<->R))"
paulson@13118
    68
by blast
paulson@13118
    69
paulson@13118
    70
lemma [simp]: "cons(a,cons(a,B)) = cons(a,B)"
paulson@13118
    71
by blast
paulson@13118
    72
paulson@13118
    73
lemma trans_imp_trans_on: "trans(r) ==> trans[A](r)"
paulson@13118
    74
by (unfold trans_def trans_on_def, blast)
paulson@13118
    75
paulson@13162
    76
lemma image_is_UN: "[| function(g); x <= domain(g) |] ==> g``x = (UN k:x. {g`k})"
paulson@13118
    77
by (blast intro: function_apply_equality [THEN sym] function_apply_Pair) 
paulson@13118
    78
paulson@13118
    79
lemma functionI: 
paulson@13162
    80
     "[| !!x y y'. [| <x,y>:r; <x,y'>:r |] ==> y=y' |] ==> function(r)"
paulson@13118
    81
by (simp add: function_def, blast) 
paulson@13118
    82
paulson@13118
    83
lemma function_lam: "function (lam x:A. b(x))"
paulson@13118
    84
by (simp add: function_def lam_def) 
paulson@13118
    85
paulson@13118
    86
lemma relation_lam: "relation (lam x:A. b(x))"  
paulson@13149
    87
by (simp add: relation_def lam_def) 
paulson@13118
    88
paulson@13118
    89
lemma restrict_iff: "z \<in> restrict(r,A) \<longleftrightarrow> z \<in> r & (\<exists>x\<in>A. \<exists>y. z = \<langle>x, y\<rangle>)"
paulson@13118
    90
by (simp add: restrict_def) 
paulson@13118
    91
paulson@12620
    92
(** These mostly belong to theory Ordinal **)
paulson@12620
    93
paulson@12620
    94
lemma Union_upper_le:
paulson@13162
    95
     "[| j: J;  i\<le>j;  Ord(\<Union>(J)) |] ==> i \<le> \<Union>J"
paulson@12620
    96
apply (subst Union_eq_UN)  
paulson@12820
    97
apply (rule UN_upper_le, auto)
paulson@12620
    98
done
paulson@12620
    99
paulson@12667
   100
lemma zero_not_Limit [iff]: "~ Limit(0)"
paulson@12667
   101
by (simp add: Limit_def)
paulson@12667
   102
paulson@13162
   103
lemma Limit_has_1: "Limit(i) ==> 1 < i"
paulson@12667
   104
by (blast intro: Limit_has_0 Limit_has_succ)
paulson@12667
   105
paulson@13162
   106
lemma Limit_Union [rule_format]: "[| I \<noteq> 0;  \<forall>i\<in>I. Limit(i) |] ==> Limit(\<Union>I)"
paulson@12667
   107
apply (simp add: Limit_def lt_def)
paulson@12667
   108
apply (blast intro!: equalityI)
paulson@12667
   109
done
paulson@12667
   110
paulson@13162
   111
lemma increasing_LimitI: "[| 0<l; \<forall>x\<in>l. \<exists>y\<in>l. x<y |] ==> Limit(l)"
paulson@12820
   112
apply (simp add: Limit_def lt_Ord2, clarify)
paulson@12620
   113
apply (drule_tac i=y in ltD) 
paulson@12825
   114
apply (blast intro: lt_trans1 [OF _ ltI] lt_Ord2)
paulson@12620
   115
done
paulson@12620
   116
paulson@12620
   117
lemma UN_upper_lt:
paulson@13162
   118
     "[| a\<in>A;  i < b(a);  Ord(\<Union>x\<in>A. b(x)) |] ==> i < (\<Union>x\<in>A. b(x))"
paulson@12620
   119
by (unfold lt_def, blast) 
paulson@12620
   120
paulson@13162
   121
lemma lt_imp_0_lt: "j<i ==> 0<i"
paulson@12620
   122
by (blast intro: lt_trans1 Ord_0_le [OF lt_Ord]) 
paulson@12620
   123
paulson@12620
   124
lemma Ord_set_cases:
paulson@13162
   125
   "\<forall>i\<in>I. Ord(i) ==> I=0 \<or> \<Union>(I) \<in> I \<or> (\<Union>(I) \<notin> I \<and> Limit(\<Union>(I)))"
paulson@12620
   126
apply (clarify elim!: not_emptyE) 
paulson@12620
   127
apply (cases "\<Union>(I)" rule: Ord_cases) 
paulson@12620
   128
   apply (blast intro: Ord_Union)
paulson@12620
   129
  apply (blast intro: subst_elem)
paulson@12620
   130
 apply auto 
paulson@12620
   131
apply (clarify elim!: equalityE succ_subsetE)
paulson@12620
   132
apply (simp add: Union_subset_iff)
paulson@12620
   133
apply (subgoal_tac "B = succ(j)", blast )
paulson@12620
   134
apply (rule le_anti_sym) 
paulson@12620
   135
 apply (simp add: le_subset_iff) 
paulson@12620
   136
apply (simp add: ltI)
paulson@12620
   137
done
paulson@12620
   138
paulson@12620
   139
lemma Ord_Union_eq_succD: "[|\<forall>x\<in>X. Ord(x);  \<Union>X = succ(j)|] ==> succ(j) \<in> X"
paulson@12620
   140
by (drule Ord_set_cases, auto)
paulson@12620
   141
paulson@12620
   142
(*See also Transset_iff_Union_succ*)
paulson@13162
   143
lemma Ord_Union_succ_eq: "Ord(i) ==> \<Union>(succ(i)) = i"
paulson@12620
   144
by (blast intro: Ord_trans)
wenzelm@2540
   145
paulson@13162
   146
lemma lt_Union_iff: "\<forall>i\<in>A. Ord(i) ==> (j < \<Union>(A)) <-> (\<exists>i\<in>A. j<i)"
paulson@12620
   147
by (auto simp: lt_def Ord_Union)
paulson@12620
   148
paulson@12620
   149
lemma Un_upper1_lt: "[|k < i; Ord(j)|] ==> k < i Un j"
paulson@12620
   150
by (simp add: lt_def) 
paulson@12620
   151
paulson@12620
   152
lemma Un_upper2_lt: "[|k < j; Ord(i)|] ==> k < i Un j"
paulson@12620
   153
by (simp add: lt_def) 
paulson@12620
   154
paulson@12620
   155
lemma Ord_OUN [intro,simp]:
paulson@13162
   156
     "[| !!x. x<A ==> Ord(B(x)) |] ==> Ord(\<Union>x<A. B(x))"
paulson@12620
   157
by (simp add: OUnion_def ltI Ord_UN) 
paulson@12620
   158
paulson@12620
   159
lemma OUN_upper_lt:
paulson@13162
   160
     "[| a<A;  i < b(a);  Ord(\<Union>x<A. b(x)) |] ==> i < (\<Union>x<A. b(x))"
paulson@12620
   161
by (unfold OUnion_def lt_def, blast )
paulson@12620
   162
paulson@12620
   163
lemma OUN_upper_le:
paulson@13162
   164
     "[| a<A;  i\<le>b(a);  Ord(\<Union>x<A. b(x)) |] ==> i \<le> (\<Union>x<A. b(x))"
paulson@12820
   165
apply (unfold OUnion_def, auto)
paulson@12620
   166
apply (rule UN_upper_le )
paulson@12620
   167
apply (auto simp add: lt_def) 
paulson@12620
   168
done
paulson@2469
   169
paulson@12620
   170
lemma Limit_OUN_eq: "Limit(i) ==> (UN x<i. x) = i"
paulson@12620
   171
by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)
paulson@12620
   172
paulson@12620
   173
(* No < version; consider (UN i:nat.i)=nat *)
paulson@12620
   174
lemma OUN_least:
paulson@12620
   175
     "(!!x. x<A ==> B(x) \<subseteq> C) ==> (UN x<A. B(x)) \<subseteq> C"
paulson@12620
   176
by (simp add: OUnion_def UN_least ltI)
paulson@12620
   177
paulson@12620
   178
(* No < version; consider (UN i:nat.i)=nat *)
paulson@12620
   179
lemma OUN_least_le:
paulson@12620
   180
     "[| Ord(i);  !!x. x<A ==> b(x) \<le> i |] ==> (UN x<A. b(x)) \<le> i"
paulson@12620
   181
by (simp add: OUnion_def UN_least_le ltI Ord_0_le)
paulson@12620
   182
paulson@12620
   183
lemma le_implies_OUN_le_OUN:
paulson@12620
   184
     "[| !!x. x<A ==> c(x) \<le> d(x) |] ==> (UN x<A. c(x)) \<le> (UN x<A. d(x))"
paulson@12620
   185
by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)
paulson@12620
   186
paulson@12620
   187
lemma OUN_UN_eq:
paulson@12620
   188
     "(!!x. x:A ==> Ord(B(x)))
paulson@12620
   189
      ==> (UN z < (UN x:A. B(x)). C(z)) = (UN  x:A. UN z < B(x). C(z))"
paulson@12620
   190
by (simp add: OUnion_def) 
paulson@12620
   191
paulson@12620
   192
lemma OUN_Union_eq:
paulson@12620
   193
     "(!!x. x:X ==> Ord(x))
paulson@12620
   194
      ==> (UN z < Union(X). C(z)) = (UN x:X. UN z < x. C(z))"
paulson@12620
   195
by (simp add: OUnion_def) 
paulson@12620
   196
paulson@12763
   197
(*So that rule_format will get rid of ALL x<A...*)
paulson@12763
   198
lemma atomize_oall [symmetric, rulify]:
paulson@12763
   199
     "(!!x. x<A ==> P(x)) == Trueprop (ALL x<A. P(x))"
paulson@12763
   200
by (simp add: oall_def atomize_all atomize_imp)
paulson@12763
   201
paulson@13169
   202
(*** universal quantifier for ordinals ***)
paulson@13169
   203
paulson@13169
   204
lemma oallI [intro!]:
paulson@13169
   205
    "[| !!x. x<A ==> P(x) |] ==> ALL x<A. P(x)"
paulson@13170
   206
by (simp add: oall_def) 
paulson@13169
   207
paulson@13169
   208
lemma ospec: "[| ALL x<A. P(x);  x<A |] ==> P(x)"
paulson@13170
   209
by (simp add: oall_def) 
paulson@13169
   210
paulson@13169
   211
lemma oallE:
paulson@13169
   212
    "[| ALL x<A. P(x);  P(x) ==> Q;  ~x<A ==> Q |] ==> Q"
paulson@13170
   213
apply (simp add: oall_def, blast) 
paulson@13169
   214
done
paulson@13169
   215
paulson@13169
   216
lemma rev_oallE [elim]:
paulson@13169
   217
    "[| ALL x<A. P(x);  ~x<A ==> Q;  P(x) ==> Q |] ==> Q"
paulson@13170
   218
apply (simp add: oall_def, blast)  
paulson@13169
   219
done
paulson@13169
   220
paulson@13169
   221
paulson@13169
   222
(*Trival rewrite rule;   (ALL x<a.P)<->P holds only if a is not 0!*)
paulson@13169
   223
lemma oall_simp [simp]: "(ALL x<a. True) <-> True"
paulson@13170
   224
by blast
paulson@13169
   225
paulson@13169
   226
(*Congruence rule for rewriting*)
paulson@13169
   227
lemma oall_cong [cong]:
paulson@13169
   228
    "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |] ==> oall(a,P) <-> oall(a',P')"
paulson@13169
   229
by (simp add: oall_def)
paulson@13169
   230
paulson@13169
   231
paulson@13169
   232
(*** existential quantifier for ordinals ***)
paulson@13169
   233
paulson@13169
   234
lemma oexI [intro]:
paulson@13169
   235
    "[| P(x);  x<A |] ==> EX x<A. P(x)"
paulson@13170
   236
apply (simp add: oex_def, blast) 
paulson@13169
   237
done
paulson@13169
   238
paulson@13169
   239
(*Not of the general form for such rules; ~EX has become ALL~ *)
paulson@13169
   240
lemma oexCI:
paulson@13169
   241
   "[| ALL x<A. ~P(x) ==> P(a);  a<A |] ==> EX x<A. P(x)"
paulson@13170
   242
apply (simp add: oex_def, blast) 
paulson@13169
   243
done
paulson@13169
   244
paulson@13169
   245
lemma oexE [elim!]:
paulson@13169
   246
    "[| EX x<A. P(x);  !!x. [| x<A; P(x) |] ==> Q |] ==> Q"
paulson@13170
   247
apply (simp add: oex_def, blast) 
paulson@13169
   248
done
paulson@13169
   249
paulson@13169
   250
lemma oex_cong [cong]:
paulson@13169
   251
    "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |] ==> oex(a,P) <-> oex(a',P')"
paulson@13169
   252
apply (simp add: oex_def cong add: conj_cong)
paulson@13169
   253
done
paulson@13169
   254
paulson@13169
   255
paulson@13169
   256
(*** Rules for Ordinal-Indexed Unions ***)
paulson@13169
   257
paulson@13169
   258
lemma OUN_I [intro]: "[| a<i;  b: B(a) |] ==> b: (UN z<i. B(z))"
paulson@13170
   259
by (unfold OUnion_def lt_def, blast)
paulson@13169
   260
paulson@13169
   261
lemma OUN_E [elim!]:
paulson@13169
   262
    "[| b : (UN z<i. B(z));  !!a.[| b: B(a);  a<i |] ==> R |] ==> R"
paulson@13170
   263
apply (unfold OUnion_def lt_def, blast)
paulson@13169
   264
done
paulson@13169
   265
paulson@13169
   266
lemma OUN_iff: "b : (UN x<i. B(x)) <-> (EX x<i. b : B(x))"
paulson@13170
   267
by (unfold OUnion_def oex_def lt_def, blast)
paulson@13169
   268
paulson@13169
   269
lemma OUN_cong [cong]:
paulson@13169
   270
    "[| i=j;  !!x. x<j ==> C(x)=D(x) |] ==> (UN x<i. C(x)) = (UN x<j. D(x))"
paulson@13169
   271
by (simp add: OUnion_def lt_def OUN_iff)
paulson@13169
   272
paulson@13169
   273
declare ltD [THEN beta, simp]
paulson@13169
   274
paulson@13169
   275
paulson@13169
   276
lemma lt_induct: 
paulson@13169
   277
    "[| i<k;  !!x.[| x<k;  ALL y<x. P(y) |] ==> P(x) |]  ==>  P(i)"
paulson@13169
   278
apply (simp add: lt_def oall_def)
paulson@13169
   279
apply (erule conjE) 
paulson@13170
   280
apply (erule Ord_induct, assumption, blast) 
paulson@13169
   281
done
paulson@13169
   282
paulson@13169
   283
ML
paulson@13169
   284
{*
paulson@13169
   285
val oall_def = thm "oall_def"
paulson@13169
   286
val oex_def = thm "oex_def"
paulson@13169
   287
val OUnion_def = thm "OUnion_def"
paulson@13169
   288
paulson@13169
   289
val oallI = thm "oallI";
paulson@13169
   290
val ospec = thm "ospec";
paulson@13169
   291
val oallE = thm "oallE";
paulson@13169
   292
val rev_oallE = thm "rev_oallE";
paulson@13169
   293
val oall_simp = thm "oall_simp";
paulson@13169
   294
val oall_cong = thm "oall_cong";
paulson@13169
   295
val oexI = thm "oexI";
paulson@13169
   296
val oexCI = thm "oexCI";
paulson@13169
   297
val oexE = thm "oexE";
paulson@13169
   298
val oex_cong = thm "oex_cong";
paulson@13169
   299
val OUN_I = thm "OUN_I";
paulson@13169
   300
val OUN_E = thm "OUN_E";
paulson@13169
   301
val OUN_iff = thm "OUN_iff";
paulson@13169
   302
val OUN_cong = thm "OUN_cong";
paulson@13169
   303
val lt_induct = thm "lt_induct";
paulson@13169
   304
paulson@13169
   305
val Ord_atomize =
paulson@13169
   306
    atomize (("OrdQuant.oall", [ospec])::ZF_conn_pairs, ZF_mem_pairs);
paulson@13169
   307
simpset_ref() := simpset() setmksimps (map mk_eq o Ord_atomize o gen_all);
paulson@13169
   308
*}
paulson@13169
   309
paulson@2469
   310
end