Beweisbar und widersprüchlich?

Wir müssen uns an die Aussage des Theorems erinnern:

Erster Unvollständigkeitssatz (Gödel) . Jedes ω-konsistente formale System S , innerhalb dessen ein "gewisses Maß" elementarer Arithmetik durchgeführt werden kann, ist bezüglich Aussagen der elementaren Arithmetik unvollständig: dh es gibt solche Aussagen, die in S weder bewiesen noch widerlegt werden können .

Das Argument von Gödels erstem Unvollständigkeitssatz ist etwas komplex.

Außerdem ist die Bedingung der ω-Konsistenz etwas „verworren“; daher werden wir ausgehend von Wikis Darstellung ein "einfaches" Argument entwickeln, wobei wir die Korrektheit des Systems S annehmen [dh das System S beweist keine falschen Sätze; Übrigens impliziert Solidität Konsistenz ].

Wir müssen beginnen mit:

1) Arithmetisierung der Syntax : Das Hauptproblem [ist], eine Aussage p zu konstruieren , die äquivalent ist zu „ p kann nicht bewiesen werden“ [...] Gödels geniale Technik besteht darin zu zeigen, dass Aussagen Zahlen zugeordnet werden können (oft als Arithmetisierung bezeichnet der Syntax so, dass "eine Aussage beweisen" ersetzt werden kann durch "testen, ob eine Zahl eine gegebene Eigenschaft hat" [hier brauchen wir die Eigenschaft von System S , um eine "bestimmte Menge" an Arithmetik einzubeziehen: das System S muss haben genügend Fähigkeiten, um die syntaktischen Beziehungen und Eigenschaften des Systems selbst "auszudrücken".

2) Konstruktion einer Aussage über „Beweisbarkeit“ : Nachdem gezeigt wurde, dass das System im Prinzip indirekt Aussagen über die Beweisbarkeit machen kann, ist es nun möglich, durch die Analyse der Eigenschaften dieser Zahlen, die Aussagen darstellen, zu zeigen, wie man eine Aussage erstellt, die dies tatsächlich tut.

Daher gibt es eine Aussageform Bew(y) , die anhand dieser arithmetischen Beziehung aussagt, dass eine Gödelzahl eines Beweises von y existiert:

Bew(y) = ∃ x ( y ist die Gödelzahl einer Formel und x ist die Gödelzahl eines Beweises [in S ] der durch y codierten Formel ).

Letzter Schritt ist:

Diagonalisierung : Der nächste Beweisschritt besteht darin, eine Aussage zu erhalten, die besagt, dass sie unbeweisbar ist. Obwohl Gödel diese Aussage direkt konstruierte, folgt die Existenz mindestens einer solchen Aussage aus dem Diagonallemma, das besagt, dass es für jedes hinreichend starke formale System und jede Aussageform F eine Aussage p gibt , so dass das System [ S ] beweist:

p ↔ F(G(p)) .

Indem wir F die Negation von Bew(x) sein lassen , erhalten wir den Satz

p ↔ ~Bew(G(p)) ,

und das dadurch definierte p sagt grob aus, dass seine eigene Gödelzahl die Gödelzahl einer unbeweisbaren Formel ist.

Die Aussage p [...] besagt, dass bei Durchführung einer bestimmten Rechnung die resultierende Gödel-Zahl die einer unbeweisbaren Aussage ist. Aber wenn diese Berechnung durchgeführt wird, stellt sich heraus, dass die resultierende Gödel-Zahl die Gödel-Zahl von p selbst ist.

Jetzt können wir alle Zutaten zusammenstellen.

Die Begründung in Gödels Beweis lautet nun wie folgt. Erstens, wenn p tatsächlich ein Satz von S ist, dann ist es in S beweisbar, dass p ein Satz von S ist [das heißt: Bew(G(p)) , die Formel, die behauptet, dass es eine Zahl x gibt, die die ist Gödelzahl eines Beweises in S der durch G(p) codierten Formel ].

Der Grund dafür ist, dass "ein Theorem von S zu sein" eine Eigenschaft ist, die verifiziert werden kann, indem ein Beweis in S gezeigt wird, und da es erforderlich ist, dass ein Beweis in S eine berechenbare Eigenschaft von Satzfolgen ist, kann die Verifikation sein innerhalb von S selbst durchgeführt [nochmals: S enthält eine "gewisse Menge" an Arithmetik ...].

Wenn also S p beweist , dh wenn p ein Satz von S ist, dann beweist S auch ~Bew(G(p)) , durch die obige Äquivalenz [denken Sie daran, dass p ein beweisbarer Fixpunkt der Eigenschaft ist, kein Satz von zu sein S ]; aber es beweist auch Bew(G(p)) , durch das vorherige Argument. Wir haben also einen Widerspruch.

Betrachten Sie nun den Fall, dass S ~p beweist ; durch "Konstruktion" von p beweist es einen Satz, der "sagt, dass" p unbeweisbar ist . Jetzt haben wir zwei Möglichkeiten.

(i) der Beweis von p existiert: in diesem Fall ist S eindeutig inkonsistent ;

Andernfalls :

(ii) der Beweis von p existiert nicht : in diesem Fall beweist S einen falschen Satz, weil es Bew(G(p)) beweist , die behaupten, dass der Beweis existiert. Also muss S ungesund sein .

Schlussfolgerung: Unter der Annahme, dass S "in der Lage" ist, eine "bestimmte Menge" an Arithmetik auszudrücken, kann das System S nicht sowohl solide als auch vollständig sein .

Aber wir bleiben bei unserer "natürlichen Einsicht" über die Solidität der Arithmetik. Daher muss ein System, das Arithmetik "enthält", unvollständig sein .

Nachdem bewiesen wurde, dass Gödels Satz p in S unbeweisbar ist , zeigt Gödels Beweis, dass p wahr ist , da p als Behauptung seiner eigenen Unbeweisbarkeit "gelesen" werden kann . Somit gibt uns Gödels Beweis nicht nur die Existenz eines unporvierbaren Satzes, sondern auch eine Methode zur "Herstellung" an die Hand:

ein in S ausdrückbarer wahrer Satz, der in S nicht beweisbar ist .

Siehe Torkel Franzén, Gödels Theorem Ein unvollständiger Leitfaden für seine Verwendung und seinen Missbrauch (2005).

Wenn Sie verstehen, wie formale Systeme in Logik und Mathematik funktionieren, dann lassen sich Gödels Theoreme am besten darstellen, indem Sie einen Umweg über eine Modallogik namens Beweisbarkeitslogik machen.

Es gibt eine (Standard-) Modallogik namens K nach Kripke, die (standardmäßig) die Notwendigkeit modelliert und deren Axiome sind

1. Wenn T |- p dann T |- Np

2. Gegeben T |- N(p -> q) dann T |- Np -> Nq

3. Für alle p gilt T |-Np ->NNp

Das erste Axiom sagt, wenn p der Fall ist, dann ist p notwendigerweise der Fall; dann sagt zweitens, wenn es notwendigerweise der Fall ist, dass p zwangsläufig q impliziert , dann ist es notwendigerweise der Fall, dass p notwendigerweise q impliziert .

Man beachte auch, dass wenn p notwendigerweise der Fall ist, dann p notwendigerweise notwendigerweise der Fall ist, oder in Symbolen ist es das dritte Axiom.

Wir fügen ein neues Axiom hinzu, dessen Motivation von der Beweisbarkeit herrührt, genannt Lobs-Axiom, und das besagt

Lob: Für jedes p haben wir das N(Np ->p) -> Np

In dieser Modallogik können wir zeigen, dass sie einen Fixpunktsatz erfüllt, der besagt, wenn ein Prädikat A(p) gegeben ist, das von einer Aussagenvariable p abhängt , dann gibt es eine Formel q , in der p nicht vorkommt, und

Thm: |- q <-> A(q)

Nun stellt sich heraus, dass das Beweisbarkeitsprädikat P in der Arithmetik die oben ausgearbeiteten Axiome der Modallogik erfüllt, ebenso wie dieser Fixpunktsatz.

Wenn man schließlich A(p):= nicht Pp setzt, also p nicht beweisbar ist, dann ist sein Fixpunkt nicht P(_|_) , das heißt, es beweist keinen Widerspruch, und wir haben vom Fixpunkt Satz, der Satz:

|- nicht P(_|_) <-> nicht P(nicht P(_|_))

Wenn wir dies lesen (von links nach rechts), heißt es: Wenn wir keine Inkonsistenz ableiten können, können wir nicht beweisen, dass wir eine Inkonsistenz ableiten können. Dies ist Gödels Unvollständigkeitssatz, der besagt, dass eine konsistente Theorie einen Satz hat, der wahr, aber nicht beweisbar ist – und wir haben gezeigt, dass diese Aussage darin besteht, dass Widersprüche nicht beweisbar sind.

All dies steht im SEP-Artikel zur Beweisbarkeitslogik

Ein System kann sich nur dann als wahr erweisen, wenn dieses System widersprüchlich ist. In diesen Fällen kann das System alles beweisen , sogar seine eigene Wahrheit und Konsistenz. Wenn also G beweisbar ist, ist es beweisbar, weil G widersprüchlich ist.

G: "G kann nicht innerhalb der Theorie T bewiesen werden"

„Wenn G beweisbar ist, dann widerspricht G sich selbst“

Nehmen wir also an, jemand geht weiter und schafft es zu beweisen, dass G innerhalb der T-Theorie wahr ist.

Aber da G das Gegenteil aussagt, dh dass es innerhalb der T-Theorie nicht bewiesen werden kann, ist es, wenn es sich als wahr erweist, bewiesen ... falsch. Es ist also widersprüchlich, da es gleichzeitig wahr und falsch ist.

Es ist eine Variante des Epimenides-Paradhoxes ("Alles, was ich sage, ist eine Lüge ...", was nur wahr ist, wenn es nicht wahr ist).

Gödel gelang es, einen Satz G zu konstruieren, der ausdrückt "es gibt keinen Beweis für den Satz G". Sehen Sie sich nun den Satz an, der Ihnen ein Problem bereitet: "Wenn G beweisbar ist, dann widerspricht sich G".

G macht eine Aussage. Wenn das Gegenteil der Aussage, die G macht, wahr ist, dann ist G eindeutig falsch. Wie lautet die Aussage von G? "Es gibt keinen Beweis für den Satz G". Was ist das Gegenteil dieser Aussage? "Es gibt einen Beweis für den Satz G". Weiter oben haben wir gesehen „Wenn das Gegenteil der Aussage, die G macht, wahr ist, dann ist G falsch“. Also "wenn es einen Beweis für den Satz G gibt, dann ist G falsch".