Einige Zweifel an Unvollständigkeitssätzen

Ein wichtiger Punkt, der beim ersten Unvollständigkeitssatz zu beachten ist, ist, dass eine bestimmte Formel zwar "wahr", aber nicht beweisbar ist, aber auf der Grundlage meines Verständnisses ( beabsichtigte Interpretation) des fraglichen "formalen Systems" "wahr". Das ist, glaube ich, gemeint, wenn gesagt wird, dass man sehen kann , dass es wahr ist. Wikipedia liefert Erklärung:

Der Gödel-Satz soll indirekt auf sich selbst verweisen. Der Satz besagt, dass, wenn eine bestimmte Abfolge von Schritten verwendet wird, um einen anderen Satz zu konstruieren, dieser konstruierte Satz in F nicht beweisbar ist. Die Abfolge von Schritten ist jedoch so, dass sich herausstellt, dass der konstruierte Satz selbst GF ist. Damit stellt der Gödel-Satz GF indirekt seine eigene Unbeweisbarkeit innerhalb von F dar (Smith 2007, S. 135).

... Der erste Unvollständigkeitssatz zeigt, dass der Gödelsatz GF einer geeigneten formalen Theorie F in F unbeweisbar ist. Denn als Aussage über Arithmetik interpretiert, ist diese Unbeweisbarkeit genau das, was der Satz (indirekt) behauptet, der Gödelsatz ist , in der Tat wahr (Smoryński 1977 S. 825; siehe auch Franzén 2005 S. 28–33). Aus diesem Grund wird der Satz GF oft als „wahr, aber nicht beweisbar“ bezeichnet. (Raatikainen 2015).

Bisher geht es mir gut. Als nächstes kommt Konsistenz.

System kann seine eigene Konsistenz nicht nachweisen. Konsistenz beweisen bedeutet "Es ist nicht möglich, einen Widerspruch abzuleiten, dh 1=0". Wird diese Aussage bewiesen, ist Konsistenz hergestellt. Zweiter Satz: Konsistenz kann innerhalb des Systems nicht bewiesen werden. Ich kann also ein Axiom hinzufügen, dass mein System S konsistent ist, und zu einem neuen System S' gelangen, wobei S' = S + (S ist konsistent). Meine Frage ist:

  1. Dies macht S immer noch nicht konsistent! Oder doch? Wenn ich die Regeln des Systems S verstehe, kann ich die Konsistenz von S wieder sehen , aber nicht beweisen , oder ist die Konsistenz von S immer noch eine offene Frage?
  2. Wie hängt die Konsistenz eines Systems S mit der universellen Turing-Maschine für die Logik erster Ordnung zusammen? Ich meine, was ist das technische Analogon der Konsistenz in Turing-Maschinen? Ist mein Computer wirklich nicht beweisbar konsistent ? Und bedeutet das, dass es eines Tages einen erkennbaren Widerspruch geben kann?
