src/Doc/Tutorial/Misc/AdvancedInd.thy
changeset 69505 cc2d676d5395
parent 67406 23307fd33906
child 69597 ff784d5a5bfb
equal deleted inserted replaced
69504:bda7527ccf05 69505:cc2d676d5395
    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)
   206 \<close>
   206 \<close>
   207 
   207 
   208 lemmas f_incr = f_incr_lem[rule_format, OF refl]
   208 lemmas f_incr = f_incr_lem[rule_format, OF refl]
   209 
   209 
   210 text\<open>\noindent
   210 text\<open>\noindent
   211 The final @{thm[source]refl} gets rid of the premise @{text"?k = f ?i"}. 
   211 The final @{thm[source]refl} gets rid of the premise \<open>?k = f ?i\<close>. 
   212 We could have included this derivation in the original statement of the lemma:
   212 We could have included this derivation in the original statement of the lemma:
   213 \<close>
   213 \<close>
   214 
   214 
   215 lemma f_incr[rule_format, OF refl]: "\<forall>i. k = f i \<longrightarrow> i \<le> f i"
   215 lemma f_incr[rule_format, OF refl]: "\<forall>i. k = f i \<longrightarrow> i \<le> f i"
   216 (*<*)oops(*>*)
   216 (*<*)oops(*>*)
   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}
   277 
   277 
   278 text\<open>
   278 text\<open>
   279 HOL already provides the mother of
   279 HOL already provides the mother of
   280 all inductions, well-founded induction (see \S\ref{sec:Well-founded}).  For
   280 all inductions, well-founded induction (see \S\ref{sec:Well-founded}).  For
   281 example theorem @{thm[source]nat_less_induct} is
   281 example theorem @{thm[source]nat_less_induct} is
   282 a special case of @{thm[source]wf_induct} where @{term r} is @{text"<"} on
   282 a special case of @{thm[source]wf_induct} where @{term r} is \<open><\<close> on
   283 @{typ nat}. The details can be found in theory \isa{Wellfounded_Recursion}.
   283 @{typ nat}. The details can be found in theory \isa{Wellfounded_Recursion}.
   284 \<close>
   284 \<close>
   285 (*<*)end(*>*)
   285 (*<*)end(*>*)