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:


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 Σ10 but not in Σ00 according to the first definition given above, while it is in Σ00 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?

  • 1
    $\begingroup$ Note that the complexity class of sets decidable in polynomial time of the variables is E rather than EXPTIME, since the latter allows running time to be exponential in a polynomial in the number of bits. $\endgroup$ – Henning Makholm Jun 18 '16 at 12:19

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

  • $\begingroup$ To complement this nice answer: I suspect one reason for the variation is context. For example, "classical" computability theory is about the standard naturals, not about formal theories of arithmetic, and it is convenient to define $\Delta^0_0 = \Delta^0_1$ (that is, option $D$) to make it easier to prove that various things are $\Sigma^0_1$. In the context of formal theories of arithmetic, it is often easier to take option $A$ or $B$, because then the class of $\Delta^0_0$ formulas does not depend on which theory we consider. Of course option $B$ requires a language richer than that of PA. $\endgroup$ – Carl Mummert Jun 20 '16 at 0:27
  • $\begingroup$ Regarding $C\ne D$: how, in fact, do you enumerate C? You can of course enumerate all the relevant proofs. But some of them might be proofs of existence only (that is, existence of a Turing machine that computes some function); is there an effective way to get the Turing machine itself and call it (in order to compute $f_n(n)$? $\endgroup$ – Dani Jun 21 '16 at 5:43
  • $\begingroup$ @Dani: You enumerate all pairs $(n,a)$ and select those where $a$ is a valid proof that Turing machine number $n$ always terminates. You can't prove things about "functions" in abstract general, only about concrete descriptions of functions, and requiring that description to be in the form of an executable algorithm for computing the function is standard. (But it's a good point that what I meant was not just functions defined by an arbitrary arithmetical formula where one can prove merely that a Turing machine for it must exist). $\endgroup$ – Henning Makholm Jun 21 '16 at 6:15
  • $\begingroup$ But here the description of the function is in fact by a formula, so the relation with the Turing machine is not trivial. You can of course, once you found an existence proof, enumerate over all Turing machines until you find the one that computes the function, but for a guarantee that this will halt you need $\Sigma_1^0$-soundness, don't you? $\endgroup$ – Dani Jun 21 '16 at 6:19
  • 1
    $\begingroup$ @Dani: What I meant by $\mathcal C$ was "functions defined by provably-always-halting Turing machines", no more or less. This is, I believe, what is usually meant by "provably total recursive function" in computability in general. $\endgroup$ – Henning Makholm Jun 21 '16 at 6:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.