43 Thus the case that should have been trivial |
43 Thus the case that should have been trivial |
44 becomes unprovable. Fortunately, the solution is easy:\footnote{A similar |
44 becomes unprovable. Fortunately, the solution is easy:\footnote{A similar |
45 heuristic applies to rule inductions; see \S\ref{sec:rtc}.} |
45 heuristic applies to rule inductions; see \S\ref{sec:rtc}.} |
46 \begin{quote} |
46 \begin{quote} |
47 \emph{Pull all occurrences of the induction variable into the conclusion |
47 \emph{Pull all occurrences of the induction variable into the conclusion |
48 using @{text"\<longrightarrow>"}.} |
48 using \<open>\<longrightarrow>\<close>.} |
49 \end{quote} |
49 \end{quote} |
50 Thus we should state the lemma as an ordinary |
50 Thus we should state the lemma as an ordinary |
51 implication~(@{text"\<longrightarrow>"}), letting |
51 implication~(\<open>\<longrightarrow>\<close>), letting |
52 \attrdx{rule_format} (\S\ref{sec:forward}) convert the |
52 \attrdx{rule_format} (\S\ref{sec:forward}) convert the |
53 result to the usual @{text"\<Longrightarrow>"} form: |
53 result to the usual \<open>\<Longrightarrow>\<close> form: |
54 \<close> |
54 \<close> |
55 (*<*)oops(*>*) |
55 (*<*)oops(*>*) |
56 lemma hd_rev [rule_format]: "xs \<noteq> [] \<longrightarrow> hd(rev xs) = last xs" |
56 lemma hd_rev [rule_format]: "xs \<noteq> [] \<longrightarrow> hd(rev xs) = last xs" |
57 (*<*) |
57 (*<*) |
58 apply(induct_tac xs) |
58 apply(induct_tac xs) |
59 (*>*) |
59 (*>*) |
60 |
60 |
61 txt\<open>\noindent |
61 txt\<open>\noindent |
62 This time, induction leaves us with a trivial base case: |
62 This time, induction leaves us with a trivial base case: |
63 @{subgoals[display,indent=0,goals_limit=1]} |
63 @{subgoals[display,indent=0,goals_limit=1]} |
64 And @{text"auto"} completes the proof. |
64 And \<open>auto\<close> completes the proof. |
65 |
65 |
66 If there are multiple premises $A@1$, \dots, $A@n$ containing the |
66 If there are multiple premises $A@1$, \dots, $A@n$ containing the |
67 induction variable, you should turn the conclusion $C$ into |
67 induction variable, you should turn the conclusion $C$ into |
68 \[ A@1 \longrightarrow \cdots A@n \longrightarrow C. \] |
68 \[ A@1 \longrightarrow \cdots A@n \longrightarrow C. \] |
69 Additionally, you may also have to universally quantify some other variables, |
69 Additionally, you may also have to universally quantify some other variables, |
70 which can yield a fairly complex conclusion. However, @{text rule_format} |
70 which can yield a fairly complex conclusion. However, \<open>rule_format\<close> |
71 can remove any number of occurrences of @{text"\<forall>"} and |
71 can remove any number of occurrences of \<open>\<forall>\<close> and |
72 @{text"\<longrightarrow>"}. |
72 \<open>\<longrightarrow>\<close>. |
73 |
73 |
74 \index{induction!on a term}% |
74 \index{induction!on a term}% |
75 A second reason why your proposition may not be amenable to induction is that |
75 A second reason why your proposition may not be amenable to induction is that |
76 you want to induct on a complex term, rather than a variable. In |
76 you want to induct on a complex term, rather than a variable. In |
77 general, induction on a term~$t$ requires rephrasing the conclusion~$C$ |
77 general, induction on a term~$t$ requires rephrasing the conclusion~$C$ |
90 replace it with $(x@1,\dots,x@k) \in R$, and rephrase the conclusion $C$ as |
90 replace it with $(x@1,\dots,x@k) \in R$, and rephrase the conclusion $C$ as |
91 \[ \forall y@1 \dots y@n.~ (x@1,\dots,x@k) = t \longrightarrow C. \] |
91 \[ \forall y@1 \dots y@n.~ (x@1,\dots,x@k) = t \longrightarrow C. \] |
92 For an example see \S\ref{sec:CTL-revisited} below. |
92 For an example see \S\ref{sec:CTL-revisited} below. |
93 |
93 |
94 Of course, all premises that share free variables with $t$ need to be pulled into |
94 Of course, all premises that share free variables with $t$ need to be pulled into |
95 the conclusion as well, under the @{text"\<forall>"}, again using @{text"\<longrightarrow>"} as shown above. |
95 the conclusion as well, under the \<open>\<forall>\<close>, again using \<open>\<longrightarrow>\<close> as shown above. |
96 |
96 |
97 Readers who are puzzled by the form of statement |
97 Readers who are puzzled by the form of statement |
98 (\ref{eqn:ind-over-term}) above should remember that the |
98 (\ref{eqn:ind-over-term}) above should remember that the |
99 transformation is only performed to permit induction. Once induction |
99 transformation is only performed to permit induction. Once induction |
100 has been applied, the statement can be transformed back into something quite |
100 has been applied, the statement can be transformed back into something quite |
136 where f_ax: "f(f(n)) < f(Suc(n))" for n :: nat |
136 where f_ax: "f(f(n)) < f(Suc(n))" for n :: nat |
137 |
137 |
138 text\<open> |
138 text\<open> |
139 \begin{warn} |
139 \begin{warn} |
140 We discourage the use of axioms because of the danger of |
140 We discourage the use of axioms because of the danger of |
141 inconsistencies. Axiom @{text f_ax} does |
141 inconsistencies. Axiom \<open>f_ax\<close> does |
142 not introduce an inconsistency because, for example, the identity function |
142 not introduce an inconsistency because, for example, the identity function |
143 satisfies it. Axioms can be useful in exploratory developments, say when |
143 satisfies it. Axioms can be useful in exploratory developments, say when |
144 you assume some well-known theorems so that you can quickly demonstrate some |
144 you assume some well-known theorems so that you can quickly demonstrate some |
145 point about methodology. If your example turns into a substantial proof |
145 point about methodology. If your example turns into a substantial proof |
146 development, you should replace axioms by theorems. |
146 development, you should replace axioms by theorems. |
161 apply(induct_tac k rule: nat_less_induct) |
161 apply(induct_tac k rule: nat_less_induct) |
162 |
162 |
163 txt\<open>\noindent |
163 txt\<open>\noindent |
164 We get the following proof state: |
164 We get the following proof state: |
165 @{subgoals[display,indent=0,margin=65]} |
165 @{subgoals[display,indent=0,margin=65]} |
166 After stripping the @{text"\<forall>i"}, the proof continues with a case |
166 After stripping the \<open>\<forall>i\<close>, the proof continues with a case |
167 distinction on @{term"i"}. The case @{prop"i = (0::nat)"} is trivial and we focus on |
167 distinction on @{term"i"}. The case @{prop"i = (0::nat)"} is trivial and we focus on |
168 the other case: |
168 the other case: |
169 \<close> |
169 \<close> |
170 |
170 |
171 apply(rule allI) |
171 apply(rule allI) |
223 |
223 |
224 Method \methdx{induct_tac} can be applied with any rule $r$ |
224 Method \methdx{induct_tac} can be applied with any rule $r$ |
225 whose conclusion is of the form ${?}P~?x@1 \dots ?x@n$, in which case the |
225 whose conclusion is of the form ${?}P~?x@1 \dots ?x@n$, in which case the |
226 format is |
226 format is |
227 \begin{quote} |
227 \begin{quote} |
228 \isacommand{apply}@{text"(induct_tac"} $y@1 \dots y@n$ @{text"rule:"} $r$@{text")"} |
228 \isacommand{apply}\<open>(induct_tac\<close> $y@1 \dots y@n$ \<open>rule:\<close> $r$\<open>)\<close> |
229 \end{quote} |
229 \end{quote} |
230 where $y@1, \dots, y@n$ are variables in the conclusion of the first subgoal. |
230 where $y@1, \dots, y@n$ are variables in the conclusion of the first subgoal. |
231 |
231 |
232 A further useful induction rule is @{thm[source]length_induct}, |
232 A further useful induction rule is @{thm[source]length_induct}, |
233 induction on the length of a list\indexbold{*length_induct} |
233 induction on the length of a list\indexbold{*length_induct} |