# Primitive recursion and $\Delta^0_0$

Until recently I assumed that primitive recursive relations are exactly $\Delta^0_0$ (i.e. bounded) ones, but I learned they're different (the former is a proper superclass of the latter).

I have questions regarding the difference between the two:

1. I have some intuition about primitive recursive functions. For example, a function is primitive recursive if its algorithm is described by means of "only for-loops, not while-loops". How the intuition for $\Delta^0_0$ relations are different from that for primitive recursive ones?

2. What syntactic condition does primitive recursiveness correspond to, if it does at all? More precisely, if $R$ is a primitive recursive relation, what is the syntactic necessary and sufficient condition for $\phi$ if $\bar n \in R \Leftrightarrow \mathbb N \models \phi(\bar n)$, modulo first-order equivalence of $\phi$?

EDIT: The for-loop explanation of primitive recursion can, for example, be seen in Section 2.5 of Schwichtenberg and Wainer's Proofs and Computations.

• Just for those who haven't come across it (not the OP!) there's a nice example of a p.r. function which isn't $\Delta^0_1$ given in this answer. Commented Jun 21, 2015 at 9:16
• @PeterSmith Don't you mean not $\Delta_0^0$? $\Delta_1^0$ are the recursive functions, and so of course contain all p.r. functions. Commented Jun 25, 2015 at 3:49
• Oops I mostly certainly did :-) Commented Jun 25, 2015 at 7:32
• Seems to me that the "only for-loops, not while-loops" intuition actually describes the $\Delta_{0}^{0}$ class because a for loop seems like bounded quantification. No? Commented Jul 1, 2015 at 20:50
• @QuinnCulver That's exactly why I confused the two; some describe primitive recursive functions as "only for-loops, not while-loops", including a Wikipedia article en.wikipedia.org/w/… and a book I skimmed a few years ago (too bad I don't have the copy and the book isn't in English). There should be a subtle technical point which I should have missed, I think. Commented Jul 2, 2015 at 1:44

It's many years after the original question was asked, but I saw this recently and think I can give a more satisfactory answer than the current one.

The $$\Delta^0_0$$ functions can be thought of as functions in a programming language with "only for loops, not while loops," but only if we cannot change the values of non-boolean variables. Maybe it's not clear what I mean, so here are some examples.

The following program is allowed:

program allowed(x):
a = true
for y = 0,...,x*x + 5:
for z = 0,...,x*y*y:
if x*x - y*y*y + z = 6:
a = false
return a


The following program is not allowed:

program not_allowed(x):
a = 2
b = 2
for y = 0,...,x:
a = a*a
for z = 0,...,a:
b = b*b
return true


The idea is just that the bounded quantifiers of a $$\Delta^0_0$$ formula are analogous to for loops, but there is nothing in a $$\Delta^0_0$$ formula to simulate reassigning variables in any way other than incrementing them via a for loop. This ability to reassign variables is what makes possible primitive recursive functions like tetration.

• That's a neat way of explaining it. Commented Jun 1, 2020 at 17:18
• That makes sense. What doesn't is why I hadn't heard this explanation in person (or I hadn't come up with this myself). Where did you learn this? Commented Aug 1, 2020 at 1:40
• @Pteromys I didn't learn it anywhere. I have previously been interested in characterizations of $\Delta^0_0$ formulas and after I happened to see this question I tried to see if I could think of a characterization in terms of some programming language. The fact that every $\Delta^0_0$ formula can be expressed in this programming language is pretty much obvious. The other direction strikes me as less obvious, but follows from the characterizations of $\Delta^0_0$ formulas described here. Commented Aug 2, 2020 at 19:01
1. Let $\Sigma =\left \{0,1 \right \}$, then it's easy to check that for every $\phi({\bf x})\in \Delta_0^0$ there exists a Turing Machine $M$ in $\Sigma$ alphabet such that:

• $L(M)$ is in class of Elementary,

• $\forall n\in\mathbb{N}(|n|\in L(M) \leftrightarrow \phi(n))$, which $|n|$ is binary representation of $n$ in $\Sigma$.

But by Time hierarchy theorem we have $Elementary \subsetneq PR$, so there exists a language $L\in PR$ and $L\not\in Elementary$, therefore $L$ is not $\Delta_0^0$ definable.

2. Let $\Sigma = \left \{ \forall, \exists, \rightarrow, \neg, \wedge, \vee, <, =, +, \cdot, 0, 1 \right \}$. Let $A$ be set of all $r.e.$ languages in this alphabet. we can show every Turing Machine by a $\Sigma_1$ formula $\psi$ in this alphabet, (See this ). Define $M=\left \{L\in A |L\subseteq \left \{0,1 \right \}^* \wedge L\in PR \right \}$, then $M$ is nonetrivial subset of $A$, so by Rice Theorem, $L=\left \{x\in \Sigma^*|(x\: is\:a\:formula)\wedge L(x)\in M \right \}$ is undecidable. Therefore there doesn't exists any syntactic necessary and sufficient condition for deciding primitive recursive predicates.

• 1. I knew this, as stated above. 2. By a similar argument to yours, one could even show that $\Delta^0_0$ cannot be "syntactically characterized". Obviously this is not what I mean by this phrase. Commented Nov 16, 2015 at 23:35
• @Pteromys: $\Delta_0^0$ formulas are syntactically decidable, but if you want to know for formula $\phi$ Is there any $\Delta_0^0$ like $\psi$ such that formula $\phi\equiv \psi$ is undecidable. Commented Nov 17, 2015 at 11:37
• The smallest class of formula that can define primitive recursive function are in form of $\phi(x)\equiv \exists \vec{u}(t_1(x,\vec{u})=t_2(x,\vec{u}))$(see [link](en.wikipedia.org/wiki/Hilbert%27s_tenth_problem)) and also all $r.e.$ sets can defined in this class, so by Rice theorem a turing machine can not distinguish between primitive recursive predicate and the other one, so there does not exists syntactically characterization of primitive recursive sets in this language. Commented Nov 17, 2015 at 11:37