Some new theorems for ordinals
authorpaulson
Thu Jan 03 17:01:59 2002 +0100 (2002-01-03)
changeset 126204e6626725e21
parent 12619 ddfe8083fef2
child 12621 48cafea0684b
Some new theorems for ordinals
src/ZF/Main.thy
src/ZF/OrdQuant.ML
src/ZF/OrdQuant.thy
     1.1 --- a/src/ZF/Main.thy	Wed Jan 02 21:54:45 2002 +0100
     1.2 +++ b/src/ZF/Main.thy	Thu Jan 03 17:01:59 2002 +0100
     1.3 @@ -46,4 +46,14 @@
     1.4  lemmas posDivAlg_induct = posDivAlg_induct [consumes 2]
     1.5    and negDivAlg_induct = negDivAlg_induct [consumes 2]
     1.6  
     1.7 +
     1.8 +(* belongs to theory Epsilon *)
     1.9 +
    1.10 +lemma def_transrec2:
    1.11 +     "(!!x. f(x)==transrec2(x,a,b))
    1.12 +      ==> f(0) = a & 
    1.13 +          f(succ(i)) = b(i, f(i)) & 
    1.14 +          (Limit(K) --> f(K) = (UN j<K. f(j)))"
    1.15 +by (simp add: transrec2_Limit)
    1.16 +
    1.17  end
     2.1 --- a/src/ZF/OrdQuant.ML	Wed Jan 02 21:54:45 2002 +0100
     2.2 +++ b/src/ZF/OrdQuant.ML	Thu Jan 03 17:01:59 2002 +0100
     2.3 @@ -5,6 +5,10 @@
     2.4  Quantifiers and union operator for ordinals. 
     2.5  *)
     2.6  
     2.7 +val oall_def = thm "oall_def";
     2.8 +val oex_def = thm "oex_def"; 
     2.9 +val OUnion_def = thm "OUnion_def";
    2.10 +
    2.11  (*** universal quantifier for ordinals ***)
    2.12  
    2.13  val prems = Goalw [oall_def] 
     3.1 --- a/src/ZF/OrdQuant.thy	Wed Jan 02 21:54:45 2002 +0100
     3.2 +++ b/src/ZF/OrdQuant.thy	Thu Jan 03 17:01:59 2002 +0100
     3.3 @@ -5,20 +5,25 @@
     3.4  Quantifiers and union operator for ordinals. 
     3.5  *)
     3.6  
     3.7 -OrdQuant = Ordinal +
     3.8 +theory OrdQuant = Ordinal:
     3.9  
    3.10 -consts
    3.11 +constdefs
    3.12    
    3.13    (* Ordinal Quantifiers *)
    3.14 -  oall, oex   :: [i, i => o] => o
    3.15 +  oall :: "[i, i => o] => o"
    3.16 +    "oall(A, P) == ALL x. x<A --> P(x)"
    3.17 +  
    3.18 +  oex :: "[i, i => o] => o"
    3.19 +    "oex(A, P)  == EX x. x<A & P(x)"
    3.20  
    3.21    (* Ordinal Union *)
    3.22 -  OUnion      :: [i, i => i] => i
    3.23 +  OUnion :: "[i, i => i] => i"
    3.24 +    "OUnion(i,B) == {z: UN x:i. B(x). Ord(i)}"
    3.25    
    3.26  syntax
    3.27 -  "@oall"     :: [idt, i, o] => o        ("(3ALL _<_./ _)" 10)
    3.28 -  "@oex"      :: [idt, i, o] => o        ("(3EX _<_./ _)" 10)
    3.29 -  "@OUNION"   :: [idt, i, i] => i        ("(3UN _<_./ _)" 10)
    3.30 +  "@oall"     :: "[idt, i, o] => o"        ("(3ALL _<_./ _)" 10)
    3.31 +  "@oex"      :: "[idt, i, o] => o"        ("(3EX _<_./ _)" 10)
    3.32 +  "@OUNION"   :: "[idt, i, i] => i"        ("(3UN _<_./ _)" 10)
    3.33  
    3.34  translations
    3.35    "ALL x<a. P"  == "oall(a, %x. P)"
    3.36 @@ -26,16 +31,110 @@
    3.37    "UN x<a. B"   == "OUnion(a, %x. B)"
    3.38  
    3.39  syntax (xsymbols)
    3.40 -  "@oall"     :: [idt, i, o] => o        ("(3\\<forall>_<_./ _)" 10)
    3.41 -  "@oex"      :: [idt, i, o] => o        ("(3\\<exists>_<_./ _)" 10)
    3.42 -  "@OUNION"   :: [idt, i, i] => i        ("(3\\<Union>_<_./ _)" 10)
    3.43 +  "@oall"     :: "[idt, i, o] => o"        ("(3\<forall>_<_./ _)" 10)
    3.44 +  "@oex"      :: "[idt, i, o] => o"        ("(3\<exists>_<_./ _)" 10)
    3.45 +  "@OUNION"   :: "[idt, i, i] => i"        ("(3\<Union>_<_./ _)" 10)
    3.46 +
    3.47 +
    3.48 +declare Ord_Un [intro,simp]
    3.49 +declare Ord_UN [intro,simp]
    3.50 +declare Ord_Union [intro,simp]
    3.51 +
    3.52 +(** These mostly belong to theory Ordinal **)
    3.53 +
    3.54 +lemma Union_upper_le:
    3.55 +     "\<lbrakk>j: J;  i\<le>j;  Ord(\<Union>(J))\<rbrakk> \<Longrightarrow> i \<le> \<Union>J"
    3.56 +apply (subst Union_eq_UN)  
    3.57 +apply (rule UN_upper_le)
    3.58 +apply auto
    3.59 +done
    3.60 +
    3.61 +lemma increasing_LimitI: "\<lbrakk>0<l; \<forall>x\<in>l. \<exists>y\<in>l. x<y\<rbrakk> \<Longrightarrow> Limit(l)"
    3.62 +apply (simp add: Limit_def lt_Ord2)
    3.63 +apply clarify
    3.64 +apply (drule_tac i=y in ltD) 
    3.65 +apply (blast intro: lt_trans1 succ_leI ltI lt_Ord2)
    3.66 +done
    3.67 +
    3.68 +lemma UN_upper_lt:
    3.69 +     "\<lbrakk>a\<in> A;  i < b(a);  Ord(\<Union>x\<in>A. b(x))\<rbrakk> \<Longrightarrow> i < (\<Union>x\<in>A. b(x))"
    3.70 +by (unfold lt_def, blast) 
    3.71 +
    3.72 +lemma lt_imp_0_lt: "j<i \<Longrightarrow> 0<i"
    3.73 +by (blast intro: lt_trans1 Ord_0_le [OF lt_Ord]) 
    3.74 +
    3.75 +lemma Ord_set_cases:
    3.76 +   "\<forall>i\<in>I. Ord(i) \<Longrightarrow> I=0 \<or> \<Union>(I) \<in> I \<or> (\<Union>(I) \<notin> I \<and> Limit(\<Union>(I)))"
    3.77 +apply (clarify elim!: not_emptyE) 
    3.78 +apply (cases "\<Union>(I)" rule: Ord_cases) 
    3.79 +   apply (blast intro: Ord_Union)
    3.80 +  apply (blast intro: subst_elem)
    3.81 + apply auto 
    3.82 +apply (clarify elim!: equalityE succ_subsetE)
    3.83 +apply (simp add: Union_subset_iff)
    3.84 +apply (subgoal_tac "B = succ(j)", blast )
    3.85 +apply (rule le_anti_sym) 
    3.86 + apply (simp add: le_subset_iff) 
    3.87 +apply (simp add: ltI)
    3.88 +done
    3.89 +
    3.90 +lemma Ord_Union_eq_succD: "[|\<forall>x\<in>X. Ord(x);  \<Union>X = succ(j)|] ==> succ(j) \<in> X"
    3.91 +by (drule Ord_set_cases, auto)
    3.92 +
    3.93 +(*See also Transset_iff_Union_succ*)
    3.94 +lemma Ord_Union_succ_eq: "Ord(i) \<Longrightarrow> \<Union>(succ(i)) = i"
    3.95 +by (blast intro: Ord_trans)
    3.96  
    3.97 -defs
    3.98 -  
    3.99 -  (* Ordinal Quantifiers *)
   3.100 -  oall_def      "oall(A, P) == ALL x. x<A --> P(x)"
   3.101 -  oex_def       "oex(A, P) == EX x. x<A & P(x)"
   3.102 +lemma lt_Union_iff: "\<forall>i\<in>A. Ord(i) \<Longrightarrow> (j < \<Union>(A)) <-> (\<exists>i\<in>A. j<i)"
   3.103 +by (auto simp: lt_def Ord_Union)
   3.104 +
   3.105 +lemma Un_upper1_lt: "[|k < i; Ord(j)|] ==> k < i Un j"
   3.106 +by (simp add: lt_def) 
   3.107 +
   3.108 +lemma Un_upper2_lt: "[|k < j; Ord(i)|] ==> k < i Un j"
   3.109 +by (simp add: lt_def) 
   3.110 +
   3.111 +lemma Ord_OUN [intro,simp]:
   3.112 +     "\<lbrakk>!!x. x<A \<Longrightarrow> Ord(B(x))\<rbrakk> \<Longrightarrow> Ord(\<Union>x<A. B(x))"
   3.113 +by (simp add: OUnion_def ltI Ord_UN) 
   3.114 +
   3.115 +lemma OUN_upper_lt:
   3.116 +     "\<lbrakk>a<A;  i < b(a);  Ord(\<Union>x<A. b(x))\<rbrakk> \<Longrightarrow> i < (\<Union>x<A. b(x))"
   3.117 +by (unfold OUnion_def lt_def, blast )
   3.118 +
   3.119 +lemma OUN_upper_le:
   3.120 +     "\<lbrakk>a<A;  i\<le>b(a);  Ord(\<Union>x<A. b(x))\<rbrakk> \<Longrightarrow> i \<le> (\<Union>x<A. b(x))"
   3.121 +apply (unfold OUnion_def)
   3.122 +apply auto
   3.123 +apply (rule UN_upper_le )
   3.124 +apply (auto simp add: lt_def) 
   3.125 +done
   3.126  
   3.127 -  OUnion_def     "OUnion(i,B) == {z: UN x:i. B(x). Ord(i)}"
   3.128 -  
   3.129 +lemma Limit_OUN_eq: "Limit(i) ==> (UN x<i. x) = i"
   3.130 +by (simp add: OUnion_def Limit_Union_eq Limit_is_Ord)
   3.131 +
   3.132 +(* No < version; consider (UN i:nat.i)=nat *)
   3.133 +lemma OUN_least:
   3.134 +     "(!!x. x<A ==> B(x) \<subseteq> C) ==> (UN x<A. B(x)) \<subseteq> C"
   3.135 +by (simp add: OUnion_def UN_least ltI)
   3.136 +
   3.137 +(* No < version; consider (UN i:nat.i)=nat *)
   3.138 +lemma OUN_least_le:
   3.139 +     "[| Ord(i);  !!x. x<A ==> b(x) \<le> i |] ==> (UN x<A. b(x)) \<le> i"
   3.140 +by (simp add: OUnion_def UN_least_le ltI Ord_0_le)
   3.141 +
   3.142 +lemma le_implies_OUN_le_OUN:
   3.143 +     "[| !!x. x<A ==> c(x) \<le> d(x) |] ==> (UN x<A. c(x)) \<le> (UN x<A. d(x))"
   3.144 +by (blast intro: OUN_least_le OUN_upper_le le_Ord2 Ord_OUN)
   3.145 +
   3.146 +lemma OUN_UN_eq:
   3.147 +     "(!!x. x:A ==> Ord(B(x)))
   3.148 +      ==> (UN z < (UN x:A. B(x)). C(z)) = (UN  x:A. UN z < B(x). C(z))"
   3.149 +by (simp add: OUnion_def) 
   3.150 +
   3.151 +lemma OUN_Union_eq:
   3.152 +     "(!!x. x:X ==> Ord(x))
   3.153 +      ==> (UN z < Union(X). C(z)) = (UN x:X. UN z < x. C(z))"
   3.154 +by (simp add: OUnion_def) 
   3.155 +
   3.156  end