17  Well Ordering

A partially ordered set may not have a smallest element, and, even if it has one, it is perfectly possible that some subset will fail to have one. A partially ordered set is called well ordered (and its ordering is called a well ordering) if every non-empty subset of it has a smallest element. One consequence of this definition, worth noting even before we look at any examples and counterexamples, is that every well ordered set is totally ordered. Indeed, if \(x\) and \(y\) are elements of a well ordered set, then \(\{ x,y \}\) is a non-empty subset of that well ordered set and has therefore a first element; according as that first element is \(x\) or \(y\), we have \(x \le y\) or \(y \le x\).

For each natural number \(n\), the set of all predecessors of \(n\) (that is, in accordance with our definitions, the set \(n\)) is a well ordered set (ordered by magnitude), and the same is true of the set \(\omega\) of all natural numbers. The set \(\omega \times \omega\), with \((a,b) \le (x,y)\) defined to mean \((2a + 1)2^{y} \le (2x + 1)2^{b}\) is not well ordered. One way to see this is to note that \((a,b + 1) \le (a,b)\) for all \(a\) and \(b\); it follows that the entire set \(\omega \times \omega\) has no least element. Some subsets of \(\omega \times \omega\) do have a least element. Consider, for example, the set \(E\) of all those pairs \((a, b)\) for which \((1,1) \le (a,b)\); the set \(E\) has \((1, 1)\) for its least element. Caution: \(E\), considered as a partially ordered set on its own right, is still not well ordered. The trouble is that even though \(E\) has a least element, many subsets of \(E\) fail to have one; for an example consider the set of all those pairs \((a,b)\) in \(E\) for which \((a,b) \neq (1, 1)\). One more example: \(\omega \times \omega\) is well ordered by its lexicographical ordering.

One of the pleasantest facts about well ordered sets is that we can prove things about their elements by process similar to mathematical induction. Precisely speaking, suppose that \(S\) is a subset of a well ordered set \(X\), and suppose that whenever an element \(x\) of \(X\) is such that the entire initial segment \(s(x)\) is included in \(S\), then \(x\) itself belongs to \(S\); the principle of transfinite induction asserts that under these circumstances we must have \(S = X\). Equivalently: if the presence in a set of all the strict predecessors of an element always implies the presence of the element itself, then the set must contain everything.

A few remarks are in order before we look at the proof. The statement of the ordinary principle of mathematical induction differs from that of transfinite induction in two conspicuous respects. One: the latter, instead of passing to each element from its predecessor, passes to each element from the set of all its predecessors. Two: in the latter there is no assumption about a starting element (such as zero). The first difference is important: an element in a well ordered set may fail to have an immediate predecessor. The present statement when applied to \(\omega\) is easily proved to be equivalent to the principle of mathematical induction; that principle, however, when applied to an arbitrary well ordered set, is not equivalent to the principle of transfinite induction. To put it differently: the two statements are in general not equivalent to each other; their equivalence in \(\omega\) is a happy but special circumstance.

Here is an example. Let \(X\) be \(\omega^{+}\), i.e., \(X = \omega \cup \{ \omega \}\). Define order in \(X\) by ordering the elements of \(\omega\) as usual and by requiring that \(n < \omega\) for all \(n\) in \(\omega\). The result is a well ordered set. Question: does there exist a proper subset \(S\) of \(X\) such that \(0 \in S\) and such that \(n + 1 \in S\) whenever \(n \in S\)? Answer: yes, namely \(S = \omega\).

The second difference between ordinary induction and transfinite induction (no starting element required for the latter) is more linguistic than conceptual. If \(x_{0}\) is the smallest element of \(X\), then \(s(x_{0})\) is empty, and, consequently, \(s(x_{0}) \subset S\); the hypothesis of the principle of transfinite induction requires therefore that \(x_{0}\) belong to \(S\).

The proof of the principle of transfinite induction is almost trivial. If \(X - S\) is not empty, then it has a smallest element, say \(x\). This implies that every element of the initial segment \(s(x)\) belongs to \(S\), and hence, by the induction hypothesis, that \(x\) belongs to \(S\). This is a contradiction (\(x\) cannot belong to both \(S\) and \(X - S\)); the conclusion is that \(X - S\) is empty after all.

We shall say that a well ordered set \(A\) is a continuation of a well ordered set \(B\), if, in the first place, \(B\) is a subset of \(A\), if, in fact, \(B\) is an initial segment of \(A\), and if, finally, the ordering of the elements in \(B\) is the same as their ordering in \(A\). Thus if \(X\) is a well ordered set and if \(a\) and \(b\) are elements of \(X\) with \(b < a\), then \(s(a)\) is a continuation of \(s(b)\), and, of course, \(X\) is a continuation of both \(s(a)\) and \(s(b)\).

