src/ZF/Sum.thy
changeset 13240 bb5f4faea1f3
parent 13220 62c899c77151
child 13255 407ad9c3036d
     1.1 --- a/src/ZF/Sum.thy	Sat Jun 22 18:28:46 2002 +0200
     1.2 +++ b/src/ZF/Sum.thy	Sun Jun 23 10:14:13 2002 +0200
     1.3 @@ -7,25 +7,270 @@
     1.4  "Part" primitive for simultaneous recursive type definitions
     1.5  *)
     1.6  
     1.7 -Sum = Bool + equalities + 
     1.8 +theory Sum = Bool + equalities:
     1.9  
    1.10  global
    1.11  
    1.12 -consts
    1.13 -    "+"     :: "[i,i]=>i"                     (infixr 65)
    1.14 -    Inl     :: "i=>i"
    1.15 -    Inr     :: "i=>i"
    1.16 -    "case"  :: "[i=>i, i=>i, i]=>i"
    1.17 -    Part    :: "[i,i=>i] => i"
    1.18 +constdefs
    1.19 +  sum     :: "[i,i]=>i"                     (infixr "+" 65)
    1.20 +     "A+B == {0}*A Un {1}*B"
    1.21 +
    1.22 +  Inl     :: "i=>i"
    1.23 +     "Inl(a) == <0,a>"
    1.24 +
    1.25 +  Inr     :: "i=>i"
    1.26 +     "Inr(b) == <1,b>"
    1.27 +
    1.28 +  "case"  :: "[i=>i, i=>i, i]=>i"
    1.29 +     "case(c,d) == (%<y,z>. cond(y, d(z), c(z)))"
    1.30 +
    1.31 +  (*operator for selecting out the various summands*)
    1.32 +  Part    :: "[i,i=>i] => i"
    1.33 +     "Part(A,h) == {x: A. EX z. x = h(z)}"
    1.34  
    1.35  local
    1.36  
    1.37 -defs
    1.38 -    sum_def     "A+B == {0}*A Un {1}*B"
    1.39 -    Inl_def     "Inl(a) == <0,a>"
    1.40 -    Inr_def     "Inr(b) == <1,b>"
    1.41 -    case_def    "case(c,d) == (%<y,z>. cond(y, d(z), c(z)))"
    1.42 +(*** Rules for the Part primitive ***)
    1.43 +
    1.44 +lemma Part_iff: 
    1.45 +    "a : Part(A,h) <-> a:A & (EX y. a=h(y))"
    1.46 +apply (unfold Part_def)
    1.47 +apply (rule separation)
    1.48 +done
    1.49 +
    1.50 +lemma Part_eqI [intro]: 
    1.51 +    "[| a : A;  a=h(b) |] ==> a : Part(A,h)"
    1.52 +apply (unfold Part_def)
    1.53 +apply blast
    1.54 +done
    1.55 +
    1.56 +lemmas PartI = refl [THEN [2] Part_eqI]
    1.57 +
    1.58 +lemma PartE [elim!]: 
    1.59 +    "[| a : Part(A,h);  !!z. [| a : A;  a=h(z) |] ==> P   
    1.60 +     |] ==> P"
    1.61 +apply (unfold Part_def)
    1.62 +apply blast
    1.63 +done
    1.64 +
    1.65 +lemma Part_subset: "Part(A,h) <= A"
    1.66 +apply (unfold Part_def)
    1.67 +apply (rule Collect_subset)
    1.68 +done
    1.69 +
    1.70 +
    1.71 +(*** Rules for Disjoint Sums ***)
    1.72 +
    1.73 +lemmas sum_defs = sum_def Inl_def Inr_def case_def
    1.74 +
    1.75 +lemma Sigma_bool: "Sigma(bool,C) = C(0) + C(1)"
    1.76 +apply (unfold bool_def sum_def)
    1.77 +apply blast
    1.78 +done
    1.79 +
    1.80 +(** Introduction rules for the injections **)
    1.81 +
    1.82 +lemma InlI [intro!,simp,TC]: "a : A ==> Inl(a) : A+B"
    1.83 +apply (unfold sum_defs)
    1.84 +apply blast
    1.85 +done
    1.86 +
    1.87 +lemma InrI [intro!,simp,TC]: "b : B ==> Inr(b) : A+B"
    1.88 +apply (unfold sum_defs)
    1.89 +apply blast
    1.90 +done
    1.91 +
    1.92 +(** Elimination rules **)
    1.93 +
    1.94 +lemma sumE [elim!]:
    1.95 +    "[| u: A+B;   
    1.96 +        !!x. [| x:A;  u=Inl(x) |] ==> P;  
    1.97 +        !!y. [| y:B;  u=Inr(y) |] ==> P  
    1.98 +     |] ==> P"
    1.99 +apply (unfold sum_defs)
   1.100 +apply (blast intro: elim:); 
   1.101 +done
   1.102 +
   1.103 +(** Injection and freeness equivalences, for rewriting **)
   1.104 +
   1.105 +lemma Inl_iff [iff]: "Inl(a)=Inl(b) <-> a=b"
   1.106 +apply (simp add: sum_defs)
   1.107 +done
   1.108 +
   1.109 +lemma Inr_iff [iff]: "Inr(a)=Inr(b) <-> a=b"
   1.110 +apply (simp add: sum_defs)
   1.111 +done
   1.112 +
   1.113 +lemma Inl_Inr_iff [iff]: "Inl(a)=Inr(b) <-> False"
   1.114 +apply (simp add: sum_defs)
   1.115 +done
   1.116 +
   1.117 +lemma Inr_Inl_iff [iff]: "Inr(b)=Inl(a) <-> False"
   1.118 +apply (simp add: sum_defs)
   1.119 +done
   1.120 +
   1.121 +lemma sum_empty [simp]: "0+0 = 0"
   1.122 +apply (simp add: sum_defs)
   1.123 +done
   1.124 +
   1.125 +(*Injection and freeness rules*)
   1.126 +
   1.127 +lemmas Inl_inject = Inl_iff [THEN iffD1, standard]
   1.128 +lemmas Inr_inject = Inr_iff [THEN iffD1, standard]
   1.129 +lemmas Inl_neq_Inr = Inl_Inr_iff [THEN iffD1, THEN FalseE]
   1.130 +lemmas Inr_neq_Inl = Inr_Inl_iff [THEN iffD1, THEN FalseE]
   1.131 +
   1.132 +
   1.133 +lemma InlD: "Inl(a): A+B ==> a: A"
   1.134 +apply blast
   1.135 +done
   1.136 +
   1.137 +lemma InrD: "Inr(b): A+B ==> b: B"
   1.138 +apply blast
   1.139 +done
   1.140 +
   1.141 +lemma sum_iff: "u: A+B <-> (EX x. x:A & u=Inl(x)) | (EX y. y:B & u=Inr(y))"
   1.142 +apply blast
   1.143 +done
   1.144 +
   1.145 +lemma sum_subset_iff: "A+B <= C+D <-> A<=C & B<=D"
   1.146 +apply blast
   1.147 +done
   1.148 +
   1.149 +lemma sum_equal_iff: "A+B = C+D <-> A=C & B=D"
   1.150 +apply (simp add: extension sum_subset_iff)
   1.151 +apply blast
   1.152 +done
   1.153 +
   1.154 +lemma sum_eq_2_times: "A+A = 2*A"
   1.155 +apply (simp add: sum_def)
   1.156 +apply blast
   1.157 +done
   1.158 +
   1.159 +
   1.160 +(*** Eliminator -- case ***)
   1.161  
   1.162 -  (*operator for selecting out the various summands*)
   1.163 -    Part_def    "Part(A,h) == {x: A. EX z. x = h(z)}"
   1.164 +lemma case_Inl [simp]: "case(c, d, Inl(a)) = c(a)"
   1.165 +apply (simp add: sum_defs)
   1.166 +done
   1.167 +
   1.168 +lemma case_Inr [simp]: "case(c, d, Inr(b)) = d(b)"
   1.169 +apply (simp add: sum_defs)
   1.170 +done
   1.171 +
   1.172 +lemma case_type [TC]:
   1.173 +    "[| u: A+B;  
   1.174 +        !!x. x: A ==> c(x): C(Inl(x));    
   1.175 +        !!y. y: B ==> d(y): C(Inr(y))  
   1.176 +     |] ==> case(c,d,u) : C(u)"
   1.177 +apply (auto );  
   1.178 +done
   1.179 +
   1.180 +lemma expand_case: "u: A+B ==>    
   1.181 +        R(case(c,d,u)) <->  
   1.182 +        ((ALL x:A. u = Inl(x) --> R(c(x))) &  
   1.183 +        (ALL y:B. u = Inr(y) --> R(d(y))))"
   1.184 +by auto
   1.185 +
   1.186 +lemma case_cong:
   1.187 +  "[| z: A+B;    
   1.188 +      !!x. x:A ==> c(x)=c'(x);   
   1.189 +      !!y. y:B ==> d(y)=d'(y)    
   1.190 +   |] ==> case(c,d,z) = case(c',d',z)"
   1.191 +by (auto ); 
   1.192 +
   1.193 +lemma case_case: "z: A+B ==>    
   1.194 +        case(c, d, case(%x. Inl(c'(x)), %y. Inr(d'(y)), z)) =  
   1.195 +        case(%x. c(c'(x)), %y. d(d'(y)), z)"
   1.196 +by auto
   1.197 +
   1.198 +
   1.199 +(*** More rules for Part(A,h) ***)
   1.200 +
   1.201 +lemma Part_mono: "A<=B ==> Part(A,h)<=Part(B,h)"
   1.202 +apply blast
   1.203 +done
   1.204 +
   1.205 +lemma Part_Collect: "Part(Collect(A,P), h) = Collect(Part(A,h), P)"
   1.206 +apply blast
   1.207 +done
   1.208 +
   1.209 +lemmas Part_CollectE =
   1.210 +     Part_Collect [THEN equalityD1, THEN subsetD, THEN CollectE, standard]
   1.211 +
   1.212 +lemma Part_Inl: "Part(A+B,Inl) = {Inl(x). x: A}"
   1.213 +apply blast
   1.214 +done
   1.215 +
   1.216 +lemma Part_Inr: "Part(A+B,Inr) = {Inr(y). y: B}"
   1.217 +apply blast
   1.218 +done
   1.219 +
   1.220 +lemma PartD1: "a : Part(A,h) ==> a : A"
   1.221 +apply (simp add: Part_def)
   1.222 +done
   1.223 +
   1.224 +lemma Part_id: "Part(A,%x. x) = A"
   1.225 +apply blast
   1.226 +done
   1.227 +
   1.228 +lemma Part_Inr2: "Part(A+B, %x. Inr(h(x))) = {Inr(y). y: Part(B,h)}"
   1.229 +apply blast
   1.230 +done
   1.231 +
   1.232 +lemma Part_sum_equality: "C <= A+B ==> Part(C,Inl) Un Part(C,Inr) = C"
   1.233 +apply blast
   1.234 +done
   1.235 +
   1.236 +ML
   1.237 +{*
   1.238 +val sum_def = thm "sum_def";
   1.239 +val Inl_def = thm "Inl_def";
   1.240 +val Inr_def = thm "Inr_def";
   1.241 +val sum_defs = thms "sum_defs";
   1.242 +
   1.243 +val Part_iff = thm "Part_iff";
   1.244 +val Part_eqI = thm "Part_eqI";
   1.245 +val PartI = thm "PartI";
   1.246 +val PartE = thm "PartE";
   1.247 +val Part_subset = thm "Part_subset";
   1.248 +val Sigma_bool = thm "Sigma_bool";
   1.249 +val InlI = thm "InlI";
   1.250 +val InrI = thm "InrI";
   1.251 +val sumE = thm "sumE";
   1.252 +val Inl_iff = thm "Inl_iff";
   1.253 +val Inr_iff = thm "Inr_iff";
   1.254 +val Inl_Inr_iff = thm "Inl_Inr_iff";
   1.255 +val Inr_Inl_iff = thm "Inr_Inl_iff";
   1.256 +val sum_empty = thm "sum_empty";
   1.257 +val Inl_inject = thm "Inl_inject";
   1.258 +val Inr_inject = thm "Inr_inject";
   1.259 +val Inl_neq_Inr = thm "Inl_neq_Inr";
   1.260 +val Inr_neq_Inl = thm "Inr_neq_Inl";
   1.261 +val InlD = thm "InlD";
   1.262 +val InrD = thm "InrD";
   1.263 +val sum_iff = thm "sum_iff";
   1.264 +val sum_subset_iff = thm "sum_subset_iff";
   1.265 +val sum_equal_iff = thm "sum_equal_iff";
   1.266 +val sum_eq_2_times = thm "sum_eq_2_times";
   1.267 +val case_Inl = thm "case_Inl";
   1.268 +val case_Inr = thm "case_Inr";
   1.269 +val case_type = thm "case_type";
   1.270 +val expand_case = thm "expand_case";
   1.271 +val case_cong = thm "case_cong";
   1.272 +val case_case = thm "case_case";
   1.273 +val Part_mono = thm "Part_mono";
   1.274 +val Part_Collect = thm "Part_Collect";
   1.275 +val Part_CollectE = thm "Part_CollectE";
   1.276 +val Part_Inl = thm "Part_Inl";
   1.277 +val Part_Inr = thm "Part_Inr";
   1.278 +val PartD1 = thm "PartD1";
   1.279 +val Part_id = thm "Part_id";
   1.280 +val Part_Inr2 = thm "Part_Inr2";
   1.281 +val Part_sum_equality = thm "Part_sum_equality";
   1.282 +
   1.283 +*}
   1.284 +
   1.285 +
   1.286 +
   1.287  end