| Version 17 |
Version 16 |
| \PMlinkescapeword{moment's} |
\PMlinkescapeword{moment's} |
| \PMlinkescapeword{complete} |
\PMlinkescapeword{complete} |
| \PMlinkescapeword{equivalent} |
\PMlinkescapeword{equivalent} |
| \PMlinkescapeword{term} |
\PMlinkescapeword{term} |
| \PMlinkescapeword{base} |
\PMlinkescapeword{base} |
| \PMlinkescapeword{hypothesis} |
\PMlinkescapeword{hypothesis} |
| \PMlinkescapeword{range} |
\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 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).
|
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 natual 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: |
A moment's thought will show that the first formulation (weak induction) is equivalent to the following: |
| \begin{quote} |
\begin{quote} |
| Let $S$ be a set natural numbers such that |
Let $S$ be a set natural numbers such that |
| \begin{enumerate} |
\begin{enumerate} |
| \item $0$ belongs to $S$, and |
\item $0$ belongs to $S$, and |
| \item if $n$ belongs to $S$, so does $n+1$. |
\item if $n$ belongs to $S$, so does $n+1$. |
| \end{enumerate} |
\end{enumerate} |
| Then $S$ is the set of all natural numbers. |
Then $S$ is the set of all natural numbers. |
| \end{quote} |
\end{quote} |
|
|
| Similarly, strong induction can be stated: |
Similarly, strong induction can be stated: |
| \begin{quote} |
\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. |
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} |
\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.) |
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.) |
