Definition of Well-Ordered Sets
We first briefly review totally ordered sets and then formally define a special kind of totally ordered set called a well-ordered set. We then examine the meaning of a totally ordered set being well ordered from several perspectives.
A binary relation \(\leq\) defined on a set \(A\) is a total order if it satisfies reflexivity, antisymmetry, transitivity, and completeness, that is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in A:x\leq x\\
& \left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] \\
& \left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{align*}hold. If a total order \(\leq\) is defined on a set \(A\), the pair \[
\left( A,\leq\right)
\]is called a totally ordered set. When it is clear from the context that a totally ordered set is being discussed, we may simply write
\[
A
\]for the totally ordered set. For elements \(x,y\in A\) of a totally ordered set, if \[
x\leq y
\]holds, we say that \(x\) is less than or equal to \(y\), or equivalently that \(y\) is greater than or equal to \(x\).
Given a totally ordered set \(A\), define a new binary relation \(<\) on \(A\) by requiring, for arbitrary \(x,y\in A\), \[
x<y\Leftrightarrow\left( x\leq y\wedge x\not =y\right)
\]Then \(<\) is guaranteed to be a strict total order. That is, in addition to asymmetry and transitivity, \(<\) satisfies trichotomy, specifically, \begin{align*}
& \left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow\lnot\left(
y<x\right) \right] \\
& \left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge y<z\right) \Rightarrow x<z\right] \\
& \left( S_{3}\right) \ \forall x,y\in A:\text{exactly one of }x<y,\ y<x,\ x=y\text{ holds}\end{align*}For elements \(x,y\in A\) of a totally ordered set, if \[
x<y
\]holds, we say that \(x\) is less than \(y\), or equivalently that \(y\) is greater than \(x\).
If a set contains identical elements, those elements are not distinguished. Hence, when a set is given, we lose no generality by regarding all of its elements as distinct from one another. In view of this, the fact that the binary relation \(<\) defined from a total order \(\leq\) is a strict total order means that all elements of a totally ordered set lie along a single order under \(<\).
\left(\mathbb{R} ,\leq\right)
\]is obtained.
Let \(B\) be a nonempty subset of a totally ordered set \(A\). If a binary relation \(\leq_{B}\) on \(B\) is defined for arbitrary \(x,y\in B\) by \[
x\leq_{B}y\Leftrightarrow x\leq y,
\]then \(\leq_{B}\) is guaranteed to be a total order on \(B\). That is, \begin{align*}
& \left( O_{1}\right) \ \forall x\in B:x\leq_{B}x\\
& \left( O_{2}\right) \ \forall x,y\in B:\left[ \left( x\leq_{B}y\wedge y\leq_{B}x\right) \Rightarrow x=y\right] \\
& \left( O_{3}\right) \ \forall x,y,z\in B:\left[ \left( x\leq_{B}y\wedge y\leq_{B}z\right) \Rightarrow x\leq_{B}z\right] \\
& \left( O_{4}\right) \ \forall x,y\in B:\left( x\leq_{B}y\vee y\leq
_{B}x\right)
\end{align*}hold. Therefore,
\[
\left( B,\leq_{B}\right)
\]is a totally ordered set. In other words, restricting the initial set and terminal set of a total order \(\leq\) defined on \(A\) to a subset \(B\) of \(A\) leaves a total order. In many cases, the restricted total order \(\leq_{B}\) is denoted by the same symbol \(\leq\) as the original total order.
& \left(\mathbb{Q} ,\leq_{\mathbb{Q} }\right) \\
& \left(\mathbb{Z} ,\leq_{\mathbb{Z} }\right) \\
& \left(\mathbb{N} ,\leq_{\mathbb{N} }\right)
\end{align*}are all totally ordered sets. By convention, however, \(\leq_{\mathbb{Q} },\leq_{\mathbb{Z} },\leq_{\mathbb{N} }\) are all denoted simply by \(\leq\).
Let \(B\) be a nonempty subset of a totally ordered set \(A\). If some element \(b\in B\) is less than or equal to every element of \(B\), that is, if \[
\exists b\in B,\ \forall x\in B:b\leq x
\]holds, then \(b\) is called the least element of \(B\), and we write \[
b=\min B.
\]Thus, the least element \(\min B\) of \(B\) is defined as an element of \(B\) satisfying
\[
\forall x\in B:\min B\leq x.
\]The least element of \(B\) must belong to \(B\) itself. That is, \[
\min B\in B.
\]An element not belonging to \(B\) cannot be the least element of \(B\).
Conversely, for an element \(b\in B\), saying that \(b\) is not the least element of \(B\) means that \[
\exists x\in B:\lnot\left( b\leq x\right)
\]holds. Since \(\leq\) is a total order, \[
\lnot\left( b\leq x\right) \Leftrightarrow x<b
\]holds, so \(b\) is not the least element of \(B\) if and only if \[
\exists x\in X:x<b
\]holds. In other words, if there is an element of \(B\) smaller than \(b\in B\), then \(b\) is not the least element of \(B\).
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]Since the element \(0\in\left[ 0,1\right] \) satisfies \[
\forall x\in\left[ 0,1\right] :0\leq x,
\]we have
\[
\min\left[ 0,1\right] =0.
\]
A nonempty subset of a totally ordered set need not have a least element, as the following example shows.
A=\left\{ x\in\mathbb{R} \ |\ a<x<b\right\} .
\]To show that \(\min A\) does not exist, suppose that it does and derive a contradiction. If \(\min A\) exists, then by definition \(\min A\in A\), so \begin{equation}
a<\min A<b\quad \cdots (1)\end{equation}holds. Since \(\min A\) and \(a\) are both real numbers, by the density of the rational numbers there exists a rational number \(x\) satisfying \begin{equation}
a<x<\min A\quad \cdots (2)\end{equation}A rational number is a real number, so \(x\) is real. By \(\left( 1\right) \), \(\left( 2\right) \), and transitivity of \(<\), \[
a<x<b
\]holds, which by the definition of \(A\) means that \(x\in A\). Thus there exists an element \(x\) of \(A\) smaller than \(\min A\), contradicting the assumption that \(\min A\) is the least element of \(A\). Therefore \(\min A\) does not exist.
We have seen that a nonempty subset of a totally ordered set \(A\) need not have a least element. Conversely, if every nonempty subset of a totally ordered set \(A\) has a least element, that is, if \[
\forall B\subset A:\left( B\not =\phi\Rightarrow\exists\min B\right)
\]holds, then \(A\) is called a well-ordered set.
A=\left\{ x\in\mathbb{R} \ |\ a<x<b\right\} .
\]The set \(A\) is a nonempty subset of \(\mathbb{R} \), but as shown above, \(\min A\) does not exist. Therefore, \(\mathbb{R} \) is not a well-ordered set.
This is the definition of a well-ordered set. What does it mean for a totally ordered set to be well ordered? What are some concrete examples of totally ordered sets that are well ordered? We consider these questions in turn.
Intuitive Meaning of Well-Ordered Sets
We first use a finite set to explain the intuitive meaning of a well-ordered set.
When we count objects, we usually do not count them in a random order. Rather, we often arrange the objects to be counted and count them one by one in order.
\[
A=\left\{ a,b,c\right\} ,
\]we may arrange the elements in a line as
\[
a<b<c
\]and count them from left to right as
\[
1\rightarrow2\rightarrow3.
\]We then find that the number of elements of \(A\) is \(3\).
As the example suggests, there is a close relationship between counting objects and ordering them.
With an eye toward generalization, we now systematize the process of counting the elements of a set by using the preceding example.
\[
A=\left\{ a,b,c\right\} ,
\]we first introduce a total order \(\leq\) on \(A\). A total order allows all elements to be arranged along a single order. Here we suppose that they are ordered as \[
a<b<c.
\]We then count the elements according to this order.
- At the initial stage we have the empty set \(\phi\), which contains \(0\) elements.
- By adding the first element \(a\) to the set \(\phi\), which has \(0\) elements, we obtain the set \(\left\{ a\right\} \), which has \(0+1=1\) element.
- By adding the next element \(b\) to the set \(\left\{ a\right\} \), which has \(1\) element, we obtain \(\left\{ a,b\right\} \), which has \(1+1=2\) elements.
- By adding the next element \(c\) to the set \(\left\{ a,b\right\} \), which has \(2\) elements, we obtain \(\left\{ a,b,c\right\} \), namely \(A\), which has \(2+1=3\) elements.
- Therefore, the set \(A\) has \(3\) elements.
For this process to proceed without interruption, the set \(A\) must satisfy the following two conditions.
First, all elements of \(A\) must be arranged along a single order, so \(A\) must be a totally ordered set. That is, a total order \(\leq\) must be defined on \(A\).
In the preceding example, while counting the elements of the finite set \(A\) one by one, we successively generated the subsets
\[
\phi\rightarrow\left\{ a\right\} \rightarrow\left\{ a,b\right\}
\rightarrow\left\{ a,b,c\right\} .
\]These sets are called initial segments of \(A\). We generated the new initial segment \(\left\{ a\right\} \) by adding the element \(a\) to the initial segment \(\phi\), then generated \(\left\{ a,b\right\} \) by adding \(b\) to \(\left\{ a\right\} \), and finally generated \(\left\{ a,b,c\right\} \), that is, \(A\), by adding \(c\) to \(\left\{ a,b\right\} \). For a finite set \(A\), repeated application of this operation reaches the whole set \(A\).
For the process to proceed without interruption, it must be possible to identify, for each initial segment, one element that should be added next. We call the element to be added to an initial segment the immediate successor of that initial segment.%
$$\begin{array}{cc}\hline \text{Initial segment} & \text{Immediate successor}\\\hline \phi & a\\\hline \left\{ a\right\} & b\\\hline \left\{ a,b\right\} & c\\\hline \end{array}$$
As the preceding discussion shows, to count the elements of a finite set \(A\) one by one through this process, it is not enough for \(A\) merely to be totally ordered. For each initial segment other than \(A\) itself, the next element to be added must be uniquely identifiable. In the finite case, if this property holds, then starting from the empty set and adding one element at a time to successive initial segments eventually reaches the whole set \(A\).
The concept of a well order generalizes this kind of structure to arbitrary sets. Although we used a finite set in the preceding example, from this point onward we carry out the same discussion for general totally ordered sets, including infinite sets.
Initial and Final Segments of Totally Ordered Sets
Let \(a\in A\) be an element of a totally ordered set \(A\). The set consisting of all elements of \(A\) less than or equal to \(a\) is denoted by \[
A_{\leq a}=\left\{ x\in A\ |\ x\leq a\right\}
\]and is called the weak initial segment of \(A\) with respect to \(a\), or the weak lower contour set of \(A\) with respect to \(a\).
\[
A=\left\{ a,b,c\right\}
\]and suppose that the total order \(\leq\) on \(A\) satisfies \[
a<b<c.
\]The weak initial segments with respect to the elements of \(A\) are \begin{align*}
A_{\leq a} & =\left\{ a\right\} \\
A_{\leq b} & =\left\{ a,b\right\} \\
A_{\leq c} & =\left\{ a,b,c\right\} .
\end{align*}
Let \(a\in A\) be an element of a totally ordered set \(A\). The set consisting of all elements of \(A\) strictly less than \(a\) is denoted by \[
A_{<a}=\left\{ x\in A\ |\ x<a\right\}
\]and is called the strict initial segment of \(A\) with respect to \(a\), or the strict lower contour set of \(A\) with respect to \(a\).
\[
A=\left\{ a,b,c\right\}
\]and suppose that
\[
a<b<c.
\]Then
\begin{align*}
A_{<a} & =\phi\\
A_{<b} & =\left\{ a\right\} \\
A_{<c} & =\left\{ a,b\right\} .
\end{align*}
Let \(a\in A\) be an element of a totally ordered set \(A\). The set consisting of all elements of \(A\) greater than or equal to \(a\) is denoted by \[
A_{\geq a}=\left\{ x\in A\ |\ x\geq a\right\}
\]and is called the weak final segment of \(A\) with respect to \(a\), or the weak upper contour set of \(A\) with respect to \(a\).
\[
A=\left\{ a,b,c\right\}
\]and suppose that
\[
a<b<c.
\]Then
\begin{align*}
A_{\geq a} & =\left\{ a,b,c\right\} \\
A_{\geq b} & =\left\{ b,c\right\} \\
A_{\geq c} & =\left\{ c\right\} .
\end{align*}
Let \(a\in A\) be an element of a totally ordered set \(A\). The set consisting of all elements of \(A\) strictly greater than \(a\) is denoted by \[
A_{>a}=\left\{ x\in A\ |\ x>a\right\}
\]and is called the strict final segment of \(A\) with respect to \(a\), or the strict upper contour set of \(A\) with respect to \(a\).
\[
A=\left\{ a,b,c\right\}
\]and suppose that
\[
a<b<c.
\]Then
\begin{align*}
A_{>a} & =\left\{ b,c\right\} \\
A_{>b} & =\left\{ c\right\} \\
A_{>c} & =\phi.
\end{align*}
Immediate Predecessors and Immediate Successors of Elements of Totally Ordered Sets
Let \(x,y\in A\) be two elements of a totally ordered set. If there exists an element \(z\in A\) satisfying \[
\exists z\in A:\left( x<z<y\right) \vee\left( y<z<x\right) ,
\]that is, if \(z\) is greater than \(x\) and less than \(y\), or greater than \(y\) and less than \(x\), then such a \(z\) is called an element between \(x\) and \(y\).
Let \(x,y\in A\) be two elements of a totally ordered set. If \(y\) is greater than \(x\) and there is no element between \(x\) and \(y\), that is, if \begin{align*}
& \left( a\right) \ x<y\\
& \left( b\right) \ \forall z\in A:\lnot\left( x<z<y\right)
\end{align*}both hold, then \(x\) is called the immediate predecessor of \(y\). Equivalently, \(y\) is called the immediate successor of \(x\).
An element of a totally ordered set need not have an immediate predecessor or an immediate successor, as the following example shows.
\[
A=\left\{ a,b,c\right\}
\]and suppose that
\[
a<b<c.
\]The immediate successor of \(a\) is \(b\), and the immediate successor of \(b\) is \(c\). However, \(c\) has no immediate successor. Likewise, the immediate predecessor of \(c\) is \(b\), and the immediate predecessor of \(b\) is \(a\), but \(a\) has no immediate predecessor.
If an immediate predecessor or an immediate successor of an element of a totally ordered set exists, it is unique.
Immediate Successors of Subsets of Totally Ordered Sets
Let \(B\) be a subset of a totally ordered set \(A\). If an element \(a\in A\) satisfies
\begin{align*}
& \left( a\right) \ \forall x\in B:x<a\\
& \left( b\right) \ \forall x\in A:\left( x<a\Rightarrow\exists b\in B:x\leq b<a\right) ,
\end{align*}then \(a\) is greater than every element of \(B\), and for every element \(x\in A\) below \(a\), there is an element of \(B\) lying between \(x\) and \(a\) in the weak-strict sense \(x\leq b<a\). Such an element \(a\) is called the immediate successor of \(B\).
\[
A=\left\{ a,b,c\right\}
\]and suppose that
\[
a<b<c.
\]Since the empty set is a subset of every set,
\[
\phi\subset A.
\]For the element \(a\in A\), we have \begin{align*}
& \left( a\right) \ \forall x\in\phi:x<a\\
& \left( b\right) \ \forall x\in\left\{ a,b,c\right\} :\left(
x<a\Rightarrow\exists y\in\phi:x\leq y<a\right) .
\end{align*}Because \(x\in\phi\) is false, \(\left( a\right) \) is true, and because \(a\) is the least element of \(\left\{ a,b,c\right\} \), \(x<a\) is false for every \(x\in A\), so \(\left( b\right) \) is true. Hence the immediate successor of \(\phi\) is \(a\).
Next, for
\[
\left\{ a\right\} \subset A,
\]the element \(b\in A\) satisfies \begin{align*}
& \left( a\right) \ \forall x\in\left\{ a\right\} :x<b\\
& \left( b\right) \ \forall x\in\left\{ a,b,c\right\} :\left(
x<b\Rightarrow\exists y\in\left\{ a\right\} :x\leq y<b\right) ,
\end{align*}so the immediate successor of \(\left\{ a\right\} \) is \(b\).
Likewise, for
\[
\left\{ a,b\right\} \subset A,
\]the element \(c\in A\) satisfies \begin{align*}
& \left( a\right) \ \forall x\in\left\{ a,b\right\} :x<c\\
& \left( b\right) \ \forall x\in\left\{ a,b,c\right\} :\left(
x<c\Rightarrow\exists y\in\left\{ a,b\right\} :x\leq y<c\right) ,
\end{align*}so the immediate successor of \(\left\{ a,b\right\} \) is \(c\).
Because a totally ordered set \(A\) is a subset of itself, we can ask whether \(A\) has an immediate successor. It does not.
Because the empty set is a subset of every set, we can also ask whether the empty set has an immediate successor. The empty set has an immediate successor if and only if the totally ordered set \(A\) has a least element.
A subset of a totally ordered set need not have an immediate successor, as the following example shows.
B=\left\{ x\in\mathbb{R} \ |\ x\leq1\right\} .
\]This subset has no immediate successor. Suppose, for contradiction, that \(a\in\mathbb{R} \) is an immediate successor of \(B\). Then \begin{align*}
& \left( a\right) \ \forall x\in B:x<a\\
& \left( b\right) \ \forall x\in\mathbb{R} :\left( x<a\Rightarrow\exists b\in B:x\leq b<a\right)
\end{align*}both hold. By the definition of \(B\) and condition \(\left( a\right) \), \[
a>1.
\]Then
\[
1<\frac{1+a}{2}<a
\]holds, but the existence of the real number \(\frac{1+a}{2}\) contradicts \(\left( b\right) \). Hence, by contradiction, \(B\) has no immediate successor.
If a subset of a totally ordered set has an immediate successor, that successor is unique.
For every \(a\in A\), the strict initial segment \(A_{<a}\) has an immediate successor, and that successor is \(a\). Since the immediate successor of a set, when it exists, is unique, \(a\) is the only immediate successor of \(A_{<a}\).
A_{<a}=\left\{ x\in A\ |\ x<a\right\} ,
\]has an immediate successor, and it is \(a\).
For elements \(a,b\in A\), \(b\) is the immediate successor of \(a\) if and only if \(b\) is the immediate successor of the weak initial segment \(A_{\leq a}\) generated by \(a\).
A_{\leq a}=\left\{ x\in A\ |\ x\leq a\right\}
\]is the weak initial segment generated by \(a\).
Initial Segments of Totally Ordered Sets
Let \(B\) be a subset of a totally ordered set \(A\). If \[
\forall x\in B,\ \forall y\in A:\left( y<x\Rightarrow y\in B\right)
\]holds, that is, if every element of \(A\) smaller than any chosen element of \(B\) also belongs to \(B\), then \(B\) is called an initial segment of \(A\).
\[
A=\left\{ a,b,c\right\}
\]and suppose that
\[
a<b<c.
\]Since the empty set is a subset of every set,
\[
\phi\subset A.
\]Because \(x\in\phi\) is false, the statement \[
\forall x\in\phi,\ \forall y\in A:\left( y<x\Rightarrow y\in\phi\right)
\]is true, so \(\phi\) is an initial segment of \(A\).
Next consider
\[
\left\{ a\right\} \subset A.
\]There is no element \(y\in A\) satisfying \(y<a\), so \[
\forall x\in\left\{ a\right\} ,\ \forall y\in A:\left( y<x\Rightarrow y\in\left\{ a\right\} \right)
\]is true. Hence \(\left\{ a\right\} \) is an initial segment of \(A\).
Next consider
\[
\left\{ a,b\right\} \subset A.
\]The statement
\[
\forall x\in\left\{ a,b\right\} ,\ \forall y\in A:\left( y<x\Rightarrow y\in\left\{ a,b\right\} \right)
\]is true, so \(\left\{ a,b\right\} \) is an initial segment of \(A\).
Finally,
\[
A\subset A
\]and
\[
\forall x\in A,\ \forall y\in A:\left( y<x\Rightarrow y\in A\right)
\]is true, so \(A\) is an initial segment of itself.
The empty set is an initial segment of every totally ordered set.
A totally ordered set \(A\) is an initial segment of itself.
Every weak initial segment generated by an element of a totally ordered set
\(A\) is an initial segment of \(A\).
A_{\leq a}=\left\{ x\in A\mid x\leq a\right\}
\]is an initial segment of \(A\).
Every strict initial segment generated by an element of \(A\) is also an initial segment of \(A\).
A_{<a}=\left\{ x\in A\mid x<a\right\}
\]is an initial segment of \(A\).
If an initial segment \(B\) of a totally ordered set \(A\) has an immediate successor \(a\), then \(B\) coincides with the strict initial segment \(A_{<a}\).
B=A_{<a},
\]where
\[
A_{<a}=\left\{ x\in A\mid x<a\right\} .
\]
We summarize the discussion. For any \(a\in A\), the strict initial segment \(A_{<a}\) has immediate successor \(a\) and is an initial segment of \(A\). Conversely, if an initial segment \(B\) of \(A\) has immediate successor \(a\), then \(B=A_{<a}\). Thus, an initial segment \(B\) has immediate successor \(a\) if and only if \(B\) is the strict initial segment generated by \(a\).
B\text{ has an immediate successor}\Leftrightarrow\exists a\in A:B=A_{<a}.
\]Moreover, in this case the immediate successor of \(B\) is \(a\), where \[
A_{<a}=\left\{ x\in A\ |\ x<a\right\} .
\]
Well-Ordered Sets
Since every initial segment of a totally ordered set \(A\) is a subset of \(A\), we can ask whether each initial segment of \(A\) has an immediate successor. As shown above, \(A\) itself is an initial segment of \(A\), and \(A\) itself has no immediate successor. We therefore call \(A\) a well-ordered set if every initial segment of \(A\) other than \(A\) itself has an immediate successor.
\[
A=\left\{ a,b,c\right\}
\]and suppose that
\[
a<b<c.
\]As shown above, the initial segments of \(A\) are \(\phi,\left\{ a\right\} ,\left\{ a,b\right\} ,A\). Among these, the initial segments different from \(A\) all have immediate successors.%
$$\begin{array}{cc}\hline \text{Initial segment} & \text{Immediate successor}\\\hline \phi & a\\\hline \left\{ a\right\} & b\\\hline \left\{ a,b\right\} & c\\\hline \end{array}$$
Therefore, \(A\) is well ordered.
Conversely, if some initial segment of a totally ordered set \(A\), other than \(A\) itself, has no immediate successor, then \(A\) is not well ordered. Thus, not every totally ordered set is well ordered.
B=\left\{ x\in\mathbb{R} \ |\ x\leq1\right\}
\]is an initial segment of \(\mathbb{R} \) different from \(\mathbb{R} \) itself, but, as shown above, \(B\) has no immediate successor. Therefore, \(\mathbb{R} \) is not well ordered.
In a well-ordered set, the next element after any initial segment other than the whole set is uniquely determined. Consequently, for a finite well-ordered set, starting from the empty set and repeatedly adding the immediate successor of each initial segment generates the whole set in the form
\[
\phi\rightarrow\left\{ x_{1}\right\} \rightarrow\left\{ x_{1},x_{2}\right\} \rightarrow\left\{ x_{1},x_{2},x_{3}\right\} \rightarrow
\cdots.
\]As a result, the number of elements of \(A\) can be counted without interruption as \[
0\rightarrow1\rightarrow2\rightarrow3\rightarrow\cdots.
\]
For an infinite well-ordered set, however, it is not always possible to arrange all elements in an order-preserving sequence indexed by the natural numbers,
\[
x_{1}<x_{2}<x_{3}<\cdots.
\]There may also be initial segments that cannot be reached by finitely many stages of adding one element at a time. Nevertheless, in a well-ordered set, whenever uncounted elements remain, the least among them can be uniquely determined as the next element to be selected. In this sense, as in the finite case, the elements of a well-ordered set can be selected successively according to the order.
For an infinite set, however, this process need not be completed using only finite stages represented by natural numbers. Thus, when we say that the elements of an infinite well-ordered set are “counted in order,” this does not necessarily mean that every element can be assigned a position among
\[
1,2,3,\cdots.
\]More generally, it means that the elements can be selected successively according to the well order, always choosing the least remaining element.
Alternative Definitions of Well-Ordered Sets
A well-ordered set can be characterized in several equivalent ways.
- \(A\) is well ordered; that is, every initial segment of \(A\) other than \(A\) itself has an immediate successor.
- Every initial segment of \(A\) other than \(A\) itself is a strict initial segment with respect to some element of \(A\). That is, for every initial segment \(B\) of \(A\) with \(B\neq A\), \[
\exists a\in A:B=A_{<a}.
\] - Every nonempty subset of \(A\) has a least element.
Concrete Examples of Well-Ordered Sets: Finite Sets
If a totally ordered set is finite, then it is guaranteed to be well ordered.
\[
A=\left\{ a,b,c\right\}
\]and suppose that
\[
a<b<c.
\]Since \(A\) is finite, it is well ordered. Its initial segments and their immediate successors are as follows. $$\begin{array}{cc}\hline \text{Initial segment} & \text{Immediate successor}\\\hline \phi & a\\\hline \left\{ a\right\} & b\\\hline \left\{ a,b\right\} & c\\\hline \end{array}$$ Thus the initial segments can be generated successively as
\[
\phi\rightarrow\left\{ a\right\} \rightarrow\left\{ a,b\right\}
\rightarrow A,
\]and the number of elements of \(A\) can be counted without interruption as \[
0\rightarrow1\rightarrow2\rightarrow3.
\]
Concrete Examples of Well-Ordered Sets: The Natural Numbers
If the usual order \(\leq\) is defined on the set of all natural numbers \(\mathbb{N} \), then the totally ordered set \(\left(\mathbb{N} ,\leq\right) \) is obtained, and it is well ordered.
For the natural numbers
\[\mathbb{N} =\left\{ 1,2,3,\cdots\right\} ,
\]under the usual order \(\leq\), all natural numbers can be arranged in the order \[
1<2<3<\cdots.
\]By the preceding proposition, \(\left(\mathbb{N} ,\leq\right) \) is well ordered. Thus, starting from the empty set \(\phi\) and adding the immediate successor of each initial segment, we can generate \[
\phi\rightarrow\left\{ 1\right\} \rightarrow\left\{ 1,2\right\}
\rightarrow\left\{ 1,2,3\right\} \rightarrow\cdots.
\]Consequently, the number of natural numbers can be counted without interruption as
\[
0\rightarrow1\rightarrow2\rightarrow3\rightarrow\cdots.
\]
Concrete Example of a Well-Ordered Set That Cannot Be Counted in Order by the Natural Numbers
Even if a set is well ordered, it need not be possible to count all of its elements in an order-preserving way by the natural numbers. The following example shows this.
A=\mathbb{N} \cup\left\{ \omega\right\} .
\]Define an order \(\leq\) on \(A\) so that it agrees with the usual order on pairs of natural numbers, and define the relation between natural numbers and \(\omega\) by \[
\forall n\in\mathbb{N} :n<\omega.
\]Thus the elements of \(A\) are ordered as \[
1<2<3<\cdots<\omega.
\]Then \(\left( A,\leq\right) \) is well ordered (see the exercise). However, it is impossible to count all elements of \(A\) in an order-preserving way in the form \[
x_{1}<x_{2}<x_{3}<\cdots.
\]Suppose, to derive a contradiction, that such an enumeration is possible. Since \(\omega\in A\), there must exist some \(k\in\mathbb{N} \) such that \[
x_{k}=\omega.
\]But because
\[
1<2<3<\cdots<\omega,
\]every natural number must appear before \(\omega\). Thus infinitely many natural numbers would have to appear before \(x_{k}=\omega\). On the other hand, only \[
x_{1},x_{2},\ldots,x_{k-1}\]appear before \(x_{k}\), and there are only \(k-1\) of them. This is a contradiction.
As this example shows, being well ordered does not mean that every element can be assigned a position in the natural-number order
\[
1,2,3,\ldots.
\]What is required for a set to be well ordered is that every nonempty subset have a least element. Order-preserving enumerability by the natural numbers is a stronger property.
Exercises
A=\left\{ \sqrt{2},\sqrt{3},\sqrt{4},\sqrt{5},\sqrt{6},\sqrt{7}\right\} .
\]Is \(\left( A,\leq\right) \) well ordered? Discuss.
A=\left\{ \frac{1}{x}\ |\ x\in\mathbb{N} \wedge x\leq100\right\} .
\]Is \(\left( A,\leq\right) \) well ordered? Discuss.
A=\left\{ x\ |\ x\in\mathbb{Q} \wedge x>5\right\} .
\]Is \(\left( A,\leq\right) \) well ordered? Discuss.
\left[ 0,1\right] =\left\{ x\in\mathbb{R} \ |\ 0\leq x\leq1\right\} .
\]Is \(\left( \left[ 0,1\right] ,\leq\right) \) well ordered? Discuss.
m\preceq n\Leftrightarrow n\leq m.
\]Here \(\leq\) on the right-hand side is the usual order on the natural numbers. Show that \(\left(\mathbb{N} ,\preceq\right) \) is a totally ordered set but is not well ordered.
\[
A=\left\{ \frac{1}{n}\ |\ n\in\mathbb{N}\right\}
\]with the restriction of the usual order \(\leq\) on the real numbers. Show that \(\left( A,\leq\right) \) is a totally ordered set but not a well-ordered set.
(m,n)\preceq(p,q)\Leftrightarrow\left[ m<p\vee\left( m=p\wedge n\leq q\right) \right] .
\]
- Show that \(\preceq\) is a total order.
- Show that \(\left(\mathbb{N} \times\mathbb{N} ,\preceq\right) \) is well ordered.
- Show that the elements of this well-ordered set cannot all be enumerated in an order-preserving form
\[
x_{1}\prec x_{2}\prec x_{3}\prec\cdots.
\]
\[
A=\mathbb{N} \cup\{\omega\},
\]where \(\omega\notin\mathbb{N} \). Define an order \(\leq_{A}\) on \(A\) so that it agrees with the usual order on pairs of natural numbers and also satisfies \[
\forall n\in\mathbb{N} :n<_{A}\omega.
\]
- Show that \(\left( A,\leq_{A}\right) \) is well ordered.
- Show that \(\omega\) has no immediate predecessor.
- Show that the finite initial segments
\[
\phi,\ \{1\},\ \{1,2\},\ \{1,2,3\},\ldots
\]do not exhaust all initial segments of \(A\) different from \(A\) itself.
