Timeline for Godel 's Ladder: Undecidable PI_N sentences for N =2, 3, ......
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 26, 2012 at 0:11 | comment | added | Joel David Hamkins | Andreas, it seems that my original conjunction would fit your criterion. Perhaps what is wanted is simply a $\Pi^0_n$-complete set, since this can be viewed as a scheme of $\Pi^0_n$ statements, many of which will have to be independent (since otherwise the complexity would collapse by searching for proofs). Thus, David's answer provides the key. | |
| Jun 23, 2012 at 17:21 | vote | accept | Mirco A. Mannucci | ||
| Jun 23, 2012 at 17:21 | comment | added | Mirco A. Mannucci | What this "graspability" should be is the philosophical gist of my question. Meanwhile, though, David's answer, modulo its proper arithmetization, is a valid answer, so I am going to accept it, for the time being. Maybe someone in MO will manage to reformulate my question in a better way. | |
| Jun 23, 2012 at 17:15 | comment | added | Mirco A. Mannucci | 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". | |
| Jun 23, 2012 at 16:08 | comment | added | Andreas Blass |
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.
|
|
| Jun 23, 2012 at 14:14 | comment | added | Joel David Hamkins | 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$. | |
| Jun 23, 2012 at 13:36 | answer | added | David Harris | timeline score: 2 | |
| Jun 23, 2012 at 12:19 | history | edited | Mirco A. Mannucci | CC BY-SA 3.0 |
added 609 characters in body
|
| Jun 23, 2012 at 12:10 | comment | added | Mirco A. Mannucci | 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. | |
| Jun 23, 2012 at 11:28 | comment | added | Joel David Hamkins | 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? | |
| Jun 23, 2012 at 10:53 | history | asked | Mirco A. Mannucci | CC BY-SA 3.0 |