author  wenzelm 
Sat, 07 Apr 2012 16:41:59 +0200  
changeset 47389  e8552cba702d 
parent 45694  4a8743618257 
child 49834  b27bbb021df1 
permissions  rwrr 
10213  1 
(* Title: HOL/Sum_Type.thy 
2 
Author: Lawrence C Paulson, Cambridge University Computer Laboratory 

3 
Copyright 1992 University of Cambridge 

4 
*) 

5 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

6 
header{*The Disjoint Sum of Two Types*} 
10213  7 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

8 
theory Sum_Type 
33961  9 
imports Typedef Inductive Fun 
15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

10 
begin 
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

11 

33962  12 
subsection {* Construction of the sum type and its basic abstract operations *} 
10213  13 

33962  14 
definition Inl_Rep :: "'a \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> bool \<Rightarrow> bool" where 
15 
"Inl_Rep a x y p \<longleftrightarrow> x = a \<and> p" 

10213  16 

33962  17 
definition Inr_Rep :: "'b \<Rightarrow> 'a \<Rightarrow> 'b \<Rightarrow> bool \<Rightarrow> bool" where 
18 
"Inr_Rep b x y p \<longleftrightarrow> y = b \<and> \<not> p" 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

19 

45694
4a8743618257
prefer typedef without extra definition and alternative name;
wenzelm
parents:
45204
diff
changeset

20 
definition "sum = {f. (\<exists>a. f = Inl_Rep (a::'a)) \<or> (\<exists>b. f = Inr_Rep (b::'b))}" 
4a8743618257
prefer typedef without extra definition and alternative name;
wenzelm
parents:
45204
diff
changeset

21 

4a8743618257
prefer typedef without extra definition and alternative name;
wenzelm
parents:
45204
diff
changeset

22 
typedef (open) ('a, 'b) sum (infixr "+" 10) = "sum :: ('a => 'b => bool => bool) set" 
4a8743618257
prefer typedef without extra definition and alternative name;
wenzelm
parents:
45204
diff
changeset

23 
unfolding sum_def by auto 
10213  24 

37388  25 
lemma Inl_RepI: "Inl_Rep a \<in> sum" 
26 
by (auto simp add: sum_def) 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

27 

37388  28 
lemma Inr_RepI: "Inr_Rep b \<in> sum" 
29 
by (auto simp add: sum_def) 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

30 

37388  31 
lemma inj_on_Abs_sum: "A \<subseteq> sum \<Longrightarrow> inj_on Abs_sum A" 
32 
by (rule inj_on_inverseI, rule Abs_sum_inverse) auto 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

33 

33962  34 
lemma Inl_Rep_inject: "inj_on Inl_Rep A" 
35 
proof (rule inj_onI) 

36 
show "\<And>a c. Inl_Rep a = Inl_Rep c \<Longrightarrow> a = c" 

39302
d7728f65b353
renamed lemmas: ext_iff > fun_eq_iff, set_ext_iff > set_eq_iff, set_ext > set_eqI
nipkow
parents:
39198
diff
changeset

37 
by (auto simp add: Inl_Rep_def fun_eq_iff) 
33962  38 
qed 
15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

39 

33962  40 
lemma Inr_Rep_inject: "inj_on Inr_Rep A" 
41 
proof (rule inj_onI) 

42 
show "\<And>b d. Inr_Rep b = Inr_Rep d \<Longrightarrow> b = d" 

39302
d7728f65b353
renamed lemmas: ext_iff > fun_eq_iff, set_ext_iff > set_eq_iff, set_ext > set_eqI
nipkow
parents:
39198
diff
changeset

43 
by (auto simp add: Inr_Rep_def fun_eq_iff) 
33962  44 
qed 
15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

45 

33962  46 
lemma Inl_Rep_not_Inr_Rep: "Inl_Rep a \<noteq> Inr_Rep b" 
39302
d7728f65b353
renamed lemmas: ext_iff > fun_eq_iff, set_ext_iff > set_eq_iff, set_ext > set_eqI
nipkow
parents:
39198
diff
changeset

47 
by (auto simp add: Inl_Rep_def Inr_Rep_def fun_eq_iff) 
15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

48 

33962  49 
definition Inl :: "'a \<Rightarrow> 'a + 'b" where 
37388  50 
"Inl = Abs_sum \<circ> Inl_Rep" 
15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

51 

33962  52 
definition Inr :: "'b \<Rightarrow> 'a + 'b" where 
37388  53 
"Inr = Abs_sum \<circ> Inr_Rep" 
15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

54 

29025
8c8859c0d734
move lemmas from Numeral_Type.thy to other theories
huffman
parents:
28524
diff
changeset

55 
lemma inj_Inl [simp]: "inj_on Inl A" 
37388  56 
by (auto simp add: Inl_def intro!: comp_inj_on Inl_Rep_inject inj_on_Abs_sum Inl_RepI) 
29025
8c8859c0d734
move lemmas from Numeral_Type.thy to other theories
huffman
parents:
28524
diff
changeset

57 

