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

Let $S$ be a nonempty set of natural numbers^{}. We show that there is an $a\in S$ such that for all $b\in S$, $a\le b$. Suppose not, then

$$ |

We will use the principle of finite induction (the strong form) to show that $S$ is empty, a contradition.

Fix any natural number $n$, and suppose that for all natural numbers $$, $m\in \mathbb{N}\setminus S$. If $n\in S$, then (*) implies that there is an element $b\in S$ such that $$. This would be incompatible with the assumption^{} that for all natural numbers $$, $m\in \mathbb{N}\setminus S$.
Hence, we conclude that $n$ is not in $S$.

Therefore, by induction^{}, no natural number is a member of $S$. The set is empty.

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

Canonical name | WellorderingPrincipleForNaturalNumbersProvenFromThePrincipleOfFiniteInduction |

Date of creation | 2013-03-22 16:38:02 |

Last modified on | 2013-03-22 16:38:02 |

Owner | CWoo (3771) |

Last modified by | CWoo (3771) |

Numerical id | 5 |

Author | CWoo (3771) |

Entry type | Proof |

Classification | msc 03E25 |

Related topic | NaturalNumbersAreWellOrdered |