3
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Joel David Hamkins
    Commented Jun 23, 2012 at 11:28
  • $\begingroup$ 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. $\endgroup$
    – Mirco A. Mannucci
    Commented Jun 23, 2012 at 12:10
  • $\begingroup$ 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$. $\endgroup$
    – Joel David Hamkins
    Commented Jun 23, 2012 at 14:14
  • $\begingroup$ 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. $\endgroup$
    – Andreas Blass
    Commented Jun 23, 2012 at 16:08
  • $\begingroup$ 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". $\endgroup$
    – Mirco A. Mannucci
    Commented Jun 23, 2012 at 17:15

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Ali Enayat
    Commented Jun 28, 2012 at 1:30
  • $\begingroup$ 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$. $\endgroup$
    – Joel David Hamkins
    Commented Jun 28, 2012 at 9:32
  • $\begingroup$ Joel, you are right, my concern is with the wording of David's answer. $\endgroup$
    – Ali Enayat
    Commented Jun 30, 2012 at 14:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .