Skip to main content
MathOverflow

Return to Question

added 609 characters in body
Source Link
Mirco A. Mannucci
Mirco A. Mannucci
  • 7.9k
  • 4
  • 36
  • 66

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.

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.

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.

Source Link
Mirco A. Mannucci
Mirco A. Mannucci
  • 7.9k
  • 4
  • 36
  • 66

Godel 's Ladder: Undecidable PI_N sentences for N =2, 3, ......

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.