7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Where did you find these definitions? $\endgroup$ – Asaf Karagila Feb 2 '15 at 16:05
  • $\begingroup$ I don't see in Wikipedia a definition saying that it's a formula without quantifiers. I do see a definition equivalent to the one in my answer, though. $\endgroup$ – Asaf Karagila Feb 2 '15 at 16:20
  • $\begingroup$ @AsafKaragila You are right, I removed the link. Thanks for the answer. $\endgroup$ – Dávid Natingga Feb 2 '15 at 16:23
9
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ To be fair, Soare's book defines a set to be $\Delta_0$ and $\Sigma_0$ if it is recursive. $\endgroup$ – Carl Mummert Feb 2 '15 at 16:16
  • 2
    $\begingroup$ The differences in the definitions are relatively common. The progression up the hierarchy is always the same, by taking projections/quantifiers and complements/negations, respectively. It's just the starting point that varies. $\endgroup$ – Carl Mummert Feb 2 '15 at 16:30
  • 4
    $\begingroup$ I must add to the confusion. Another standard convention goes by not ignoring bounded quantifiers, so that $\Delta_0=\Sigma_0=\Pi_0$ is quantifier free and then we alternate as usual. With this convention we have $\Sigma_1=\Sigma^0_1$ (and agreement from this point on), but this is the Davis-Matiyasevich-Putnam-Robinson theorem. $\endgroup$ – Andrés E. Caicedo Feb 2 '15 at 16:34
  • 2
    $\begingroup$ (Well, past the zeroth level everybody agrees. I think having $\Delta_0$ be formulas with only bounded quantifiers is the most sensical convention, since it most closely resembles the starting points of other standard hierarchies.) $\endgroup$ – Andrés E. Caicedo Feb 2 '15 at 16:43
  • 2
    $\begingroup$ The definition of the initial $\Delta_0^t$ may vary across $t$ with respect to bounded/no quantifiers. While $\Delta_0^0$ formulas can have bounded quantifiers, $\Delta_0^1$ "indicates the class of formulas in the language of second-order arithmetic with no set quantifiers." en.wikipedia.org/wiki/Analytical_hierarchy $\endgroup$ – Dávid Natingga Feb 2 '15 at 17:52
6
$\begingroup$

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.

$\endgroup$

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.