# Well-ordered set

A set $\mathbb{P}$ equipped with a binary relation $\leq$ that satisfies the following conditions:

1. For any $x,y \in \mathbb{P}$, either $x \leq y$ or $y \leq x$.
2. For any $x,y \in \mathbb{P}$, if $x \leq y$ and $y \leq x$, then $x = y$.
3. For any $x,y,z \in \mathbb{P}$, if $x \leq y$ and $y \leq z$, then $x \leq z$.
4. In any non-empty subset $X \subseteq \mathbb{P}$, there exists an element $a$ such that $a \leq x$ for all $x \in X$.

Thus, a well-ordered set is a totally ordered set satisfying the minimum condition.

The concept of a well-ordered set was introduced by G. Cantor (). An example of a well-ordered set is the naturally ordered set of natural numbers. On the other hand, the interval of real numbers $[0,1]$ with the natural order is not well-ordered. Any subset of a well-ordered set is itself well-ordered. The Cartesian product of a finite number of well-ordered sets is well-ordered by the relation of lexicographic order. A totally ordered set is well-ordered if and only if it contains no subset that is anti-isomorphic to the set of natural numbers.

The smallest element of a well-ordered set $\mathbb{P}$ is denoted by zero (the symbol $0$). For any element $a \in \mathbb{P}$, the set $$[0,a) \stackrel{\text{df}}{=} \{ x \mid x \in \mathbb{P}, x < a \}$$ is called an initial segment of $\mathbb{P}$. For any element $a$ that is not the largest element in $\mathbb{P}$, there exists an element immediately following it; it is usually denoted by $a + 1$. An element of a well-ordered set that has no element immediately preceding it is called a limit element.

The Comparison Theorem. For any two well-ordered sets $\mathbb{P}_{1}$ and $\mathbb{P}_{2}$, one and only one of the following situations occurs: (a) $\mathbb{P}_{1}$ is isomorphic to $\mathbb{P}_{2}$; (b) $\mathbb{P}_{1}$ is isomorphic to an initial segment of $\mathbb{P}_{2}$; or (c) $\mathbb{P}_{2}$ is isomorphic to an initial segment of $\mathbb{P}_{1}$.

If the axiom of choice is included in the axioms of set theory, it may be shown that it is possible to impose on any non-empty set an order relation that converts it into a well-ordered set (i.e., any non-empty set can be well-ordered). This theorem, known as Zermelo’s Well-Ordering Theorem, is in fact equivalent to the axiom of choice. Zermelo’s Well-Ordering Theorem and the Comparison Theorem form the basis for the comparison between cardinalities of sets. Order types of well-ordered sets are called ordinal numbers.

How to Cite This Entry:
Well-ordered set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Well-ordered_set&oldid=40154
This article was adapted from an original article by B.A. EfimovT.S. Fofanova (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article