src/ZF/Ordinal.thy
changeset 13172 03a5afa7b888
parent 13162 660a71e712af
child 13203 fac77a839aa2
     1.1 --- a/src/ZF/Ordinal.thy	Wed May 22 17:26:34 2002 +0200
     1.2 +++ b/src/ZF/Ordinal.thy	Wed May 22 18:11:57 2002 +0200
     1.3 @@ -147,7 +147,7 @@
     1.4  lemma Ord_succ_iff [iff]: "Ord(succ(i)) <-> Ord(i)"
     1.5  by (blast intro: Ord_succ dest!: Ord_succD)
     1.6  
     1.7 -lemma Ord_Un [TC]: "[| Ord(i); Ord(j) |] ==> Ord(i Un j)"
     1.8 +lemma Ord_Un [intro,simp,TC]: "[| Ord(i); Ord(j) |] ==> Ord(i Un j)"
     1.9  apply (unfold Ord_def)
    1.10  apply (blast intro!: Transset_Un)
    1.11  done
    1.12 @@ -456,6 +456,9 @@
    1.13  apply (blast intro: elim: ltE) +
    1.14  done
    1.15  
    1.16 +lemma lt_imp_0_lt: "j<i ==> 0<i"
    1.17 +by (blast intro: lt_trans1 Ord_0_le [OF lt_Ord]) 
    1.18 +
    1.19  lemma succ_lt_iff: "succ(i) < j \<longleftrightarrow> i<j & succ(i) \<noteq> j"
    1.20  apply auto 
    1.21  apply (blast intro: lt_trans le_refl dest: lt_Ord) 
    1.22 @@ -518,17 +521,28 @@
    1.23       "[| Ord(i); Ord(j) |] ==> k \<le> i \<union> j <-> k \<le> i | k \<le> j";
    1.24  by (simp add: succ_Un_distrib lt_Un_iff [symmetric]) 
    1.25  
    1.26 +lemma Un_upper1_lt: "[|k < i; Ord(j)|] ==> k < i Un j"
    1.27 +by (simp add: lt_Un_iff lt_Ord2) 
    1.28 +
    1.29 +lemma Un_upper2_lt: "[|k < j; Ord(i)|] ==> k < i Un j"
    1.30 +by (simp add: lt_Un_iff lt_Ord2) 
    1.31 +
    1.32 +(*See also Transset_iff_Union_succ*)
    1.33 +lemma Ord_Union_succ_eq: "Ord(i) ==> \<Union>(succ(i)) = i"
    1.34 +by (blast intro: Ord_trans)
    1.35 +
    1.36  
    1.37  (*FIXME: the Intersection duals are missing!*)
    1.38  
    1.39  (*** Results about limits ***)
    1.40  
    1.41 -lemma Ord_Union: "[| !!i. i:A ==> Ord(i) |] ==> Ord(Union(A))"
    1.42 +lemma Ord_Union [intro,simp,TC]: "[| !!i. i:A ==> Ord(i) |] ==> Ord(Union(A))"
    1.43  apply (rule Ord_is_Transset [THEN Transset_Union_family, THEN OrdI])
    1.44  apply (blast intro: Ord_contains_Transset)+
    1.45  done
    1.46  
    1.47 -lemma Ord_UN: "[| !!x. x:A ==> Ord(B(x)) |] ==> Ord(UN x:A. B(x))"
    1.48 +lemma Ord_UN [intro,simp,TC]:
    1.49 +     "[| !!x. x:A ==> Ord(B(x)) |] ==> Ord(UN x:A. B(x))"
    1.50  by (rule Ord_Union, blast)
    1.51  
    1.52  (* No < version; consider (UN i:nat.i)=nat *)
    1.53 @@ -545,6 +559,10 @@
    1.54  apply (blast intro: succ_leI)+
    1.55  done
    1.56  
    1.57 +lemma UN_upper_lt:
    1.58 +     "[| a\<in>A;  i < b(a);  Ord(\<Union>x\<in>A. b(x)) |] ==> i < (\<Union>x\<in>A. b(x))"
    1.59 +by (unfold lt_def, blast) 
    1.60 +
    1.61  lemma UN_upper_le:
    1.62       "[| a: A;  i le b(a);  Ord(UN x:A. b(x)) |] ==> i le (UN x:A. b(x))"
    1.63  apply (frule ltD)
    1.64 @@ -552,6 +570,15 @@
    1.65  apply (blast intro: lt_Ord UN_upper)+
    1.66  done
    1.67  
    1.68 +lemma lt_Union_iff: "\<forall>i\<in>A. Ord(i) ==> (j < \<Union>(A)) <-> (\<exists>i\<in>A. j<i)"
    1.69 +by (auto simp: lt_def Ord_Union)
    1.70 +
    1.71 +lemma Union_upper_le:
    1.72 +     "[| j: J;  i\<le>j;  Ord(\<Union>(J)) |] ==> i \<le> \<Union>J"
    1.73 +apply (subst Union_eq_UN)  
    1.74 +apply (rule UN_upper_le, auto)
    1.75 +done
    1.76 +
    1.77  lemma le_implies_UN_le_UN:
    1.78      "[| !!x. x:A ==> c(x) le d(x) |] ==> (UN x:A. c(x)) le (UN x:A. d(x))"
    1.79  apply (rule UN_least_le)
    1.80 @@ -587,6 +614,18 @@
    1.81  lemma Limit_has_succ: "[| Limit(i);  j<i |] ==> succ(j) < i"
    1.82  by (unfold Limit_def, blast)
    1.83  
    1.84 +lemma zero_not_Limit [iff]: "~ Limit(0)"
    1.85 +by (simp add: Limit_def)
    1.86 +
    1.87 +lemma Limit_has_1: "Limit(i) ==> 1 < i"
    1.88 +by (blast intro: Limit_has_0 Limit_has_succ)
    1.89 +
    1.90 +lemma increasing_LimitI: "[| 0<l; \<forall>x\<in>l. \<exists>y\<in>l. x<y |] ==> Limit(l)"
    1.91 +apply (simp add: Limit_def lt_Ord2, clarify)
    1.92 +apply (drule_tac i=y in ltD) 
    1.93 +apply (blast intro: lt_trans1 [OF _ ltI] lt_Ord2)
    1.94 +done
    1.95 +
    1.96  lemma non_succ_LimitI: 
    1.97      "[| 0<i;  ALL y. succ(y) ~= i |] ==> Limit(i)"
    1.98  apply (unfold Limit_def)
    1.99 @@ -608,6 +647,7 @@
   1.100  lemma Limit_le_succD: "[| Limit(i);  i le succ(j) |] ==> i le j"
   1.101  by (blast elim!: leE)
   1.102  
   1.103 +
   1.104  (** Traditional 3-way case analysis on ordinals **)
   1.105  
   1.106  lemma Ord_cases_disj: "Ord(i) ==> i=0 | (EX j. Ord(j) & i=succ(j)) | Limit(i)"
   1.107 @@ -631,6 +671,33 @@
   1.108  apply (erule Ord_cases, blast+)
   1.109  done
   1.110  
   1.111 +text{*A set of ordinals is either empty, contains its own union, or its
   1.112 +union is a limit ordinal.*}
   1.113 +lemma Ord_set_cases:
   1.114 +   "\<forall>i\<in>I. Ord(i) ==> I=0 \<or> \<Union>(I) \<in> I \<or> (\<Union>(I) \<notin> I \<and> Limit(\<Union>(I)))"
   1.115 +apply (clarify elim!: not_emptyE) 
   1.116 +apply (cases "\<Union>(I)" rule: Ord_cases) 
   1.117 +   apply (blast intro: Ord_Union)
   1.118 +  apply (blast intro: subst_elem)
   1.119 + apply auto 
   1.120 +apply (clarify elim!: equalityE succ_subsetE)
   1.121 +apply (simp add: Union_subset_iff)
   1.122 +apply (subgoal_tac "B = succ(j)", blast)
   1.123 +apply (rule le_anti_sym) 
   1.124 + apply (simp add: le_subset_iff) 
   1.125 +apply (simp add: ltI)
   1.126 +done
   1.127 +
   1.128 +text{*If the union of a set of ordinals is a successor, then it is
   1.129 +an element of that set.*}
   1.130 +lemma Ord_Union_eq_succD: "[|\<forall>x\<in>X. Ord(x);  \<Union>X = succ(j)|] ==> succ(j) \<in> X"
   1.131 +by (drule Ord_set_cases, auto)
   1.132 +
   1.133 +lemma Limit_Union [rule_format]: "[| I \<noteq> 0;  \<forall>i\<in>I. Limit(i) |] ==> Limit(\<Union>I)"
   1.134 +apply (simp add: Limit_def lt_def)
   1.135 +apply (blast intro!: equalityI)
   1.136 +done
   1.137 +
   1.138  (*special induction rules for the "induct" method*)
   1.139  lemmas Ord_induct = Ord_induct [consumes 2]
   1.140    and Ord_induct_rule = Ord_induct [rule_format, consumes 2]