Well-Ordered Sets

If every nonempty subset of a totally ordered set has a least element, the totally ordered set is called a well-ordered set. The total order defined on a well-ordered set is called a well-order.

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

Example (Totally Ordered Set)
If the usual order relation \(\leq\) is defined on the set of real numbers \(\mathbb{R} \), then the totally ordered set \[
\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.

Example (Totally Ordered Sets)
If the usual order \(\leq\) is defined on the set of real numbers \(\mathbb{R} \), then the totally ordered set \(\left(\mathbb{R} ,\leq\right) \) is obtained. Hence, for the nonempty subsets of \(\mathbb{R} \) consisting of the rational numbers \(\mathbb{Q} \), the integers \(\mathbb{Z} \), and the natural numbers \(\mathbb{N} \), respectively, \begin{align*}
& \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\).

Example (Least Element of a Totally Ordered Subset)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Consider the subset \[
\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.
\]
Example (Least Element of the Empty Set)
Because the empty set is a subset of every set, if a totally ordered set \(A\) is given, then \(\phi\subset A\). Does the empty set \(\phi\) have a least element? Suppose that \(\min\phi\) exists. By definition of a least element, we must have \(\min\phi\in\phi\), but this is impossible because the empty set has no elements. Hence, by contradiction, the empty set has no least element.

A nonempty subset of a totally ordered set need not have a least element, as the following example shows.

