principle of finite induction

The principle 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 or base step 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<nP(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<nP(m))\Rightarrow P(n)$ already entails $P(0)$ since the statement $\forall m<0P(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:

Let $S$ be a set natural numbers such that

1.

$0$ belongs to $S$ , and

2.

if $n$ belongs to $S$ , so does $n+1$ .

Then $S$ is the set of all natural numbers.

Similarly, strong induction can be stated:

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.

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.)

Title	principle of finite induction
Canonical name	PrincipleOfFiniteInduction
Date of creation	2013-03-22 11:46:41
Last modified on	2013-03-22 11:46:41
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	24
Author	CWoo (3771)
Entry type	Theorem
Classification	msc 03E25
Classification	msc 00-02
Related topic	TransfiniteInduction
Related topic	AnExampleOfMathematicalInduction
Related topic	Induction
Related topic	WellFoundedInduction
Defines	induction hypothesis
Defines	inductive hypothesis
Defines	base case
Defines	base step