Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Oh, that would have been a useful question two weeks ago! Oh well :-) –  Asaf Karagila Apr 17 '13 at 17:40

1 Answer 1

up vote 8 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|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

Your Answer

 
discard

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.