|
|
|
Viewing Version
13
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-21 20:54:29 |
| Classification: |
msc:03E25 |
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic} |
Content:
\PMlinkescapeword{moment's}
\PMlinkescapeword{complete}
The principal of finite induction, also known as ``mathematical induction," is commonly formulated in two ways. Both are equivalent. The first formulation is known as ``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 ``base case" and the implication $P(n)\Rightarrow P(n+1)$ is called the ``inductive step." In an inductive proof, one uses the term ``induction hypothesis" or ``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 ``strong," or ``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:
\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 ``well-ordering principle for natural numbers." (Note that this is not the same thing as the ``well-ordering principle," which is equivalent to the axiom of choice and has nothing to do with induction.) |
|
|
|
|
|
