18  Transfinite Recursion

The process of “definition by induction” has a transfinite analogue. The ordinary recursion theorem constructs a function on \(\omega\); the raw material is a way of getting the value of the function at each non-zero element \(n\) of \(\omega\) from its value at the element preceding \(n\). The transfinite analogue constructs a function on any well ordered set \(W\); the raw material is a way of getting the value of the function at each element \(a\) of \(W\) from its values at all the predecessors of \(a\).

To be able to state the result concisely, we introduce some auxiliary concepts. If \(a\) is an element of a well ordered set \(W\), and if \(X\) is an arbitrary set, then by a sequence of type \(a\) in \(X\) we shall mean a function from the initial segment of \(a\) in \(W\) into \(X\). The sequences of type \(a\), for \(a\) in \(\omega^{+}\), are just what we called sequences before, finite or infinite according as \(a < \omega\) or \(a = \omega\). If \(U\) is a function from \(W\) to \(X\), then the restriction of \(U\) to the initial segment \(s(a)\) of \(a\) is an example of a sequence of type \(a\) for each \(a\) in \(W\); in what follows we shall find it convenient to denote that sequence by \(U^{a}\) (instead of \(U\ \mid \ s(a)\)).

A sequence function of type \(W\) in \(X\) is a function \(f\) whose domain consists of all sequences of type \(a\) in \(X\), for all elements \(a\) in \(W\), and whose range is included in \(X\). Roughly speaking, a sequence function tells us how “lengthen” a sequence; given a sequence that stretches up to (but not including) some element of \(W\) we can use a sequence function to tack on one more term.

Theorem 18.1 (Transfinite recursion) If \(W\) is a well ordered set, and if \(f\) is a sequence function of type \(W\) in a set \(X\), then there exists a unique function \(U\) from \(W\) into \(X\) such that \(U(a) = f(U^{a})\) for each \(a\) in \(W\).

Proof. The proof of uniqueness is an easy transfinite induction. To prove existence, recall that a function from \(W\) to \(X\) is a certain kind of subset of \(W \times X\); we shall construct \(U\) explicitly as a set of ordered pairs. Call a subset \(A\) of \(W \times X\) \(f\)-closed if it has the following property: whenever \(a \in W\) and \(t\) is a sequence of type \(a\) included in \(A\) (that is, \((c, t(c)) \in A\) for all \(c\) in the initial segment \(s(a)\)), then \((a,f(t)) \in A\). Since \(W \times X\) itself is \(f\)-closed, such sets do exist; let \(U\) be the intersection of them all. Since \(U\) itself is \(f\)-closed, it remains only to prove that \(U\) is a function. We are to prove, in other words, that for each \(c\) in \(W\) there exists at most one element \(x\) in \(X\) such that \((c,x) \in U\). (Explicitly: if both \((c, x)\) and \((c,y)\) belong to \(U\), then \(x = y\).) The proof is inductive. Let \(S\) be the set of all those elements \(c\) of \(W\) for which it is indeed true that \((c, x) \in U\) for at most one \(x\). We shall prove that if \(s(a) \subset S\), then \(a \in S\).

To say that \(s(a) \subset S\) means that if \(c < a\) in \(W\), then there exists a unique element \(x\) in \(X\) such that \((c, x) \in U\). The correspondence \(c \rightarrow x\) thereby defined is a sequence of type \(a\), say \(t\), and \(t \subset U\). If \(a\) does not belong to \(S\), then \((a,y) \in U\) for some \(y\) different from \(f(t)\). Assertion: the set \(U - \{ (a, y) \}\) is \(f\)-closed. This means that if \(b \in W\) and if \(r\) is a sequence of type \(b\) included in \(U - \{ (a, y) \}\), then \((b,f(r)) \in U - \{ (a, y) \}\). Indeed, if \(b = a\), then \(r\) must be \(t\) (by the uniqueness assertion of the theorem), and the reason the diminished set contains \((b, f(r))\) is that \(f(t) \neq y\); if, on the other hand, \(b \neq a\), then the reason the diminished set contains \((b,f(r))\) is that \(U\) is \(f\)-closed (and \(b \neq a\)). This contradicts the fact that \(U\) is the smallest \(f\)-closed set, and we may conclude that \(a \in S\).

The proof of the existence assertion of the transfinite recursion theorem is complete. An application of the transfinite recursion theorem is called definition by transfinite induction.

We continue with an important part of the theory of order, which, incidentally, will also serve as an illustration of how the transfinite recursion theorem can be applied.

Two partially ordered sets (which may in particular be totally ordered and even well ordered) are called similar if there exists an order-preserving one-to-one correspondence between them. More explicitly: to say of the partially ordered sets \(X\) and \(Y\) that they are similar (in symbols \(X \cong Y\)) means that there exists a one-to-one correspondence, say \(f\), from \(X\) onto \(Y\), such that if \(a\) and \(b\) are in \(X\), then a necessary and sufficient condition that \(f(a) \le f(b)\) (in \(Y\)) is that \(a \le b\) (in \(X\)). A correspondence such as \(f\) is sometimes called similarity.

Exercise 18.1 Prove that a similarity preserves \(<\) (in the same sense in which the definition demands the preservation of \(\le\)) and that, in fact, a one-to-one function that maps one partially ordered set onto another is a similarity if and only if it preserves \(<\).

