13999
|
1 |
%
|
|
2 |
\begin{isabellebody}%
|
|
3 |
\def\isabellecontext{Induction}%
|
17125
|
4 |
%
|
|
5 |
\isadelimtheory
|
|
6 |
%
|
|
7 |
\endisadelimtheory
|
|
8 |
%
|
|
9 |
\isatagtheory
|
17175
|
10 |
\isamarkupfalse%
|
17125
|
11 |
%
|
|
12 |
\endisatagtheory
|
|
13 |
{\isafoldtheory}%
|
|
14 |
%
|
|
15 |
\isadelimtheory
|
|
16 |
%
|
|
17 |
\endisadelimtheory
|
13999
|
18 |
%
|
|
19 |
\isamarkupsection{Case distinction and induction \label{sec:Induct}%
|
|
20 |
}
|
|
21 |
\isamarkuptrue%
|
|
22 |
%
|
|
23 |
\begin{isamarkuptext}%
|
|
24 |
Computer science applications abound with inductively defined
|
|
25 |
structures, which is why we treat them in more detail. HOL already
|
|
26 |
comes with a datatype of lists with the two constructors \isa{Nil}
|
|
27 |
and \isa{Cons}. \isa{Nil} is written \isa{{\isacharbrackleft}{\isacharbrackright}} and \isa{Cons\ x\ xs} is written \isa{x\ {\isacharhash}\ xs}.%
|
|
28 |
\end{isamarkuptext}%
|
|
29 |
\isamarkuptrue%
|
|
30 |
%
|
|
31 |
\isamarkupsubsection{Case distinction\label{sec:CaseDistinction}%
|
|
32 |
}
|
|
33 |
\isamarkuptrue%
|
|
34 |
%
|
|
35 |
\begin{isamarkuptext}%
|
|
36 |
We have already met the \isa{cases} method for performing
|
|
37 |
binary case splits. Here is another example:%
|
|
38 |
\end{isamarkuptext}%
|
17175
|
39 |
\isamarkuptrue%
|
|
40 |
\isacommand{lemma}\isamarkupfalse%
|
|
41 |
\ {\isachardoublequoteopen}{\isasymnot}\ A\ {\isasymor}\ A{\isachardoublequoteclose}\isanewline
|
17125
|
42 |
%
|
|
43 |
\isadelimproof
|
|
44 |
%
|
|
45 |
\endisadelimproof
|
|
46 |
%
|
|
47 |
\isatagproof
|
17175
|
48 |
\isacommand{proof}\isamarkupfalse%
|
|
49 |
\ cases\isanewline
|
|
50 |
\ \ \isacommand{assume}\isamarkupfalse%
|
|
51 |
\ {\isachardoublequoteopen}A{\isachardoublequoteclose}\ \isacommand{thus}\isamarkupfalse%
|
|
52 |
\ {\isacharquery}thesis\ \isacommand{{\isachardot}{\isachardot}}\isamarkupfalse%
|
|
53 |
\isanewline
|
|
54 |
\isacommand{next}\isamarkupfalse%
|
|
55 |
\isanewline
|
|
56 |
\ \ \isacommand{assume}\isamarkupfalse%
|
|
57 |
\ {\isachardoublequoteopen}{\isasymnot}\ A{\isachardoublequoteclose}\ \isacommand{thus}\isamarkupfalse%
|
|
58 |
\ {\isacharquery}thesis\ \isacommand{{\isachardot}{\isachardot}}\isamarkupfalse%
|
|
59 |
\isanewline
|
|
60 |
\isacommand{qed}\isamarkupfalse%
|
|
61 |
%
|
17125
|
62 |
\endisatagproof
|
|
63 |
{\isafoldproof}%
|
|
64 |
%
|
|
65 |
\isadelimproof
|
|
66 |
%
|
|
67 |
\endisadelimproof
|
13999
|
68 |
%
|
|
69 |
\begin{isamarkuptext}%
|
|
70 |
\noindent The two cases must come in this order because \isa{cases} merely abbreviates \isa{{\isacharparenleft}rule\ case{\isacharunderscore}split{\isacharunderscore}thm{\isacharparenright}} where
|
|
71 |
\isa{case{\isacharunderscore}split{\isacharunderscore}thm} is \isa{{\isasymlbrakk}{\isacharquery}P\ {\isasymLongrightarrow}\ {\isacharquery}Q{\isacharsemicolon}\ {\isasymnot}\ {\isacharquery}P\ {\isasymLongrightarrow}\ {\isacharquery}Q{\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isacharquery}Q}. If we reverse
|
|
72 |
the order of the two cases in the proof, the first case would prove
|
|
73 |
\isa{{\isasymnot}\ A\ {\isasymLongrightarrow}\ {\isasymnot}\ A\ {\isasymor}\ A} which would solve the first premise of
|
|
74 |
\isa{case{\isacharunderscore}split{\isacharunderscore}thm}, instantiating \isa{{\isacharquery}P} with \isa{{\isasymnot}\ A}, thus making the second premise \isa{{\isasymnot}\ {\isasymnot}\ A\ {\isasymLongrightarrow}\ {\isasymnot}\ A\ {\isasymor}\ A}.
|
|
75 |
Therefore the order of subgoals is not always completely arbitrary.
|
|
76 |
|
|
77 |
The above proof is appropriate if \isa{A} is textually small.
|
|
78 |
However, if \isa{A} is large, we do not want to repeat it. This can
|
|
79 |
be avoided by the following idiom%
|
|
80 |
\end{isamarkuptext}%
|
17175
|
81 |
\isamarkuptrue%
|
|
82 |
\isacommand{lemma}\isamarkupfalse%
|
|
83 |
\ {\isachardoublequoteopen}{\isasymnot}\ A\ {\isasymor}\ A{\isachardoublequoteclose}\isanewline
|
17125
|
84 |
%
|
|
85 |
\isadelimproof
|
|
86 |
%
|
|
87 |
\endisadelimproof
|
|
88 |
%
|
|
89 |
\isatagproof
|
17175
|
90 |
\isacommand{proof}\isamarkupfalse%
|
|
91 |
\ {\isacharparenleft}cases\ {\isachardoublequoteopen}A{\isachardoublequoteclose}{\isacharparenright}\isanewline
|
|
92 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
93 |
\ True\ \isacommand{thus}\isamarkupfalse%
|
|
94 |
\ {\isacharquery}thesis\ \isacommand{{\isachardot}{\isachardot}}\isamarkupfalse%
|
|
95 |
\isanewline
|
|
96 |
\isacommand{next}\isamarkupfalse%
|
|
97 |
\isanewline
|
|
98 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
99 |
\ False\ \isacommand{thus}\isamarkupfalse%
|
|
100 |
\ {\isacharquery}thesis\ \isacommand{{\isachardot}{\isachardot}}\isamarkupfalse%
|
|
101 |
\isanewline
|
|
102 |
\isacommand{qed}\isamarkupfalse%
|
|
103 |
%
|
17125
|
104 |
\endisatagproof
|
|
105 |
{\isafoldproof}%
|
|
106 |
%
|
|
107 |
\isadelimproof
|
|
108 |
%
|
|
109 |
\endisadelimproof
|
13999
|
110 |
%
|
|
111 |
\begin{isamarkuptext}%
|
|
112 |
\noindent which is like the previous proof but instantiates
|
|
113 |
\isa{{\isacharquery}P} right away with \isa{A}. Thus we could prove the two
|
|
114 |
cases in any order. The phrase `\isakeyword{case}~\isa{True}'
|
|
115 |
abbreviates `\isakeyword{assume}~\isa{True{\isacharcolon}\ A}' and analogously for
|
|
116 |
\isa{False} and \isa{{\isasymnot}\ A}.
|
|
117 |
|
|
118 |
The same game can be played with other datatypes, for example lists,
|
|
119 |
where \isa{tl} is the tail of a list, and \isa{length} returns a
|
|
120 |
natural number (remember: $0-1=0$):%
|
|
121 |
\end{isamarkuptext}%
|
17175
|
122 |
\isamarkuptrue%
|
13999
|
123 |
\isamarkupfalse%
|
17175
|
124 |
\isacommand{lemma}\isamarkupfalse%
|
|
125 |
\ {\isachardoublequoteopen}length{\isacharparenleft}tl\ xs{\isacharparenright}\ {\isacharequal}\ length\ xs\ {\isacharminus}\ {\isadigit{1}}{\isachardoublequoteclose}\isanewline
|
17125
|
126 |
%
|
|
127 |
\isadelimproof
|
|
128 |
%
|
|
129 |
\endisadelimproof
|
|
130 |
%
|
|
131 |
\isatagproof
|
17175
|
132 |
\isacommand{proof}\isamarkupfalse%
|
|
133 |
\ {\isacharparenleft}cases\ xs{\isacharparenright}\isanewline
|
|
134 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
135 |
\ Nil\ \isacommand{thus}\isamarkupfalse%
|
|
136 |
\ {\isacharquery}thesis\ \isacommand{by}\isamarkupfalse%
|
|
137 |
\ simp\isanewline
|
|
138 |
\isacommand{next}\isamarkupfalse%
|
|
139 |
\isanewline
|
|
140 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
141 |
\ Cons\ \isacommand{thus}\isamarkupfalse%
|
|
142 |
\ {\isacharquery}thesis\ \isacommand{by}\isamarkupfalse%
|
|
143 |
\ simp\isanewline
|
|
144 |
\isacommand{qed}\isamarkupfalse%
|
|
145 |
%
|
17125
|
146 |
\endisatagproof
|
|
147 |
{\isafoldproof}%
|
|
148 |
%
|
|
149 |
\isadelimproof
|
|
150 |
%
|
|
151 |
\endisadelimproof
|
13999
|
152 |
%
|
|
153 |
\begin{isamarkuptext}%
|
|
154 |
\noindent Here `\isakeyword{case}~\isa{Nil}' abbreviates
|
|
155 |
`\isakeyword{assume}~\isa{Nil{\isacharcolon}}~\isa{xs\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}}' and
|
|
156 |
`\isakeyword{case}~\isa{Cons}'
|
|
157 |
abbreviates `\isakeyword{fix}~\isa{{\isacharquery}\ {\isacharquery}{\isacharquery}}
|
|
158 |
\isakeyword{assume}~\isa{Cons{\isacharcolon}}~\isa{xs\ {\isacharequal}\ {\isacharquery}\ {\isacharhash}\ {\isacharquery}{\isacharquery}}'
|
|
159 |
where \isa{{\isacharquery}} and \isa{{\isacharquery}{\isacharquery}}
|
|
160 |
stand for variable names that have been chosen by the system.
|
|
161 |
Therefore we cannot refer to them.
|
|
162 |
Luckily, this proof is simple enough we do not need to refer to them.
|
|
163 |
However, sometimes one may have to. Hence Isar offers a simple scheme for
|
|
164 |
naming those variables: replace the anonymous \isa{Cons} by
|
|
165 |
\isa{{\isacharparenleft}Cons\ y\ ys{\isacharparenright}}, which abbreviates `\isakeyword{fix}~\isa{y\ ys}
|
|
166 |
\isakeyword{assume}~\isa{Cons{\isacharcolon}}~\isa{xs\ {\isacharequal}\ y\ {\isacharhash}\ ys}'.
|
|
167 |
In each \isakeyword{case} the assumption can be
|
|
168 |
referred to inside the proof by the name of the constructor. In
|
|
169 |
Section~\ref{sec:full-Ind} below we will come across an example
|
|
170 |
of this.%
|
|
171 |
\end{isamarkuptext}%
|
|
172 |
\isamarkuptrue%
|
|
173 |
%
|
|
174 |
\isamarkupsubsection{Structural induction%
|
|
175 |
}
|
|
176 |
\isamarkuptrue%
|
|
177 |
%
|
|
178 |
\begin{isamarkuptext}%
|
|
179 |
We start with an inductive proof where both cases are proved automatically:%
|
|
180 |
\end{isamarkuptext}%
|
17175
|
181 |
\isamarkuptrue%
|
|
182 |
\isacommand{lemma}\isamarkupfalse%
|
|
183 |
\ {\isachardoublequoteopen}{\isadigit{2}}\ {\isacharasterisk}\ {\isacharparenleft}{\isasymSum}i{\isacharcolon}{\isacharcolon}nat{\isasymle}n{\isachardot}\ i{\isacharparenright}\ {\isacharequal}\ n{\isacharasterisk}{\isacharparenleft}n{\isacharplus}{\isadigit{1}}{\isacharparenright}{\isachardoublequoteclose}\isanewline
|
17125
|
184 |
%
|
|
185 |
\isadelimproof
|
|
186 |
%
|
|
187 |
\endisadelimproof
|
|
188 |
%
|
|
189 |
\isatagproof
|
17175
|
190 |
\isacommand{by}\isamarkupfalse%
|
|
191 |
\ {\isacharparenleft}induct\ n{\isacharcomma}\ simp{\isacharunderscore}all{\isacharparenright}%
|
17125
|
192 |
\endisatagproof
|
|
193 |
{\isafoldproof}%
|
|
194 |
%
|
|
195 |
\isadelimproof
|
|
196 |
%
|
|
197 |
\endisadelimproof
|
13999
|
198 |
%
|
|
199 |
\begin{isamarkuptext}%
|
15909
|
200 |
\noindent The constraint \isa{{\isacharcolon}{\isacharcolon}nat} is needed because all of
|
|
201 |
the operations involved are overloaded.
|
|
202 |
|
|
203 |
If we want to expose more of the structure of the
|
13999
|
204 |
proof, we can use pattern matching to avoid having to repeat the goal
|
|
205 |
statement:%
|
|
206 |
\end{isamarkuptext}%
|
17175
|
207 |
\isamarkuptrue%
|
|
208 |
\isacommand{lemma}\isamarkupfalse%
|
|
209 |
\ {\isachardoublequoteopen}{\isadigit{2}}\ {\isacharasterisk}\ {\isacharparenleft}{\isasymSum}i{\isacharcolon}{\isacharcolon}nat{\isasymle}n{\isachardot}\ i{\isacharparenright}\ {\isacharequal}\ n{\isacharasterisk}{\isacharparenleft}n{\isacharplus}{\isadigit{1}}{\isacharparenright}{\isachardoublequoteclose}\ {\isacharparenleft}\isakeyword{is}\ {\isachardoublequoteopen}{\isacharquery}P\ n{\isachardoublequoteclose}{\isacharparenright}\isanewline
|
17125
|
210 |
%
|
|
211 |
\isadelimproof
|
|
212 |
%
|
|
213 |
\endisadelimproof
|
|
214 |
%
|
|
215 |
\isatagproof
|
17175
|
216 |
\isacommand{proof}\isamarkupfalse%
|
|
217 |
\ {\isacharparenleft}induct\ n{\isacharparenright}\isanewline
|
|
218 |
\ \ \isacommand{show}\isamarkupfalse%
|
|
219 |
\ {\isachardoublequoteopen}{\isacharquery}P\ {\isadigit{0}}{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
220 |
\ simp\isanewline
|
|
221 |
\isacommand{next}\isamarkupfalse%
|
|
222 |
\isanewline
|
|
223 |
\ \ \isacommand{fix}\isamarkupfalse%
|
|
224 |
\ n\ \isacommand{assume}\isamarkupfalse%
|
|
225 |
\ {\isachardoublequoteopen}{\isacharquery}P\ n{\isachardoublequoteclose}\isanewline
|
|
226 |
\ \ \isacommand{thus}\isamarkupfalse%
|
|
227 |
\ {\isachardoublequoteopen}{\isacharquery}P{\isacharparenleft}Suc\ n{\isacharparenright}{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
228 |
\ simp\isanewline
|
|
229 |
\isacommand{qed}\isamarkupfalse%
|
|
230 |
%
|
17125
|
231 |
\endisatagproof
|
|
232 |
{\isafoldproof}%
|
|
233 |
%
|
|
234 |
\isadelimproof
|
|
235 |
%
|
|
236 |
\endisadelimproof
|
13999
|
237 |
%
|
|
238 |
\begin{isamarkuptext}%
|
|
239 |
\noindent We could refine this further to show more of the equational
|
|
240 |
proof. Instead we explore the same avenue as for case distinctions:
|
|
241 |
introducing context via the \isakeyword{case} command:%
|
|
242 |
\end{isamarkuptext}%
|
17175
|
243 |
\isamarkuptrue%
|
|
244 |
\isacommand{lemma}\isamarkupfalse%
|
|
245 |
\ {\isachardoublequoteopen}{\isadigit{2}}\ {\isacharasterisk}\ {\isacharparenleft}{\isasymSum}i{\isacharcolon}{\isacharcolon}nat\ {\isasymle}\ n{\isachardot}\ i{\isacharparenright}\ {\isacharequal}\ n{\isacharasterisk}{\isacharparenleft}n{\isacharplus}{\isadigit{1}}{\isacharparenright}{\isachardoublequoteclose}\isanewline
|
17125
|
246 |
%
|
|
247 |
\isadelimproof
|
|
248 |
%
|
|
249 |
\endisadelimproof
|
|
250 |
%
|
|
251 |
\isatagproof
|
17175
|
252 |
\isacommand{proof}\isamarkupfalse%
|
|
253 |
\ {\isacharparenleft}induct\ n{\isacharparenright}\isanewline
|
|
254 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
255 |
\ {\isadigit{0}}\ \isacommand{show}\isamarkupfalse%
|
|
256 |
\ {\isacharquery}case\ \isacommand{by}\isamarkupfalse%
|
|
257 |
\ simp\isanewline
|
|
258 |
\isacommand{next}\isamarkupfalse%
|
|
259 |
\isanewline
|
|
260 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
261 |
\ Suc\ \isacommand{thus}\isamarkupfalse%
|
|
262 |
\ {\isacharquery}case\ \isacommand{by}\isamarkupfalse%
|
|
263 |
\ simp\isanewline
|
|
264 |
\isacommand{qed}\isamarkupfalse%
|
|
265 |
%
|
17125
|
266 |
\endisatagproof
|
|
267 |
{\isafoldproof}%
|
|
268 |
%
|
|
269 |
\isadelimproof
|
|
270 |
%
|
|
271 |
\endisadelimproof
|
13999
|
272 |
%
|
|
273 |
\begin{isamarkuptext}%
|
|
274 |
\noindent The implicitly defined \isa{{\isacharquery}case} refers to the
|
|
275 |
corresponding case to be proved, i.e.\ \isa{{\isacharquery}P\ {\isadigit{0}}} in the first case and
|
|
276 |
\isa{{\isacharquery}P{\isacharparenleft}Suc\ n{\isacharparenright}} in the second case. Context \isakeyword{case}~\isa{{\isadigit{0}}} is
|
|
277 |
empty whereas \isakeyword{case}~\isa{Suc} assumes \isa{{\isacharquery}P\ n}. Again we
|
|
278 |
have the same problem as with case distinctions: we cannot refer to an anonymous \isa{n}
|
|
279 |
in the induction step because it has not been introduced via \isakeyword{fix}
|
|
280 |
(in contrast to the previous proof). The solution is the one outlined for
|
|
281 |
\isa{Cons} above: replace \isa{Suc} by \isa{{\isacharparenleft}Suc\ i{\isacharparenright}}:%
|
|
282 |
\end{isamarkuptext}%
|
17175
|
283 |
\isamarkuptrue%
|
|
284 |
\isacommand{lemma}\isamarkupfalse%
|
|
285 |
\ \isakeyword{fixes}\ n{\isacharcolon}{\isacharcolon}nat\ \isakeyword{shows}\ {\isachardoublequoteopen}n\ {\isacharless}\ n{\isacharasterisk}n\ {\isacharplus}\ {\isadigit{1}}{\isachardoublequoteclose}\isanewline
|
17125
|
286 |
%
|
|
287 |
\isadelimproof
|
|
288 |
%
|
|
289 |
\endisadelimproof
|
|
290 |
%
|
|
291 |
\isatagproof
|
17175
|
292 |
\isacommand{proof}\isamarkupfalse%
|
|
293 |
\ {\isacharparenleft}induct\ n{\isacharparenright}\isanewline
|
|
294 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
295 |
\ {\isadigit{0}}\ \isacommand{show}\isamarkupfalse%
|
|
296 |
\ {\isacharquery}case\ \isacommand{by}\isamarkupfalse%
|
|
297 |
\ simp\isanewline
|
|
298 |
\isacommand{next}\isamarkupfalse%
|
|
299 |
\isanewline
|
|
300 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
301 |
\ {\isacharparenleft}Suc\ i{\isacharparenright}\ \isacommand{thus}\isamarkupfalse%
|
|
302 |
\ {\isachardoublequoteopen}Suc\ i\ {\isacharless}\ Suc\ i\ {\isacharasterisk}\ Suc\ i\ {\isacharplus}\ {\isadigit{1}}{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
303 |
\ simp\isanewline
|
|
304 |
\isacommand{qed}\isamarkupfalse%
|
|
305 |
%
|
17125
|
306 |
\endisatagproof
|
|
307 |
{\isafoldproof}%
|
|
308 |
%
|
|
309 |
\isadelimproof
|
|
310 |
%
|
|
311 |
\endisadelimproof
|
13999
|
312 |
%
|
|
313 |
\begin{isamarkuptext}%
|
|
314 |
\noindent Of course we could again have written
|
|
315 |
\isakeyword{thus}~\isa{{\isacharquery}case} instead of giving the term explicitly
|
|
316 |
but we wanted to use \isa{i} somewhere.%
|
|
317 |
\end{isamarkuptext}%
|
|
318 |
\isamarkuptrue%
|
|
319 |
%
|
|
320 |
\isamarkupsubsection{Induction formulae involving \isa{{\isasymAnd}} or \isa{{\isasymLongrightarrow}}\label{sec:full-Ind}%
|
|
321 |
}
|
|
322 |
\isamarkuptrue%
|
|
323 |
%
|
|
324 |
\begin{isamarkuptext}%
|
|
325 |
Let us now consider the situation where the goal to be proved contains
|
|
326 |
\isa{{\isasymAnd}} or \isa{{\isasymLongrightarrow}}, say \isa{{\isasymAnd}x{\isachardot}\ P\ x\ {\isasymLongrightarrow}\ Q\ x} --- motivation and a
|
|
327 |
real example follow shortly. This means that in each case of the induction,
|
|
328 |
\isa{{\isacharquery}case} would be of the form \isa{{\isasymAnd}x{\isachardot}\ P{\isacharprime}\ x\ {\isasymLongrightarrow}\ Q{\isacharprime}\ x}. Thus the
|
|
329 |
first proof steps will be the canonical ones, fixing \isa{x} and assuming
|
|
330 |
\isa{P{\isacharprime}\ x}. To avoid this tedium, induction performs these steps
|
|
331 |
automatically: for example in case \isa{{\isacharparenleft}Suc\ n{\isacharparenright}}, \isa{{\isacharquery}case} is only
|
|
332 |
\isa{Q{\isacharprime}\ x} whereas the assumptions (named \isa{Suc}!) contain both the
|
|
333 |
usual induction hypothesis \emph{and} \isa{P{\isacharprime}\ x}.
|
|
334 |
It should be clear how this generalises to more complex formulae.
|
|
335 |
|
|
336 |
As an example we will now prove complete induction via
|
|
337 |
structural induction.%
|
|
338 |
\end{isamarkuptext}%
|
17175
|
339 |
\isamarkuptrue%
|
|
340 |
\isacommand{lemma}\isamarkupfalse%
|
|
341 |
\ \isakeyword{assumes}\ A{\isacharcolon}\ {\isachardoublequoteopen}{\isacharparenleft}{\isasymAnd}n{\isachardot}\ {\isacharparenleft}{\isasymAnd}m{\isachardot}\ m\ {\isacharless}\ n\ {\isasymLongrightarrow}\ P\ m{\isacharparenright}\ {\isasymLongrightarrow}\ P\ n{\isacharparenright}{\isachardoublequoteclose}\isanewline
|
|
342 |
\ \ \isakeyword{shows}\ {\isachardoublequoteopen}P{\isacharparenleft}n{\isacharcolon}{\isacharcolon}nat{\isacharparenright}{\isachardoublequoteclose}\isanewline
|
17125
|
343 |
%
|
|
344 |
\isadelimproof
|
|
345 |
%
|
|
346 |
\endisadelimproof
|
|
347 |
%
|
|
348 |
\isatagproof
|
17175
|
349 |
\isacommand{proof}\isamarkupfalse%
|
|
350 |
\ {\isacharparenleft}rule\ A{\isacharparenright}\isanewline
|
|
351 |
\ \ \isacommand{show}\isamarkupfalse%
|
|
352 |
\ {\isachardoublequoteopen}{\isasymAnd}m{\isachardot}\ m\ {\isacharless}\ n\ {\isasymLongrightarrow}\ P\ m{\isachardoublequoteclose}\isanewline
|
|
353 |
\ \ \isacommand{proof}\isamarkupfalse%
|
|
354 |
\ {\isacharparenleft}induct\ n{\isacharparenright}\isanewline
|
|
355 |
\ \ \ \ \isacommand{case}\isamarkupfalse%
|
|
356 |
\ {\isadigit{0}}\ \isacommand{thus}\isamarkupfalse%
|
|
357 |
\ {\isacharquery}case\ \isacommand{by}\isamarkupfalse%
|
|
358 |
\ simp\isanewline
|
|
359 |
\ \ \isacommand{next}\isamarkupfalse%
|
|
360 |
\isanewline
|
|
361 |
\ \ \ \ \isacommand{case}\isamarkupfalse%
|
|
362 |
\ {\isacharparenleft}Suc\ n{\isacharparenright}\ \ \ %
|
16459
|
363 |
\isamarkupcmt{\isakeyword{fix} \isa{m} \isakeyword{assume} \isa{Suc}: \isa{{\isachardoublequote}{\isacharquery}m\ {\isacharless}\ n\ {\isasymLongrightarrow}\ P\ {\isacharquery}m{\isachardoublequote}} \isa{{\isachardoublequote}m\ {\isacharless}\ Suc\ n{\isachardoublequote}}%
|
|
364 |
}
|
|
365 |
\isanewline
|
17175
|
366 |
\ \ \ \ \isacommand{show}\isamarkupfalse%
|
|
367 |
\ {\isacharquery}case\ \ \ \ %
|
16459
|
368 |
\isamarkupcmt{\isa{P\ m}%
|
|
369 |
}
|
|
370 |
\isanewline
|
17175
|
371 |
\ \ \ \ \isacommand{proof}\isamarkupfalse%
|
|
372 |
\ cases\isanewline
|
|
373 |
\ \ \ \ \ \ \isacommand{assume}\isamarkupfalse%
|
|
374 |
\ eq{\isacharcolon}\ {\isachardoublequoteopen}m\ {\isacharequal}\ n{\isachardoublequoteclose}\isanewline
|
|
375 |
\ \ \ \ \ \ \isacommand{from}\isamarkupfalse%
|
|
376 |
\ Suc\ \isakeyword{and}\ A\ \isacommand{have}\isamarkupfalse%
|
|
377 |
\ {\isachardoublequoteopen}P\ n{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
378 |
\ blast\isanewline
|
|
379 |
\ \ \ \ \ \ \isacommand{with}\isamarkupfalse%
|
|
380 |
\ eq\ \isacommand{show}\isamarkupfalse%
|
|
381 |
\ {\isachardoublequoteopen}P\ m{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
382 |
\ simp\isanewline
|
|
383 |
\ \ \ \ \isacommand{next}\isamarkupfalse%
|
|
384 |
\isanewline
|
|
385 |
\ \ \ \ \ \ \isacommand{assume}\isamarkupfalse%
|
|
386 |
\ {\isachardoublequoteopen}m\ {\isasymnoteq}\ n{\isachardoublequoteclose}\isanewline
|
|
387 |
\ \ \ \ \ \ \isacommand{with}\isamarkupfalse%
|
|
388 |
\ Suc\ \isacommand{have}\isamarkupfalse%
|
|
389 |
\ {\isachardoublequoteopen}m\ {\isacharless}\ n{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
390 |
\ arith\isanewline
|
|
391 |
\ \ \ \ \ \ \isacommand{thus}\isamarkupfalse%
|
|
392 |
\ {\isachardoublequoteopen}P\ m{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
393 |
{\isacharparenleft}rule\ Suc{\isacharparenright}\isanewline
|
|
394 |
\ \ \ \ \isacommand{qed}\isamarkupfalse%
|
|
395 |
\isanewline
|
|
396 |
\ \ \isacommand{qed}\isamarkupfalse%
|
|
397 |
\isanewline
|
|
398 |
\isacommand{qed}\isamarkupfalse%
|
|
399 |
%
|
17125
|
400 |
\endisatagproof
|
|
401 |
{\isafoldproof}%
|
|
402 |
%
|
|
403 |
\isadelimproof
|
|
404 |
%
|
|
405 |
\endisadelimproof
|
13999
|
406 |
%
|
|
407 |
\begin{isamarkuptext}%
|
|
408 |
\noindent Given the explanations above and the comments in the
|
|
409 |
proof text (only necessary for novices), the proof should be quite
|
|
410 |
readable.
|
|
411 |
|
|
412 |
The statement of the lemma is interesting because it deviates from the style in
|
|
413 |
the Tutorial~\cite{LNCS2283}, which suggests to introduce \isa{{\isasymforall}} or
|
|
414 |
\isa{{\isasymlongrightarrow}} into a theorem to strengthen it for induction. In Isar
|
|
415 |
proofs we can use \isa{{\isasymAnd}} and \isa{{\isasymLongrightarrow}} instead. This simplifies the
|
|
416 |
proof and means we do not have to convert between the two kinds of
|
|
417 |
connectives.
|
|
418 |
|
|
419 |
Note that in a nested induction over the same data type, the inner
|
|
420 |
case labels hide the outer ones of the same name. If you want to refer
|
|
421 |
to the outer ones inside, you need to name them on the outside, e.g.\
|
|
422 |
\isakeyword{note}~\isa{outer{\isacharunderscore}IH\ {\isacharequal}\ Suc}.%
|
|
423 |
\end{isamarkuptext}%
|
|
424 |
\isamarkuptrue%
|
|
425 |
%
|
|
426 |
\isamarkupsubsection{Rule induction%
|
|
427 |
}
|
|
428 |
\isamarkuptrue%
|
|
429 |
%
|
|
430 |
\begin{isamarkuptext}%
|
|
431 |
HOL also supports inductively defined sets. See \cite{LNCS2283}
|
|
432 |
for details. As an example we define our own version of the reflexive
|
|
433 |
transitive closure of a relation --- HOL provides a predefined one as well.%
|
|
434 |
\end{isamarkuptext}%
|
17175
|
435 |
\isamarkuptrue%
|
|
436 |
\isacommand{consts}\isamarkupfalse%
|
|
437 |
\ rtc\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}{\isacharparenleft}{\isacharprime}a\ {\isasymtimes}\ {\isacharprime}a{\isacharparenright}set\ {\isasymRightarrow}\ {\isacharparenleft}{\isacharprime}a\ {\isasymtimes}\ {\isacharprime}a{\isacharparenright}set{\isachardoublequoteclose}\ \ \ {\isacharparenleft}{\isachardoublequoteopen}{\isacharunderscore}{\isacharasterisk}{\isachardoublequoteclose}\ {\isacharbrackleft}{\isadigit{1}}{\isadigit{0}}{\isadigit{0}}{\isadigit{0}}{\isacharbrackright}\ {\isadigit{9}}{\isadigit{9}}{\isadigit{9}}{\isacharparenright}\isanewline
|
|
438 |
\isacommand{inductive}\isamarkupfalse%
|
|
439 |
\ {\isachardoublequoteopen}r{\isacharasterisk}{\isachardoublequoteclose}\isanewline
|
13999
|
440 |
\isakeyword{intros}\isanewline
|
17175
|
441 |
refl{\isacharcolon}\ \ {\isachardoublequoteopen}{\isacharparenleft}x{\isacharcomma}x{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\isanewline
|
|
442 |
step{\isacharcolon}\ \ {\isachardoublequoteopen}{\isasymlbrakk}\ {\isacharparenleft}x{\isacharcomma}y{\isacharparenright}\ {\isasymin}\ r{\isacharsemicolon}\ {\isacharparenleft}y{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}\ {\isasymrbrakk}\ {\isasymLongrightarrow}\ {\isacharparenleft}x{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}%
|
13999
|
443 |
\begin{isamarkuptext}%
|
|
444 |
\noindent
|
|
445 |
First the constant is declared as a function on binary
|
|
446 |
relations (with concrete syntax \isa{r{\isacharasterisk}} instead of \isa{rtc\ r}), then the defining clauses are given. We will now prove that
|
|
447 |
\isa{r{\isacharasterisk}} is indeed transitive:%
|
|
448 |
\end{isamarkuptext}%
|
17175
|
449 |
\isamarkuptrue%
|
|
450 |
\isacommand{lemma}\isamarkupfalse%
|
|
451 |
\ \isakeyword{assumes}\ A{\isacharcolon}\ {\isachardoublequoteopen}{\isacharparenleft}x{\isacharcomma}y{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\ \isakeyword{shows}\ {\isachardoublequoteopen}{\isacharparenleft}y{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}\ {\isasymLongrightarrow}\ {\isacharparenleft}x{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\isanewline
|
17125
|
452 |
%
|
|
453 |
\isadelimproof
|
|
454 |
%
|
|
455 |
\endisadelimproof
|
|
456 |
%
|
|
457 |
\isatagproof
|
17175
|
458 |
\isacommand{using}\isamarkupfalse%
|
|
459 |
\ A\isanewline
|
|
460 |
\isacommand{proof}\isamarkupfalse%
|
|
461 |
\ induct\isanewline
|
|
462 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
463 |
\ refl\ \isacommand{thus}\isamarkupfalse%
|
|
464 |
\ {\isacharquery}case\ \isacommand{{\isachardot}}\isamarkupfalse%
|
|
465 |
\isanewline
|
|
466 |
\isacommand{next}\isamarkupfalse%
|
|
467 |
\isanewline
|
|
468 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
469 |
\ step\ \isacommand{thus}\isamarkupfalse%
|
|
470 |
\ {\isacharquery}case\ \isacommand{by}\isamarkupfalse%
|
|
471 |
{\isacharparenleft}blast\ intro{\isacharcolon}\ rtc{\isachardot}step{\isacharparenright}\isanewline
|
|
472 |
\isacommand{qed}\isamarkupfalse%
|
|
473 |
%
|
17125
|
474 |
\endisatagproof
|
|
475 |
{\isafoldproof}%
|
|
476 |
%
|
|
477 |
\isadelimproof
|
|
478 |
%
|
|
479 |
\endisadelimproof
|
13999
|
480 |
%
|
|
481 |
\begin{isamarkuptext}%
|
|
482 |
\noindent Rule induction is triggered by a fact $(x_1,\dots,x_n)
|
|
483 |
\in R$ piped into the proof, here \isakeyword{using}~\isa{A}. The
|
|
484 |
proof itself follows the inductive definition very
|
|
485 |
closely: there is one case for each rule, and it has the same name as
|
|
486 |
the rule, analogous to structural induction.
|
|
487 |
|
|
488 |
However, this proof is rather terse. Here is a more readable version:%
|
|
489 |
\end{isamarkuptext}%
|
17175
|
490 |
\isamarkuptrue%
|
|
491 |
\isacommand{lemma}\isamarkupfalse%
|
|
492 |
\ \isakeyword{assumes}\ A{\isacharcolon}\ {\isachardoublequoteopen}{\isacharparenleft}x{\isacharcomma}y{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\ \isakeyword{and}\ B{\isacharcolon}\ {\isachardoublequoteopen}{\isacharparenleft}y{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\isanewline
|
|
493 |
\ \ \isakeyword{shows}\ {\isachardoublequoteopen}{\isacharparenleft}x{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\isanewline
|
17125
|
494 |
%
|
|
495 |
\isadelimproof
|
|
496 |
%
|
|
497 |
\endisadelimproof
|
|
498 |
%
|
|
499 |
\isatagproof
|
17175
|
500 |
\isacommand{proof}\isamarkupfalse%
|
|
501 |
\ {\isacharminus}\isanewline
|
|
502 |
\ \ \isacommand{from}\isamarkupfalse%
|
|
503 |
\ A\ B\ \isacommand{show}\isamarkupfalse%
|
|
504 |
\ {\isacharquery}thesis\isanewline
|
|
505 |
\ \ \isacommand{proof}\isamarkupfalse%
|
|
506 |
\ induct\isanewline
|
|
507 |
\ \ \ \ \isacommand{fix}\isamarkupfalse%
|
|
508 |
\ x\ \isacommand{assume}\isamarkupfalse%
|
|
509 |
\ {\isachardoublequoteopen}{\isacharparenleft}x{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\ \ %
|
16459
|
510 |
\isamarkupcmt{\isa{B}[\isa{y} := \isa{x}]%
|
|
511 |
}
|
|
512 |
\isanewline
|
17175
|
513 |
\ \ \ \ \isacommand{thus}\isamarkupfalse%
|
|
514 |
\ {\isachardoublequoteopen}{\isacharparenleft}x{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\ \isacommand{{\isachardot}}\isamarkupfalse%
|
|
515 |
\isanewline
|
|
516 |
\ \ \isacommand{next}\isamarkupfalse%
|
|
517 |
\isanewline
|
|
518 |
\ \ \ \ \isacommand{fix}\isamarkupfalse%
|
|
519 |
\ x{\isacharprime}\ x\ y\isanewline
|
|
520 |
\ \ \ \ \isacommand{assume}\isamarkupfalse%
|
|
521 |
\ {\isadigit{1}}{\isacharcolon}\ {\isachardoublequoteopen}{\isacharparenleft}x{\isacharprime}{\isacharcomma}x{\isacharparenright}\ {\isasymin}\ r{\isachardoublequoteclose}\ \isakeyword{and}\isanewline
|
|
522 |
\ \ \ \ \ \ \ \ \ \ \ IH{\isacharcolon}\ {\isachardoublequoteopen}{\isacharparenleft}y{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}\ {\isasymLongrightarrow}\ {\isacharparenleft}x{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\ \isakeyword{and}\isanewline
|
|
523 |
\ \ \ \ \ \ \ \ \ \ \ B{\isacharcolon}\ \ {\isachardoublequoteopen}{\isacharparenleft}y{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\isanewline
|
|
524 |
\ \ \ \ \isacommand{from}\isamarkupfalse%
|
|
525 |
\ {\isadigit{1}}\ IH{\isacharbrackleft}OF\ B{\isacharbrackright}\ \isacommand{show}\isamarkupfalse%
|
|
526 |
\ {\isachardoublequoteopen}{\isacharparenleft}x{\isacharprime}{\isacharcomma}z{\isacharparenright}\ {\isasymin}\ r{\isacharasterisk}{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
527 |
{\isacharparenleft}rule\ rtc{\isachardot}step{\isacharparenright}\isanewline
|
|
528 |
\ \ \isacommand{qed}\isamarkupfalse%
|
|
529 |
\isanewline
|
|
530 |
\isacommand{qed}\isamarkupfalse%
|
|
531 |
%
|
17125
|
532 |
\endisatagproof
|
|
533 |
{\isafoldproof}%
|
|
534 |
%
|
|
535 |
\isadelimproof
|
|
536 |
%
|
|
537 |
\endisadelimproof
|
13999
|
538 |
%
|
|
539 |
\begin{isamarkuptext}%
|
|
540 |
\noindent We start the proof with \isakeyword{from}~\isa{A\ B}. Only \isa{A} is ``consumed'' by the induction step.
|
|
541 |
Since \isa{B} is left over we don't just prove \isa{{\isacharquery}thesis} but \isa{B\ {\isasymLongrightarrow}\ {\isacharquery}thesis}, just as in the previous proof. The
|
|
542 |
base case is trivial. In the assumptions for the induction step we can
|
|
543 |
see very clearly how things fit together and permit ourselves the
|
|
544 |
obvious forward step \isa{IH{\isacharbrackleft}OF\ B{\isacharbrackright}}.
|
|
545 |
|
|
546 |
The notation `\isakeyword{case}~\isa{(}\emph{constructor} \emph{vars}\isa{)}'
|
|
547 |
is also supported for inductive definitions. The \emph{constructor} is (the
|
|
548 |
name of) the rule and the \emph{vars} fix the free variables in the
|
|
549 |
rule; the order of the \emph{vars} must correspond to the
|
|
550 |
\emph{alphabetical order} of the variables as they appear in the rule.
|
|
551 |
For example, we could start the above detailed proof of the induction
|
|
552 |
with \isakeyword{case}~\isa{(step x' x y)}. However, we can then only
|
|
553 |
refer to the assumptions named \isa{step} collectively and not
|
|
554 |
individually, as the above proof requires.%
|
|
555 |
\end{isamarkuptext}%
|
|
556 |
\isamarkuptrue%
|
|
557 |
%
|
|
558 |
\isamarkupsubsection{More induction%
|
|
559 |
}
|
|
560 |
\isamarkuptrue%
|
|
561 |
%
|
|
562 |
\begin{isamarkuptext}%
|
|
563 |
We close the section by demonstrating how arbitrary induction
|
|
564 |
rules are applied. As a simple example we have chosen recursion
|
|
565 |
induction, i.e.\ induction based on a recursive function
|
|
566 |
definition. However, most of what we show works for induction in
|
|
567 |
general.
|
|
568 |
|
|
569 |
The example is an unusual definition of rotation:%
|
|
570 |
\end{isamarkuptext}%
|
17175
|
571 |
\isamarkuptrue%
|
|
572 |
\isacommand{consts}\isamarkupfalse%
|
|
573 |
\ rot\ {\isacharcolon}{\isacharcolon}\ {\isachardoublequoteopen}{\isacharprime}a\ list\ {\isasymRightarrow}\ {\isacharprime}a\ list{\isachardoublequoteclose}\isanewline
|
|
574 |
\isacommand{recdef}\isamarkupfalse%
|
|
575 |
\ rot\ {\isachardoublequoteopen}measure\ length{\isachardoublequoteclose}\ \ %
|
13999
|
576 |
\isamarkupcmt{for the internal termination proof%
|
|
577 |
}
|
|
578 |
\isanewline
|
17175
|
579 |
{\isachardoublequoteopen}rot\ {\isacharbrackleft}{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}{\isacharbrackright}{\isachardoublequoteclose}\isanewline
|
|
580 |
{\isachardoublequoteopen}rot\ {\isacharbrackleft}x{\isacharbrackright}\ {\isacharequal}\ {\isacharbrackleft}x{\isacharbrackright}{\isachardoublequoteclose}\isanewline
|
|
581 |
{\isachardoublequoteopen}rot\ {\isacharparenleft}x{\isacharhash}y{\isacharhash}zs{\isacharparenright}\ {\isacharequal}\ y\ {\isacharhash}\ rot{\isacharparenleft}x{\isacharhash}zs{\isacharparenright}{\isachardoublequoteclose}%
|
13999
|
582 |
\begin{isamarkuptext}%
|
|
583 |
\noindent This yields, among other things, the induction rule
|
|
584 |
\isa{rot{\isachardot}induct}: \begin{isabelle}%
|
|
585 |
{\isasymlbrakk}P\ {\isacharbrackleft}{\isacharbrackright}{\isacharsemicolon}\ {\isasymAnd}x{\isachardot}\ P\ {\isacharbrackleft}x{\isacharbrackright}{\isacharsemicolon}\ {\isasymAnd}x\ y\ zs{\isachardot}\ P\ {\isacharparenleft}x\ {\isacharhash}\ zs{\isacharparenright}\ {\isasymLongrightarrow}\ P\ {\isacharparenleft}x\ {\isacharhash}\ y\ {\isacharhash}\ zs{\isacharparenright}{\isasymrbrakk}\ {\isasymLongrightarrow}\ P\ x%
|
|
586 |
\end{isabelle}
|
|
587 |
In the following proof we rely on a default naming scheme for cases: they are
|
|
588 |
called 1, 2, etc, unless they have been named explicitly. The latter happens
|
|
589 |
only with datatypes and inductively defined sets, but not with recursive
|
|
590 |
functions.%
|
|
591 |
\end{isamarkuptext}%
|
17175
|
592 |
\isamarkuptrue%
|
|
593 |
\isacommand{lemma}\isamarkupfalse%
|
|
594 |
\ {\isachardoublequoteopen}xs\ {\isasymnoteq}\ {\isacharbrackleft}{\isacharbrackright}\ {\isasymLongrightarrow}\ rot\ xs\ {\isacharequal}\ tl\ xs\ {\isacharat}\ {\isacharbrackleft}hd\ xs{\isacharbrackright}{\isachardoublequoteclose}\isanewline
|
17125
|
595 |
%
|
|
596 |
\isadelimproof
|
|
597 |
%
|
|
598 |
\endisadelimproof
|
|
599 |
%
|
|
600 |
\isatagproof
|
17175
|
601 |
\isacommand{proof}\isamarkupfalse%
|
|
602 |
\ {\isacharparenleft}induct\ xs\ rule{\isacharcolon}\ rot{\isachardot}induct{\isacharparenright}\isanewline
|
|
603 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
604 |
\ {\isadigit{1}}\ \isacommand{thus}\isamarkupfalse%
|
|
605 |
\ {\isacharquery}case\ \isacommand{by}\isamarkupfalse%
|
|
606 |
\ simp\isanewline
|
|
607 |
\isacommand{next}\isamarkupfalse%
|
|
608 |
\isanewline
|
|
609 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
610 |
\ {\isadigit{2}}\ \isacommand{show}\isamarkupfalse%
|
|
611 |
\ {\isacharquery}case\ \isacommand{by}\isamarkupfalse%
|
|
612 |
\ simp\isanewline
|
|
613 |
\isacommand{next}\isamarkupfalse%
|
|
614 |
\isanewline
|
|
615 |
\ \ \isacommand{case}\isamarkupfalse%
|
|
616 |
\ {\isacharparenleft}{\isadigit{3}}\ a\ b\ cs{\isacharparenright}\isanewline
|
|
617 |
\ \ \isacommand{have}\isamarkupfalse%
|
|
618 |
\ {\isachardoublequoteopen}rot\ {\isacharparenleft}a\ {\isacharhash}\ b\ {\isacharhash}\ cs{\isacharparenright}\ {\isacharequal}\ b\ {\isacharhash}\ rot{\isacharparenleft}a\ {\isacharhash}\ cs{\isacharparenright}{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
619 |
\ simp\isanewline
|
|
620 |
\ \ \isacommand{also}\isamarkupfalse%
|
|
621 |
\ \isacommand{have}\isamarkupfalse%
|
|
622 |
\ {\isachardoublequoteopen}{\isasymdots}\ {\isacharequal}\ b\ {\isacharhash}\ tl{\isacharparenleft}a\ {\isacharhash}\ cs{\isacharparenright}\ {\isacharat}\ {\isacharbrackleft}hd{\isacharparenleft}a\ {\isacharhash}\ cs{\isacharparenright}{\isacharbrackright}{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
623 |
{\isacharparenleft}simp\ add{\isacharcolon}{\isadigit{3}}{\isacharparenright}\isanewline
|
|
624 |
\ \ \isacommand{also}\isamarkupfalse%
|
|
625 |
\ \isacommand{have}\isamarkupfalse%
|
|
626 |
\ {\isachardoublequoteopen}{\isasymdots}\ {\isacharequal}\ tl\ {\isacharparenleft}a\ {\isacharhash}\ b\ {\isacharhash}\ cs{\isacharparenright}\ {\isacharat}\ {\isacharbrackleft}hd\ {\isacharparenleft}a\ {\isacharhash}\ b\ {\isacharhash}\ cs{\isacharparenright}{\isacharbrackright}{\isachardoublequoteclose}\ \isacommand{by}\isamarkupfalse%
|
|
627 |
\ simp\isanewline
|
|
628 |
\ \ \isacommand{finally}\isamarkupfalse%
|
|
629 |
\ \isacommand{show}\isamarkupfalse%
|
|
630 |
\ {\isacharquery}case\ \isacommand{{\isachardot}}\isamarkupfalse%
|
|
631 |
\isanewline
|
|
632 |
\isacommand{qed}\isamarkupfalse%
|
|
633 |
%
|
17125
|
634 |
\endisatagproof
|
|
635 |
{\isafoldproof}%
|
|
636 |
%
|
|
637 |
\isadelimproof
|
|
638 |
%
|
|
639 |
\endisadelimproof
|
13999
|
640 |
%
|
|
641 |
\begin{isamarkuptext}%
|
|
642 |
\noindent
|
|
643 |
The third case is only shown in gory detail (see \cite{BauerW-TPHOLs01}
|
|
644 |
for how to reason with chains of equations) to demonstrate that the
|
|
645 |
`\isakeyword{case}~\isa{(}\emph{constructor} \emph{vars}\isa{)}' notation also
|
|
646 |
works for arbitrary induction theorems with numbered cases. The order
|
|
647 |
of the \emph{vars} corresponds to the order of the
|
|
648 |
\isa{{\isasymAnd}}-quantified variables in each case of the induction
|
|
649 |
theorem. For induction theorems produced by \isakeyword{recdef} it is
|
|
650 |
the order in which the variables appear on the left-hand side of the
|
|
651 |
equation.
|
|
652 |
|
|
653 |
The proof is so simple that it can be condensed to%
|
|
654 |
\end{isamarkuptext}%
|
17175
|
655 |
\isamarkuptrue%
|
|
656 |
\isamarkupfalse%
|
17125
|
657 |
%
|
|
658 |
\isadelimproof
|
|
659 |
%
|
|
660 |
\endisadelimproof
|
|
661 |
%
|
|
662 |
\isatagproof
|
17175
|
663 |
\isacommand{by}\isamarkupfalse%
|
|
664 |
\ {\isacharparenleft}induct\ xs\ rule{\isacharcolon}\ rot{\isachardot}induct{\isacharcomma}\ simp{\isacharunderscore}all{\isacharparenright}\isanewline
|
17125
|
665 |
%
|
|
666 |
\endisatagproof
|
|
667 |
{\isafoldproof}%
|
|
668 |
%
|
|
669 |
\isadelimproof
|
|
670 |
%
|
|
671 |
\endisadelimproof
|
|
672 |
%
|
|
673 |
\isadelimtheory
|
|
674 |
%
|
|
675 |
\endisadelimtheory
|
|
676 |
%
|
|
677 |
\isatagtheory
|
17175
|
678 |
\isamarkupfalse%
|
17125
|
679 |
%
|
|
680 |
\endisatagtheory
|
|
681 |
{\isafoldtheory}%
|
|
682 |
%
|
|
683 |
\isadelimtheory
|
|
684 |
%
|
|
685 |
\endisadelimtheory
|
13999
|
686 |
\end{isabellebody}%
|
|
687 |
%%% Local Variables:
|
|
688 |
%%% mode: latex
|
|
689 |
%%% TeX-master: "root"
|
|
690 |
%%% End:
|