Recursion

Overview

The recursion theorem guarantees recursively defined functions exist. More formally, let $A$ be a set, $a \in A$ , and $F : A \to A$ . Then there exists a unique function $h : ω \to A$ such that, for every $n \in ω$ ,

\begin{aligned} h (0) & = a \\ h (n^{+}) & = F (h (n)) \end{aligned}

Arithmetic

The recursion theorem asserts existence of many arithmetic operations on the natural numbers.

Addition

For each $m \in ω$ , there exists a unique function $A_{m} : ω \to ω$ such that for all $n \in ω$ ,

\begin{aligned} A_{m} (0) & = m, \\ A_{m} (n^{+}) & = A_{m} (n)^{+} \end{aligned}

Addition ( $+$ ) is the binary operation on $ω$ such that for any $m, n \in ω$ ,

m + n = A_{m} (n) .

Multiplication

For each $m \in ω$ , there exists a unique function $M_{m} : ω \to ω$ such that for all $n \in ω$ ,

\begin{aligned} M_{m} (0) & = 0, \\ M_{m} (n^{+}) & = M_{m} (n) + m \end{aligned}

Multiplication ( $\cdot$ ) is the binary operation on $ω$ such that for any $m, n \in ω$ ,

m \cdot n = M_{m} (n) .

Exponentiation

For each $m \in ω$ , there exists a unique function $E_{m} : ω \to ω$ such that for all $n \in ω$ ,

\begin{aligned} E_{m} (0) & = 1, \\ E_{m} (n^{+}) & = E_{m} (n) \cdot m \end{aligned}

Exponentiation is the binary operation on $ω$ such that for any $m, n \in ω$ ,

m^{n} = E_{m} (n) .

Transfinite Recursion

For any formula $γ (x, y)$ , the following is a theorem:

Assume that $<$ is a well ordering on a set $A$ . Assume that for any $f$ there is a unique $y$ such that $γ (f, y)$ . Then there exists a unique function $F$ with domain $A$ such that, for all $t \in A$ ,
$γ (F ↾ {seg}_{<} t, F (t)) .$

We say $F$ is $γ$ -constructed if $γ (F ↾ {seg}_{<} t, F (t))$ holds for all $t \in dom F$ .