2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Who told you that P=NP would collapse the arithmetical hierarchy? $\endgroup$ – Asaf Karagila Jun 8 '17 at 10:46
  • $\begingroup$ @AsafKaragila I remember that I might have read this in a book on complexity theory. Could be wrong tho. This is why I am asking. I cannot trust my memory here ;). So by your reaction I can assume it is wrong? $\endgroup$ – M. Winter Jun 8 '17 at 10:48
  • 2
    $\begingroup$ Also by my answer which shows that you can explicitly construct such statements. So unless P=NP implies that PA is inconsistent... $\endgroup$ – Asaf Karagila Jun 8 '17 at 10:51
  • 3
    $\begingroup$ The result you heard about P = NP is certainly about the polynomial hierarchy, en.wikipedia.org/wiki/Polynomial_hierarchy . The entire polynomial hierarchy is a subset and refinement of the class $\Delta^0_1$ in the usual arithmetical hierarchy. $\endgroup$ – Carl Mummert Jun 8 '17 at 14:57
  • $\begingroup$ There is an analogy between the polynomial hierarchy and the arithmetical hierarchy, but they're not as close (or at least, not known to be as close) as they might appear at first glance. Incidentally, it's not the only such analogue: lots of natural complexity classes give rise to parallel analogues, of varying similarity (e.g. some of them collapse). The polynomial hierarchy is merely the most interesting, at least at the moment. $\endgroup$ – Noah Schweber Jun 8 '17 at 15:34
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am not very familiar with the terminology here. Let me guess what a $\Sigma_n^0$ truth predicate is: a predicate $P(n)$ which is satisfied if and only if $n$ is the Gödel number of some provable (or true, w.r.t. to the standard model??) $\Sigma_n^0$-sentence? $\endgroup$ – M. Winter Jun 8 '17 at 11:03
  • 1
    $\begingroup$ Not provable, true. $\endgroup$ – Asaf Karagila Jun 8 '17 at 11:10
  • 2
    $\begingroup$ No, I'm talking about truth in the standard model. And indeed such predicates are surprising. They give us a very strong form of "PA proves the consistency of its finite subtheories" by replacing "finite" by "bounded". $\endgroup$ – Asaf Karagila Jun 8 '17 at 11:15
  • 1
    $\begingroup$ @M.Winter In general, referring to a statement inthe language of arithmetic as "true" means "true in the standard model" - this is the case across logic, as far as I'm aware. A sentence which is true in every $\Sigma$-structure is valid, or a validity - and a sentence which is true in every model of a theory $T$ is usually called a $T$-validity. $\endgroup$ – Noah Schweber Jun 8 '17 at 15:28
  • 1
    $\begingroup$ (Sadly, there are texts which say things like "true in $T$" where $T$ is a theory; I find this a terrible conflation. Regardless, the point about truth in the context of arithmetic stands.) $\endgroup$ – Noah Schweber Jun 8 '17 at 15:31
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1 - for whatever reason, I've found that bounded truth predicates tend to cause some confusion in a way that the jumps don'. Incidentally to the OP: the task of proving that the arithmetical hierarchy in the sense of computability theory doesn't collapse is just the proof that the Halting Problem is incomputable, appropriately relativized; the more interesting part is showing that $0^{(n)}$ is definable in the language of arithmetic by a $\Sigma^0_n$ formula, and this is basically the same as constructing a $\Sigma^0_n$-truth predicate. $\endgroup$ – Noah Schweber Jun 8 '17 at 15:33
  • $\begingroup$ I think so too. And the most natural way of constructing a $\Sigma^0_n$ truth predicate is to first construct a $\Sigma^0_1$ truth predicate, and that in turn is easiest to do by first defining Kleene's T predicate to encode a universal Turing machine in a $\Sigma^0_1$ way, and then programming the universal machine to decide the truth of quantifier-free sentences. Directly defining a universal $\Sigma^0_1$ formula without going through the T predicate would be possible, but probably even more tedious work than just defining the T predicate. $\endgroup$ – Carl Mummert Jun 8 '17 at 17:58
  • $\begingroup$ @Noah, Carl: In the last couple of years I was TA'ing the course about incompleteness in HUJI, and we usually teach about truth predicates. Of course, computability models (using register machines) are being taught, so the notion of a universal machine is somewhat accessible for us. Nevertheless, I think that the confusion is mostly after the fact. When the students haven't fully grasped the minutes of Tarski's theorem, this is not entirely surprising. Last year, though, we didn't go through the machines, but rather directly arguing there is a truth predicate. I think it was well received. $\endgroup$ – Asaf Karagila Jun 8 '17 at 21:11

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.