Precise definition of $\Sigma_0^0$ in the arithmetical hierarchy

Question

I encountered several different definitions for $$\Sigma_0^0 = \Pi_0^0 = \Delta_0^0$$ of the arithmetical hierarchy. Following are two definitions which seem to me different, but I'm not sure:

1. All first-order arithmetic formulas that have no unbounded quantifiers.

2. In the second version, one is additionally allowed to use primitive recursive functions (or, in yet another version, every function that can be defined recursively; this definition includes also functions such as Ackermann's function, but only provably total functions).

Primitive recursive functions can be formalized in first-order Peano arithmetic using Gödel's $\beta$ function, but this seems to necessitate the use of unbounded quantifiers as well.

Why? suppose we want to write formally a formula $\varphi(n)$ of the following form:

$\forall k<n: \varphi_0(a_k)$

where $\varphi_0$ is some first-order formula and $a_k$ is primitive recursively defined by:

$a_0 = C$

$a_{n+1} = F(a_n,n)$

with $C$ a constant and $F$ some already defined function (could be just multiplication, for the sake of the argument).

We use Gödel's $\beta$ function as in here:

https://en.wikipedia.org/wiki/G%C3%B6del%27s_%CE%B2_function

Then we should actually write $\varphi(n)$ in the following way:

$\exists b: \exists c<b: \forall k<n: \varphi_0(\beta(b,c,k))\land (\beta(b,c,0) = C)\land \forall i<n:(\beta(b,c,i+1) = F(\beta(b,c,i),i))$

Crucially, the quantifier on $b$ cannot be bounded (without using yet other primitive recursive functions, and so on ad infinitum).

So $\varphi(n)$ is in Σ₁⁰ but not in Σ₀⁰ according to the first definition given above, while it is in Σ₀⁰ according to the second definition.

More generally, it seems that by definition 1 includes only formulas decidable in polynomial time of its variables (corresponding to problems in EXPTIME, since it is exponential in the number of bits); definition 2, on the other hand, includes all formulas decidable in time that is any primitive recursive function of its variables.

Note that this will not affect the rest of the arithmetical hierarchy since we can always bound $b$ by a variable given in an "external" unbounded quantifier.

To conclude, my question is: are these two definitions really different?

Answer 1

You're speaking about at least three possible definitions of $\Delta^0_0$ sets, not just two:

• $\mathcal A=$ the sets definable with bounded quantification, $0$, $1$, $+$, and $\times$.
• $\mathcal B=$ the sets definable with bounded quantification and primitive recursive functions. These are exactly the sets of the form $\{x\in\mathbb N\mid f(n)=0\}$ for some primitive recursive function $f$, since we can always code up bounded quantification using primitive recursion.
• $\mathcal C=$ the sets definable with bounded quantification and provably (in some appropriate axiomatic system) total recursive functions.
• $\mathcal D=$ the sets definable with actually total recursive functions -- that is every Turing machine that happens to halt on every input is fair game, no matter whether we can prove this or not. These are exactly the decidable sets.

Clearly we have $\mathcal A\subseteq \mathcal B\subseteq \mathcal C\subseteq\mathcal D$, but -- as you have surmised -- all of these inclusions are strict.

Your argument about decidability in polynomial time works to dinstinguish $\mathcal A$ from $\mathcal B$ -- the time hierarchy theorem will produce a set that is in $\mathcal B$ but not in $\mathcal A$.

To see that $\mathcal B\ne \mathcal C$, we can construct a set in $\mathcal C\setminus\mathcal B$ by diagonalization, since the primitive recursive functions are effectively enumerable.

To see that $\mathcal C\ne\mathcal D$, note that the provably total Turing machines are effectively enumerable, so we can do the same diagonalization trick once again. However, for this proof we have to assume that the proof system we use to define $\mathcal C$ is sound with respect to the true natural numbers.

The reason why this confusion is allowed to persist is that no matter which of $\mathcal A$, $\mathcal B$, $\mathcal C$, or $\mathcal D$ is chosen as $\Delta^0_0 = \Pi^0_0 = \Sigma^0_0$, we get the same $\Sigma^0_1$ in every case, namely exactly the recursively enumerable sets! Similarly, $\Pi^0_1$ is always exactly the co-r.e. sets, and the entire rest of the arithmetical hierarchy is the same in all three cases.

(And so, in each case we get $\Delta^0_1=\mathcal D$. Funnily enough the two different arguments for $\mathcal A\ne \Delta^0_1$ I offered in my earlier answer split nicely into the arguments for strict inclusion given above).