Transfinite Recursion

Question

I'm trying to understand the concept of transfinite recursion. Can someone provide me examples which clearly illustrates transfinite recursion or provide some references which I can go through?

Answer 1

First, let me clarify the relationship between transfinite induction and recursion. Transfinite induction is a proof technique. Transfinite recursion, on the other hand, is a construction technique. You use transfinite recursion to build some mathematical object (usually but not always a function), and you use transfinite induction to prove things about it.

(Note that these terms often get conflated in the literature.)

Now, you'll often see transfinite recursion stated as a principle specifically for constructing functions, as e.g.:

If I have a map $I:X^{<\alpha}\rightarrow X$ (for $\alpha$ some ordinal - here "$X^{<\alpha}$" denotes the set of maps from $\beta$ to $X$, for any $\beta<\alpha$), then there is a unique function $f: \alpha\rightarrow X$ such that for all $\beta<\alpha$, $f(\beta)=I(f\upharpoonright\beta)$.

Note that we can conflate a set and its characteristic function, so even if you stick to this definition of transfinite recursion, it's still meaningful to define a set $A$ via transfinite recursion. What you're doing is recursively answering questions of the form, "Is $\beta$ in $A$?".

This is quite abstract on the face of it, but what it's saying is not too complicated. We're trying to build a function $\alpha\rightarrow X$. Now, $I$ is a method for extending a partial function "one step further": if I feed $I$ a map $p:\beta\rightarrow X$ for some $\beta<\alpha$, $I$ tells me what $f(\beta)$ "ought" to be given that $p=f\upharpoonright\beta$. That is, if I've defined $f$ for the first $\beta$-many inputs, $I$ tells me how to define $f$ for the next input.

This lets us "build $f$ from below". For instance, how do I compute $f(0)$? Well, so far I haven't built any of $f$, so the thing I feed $I$ is the empty function $\emptyset$. Then $f(0)$ is just $I(\emptyset)$. What about $f(1)$? Well, now I've built the first "bit" of $f$, so I feed $I$ the partial function $\{(0, I(\emptyset))\}$; so $f(1)=I(\{(0, I(\emptyset))\}$. And so on. Note that $I$ is allowed to look at all previous values of $f$, not just the "last" one (and note that that doesn't even make sense all the time: when computing $f(\omega)$ using $I$, there isn't a "last" value of $f$).

A concrete example. Here's a good exercise. Let $\alpha$ be some large infinite ordinal - say, $\alpha=\omega^2$ - and take $X=\omega$. We're going to build a map from $\alpha$ to $X$ by transfinite recursion.

For $p:\beta\rightarrow X$ ($\beta<\alpha$), let $I(p)=0$ if $\beta$ is a limit ordinal, and $I(p)=p(\gamma)+1$ if $\beta=\gamma+1$. Then what function $f$ do we get?

HINT: Compute the first few values of $f$: $f(0)$, $f(1)$, $f(2)$, . . .. Do you see a pattern? Now compute $f(\omega)$, $f(\omega+1)$, $f(\omega+2)$; you should be able to guess at this point what the function is doing.

FURTHER HINT (rot13'd to prevent spoilers): Guvf vf onfvpnyyl zbqhyne nevguzrgvp sbe beqvanyf. Guvax nobhg jung "zbq bzrtn" fubhyq zrna . . .