# 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 $$ 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 $$ already entails $P(0)$ since the statement $$ 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 |