Is $\Delta_0=\Delta_1$ in arithmetical hierarchy?

Question

I have seen a definition (e.g. http://www.math.ubc.ca/~bwallace/ArithmeticalHierarchy.pdf) of an arithmetical hierarchy in computability starting with: "let $\Delta_0=\Sigma_0=\Pi_0$ be the set of all computable subsets of natural numbers...", then of course $\Delta_0=\Delta_1$.

However, I have seen another definition where "$\Delta_0=\Sigma_0=\Pi_0$ is the set of all subsets of natural numbers definable by a formula of first-order arithmetic with no quantifiers...".

For the later definition, I do believe that $\Delta_0 \subset \Delta_1$, but cannot prove the proper inclusion. Clearly, $\mathtt{Even}$, the set of even numbers, is in $\Delta_1$, but could I prove that $\mathtt{Even} \not\in \Delta_0$? Or is it perhaps true that $\Delta_0=\Delta_1$?

Answer 1

Here is the definition I am familiar with, which is the one you can find in Wikipedia. It seems that the first definition you give is standard in some places; however I have never seen the definition where we begin with quantifier free formulas.

I should also remark that even if you get the same sets, you can spread them differently over a hierarchy. The question is what you intend to do with that hierarchy which will decide how you should break the sets into a hierarchy.

---

We say that a formula is a $\Sigma^0_0$ formula if it is logically equivalent to a formula that all its quantifiers are bounded. Now we define by recursion hierarchy of formulas:

• $\Pi^0_n$ are formulas logically equivalent to a negation of a $\Sigma^0_n$ formula.
• $\Delta^0_n$ are formulas which are equivalent to both $\Sigma^0_n$ and $\Pi^0_n$ formulas.
• $\Sigma^0_{n+1}$ formulas are those logically equivalent to something of the form $\exists y\varphi(x,y)$ where $\varphi(x,y)$ is a $\Pi^0_n$ formula.

Of course, there are nontrivial theorems here, that you can define the $\Pi^0_n$'s by universal quantifiers; that you can chalk a bunch of consecutive existential quantifiers into a single existential unbounded quantifier, and so on.

We often omit the superscript $0$ and just write $\Sigma_0$ or $\Delta_1$ and so on. Now we say that a subset is $\Sigma_n$ (or $\Pi_n$ or $\Delta_n$) if it is definable by a formula of that complexity.

Why this is different? Because bounded quantifiers are much much more than "no quantifiers at all". And we can express whole lot of stuff using bounded quantifiers. For example, the set of prime numbers is definable with a $\Sigma_0$ formula. Can you find a formula without any quantifiers that defines the set of all prime numbers?

---

Now, why $\Delta_0\subsetneq\Delta_1$? This is a non-trivial theorem, but there is a $\Sigma_1$ universal formula. Namely, a $\Sigma_1$ formula $\varphi(x,y)$ such that whenever $\psi(x)$ is a $\Sigma_1$ formula, there is some $y$ such that $\psi(x)\leftrightarrow\varphi(x,y)$.

Using some $\Delta_0$ encoding of pairs we can show that this defines a $\Sigma_1$ subset of $\Bbb N$ which is not $\Pi_1$. And this means exactly that this set is not $\Delta_1$. Why is this important? Because if $\Delta_0=\Delta_1$, then you can show that in fact $\Sigma_1=\Pi_1$, and therefore this universal set cannot exist. But it does so...

Answer 2

There are several conventions about this, depending on which area you work in. They become equivalent at the level $\Delta^0_1$ and higher, but vary on $\Delta^0_0$, $\Sigma^0_0$, and $\Pi^0_0$. I will drop the superscripts for the rest of this answer.

In computability theory, the most common "starting point" is the computable sets. So it is relatively common, as in Soare's book Computably Enumerable Sets and Degrees, to define a set to be $\Delta_0$, $\Sigma_0$, and/or $\Pi_0$ if it is computable. I suspect this relates to the viewpoint that interprets $\Sigma_{n+1}$ sets as projections of $\Pi_n$ sets: this viewpoint doesn't need any notion of "formula" to define the arithmetical hierarchy. So a $\Sigma_1$ subset of $\mathbb{N}$ is exactly a projection of a computable subset of $\mathbb{N}\times\mathbb{N}$, etc.

On the other hand, in formalized arithmetic, the most common "starting point" is the set of bounded-quantifier formulas. So it is relatively common, as in Kaye's book Models of Peano Arithmetic, to define a formula to be $\Sigma_0$, $\Pi_0$ and/or $\Delta_0$ if it has only bounded quantifiers.

Of course, Post's theorem shows there is a tight link between the formula viewpoint and the computability/projection viewpoint. But the exact statement can be different at the lowest levels of the arithmetical hierarchy depending on how the hierarchy is defined.

There may be some other variations, e.g. I think I might have once seen someone define a set to be $\Delta_0$ if the set is primitive recursive.