Proof of the Recursion Theorem

The recursion theorem guarantees that recursive definitions produce well-defined functions on the natural numbers. This fundamental result justifies the definition of addition, multiplication, exponentiation, and sequences by recursion.

Theorem Statement

Theorem3.2Recursion theorem (Dedekind)

Let $A$ be a set, $a \in A$ , and $g: A \to A$ a function. Then there exists a unique function $f: \mathbb{N} \to A$ such that:

$f(0) = a$ ,
$f(n+1) = g(f(n))$ for all $n \in \mathbb{N}$ .

More generally, given $h: \mathbb{N} \times A \to A$ , there exists a unique $f: \mathbb{N} \to A$ with $f(0) = a$ and $f(n+1) = h(n, f(n))$ .

Proof

Existence. We construct $f$ as the union of "partial recursive functions."

Call a set $F \subseteq \mathbb{N} \times A$ an $n$ -approximation if:

$F$ is a function (i.e., each natural number maps to at most one value),
$\mathrm{dom}(F) = \{0, 1, \ldots, n\}$ ,
$F(0) = a$ ,
$F(k+1) = g(F(k))$ for all $k < n$ .

Claim 1: For each $n \in \mathbb{N}$ , there exists a unique $n$ -approximation $F_n$ .

Proof by induction: The $0$ -approximation is $\{(0, a)\}$ . Given the $n$ -approximation $F_n$ , define $F_{n+1} = F_n \cup \{(n+1, g(F_n(n)))\}$ , which is the unique $(n+1)$ -approximation.

Claim 2: If $m \leq n$ , then $F_n$ and $F_m$ agree on $\{0, \ldots, m\}$ .

Proof by induction on $m$ : for $m = 0$ , both give $F(0) = a$ . If $F_n$ and $F_m$ agree on $\{0, \ldots, m-1\}$ , then $F_n(m) = g(F_n(m-1)) = g(F_m(m-1)) = F_m(m)$ .

Definition of $f$ : Set $f = \bigcup_{n \in \mathbb{N}} F_n$ . By Claim 2, this is a well-defined function with domain $\mathbb{N}$ .

Verification: $f(0) = F_0(0) = a$ . For any $n$ : $f(n+1) = F_{n+1}(n+1) = g(F_{n+1}(n)) = g(F_n(n)) = g(f(n))$ .

Uniqueness. Suppose $f, f': \mathbb{N} \to A$ both satisfy the conditions. By induction:

$f(0) = a = f'(0)$ .
If $f(n) = f'(n)$ , then $f(n+1) = g(f(n)) = g(f'(n)) = f'(n+1)$ .

So $f = f'$ . $\blacksquare$

■

Applications

ExampleDefining arithmetic via recursion

Using the recursion theorem, we define:

Addition: For each $m$ , define $f_m: \mathbb{N} \to \mathbb{N}$ by $f_m(0) = m$ and $f_m(n+1) = S(f_m(n))$ , where $S$ is the successor. Then $m + n := f_m(n)$ .

Multiplication: $g_m(0) = 0$ , $g_m(n+1) = g_m(n) + m$ . Then $m \cdot n := g_m(n)$ .

Exponentiation: $h_m(0) = 1$ , $h_m(n+1) = h_m(n) \cdot m$ . Then $m^n := h_m(n)$ .

Each definition is justified by the recursion theorem with appropriate choices of $a$ and $g$ .

RemarkSet-theoretic subtlety

The recursion theorem requires the axiom of replacement (or at least the axiom of union) to form $f = \bigcup F_n$ . In ZFC, replacement guarantees that $\{F_n : n \in \mathbb{N}\}$ is a set, so its union exists. Without replacement, the recursion theorem can fail in certain models.