If \(\mathcal{C}\) is an arbitrary collection of initial segments of a well ordered set, then \(\mathcal{C}\) is a chain with respect to continuation; this means that \(\mathcal{C}\) is a collection of well ordered sets with the property that of any two distinct members of the collection one is a continuation of the other. A sort of converse of this comment is also true and is frequently useful. If a collection \(\mathcal{C}\) of well ordered sets is a chain with respect to continuation, and if \(U\) is the union of the sets of \(\mathcal{C}\), then there is a unique well ordering of \(U\) such that \(U\) is a continuation of each set (distinct from \(U\) itself) in the collection \(\mathcal{C}\). Roughly speaking, the union of a chain of well ordered sets is well ordered. This abbreviated formulation is dangerous because it does not explain that “chain” is meant with respect to continuation. If the ordering implied by the word “chain” is taken to be simply order-preserving inclusion, then the conclusion is not valid.

The proof is straightforward. If \(a\) and \(b\) are in \(U\), then there exist sets \(A\) and \(B\) in \(\mathcal{C}\) with \(a \in A\) and \(b \in B\). Since either \(A = B\) or one of \(A\) and \(B\) is a continuation of the other, it follows that in every case both \(a\) and \(b\) belong to some one set in \(\mathcal{C}\); the order of \(U\) is defined by ordering each pair \(\{ a,b \}\) the way it is ordered in any set of \(\mathcal{C}\) that contains both \(a\) and \(b\). Since \(\mathcal{C}\) is a chain, this order is unambiguously determined. (An alternative way of defining the promised order in \(U\) is to recall that the given orders, in the sets of \(\mathcal{C}\), are sets of ordered pairs, and to form the union of all those sets of ordered pairs.)

A direct verification shows that the relation defined in the preceding paragraph is indeed an order, and that, moreover, its construction was forced on us at every step (i.e., that the final order is uniquely determined by the given orders). The proof that the result is actually a well ordering is equally direct. Each non-empty subset of \(U\) must have non-empty intersection with some set in \(\mathcal{C}\), and hence it must have a first element in that set; the fact that \(\mathcal{C}\) is a continuation chain implies that that first element is necessarily the first element of \(U\) also.

Exercise 17.1 A subset \(A\) of a partially ordered set \(X\) is cofinal in \(X\) in case for each element \(x\) of \(X\) there exists an element \(a\) of \(A\) such that \(x \le a\). Prove that every totally ordered set has a cofinal well ordered subset.

The importance of well ordering stems from the following result, from which we may infer, among other things, that the principle of transfinite induction is much more widely applicable than a casual glance might indicate.

Theorem 17.1 (Well ordering theorem) Every set can be well ordered.

Discussion. A better (but less traditional) statement is this: for each set \(X\), there is a well ordering with domain \(X\). Warning: the well ordering is not promised to have any relation whatsoever to any other structure that the given set might already possess. If, for instance, the reader knows of some partially or totally ordered sets whose ordering is very definitely not a well ordering, he should not jump to the conclusion that he has discovered a paradox. The only conclusion to be drawn is that some sets can be ordered in many ways, some of which are well orderings others are not, and we already knew that.

Proof. We apply Zorn’s lemma. Given the set \(X\), consider the collection \(\mathcal{W}\) of all well ordered subsets of \(X\). Explicitly: an element of \(\mathcal{W}\) is a subset \(A\) of \(X\) together with a well ordering of \(A\). We partially order \(\mathcal{W}\) by continuation.

The collection \(\mathcal{W}\) is not empty, because, for instance, \(\emptyset \in \mathcal{W}\). If \(X \neq \emptyset\), less annoying elements of \(\mathcal{W}\) can be exhibited; one such is \(\{ (x,x) \}\), for any particular element \(x\) of \(X\). If \(\mathcal{C}\) is a chain in \(\mathcal{W}\) then the union \(U\) of the sets in \(\mathcal{C}\) has a unique well ordering that makes \(U\) “larger” than (or equal to) each set in \(\mathcal{C}\); this is exactly what our preceding discussion of continuation has accomplished. This means that the principal hypothesis of Zorn’s lemma has been verified; the conclusion is that there exists a maximal well ordered set, say \(M\), in \(\mathcal{W}\). The set \(M\) must be equal to the entire set \(X\). Reason: if \(x\) is an element of \(X\) not in \(M\), then \(M\) can be enlarged by putting \(x\) after all the elements of \(M\). The rigorous formulation of this unambiguous but informal description is left as an exercise for the reader. With that out of the way, the proof of the well ordering theorem is complete.

Exercise 17.2 Prove that a totally ordered set is well ordered if and only if the set of strict predecessors of each element is well ordered. Does any such condition apply to partially ordered sets? Prove that the well ordering theorem implies the axiom of choice (and hence is equivalent to that axiom and to Zorn’s lemma). Prove that if \(R\) is a partial order in a set \(X\), then there exists a total order \(S\) in \(X\) such that \(R \subset S\); in other words, every partial order can be extended to total a order without enlarging the domain.