# Well-ordered set

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

- For any $ x,y \in \mathbb{P} $, either $ x \leq y $ or $ y \leq x $.
- For any $ x,y \in \mathbb{P} $, if $ x \leq y $ and $ y \leq x $, then $ x = y $.
- For any $ x,y,z \in \mathbb{P} $, if $ x \leq y $ and $ y \leq z $, then $ x \leq z $.
- 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 ([1]). 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**.

#### References

[1] |
G. Cantor, “Über unendliche, lineaire Punktmannigfaltigkeiten”, Math. Ann., 21 (1883), pp. 51–58. |

[2] | P.S. Aleksandrov, “Einführung in die Mengenlehre und die Theorie der reellen Funktionen”, Deutsch. Verlag Wissenschaft. (1956). (Translated from Russian) |

[3] | F. Hausdorff, “Grundzüge der Mengenlehre”, Leipzig (1914). (Reprinted (incomplete) English translation: Set theory, Chelsea (1978)) |

[4] | N. Bourbaki, “Elements of mathematics. Theory of sets”, Addison-Wesley (1968). (Translated from French) |

[5] | K. Kuratowski, A. Mostowski, “Set theory”, North-Holland (1968). |

#### Comments

In the definition above, Condition (3) (the transitivity of the order relation) is in fact redundant: It follows from the existence of a least element in the subset $ \{ x,y,z \} $.

Sometimes, a well-ordered set is called a **totally well-ordered set**, reflecting the fact that the ordering is a total ordering or linear ordering.

#### References

[a1] | A. Levy, “Basic set theory”, Springer (1979). |

**How to Cite This Entry:**

Well-ordered set.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Well-ordered_set&oldid=40154