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:


*

*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?

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

*

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

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