1. Konsistenz ist noch eine offene Frage. Sie kann innerhalb der Metatheorie bewiesen werden (siehe Konsistenzbeweis von Gentzen).
2. Die Tatsache, dass die betreffende Theorie ihre eigene Konsistenz nicht beweisen kann, bedeutet nicht, dass sie widersprüchlich ist. Bis jetzt hat noch niemand Inkonsistenzen in der Arithmetik gefunden...
Man kann auch auf starke Intuitionen verweisen, dass die grundlegenden Axiome und Funktionsdefinitionen in der Peano-Arithmetik nicht widersprüchlich sein werden, weil sie semantisch als Beschreibung wahrer Tatsachen über das Zählen, Addieren und Multiplizieren von finiten Elementen verstanden werden können ... zum Beispiel ein Argument für A B=B A immer gilt, dass Sie sich "A*B" als rechteckiges Array mit A-Reihen und B-Punkten pro Reihe vorstellen können (also hat jede Spalte A-Punkte, jede Reihe B-Punkte), und dann drehen Sie einfach Bei 90 Grad haben Sie ein rechteckiges Array mit B-Reihen und A-Punkten pro Reihe (jede Spalte hat B-Punkte, jede Reihe hat A-Punkte).
@MauroALLEGRANZA Können wir daraus schließen, dass es unmöglich ist, die Konsistenz des Geistes (im mathematischen Bereich) zu beweisen? Schließlich ist Meta-Theorie Verstand (wenn nicht sofort, dann nach vielen, vielen Iterationen von S,S',S'', ..., S(aleph-null) ... und so weiter - vielleicht an der Grenze .
Betrachten Sie „ex falso quodlibet“. Wenn Ihr System inkonsistent ist, können Sie natürlich beweisen, dass es konsistent ist. Sie leiten die Konsistenz einfach aus dem Widerspruch ab, der sie als widersprüchlich erweist. Wenn Sie also Ihr Konsistenzaxiom hinzufügen, können Sie beweisen, dass Sie es nicht verletzen, selbst wenn Sie es verletzen. Das Problem ist, dass sowohl konsistente als auch inkonsistente Systeme daraus schließen können, dass sie Ihr Axiom nicht verletzen würden. Es hat also nichts zu bedeuten.
Wenn das System inkonsistent ist, dann ist S bereits ein Theorem, also ändert das Hinzufügen als Axiom nichts. Wenn das System konsistent ist, wird das System durch Hinzufügen von S inkonsistent, da Sie jetzt einen (einzeiligen) Konsistenzbeweis hätten, der dem Satz von Gödel widerspricht.
Traditionell ist eine Theorie das, was eine Turing-Maschine rekursiv aufzählen würde. Das Anhalten in der Aufzählung, wenn sie mit der fraglichen Aussage übereinstimmt, ist dann gleichbedeutend mit einem Beweis. Inkonsistente Systeme können alles beweisen. Konsistenz würde also bedeuten, dass es Aussagen gibt, bei denen die Maschine nicht stehen bleibt. Leider können wir nicht sagen, ob die Maschine anhalten wird, bis wir unendlich lange darauf gewartet haben. Wir können also nicht wissen, ob das System konsistent ist, ob wir nur versehentlich eine wahre, aber nicht beweisbare Aussage gewählt haben oder ob wir einfach nicht lange genug gewartet haben.
@Nick Basierend auf dieser Antwort widerspricht es anscheinend nicht Gödels Satz, ein neues Axiomatiksystem S2 zu erstellen, das gebildet wird, indem die Axiome von S genommen und ein Axiom hinzugefügt werden, das die Konsistenz von S behauptet. S2 kann seine eigene Konsistenz immer noch nicht beweisen, daher gilt Gödels Theorem. Andererseits lautet die Antwort, wenn Sie eine Aussage 𝜑 haben, die so etwas wie "das axiomatische System, das durch Nehmen der Axiome von S und Hinzufügen von 𝜑 als Axiom gebildet wird, konsistent ist" hat, dann wäre das Hinzufügen von 𝜑 zu den Axiomen S inkonsistent.
@Hypnosifl Danke. Ja, ich stehe korrigiert. Die Behauptung der Konsistenz von "T" sagt nichts über die Konsistenz von "T"+"CON(T)" aus. Ein ziemlich subtiler Punkt - offensichtlich zu subtil für mich.
"Können wir daraus schließen, dass es unmöglich ist, die Beständigkeit des Geistes zu beweisen ..." NEIN; Gödels Th gilt für formale Systeme mit einigen spezifischen Merkmalen. Der menschliche Geist ist kein formales System. Wenn wir außerdem versuchen, die menschliche Sprache als „System“ zu betrachten, ist sie eindeutig widersprüchlich.
@MauroALLEGRANZA Vielen Dank für Ihren Kommentar. Können wir aber nicht das menschliche Denken in seiner Gesamtheit (dh nicht nur das, was wir jetzt tun, sondern was wir grundsätzlich tun können) als ein "vernünftiges" formales System betrachten und deshalb Gödels Th anwenden?
@Ajax - ein System bedeutet: feste Sprache, feste Regeln zum Bilden von Ausdrücken, feste Regeln zum Ableiten neuer Formeln aus Axiomen und einem rekursiven Satz von Axiomen. Wenn ja, wo sind die Axiome? Denken Sie daran, dass aus intuitiver Sicht das Prinzip des naiven Verständnisses als gutes Beispiel für das Axiom des "gesunden Menschenverstandes" angenommen werden kann. Damit leiten wir das bekannte Paradoxon ab. Fazit: Der menschliche Geist ist inkonsequent .
Was die Konsistenz des arithmetischen Systems betrifft, möchte ich die Arbeit von TJ Stępień, Ł. T. Stępień, „Über die Konsistenz des arithmetischen Systems“, Journal of Mathematics and System Science , vol. 7, 43 (2017), arXiv:1803.11072. Es wurde ein Konsistenzbeweis des arithmetischen Systems veröffentlicht. Dieser Beweis wurde innerhalb dieses Systems durchgeführt (die Zusammenfassung zu diesem Artikel: TJ Stepien und LT Stepien, "On the Consistency of Peano's Arithmetic System", The Bulletin of Symbolic Logic , Bd. 16, Nr. 1, 132 (2010) ).

Antworten (2)

Ich kann also ein Axiom hinzufügen, dass mein System S konsistent ist, und zu einem neuen System S' gelangen, wobei S' = S + (S ist konsistent)

Ja, das ist in Ordnung. Wenn Sie mir erlauben, zu Variablen zu wechseln, die leichter voneinander zu unterscheiden sind, können Sie Folgendes haben:

B = A + (A ist konsistent)

Oder auch

C = A + (A ist nicht konsistent)

Beides(!) wird keinen Widerspruch nach sich ziehen (aber C wird nicht omega-konsistent sein , was eine stärkere Form der Konsistenz ist, die entsteht, wenn man versucht, Theorie und Metatheorie miteinander in Einklang zu bringen). Weder B noch C können beweisen, dass B/C selbst konsistent ist, obwohl B offensichtlich beweist, dass A konsistent ist.

Die vollständige Erklärung von C ist hier nicht vorgesehen, aber kurz gesagt, es behauptet, dass ein Beweis für einen Widerspruch, wie z. B. 0 = 1, existiert und mit einer Gödel-Zahl codiert werden kann, aber es stellt sich heraus, dass diese Zahl nicht wirklich existiert existieren im Standardmodell der Arithmetik (es ist keines von 0, 1, 2 usw.). Die Peano-Arithmetik ist nicht stark genug, um die Existenz solcher Nichtstandardzahlen zu widerlegen, daher entsteht kein Widerspruch innerhalb des Systems C. Trotzdem ist es intuitiv offensichtlich, dass C in gewisser Weise „falsch“ ist, und darum geht es bei der Omega-Konsistenz.

Aber es gibt eine große Ausnahme: Wenn A bereits inkonsistent ist, dann beweist es alles , einschließlich seiner eigenen Konsistenz und seiner eigenen Inkonsistenz, und diese Inkonsistenz wird von B und C geerbt . Wann immer wir über einen der Unvollständigkeitssätze sprechen, nehmen wir immer den Konsistenz der Theorie als Grundannahme, weil man sehr wenig über eine inkonsistente Theorie der Arithmetik sagen kann.

Auf der anderen Seite kommen wir mit so etwas nicht durch:

D = A + (D ist konsistent)

Denn es stellt sich heraus, dass das resultierende System, vorausgesetzt, Sie könnten einen Weg finden, die Selbstreferenz auszudrücken (mit geschickter Verwendung der Gödel-Nummerierung), mit dem zweiten Unvollständigkeitssatz in Konflikt geraten und daher inkonsistent wäre.

Nun zurück zu Ihren Fragen:

Dies macht S immer noch nicht konsistent! Oder doch? Wenn ich die Regeln des Systems S verstehe, kann ich die Konsistenz von S wieder sehen, aber nicht beweisen, oder ist die Konsistenz von S immer noch eine offene Frage?

Wenn Sie glauben, dass S' keine Widersprüche beweist (oder äquivalent, dass S' konsistent ist), dann glauben Sie notwendigerweise, dass S konsistent ist, und daher ist kein Beweis erforderlich. Wenn S widersprüchlich wäre, dann wäre auch S' widersprüchlich, und alle "Beweise", die es lieferte, wären wertlos. Daher können Sie S' nicht verwenden, um zu beweisen, dass S konsistent ist, weil Sie entweder bereits glauben, dass S konsistent ist, oder Sie bereits bezweifeln, dass S' konsistent ist, und S' also nichts für Sie bewirkt.

