Transfinite recursion theorem

Transfinite recursion is an instance of transfinite induction and the latter works over a well-ordered set (in fact, the feasibility of such an induction is equivalent to well-ordered-ness). In particular, the theorem can be stated for well-ordered sets. If ${\displaystyle A}$ is a partially ordered set, we write ${\displaystyle A^{a}=\{b\in A\mid b<a\}.}$

The transfinite recursion theorem is also commonly stated for ordinals. One simple version is: let a set ${\displaystyle X}$ and a class function ${\displaystyle G}$ with values in ${\displaystyle X}$ defined on the class of all functions be given. Then, for each ordinal ${\displaystyle \alpha }$, there exists a unique function

${\displaystyle f:\alpha \to X}$

such that, for every ordinal ${\displaystyle \beta <\alpha }$; that is, ${\displaystyle \beta \in \alpha }$ or ${\displaystyle \beta \subsetneq \alpha }$,

${\displaystyle f(\beta )=G(f|_{\beta })}$.

Since an ordinal is a well-ordered set, the above version follows from the well-ordered version (as ${\displaystyle \beta =\alpha ^{\beta }}$). Although it is common to ask ${\displaystyle G}$ to be defined for all functions, this is just a convenient way of stating the theorem. In practice, one usually only defines ${\displaystyle G(f)}$ for functions ${\displaystyle f:\alpha \to X}$, ${\displaystyle \alpha }$ all ordinals, and then extends ${\displaystyle G}$ for all other functions arbitrary.

We say a subset ${\displaystyle E\subset A\times X}$ is closed (with respect to ${\displaystyle G}$) if for each function ${\displaystyle f:A^{a}\to X,\,a\in A}$ whose graph is contained in ${\displaystyle E}$, we have ${\displaystyle (a,G(f))}$ is in ${\displaystyle E}$. For example, ${\displaystyle A\times X}$ is closed.

