Are there new statement at every stage of the arithmetical hierarchy?

Question

Are there new statements at every stage of the arithmetical hierarchy?

Question:

Given an $n\in \Bbb N_0$. Can you give me a statement in $\Pi_n^0$ or $\Sigma_n^0$ which is not also in $\Sigma_{n-1}^0$ or $\Pi_{n-1}^0$? How can we know that the given example can not be reduced to fit in a lower stage?

By a statement $\varphi$ being classified as $\Pi_n^0$ I mean that $\varphi$ is logically equivalent (over the empty theory) to a statement of the form

$$\underbrace{\forall\exists\cdots\exists\forall}_{n\text{ times}}\psi \qquad\text{or}\qquad \underbrace{\forall\exists\cdots\forall\exists}_{n\text{ times}}\psi$$

for some sentence $\psi$ with only bounded quantifiers. I dropped the quantified variables and also the possible repetition of $\forall$ and $\exists$, but I hope it is clear what I mean. Equivalently for $\Sigma_n^0$.

I once read that in the case $\text{P}=\text{NP}$ the arithmetical hierarchy would collapse to finite height. Is this true? If so, then currently no one can answer whether there are new statements at arbitrarily high stages. But one can still answer for "gaps" in the hierarchy, i.e. a single stages at which no new statement occure, but for which there are new statements above it.

Answer 1

The easiest way to prove this is to construct $\Sigma_n^0$ truth predicates, which are themselves $\Sigma^0_n$ formulas, for $n>0$.

Then one can show that a $\Sigma^0_n$ truth predicate cannot be $\Pi^0_n$ as well, using the usual diagonalization tricks.

If $\varphi$ is a $\Sigma_n$ truth predicate, then $\exists x\lnot\varphi$ is a $\Sigma^0_{n+1}$ statement which is not $\Sigma^0_n$. If it were, then $\lnot\varphi$ would have be $\Sigma_n^0$ as well, and then $\varphi$ would be $\Pi^0_n$.

---

To construct a truth predicate, however, one has to do some legwork. First show there is a $\Sigma_1$ predicate taking codes for $\Sigma_0$ statements and assignments, then computing their truth value. Then work out the quantifiers on the code of a formula into a more complicated definition, and all in all, you get a $\Sigma_n$ truth predicate using a $\Sigma^0_n$ formula.

Answer 2

According to Post's theorem, if we let $0^{(n)}$ denote the $n$th Turing jump of the empty set, then for all $n \geq 1$, the set $0^{(n)}$ is defined by a $\Sigma^0_{n}$ formula - call it $\phi_n$ - and cannot be defined by any $\Pi^0_{n}$ formula. Hence $\phi_n$ is $\Sigma^0_n$ but not equivalent to a formula of any lower complexity in the arithmetical hierarchy. This is a standard result in computability theory (along with the fact that the arithmetical hierarchy does not collapse).

In some sense, this is a variation of the answer by Asaf Karagila, because if we let $T_n$ be the truth set for $\Sigma^0_n$ sentences then $T_n$ and $0^{(n)}$ are $1$-equivalent for each $n \geq 1$.