= 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>.
Back to article page
