Primitive recursive function which isn't $\Delta_0$

What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?

Solution 1:

If $\phi(x,y)$ is a $\Delta^0_0$ formula that defines a function $y = f(x)$, then for each $x$ there is at most one $y$ such that $\phi(x,y)$ holds. Therefore, consider the primitive recursive function that, on input $e$, does the following:

• Interpret $e$ as a code for a $\Delta^0_0$ formula $\phi_e(x,y)$ in the canonical way.

• Check whether $\phi_e(e,0)$ holds. If it does hold, return $1$. Otherwise return $0$.

By the usual argument, this function cannot be defined by any $\Delta^0_0$ formula. Yet under the usual coding of formulas, it is a primitive recursive function, because the truth predicate for $\Delta^0_0$ sentences is primitive recursive. The proof of this latter fact is just a formalization of the fact that the primitive recursive predicates include the atomic formulas and are closed under all the logical connectives and under bounded universal and existential quantification.

In particular, this example shows that it is not necessary for a primitive recursive function to grow quickly in order for it to be non-$\Delta^0_0$.