Transfinite recursive constructions

Reaching into the higher infinite, we shall undertake various transfinite recursions—the alephs and the beths, the cumulative hierarchy, as well as some surprising geometric decompositions of space

Finite recursion

Can you see the underlying rule of this familiar sequence?

\( 1\quad 1\quad 2\quad 3\quad 5\quad 8\quad 13\quad 21\quad 34\quad 55\quad···\)

This is the Fibonacci sequence—each number is the sum of the previous two, starting with two 1s. This sequence is thus an example of a recursive definition, where the values of a function are defined in terms of earlier values of the same function. The Fibonacci sequence has two anchor values:

\( f_1=1\qquad f_2=1\)

and then the recursion rule, expressing that the sum of two successive values is the subsequent value:

\( f_n+f_{n+1}\quad=\quad f_{n+2}. \)

This information is sufficient to calculate any given value f_n of the Fibonacci function, since we can simply iterate the recursion rule as far out as necessary. If we want to know what f₇₃ is, we can simply generate the sequence out that far in order to find out what the value is. In this way, the recursive definition encapsulates a complete logical account of the function.

Recursions express fundamental relations

Recursion rules often arise when one is analyzing the fundamental nature of a process that is determined by a sequence of successive atomic interactions. Fibonacci, for example, was considering a population of reproducing rabbits. According to his simple model, we start with one pair of rabbits, one male and one female, who are initially juveniles, but they mature and mate after one month, producing one new pair of rabbits each month thereafter. And those rabbits reproduce according to the same model.

According to the model, we start with 1 pair of juvenile rabbits at the beginning of the first month. At the beginning of the second month, the female has become pregnant, but we still have only 1 pair of rabbits. At the start of the third month, however, we find the original pair plus the newly born pair, making 2 pairs altogether.

More generally, if f_n is the number of pairs of rabbits at the start of the nth month, then the model predicts the recursion

\( f_n+f_{n+1}=f_{n+2}\)

precisely because the number of rabbit pairs at month n+2 is the number at the previous month f_n+1 plus the number of newborn rabbit pairs, which arose from the rabbits at the month before that, of which there are f_n many. So f_n+2 = f_{n +} f_n+1.

In this way, the recursive rule expresses this fundamental atomic interaction in the model, and we can subsequently use this recursion rule to mount a mathematical analysis. (Let us leave aside the fact that this particular model is biologically unrealistic in several respects—it predicts that rabbits never die, for example, and that they always produce one male and one female every month without fail; and the model does not account for resource limitations or predation.)

Many familiar functions are realized by recursion

Many of our most familiar arithmetic functions, which one perhaps might not ordinarily think of as defined by recursion, nevertheless can be seen as the result of a recursive definition. These recursive definitions often express something fundamental about these functions, which can furthermore often be used fruitfully to prove things about them by induction.

Let us define addition x + y as recursively adding 1, taking the successor operation Sx = x+1 as primitive, as in Dedekind arithmetic. The recursion is specified by an anchor case and recursion rule:

\(\begin{eqnarray*} \text{Anchor: }\quad& x+0&=\quad x \\ \text{Recursion rule: }\quad& x+(y+1)&=\quad (x+y)+1. \end{eqnarray*} \)

This is a recursive definition of x + y in terms of successor, because it defines the next value x + (y + 1) in terms of the previous value (x + y) using only the primitive successor operation of adding 1. In short, to add y is repeatedly to take the successor y times.

Similarly, we can define multiplication as repeated addition by recursion. We begin with the anchor case

\(\begin{eqnarray*} \text{Anchor:}\quad& x · 0 &=\quad 0 \\ \text{Recursion rule:}\quad& x ·(y+1) &=\quad (x · y)+x. \end{eqnarray*} \)

Thus we have defined multiplication x · y recursively in terms of addition.

Exponentiation is similarly defined by recursion as follows:

\(\begin{eqnarray*} \text{Anchor:}\quad& x^0 &=\quad 1 \\ \text{Recursion rule:}\quad& x^{y+1}&=\quad x^y · x. \end{eqnarray*} \)

Can you define tetration by recursion? And pentration? Why not also define the Knuth uparrows x 🠑ⁿ y, as well as x ⇑ y, x ⤊ y and x ⟰ y, and so on?

Why are definitions by recursion legitimate?

Why does recursion work? Perhaps it might seem circular somehow, since the function is being defined in terms of itself. The essence of any recursion, after all, is the idea that the value of a function at a given stage is determined somehow from the earlier values of the same function. One can define a function f on the natural numbers ℕ by defining every value f(n) in terms of the previous values f(i) for i < n. Equivalently, we specify the anchor value f(0) and how the successor values f(n+1) are determined from the sequence of prior values f(i) for i ≤ n.

Nevertheless, definition by recursion on the natural numbers is not circular. The recursion theorem, proved by Dedekind, asserts indeed that every such definition by recursion on the natural numbers is legitimate—the recursion has a unique solution. Dedekind's recursion theorem can be proved by using the method of mathematical induction to show that for every n, there is a unique solution to the recursion that works up to n. If this is true below n, then we simply apply the recursive rule to that partial solution to discover the value at n, which shows existence at n, and since all solutions agree below n, they will also agree at n, which shows uniqueness. So the overall solution of the recursion is the function consisting of these coherent partial solutions of it. So every recursive definition on the natural numbers defines a unique function.

A failure of recursion

Does recursion work on other domains, such as the real numbers?

Suppose that I would like to define a function f recursively on the nonnegative real numbers ℝ^≥0 = [0, ∞) by specifying its value at every point in terms of the values taken at earlier points. For example, let us take f(0) = 0 as the anchor and then specify the recursive rule

\( f(x)=\sup_{y < x} f(y) \)

for every x > 0. Does this recursion define a function on ℝ^≥0?

Well, we might notice that the constant 0 function f(x) = 0 obeys the recursive definition we have provided, since it has the correct value of 0 at the anchor, and it obeys the recursion, since the supremum of a bunch of 0s is 0. So the recursion has a solution.

The problem, however, is that there are also many other solutions of this recursion. For example, the identity function f(x) = x also obeys f(0) = 0 and f(x) = sup_y<x f(y), since every real number x is the supremum of the real numbers below it. And the function f(x) = x² also obeys the recursion. Indeed, any increasing continuous function through the origin will solve this recursion, and in this sense, the recursion hasn't succeeded in defining a function on the nonnegative real numbers, because there is more than one function fulfilling it.

Meanwhile, other recursion rules on the real numbers have no solution. Consider the anchor f(0) = 0 with the recursion rule f(x) = sup_y<x f(y) + 1, for x > 0. That is, every value f(x) of the function for x > 0 is supposed to be the supremum of the prior values plus one, f(y) + 1 for y < x. But there is no function solving this rule, I claim, since whenever y < x it must be that f(y) + 1 ≤ f(x), which would require a jump discontuity at every point. But this is impossible, since for any x > 0 we can fit a tiny chain below it 0 < y₁ < y₂ < ··· < y_n < x, and the necessary jumps of 1 at each point y_i would push the value of f(x) bigger than n for every n. So there can be no solution to this recursion.

These examples show that a naive approach to recursion on the reals simply doesn't work. The recursion rule may have multiple solutions or no solution. The main issue is that the order on the real numbers is not a well order.

Recursion on the reals

Nevertheless, let me briefly explain that there is a way to make recursion work on the real numbers using the ordinary real order, even though this is not a well order. The key to making it work is to require that the recursion rule should specify a continuation of the function at every point, not merely a single value—even a very tiny nonzero continuation will be fine, as long as these various continuations don't contradict each other.