Are provable statements at the bottom of the arithmetical hierarchy?

Question

When I can assign to a statement (of PA) a classification $\Sigma_n^0$ (resp. $\Pi_n^0$) of the arithmetical hierarchy (AH), then this also classifies it as $\Sigma_m^0$ (resp. $\Pi_m^0$) for any $m\ge n$. So the only interesting question is how far down it can be placed in this hierarchy. A bit of thinking about this brought me to the following realization:

I always thought that math was about proving theorems (with theorems formally written down as statements $\varphi$). But might it be that math is more generally about pushing as many statements as far down in AH as possible?

As soon as a statement is proven, we showed that it is a tautology, that it is equivalent to some statement with bounded quantifiers, e.g. $1=1$.

Questions:

1. Is really any provable statement already in $\Sigma_0^0$ or $\Pi_0^0$?
2. If so, what is the point of placing statements in AH? Is it about classifying unprovable (independent or wrong) statements?
3. If so, what is the point of categorize unporvable statements? E.g. I know that a statement in $\Pi_1^0$ is already shown to be true in the standard natural numbers $\Bbb N$ if we can show its independence from PA. So it is not provable, but still "sufficiently true" from our meta point of view. But is there more about this? What does it help to categorize wrong statements? Does it help us to place $\varphi$ in AH during the process of proving it?

---

Update:

I read that a statement is in $\Sigma_0^0$ and $\Pi_0^0$ if it is logically equivalent to a statement with only bounded quantifiers. Does this "logically" mean that in order to show the equivalence, I am only allowed to use the axioms and rules of the deductive system I am working in but not the axioms of PA? In this case my question indeed would be very trivial because based on a false understanding.

Answer 1

The arithmetical hierarchy, of course, doesn't include all sentences in mathematics, only ones that are in the language of Peano arithmetic. (For example, the AH does not cover more complex sentences of set theory.) So it shouldn't be surprising that the AH is primarily of use when we are looking at provability of sentences within theories of arithmetic.

There are several reasons to look at the classification of a sentence, one of which you mentioned already:

• A $\Pi^0_1$ sentence that is not disprovable in PA must be true; a $\Sigma^0_1$ sentence that is not provable in PA must be false. In some cases, it is not trivial to show that a given sentence can be expressed in $\Pi^0_1$ form - for example, the Riemann hypothesis can be, but as it is usually stated the Riemann hypothesis is not even a sentence in the language of arithmetic.

• $\Pi^0_2$ sentences are related to algorithms: if a $\Pi^0_2$ sentence is true there must be a function which Skolemizes the existential quantifier of the sentence. Even if we know the original sentence is provable in PA, the complexity of constructing a suitable Skolem function may still be of significant interest. This is also related to a research program known as "proof mining" and to other research programs in computability theory.

• Similarly, the weak theory of arithmetic known as PRA, which is closely related to the program of mathematical finitism, is mostly concerned with $\Pi^0_2$ sentences, because these are the ones that have the most finitistic meaning.

• In various cases, there are "conservation theorems" which show that if a sentence of a particular form is provable in a particular stronger theory, then it is also provable in a particular weaker theory. To apply one of these theorems, we have to compute the complexity of the sentence. A trivial example is that any $\Sigma^0_1$ sentence provable in PA is provable in Robinson's arithmetic Q. There are much more subtle conservation theorems, as well.

• In many other cases, we are interested in the complexity of a formula with one free variable, in terms of the computability or noncomputability of the set that the formula defines. Post's theorem establishes a tight relationship, but we have to compute the complexity of the relevant formula in order to apply the theorem.

On the other hand, few sentences that arise naturally in mathematics have many meaningful alternations of quantifiers. I doubt I have ever seen a natural example of a $\Sigma^0_{20}$ sentence with explicitly written quantifiers, although it is easy to make a cooked-up example. So the low levels are also of interest because they arise often in practice.

Answer 2

The classes $\Pi^0_n,\Sigma^0_n,\Delta^0_n$ (and their higher generalizations) are purely syntactic - they don't refer to the meaning of a sentence, only its form. For instance, the sentence $$\forall x\exists y\forall z\exists w(0=0)$$ is strictly $\Pi^0_4$, even though it's trivial to prove even in the empty theory!

Meanwhile, there's a separate notion which we might call the essential complexity of a sentence - the essential complexity of a formula $\varphi$ is the smallest complexity class containing some $\psi$ provably equivalent to $\varphi$. This is dependent on a choice of theory: e.g. the sentence $$\forall x(0+1=1+0)$$ is strictly $\Pi^0_1$, has essential complexity $\Pi^0_1$ over the empty theory, and has essential complexity $\Sigma^0_0=\Pi^0_0=\Delta^0_0$ over PA.

Some texts - such as the one you cite - only use the essential complexity; I think this is a bad choice, since it makes everything theory-dependent in a way I think obscures things. What I've written above goes against the particular text you're using, but I think it will clarify things substantially for you.

Classifying the essential complexity of a sentence over a theory can tell us some things about that sentence's behavior within the theory. For instance, at a coarse level we have the facts you mentioned:

• If $\varphi$ is decidable (provable or disprovable!) in $T$, then $\varphi$ has essential complexity $\Sigma^0_0=\Pi^0_0=\Delta^0_0$ in $T$, and for reasonable $T$ the converse is also true. (So the nontrivial part of the arithmetic hierarchy really is about analyzing the undecidable-in-$T$ sentences.)

• If $T$ is an $\Sigma^0_1$-complete theory of arithmetic and $\varphi$ has essential complexity $\Pi^0_1$ over $T$, then $\varphi$ is true if $T$ doesn't disprove $\varphi$. (If we additionally assume $T$ is $\Pi^0_1$-sound, then $\varphi$ is true iff $T$ doesn't disprove $\varphi$.)

This may seem somewhat anticlimactic; that's fine! In my opinion, classifying the sentences

Incidentally, for appropriate $T$ it's easy to show that the essential arithmetical hierarchy is strict: for each $n$ we can cook up a sentence $\varphi$ whose essential complexity is $\Sigma^0_n$. This is a good exercise - for simplicity, assume $T=PA$, and then afterwards try to see what "appropriate" should mean here. As a hint, you might consider using the last paragraph of this answer ...

---

As an aside, there is a theory-independent hierarchy of sets of natural numbers coming from the arithmetical hierarchy: given a set $X$ of natural numbers, say $X$ is $\Pi^0_n$ (etc.) if there is a $\Pi^0_n$ (etc.) formula $\varphi(x)$ such that for each $n\in\mathbb{N}$, $n\in X$ iff $\varphi(n)$ holds in the standard model $\mathbb{N}$. This is also called the "arithmetical hierarchy" (of sets this time), which can be confusing at first. It corresponds to the jump hierarchy: a set is $\Sigma^0_n$ iff it is many-one reducible to ${\bf 0^{(n)}}$. (In particular, $\bf 0^{(n)}$ itself is $\Sigma^0_n$.) Classifying sets in the arithmetical hierarchy turns out to be extremely useful in computability theory.