## You are here

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

## Primary tabs

# 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\leq b$. Suppose not, then

$(*)\ \ \ \ \ \forall a\in S,\exists b\in S\ \ b<a.$ |

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<n$, $m\in\mathbb{N}\setminus S$. If $n\in S$, then (*) implies that there is an element $b\in S$ such that $b<n$. This would be incompatible with the assumption that for all natural numbers $m<n$, $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.

## Mathematics Subject Classification

03E25*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections