# principle of finite induction proven from the well-ordering principle for natural numbers

We give a proof for the “strong” formulation.

Let $S$ be a set of natural numbers such that $n$ belongs to $S$ whenever all numbers less than $n$ belong to $S$ (i.e., assume $$, where the quantifiers^{} range over all natural numbers^{}). For indirect proof, suppose that $S$ is not the set of natural numbers $\mathbb{N}$. That is, the complement^{} $\mathbb{N}\setminus S$ is nonempty. The well-ordering principle for natural numbers says that $\mathbb{N}\setminus S$ has a smallest element; call it $a$. By assumption^{}, the statement $$ holds. Equivalently, the contrapositive statement $$ holds. This gives a contradition since the element $a$ is an element of $\mathbb{N}\setminus S$ and is, moreover, the *smallest* element of $\mathbb{N}\setminus S$.

Title | principle of finite induction proven from the well-ordering principle for natural numbers |
---|---|

Canonical name | PrincipleOfFiniteInductionProvenFromTheWellorderingPrincipleForNaturalNumbers |

Date of creation | 2013-03-22 11:48:04 |

Last modified on | 2013-03-22 11:48:04 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 16 |

Author | CWoo (3771) |

Entry type | Proof |

Classification | msc 03E25 |

Classification | msc 37H10 |