# 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

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, $m\in\mathbb{N}\setminus S$. If $n\in S$, then (*) implies that there is an element $b\in S$ such that $b. This would be incompatible with the assumption that for all natural numbers $m, $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 WellorderingPrincipleForNaturalNumbersProvenFromThePrincipleOfFiniteInduction 2013-03-22 16:38:02 2013-03-22 16:38:02 CWoo (3771) CWoo (3771) 5 CWoo (3771) Proof msc 03E25 NaturalNumbersAreWellOrdered