Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 13 down vote accepted

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$.

share|cite|improve this answer
This looks just delightful -- especially in revealing it is not necessary for a primitive recursive function to grow quickly in order for it to be non-$\Delta_0$ (nor, it seems, require massively fast-growing computational time as a function of $e$). – Peter Smith Apr 17 '13 at 17:57
@Peter Smith: I looked at this again today, and although I can't disprove it, I am not convinced I can reconstruct whatever argument I had in mind when I wrote the original answer. I think that, in order for the rgument about the truth preducate of $\Delta_0$ formulas to go through, the Goedel numbering of formulas would need to be such that, for every $\phi(m)$ and every $n$ and $k < n$, the Goedel number of $(\forall m < n) \phi(m)$ and the Goedel number of $(\exists m < n) \phi(m)$ would need to be greater than the Goedel number of $phi(k)$. So I need to look at this problem again. – Carl Mummert Nov 15 '15 at 16:09
@CarlMummert Is it possible for you to elaborate on the point about the sizes of Goedel numbers? – Pteromys Mar 6 at 0:06
@Pteromys: the issue is with bounded quantifiers. We need to have a way to tell whether $(\exists x < n)\phi(x)$ holds, which we normally do by checking all the substitution instances $\phi(0), \phi(1), \ldots$. But to do that by primitive recursion, it seems like we need to arrange that the Goedel numbers of the substitution instances are smaller than the Goedel numbers of the original formulas. – Carl Mummert Mar 6 at 0:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.