|
|
|
Viewing Version
17
of
'principle of finite induction'
|
[ view 'principle of finite induction'
|
back to history
]
| Title of object: |
principle of finite induction |
| Canonical Name: |
PrincipleOfFiniteInduction |
| Type: |
Theorem |
| Created on: |
2001-10-16 08:43:17 |
| Modified on: |
2007-06-23 16:56:09 |
| Classification: |
msc:03E25 |
| Defines: |
induction hypothesis, inductive hypothesis |
Revision comment (for changes between this and next version):
| Changes for correction #13575 ('typo, base step'). |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic} |
Content:
\PMlinkescapeword{moment's}
\PMlinkescapeword{complete}
\PMlinkescapeword{equivalent}
\PMlinkescapeword{term}
\PMlinkescapeword{base}
\PMlinkescapeword{hypothesis}
\PMlinkescapeword{range}
The principal of finite induction, also known as \emph{mathematical induction}, is commonly formulated in two ways. Both are equivalent. The first formulation is known as \emph{weak} induction. It asserts that if a statement $P(n)$ holds for $n=0$ and if $P(n)\Rightarrow P(n+1)$, then $P(n)$ holds for all natural numbers $n$. The case $n=0$ is called the \emph{base case} and the implication $P(n)\Rightarrow P(n+1)$ is called the \emph{inductive step}. In an inductive proof, one uses the term \emph{induction hypothesis} or \emph{inductive hypothesis} to refer back to the statement $P(n)$ when one is trying to prove $P(n+1)$ from it.
The second formulation is known as \emph{strong}, or \emph{complete} induction. It asserts that if the implication $\forall n((\forall m < n P(m))\Rightarrow P(n))$ is true, then $P(n)$ is true for all natural numbers $n$. (Here, the quantifiers range over all natural numbers.) As we have formulated it, strong induction does not require a separate base case. Note that the implication $\forall n((\forall m < n P(m))\Rightarrow P(n)$ already entails $P(0)$ since the statement $\forall m<0 P(m)$ holds vacuously (there are no natural numbers less that zero).
A moment's thought will show that the first formulation (weak induction) is equivalent to the following:
\begin{quote}
Let $S$ be a set natural numbers such that
\begin{enumerate}
\item $0$ belongs to $S$, and
\item if $n$ belongs to $S$, so does $n+1$.
\end{enumerate}
Then $S$ is the set of all natural numbers.
\end{quote}
Similarly, strong induction can be stated:
\begin{quote}
If $S$ is a set of natural numbers such that $n$ belongs to $S$ whenever all numbers less than $n$ belong to $S$, then $S$ is the set of all natural numbers.
\end{quote}
The principle of finite induction can be derived from the fact that every nonempty set of natural numbers has a smallest element. This fact is known as the \emph{well-ordering principle for natural numbers}. (Note that this is not the same thing as the \emph{well-ordering principle}, which is equivalent to the axiom of choice and has nothing to do with induction.) |
|
|
|
|
|
