146 word. We start with 0 and end (at the right end) with 2. Since each move to the |
146 word. We start with 0 and end (at the right end) with 2. Since each move to the |
147 right increases or decreases the difference by 1, we must have passed through |
147 right increases or decreases the difference by 1, we must have passed through |
148 1 on our way from 0 to 2. Formally, we appeal to the following discrete |
148 1 on our way from 0 to 2. Formally, we appeal to the following discrete |
149 intermediate value theorem \isa{nat{\isadigit{0}}{\isacharunderscore}intermed{\isacharunderscore}int{\isacharunderscore}val} |
149 intermediate value theorem \isa{nat{\isadigit{0}}{\isacharunderscore}intermed{\isacharunderscore}int{\isacharunderscore}val} |
150 \begin{isabelle}% |
150 \begin{isabelle}% |
151 \ \ \ \ \ {\isasymlbrakk}{\isasymforall}i{\isachardot}\ i\ {\isacharless}\ n\ {\isasymlongrightarrow}\ {\isasymbar}f\ {\isacharparenleft}i\ {\isacharplus}\ {\isadigit{1}}{\isacharparenright}\ {\isacharminus}\ f\ i{\isasymbar}\ {\isasymle}\ {\isadigit{1}}{\isacharsemicolon}\ f\ {\isadigit{0}}\ {\isasymle}\ k{\isacharsemicolon}\ k\ {\isasymle}\ f\ n{\isasymrbrakk}\isanewline |
151 \ \ \ \ \ {\isasymlbrakk}{\isasymforall}i{\isacharless}n{\isachardot}\ {\isasymbar}f\ {\isacharparenleft}i\ {\isacharplus}\ {\isadigit{1}}{\isacharparenright}\ {\isacharminus}\ f\ i{\isasymbar}\ {\isasymle}\ {\isadigit{1}}{\isacharsemicolon}\ f\ {\isadigit{0}}\ {\isasymle}\ k{\isacharsemicolon}\ k\ {\isasymle}\ f\ n{\isasymrbrakk}\isanewline |
152 \isaindent{\ \ \ \ \ }{\isasymLongrightarrow}\ {\isasymexists}i{\isachardot}\ i\ {\isasymle}\ n\ {\isasymand}\ f\ i\ {\isacharequal}\ k% |
152 \isaindent{\ \ \ \ \ }{\isasymLongrightarrow}\ {\isasymexists}i{\isasymle}n{\isachardot}\ f\ i\ {\isacharequal}\ k% |
153 \end{isabelle} |
153 \end{isabelle} |
154 where \isa{f} is of type \isa{nat\ {\isasymRightarrow}\ int}, \isa{int} are the integers, |
154 where \isa{f} is of type \isa{nat\ {\isasymRightarrow}\ int}, \isa{int} are the integers, |
155 \isa{{\isasymbar}{\isachardot}{\isasymbar}} is the absolute value function\footnote{See |
155 \isa{{\isasymbar}{\isachardot}{\isasymbar}} is the absolute value function\footnote{See |
156 Table~\ref{tab:ascii} in the Appendix for the correct \textsc{ascii} |
156 Table~\ref{tab:ascii} in the Appendix for the correct \textsc{ascii} |
157 syntax.}, and \isa{{\isadigit{1}}} is the integer 1 (see \S\ref{sec:numbers}). |
157 syntax.}, and \isa{{\isadigit{1}}} is the integer 1 (see \S\ref{sec:numbers}). |