doc-src/TutorialI/Misc/AdvancedInd.thy
changeset 10363 6e8002c1790e
parent 10328 bf33cbd76c05
child 10396 5ab08609e6c8
equal deleted inserted replaced
10362:c6b197ccf1f1 10363:6e8002c1790e
    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