Transfinite recursion theorem

Short description: Mathematical theorem

In mathematics, the transfinite recursion theorem says a function can be defined using a recursion over a well-ordered set; for example, $\mathbb{\mathbb{N}}$ but also over general well-ordered sets.

Since each well-ordered set is isomorphic to an ordinal, the theorem is also often stated in terms of ordinals.

Statements

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 $A$ is a partially ordered set, we write $A^a=\{b\in A\mid b<a\}.$

Transfinite recursion theorem  — Let a set $X$, a well-ordered set $A$ and a function

$G:\{A^a\to X\mid a\in A\}\to X$

be given. Then there exists a unique function

$f:A\to X$

such that

$f(a)=G(f{|}_{A^a})$

for each $a$ in $A$, where the vertical bar means restriction.

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

$f:\alpha \to X$

such that, for every ordinal $\beta <\alpha$; that is, $\beta \in \alpha$ or $\beta ⊊\alpha$,

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

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

Proof

When $A=\mathbb{\mathbb{N}}$, the proof here appears in N. Jacobson's Basic Algebra I and exactly the same proof goes through for an arbitrary well-ordered set. The proof itself is taken from Halmos.

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

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

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

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

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

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

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

Examples

Example: a basis construction

Let $V$ be a vector space. There is a "very obvious" way to construct a basis of $V$ as follows. If $V\ne 0$, pick a nonzero vector $v_1$ and then pick another nonzero vector $v_2$ not in the span of $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 $V$ be given a well-ordering by the well-ordering theorem. Suppose we are given a sequence of vectors $x_{\gamma }$ indexed by an ordinal $\beta$. That is, we are given a function $f:\beta \to V$ such that $f(\gamma )=x_{\gamma }$ for each $\gamma \in \beta$ (or $\gamma <\beta$). Then let

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

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

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

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

is a basis of $V$. (Note, unlike a construction by Zorn's lemma, this basis is uniquely determined by a choice of a well-ordering on $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).

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

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

We now recursively construct a sequence over ordinals. For each function $f:\beta \to X$, let $G(f)=b(\mathrm{im}(f))$ if $\mathrm{im}(f)$ is a chain and otherwise $G(f)=$ some arbitrary element in $X$; e.g., $b(\mathrm{\varnothing })$. By the transfinite recursion theorem, we find a function $f:\alpha \to X$ such that $f(\beta )=G(f{|}_{\beta })$ for $\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 $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. $◻$

Recursion with the axiom of replacement

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 $f$ even though the codomain is a class.

Here is an example of such a need. 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 $X$ and an element $a$ in $X$, suppose we have constructed

$g_b:X^b\stackrel{\sim }{\to }{\alpha }_b$

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

$f:X^a\stackrel{\sim }{\to }s({\alpha }_b):={\alpha }_b\cup \{{\alpha }_b\},$

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

$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 $\{g_b\mid b<a\}$ is a set. Let $\alpha$ be the image of $f$, which is clearly an ordinal, and $f:X^a\stackrel{\sim }{\to }\alpha$. Finally, we check the uniqueness. By transfinite induction, we see isomorphisms between ordinals are the identities. Then given $f:X\stackrel{\sim }{\to }\alpha ,g:X\stackrel{\sim }{\to }\beta$, we have $g\circ f^{-1}:\alpha \stackrel{\sim }{\to }\beta$ is the identity and so $f=g$. $◻$

The same argument can be used to prove the transfinite recursion theorem when the target $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 $\beta <\alpha$. By inductive hypothesis, for each $\beta <\alpha$, we have a unique function $g_{\beta }:\beta \to X$ satisfying the recursion condition. Let $h_{\beta }:\beta \to X$ be given by $\gamma \mapsto G(g_{\beta }{|}_{\gamma })$. In the limit case; i.e., $\alpha$ is a limit ordinal, identifying functions with their graphs, consider the union

$\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

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

to be a set; in other words, the image of the map $\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 $f:\alpha \to X$ that satisfies the required recursion condition. The successor case is handled similarly. $◻$

References

• Halmos, Paul (1960). Naive Set Theory. Princeton, New Jersey: D. Van Nostrand Company. 
• "Chapter IV Transfinite Recursion". Axiomatic Set Theory. Studies in Logic and the Foundations of Mathematics. 21. 1958. pp. 100–113. doi:10.1016/S0049-237X(08)71575-1. 
• Paul Taylor, Practical Foundations of Mathematics, [1]

Further reading

• https://proofwiki.org/wiki/Transfinite_Recursion_Theorem