33962  58 
lemma Inl_inject: "Inl x = Inl y \<Longrightarrow> x = y" 
59 
using inj_Inl by (rule injD) 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

60 

29025
8c8859c0d734
move lemmas from Numeral_Type.thy to other theories
huffman
parents:
28524
diff
changeset

61 
lemma inj_Inr [simp]: "inj_on Inr A" 
37388  62 
by (auto simp add: Inr_def intro!: comp_inj_on Inr_Rep_inject inj_on_Abs_sum Inr_RepI) 
15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

63 

33962  64 
lemma Inr_inject: "Inr x = Inr y \<Longrightarrow> x = y" 
65 
using inj_Inr by (rule injD) 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

66 

33962  67 
lemma Inl_not_Inr: "Inl a \<noteq> Inr b" 
68 
proof  

37388  69 
from Inl_RepI [of a] Inr_RepI [of b] have "{Inl_Rep a, Inr_Rep b} \<subseteq> sum" by auto 
70 
with inj_on_Abs_sum have "inj_on Abs_sum {Inl_Rep a, Inr_Rep b}" . 

71 
with Inl_Rep_not_Inr_Rep [of a b] inj_on_contraD have "Abs_sum (Inl_Rep a) \<noteq> Abs_sum (Inr_Rep b)" by auto 

33962  72 
then show ?thesis by (simp add: Inl_def Inr_def) 
73 
qed 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

74 

33962  75 
lemma Inr_not_Inl: "Inr b \<noteq> Inl a" 
76 
using Inl_not_Inr by (rule not_sym) 

15391
797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

77 

797ed46d724b
converted Sum_Type to newstyle theory: Inl, Inr are NO LONGER global
paulson
parents:
11609
diff
changeset

78 
lemma sumE: 
33962  79 
assumes "\<And>x::'a. s = Inl x \<Longrightarrow> P" 
80 
and "\<And>y::'b. s = Inr y \<Longrightarrow> P" 

81 
shows P 

37388  82 
proof (rule Abs_sum_cases [of s]) 
33962  83 
fix f 
37388  84 
assume "s = Abs_sum f" and "f \<in> sum" 
85 
with assms show P by (auto simp add: sum_def Inl_def Inr_def) 

33962  86 
qed 
33961  87 

37678
0040bafffdef
"prod" and "sum" replace "*" and "+" respectively
haftmann
parents:
37388
diff
changeset

88 
rep_datatype Inl Inr 
33961  89 
proof  
90 
fix P 

91 
fix s :: "'a + 'b" 

92 
assume x: "\<And>x\<Colon>'a. P (Inl x)" and y: "\<And>y\<Colon>'b. P (Inr y)" 

93 
then show "P s" by (auto intro: sumE [of s]) 

33962  94 
qed (auto dest: Inl_inject Inr_inject simp add: Inl_not_Inr) 
95 

40610  96 
primrec sum_map :: "('a \<Rightarrow> 'c) \<Rightarrow> ('b \<Rightarrow> 'd) \<Rightarrow> 'a + 'b \<Rightarrow> 'c + 'd" where 
97 
"sum_map f1 f2 (Inl a) = Inl (f1 a)" 

98 
 "sum_map f1 f2 (Inr a) = Inr (f2 a)" 

99 

41505
6d19301074cf
"enriched_type" replaces less specific "type_lifting"
haftmann
parents:
41372
diff
changeset

100 
enriched_type sum_map: sum_map proof  
41372  101 
fix f g h i 
102 
show "sum_map f g \<circ> sum_map h i = sum_map (f \<circ> h) (g \<circ> i)" 

103 
proof 

104 
fix s 

105 
show "(sum_map f g \<circ> sum_map h i) s = sum_map (f \<circ> h) (g \<circ> i) s" 

106 
by (cases s) simp_all 

107 
qed 

40610  108 
next 
109 
fix s 

41372  110 
show "sum_map id id = id" 
111 
proof 

112 
fix s 

113 
show "sum_map id id s = id s" 

114 
by (cases s) simp_all 

115 
qed 

40610  116 
qed 
117 

33961  118 

33962  119 
subsection {* Projections *} 
120 

121 
lemma sum_case_KK [simp]: "sum_case (\<lambda>x. a) (\<lambda>x. a) = (\<lambda>x. a)" 

33961  122 
by (rule ext) (simp split: sum.split) 
123 

33962  124 
lemma surjective_sum: "sum_case (\<lambda>x::'a. f (Inl x)) (\<lambda>y::'b. f (Inr y)) = f" 
125 
proof 

126 
fix s :: "'a + 'b" 

127 
show "(case s of Inl (x\<Colon>'a) \<Rightarrow> f (Inl x)  Inr (y\<Colon>'b) \<Rightarrow> f (Inr y)) = f s" 

128 
by (cases s) simp_all 

129 
qed 

33961  130 

33962  131 
lemma sum_case_inject: 
132 
assumes a: "sum_case f1 f2 = sum_case g1 g2" 

133 
assumes r: "f1 = g1 \<Longrightarrow> f2 = g2 \<Longrightarrow> P" 

134 
shows P 

