src/ZF/OrdQuant.thy
author paulson
Wed May 22 18:11:57 2002 +0200 (2002-05-22)
changeset 13172 03a5afa7b888
parent 13170 9e23faed6c97
child 13174 85d3c0981a16
permissions -rw-r--r--
tidying up
     1 (*  Title:      ZF/AC/OrdQuant.thy
     2     ID:         $Id$
     3     Authors:    Krzysztof Grabczewski and L C Paulson
     4 
     5 Quantifiers and union operator for ordinals. 
     6 *)
     7 
     8 theory OrdQuant = Ordinal:
     9 
    10 constdefs
    11   
    12   (* Ordinal Quantifiers *)
    13   oall :: "[i, i => o] => o"
    14     "oall(A, P) == ALL x. x<A --> P(x)"
    15   
    16   oex :: "[i, i => o] => o"
    17     "oex(A, P)  == EX x. x<A & P(x)"
    18 
    19   (* Ordinal Union *)
    20   OUnion :: "[i, i => i] => i"
    21     "OUnion(i,B) == {z: UN x:i. B(x). Ord(i)}"
    22   
    23 syntax
    24   "@oall"     :: "[idt, i, o] => o"        ("(3ALL _<_./ _)" 10)
    25   "@oex"      :: "[idt, i, o] => o"        ("(3EX _<_./ _)" 10)
    26   "@OUNION"   :: "[idt, i, i] => i"        ("(3UN _<_./ _)" 10)
    27 
    28 translations
    29   "ALL x<a. P"  == "oall(a, %x. P)"
    30   "EX x<a. P"   == "oex(a, %x. P)"
    31   "UN x<a. B"   == "OUnion(a, %x. B)"
    32 
    33 syntax (xsymbols)
    34   "@oall"     :: "[idt, i, o] => o"        ("(3\<forall>_<_./ _)" 10)
    35   "@oex"      :: "[idt, i, o] => o"        ("(3\<exists>_<_./ _)" 10)
    36   "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
    37 
    38 
    39 (** simplification of the new quantifiers **)
    40 
    41 
    42 (*MOST IMPORTANT that this is added to the simpset BEFORE Ord_atomize
    43   is proved.  Ord_atomize would convert this rule to 
    44     x < 0 ==> P(x) == True, which causes dire effects!*)
    45 lemma [simp]: "(ALL x<0. P(x))"
    46 by (simp add: oall_def) 
    47 
    48 lemma [simp]: "~(EX x<0. P(x))"
    49 by (simp add: oex_def) 
    50 
    51 lemma [simp]: "(ALL x<succ(i). P(x)) <-> (Ord(i) --> P(i) & (ALL x<i. P(x)))"
    52 apply (simp add: oall_def le_iff) 
    53 apply (blast intro: lt_Ord2) 
    54 done
    55 
    56 lemma [simp]: "(EX x<succ(i). P(x)) <-> (Ord(i) & (P(i) | (EX x<i. P(x))))"
    57 apply (simp add: oex_def le_iff) 
    58 apply (blast intro: lt_Ord2) 
    59 done
    60 
    61 (** Now some very basic ZF theorems **)
    62 
    63 (*FIXME: move to ZF.thy or even to FOL.thy??*)
    64 lemma [simp]: "((P-->Q) <-> (P-->R)) <-> (P --> (Q<->R))"
    65 by blast
    66 
    67 (*FIXME: move to Rel.thy*)
    68 lemma trans_imp_trans_on: "trans(r) ==> trans[A](r)"
    69 by (unfold trans_def trans_on_def, blast)
    70 
    71 lemma Ord_OUN [intro,simp]:
    72      "[| !!x. x<A ==> Ord(B(x)) |] ==> Ord(\<Union>x<A. B(x))"
    73 by (simp add: OUnion_def ltI Ord_UN) 
    74 
    75 lemma OUN_upper_lt:
    76      "[| a<A;  i < b(a);  Ord(\<Union>x<A. b(x)) |] ==> i < (\<Union>x<A. b(x))"
    77 by (unfold OUnion_def lt_def, blast )
    78 
    79 lemma OUN_upper_le:
    80      "[| a<A;  i\<le>b(a);  Ord(\<Union>x<A. b(x)) |] ==> i \<le> (\<Union>x<A. b(x))"
    81 apply (unfold OUnion_def, auto)
    82 apply (rule UN_upper_le )
    83 apply (auto simp add: lt_def) 
    84 done
    85 
    86 lemma Limit_OUN_eq: "Limit(i) ==> (UN x<i. x) = i"
    87 by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)
    88 
    89 (* No < version; consider (UN i:nat.i)=nat *)
    90 lemma OUN_least:
    91      "(!!x. x<A ==> B(x) \<subseteq> C) ==> (UN x<A. B(x)) \<subseteq> C"
    92 by (simp add: OUnion_def UN_least ltI)
    93 
    94 (* No < version; consider (UN i:nat.i)=nat *)
    95 lemma OUN_least_le:
    96      "[| Ord(i);  !!x. x<A ==> b(x) \<le> i |] ==> (UN x<A. b(x)) \<le> i"
    97 by (simp add: OUnion_def UN_least_le ltI Ord_0_le)
    98 
    99 lemma le_implies_OUN_le_OUN:
   100      "[| !!x. x<A ==> c(x) \<le> d(x) |] ==> (UN x<A. c(x)) \<le> (UN x<A. d(x))"
   101 by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)
   102 
   103 lemma OUN_UN_eq:
   104      "(!!x. x:A ==> Ord(B(x)))
   105       ==> (UN z < (UN x:A. B(x)). C(z)) = (UN  x:A. UN z < B(x). C(z))"
   106 by (simp add: OUnion_def) 
   107 
   108 lemma OUN_Union_eq:
   109      "(!!x. x:X ==> Ord(x))
   110       ==> (UN z < Union(X). C(z)) = (UN x:X. UN z < x. C(z))"
   111 by (simp add: OUnion_def) 
   112 
   113 (*So that rule_format will get rid of ALL x<A...*)
   114 lemma atomize_oall [symmetric, rulify]:
   115      "(!!x. x<A ==> P(x)) == Trueprop (ALL x<A. P(x))"
   116 by (simp add: oall_def atomize_all atomize_imp)
   117 
   118 (*** universal quantifier for ordinals ***)
   119 
   120 lemma oallI [intro!]:
   121     "[| !!x. x<A ==> P(x) |] ==> ALL x<A. P(x)"
   122 by (simp add: oall_def) 
   123 
   124 lemma ospec: "[| ALL x<A. P(x);  x<A |] ==> P(x)"
   125 by (simp add: oall_def) 
   126 
   127 lemma oallE:
   128     "[| ALL x<A. P(x);  P(x) ==> Q;  ~x<A ==> Q |] ==> Q"
   129 apply (simp add: oall_def, blast) 
   130 done
   131 
   132 lemma rev_oallE [elim]:
   133     "[| ALL x<A. P(x);  ~x<A ==> Q;  P(x) ==> Q |] ==> Q"
   134 apply (simp add: oall_def, blast)  
   135 done
   136 
   137 
   138 (*Trival rewrite rule;   (ALL x<a.P)<->P holds only if a is not 0!*)
   139 lemma oall_simp [simp]: "(ALL x<a. True) <-> True"
   140 by blast
   141 
   142 (*Congruence rule for rewriting*)
   143 lemma oall_cong [cong]:
   144     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |] ==> oall(a,P) <-> oall(a',P')"
   145 by (simp add: oall_def)
   146 
   147 
   148 (*** existential quantifier for ordinals ***)
   149 
   150 lemma oexI [intro]:
   151     "[| P(x);  x<A |] ==> EX x<A. P(x)"
   152 apply (simp add: oex_def, blast) 
   153 done
   154 
   155 (*Not of the general form for such rules; ~EX has become ALL~ *)
   156 lemma oexCI:
   157    "[| ALL x<A. ~P(x) ==> P(a);  a<A |] ==> EX x<A. P(x)"
   158 apply (simp add: oex_def, blast) 
   159 done
   160 
   161 lemma oexE [elim!]:
   162     "[| EX x<A. P(x);  !!x. [| x<A; P(x) |] ==> Q |] ==> Q"
   163 apply (simp add: oex_def, blast) 
   164 done
   165 
   166 lemma oex_cong [cong]:
   167     "[| a=a';  !!x. x<a' ==> P(x) <-> P'(x) |] ==> oex(a,P) <-> oex(a',P')"
   168 apply (simp add: oex_def cong add: conj_cong)
   169 done
   170 
   171 
   172 (*** Rules for Ordinal-Indexed Unions ***)
   173 
   174 lemma OUN_I [intro]: "[| a<i;  b: B(a) |] ==> b: (UN z<i. B(z))"
   175 by (unfold OUnion_def lt_def, blast)
   176 
   177 lemma OUN_E [elim!]:
   178     "[| b : (UN z<i. B(z));  !!a.[| b: B(a);  a<i |] ==> R |] ==> R"
   179 apply (unfold OUnion_def lt_def, blast)
   180 done
   181 
   182 lemma OUN_iff: "b : (UN x<i. B(x)) <-> (EX x<i. b : B(x))"
   183 by (unfold OUnion_def oex_def lt_def, blast)
   184 
   185 lemma OUN_cong [cong]:
   186     "[| i=j;  !!x. x<j ==> C(x)=D(x) |] ==> (UN x<i. C(x)) = (UN x<j. D(x))"
   187 by (simp add: OUnion_def lt_def OUN_iff)
   188 
   189 declare ltD [THEN beta, simp]
   190 
   191 lemma lt_induct: 
   192     "[| i<k;  !!x.[| x<k;  ALL y<x. P(y) |] ==> P(x) |]  ==>  P(i)"
   193 apply (simp add: lt_def oall_def)
   194 apply (erule conjE) 
   195 apply (erule Ord_induct, assumption, blast) 
   196 done
   197 
   198 ML
   199 {*
   200 val oall_def = thm "oall_def"
   201 val oex_def = thm "oex_def"
   202 val OUnion_def = thm "OUnion_def"
   203 
   204 val oallI = thm "oallI";
   205 val ospec = thm "ospec";
   206 val oallE = thm "oallE";
   207 val rev_oallE = thm "rev_oallE";
   208 val oall_simp = thm "oall_simp";
   209 val oall_cong = thm "oall_cong";
   210 val oexI = thm "oexI";
   211 val oexCI = thm "oexCI";
   212 val oexE = thm "oexE";
   213 val oex_cong = thm "oex_cong";
   214 val OUN_I = thm "OUN_I";
   215 val OUN_E = thm "OUN_E";
   216 val OUN_iff = thm "OUN_iff";
   217 val OUN_cong = thm "OUN_cong";
   218 val lt_induct = thm "lt_induct";
   219 
   220 val Ord_atomize =
   221     atomize (("OrdQuant.oall", [ospec])::ZF_conn_pairs, ZF_mem_pairs);
   222 simpset_ref() := simpset() setmksimps (map mk_eq o Ord_atomize o gen_all);
   223 *}
   224 
   225 end