Let ${\displaystyle F}$ be the intersection of all closed subsets of ${\displaystyle A\times X}$ (with respect to ${\displaystyle G}$), which is again closed. We shall prove ${\displaystyle F}$ is a graph of a function ${\displaystyle A\to X}$; that is, the fiber ${\displaystyle p^{-1}(a)}$ for the projection ${\displaystyle p:F\subset A\times X\to A}$ has exactly one element for each ${\displaystyle a}$ in ${\displaystyle A}$. For this, we shall use strong induction over ${\displaystyle A}$. That is, assuming ${\displaystyle \#p^{-1}(b)=1}$ for every ${\displaystyle b<a}$, we show ${\displaystyle \#p^{-1}(a)=1}$.

By inductive hypothesis, we have the function ${\displaystyle f:A^{a}\to X,\,b\mapsto {\text{unique element in }}p^{-1}(b)}$. Note the graph of it lies in ${\displaystyle F}$. Since ${\displaystyle F}$ is closed, ${\displaystyle (a,G(f))}$ is in ${\displaystyle F}$. Thus, ${\displaystyle \#p^{-1}(a)\geq 1}$. To show it is the equality, suppose otherwise. That means there is some pair ${\displaystyle (a,y)\neq (a,G(f))}$ in ${\displaystyle F}$. We claim the set

${\displaystyle E:=F-\{(a,y)\}}$

is closed. Thus, let ${\displaystyle g:A^{b}\to X}$ be a function whose graph lies in ${\displaystyle E}$. If ${\displaystyle b=a}$, then we have ${\displaystyle f=g}$ by inductive hypothesis; indeed, since their graphs lie in ${\displaystyle F}$,

${\displaystyle \{f(c),g(c)\}\subset p^{-1}(c)}$

for each ${\displaystyle c<a}$. Thus, ${\displaystyle (b,G(g))\in E}$ since ${\displaystyle y\neq G(f)=G(g)}$ and ${\displaystyle F}$ is closed. If ${\displaystyle b\neq a}$, then again ${\displaystyle (b,G(g))}$ is in ${\displaystyle E}$ as ${\displaystyle F}$ is closed. This proves the claim and then ${\displaystyle E\subsetneq F}$ is a contradiction to the smallest-ness of ${\displaystyle F}$. Finally, the uniqueness holds by a similar but easier induction. ${\displaystyle \square }$

Example: a basis construction

Let ${\displaystyle V}$ be a vector space. There is a "very obvious" way to construct a basis of ${\displaystyle V}$ as follows. If ${\displaystyle V\neq 0}$, pick a nonzero vector ${\displaystyle v_{1}}$ and then pick another nonzero vector ${\displaystyle v_{2}}$ not in the span of ${\displaystyle v_{1}}$, if any, and so on. Transfinite recursion can make this argument rigorous, as we now show (alternatively, one can use Zorn's lemma; see Zorn's lemma § Every vector space has a basis.)

Let the above ${\displaystyle V}$ be given a well-ordering by the well-ordering theorem. Suppose we are given a sequence of vectors ${\displaystyle x_{\gamma }}$ indexed by an ordinal ${\displaystyle \beta }$. That is, we are given a function ${\displaystyle f:\beta \to V}$ such that ${\displaystyle f(\gamma )=x_{\gamma }}$ for each ${\displaystyle \gamma \in \beta }$ (or ${\displaystyle \gamma <\beta }$). Then let

${\displaystyle G(f)=}$ the least element in the complement ${\displaystyle V-\operatorname {span} (\operatorname {im} (f))}$

if ${\displaystyle V\neq \operatorname {span} (\operatorname {im} (f))}$ and ${\displaystyle G(f)=0}$ otherwise. Note, since ${\displaystyle f}$ is arbitrary, the image of ${\displaystyle f}$ is not necessarily linearly independent; all we have is that ${\displaystyle G(f)}$ is linearly independent from the nonzero vectors in ${\displaystyle \operatorname {im} (f)}$.

The transfinite recursion theorem then says: given an ordinal ${\displaystyle \alpha }$, there exists a unique ${\displaystyle f:\alpha \to V}$ that satisfies the recursion condition; i.e., ${\displaystyle f(\beta )=G(f|_{\beta })}$ is linearly independent from ${\displaystyle \operatorname {im} (f|_{\beta })}$ for ${\displaystyle \beta <\alpha }$. In particular, the nonzero vectors in the image of ${\displaystyle f}$ are linearly independent. Finally, if we take ${\displaystyle \alpha =\kappa }$ to be some large ordinal; e.g., take ${\displaystyle \kappa }$ to have cardinality strictly larger than that of ${\displaystyle V}$, then, for the reason of cardinality,

${\displaystyle B:=\operatorname {im} (f:\kappa \to V)-\{0\}}$

is a basis of ${\displaystyle V}$. (Note, unlike a construction by Zorn's lemma, this basis is uniquely determined by a choice of a well-ordering on ${\displaystyle V}$.)

Example: a proof of Zorn's lemma

Transfinite recursion is used in a typical proof of Zorn's lemma, assuming the axiom of choice. Here is an argument (which is fairly similar to the construction of a basis above).^[2]

Let ${\displaystyle X}$ be a partially ordered set in which each chain, including the empty chain, has an upper bound. To show ${\displaystyle X}$ has a maximal element, suppose, on the contrary, that it has none. Then each chain ${\displaystyle C}$ has a strict upper bound; i.e., an element ${\displaystyle x}$ in ${\displaystyle X}$ such that ${\displaystyle x>y}$ for each ${\displaystyle y}$ in ${\displaystyle C}$, since it has an upper bound which is bounded by some strictly larger element. Let ${\displaystyle c:{\mathfrak {P}}(X)-\{\emptyset \}\to X}$ be a choice function; i.e., ${\displaystyle c(S)\in S}$ and then for each chain ${\displaystyle C}$ in ${\displaystyle X}$, let

${\displaystyle b(C)=c(\{{\text{strict upper bounds of }}C\}).}$

We now recursively construct a sequence over ordinals. For each function ${\displaystyle f:\beta \to X}$, let ${\displaystyle G(f)=b(\operatorname {im} (f))}$ if ${\displaystyle \operatorname {im} (f)}$ is a chain and otherwise ${\displaystyle G(f)=}$ some arbitrary element in ${\displaystyle X}$; e.g., ${\displaystyle b(\emptyset )}$. By the transfinite recursion theorem, we find a function ${\displaystyle f:\alpha \to X}$ such that ${\displaystyle f(\beta )=G(f|_{\beta })}$ for ${\displaystyle \beta <\alpha }$; in particular, it is injective. But this is a contradiction since there is an ordinal whose cardinality is strictly larger than that of ${\displaystyle X}$ (see Hartogs number). If one is not sure about the existence of a large ordinal, there is also an argument that avoids ordinals altogether (still using transfinite recursion). See e.g., Hausdorff maximal principle § Proof from the well-ordering theorem. ${\displaystyle \square }$

For some use of transfinite recursion, we may need to construction a function with values in a class; in that case, we need to use the axiom of replacement to ensure we still get the function ${\displaystyle f}$ even though the codomain is a class.

Here is an example of such a need.^[3][4] Suppose we want to show

Each well-ordered set is uniquely isomorphic to a unique ordinal.

The problem is that, a priori, we don’t know what ordinal to use. Thus, at each stage in transfinite induction, we construct a new ordinal. Precisely, given a well-ordered set ${\displaystyle X}$ and an element ${\displaystyle a}$ in ${\displaystyle X}$, suppose we have constructed

${\displaystyle g_{b}:X^{b}{\overset {\sim }{\to }}\alpha _{b}}$

where ${\displaystyle X^{b}=\{c\mid c<b\}}$. We shall extend these isomorphisms to an isomorphism ${\displaystyle X^{a}\simeq \alpha }$ for some ordinal ${\displaystyle \alpha }$. If ${\displaystyle a=s(b)}$ is a successor; i.e., the least element among strict upper bounds of ${\displaystyle b}$, then we let ${\displaystyle f|_{X^{b}}=g_{b}}$ and ${\displaystyle f(a)=\alpha _{b}}$. Then

${\displaystyle f:X^{a}{\overset {\sim }{\to }}s(\alpha _{b}):=\alpha _{b}\cup \{\alpha _{b}\},}$

where the union on the right exists by the axiom of union. If ${\displaystyle a=\sup(X^{a})}$, then, thinking ${\displaystyle g_{b}}$ as sets of ordered pairs, let

${\displaystyle f=\bigcup _{b<a}g_{b}.}$

The union on the right is a set by the axiom of replacement and the axiom of union; indeed, the former guarantees the collection ${\displaystyle \{g_{b}\mid b<a\}}$ is a set. Let ${\displaystyle \alpha }$ be the image of ${\displaystyle f}$, which is clearly an ordinal, and ${\displaystyle f:X^{a}{\overset {\sim }{\to }}\alpha }$. Finally, we check the uniqueness. By transfinite induction, we see isomorphisms between ordinals are the identities. Then given ${\displaystyle f:X{\overset {\sim }{\to }}\alpha ,g:X{\overset {\sim }{\to }}\beta }$, we have ${\displaystyle g\circ f^{-1}:\alpha {\overset {\sim }{\to }}\beta }$ is the identity and so ${\displaystyle f=g}$. ${\displaystyle \square }$

The same argument can be used to prove the transfinite recursion theorem when the target ${\displaystyle X}$ is a class. The proof is by strong induction over ordinals (the same proof works for well-ordered sets but we use ordinals for simplicity). Thus, assume the theorem is true for every ${\displaystyle \beta <\alpha }$. By inductive hypothesis, for each ${\displaystyle \beta <\alpha }$, we have a unique function ${\displaystyle g_{\beta }:\beta \to X}$ satisfying the recursion condition. Let ${\displaystyle h_{\beta }:\beta \to X}$ be given by ${\displaystyle \gamma \mapsto G(g_{\beta }|_{\gamma })}$. In the limit case; i.e., ${\displaystyle \alpha }$ is a limit ordinal, identifying functions with their graphs, consider the union

${\displaystyle \bigcup _{\beta <\alpha }h_{\beta }.}$

The formation of a union is justified by the axiom of union but for the above union to be a set, we need the collection

${\displaystyle \{h_{\beta }\mid \beta <\alpha \}}$

to be a set; in other words, the image of the map ${\displaystyle \beta \mapsto h_{\beta }}$ to be a set and that is ensured by the axiom of replacement. Finally, this union is the graph of a function ${\displaystyle f:\alpha \to X}$ that satisfies the required recursion condition. The successor case is handled similarly. ${\displaystyle \square }$