src/ZF/OrdQuant.thy
author paulson
Thu Jan 03 17:01:59 2002 +0100 (2002-01-03)
changeset 12620 4e6626725e21
parent 12552 d2d2ab3f1f37
child 12667 7e6eaaa125f2
permissions -rw-r--r--
Some new theorems for ordinals
     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 declare Ord_Un [intro,simp]
    40 declare Ord_UN [intro,simp]
    41 declare Ord_Union [intro,simp]
    42 
    43 (** These mostly belong to theory Ordinal **)
    44 
    45 lemma Union_upper_le:
    46      "\<lbrakk>j: J;  i\<le>j;  Ord(\<Union>(J))\<rbrakk> \<Longrightarrow> i \<le> \<Union>J"
    47 apply (subst Union_eq_UN)  
    48 apply (rule UN_upper_le)
    49 apply auto
    50 done
    51 
    52 lemma increasing_LimitI: "\<lbrakk>0<l; \<forall>x\<in>l. \<exists>y\<in>l. x<y\<rbrakk> \<Longrightarrow> Limit(l)"
    53 apply (simp add: Limit_def lt_Ord2)
    54 apply clarify
    55 apply (drule_tac i=y in ltD) 
    56 apply (blast intro: lt_trans1 succ_leI ltI lt_Ord2)
    57 done
    58 
    59 lemma UN_upper_lt:
    60      "\<lbrakk>a\<in> A;  i < b(a);  Ord(\<Union>x\<in>A. b(x))\<rbrakk> \<Longrightarrow> i < (\<Union>x\<in>A. b(x))"
    61 by (unfold lt_def, blast) 
    62 
    63 lemma lt_imp_0_lt: "j<i \<Longrightarrow> 0<i"
    64 by (blast intro: lt_trans1 Ord_0_le [OF lt_Ord]) 
    65 
    66 lemma Ord_set_cases:
    67    "\<forall>i\<in>I. Ord(i) \<Longrightarrow> I=0 \<or> \<Union>(I) \<in> I \<or> (\<Union>(I) \<notin> I \<and> Limit(\<Union>(I)))"
    68 apply (clarify elim!: not_emptyE) 
    69 apply (cases "\<Union>(I)" rule: Ord_cases) 
    70    apply (blast intro: Ord_Union)
    71   apply (blast intro: subst_elem)
    72  apply auto 
    73 apply (clarify elim!: equalityE succ_subsetE)
    74 apply (simp add: Union_subset_iff)
    75 apply (subgoal_tac "B = succ(j)", blast )
    76 apply (rule le_anti_sym) 
    77  apply (simp add: le_subset_iff) 
    78 apply (simp add: ltI)
    79 done
    80 
    81 lemma Ord_Union_eq_succD: "[|\<forall>x\<in>X. Ord(x);  \<Union>X = succ(j)|] ==> succ(j) \<in> X"
    82 by (drule Ord_set_cases, auto)
    83 
    84 (*See also Transset_iff_Union_succ*)
    85 lemma Ord_Union_succ_eq: "Ord(i) \<Longrightarrow> \<Union>(succ(i)) = i"
    86 by (blast intro: Ord_trans)
    87 
    88 lemma lt_Union_iff: "\<forall>i\<in>A. Ord(i) \<Longrightarrow> (j < \<Union>(A)) <-> (\<exists>i\<in>A. j<i)"
    89 by (auto simp: lt_def Ord_Union)
    90 
    91 lemma Un_upper1_lt: "[|k < i; Ord(j)|] ==> k < i Un j"
    92 by (simp add: lt_def) 
    93 
    94 lemma Un_upper2_lt: "[|k < j; Ord(i)|] ==> k < i Un j"
    95 by (simp add: lt_def) 
    96 
    97 lemma Ord_OUN [intro,simp]:
    98      "\<lbrakk>!!x. x<A \<Longrightarrow> Ord(B(x))\<rbrakk> \<Longrightarrow> Ord(\<Union>x<A. B(x))"
    99 by (simp add: OUnion_def ltI Ord_UN) 
   100 
   101 lemma OUN_upper_lt:
   102      "\<lbrakk>a<A;  i < b(a);  Ord(\<Union>x<A. b(x))\<rbrakk> \<Longrightarrow> i < (\<Union>x<A. b(x))"
   103 by (unfold OUnion_def lt_def, blast )
   104 
   105 lemma OUN_upper_le:
   106      "\<lbrakk>a<A;  i\<le>b(a);  Ord(\<Union>x<A. b(x))\<rbrakk> \<Longrightarrow> i \<le> (\<Union>x<A. b(x))"
   107 apply (unfold OUnion_def)
   108 apply auto
   109 apply (rule UN_upper_le )
   110 apply (auto simp add: lt_def) 
   111 done
   112 
   113 lemma Limit_OUN_eq: "Limit(i) ==> (UN x<i. x) = i"
   114 by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)
   115 
   116 (* No < version; consider (UN i:nat.i)=nat *)
   117 lemma OUN_least:
   118      "(!!x. x<A ==> B(x) \<subseteq> C) ==> (UN x<A. B(x)) \<subseteq> C"
   119 by (simp add: OUnion_def UN_least ltI)
   120 
   121 (* No < version; consider (UN i:nat.i)=nat *)
   122 lemma OUN_least_le:
   123      "[| Ord(i);  !!x. x<A ==> b(x) \<le> i |] ==> (UN x<A. b(x)) \<le> i"
   124 by (simp add: OUnion_def UN_least_le ltI Ord_0_le)
   125 
   126 lemma le_implies_OUN_le_OUN:
   127      "[| !!x. x<A ==> c(x) \<le> d(x) |] ==> (UN x<A. c(x)) \<le> (UN x<A. d(x))"
   128 by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)
   129 
   130 lemma OUN_UN_eq:
   131      "(!!x. x:A ==> Ord(B(x)))
   132       ==> (UN z < (UN x:A. B(x)). C(z)) = (UN  x:A. UN z < B(x). C(z))"
   133 by (simp add: OUnion_def) 
   134 
   135 lemma OUN_Union_eq:
   136      "(!!x. x:X ==> Ord(x))
   137       ==> (UN z < Union(X). C(z)) = (UN x:X. UN z < x. C(z))"
   138 by (simp add: OUnion_def) 
   139 
   140 end