273 |
273 |
274 theorem nat_less_induct: "(\<And>n::nat. \<forall>m<n. P m \<Longrightarrow> P n) \<Longrightarrow> P n"; |
274 theorem nat_less_induct: "(\<And>n::nat. \<forall>m<n. P m \<Longrightarrow> P n) \<Longrightarrow> P n"; |
275 by(insert induct_lem, blast); |
275 by(insert induct_lem, blast); |
276 |
276 |
277 text{* |
277 text{* |
|
278 |
278 Finally we should mention that HOL already provides the mother of all |
279 Finally we should mention that HOL already provides the mother of all |
279 inductions, \emph{wellfounded induction} (@{thm[source]wf_induct}): |
280 inductions, \textbf{wellfounded |
280 @{thm[display]"wf_induct"[no_vars]} |
281 induction}\indexbold{induction!wellfounded}\index{wellfounded |
281 where @{term"wf r"} means that the relation @{term"r"} is wellfounded. |
282 induction|see{induction, wellfounded}} (@{thm[source]wf_induct}): |
|
283 @{thm[display]wf_induct[no_vars]} |
|
284 where @{term"wf r"} means that the relation @{term r} is wellfounded |
|
285 (see \S\ref{sec:wellfounded}). |
282 For example, theorem @{thm[source]nat_less_induct} can be viewed (and |
286 For example, theorem @{thm[source]nat_less_induct} can be viewed (and |
283 derived) as a special case of @{thm[source]wf_induct} where |
287 derived) as a special case of @{thm[source]wf_induct} where |
284 @{term"r"} is @{text"<"} on @{typ"nat"}. For details see the library. |
288 @{term r} is @{text"<"} on @{typ nat}. The details can be found in the HOL library. |
|
289 For a mathematical account of wellfounded induction see, for example, \cite{Baader-Nipkow}. |
285 *}; |
290 *}; |
286 |
291 |
287 (*<*) |
292 (*<*) |
288 end |
293 end |
289 (*>*) |
294 (*>*) |