The structural induction principle says that a property 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 .
Take to mean that is total. The zero, successor, and projection functions are total. A composition of total functions is total. Finally, suppose and are total and is defined from them by primitive recursion. For fixed , induction on proves that exists: the value at zero is , and from the existing value at , totality of gives the value at . Therefore every primitive recursive function is total.
A partial recursive function is obtained from the three kinds of initial function of recursion theory—
the zero function, successor function, and projection function—by finitely many applications of function composition in recursion theory, primitive recursion, and unbounded minimization. Explicitly, primitive recursion has the form
while minimization takes the least for which and is undefined if no such is found.
For the function in part (i), define
The initial value and the identically zero recursion step are primitive recursive, so this is a primitive-recursive definition of the required zero test. It uses no minimization.
Successor function Created 2026-09-24 Updated 2026-11-05
The successor function on the natural numbers is the function . With as the initial natural number, its repeated application produces .
In recursion theory, the successor function is an initial function of recursion theory. Together with the other initial functions and the permitted operations, it helps generate primitive recursive functions. For example, addition can be specified recursively by and . This description builds addition from a base case and a successor step, matching the structure used in mathematical induction.