View source for 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|totally ordered set]] satisfying the minimum condition.

The concept of a well-ordered set was introduced by G. Cantor ([[#References|[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|lexicographic order]]. A totally ordered set is well-ordered if and only if it contains no subset that is [[Anti-isomorphism of partially ordered sets|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|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 theorem|'''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 type|Order types]] of well-ordered sets are called [[Ordinal number|'''ordinal numbers''']].

====References====

<table>
<TR><TD valign="top">[1]</TD><TD valign="top">
G. Cantor, “Über unendliche, lineaire Punktmannigfaltigkeiten”, ''Math. Ann.'', '''21''' (1883), pp. 51–58.</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">
P.S. Aleksandrov, “Einführung in die Mengenlehre und die Theorie der reellen Funktionen”, Deutsch. Verlag Wissenschaft. (1956). (Translated from Russian)</TD></TR>
<TR><TD valign="top">[3]</TD><TD valign="top">
F. Hausdorff, “Grundzüge der Mengenlehre”, Leipzig (1914). (Reprinted (incomplete) English translation: Set theory, Chelsea (1978))</TD></TR>
<TR><TD valign="top">[4]</TD><TD valign="top">
N. Bourbaki, “Elements of mathematics. Theory of sets”, Addison-Wesley (1968). (Translated from French)</TD></TR>
<TR><TD valign="top">[5]</TD><TD valign="top">
K. Kuratowski, A. Mostowski, “Set theory”, North-Holland (1968).</TD></TR>
</table>

====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 [[Totally ordered set|total ordering]] or linear ordering.

====References====

<table>
<TR><TD valign="top">[a1]</TD><TD valign="top">
A. Levy, “Basic set theory”, Springer (1979).</TD></TR>
</table>