The identity mapping on a partially ordered set \(X\) is a similarity from \(X\) onto \(X\). If \(X\) and \(Y\) are partially ordered sets and if \(f\) is a similarity from \(X\) onto \(Y\), then (since \(f\) is one-to-one) there exists an unambiguously determined inverse function \(f^{-1}\) from \(Y\) onto \(X\), and \(f^{-1}\) is a similarity. If, moreover, \(g\) is a similarity from \(Y\) onto a partially ordered set \(Z\), then the composite \(gf\) is a similarity from \(X\) onto \(Z\). It follows from these comments that if we restrict attention to some particular set \(E\), and if, accordingly, we consider only such partial orders whose domain is a subset of \(E\), then similarity is an equivalence relation in the set of partially ordered sets so obtained. The same is true if we narrow the field even further and consider only well orderings whose domain is included in \(E\); similarity is an equivalence relation in the set of well ordered sets so obtained. Although similarity was defined for partially ordered sets in complete generality, and the subject can be studied on that level, our interest in what follows will be in similarity for well ordered sets only.

It is easily possible for a well ordered set to be similar to proper subset; for an example consider the set of all natural numbers and the set of all even numbers. (As always, a natural number \(m\) is defined to be even if there exists a natural number \(n\) such that \(m = 2n\). The mapping \(n \rightarrow 2n\) is a similarity from the set of all natural numbers onto the set of all even numbers.) A similarity of a well ordered set with a part of itself is, however, a very special kind of mapping. If, in fact, \(f\) is a similarity of a well ordered set \(X\) into itself, then \(a \le f(a)\) for each \(a\) in \(X\). The proof is based directly on the definition of well ordering. If there are elements \(b\) such that \(f(b) < b\), then there is a least one among them. If \(a < b\), where \(b\) is that least one, then \(a \le f(a)\); it follows, in particular, with \(a = f(b)\), that \(f(b) \le f(f(b))\). Since, however, \(f(b) < b\), the order-preserving character of \(f\) implies that \(f(f(b)) < f(b)\). The only way out of the contradiction is to admit the impossibility of \(f(b) < b\).

The result of the preceding paragraph has three especially useful consequences. The first of these is the fact that if two well ordered sets, \(X\) and \(Y\) say, are similar at all, then there is just one similarity between them. Suppose indeed that both \(g\) and \(h\) are similarities \(X\) onto \(Y\), and write \(f = g^{-1}h\). Since \(f\) is a similarity of \(X\) onto itself; it follows that \(a \le f(a)\) for each \(a\) in \(X\). This means that \(a \le g^{-1}(h(a))\) for each \(a\) in \(X\). Applying \(g\), we infer that \(g(a) \le h(a)\) for each \(a\) in \(X\). The situation is symmetric in \(g\) and \(h\), so that we may also infer that \(h(a) \le g(a)\) for each \(a\) in \(X\). Conclusion: \(g = h\).

A second consequence is the fact that a well ordered set is never similar to one of its initial segments. If, indeed, \(X\) is a well ordered set, \(a\) is an element of \(X\), and \(f\) is a similarity from \(X\) onto \(s(a)\), then, in particular, \(f(a) \in s(a)\), so that \(f(a) < a\), and that is impossible.

The third and chief consequence is the comparability theorem for well ordered sets. The assertion is that if \(X\) and \(Y\) are well ordered sets, then either \(X\) and \(Y\) are similar, or one of them is similar to an initial segment of the other. Just for practice we shall use the transfinite recursion theorem in the proof, although it is perfectly easy to avoid it. We assume that \(X\) and \(Y\) are non-empty well ordered sets such that neither is similar to an initial segment of the other; we proceed to prove that under these circumstances \(X\) must be similar to \(Y\). Suppose that \(a \in X\) and that \(t\) is a sequence of type \(a\) in \(Y\); in other words \(t\) is a function from \(s(a)\) into \(Y\). Let \(f(t)\) be the least of the proper upper bounds of the range of \(t\) in \(Y\), if there are any; in the contrary case, let \(f(t)\) be the least element of \(Y\). In the terminology of the transfinite recursion theorem, the function \(f\) thereby determined is a sequence function of type \(X\) in \(Y\). Let \(U\) be the function that the transfinite recursion theorem associates with this situation. An easy argument (by transfinite induction) shows that, for each \(z\) in \(X\), the function \(U\) maps the initial segment determined by \(a\) in \(X\) one-to-one onto the initial segment determined by \(U(a)\) in \(Y\). This implies that \(U\) is a similarity, and the proof is complete.

Here is a sketch of an alternative proof that does not use the transfinite cursion theorem. Let \(X_{0}\) be the set of those elements \(a\) of \(X\) for which there exists an element \(b\) of \(Y\) such that \(s(a)\) is similar to \(s(b)\). For each \(a\) in \(X_{0}\), write \(U(a)\) for the corresponding (uniquely determined) \(b\) in \(Y\), and let \(Y_{0}\) be the range of \(U\). It follows that either \(X_{0} = X\), or else \(X_{0}\) is an initial segment of \(X\) and \(Y_{0} = Y\).

Exercise 18.2 Each subset of a well ordered set \(X\) is similar either to \(X\) or to an initial segment of \(X\). If \(X\) and \(Y\) are well ordered sets and \(X \cong Y\) (i.e., \(X\) is similar to \(Y\)), then the similarity maps the least upper bound (if any) of each subset of \(X\) onto the least upper bound of the image of that subset.