Wie hängt die Konsistenz eines Systems S mit der universellen Turing-Maschine für die Logik erster Ordnung zusammen? Ich meine, was ist das technische Analogon der Konsistenz in Turing-Maschinen? Ist mein Computer wirklich nicht beweisbar konsistent? Und bedeutet das, dass es eines Tages einen erkennbaren Widerspruch geben kann?

Die Tatsache, dass Sie nicht beweisen könnenKonsistenz bedeutet nicht, dass ein System zwangsläufig inkonsistent ist. Mathematiker haben die Konsistenz der Peano-Arithmetik und der Zermelo-Fraenkel-Mengentheorie sehr lange sorgfältig geprüft, und niemand hat jemals gezeigt, dass beide Systeme inkonsistent sind. Wir könnten uns vorstellen, dass eines Tages ein unglaublich subtiler und ausgefeilter Widerspruch konstruiert werden könnte, aber es wäre keine einfache Neuformulierung von zB Russells Paradoxon, da alle „einfachen“ Probleme wie Russells Paradoxon bereits erforscht und „gelöst“ wurden. Wenn wir jemals einen solchen Widerspruch finden, könnte er wahrscheinlich durch eine leichte Modifikation der Axiome eingeschränkt werden, um jede Argumentationslinie auszuschließen, die zu einem Widerspruch führt, sodass wir wahrscheinlich die meisten existierenden mathematischen Theoreme mit wenig Unterbrechung wiederherstellen könnten.

