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 $\mathbb{N}$.  Denote

$$C=\{x\in \mathbb{N}\mathrm{⋮}x\le 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  .  On the other , we must have  $c\le a_0$.  Consequently,  $c=a_0$  and therefore

$$a_0=c\le a\forall a\in A.$$

Hence, $A$ has the least number $a_0$.  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