Die Selbstreferenzialität des P / NP-Problems wurde manchmal als Hindernis für seine Lösung herausgestellt, siehe zum Beispiel Scott Aaronsons Artikel: Ist P vs. NP formal unabhängig ? Eine der vielen denkbaren Lösungen für P / NP wäre der Nachweis, dass das Problem formal unabhängig von ZFC oder wahr, aber nicht beweisbar ist.
Es ist vorstellbar, dass die Selbstreferenzialität des Problems eine tiefere Herausforderung für die Beweise der Unabhängigkeit darstellen kann, zum Beispiel wenn Aussagen über seine Beweisbarkeit selbst unbeweisbar oder auf andere Weise unmöglich zu begründen sind.
Nehmen wir an, wir nennen einen Satz T Godel_0, wenn er wahr, aber im Sinne von Godels Satz nicht beweisbar ist. Rufe T Godel_1 auf, wenn die Aussage "T is Godel_0" wahr ist, aber nicht beweisbar. Nenne T Godel_i, wenn die Aussage "T ist Godel _ {(i-1)} wahr ist.
Wir wissen, dass Godel_0-Anweisungen existieren, und es wurden einige Beispiele "in the wild" gefunden, die nicht explizit für diesen Zweck konstruiert wurden, wie in diesem Artikel .
Meine Frage ist: Gibt es Godel_1-Aussagen oder höher? Sind solche Aussagen eine natürliche Folge von Godels Theorem?
Was ist mit einer Aussage, über die wir absolut nichts beweisen können: dh eine, für die für jedes k > 0 T Godel_k ist?
Ich kann eine analoge Frage zur formalen Unabhängigkeit stellen, obwohl ich vermute, dass die Antwort dort "nein" ist.
Um auf die Frage P vs. NP zurückzukommen, lassen Sie mich fragen, ob es überhaupt einen Hinweis darauf gibt, dass der Satz von Godel für Fragen der Klassentrennbarkeit relevant ist. Wurden in Bezug auf die Komplexitätsklassen irgendwelche wahren, aber unbeweisbaren Aussagen gemacht - natürlich jenseits des offensichtlichen Zusammenhangs zwischen dem Halteproblem und Godels Theorem?
quelle
Antworten:
Wie bereits erwähnt, gibt es bei der Beantwortung Ihrer Frage bestimmte technische Schwierigkeiten. Um sie zu begradigen, lassen Sie uns zunächst die Verwendung des Begriffs "unbeweisbar" ohne Einschränkung vermeiden und explizit angeben, aus welchen Axiomen Ihre Aussage T unbeweisbar sein soll. Nehmen wir zum Beispiel an, dass wir an Aussagen T interessiert sind, die für PA, die Axiome der Peano-Arithmetik erster Ordnung, nicht beweisbar sind.
Das erste Ärgernis ist, dass "T ist wahr" nach Tarskis Theorem in der Sprache erster Ordnung der Arithmetik nicht ausgedrückt werden kann. Wir könnten das umgehen, indem wir in einer Metatheorie arbeiten, die stark genug ist, um die Wahrheit einer arithmetischen Aussage zu definieren, aber ich denke, für Ihre Zwecke ist dies ein unnötig komplizierter Weg. Ich denke, Sie interessieren sich nicht so sehr für die Wahrheit an sich, sondern für die Beweisbarkeit. Ich vermute, Sie geben sich damit zufrieden, T als Godel_0 zu definieren, wenn T wahr, aber in PA nicht beweisbar ist, und T als Godel_1 zu definieren, wenn T in PA nicht beweisbar ist, aber "T in PA nicht beweisbar ist" in PA nicht beweisbar ist. und die Definition von T als Godel_2, wenn T in PA nicht beweisbar ist und "T in PA nicht beweisbar ist" in PA nicht beweisbar ist, aber "T in PA nicht beweisbar ist" in PA nicht beweisbar ist ", usw.
Dies reicht aus, um Ihre Frage zu präzisieren, aber leider gibt es dann eine eher triviale Lösung. Nehmen Sie T = "PA ist konsistent." Dann ist T wahr, weil PA konsistent ist, und T ist in PA nach Goedels zweitem Unvollständigkeitssatz nicht beweisbar. Außerdem ist "T ist in PA nicht beweisbar" aus einem etwas albernen Grund auch in PA nicht beweisbar: Jede Aussage der Form "X ist in PA nicht beweisbar" ist in PA nicht beweisbar, weil "X ist in PA nicht beweisbar" trivial impliziert, dass "PA konsistent ist "(da inkonsistente Systeme alles beweisen ). T ist also Godel_n für alle n, aber ich weiß nicht, ob dies wirklich zu Ihrer beabsichtigten Frage passt.
Wir könnten versuchen, Ihre Frage zu "flicken", um solche Kleinigkeiten zu vermeiden. Lassen Sie mich stattdessen versuchen, auf die Frage einzugehen, die Sie meiner Meinung nach haben. Stillschweigend glaube ich, dass Sie die logische Stärke, die erforderlich ist, um einen Satz zu beweisen, mit der psychologischen Schwierigkeit in Einklang bringenes zu beweisen. Das heißt, Sie interpretieren ein Ergebnis der Form "T ist in X nicht beweisbar" so, dass T in irgendeiner Weise über unsere Fähigkeit hinausgeht, es zu verstehen. Es gibt diese monströsen Vermutungen da draußen, und wir töten Menschen, die PA- oder ZFC-Peitschen knacken oder was haben Sie gegen diese wilden Bestien, die versuchen, sie zu zähmen. Aber ich denke nicht, dass "T ist unbeweisbar in X" so interpretiert werden sollte, dass "T ist unmöglich zu überlegen". Es wird vielmehr nur eine bestimmte technische Eigenschaft von T gemessen, nämlich die logische Stärke. Wenn Sie also versuchen, das Über-Monster zu finden, ist es meiner Meinung nach nicht die richtige Richtung, etwas zu finden, das nicht nur unbeweisbar ist, sondern dessen Unbeweisbarkeit unbeweisbar ist, usw.
Bezüglich Ihrer Frage, ob Unprovierbarkeit überhaupt mit der Trennbarkeit von Komplexitätsklassen zusammenhängt, gibt es schließlich einige Zusammenhänge zwischen rechnerischer Unprovierbarkeit und Unprovierbarkeit in bestimmten Systemen beschränkter Arithmetik. Einiges davon wird in dem von Ihnen zitierten Artikel von Aaronson erwähnt. siehe auch Cook und Nguyens Buch Logical Foundations of Proof Complexity .
quelle
Ich bin mir bei der Definition von Godel_1 nicht so sicher. Können Sie versuchen, es ein bisschen mehr zu formalisieren?
Wie können Sie die Formel "T is Godel_0" kodieren? Dafür müssen Sie irgendwie codieren, dass "T ist semantisch wahr", ohne sich auf den Beweisbegriff zu beziehen. Wie kannst du das machen?
quelle
Für jedes n existieren Godel_n-Anweisungen. Das könnte Sie auch interessieren: The Unprovability of Consistency, ein Buch von George Boolos. Er definiert eine modale Logik, in der Box bedeutet "ist nachweisbar", Diamond bedeutet "ist konsistent" und untersucht dann das Verhalten von Sätzen vom Typ Godel. (Er schrieb auch ein Folgebuch, The Logic of Provability.)
quelle