# natural numbers are well-ordered

In many proofs, one needs the following property of positive and nonnegative integers:

Any non-empty set of natural numbers contains a least number.

Proof.  Let $A$ be an arbitrary non-empty subset of $\mathbb{N}$.  Denote

 $C\;=\;\{x\in\mathbb{N}\,\vdots\;\;x\leq a\;\forall a\in A\}.$

Then of course,  $0\in C$.  There exists surely an element $c$ of $C$ such that  $c\!+\!1\notin C$,  since otherwise the induction  property would imply that  $C=\mathbb{N}$.  Because  $c\!+\!1\notin C$,  there is a number $a_{0}$ of the set $A$ such that  $a_{0}.  On the other , we must have  $c\leq a_{0}$.  Consequently,  $c=a_{0}$  and therefore

 $a_{0}\;=\;c\;\leq\;a\;\;\forall a\in A.$

Hence, $A$ has the least number $a_{0}$.  Q.E.D.

Title natural numbers are well-ordered NaturalNumbersAreWellordered 2013-03-22 19:02:36 2013-03-22 19:02:36 pahio (2872) pahio (2872) 6 pahio (2872) Theorem msc 03E10 AVariantDerivationOfWellOrderedSet WellOrderedSet WellOrderingPrincipleForNaturalNumbersProvenFromThePrincipleOfFiniteInduction