Recursion and Inductive Constructions

Recursion is the dual of induction: while induction proves properties of all natural numbers, recursion defines functions and sequences on natural numbers. Both stem from the well-founded structure of $\omega$ .

DefinitionPrimitive Recursion

A function $f: \omega^{k+1} \to \omega$ is defined by primitive recursion from functions $g: \omega^k \to \omega$ and $h: \omega^{k+2} \to \omega$ if:

\begin{align*} f(x_1, \ldots, x_k, 0) &= g(x_1, \ldots, x_k) \\ f(x_1, \ldots, x_k, n+1) &= h(x_1, \ldots, x_k, n, f(x_1, \ldots, x_k, n)) \end{align*}

The value at $n+1$ depends on the previous value at $n$ , building up the function recursively.

ExampleFactorial Function

The factorial function $n! = 1 \cdot 2 \cdot 3 \cdots n$ can be defined by primitive recursion:

\begin{align*} 0! &= 1 \\ (n+1)! &= (n+1) \cdot n! \end{align*}

Here $g() = 1$ (constant function) and $h(n, y) = (n+1) \cdot y$ . By the recursion theorem, this uniquely determines a function $f: \omega \to \omega$ with $f(n) = n!$ .

Computing: $1! = 1 \cdot 0! = 1$ , $2! = 2 \cdot 1! = 2$ , $3! = 3 \cdot 2! = 6$ , etc.

DefinitionCourse-of-Values Recursion

A more general form allows the value at $n+1$ to depend on all previous values:

f(n+1) = h(n, f(0), f(1), \ldots, f(n))

This is equivalent to primitive recursion but sometimes more convenient. It corresponds to strong induction.

ExampleAckermann Function

The Ackermann function demonstrates that not all computable functions are primitive recursive:

\begin{align*} A(0, n) &= n + 1 \\ A(m+1, 0) &= A(m, 1) \\ A(m+1, n+1) &= A(m, A(m+1, n)) \end{align*}

This grows extremely rapidly: $A(4, 2)$ has over 19,000 digits. The Ackermann function is computable (by double recursion) but not primitive recursive, showing that recursion can be more powerful than simple iteration.

TheoremUnique Readability

Every natural number $n \in \omega$ has a unique representation. Specifically:

Either $n = 0$ , or
$n = S(m) = m + 1$ for a unique $m \in \omega$

This is immediate from the construction: $n = m \cup \{m\}$ , and we can recover $m$ as the largest element of $n$ .

Remark

Unique readability is crucial for induction and recursion. It ensures that when we define a function by cases $f(0) = a$ and $f(n+1) = h(n, f(n))$ , these cases are mutually exclusive and exhaustive, so $f$ is well-defined.

DefinitionStructural Recursion

More abstractly, we can define functions by structural recursion on any well-founded structure. For natural numbers, this means:

Given $a \in A$ and $h: \omega \times A \to A$ , there exists a unique $f: \omega \to A$ with:

f(n) = \begin{cases} a & \text{if } n = 0 \\ h(m, f(m)) & \text{if } n = S(m) \end{cases}

This principle extends to trees, lists, and other inductive data structures.

ExampleBinary Representation

Every natural number has a unique binary representation. We can define a function $\text{bin}: \omega \to \{0,1\}^*$ (finite binary strings) recursively:

\begin{align*} \text{bin}(0) &= 0 \\ \text{bin}(2n) &= \text{bin}(n) \cdot 0 \\ \text{bin}(2n+1) &= \text{bin}(n) \cdot 1 \end{align*}

For instance: $\text{bin}(5) = \text{bin}(2 \cdot 2 + 1) = \text{bin}(2) \cdot 1 = (\text{bin}(1) \cdot 0) \cdot 1 = ((\text{bin}(0) \cdot 1) \cdot 0) \cdot 1 = 101$ .

TheoremExistence of Arithmetic

Using primitive recursion, we can define addition, multiplication, and exponentiation on $\omega$ , and prove all their standard properties by induction:

Associativity: $(m + n) + p = m + (n + p)$
Commutativity: $m + n = n + m$
Distributivity: $m \cdot (n + p) = m \cdot n + m \cdot p$
Identity: $m + 0 = m$ and $m \cdot 1 = m$
No zero divisors: $m \cdot n = 0 \Rightarrow m = 0 \lor n = 0$

These are proved by induction on one variable while holding others fixed.

ExampleDivision with Remainder

The division algorithm can be proved by strong induction: for any $m, n \in \omega$ with $n > 0$ , there exist unique $q, r \in \omega$ with $m = qn + r$ and $r < n$ .

Proof sketch: By strong induction on $m$ . If $m < n$ , take $q = 0, r = m$ . Otherwise $m \geq n$ , so by induction hypothesis applied to $m - n$ , we have $m - n = q'n + r'$ with $r' < n$ . Then $m = (q'+1)n + r'$ with $r' < n$ .

DefinitionIntegers from Natural Numbers

We can construct the integers from $\omega$ using equivalence classes. Define an equivalence relation on $\omega \times \omega$ by:

(a, b) \sim (c, d) \iff a + d = b + c

The equivalence class $[(a, b)]$ represents the integer $a - b$ . The set $\mathbb{Z} = (\omega \times \omega) / \sim$ with operations:

\begin{align*} [(a, b)] + [(c, d)] &= [(a+c, b+d)] \\ [(a, b)] \cdot [(c, d)] &= [(ac+bd, ad+bc)] \end{align*}

forms an integral domain extending $\omega$ .

Remark

This construction shows how all of arithmetic—and indeed all of mathematics—can be built from the empty set through the axioms of ZFC. The natural numbers come from the axiom of infinity, and more complex number systems (integers, rationals, reals, complex numbers) are constructed via quotients, completions, and other set-theoretic operations.

Recursion and induction are two sides of the same coin, both exploiting the well-founded nature of $\omega$ . Together, they provide the foundation for all discrete mathematics and computer science.