67 |
67 |
68 Let us work a simple example, the definition of a three-element type. |
68 Let us work a simple example, the definition of a three-element type. |
69 It is easily represented by the first three natural numbers: |
69 It is easily represented by the first three natural numbers: |
70 *} |
70 *} |
71 |
71 |
72 typedef three = "{0::nat, 1, 2}" |
72 typedef (open) three = "{0::nat, 1, 2}" |
73 |
73 |
74 txt{*\noindent |
74 txt{*\noindent |
75 In order to enforce that the representing set on the right-hand side is |
75 In order to enforce that the representing set on the right-hand side is |
76 non-empty, this definition actually starts a proof to that effect: |
76 non-empty, this definition actually starts a proof to that effect: |
77 @{subgoals[display,indent=0]} |
77 @{subgoals[display,indent=0]} |
88 is expressed via a bijection between the \emph{type} @{typ three} and the |
88 is expressed via a bijection between the \emph{type} @{typ three} and the |
89 \emph{set} @{term"{0::nat,1,2}"}. To this end, the command declares the following |
89 \emph{set} @{term"{0::nat,1,2}"}. To this end, the command declares the following |
90 constants behind the scenes: |
90 constants behind the scenes: |
91 \begin{center} |
91 \begin{center} |
92 \begin{tabular}{rcl} |
92 \begin{tabular}{rcl} |
93 @{term three} &::& @{typ"nat set"} \\ |
|
94 @{term Rep_three} &::& @{typ"three \<Rightarrow> nat"}\\ |
93 @{term Rep_three} &::& @{typ"three \<Rightarrow> nat"}\\ |
95 @{term Abs_three} &::& @{typ"nat \<Rightarrow> three"} |
94 @{term Abs_three} &::& @{typ"nat \<Rightarrow> three"} |
96 \end{tabular} |
95 \end{tabular} |
97 \end{center} |
96 \end{center} |
98 where constant @{term three} is explicitly defined as the representing set: |
|
99 \begin{center} |
|
100 @{thm three_def}\hfill(@{thm[source]three_def}) |
|
101 \end{center} |
|
102 The situation is best summarized with the help of the following diagram, |
97 The situation is best summarized with the help of the following diagram, |
103 where squares denote types and the irregular region denotes a set: |
98 where squares denote types and the irregular region denotes a set: |
104 \begin{center} |
99 \begin{center} |
105 \includegraphics[scale=.8]{typedef} |
100 \includegraphics[scale=.8]{typedef} |
106 \end{center} |
101 \end{center} |
107 Finally, \isacommand{typedef} asserts that @{term Rep_three} is |
102 Finally, \isacommand{typedef} asserts that @{term Rep_three} is |
108 surjective on the subset @{term three} and @{term Abs_three} and @{term |
103 surjective on the subset and @{term Abs_three} and @{term |
109 Rep_three} are inverses of each other: |
104 Rep_three} are inverses of each other: |
110 \begin{center} |
105 \begin{center} |
111 \begin{tabular}{@ {}r@ {\qquad\qquad}l@ {}} |
106 \begin{tabular}{@ {}r@ {\qquad\qquad}l@ {}} |
112 @{thm Rep_three[no_vars]} & (@{thm[source]Rep_three}) \\ |
107 @{thm Rep_three[no_vars]} & (@{thm[source]Rep_three}) \\ |
113 @{thm Rep_three_inverse[no_vars]} & (@{thm[source]Rep_three_inverse}) \\ |
108 @{thm Rep_three_inverse[no_vars]} & (@{thm[source]Rep_three_inverse}) \\ |
151 express injectivity of @{term Rep_three} and @{term Abs_three}: |
146 express injectivity of @{term Rep_three} and @{term Abs_three}: |
152 \begin{center} |
147 \begin{center} |
153 \begin{tabular}{@ {}r@ {\qquad}l@ {}} |
148 \begin{tabular}{@ {}r@ {\qquad}l@ {}} |
154 @{thm Rep_three_inject[no_vars]} & (@{thm[source]Rep_three_inject}) \\ |
149 @{thm Rep_three_inject[no_vars]} & (@{thm[source]Rep_three_inject}) \\ |
155 \begin{tabular}{@ {}l@ {}} |
150 \begin{tabular}{@ {}l@ {}} |
156 @{text"\<lbrakk>x \<in> three; y \<in> three \<rbrakk>"} \\ |
151 @{text"\<lbrakk>x \<in> {0, 1, 2}; y \<in> {0, 1, 2} \<rbrakk>"} \\ |
157 @{text"\<Longrightarrow> (Abs_three x = Abs_three y) = (x = y)"} |
152 @{text"\<Longrightarrow> (Abs_three x = Abs_three y) = (x = y)"} |
158 \end{tabular} & (@{thm[source]Abs_three_inject}) \\ |
153 \end{tabular} & (@{thm[source]Abs_three_inject}) \\ |
159 \end{tabular} |
154 \end{tabular} |
160 \end{center} |
155 \end{center} |
161 The following ones allow to replace some @{text"x::three"} by |
156 The following ones allow to replace some @{text"x::three"} by |
166 @{thm Abs_three_cases[no_vars]} & (@{thm[source]Abs_three_cases}) \\ |
161 @{thm Abs_three_cases[no_vars]} & (@{thm[source]Abs_three_cases}) \\ |
167 @{thm Rep_three_induct[no_vars]} & (@{thm[source]Rep_three_induct}) \\ |
162 @{thm Rep_three_induct[no_vars]} & (@{thm[source]Rep_three_induct}) \\ |
168 @{thm Abs_three_induct[no_vars]} & (@{thm[source]Abs_three_induct}) \\ |
163 @{thm Abs_three_induct[no_vars]} & (@{thm[source]Abs_three_induct}) \\ |
169 \end{tabular} |
164 \end{tabular} |
170 \end{center} |
165 \end{center} |
171 These theorems are proved for any type definition, with @{term three} |
166 These theorems are proved for any type definition, with @{text three} |
172 replaced by the name of the type in question. |
167 replaced by the name of the type in question. |
173 |
168 |
174 Distinctness of @{term A}, @{term B} and @{term C} follows immediately |
169 Distinctness of @{term A}, @{term B} and @{term C} follows immediately |
175 if we expand their definitions and rewrite with the injectivity |
170 if we expand their definitions and rewrite with the injectivity |
176 of @{term Abs_three}: |
171 of @{term Abs_three}: |
177 *} |
172 *} |
178 |
173 |
179 lemma "A \<noteq> B \<and> B \<noteq> A \<and> A \<noteq> C \<and> C \<noteq> A \<and> B \<noteq> C \<and> C \<noteq> B" |
174 lemma "A \<noteq> B \<and> B \<noteq> A \<and> A \<noteq> C \<and> C \<noteq> A \<and> B \<noteq> C \<and> C \<noteq> B" |
180 by(simp add: Abs_three_inject A_def B_def C_def three_def) |
175 by(simp add: Abs_three_inject A_def B_def C_def) |
181 |
176 |
182 text{*\noindent |
177 text{*\noindent |
183 Of course we rely on the simplifier to solve goals like @{prop"(0::nat) \<noteq> 1"}. |
178 Of course we rely on the simplifier to solve goals like @{prop"(0::nat) \<noteq> 1"}. |
184 |
179 |
185 The fact that @{term A}, @{term B} and @{term C} exhaust type @{typ three} is |
180 The fact that @{term A}, @{term B} and @{term C} exhaust type @{typ three} is |
193 |
188 |
194 apply(induct_tac x) |
189 apply(induct_tac x) |
195 |
190 |
196 txt{* |
191 txt{* |
197 @{subgoals[display,indent=0]} |
192 @{subgoals[display,indent=0]} |
198 Simplification with @{thm[source]three_def} leads to the disjunction @{prop"y |
193 Simplification leads to the disjunction @{prop"y |
199 = 0 \<or> y = 1 \<or> y = (2::nat)"} which \isa{auto} separates into three |
194 = 0 \<or> y = 1 \<or> y = (2::nat)"} which \isa{auto} separates into three |
200 subgoals, each of which is easily solved by simplification: *} |
195 subgoals, each of which is easily solved by simplification: *} |
201 |
196 |
202 apply(auto simp add: three_def A_def B_def C_def) |
197 apply(auto simp add: A_def B_def C_def) |
203 done |
198 done |
204 |
199 |
205 text{*\noindent |
200 text{*\noindent |
206 This concludes the derivation of the characteristic theorems for |
201 This concludes the derivation of the characteristic theorems for |
207 type @{typ three}. |
202 type @{typ three}. |