26 produces the warning |
26 produces the warning |
27 \begin{quote}\tt |
27 \begin{quote}\tt |
28 Induction variable occurs also among premises! |
28 Induction variable occurs also among premises! |
29 \end{quote} |
29 \end{quote} |
30 and leads to the base case |
30 and leads to the base case |
31 \begin{isabelle} |
31 @{subgoals[display,indent=0,goals_limit=1]} |
32 \ 1.\ xs\ {\isasymnoteq}\ []\ {\isasymLongrightarrow}\ hd\ (rev\ [])\ =\ last\ [] |
|
33 \end{isabelle} |
|
34 which, after simplification, becomes |
32 which, after simplification, becomes |
35 \begin{isabelle} |
33 \begin{isabelle} |
36 \ 1.\ xs\ {\isasymnoteq}\ []\ {\isasymLongrightarrow}\ hd\ []\ =\ last\ [] |
34 \ 1.\ xs\ {\isasymnoteq}\ []\ {\isasymLongrightarrow}\ hd\ []\ =\ last\ [] |
37 \end{isabelle} |
35 \end{isabelle} |
38 We cannot prove this equality because we do not know what @{term hd} and |
36 We cannot prove this equality because we do not know what @{term hd} and |
55 by(induct_tac xs, auto); |
53 by(induct_tac xs, auto); |
56 (*>*) |
54 (*>*) |
57 |
55 |
58 text{*\noindent |
56 text{*\noindent |
59 This time, induction leaves us with the following base case |
57 This time, induction leaves us with the following base case |
60 %{goals[goals_limit=1,display]} |
|
61 \begin{isabelle} |
58 \begin{isabelle} |
62 \ 1.\ []\ {\isasymnoteq}\ []\ {\isasymlongrightarrow}\ hd\ (rev\ [])\ =\ last\ [] |
59 \ 1.\ []\ {\isasymnoteq}\ []\ {\isasymlongrightarrow}\ hd\ (rev\ [])\ =\ last\ [] |
63 \end{isabelle} |
60 \end{isabelle} |
64 which is trivial, and @{text"auto"} finishes the whole proof. |
61 which is trivial, and @{text"auto"} finishes the whole proof. |
65 |
62 |
168 *}; |
165 *}; |
169 |
166 |
170 lemma f_incr_lem: "\<forall>i. k = f i \<longrightarrow> i \<le> f i"; |
167 lemma f_incr_lem: "\<forall>i. k = f i \<longrightarrow> i \<le> f i"; |
171 |
168 |
172 txt{*\noindent |
169 txt{*\noindent |
173 To perform induction on @{term"k"} using @{thm[source]nat_less_induct}, we use the same |
170 To perform induction on @{term k} using @{thm[source]nat_less_induct}, we use |
174 general induction method as for recursion induction (see |
171 the same general induction method as for recursion induction (see |
175 \S\ref{sec:recdef-induction}): |
172 \S\ref{sec:recdef-induction}): |
176 *}; |
173 *}; |
177 |
174 |
178 apply(induct_tac k rule: nat_less_induct); |
175 apply(induct_tac k rule: nat_less_induct); |
179 (*<*) |
176 |
|
177 txt{*\noindent |
|
178 which leaves us with the following proof state: |
|
179 @{subgoals[display,indent=0,margin=65]} |
|
180 After stripping the @{text"\<forall>i"}, the proof continues with a case |
|
181 distinction on @{term"i"}. The case @{prop"i = 0"} is trivial and we focus on |
|
182 the other case: |
|
183 *} |
|
184 |
180 apply(rule allI); |
185 apply(rule allI); |
181 apply(case_tac i); |
186 apply(case_tac i); |
182 apply(simp); |
187 apply(simp); |
183 (*>*) |
188 |
184 txt{*\noindent |
189 txt{* |
185 which leaves us with the following proof state: |
190 @{subgoals[display,indent=0]} |
186 \begin{isabelle} |
|
187 \ 1.\ {\isasymAnd}\mbox{n}.\ {\isasymforall}\mbox{m}.\ \mbox{m}\ <\ \mbox{n}\ {\isasymlongrightarrow}\ ({\isasymforall}\mbox{i}.\ \mbox{m}\ =\ f\ \mbox{i}\ {\isasymlongrightarrow}\ \mbox{i}\ {\isasymle}\ f\ \mbox{i})\isanewline |
|
188 \ \ \ \ \ \ \ {\isasymLongrightarrow}\ {\isasymforall}\mbox{i}.\ \mbox{n}\ =\ f\ \mbox{i}\ {\isasymlongrightarrow}\ \mbox{i}\ {\isasymle}\ f\ \mbox{i} |
|
189 \end{isabelle} |
|
190 After stripping the @{text"\<forall>i"}, the proof continues with a case |
|
191 distinction on @{term"i"}. The case @{prop"i = 0"} is trivial and we focus on |
|
192 the other case: |
|
193 \begin{isabelle} |
|
194 \ 1.\ {\isasymAnd}\mbox{n}\ \mbox{i}\ \mbox{nat}.\isanewline |
|
195 \ \ \ \ \ \ \ {\isasymlbrakk}{\isasymforall}\mbox{m}.\ \mbox{m}\ <\ \mbox{n}\ {\isasymlongrightarrow}\ ({\isasymforall}\mbox{i}.\ \mbox{m}\ =\ f\ \mbox{i}\ {\isasymlongrightarrow}\ \mbox{i}\ {\isasymle}\ f\ \mbox{i});\ \mbox{i}\ =\ Suc\ \mbox{nat}{\isasymrbrakk}\isanewline |
|
196 \ \ \ \ \ \ \ {\isasymLongrightarrow}\ \mbox{n}\ =\ f\ \mbox{i}\ {\isasymlongrightarrow}\ \mbox{i}\ {\isasymle}\ f\ \mbox{i} |
|
197 \end{isabelle} |
|
198 *}; |
191 *}; |
199 |
192 |
200 by(blast intro!: f_ax Suc_leI intro: le_less_trans); |
193 by(blast intro!: f_ax Suc_leI intro: le_less_trans); |
201 |
194 |
202 text{*\noindent |
195 text{*\noindent |