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.

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