src/ZF/Sum.thy
author wenzelm
Sun Nov 09 17:04:14 2014 +0100 (2014-11-09)
changeset 58957 c9e744ea8a38
parent 58871 c399ae4b836f
child 60770 240563fbf41d
permissions -rw-r--r--
proper context for match_tac etc.;
     1 (*  Title:      ZF/Sum.thy
     2     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     3     Copyright   1993  University of Cambridge
     4 *)
     5 
     6 section{*Disjoint Sums*}
     7 
     8 theory Sum imports Bool equalities begin
     9 
    10 text{*And the "Part" primitive for simultaneous recursive type definitions*}
    11 
    12 definition sum :: "[i,i]=>i" (infixr "+" 65) where
    13      "A+B == {0}*A \<union> {1}*B"
    14 
    15 definition Inl :: "i=>i" where
    16      "Inl(a) == <0,a>"
    17 
    18 definition Inr :: "i=>i" where
    19      "Inr(b) == <1,b>"
    20 
    21 definition "case" :: "[i=>i, i=>i, i]=>i" where
    22      "case(c,d) == (%<y,z>. cond(y, d(z), c(z)))"
    23 
    24   (*operator for selecting out the various summands*)
    25 definition Part :: "[i,i=>i] => i" where
    26      "Part(A,h) == {x \<in> A. \<exists>z. x = h(z)}"
    27 
    28 subsection{*Rules for the @{term Part} Primitive*}
    29 
    30 lemma Part_iff:
    31     "a \<in> Part(A,h) \<longleftrightarrow> a \<in> A & (\<exists>y. a=h(y))"
    32 apply (unfold Part_def)
    33 apply (rule separation)
    34 done
    35 
    36 lemma Part_eqI [intro]:
    37     "[| a \<in> A;  a=h(b) |] ==> a \<in> Part(A,h)"
    38 by (unfold Part_def, blast)
    39 
    40 lemmas PartI = refl [THEN [2] Part_eqI]
    41 
    42 lemma PartE [elim!]:
    43     "[| a \<in> Part(A,h);  !!z. [| a \<in> A;  a=h(z) |] ==> P
    44      |] ==> P"
    45 apply (unfold Part_def, blast)
    46 done
    47 
    48 lemma Part_subset: "Part(A,h) \<subseteq> A"
    49 apply (unfold Part_def)
    50 apply (rule Collect_subset)
    51 done
    52 
    53 
    54 subsection{*Rules for Disjoint Sums*}
    55 
    56 lemmas sum_defs = sum_def Inl_def Inr_def case_def
    57 
    58 lemma Sigma_bool: "Sigma(bool,C) = C(0) + C(1)"
    59 by (unfold bool_def sum_def, blast)
    60 
    61 (** Introduction rules for the injections **)
    62 
    63 lemma InlI [intro!,simp,TC]: "a \<in> A ==> Inl(a) \<in> A+B"
    64 by (unfold sum_defs, blast)
    65 
    66 lemma InrI [intro!,simp,TC]: "b \<in> B ==> Inr(b) \<in> A+B"
    67 by (unfold sum_defs, blast)
    68 
    69 (** Elimination rules **)
    70 
    71 lemma sumE [elim!]:
    72     "[| u \<in> A+B;
    73         !!x. [| x \<in> A;  u=Inl(x) |] ==> P;
    74         !!y. [| y \<in> B;  u=Inr(y) |] ==> P
    75      |] ==> P"
    76 by (unfold sum_defs, blast)
    77 
    78 (** Injection and freeness equivalences, for rewriting **)
    79 
    80 lemma Inl_iff [iff]: "Inl(a)=Inl(b) \<longleftrightarrow> a=b"
    81 by (simp add: sum_defs)
    82 
    83 lemma Inr_iff [iff]: "Inr(a)=Inr(b) \<longleftrightarrow> a=b"
    84 by (simp add: sum_defs)
    85 
    86 lemma Inl_Inr_iff [simp]: "Inl(a)=Inr(b) \<longleftrightarrow> False"
    87 by (simp add: sum_defs)
    88 
    89 lemma Inr_Inl_iff [simp]: "Inr(b)=Inl(a) \<longleftrightarrow> False"
    90 by (simp add: sum_defs)
    91 
    92 lemma sum_empty [simp]: "0+0 = 0"
    93 by (simp add: sum_defs)
    94 
    95 (*Injection and freeness rules*)
    96 
    97 lemmas Inl_inject = Inl_iff [THEN iffD1]
    98 lemmas Inr_inject = Inr_iff [THEN iffD1]
    99 lemmas Inl_neq_Inr = Inl_Inr_iff [THEN iffD1, THEN FalseE, elim!]
   100 lemmas Inr_neq_Inl = Inr_Inl_iff [THEN iffD1, THEN FalseE, elim!]
   101 
   102 
   103 lemma InlD: "Inl(a): A+B ==> a \<in> A"
   104 by blast
   105 
   106 lemma InrD: "Inr(b): A+B ==> b \<in> B"
   107 by blast
   108 
   109 lemma sum_iff: "u \<in> A+B \<longleftrightarrow> (\<exists>x. x \<in> A & u=Inl(x)) | (\<exists>y. y \<in> B & u=Inr(y))"
   110 by blast
   111 
   112 lemma Inl_in_sum_iff [simp]: "(Inl(x) \<in> A+B) \<longleftrightarrow> (x \<in> A)"
   113 by auto
   114 
   115 lemma Inr_in_sum_iff [simp]: "(Inr(y) \<in> A+B) \<longleftrightarrow> (y \<in> B)"
   116 by auto
   117 
   118 lemma sum_subset_iff: "A+B \<subseteq> C+D \<longleftrightarrow> A<=C & B<=D"
   119 by blast
   120 
   121 lemma sum_equal_iff: "A+B = C+D \<longleftrightarrow> A=C & B=D"
   122 by (simp add: extension sum_subset_iff, blast)
   123 
   124 lemma sum_eq_2_times: "A+A = 2*A"
   125 by (simp add: sum_def, blast)
   126 
   127 
   128 subsection{*The Eliminator: @{term case}*}
   129 
   130 lemma case_Inl [simp]: "case(c, d, Inl(a)) = c(a)"
   131 by (simp add: sum_defs)
   132 
   133 lemma case_Inr [simp]: "case(c, d, Inr(b)) = d(b)"
   134 by (simp add: sum_defs)
   135 
   136 lemma case_type [TC]:
   137     "[| u \<in> A+B;
   138         !!x. x \<in> A ==> c(x): C(Inl(x));
   139         !!y. y \<in> B ==> d(y): C(Inr(y))
   140      |] ==> case(c,d,u) \<in> C(u)"
   141 by auto
   142 
   143 lemma expand_case: "u \<in> A+B ==>
   144         R(case(c,d,u)) \<longleftrightarrow>
   145         ((\<forall>x\<in>A. u = Inl(x) \<longrightarrow> R(c(x))) &
   146         (\<forall>y\<in>B. u = Inr(y) \<longrightarrow> R(d(y))))"
   147 by auto
   148 
   149 lemma case_cong:
   150   "[| z \<in> A+B;
   151       !!x. x \<in> A ==> c(x)=c'(x);
   152       !!y. y \<in> B ==> d(y)=d'(y)
   153    |] ==> case(c,d,z) = case(c',d',z)"
   154 by auto
   155 
   156 lemma case_case: "z \<in> A+B ==>
   157         case(c, d, case(%x. Inl(c'(x)), %y. Inr(d'(y)), z)) =
   158         case(%x. c(c'(x)), %y. d(d'(y)), z)"
   159 by auto
   160 
   161 
   162 subsection{*More Rules for @{term "Part(A,h)"}*}
   163 
   164 lemma Part_mono: "A<=B ==> Part(A,h)<=Part(B,h)"
   165 by blast
   166 
   167 lemma Part_Collect: "Part(Collect(A,P), h) = Collect(Part(A,h), P)"
   168 by blast
   169 
   170 lemmas Part_CollectE =
   171      Part_Collect [THEN equalityD1, THEN subsetD, THEN CollectE]
   172 
   173 lemma Part_Inl: "Part(A+B,Inl) = {Inl(x). x \<in> A}"
   174 by blast
   175 
   176 lemma Part_Inr: "Part(A+B,Inr) = {Inr(y). y \<in> B}"
   177 by blast
   178 
   179 lemma PartD1: "a \<in> Part(A,h) ==> a \<in> A"
   180 by (simp add: Part_def)
   181 
   182 lemma Part_id: "Part(A,%x. x) = A"
   183 by blast
   184 
   185 lemma Part_Inr2: "Part(A+B, %x. Inr(h(x))) = {Inr(y). y \<in> Part(B,h)}"
   186 by blast
   187 
   188 lemma Part_sum_equality: "C \<subseteq> A+B ==> Part(C,Inl) \<union> Part(C,Inr) = C"
   189 by blast
   190 
   191 end