natural numbers are well-ordered

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

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

Proof.  Let A be an arbitrary non-empty subset of .  Denote


Then of course,  0C.  There exists surely an element c of C such that  c+1C,  since otherwise the inductionMathworldPlanetmath property would imply that  C=.  Because  c+1C,  there is a number a0 of the set A such that  a0<c+1.  On the other , we must have  ca0.  Consequently,  c=a0  and therefore


Hence, A has the least number a0.  Q.E.D.

Title natural numbers are well-ordered
Canonical name NaturalNumbersAreWellordered
Date of creation 2013-03-22 19:02:36
Last modified on 2013-03-22 19:02:36
Owner pahio (2872)
Last modified by pahio (2872)
Numerical id 6
Author pahio (2872)
Entry type Theorem
Classification msc 03E10
Related topic AVariantDerivationOfWellOrderedSet
Related topic WellOrderedSet
Related topic WellOrderingPrincipleForNaturalNumbersProvenFromThePrincipleOfFiniteInduction