MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

After Godel's groundbreaking results, a plethora of $\Pi_1^0$ undecidable arithmetical sentences have been found by many authors.

But what about $\Pi_n^0$ for $n=2,3,.....$ ?

There are, to my knowledge (but I am no expert) a few examples on the low end of the ladder, for instance Svejdar, a student of Petr Hajek, in the early eighties initiated the study of interpretability logic, and in the process identified one such sentence.

Now, my question:

Is there some systematic procedure/strategy for building a list of progressively higher (in the sense of the arithmetical hierarchy) undecidable sentences?

NOTE: I would think that one option could be to follow Svejdar's steps, and identify sentences which express higher (and/or looser) forms of auto-referentiality.

ADDENDUM: As Joel Hamkins has immediately pointed out in the comment below, the question, as formulated above, is entirely trivial (you simply join a pi_0 godelian sentence with a known to be true pi_n sentence and the game is over). I guess it should be emended by ruling out such cases, and stipulating that the rungs of the ladder should be $\Pi_0^n$ sentences which are undecomposable, meaning that they cannot be boolean-broken in smaller pieces where a $\Pi_0^k$ with k less than n undecidable is found. The idea is that the new rung should express a genuine new (higher) form of undecidability.

share|cite|improve this question
What is to stop you from taking an independent $\Pi^0_1$ statement and conjuncting it with a given $\Pi^0_n$ statement known to be true? – Joel David Hamkins Jun 23 '12 at 11:28
Touche'. Absolutely nothing Joel. My sloppily formulated question does not rule out tricks like yours. Of course that is not what I am after, I am looking for real higher order forms of undecidability, but I need to be more precise. – Mirco A. Mannucci Jun 23 '12 at 12:10
Mirco, your indecomposability concept admits other tricks, if one only considers assertions up to logical equivalence, since every statement $\varphi$ is equivalent to $(\phi\vee\neg\phi)\wedge\varphi$, even when $\phi$ is much simpler than $\varphi$. – Joel David Hamkins Jun 23 '12 at 14:14
I conjecture that what Mirco really wants is a $\Pi^0_n$ sentence that is not provably equivalent to a $\Sigma^0_n$ sentence (and therefore not provably equivalent to any sentence at any lower level of the arithmetical hierarchy). Maybe he also wants it to not be too explicitly about computability, but it's not clear where the boundary of "too explicitly" would be. – Andreas Blass Jun 23 '12 at 16:08
Joel, yes, my indecomposability was not adequate (to my partial excuse I say I just made it up before my morning coffee). Perhaps Andreas ' own emendation is. At all event, this is interesting: I see now that my question was ill-posed, and by no means easy to make clear. Andreas is right on the computability side, in that what I have in mind is basically this: the ground zero is provability, ground one (ie $\Pi_2) seems to be partially captured by interpretability, so it looks like that genuine godelian sentences higher up would capture broader notions of "graspability". – Mirco A. Mannucci Jun 23 '12 at 17:15
up vote 2 down vote accepted

The halting set relative to an oracle deciding $\Pi_{n-1}$ sentences, provides such a sentence. This set is $m$-complete for $\Pi_n$.

share|cite|improve this answer
David, how exactly does the set you describe provide "such a sentence"? It seems to me that your solution is conflating two meanings of the word "undecidable": one meaning applies to a set of integers, the other to a sentence. – Ali Enayat Jun 28 '12 at 1:30
But Ali, those two notions are deeply connected: every strictly $\Pi^0_n$ set $A$, for nonzero $n$, has infinitely many $k$ for which the assertion $k\in A$ is independent of your favorite theory, for otherwise the proof-search algorithm would show that $A$ is not actually $\Pi^0_n$. – Joel David Hamkins Jun 28 '12 at 9:32
Joel, you are right, my concern is with the wording of David's answer. – Ali Enayat Jun 30 '12 at 14:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.