Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 120 / 4 / a / Solution

The structural induction principle says that a property $P(f)$ holds for every primitive recursive function if it holds for every initial function of recursion theory and is preserved by function composition in recursion theory and primitive recursion. This is justified because primitive recursive functions are, by definition, the smallest class closed under those constructors; equivalently, every such function has a finite construction tree, and ordinary induction on its height proves $P$.

Take $P(f)$ to mean that $f$ is total. The zero, successor, and projection functions are total. A composition of total functions is total. Finally, suppose $g$ and $h$ are total and $f$ is defined from them by primitive recursion. For fixed $\mathbf{x}$, induction on $n$ proves that $f(\mathbf{x},n)$ exists: the value at zero is $g(\mathbf{x})$, and from the existing value at $n$, totality of $h$ gives the value at $n+1$. Therefore every primitive recursive function is total.