# 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{\vdots}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 |