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.

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.
