src/Doc/Tutorial/Types/Typedefs.thy
changeset 49812 e3945ddcb9aa
parent 48994 c84278efa9d5
child 49834 b27bbb021df1
equal deleted inserted replaced
49811:3fc6b3289c31 49812:e3945ddcb9aa
    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}.