135 
proof (rule r) 

136 
show "f1 = g1" proof 

137 
fix x :: 'a 

138 
from a have "sum_case f1 f2 (Inl x) = sum_case g1 g2 (Inl x)" by simp 

139 
then show "f1 x = g1 x" by simp 

140 
qed 

141 
show "f2 = g2" proof 

142 
fix y :: 'b 

143 
from a have "sum_case f1 f2 (Inr y) = sum_case g1 g2 (Inr y)" by simp 

144 
then show "f2 y = g2 y" by simp 

145 
qed 

146 
qed 

147 

148 
lemma sum_case_weak_cong: 

149 
"s = t \<Longrightarrow> sum_case f g s = sum_case f g t" 

33961  150 
 {* Prevents simplification of @{text f} and @{text g}: much faster. *} 
151 
by simp 

152 

33962  153 
primrec Projl :: "'a + 'b \<Rightarrow> 'a" where 
154 
Projl_Inl: "Projl (Inl x) = x" 

155 

156 
primrec Projr :: "'a + 'b \<Rightarrow> 'b" where 

157 
Projr_Inr: "Projr (Inr x) = x" 

158 

159 
primrec Suml :: "('a \<Rightarrow> 'c) \<Rightarrow> 'a + 'b \<Rightarrow> 'c" where 

160 
"Suml f (Inl x) = f x" 

161 

162 
primrec Sumr :: "('b \<Rightarrow> 'c) \<Rightarrow> 'a + 'b \<Rightarrow> 'c" where 

163 
"Sumr f (Inr x) = f x" 

164 

165 
lemma Suml_inject: 

166 
assumes "Suml f = Suml g" shows "f = g" 

167 
proof 

168 
fix x :: 'a 

169 
let ?s = "Inl x \<Colon> 'a + 'b" 

170 
from assms have "Suml f ?s = Suml g ?s" by simp 

171 
then show "f x = g x" by simp 

33961  172 
qed 
173 

33962  174 
lemma Sumr_inject: 
175 
assumes "Sumr f = Sumr g" shows "f = g" 

176 
proof 

177 
fix x :: 'b 

178 
let ?s = "Inr x \<Colon> 'a + 'b" 

179 
from assms have "Sumr f ?s = Sumr g ?s" by simp 

180 
then show "f x = g x" by simp 

181 
qed 

33961  182 

33995  183 

33962  184 
subsection {* The Disjoint Sum of Sets *} 
33961  185 

33962  186 
definition Plus :: "'a set \<Rightarrow> 'b set \<Rightarrow> ('a + 'b) set" (infixr "<+>" 65) where 
187 
"A <+> B = Inl ` A \<union> Inr ` B" 

188 

40271  189 
hide_const (open) Plus "Valuable identifier" 
190 

33962  191 
lemma InlI [intro!]: "a \<in> A \<Longrightarrow> Inl a \<in> A <+> B" 
192 
by (simp add: Plus_def) 

33961  193 

33962  194 
lemma InrI [intro!]: "b \<in> B \<Longrightarrow> Inr b \<in> A <+> B" 
195 
by (simp add: Plus_def) 

33961  196 

33962  197 
text {* Exhaustion rule for sums, a degenerate form of induction *} 
198 

199 
lemma PlusE [elim!]: 

200 
"u \<in> A <+> B \<Longrightarrow> (\<And>x. x \<in> A \<Longrightarrow> u = Inl x \<Longrightarrow> P) \<Longrightarrow> (\<And>y. y \<in> B \<Longrightarrow> u = Inr y \<Longrightarrow> P) \<Longrightarrow> P" 

201 
by (auto simp add: Plus_def) 

33961  202 

33962  203 
lemma Plus_eq_empty_conv [simp]: "A <+> B = {} \<longleftrightarrow> A = {} \<and> B = {}" 
204 
by auto 

33961  205 

33962  206 
lemma UNIV_Plus_UNIV [simp]: "UNIV <+> UNIV = UNIV" 
39302
d7728f65b353
renamed lemmas: ext_iff > fun_eq_iff, set_ext_iff > set_eq_iff, set_ext > set_eqI
nipkow
parents:
39198
diff
changeset

207 
proof (rule set_eqI) 
33962  208 
fix u :: "'a + 'b" 
209 
show "u \<in> UNIV <+> UNIV \<longleftrightarrow> u \<in> UNIV" by (cases u) auto 

210 
qed 

33961  211 

36176
3fe7e97ccca8
replaced generic 'hide' command by more conventional 'hide_class', 'hide_type', 'hide_const', 'hide_fact'  frees some popular keywords;
wenzelm
parents:
33995
diff
changeset

212 
hide_const (open) Suml Sumr Projl Projr 
33961  213 

45204
5e4a1270c000
hide typedefgenerated constants Product_Type.prod and Sum_Type.sum
huffman
parents:
41505
diff
changeset

214 
hide_const (open) sum 
5e4a1270c000
hide typedefgenerated constants Product_Type.prod and Sum_Type.sum
huffman
parents:
41505
diff
changeset

215 

10213  216 
end 