equal
deleted
inserted
replaced
177 usually known as mathematical induction. There is also \textbf{complete} |
177 usually known as mathematical induction. There is also \textbf{complete} |
178 \index{induction!complete}% |
178 \index{induction!complete}% |
179 induction, where you prove $P(n)$ under the assumption that $P(m)$ |
179 induction, where you prove $P(n)$ under the assumption that $P(m)$ |
180 holds for all $m<n$. In Isabelle, this is the theorem \tdx{nat_less_induct}: |
180 holds for all $m<n$. In Isabelle, this is the theorem \tdx{nat_less_induct}: |
181 \begin{isabelle}% |
181 \begin{isabelle}% |
182 \ \ \ \ \ {\isacharparenleft}{\isasymAnd}n{\isachardot}\ {\isasymforall}m{\isacharless}n{\isachardot}\ P\ m\ {\isasymLongrightarrow}\ P\ n{\isacharparenright}\ {\isasymLongrightarrow}\ P\ n% |
182 \ \ \ \ \ {\isacharparenleft}{\isasymAnd}n{\isachardot}\ {\isasymforall}m{\isachardot}\ m\ {\isacharless}\ n\ {\isasymlongrightarrow}\ P\ m\ {\isasymLongrightarrow}\ P\ n{\isacharparenright}\ {\isasymLongrightarrow}\ P\ n% |
183 \end{isabelle} |
183 \end{isabelle} |
184 As an application, we prove a property of the following |
184 As an application, we prove a property of the following |
185 function:% |
185 function:% |
186 \end{isamarkuptext}% |
186 \end{isamarkuptext}% |
187 \isamarkuptrue% |
187 \isamarkuptrue% |
223 {\isacharparenleft}induct{\isacharunderscore}tac\ k\ rule{\isacharcolon}\ nat{\isacharunderscore}less{\isacharunderscore}induct{\isacharparenright}% |
223 {\isacharparenleft}induct{\isacharunderscore}tac\ k\ rule{\isacharcolon}\ nat{\isacharunderscore}less{\isacharunderscore}induct{\isacharparenright}% |
224 \begin{isamarkuptxt}% |
224 \begin{isamarkuptxt}% |
225 \noindent |
225 \noindent |
226 We get the following proof state: |
226 We get the following proof state: |
227 \begin{isabelle}% |
227 \begin{isabelle}% |
228 \ {\isadigit{1}}{\isachardot}\ {\isasymAnd}n{\isachardot}\ {\isasymforall}m{\isacharless}n{\isachardot}\ {\isasymforall}i{\isachardot}\ m\ {\isacharequal}\ f\ i\ {\isasymlongrightarrow}\ i\ {\isasymle}\ f\ i\ {\isasymLongrightarrow}\ {\isasymforall}i{\isachardot}\ n\ {\isacharequal}\ f\ i\ {\isasymlongrightarrow}\ i\ {\isasymle}\ f\ i% |
228 \ {\isadigit{1}}{\isachardot}\ {\isasymAnd}n{\isachardot}\ {\isasymforall}m{\isachardot}\ m\ {\isacharless}\ n\ {\isasymlongrightarrow}\ {\isacharparenleft}{\isasymforall}i{\isachardot}\ m\ {\isacharequal}\ f\ i\ {\isasymlongrightarrow}\ i\ {\isasymle}\ f\ i{\isacharparenright}\ {\isasymLongrightarrow}\isanewline |
|
229 \isaindent{\ {\isadigit{1}}{\isachardot}\ {\isasymAnd}n{\isachardot}\ }{\isasymforall}i{\isachardot}\ n\ {\isacharequal}\ f\ i\ {\isasymlongrightarrow}\ i\ {\isasymle}\ f\ i% |
229 \end{isabelle} |
230 \end{isabelle} |
230 After stripping the \isa{{\isasymforall}i}, the proof continues with a case |
231 After stripping the \isa{{\isasymforall}i}, the proof continues with a case |
231 distinction on \isa{i}. The case \isa{i\ {\isacharequal}\ {\isadigit{0}}} is trivial and we focus on |
232 distinction on \isa{i}. The case \isa{i\ {\isacharequal}\ {\isadigit{0}}} is trivial and we focus on |
232 the other case:% |
233 the other case:% |
233 \end{isamarkuptxt}% |
234 \end{isamarkuptxt}% |
239 \ \isacommand{apply}\isamarkupfalse% |
240 \ \isacommand{apply}\isamarkupfalse% |
240 {\isacharparenleft}simp{\isacharparenright}% |
241 {\isacharparenleft}simp{\isacharparenright}% |
241 \begin{isamarkuptxt}% |
242 \begin{isamarkuptxt}% |
242 \begin{isabelle}% |
243 \begin{isabelle}% |
243 \ {\isadigit{1}}{\isachardot}\ {\isasymAnd}n\ i\ nat{\isachardot}\isanewline |
244 \ {\isadigit{1}}{\isachardot}\ {\isasymAnd}n\ i\ nat{\isachardot}\isanewline |
244 \isaindent{\ {\isadigit{1}}{\isachardot}\ \ \ \ }{\isasymlbrakk}{\isasymforall}m{\isacharless}n{\isachardot}\ {\isasymforall}i{\isachardot}\ m\ {\isacharequal}\ f\ i\ {\isasymlongrightarrow}\ i\ {\isasymle}\ f\ i{\isacharsemicolon}\ i\ {\isacharequal}\ Suc\ nat{\isasymrbrakk}\ {\isasymLongrightarrow}\ n\ {\isacharequal}\ f\ i\ {\isasymlongrightarrow}\ i\ {\isasymle}\ f\ i% |
245 \isaindent{\ {\isadigit{1}}{\isachardot}\ \ \ \ }{\isasymlbrakk}{\isasymforall}m{\isachardot}\ m\ {\isacharless}\ n\ {\isasymlongrightarrow}\ {\isacharparenleft}{\isasymforall}i{\isachardot}\ m\ {\isacharequal}\ f\ i\ {\isasymlongrightarrow}\ i\ {\isasymle}\ f\ i{\isacharparenright}{\isacharsemicolon}\ i\ {\isacharequal}\ Suc\ nat{\isasymrbrakk}\isanewline |
|
246 \isaindent{\ {\isadigit{1}}{\isachardot}\ \ \ \ }{\isasymLongrightarrow}\ n\ {\isacharequal}\ f\ i\ {\isasymlongrightarrow}\ i\ {\isasymle}\ f\ i% |
245 \end{isabelle}% |
247 \end{isabelle}% |
246 \end{isamarkuptxt}% |
248 \end{isamarkuptxt}% |
247 \isamarkuptrue% |
249 \isamarkuptrue% |
248 \isacommand{by}\isamarkupfalse% |
250 \isacommand{by}\isamarkupfalse% |
249 {\isacharparenleft}blast\ intro{\isacharbang}{\isacharcolon}\ f{\isacharunderscore}ax\ Suc{\isacharunderscore}leI\ intro{\isacharcolon}\ le{\isacharunderscore}less{\isacharunderscore}trans{\isacharparenright}% |
251 {\isacharparenleft}blast\ intro{\isacharbang}{\isacharcolon}\ f{\isacharunderscore}ax\ Suc{\isacharunderscore}leI\ intro{\isacharcolon}\ le{\isacharunderscore}less{\isacharunderscore}trans{\isacharparenright}% |