# 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).

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 \}$.