Sind rekursive Formen von Godels Aussage möglich?

20

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?

Anand Kulkarni
quelle
Dies ist möglicherweise besser für die Logiker bei MO geeignet. Sie können jederzeit angeben, ob dies der Fall ist.
Anand Kulkarni

Antworten:

14

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 .

Timothy Chow
quelle
In der Tat löst Ihr triviales Beispiel die Frage, und ich bin froh zu sehen, dass es eine so einfache Lösung hatte - ich hatte vermutet, dass solche Aussagen wahrscheinlich gleichwertig waren. Es geht mir jedoch nur um logische Stärke, nicht um die psychologische Schwierigkeit, Dinge zu beweisen oder zu argumentieren. Mit meiner Frage wollte ich fragen: "Ist es jemals formell schwieriger, die Unbeweisbarkeit einer Aussage zu beweisen, als zu beweisen, dass eine Aussage unbeweisbar ist?" Ihr Beispiel scheint darauf hinzudeuten, dass die Antwort "nein" ist.
Anand Kulkarni
Ich verstehe Ihre umformulierte Frage nicht ganz, weil Sie immer noch das Wort "unbeweisbar" ohne Einschränkung verwenden. Angenommen, T1 ist in X1 nicht beweisbar. Dann ist "T1 ist in X1 unbeweisbar" (nennen Sie diese Anweisung T2) in einigen Systemen nachweisbar und in anderen nicht. Interessieren Sie sich für die (Un) Beweisbarkeit von T2 in X1 selbst oder in einem anderen System X2? Wenn letzteres der Fall ist, existieren im Allgemeinen Systeme X3, die T2 beweisen, aber nicht "T2 ist in X2 nicht beweisbar".
Timothy Chow
8

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?

Ohad Kammar
quelle
1
Hervorragender Punkt. Der Begriff der Wahrheit ist unmöglich in einer konsistenten "stark genug" Logik zu kodieren.
Ripper234
Wie Sie meinen, bin ich mir nicht sicher, ob die Aussage ohne explizit definierte Begriffe von Wahrheit und Beweisbarkeit formalisiert werden kann. Ich nehme an, es ist offensichtlich, was ich im informellen Sinne meine: Eine Aussage T ist Godel_1, wenn die Aussage "T ist wahr, aber nicht beweisbar" wahr, aber nicht beweisbar ist. Wenn der Satz von Godel lose lautet: "Es gibt keinen Beweis für diesen Satz", könnte ein Satz von Godel_1 lauten: "Es gibt keinen Beweis für den Satz" Es gibt keinen Beweis für diesen Satz "." der inneren Aussage ist jedoch wahr
Anand Kulkarni
6

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.)

Aaron Sterling
quelle
Könnten Sie die Ergebnisse von Boolos erläutern? Beweist er, dass solche Aussagen existieren?
Anand Kulkarni
Argh. Ich las das erste Buch, nicht das zweite, aber das war vor einer Million Jahren, als ich dachte, ich würde Logik machen, als ich groß war. Ich habe sogar mein Exemplar des Buches an eine Buchhandlung verkauft. Ich könnte nachsehen, ob es hier in der Bibliothek ist. Wenn ich es mir noch einmal anschaute, konnte ich mich wahrscheinlich einigermaßen schnell an die Dinge erinnern. Keine Versprechungen, und tut mir leid, dass ich nicht mehr helfe.
Aaron Sterling