Ehrlich gesagt wäre ich viel mehr besorgt über die Möglichkeit, dass die Software Ihres Computers fehlerhaft oder falsch konzipiert ist, als dass die gesamte Curry-Howard-Korrespondenz irgendwann in naher Zukunft zusammenbrechen wird. Softwarefehler treten ständig auf; Mathematikfehler sind (in den letzten Jahren) viel seltener.

Aber in jedem Fall können die Festkommakombinatoren unter der oben erwähnten CH-Korrespondenz bereits verwendet werden, um Currys Paradoxon wiederzugewinnen (oder besser gesagt, sie wären dazu in der Lage, wenn die CH-Korrespondenz nicht ausdrücklich den untypisierten Lambda-Kalkül ausgeschlossen hätte, in dem Festkomma- Punktkombinatoren entstehen, genau um dieses Problem zu beheben). Tatsächlich haben sich moderne (Turing-vollständige) Programmiersprachen bereits vollständig von der Konsistenz "abgemeldet" (und dies wird noch offensichtlicher, wenn Sie die Möglichkeit einer willkürlichen Typumwandlung in den meisten statisch typisierten Sprachen in Betracht ziehen).

Vielen Dank für Ihre Antwort. Ich bin mit der CH-Korrespondenz nicht sehr vertraut. Können Sie erklären, was der Sinn von CH ist? Gilt das generell? Ist meine Intuition, dass, weil Algorithmus A Theorem T "entscheidet", es der Fall sein muss, dass A den Beweis von T auf irgendeine Weise codiert ... -richtig?
@Ajax: Nein, die Korrespondenz ist viel subtiler und allgemeiner. Es hat mehr mit Typentheorie als mit Berechnungstheorie zu tun. Algorithmen, die Dinge "entscheiden", oder gar Algorithmen im Allgemeinen, sind nicht wirklich der Punkt der CH-Korrespondenz.
Ausgezeichnete Antwort. Vielleicht möchten Sie anmerken, dass die ω-Konsistenz durch die Σ1-Korrektheit abgeschwächt werden kann. C ist kein Σ1-Ton. Deshalb müssen wir glauben, dass B sinnvoll und C bedeutungslos ist, wenn wir glauben, dass A sinnvoll ist.

Nehmen Sie ein inkonsistentes System S und erstellen Sie ein weiteres System S', indem Sie das Axiom „S' ist konsistent“ hinzufügen. Jetzt haben Sie einen sehr einfachen Beweis, dass S' konsistent ist. Aber Sie haben immer noch eine Aussage X mit s-Beweis sowohl für X als auch nicht für X, also ist S' genauso inkonsistent wie S, und Sie haben einen direkten Widerspruch zum hinzugefügten Axiom!

Fügen Sie stattdessen ein Axiom „S' ist vollständig“ hinzu. Aber genau wie in S können Sie eine Aussage X ausdrücken , die laienhaft sagt „es gibt keinen Beweis für die Aussage X“. Wir müssen X nicht beweisen oder widerlegen, allein die Tatsache, dass wir es ausdrücken können , führt dazu, dass Gödels Gesetz zutrifft. Die Existenz von X zeigt, dass S' entweder unvollständig oder inkonsistent ist. Natürlich zeigt das hinzugefügte Axiom, dass S' nicht unvollständig ist, also inkonsistent.

Was ist, wenn wir „S' ist unvollständig“ hinzufügen? Jedes inkonsistente System ist vollständig, also haben wir wieder einen sofortigen Beweis dafür, dass S' konsistent ist. Aber ein Beweis, dass S' konsistent ist, hindert es nicht daran, inkonsistent zu sein, also nichts gewonnen.

Es kommt darauf an, was Sie hier mit "vollständig" meinen. Zum Beispiel ist T:=ZFC+"ZFC ist inkonsistent" eine konsistente Theorie unter der Annahme, dass ZFC selbst ist , aber natürlich beweist T "Für jeden Satz p beweist entweder T p oder T widerlegt p " (da T tatsächlich seine eigene Inkonsistenz beweist ). ZFC + "ZFC ist konsistent und vollständig" ist jedoch inkonsistent.
Einige Zweifel an Unvollständigkeitssätzen
AntwortenHierDatenschutz-Bestimmungen1y, 0v