Example (A Totally Ordered Subset with No Least Element)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Choose arbitrary real numbers \(a,b\in\mathbb{R} \) satisfying \(a<b\), and define \[
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.

Example (The Real Line Is Not Well Ordered)
The usual order \(\leq\) on the set of real numbers \(\mathbb{R} \) is a total order. Choose arbitrary real numbers \(a,b\in\mathbb{R} \) satisfying \(a<b\), and define \[
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.

Example (Cardinality and Order)
When counting the number of elements in the finite set
\[
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.

Example (Cardinality and Order)
To count the number of elements in the finite set
\[
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.

  1. At the initial stage we have the empty set \(\phi\), which contains \(0\) elements.
  2. 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.
  3. 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.
  4. 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.
  5. 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\).

Example (Weak Initial Segments)
Let
\[
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\).

Example (Strict Initial Segments)
Let
\[
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\).

Example (Weak Final Segments)
Let
\[
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\).

Example (Strict Final Segments)
Let
\[
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.

Example (When an Immediate Predecessor or Immediate Successor Does Not Exist)
Let
\[
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.

Proposition (Uniqueness of Immediate Predecessors and Immediate Successors)
If an element \(x\in A\) of a totally ordered set \(\left( A,\leq\right) \) has an immediate predecessor, then it is unique. If \(x\) has an immediate successor, then it is unique.
Proof

Members-Only Content
【Log In】【Sign Up】

 

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

Example (Immediate Successors of Sets)
Let
\[
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.

Proposition (A Totally Ordered Set Has No Immediate Successor)
A totally ordered set \(\left( A,\leq\right) \) has no immediate successor.
Proof

Members-Only Content
【Log In】【Sign Up】

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.

Proposition (Necessary and Sufficient Condition for the Empty Set to Have an Immediate Successor)
A totally ordered set \(\left( A,\leq\right) \) has a least element if and only if the empty set \(\phi\subset A\) has an immediate successor.
Proof

Members-Only Content
【Log In】【Sign Up】

A subset of a totally ordered set need not have an immediate successor, as the following example shows.

Example (A Set with No Immediate Successor)
If the usual order \(\leq\) is defined on the real line \(\mathbb{R} \), then \(\left(\mathbb{R} ,\leq\right) \) is a totally ordered set. Consider \[
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.

Proposition (Uniqueness of the Immediate Successor of a Set)
If a subset \(B\subset A\) of a totally ordered set \(\left( A,\leq\right) \) has an immediate successor, then it is unique.
Proof

Members-Only Content
【Log In】【Sign Up】

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

Proposition (Immediate Successor of a Strict Initial Segment)
Let \(a\in A\) be arbitrary in a totally ordered set \(\left( A,\leq\right) \). The strict initial segment generated by \(a\), \[
A_{<a}=\left\{ x\in A\ |\ x<a\right\} ,
\]has an immediate successor, and it is \(a\).
Proof

Members-Only Content
【Log In】【Sign Up】

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

Proposition (Relationship Between Being the Immediate Successor of an Element and of a Set)
Let \(a,b\in A\) be arbitrary in a totally ordered set \(\left( A,\leq\right) \). Then \(b\) is the immediate successor of \(a\) if and only if \(b\) is the immediate successor of \(A_{\leq a}\), where \[
A_{\leq a}=\left\{ x\in A\ |\ x\leq a\right\}
\]is the weak initial segment generated by \(a\).
Proof

Members-Only Content
【Log In】【Sign Up】

 

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

Example (Initial Segments of a Totally Ordered Set)
Let
\[
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.

Proposition (The Empty Set Is an Initial Segment of a Totally Ordered Set)
For every totally ordered set \(\left( A,\leq\right) \), the empty set \(\phi\) is an initial segment of \(A\).
Proof

Members-Only Content
【Log In】【Sign Up】

A totally ordered set \(A\) is an initial segment of itself.

Proposition (A Totally Ordered Set Is an Initial Segment of Itself)
Every totally ordered set \(\left( A,\leq\right) \) is an initial segment of itself.
Proof

Members-Only Content
【Log In】【Sign Up】

Every weak initial segment generated by an element of a totally ordered set
\(A\) is an initial segment of \(A\).

Proposition (A Weak Initial Segment Is an Initial Segment)
Let \(a\in A\) be arbitrary in a totally ordered set \(\left( A,\leq\right) \). Then \[
A_{\leq a}=\left\{ x\in A\mid x\leq a\right\}
\]is an initial segment of \(A\).
Proof

Members-Only Content
【Log In】【Sign Up】

Every strict initial segment generated by an element of \(A\) is also an initial segment of \(A\).

Proposition (A Strict Initial Segment Is an Initial Segment)
Let \(a\in A\) be arbitrary in a totally ordered set \(\left( A,\leq\right) \). Then \[
A_{<a}=\left\{ x\in A\mid x<a\right\}
\]is an initial segment of \(A\).
Proof

Members-Only Content
【Log In】【Sign Up】

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

Proposition (Condition Under Which an Initial Segment Is a Strict Initial Segment)
Let \(B\) be an initial segment of a totally ordered set \(\left( A,\leq\right) \). If \(B\) has an immediate successor \(a\in A\), then \[
B=A_{<a},
\]where
\[
A_{<a}=\left\{ x\in A\mid x<a\right\} .
\]
Proof

Members-Only Content
【Log In】【Sign Up】

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

Proposition (Relationship Between Initial Segments and Strict Initial Segments)
Let \(B\) be an initial segment of a totally ordered set \(\left( A,\leq\right) \). Then \[
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.

Example (Well-Ordered Set)
Let
\[
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.

Example (A Totally Ordered Set That Is Not Well Ordered)
If the usual order \(\leq\) is defined on the real line \(\mathbb{R} \), then \(\left(\mathbb{R} ,\leq\right) \) is a totally ordered set. The subset \[
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.

Proposition (Equivalent Definitions of a Well-Ordered Set)
For a totally ordered set \(\left( A,\leq\right) \), the following three statements are equivalent.

  1. \(A\) is well ordered; that is, every initial segment of \(A\) other than \(A\) itself has an immediate successor.
  2. 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}.
    \]
  3. Every nonempty subset of \(A\) has a least element.
Proof

Members-Only Content
【Log In】【Sign Up】

 

Concrete Examples of Well-Ordered Sets: Finite Sets

If a totally ordered set is finite, then it is guaranteed to be well ordered.

Proposition (Every Finite Totally Ordered Set Is Well Ordered)
If a totally ordered set \(\left( A,\leq\right) \) is finite, then \(\left( A,\leq\right) \) is well ordered.
Proof

Members-Only Content
【Log In】【Sign Up】

Example (Every Finite Totally Ordered Set Is Well Ordered)
Let
\[
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.

Proposition (The Natural Numbers with the Usual Order Are Well Ordered)
Define the usual order \(\leq\) on the set of all natural numbers \(\mathbb{N} \). Then \(\left(\mathbb{N} ,\leq\right) \) is well ordered.
Proof

Members-Only Content
【Log In】【Sign Up】

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.

Example (A Well-Ordered Set That Cannot Be Counted in Order by the Natural Numbers)
Add to the set of natural numbers \(\mathbb{N} \) a new element \(\omega\) not belonging to \(\mathbb{N} \), and let \[
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

Problem (The Integers)
If the usual order \(\leq\) is defined on the set of integers \(\mathbb{Z} \), then the totally ordered set \(\left(\mathbb{Z} ,\leq\right) \) is obtained. Is \(\left(\mathbb{Z} ,\leq\right) \) well ordered? Discuss.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Well-Ordered Set)
Define the usual order \(\leq\) on \[
A=\left\{ \sqrt{2},\sqrt{3},\sqrt{4},\sqrt{5},\sqrt{6},\sqrt{7}\right\} .
\]Is \(\left( A,\leq\right) \) well ordered? Discuss.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Well-Ordered Set)
Define the usual order \(\leq\) on \[
A=\left\{ \frac{1}{x}\ |\ x\in\mathbb{N} \wedge x\leq100\right\} .
\]Is \(\left( A,\leq\right) \) well ordered? Discuss.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Well-Ordered Set)
Define the usual order \(\leq\) on \[
A=\left\{ x\ |\ x\in\mathbb{Q} \wedge x>5\right\} .
\]Is \(\left( A,\leq\right) \) well ordered? Discuss.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Well-Ordered Set)
Define the usual order \(\leq\) on \[
\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.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Subset of a Well-Ordered Set)
Let \(\left( A,\leq\right) \) be a well-ordered set and let \(B\subset A\) be a nonempty subset. Show that \(B\), with the order obtained by restricting \(\leq\) to \(B\), is also well ordered.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Reverse Order on the Natural Numbers)
Define a binary relation \(\preceq\) on \(\mathbb{N} \) by \[
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.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (A Set of Reciprocals)
Let
\[
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.
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (Well Ordering by Lexicographic Order)
Define the lexicographic order \(\preceq\) on \(\mathbb{N} \times\mathbb{N} \) by \[
(m,n)\preceq(p,q)\Leftrightarrow\left[ m<p\vee\left( m=p\wedge n\leq q\right) \right] .
\]
  1. Show that \(\preceq\) is a total order.
  2. Show that \(\left(\mathbb{N} \times\mathbb{N} ,\preceq\right) \) is well ordered.
  3. 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.
    \]
View Solution

Members-Only Content
【Log In】【Sign Up】

Problem (A Well-Ordered Set Obtained by Adding One Point After the Natural Numbers)
Consider
\[
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.
\]
  1. Show that \(\left( A,\leq_{A}\right) \) is well ordered.
  2. Show that \(\omega\) has no immediate predecessor.
  3. 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.
View Solution

Members-Only Content
【Log In】【Sign Up】

Discussion

To ask questions about this material or discuss it with other learners, you need to register as a member and log in.

  • Members can post comments
  • You can reply to other users
  • You can search and view past discussions
  • You can edit your posts later

At WIIS, we believe that all users are equal as learners, regardless of age, gender, educational background, occupation, or social status.

This is not a place to compete over knowledge, but a space to deepen understanding while respecting one another’s ideas. Questions and opinions are welcome, and you are also encouraged to ask openly about anything you do not understand.

To help maintain a constructive and welcoming learning environment, please review the guidelines before posting.

If you find a typo, broken link, or error in the content, please let us know using the form below.

User Posts Related to This Lesson

Table of Contents

MEMBERSHIP

Take your learning further.

Join WIIS to access
members-only content,
downloadable PDF textbooks,
AI Tutor, forums,
and other member benefits.

MEMBERS-ONLY CONTENT

Access exclusive materials designed for deeper learning.

PDF TEXTBOOKS

Download textbooks and study them anywhere.

AI Tutor

Use AI-powered support to deepen your understanding.

COMMUNITY FEATURES

Connect with other learners and join discussions and research.

ログイン

アカウントにログインして、学習ノートやブックマーク、投稿記事などを管理できます。

Recently Viewed Pages