src/ZF/Sum.thy
 author paulson Tue Mar 06 16:06:52 2012 +0000 (2012-03-06 ago) changeset 46821 ff6b0c1087f2 parent 46820 c656222c4dc1 child 46953 2b6e55924af3 permissions -rw-r--r--
Using mathematical notation for <-> and cardinal arithmetic
1 (*  Title:      ZF/Sum.thy
2     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
3     Copyright   1993  University of Cambridge
4 *)
8 theory Sum imports Bool equalities begin
10 text{*And the "Part" primitive for simultaneous recursive type definitions*}
12 definition sum :: "[i,i]=>i" (infixr "+" 65) where
13      "A+B == {0}*A \<union> {1}*B"
15 definition Inl :: "i=>i" where
16      "Inl(a) == <0,a>"
18 definition Inr :: "i=>i" where
19      "Inr(b) == <1,b>"
21 definition "case" :: "[i=>i, i=>i, i]=>i" where
22      "case(c,d) == (%<y,z>. cond(y, d(z), c(z)))"
24   (*operator for selecting out the various summands*)
25 definition Part :: "[i,i=>i] => i" where
26      "Part(A,h) == {x: A. \<exists>z. x = h(z)}"
28 subsection{*Rules for the @{term Part} Primitive*}
30 lemma Part_iff:
31     "a \<in> Part(A,h) \<longleftrightarrow> a:A & (\<exists>y. a=h(y))"
32 apply (unfold Part_def)
33 apply (rule separation)
34 done
36 lemma Part_eqI [intro]:
37     "[| a \<in> A;  a=h(b) |] ==> a \<in> Part(A,h)"
38 by (unfold Part_def, blast)
40 lemmas PartI = refl [THEN [2] Part_eqI]
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
48 lemma Part_subset: "Part(A,h) \<subseteq> A"
49 apply (unfold Part_def)
50 apply (rule Collect_subset)
51 done
54 subsection{*Rules for Disjoint Sums*}
56 lemmas sum_defs = sum_def Inl_def Inr_def case_def
58 lemma Sigma_bool: "Sigma(bool,C) = C(0) + C(1)"
59 by (unfold bool_def sum_def, blast)
61 (** Introduction rules for the injections **)
63 lemma InlI [intro!,simp,TC]: "a \<in> A ==> Inl(a) \<in> A+B"
64 by (unfold sum_defs, blast)
66 lemma InrI [intro!,simp,TC]: "b \<in> B ==> Inr(b) \<in> A+B"
67 by (unfold sum_defs, blast)
69 (** Elimination rules **)
71 lemma sumE [elim!]:
72     "[| u: A+B;
73         !!x. [| x:A;  u=Inl(x) |] ==> P;
74         !!y. [| y:B;  u=Inr(y) |] ==> P
75      |] ==> P"
76 by (unfold sum_defs, blast)
78 (** Injection and freeness equivalences, for rewriting **)
80 lemma Inl_iff [iff]: "Inl(a)=Inl(b) \<longleftrightarrow> a=b"
83 lemma Inr_iff [iff]: "Inr(a)=Inr(b) \<longleftrightarrow> a=b"
86 lemma Inl_Inr_iff [simp]: "Inl(a)=Inr(b) \<longleftrightarrow> False"
89 lemma Inr_Inl_iff [simp]: "Inr(b)=Inl(a) \<longleftrightarrow> False"
92 lemma sum_empty [simp]: "0+0 = 0"
95 (*Injection and freeness rules*)
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!]
103 lemma InlD: "Inl(a): A+B ==> a: A"
104 by blast
106 lemma InrD: "Inr(b): A+B ==> b: B"
107 by blast
109 lemma sum_iff: "u: A+B \<longleftrightarrow> (\<exists>x. x:A & u=Inl(x)) | (\<exists>y. y:B & u=Inr(y))"
110 by blast
112 lemma Inl_in_sum_iff [simp]: "(Inl(x) \<in> A+B) \<longleftrightarrow> (x \<in> A)";
113 by auto
115 lemma Inr_in_sum_iff [simp]: "(Inr(y) \<in> A+B) \<longleftrightarrow> (y \<in> B)";
116 by auto
118 lemma sum_subset_iff: "A+B \<subseteq> C+D \<longleftrightarrow> A<=C & B<=D"
119 by blast
121 lemma sum_equal_iff: "A+B = C+D \<longleftrightarrow> A=C & B=D"
122 by (simp add: extension sum_subset_iff, blast)
124 lemma sum_eq_2_times: "A+A = 2*A"
125 by (simp add: sum_def, blast)
128 subsection{*The Eliminator: @{term case}*}
130 lemma case_Inl [simp]: "case(c, d, Inl(a)) = c(a)"
133 lemma case_Inr [simp]: "case(c, d, Inr(b)) = d(b)"
136 lemma case_type [TC]:
137     "[| u: A+B;
138         !!x. x: A ==> c(x): C(Inl(x));
139         !!y. y: B ==> d(y): C(Inr(y))
140      |] ==> case(c,d,u) \<in> C(u)"
141 by auto
143 lemma expand_case: "u: 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
149 lemma case_cong:
150   "[| z: A+B;
151       !!x. x:A ==> c(x)=c'(x);
152       !!y. y:B ==> d(y)=d'(y)
153    |] ==> case(c,d,z) = case(c',d',z)"
154 by auto
156 lemma case_case: "z: 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
162 subsection{*More Rules for @{term "Part(A,h)"}*}
164 lemma Part_mono: "A<=B ==> Part(A,h)<=Part(B,h)"
165 by blast
167 lemma Part_Collect: "Part(Collect(A,P), h) = Collect(Part(A,h), P)"
168 by blast
170 lemmas Part_CollectE =
171      Part_Collect [THEN equalityD1, THEN subsetD, THEN CollectE]
173 lemma Part_Inl: "Part(A+B,Inl) = {Inl(x). x: A}"
174 by blast
176 lemma Part_Inr: "Part(A+B,Inr) = {Inr(y). y: B}"
177 by blast
179 lemma PartD1: "a \<in> Part(A,h) ==> a \<in> A"