Well-ordering principle

In mathematics, the well-ordering principle, also called the well-ordering property or least natural number principle, states that every non-empty subset of the nonnegative integers contains a least element, also called a smallest element. In other words, if ${\displaystyle A}$ is a nonempty subset of the nonnegative integers, then there exists an element of ${\displaystyle A}$ which is less than, or equal to, any other element of ${\displaystyle A}$. Formally, ${\displaystyle \forall A\left[\left(A\subseteq \mathbb {Z} _{\geq 0}\land A\neq \varnothing \right)\rightarrow \left(\exists m\in A\,\forall a\in A\,(m\leq a)\right)\right]}$. Most sources state this as an axiom or theorem about the natural numbers, but the phrase "natural number" was avoided here because of ambiguity over the inclusion of zero. The statement is true about the set of natural numbers ${\displaystyle \mathbb {N} }$ regardless whether it is defined as ${\displaystyle \mathbb {Z} _{\geq 0}}$ (nonnegative integers) or as ${\displaystyle \mathbb {Z} ^{+}}$ (positive integers), since one of Peano's axioms for ${\displaystyle \mathbb {N} }$, the induction axiom (or principle of mathematical induction), is logically equivalent to the well-ordering principle. Since ${\displaystyle \mathbb {Z} ^{+}\subseteq \mathbb {Z} _{\geq 0}}$ and the subset relation ${\displaystyle \subseteq }$ is transitive, the statement about ${\displaystyle \mathbb {Z} ^{+}}$ is implied by the statement about ${\displaystyle \mathbb {Z} _{\geq 0}}$.

The standard order on ${\displaystyle \mathbb {N} }$ is well-ordered by the well-ordering principle, since it begins with a least element, regardless whether it is 1 or 0. By contrast, the standard order on ${\displaystyle \mathbb {R} }$ (or on ${\displaystyle \mathbb {Z} }$) is not well-ordered by this principle, since there is no smallest negative number. According to Deaconu and Pfaff, the phrase "well-ordering principle" is used by some (unnamed) authors as a name for Zermelo's "well-ordering theorem" in set theory, according to which every set can be well-ordered. This theorem, which is not the subject of this article, implies that "in principle there is some other order on ${\displaystyle \mathbb {R} }$ which is well-ordered, though there does not appear to be a concrete description of such an order."