diff -r 5b6305cab436 -r 9feb1e0c4cb3 doc-src/TutorialI/Misc/AdvancedInd.thy --- a/doc-src/TutorialI/Misc/AdvancedInd.thy Tue Sep 12 14:59:44 2000 +0200 +++ b/doc-src/TutorialI/Misc/AdvancedInd.thy Tue Sep 12 15:43:15 2000 +0200 @@ -17,7 +17,7 @@ that is amenable to induction, but this is not always the case: *}; -lemma "xs \\ [] \\ hd(rev xs) = last xs"; +lemma "xs \ [] \ hd(rev xs) = last xs"; apply(induct_tac xs); txt{*\noindent @@ -49,7 +49,7 @@ This means we should prove *}; (*<*)oops;(*>*) -lemma hd_rev: "xs \\ [] \\ hd(rev xs) = last xs"; +lemma hd_rev: "xs \ [] \ hd(rev xs) = last xs"; (*<*) by(induct_tac xs, auto); (*>*) @@ -82,7 +82,7 @@ Here is a simple example (which is proved by @{text"blast"}): *}; -lemma simple: "\\y. A y \\ B y \ B y & A y"; +lemma simple: "\y. A y \ B y \ B y & A y"; (*<*)by blast;(*>*) text{*\noindent @@ -105,7 +105,7 @@ statement of your original lemma, thus avoiding the intermediate step: *}; -lemma myrule[rulified]: "\\y. A y \\ B y \ B y & A y"; +lemma myrule[rulified]: "\y. A y \ B y \ B y & A y"; (*<*) by blast; (*>*) @@ -134,8 +134,8 @@ Structural induction on @{typ"nat"} is usually known as ``mathematical induction''. There is also ``complete induction'', where you must prove $P(n)$ under the assumption that $P(m)$ -holds for all $mi. k = f i \\ i \\ f i"; +lemma f_incr_lem: "\i. k = f i \ i \ f i"; txt{*\noindent -To perform induction on @{term"k"} using @{thm [source] nat_less_induct}, we use the same +To perform induction on @{term"k"} using @{thm[source]nat_less_induct}, we use the same general induction method as for recursion induction (see \S\ref{sec:recdef-induction}): *}; @@ -213,7 +213,7 @@ we could have included this derivation in the original statement of the lemma: *}; -lemma f_incr[rulified, OF refl]: "\\i. k = f i \\ i \\ f i"; +lemma f_incr[rulified, OF refl]: "\i. k = f i \ i \ f i"; (*<*)oops;(*>*) text{* @@ -242,49 +242,46 @@ text{*\label{sec:derive-ind} Induction schemas are ordinary theorems and you can derive new ones whenever you wish. This section shows you how to, using the example -of @{thm [source] nat_less_induct}. Assume we only have structural induction +of @{thm[source]nat_less_induct}. Assume we only have structural induction available for @{typ"nat"} and want to derive complete induction. This requires us to generalize the statement first: *}; -lemma induct_lem: "(\\n::nat. \\m P n) \\ \\mn::nat. \m P n) \ \mn::nat. \\m P n) \\ P n"; +theorem nat_less_induct: "(\n::nat. \m P n) \ P n"; by(insert induct_lem, blast); -text{*\noindent +text{* Finally we should mention that HOL already provides the mother of all inductions, \emph{wellfounded induction} (@{thm[source]wf_induct}): @{thm[display]"wf_induct"[no_vars]} where @{term"wf r"} means that the relation @{term"r"} is wellfounded. -For example @{thm [source] nat_less_induct} is the special case where @{term"r"} is -@{text"<"} on @{typ"nat"}. For details see the library. +For example, theorem @{thm[source]nat_less_induct} can be viewed (and +derived) as a special case of @{thm[source]wf_induct} where +@{term"r"} is @{text"<"} on @{typ"nat"}. For details see the library. *}; (*<*)