2.4: Well Ordered Sets

A set of numbers is well ordered when each of its nonempty subsets has a minimum element. The Well Ordering Principle says, of course, that the set of nonnegative integers is well ordered, but so are lots of other sets, such as every finite set, or the sets \(r \mathbb{N}\) of numbers of the form \(rn\), where \(r\) is a positive real number and \(n \in \mathbb{N}\).

Well ordering commonly comes up in computer science as a method for proving that computations won’t run forever. The idea is to assign a value to the successive steps of a computation so that the values get smaller at every step. If the values are all from a well ordered set, then the computation can’t run forever, because if it did, the values assigned to its successive steps would define a subset with no minimum element. You’ll see several examples of this technique applied in Section 5.4 to prove that various state machines will eventually terminate.

Notice that a set may have a minimum element but not be well ordered. The set of nonnegative rational numbers is an example: it has a minimum element, zero, but it also has nonempty subsets that don’t have minimum elements—the positive rationals, for example.

The following theorem is a tiny generalization of the Well Ordering Principle.

Theorem \(\PageIndex{1}\)

For any nonnegative integer, \(n\), the set of integers greater than or equal to \(-n\) is well ordered.

This theorem is just as obvious as the Well Ordering Principle, and it would be harmless to accept it as another axiom. But repeatedly introducing axioms gets worrisome after a while, and it’s worth noticing when a potential axiom can actually be proved. We can easily prove Theorem 2.4.1 using the Well Ordering Principle:

Proof

Let \(S\) be any nonempty set of integers \(\geq -n\). Now add \(n\) to each of the elements in \(S\); let’s call this new set \(S + n\). Now \(S + n\) is a nonempty set of nonnegative integers, and so by the Well Ordering Principle, it has a minimum element, \(m\). But then it’s easy to see that \(m - n\) is the minimum element of \(S\). \(\quad \blacksquare\)

The definition of well ordering states that every subset of a well ordered set is well ordered, and this yields two convenient, immediate corollaries of Theorem 2.4.1:

Definition \(\PageIndex{2}\)

A lower bound (respectively, upper bound) for a set, \(S\), of real numbers is a number, \(b\), such that \(b \leq s\) (respectively, \(b \geq s\)) for every \(s \in S\).

Note that a lower or upper bound of set \(S\) is not required to be in the set.

Corollary 2.4.3. Any set of integers with a lower bound is well ordered.

Proof. A set of integers with a lower bound \(b \in \mathbb{R}\) will also have the integer \(n = \lfloor b \rfloor\) as a lower bound, where \(\lfloor b \rfloor\), called the floor of \(b\), is gotten by rounding down \(b\) to the nearest integer. So Theorem 2.4.1 implies the set is well ordered. \(\quad \blacksquare\)

Corollary 2.4.4. Any nonempty set of integers with an upper bound has a maximum element.

Proof. Suppose a set, \(S\), of integers has an upper bound \(b \in \mathbb{R}\). Now multiply each element of \(S\) by -1; let’s call this new set of elements \(-S\). Now, of course, \(-b\) is a lower bound of \(-S\). So \(-S\) has a minimum element \(-m\) by Corollary 2.4.3. But then it’s easy to see that \(m\) is the maximum element of \(S\). \(\quad \blacksquare\)

A Different Well Ordered Set (Optional)

Another example of a well ordered set of numbers is the set \(\mathbb{F}\) of fractions that can be expressed in the form \(n / (n + 1)\):

\[\nonumber \frac{0}{1}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \cdots, \frac{n}{n + 1}, \cdots\]

The minimum element of any nonempty subset of \(\mathbb{F}\) is simply the one with the minimum numerator when expressed in the form \(n / (n + 1)\).

Now we can define a very different well ordered set by adding nonnegative integers to numbers in \(\mathbb{F}\). That is, we take all the numbers of the form \(n+f\) where \(n\) is a nonnegative integer and \(f\) is a number in \(\mathbb{F}\). Let’s call this set of numbers—you guessed it—\(\mathbb{N} + \mathbb{F}\). There is a simple recipe for finding the minimum number in any nonempty subset of \(\mathbb{N} + \mathbb{F}\), which explains why this set is well ordered:

Lemma 2.4.5. \(\mathbb{N} + \mathbb{F}\) is well ordered.

Proof. Given any nonempty subset, \(S\), of \(\mathbb{N} + \mathbb{F}\), look at all the nonnegative integers, \(n\), such that \(n + f\) is in \(S\) for some \(f \in \mathbb{F}\). This is a nonempty set nonnegative integers, so by the WOP, there is a minimum one; call it \(n_s\).

By definition of \(n_s\), there is some \(f \in \mathbb{F}\) such that \(n_S + f\) is in the set \(S\). So the set all fractions \(f\) such that \(n_S + f \in S\) is a nonempty subset of \(\mathbb{F}\), and since \(\mathbb{F}\) is well ordered, this nonempty set contains a minimum element; call it \(f_S\). Now it easy to verify that \(n_S + f_S\) is the minimum element of \(S\) (Problem 2.14). \(\quad \blacksquare\)

The set \(\mathbb{N} + \mathbb{F}\) is different from the earlier examples. In all the earlier examples, each element was greater than only a finite number of other elements. In \(\mathbb{N} + \mathbb{F}\), every element greater than or equal to 1 can be the first element in strictly decreasing sequences of elements of arbitrary finite length. For example, the following decreasing sequences of elements in \(\mathbb{N} + \mathbb{F}\) all start with 1:

\[\begin{aligned}1, 0. \\ 1, \frac{1}{2}, &0. \\ 1, \frac{2}{3}, &\frac{1}{2}, 0. \\ 1, \frac{3}{4}, &\frac{2}{3}, \frac{1}{2}, 0. \\ &\vdots \end{aligned}\]

Nevertheless, since \(\mathbb{N} + \mathbb{F}\) is well ordered, it is impossible to find an infinite decreasing sequence of elements in \(\mathbb{N} + \mathbb{F}\), because the set of elements in such a sequence would have no minimum.