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 ([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).