The Recursion Theorem

The recursion theorem is the fundamental result enabling recursive definitions on natural numbers. It formalizes the intuitive idea that we can define a sequence by specifying its first term and a rule for computing subsequent terms from previous ones.

TheoremRecursion Theorem for omega

Let $A$ be any set, $a \in A$ a fixed element, and $h: A \to A$ a function. Then there exists a unique function $f: \omega \to A$ such that:

\begin{align*} f(0) &= a \\ f(n+1) &= h(f(n)) \quad \text{for all } n \in \omega \end{align*}

This theorem guarantees that recursive definitions are legitimate: they define actual functions rather than circular pseudo-definitions. The proof requires showing both existence and uniqueness.

Proof

Existence: We construct $f$ as a union of approximations. Define a partial recursive function to be a function $g: n \to A$ for some $n \in \omega$ such that:

\begin{align*} g(0) &= a \\ g(k+1) &= h(g(k)) \quad \text{for all } k+1 < n \end{align*}

Let $\mathcal{F}$ be the set of all partial recursive functions. We claim:

For each $n \in \omega$ , there is at most one partial recursive function with domain $n$
If $g_1: n_1 \to A$ and $g_2: n_2 \to A$ are both partial recursive, then $g_1$ and $g_2$ agree on $n_1 \cap n_2$

Proof of (1): By induction on $n$ . For $n = 0$ , the empty function is unique. If $g, g': n+1 \to A$ are partial recursive, then by induction $g|_n = g'|_n$ . But then $g(n) = h(g|_n(n-1)) = h(g'|_n(n-1)) = g'(n)$ .

Proof of (2): Similar, by induction on $\min(n_1, n_2)$ .

Now define $f = \bigcup \mathcal{F}$ , the union of all partial recursive functions. By (2), this is well-defined as a function. By (1), for each $n \in \omega$ , there is exactly one partial recursive $g: n+1 \to A$ , so $f(n)$ is defined. Thus $\text{dom}(f) = \omega$ .

Moreover, $f$ satisfies the recursion equations: $f(0) = a$ by definition, and $f(n+1) = h(f(n))$ because any partial recursive function extending to $n+2$ must satisfy this.

Uniqueness: Suppose $f, g: \omega \to A$ both satisfy the recursion. Define $S = \{n \in \omega : f(n) = g(n)\}$ . Then $0 \in S$ since $f(0) = a = g(0)$ . If $n \in S$ , then $f(n) = g(n)$ , so $f(n+1) = h(f(n)) = h(g(n)) = g(n+1)$ , thus $n+1 \in S$ . By induction, $S = \omega$ , so $f = g$ .

■

ExampleDefining Addition by Recursion

Fix $m \in \omega$ and define $f: \omega \to \omega$ by the recursion theorem with:

$a = m$
$h(x) = S(x) = x + 1$

This gives $f(0) = m$ and $f(n+1) = f(n) + 1$ . Denote $f(n) = m + n$ . This defines addition for fixed $m$ , and we can prove $m + n$ satisfies the expected properties.

TheoremGeneral Recursion Theorem

A more general version allows the recursive step to depend on both the index and the previous value. Given $a \in A$ and $h: \omega \times A \to A$ , there exists a unique $f: \omega \to A$ with:

\begin{align*} f(0) &= a \\ f(n+1) &= h(n, f(n)) \end{align*}

The proof is similar, incorporating the index into the partial functions.

ExampleDefining Power by Recursion

To define exponentiation $m^n$ , fix $m$ and use:

$a = 1$ (since $m^0 = 1$ )
$h(n, y) = m \cdot y$

Then $f(0) = 1$ and $f(n+1) = m \cdot f(n)$ , giving $f(n) = m^n$ .

DefinitionCourse-of-Values Recursion

An even more general form allows the value at $n$ to depend on all previous values. Given $G: \text{Seq}(A) \to A$ (where $\text{Seq}(A)$ is the set of finite sequences from $A$ ), there exists a unique $f: \omega \to A$ such that:

f(n) = G(f|_n)

where $f|_n = \langle f(0), f(1), \ldots, f(n-1) \rangle$ .

ExampleFibonacci Numbers

Define $F: \omega \to \omega$ by course-of-values recursion:

F(n) = \begin{cases} 0 & \text{if } n = 0 \\ 1 & \text{if } n = 1 \\ F(n-1) + F(n-2) & \text{if } n \geq 2 \end{cases}

This is formalized by defining $G$ appropriately on sequences: $G(\langle\rangle) = 0$ , $G(\langle 0 \rangle) = 1$ , and $G(s \smallfrown \langle a, b \rangle) = a + b$ for sequences ending in $a, b$ .

TheoremEquivalence of Recursion Forms

The basic recursion theorem, general recursion, and course-of-values recursion are all equivalent in the sense that each can be derived from any other. They are simply different presentations of the same fundamental property of $\omega$ .

Remark

The recursion theorem is not an axiom but a theorem proved from the ZFC axioms, particularly replacement and infinity. It reflects the well-founded nature of $\omega$ : every natural number is reached in finitely many steps from 0, so recursive definitions terminate and produce well-defined values.

ExamplePrimitive Recursive Functions

The class of primitive recursive functions consists of all functions that can be built from:

Zero function: $Z(n) = 0$
Successor: $S(n) = n + 1$
Projection: $P^k_i(x_1, \ldots, x_k) = x_i$
Composition: From $g$ and $h_1, \ldots, h_m$ , form $f(x) = g(h_1(x), \ldots, h_m(x))$
Primitive recursion: From $g$ and $h$ , form $f$ by $f(x, 0) = g(x)$ and $f(x, n+1) = h(x, n, f(x, n))$

This class includes addition, multiplication, exponentiation, factorials, and many other familiar functions. However, the Ackermann function is computable but not primitive recursive, showing that recursion can go beyond primitive recursion.

The recursion theorem provides the rigorous foundation for all inductive definitions in mathematics. From defining arithmetic operations to constructing complex algorithms, recursion is indispensable, and the recursion theorem ensures that such definitions are mathematically sound.