Der Beweis des Vollständigkeitslehrsatzes von Gödel, der von Kurt Gödel in seiner Doktorarbeit von 1929 (und eine umgeschriebene Version der Doktorarbeit gegeben ist, veröffentlicht als ein Artikel 1930) ist nicht leicht, heute zu lesen; es verwendet Konzepte und Formalismus, die überholt sind und Fachsprache, die häufig dunkel ist. Die unter Versuchen gegebene Version, alle Schritte im Beweis und alle wichtigen Ideen treu zu vertreten, während man den Beweis auf der modernen Sprache der mathematischen Logik neu formuliert. Dieser Umriss sollte als kein strenger Beweis des Lehrsatzes betrachtet werden.

Definitionen und Annahmen

Wir arbeiten mit der Prädikat-Rechnung der ersten Ordnung. Unsere Sprachen erlauben unveränderlich, Funktion und Beziehungssymbole. Strukturen bestehen aus (nichtleeren) Gebieten und Interpretationen der relevanten Symbole als unveränderliche Mitglieder, Funktionen oder Beziehungen über dieses Gebiet.

Wir befestigen einen axiomatization der Prädikat-Rechnung: logische Axiome und Regeln der Schlussfolgerung. Einige der mehreren wohl bekannten axiomatisations wird tun; wir nehmen ohne Beweis alle grundlegenden wohl bekannten Ergebnisse über unseren Formalismus an (wie der normale Form-Lehrsatz oder der Stichhaltigkeitslehrsatz), dass wir brauchen.

Wir axiomatize Prädikat-Rechnung ohne Gleichheit, d. h. gibt es keine speziellen Axiome, die die Eigenschaften der Gleichheit als ein spezielles Beziehungssymbol ausdrücken. Nachdem die grundlegende Form des Lehrsatzes bewiesen wird, wird es leicht sein, es zum Fall der Prädikat-Rechnung mit der Gleichheit zu erweitern.

Behauptung des Lehrsatzes und seines Beweises

Im folgenden setzen wir zwei gleichwertige Formen des Lehrsatzes fest, und zeigen ihre Gleichwertigkeit.

Später beweisen wir den Lehrsatz. Das wird in den folgenden Schritten getan:

1. Das Reduzieren des Lehrsatzes zu Sätzen (Formeln ohne freie Variablen) in der Prenex-Form, d. h. mit dem ganzen quantifiers (und) am Anfang. Außerdem reduzieren wir es auf Formeln, deren erster quantifier ist. Das ist weil für jeden Satz möglich, es gibt ein gleichwertiges in der Prenex-Form, deren erster quantifier ist.
2. Das Reduzieren des Lehrsatzes zu Sätzen der Form. Während wir das nicht tun können, indem wir einfach den quantifiers umordnen, zeigen wir, dass es noch genug ist, den Lehrsatz für Sätze dieser Form zu beweisen.
3. Schließlich beweisen wir den Lehrsatz für Sätze dieser Form.
4. * wird Das durch die erste Anmerkung getan, dass ein Satz, der entweder widerlegbar ist oder ein Modell hat, in dem er hält; dieses Modell teilt einfach Wahrheitswerte den Subvorschlägen zu, von denen B gebaut wird. Der Grund dafür ist die Vollständigkeit der Satzlogik mit dem existenziellen quantifiers, der keine Rolle spielt.
5. * erweitern Wir dieses Ergebnis zu immer komplizierteren und langen Sätzen, D (n=1,2...), gebaut aus B, so dass entweder einige von ihnen widerlegbar ist und deshalb auch φ ist, oder sie alle nicht widerlegbar sind und deshalb jeder in einem Modell hält.
6. * verwenden Wir schließlich die Modelle, in denen die D halten (im Falle dass alle nicht widerlegbar sind), um ein Modell zu bauen, in dem φ hält.

Lehrsatz 1. Jede in allen Strukturen gültige Formel ist nachweisbar.

Das ist die grundlegendste Form des Vollständigkeitslehrsatzes. Wir formulieren es sofort in einer zu unseren Zwecken günstigeren Form neu:

Lehrsatz 2. Jede Formel φ ist entweder widerlegbar oder satisfiable in einer Struktur.

"φ ist widerlegbar" bedeutet definitionsgemäß "¬φ ist nachweisbar".

Gleichwertigkeit von beiden Lehrsätzen

Um die Gleichwertigkeit zu sehen, bemerken Sie zuerst, dass, wenn Lehrsatz 1 hält, und φ nicht satisfiable in jeder Struktur ist, dann ist ¬ φ in allen Strukturen gültig und deshalb nachweisbar, so ist φ widerlegbar, und Lehrsatz 2 hält. Wenn andererseits Lehrsatz 2 hält und φ in allen Strukturen gültig ist, dann ist ¬ φ nicht satisfiable in jeder Struktur und deshalb widerlegbar; dann ist ¬¬φ nachweisbar, und ist dann auch φ, so hält Lehrsatz 1.

Beweis des Lehrsatzes 2: der erste Schritt

Wir nähern uns dem Beweis des Lehrsatzes 2, indem wir die Klasse aller Formeln φ nacheinander einschränken, für den wir uns "&phi erweisen müssen; ist entweder widerlegbar oder satisfiable". Am Anfang müssen wir das für alle möglichen Formeln φ auf unserer Sprache beweisen. Nehmen Sie jedoch an, dass für jede Formel φ es eine Formel ψ genommen von einer mehr eingeschränkten Klasse von Formeln C, solch dass "&psi gibt; ist entweder widerlegbar oder satisfiable"  "φ ist entweder widerlegbar oder satisfiable". Dann, sobald dieser Anspruch (ausgedrückt im vorherigen Satz) bewiesen wird, wird es genügen, um sich "&phi zu erweisen; ist entweder widerlegbar oder satisfiable" nur für φ's, der der Klasse C gehört. Bemerken Sie auch dass, wenn φ zu ψ nachweisbar gleichwertig ist (d. h., (φ ψ) ist nachweisbar), dann ist es tatsächlich der Fall das "ψ ist entweder widerlegbar oder satisfiable"  "φ ist entweder widerlegbar oder satisfiable" (der Stichhaltigkeitslehrsatz ist erforderlich, um das zu zeigen).

Es gibt Standardtechniken, für eine willkürliche Formel in diejenige umzuschreiben, die Funktion oder unveränderliche Symbole, auf Kosten des Einführens von zusätzlichem quantifiers nicht verwendet; wir werden deshalb annehmen, dass alle Formeln frei von solchen Symbolen sind. In der Zeitung von Gödel verwendet er eine Version der Prädikat-Rechnung der ersten Ordnung, die keine Funktion oder unveränderliche Symbole zunächst hat.

Als nächstes denken wir eine allgemeine Formel φ (der nicht mehr Funktion oder unveränderliche Symbole verwendet) und wenden Sie den Prenex-Form-Lehrsatz an, um eine Formel ψ in der normalen Form solch zu finden, dass φ ψ (ψ, in der normalen Form seiend, bedeutet, dass der ganze quantifiers in ψ, wenn es irgendwelchen gibt, am wirklichen Anfang von ψ gefunden werden). Es folgt, jetzt wo wir nur Lehrsatz 2 für Formeln φ in der normalen Form beweisen müssen.

Dann beseitigen wir alle freien Variablen von φ, indem wir sie existenziell messen: wenn, sagen wir, x... x sind in φ frei, wir formen uns. Wenn ψ satisfiable in einer Struktur M ist, dann sicher auch ist φ, und wenn ψ widerlegbar ist, dann nachweisbar ist, und dann auch ¬ φ ist, so ist φ widerlegbar. Wir sehen, dass wir φ einschränken können, um ein Satz, d. h. eine Formel ohne freie Variablen zu sein.

Schließlich möchten wir aus Gründen der technischen Bequemlichkeit, dass das Präfix von φ (d. h. die Reihe von quantifiers am Anfang φ, der in der normalen Form ist) mit einem universalen quantifier beginnt und mit einem existenziellen quantifier endet. Um das für einen allgemeinen φ zu erreichen (unterwerfen Beschränkungen, die wir bereits bewiesen haben), nehmen wir Beziehungssymbol des jemandes-Platzes F unbenutzt in φ, und zwei neuen Variablen y und z.. Wenn φ = (P) Φ, wo (P) für das Präfix von φ und Φ für die Matrix eintritt (der restliche, quantifier-freie Teil von φ) wir uns formen. Seitdem ist klar nachweisbar, es ist leicht zu sehen, dass das nachweisbar ist.

Das Reduzieren des Lehrsatzes zu Formeln des Grads 1

Unsere allgemeine Formel φ ist jetzt ein Satz in der normalen Form, und sein Präfix fängt mit einem universalen quantifier an und endet mit einem existenziellen quantifier. Lassen Sie uns die Klasse aller dieser Formeln R nennen. Wir konfrontieren mit Beweis, dass jede Formel in R entweder widerlegbar ist oder satisfiable. In Anbetracht unserer Formel φ gruppieren wir Reihen von quantifiers einer Art zusammen in Blöcken:

:

Wir definieren den Grad, die Zahl von universalen Quantifier-Blöcken zu sein, die durch existenzielle Quantifier-Blöcke, wie gezeigt, oben, im Präfix dessen getrennt sind. Das folgende Lemma, das Gödel vom Beweis von Skolem des Löwenheim-Skolem Lehrsatzes angepasst hat, lässt uns scharf die Kompliziertheit der allgemeinen Formel reduzieren, für die wir den Lehrsatz beweisen müssen:

Lemma. Lassen Sie k> =1. Wenn jede Formel in R des Grads k entweder widerlegbar ist oder satisfiable, dann auch ist jede Formel in R des Grads k+1.

:Comment: Nehmen Sie eine Formel φ des Grads k+1 der Form, wo der Rest dessen ist (ist es so des Grads k-1). φ Staaten, dass für jeden x es einen solchen y dass... (etwas) gibt. Es wäre nett gewesen, ein Prädikat Q zu haben', so dass für jeden x, Q' (x, y) wahr sein würde, wenn, und nur wenn y der erforderliche ist (um etwas) wahr zu machen. Dann könnten wir eine Formel des Grads k geschrieben haben, der zu &phi gleichwertig ist; nämlich. Diese Formel ist tatsächlich zu &phi gleichwertig; weil es feststellt, dass für jeden x, wenn es einen y gibt, der Q' (x, y) dann befriedigt (etwas), und außerdem hält, wissen wir, dass es solch einen y, weil für jeden x gibt' gibt es einen y', der Q' (x', y') befriedigt. Deshalb φ folgt aus dieser Formel. Es ist auch leicht, dass zu zeigen, wenn die Formel falsch ist, dann so ist φ. leider im Allgemeinen gibt es kein solches Prädikat Q'. Jedoch kann diese Idee als eine Basis für den folgenden Beweis des Lemmas verstanden werden.

Beweis. Lassen Sie φ eine Formel des Grads k+1 sein; dann können wir es als schreiben

:

wo (P) der Rest des Präfixes ist (es ist so des Grads k-1), und ist die quantifier-freie Matrix dessen. x, y, u und v zeigen hier Tupel von Variablen aber nicht einzelnen Variablen an; z.B wirklich tritt ein, wo einige verschiedene Variablen sind.

Lassen Sie jetzt x' und y' Tupel vorher unbenutzter Variablen derselben Länge wie x und y beziehungsweise sein, und Q ein vorher unbenutztes Beziehungssymbol sein zu lassen, das so viele Argumente nimmt wie die Summe von Längen von x und y; wir denken die Formel

:

Klar, ist nachweisbar.

Jetzt, da die Reihe von quantifiers Variablen von x oder y nicht enthält, ist die folgende Gleichwertigkeit mit der Hilfe beliebigen Formalismus leicht nachweisbar, den wir verwenden:

:

Und da diese zwei Formeln gleichwertig sind, wenn wir das erste durch das zweite Innere Φ ersetzen, erhalten wir die Formel Φ' solch dass Φ Φ ':

:

Jetzt hat Φ' die Form, wo (S) und (S') einige Quantifier-Schnuren, ρ sind und ρ', und außerdem quantifier-frei sind, kommt keine Variable von (S) in ρ vor', und keine Variable von (S') kommt in ρ vor. Unter solchen Bedingungen wird jede Formel der Form, wo (T) eine Reihe von quantifiers ist, die den ganzen quantifiers in (S) und (S') durchgeschossen unter sich auf jede Mode enthalten, aber die Verhältnisordnung innen (S) und (S') aufrechterhaltend, zur ursprünglichen Formel Φ 'gleichwertig sein (das ist noch ein anderes grundlegendes Ergebnis in der Prädikat-Rechnung der ersten Ordnung, dass wir uns auf verlassen). Zum Witz bilden wir Ψ wie folgt:

:

und wir haben.

Jetzt ist eine Formel des Grads k und deshalb durch die Annahme entweder widerlegbar oder satisfiable.

Wenn satisfiable in einer Struktur M ist, dann, das Betrachten, sehen wir, dass das satisfiable ebenso ist.

Wenn widerlegbar ist, dann so ist, der dazu gleichwertig ist; so ist nachweisbar.

Jetzt können wir alle Ereignisse von Q innerhalb der nachweisbaren Formel durch einen anderen Formel-Abhängigen auf denselben Variablen ersetzen, und wir werden noch eine nachweisbare Formel bekommen.

(Das ist noch ein anderes grundlegendes Ergebnis der Prädikat-Rechnung der ersten Ordnung. Je nachdem der besondere Formalismus für die Rechnung angenommen hat, kann er als eine einfache Anwendung eines "funktionellen Ersatzes" Regel der Schlussfolgerung, als in der Zeitung von Gödel gesehen werden, oder es kann durch das Betrachten des formellen Beweises, das Ersetzen darin aller Ereignisse von Q durch eine andere Formel mit denselben freien Variablen und die Anmerkung bewiesen werden, dass alle logischen Axiome im formellen Beweis logische Axiome nach dem Ersatz bleiben, und alle Regeln der Schlussfolgerung noch ebenso gelten.)

In diesem besonderen Fall ersetzen wir Q (x', y') in mit der Formel. Hier (x, y|x', y') bedeutet, dass statt ψ wir eine verschiedene Formel schreiben, in der x und y durch x' und y ersetzt werden'. Bemerken Sie, dass Q (x, y) einfach dadurch ersetzt wird.

dann wird

:

und diese Formel ist nachweisbar; seit dem Teil unter der Ablehnung und nachdem ist das Zeichen, und der Teil unter der Ablehnung offensichtlich nachweisbar, und bevor das Zeichen offensichtlich φ, gerade mit x und y ist, der durch x' und y ersetzt ist', sehen wir, dass das nachweisbar ist, und φ widerlegbar ist. Wir haben bewiesen, dass φ entweder satisfiable oder widerlegbar ist, und das den Beweis des Lemmas schließt.

Bemerken Sie, dass wir statt Q (x', y') vom Anfang nicht verwendet haben könnten, weil keine gut gebildete Formel in diesem Fall gewesen wäre. Das ist, warum wir das Argument nicht naiv verwenden können, das an der Anmerkung erscheint, die dem Beweis vorangeht.

Der Beweis des Lehrsatzes für Formeln des Grads 1

Wie gezeigt, durch das Lemma oben müssen wir nur unseren Lehrsatz für Formeln φ in R des Grads 1 beweisen. φ kann nicht des Grads 0 sein, da Formeln in R keine freien Variablen haben und unveränderliche Symbole nicht verwenden. So die Formel hat φ die allgemeine Form:

:

Jetzt definieren wir eine Einrichtung der K-Tupel von natürlichen Zahlen wie folgt:

Setzen Sie die Formel als. Dann gestellt als

:

Lemma: Für jeden n, φ.

Beweis: Durch die Induktion auf n; wir haben, wo die letzte Implikation durch den variablen Ersatz hält, da die Einrichtung der Tupel dass solch

ist

Für den Grundfall, ist offensichtlich eine Folgeerscheinung von φ ebenso. So wird das Lemma bewiesen.

Jetzt, wenn für einen n widerlegbar ist, hieraus folgt dass φ widerlegbar ist. Nehmen Sie andererseits an, dass das für jeden n nicht widerlegbar ist. Dann für jeden n gibt es eine Weise, Wahrheitswerte den verschiedenen Subvorschlägen zuzuteilen (bestellt durch ihr erstes Äußeres darin; "verschieden" hier bedeutet entweder verschiedene Prädikate oder verschiedene bestimmte Variablen) in, solch, der wahr sein wird, wenn jeder Vorschlag auf diese Mode bewertet wird. Das folgt aus der Vollständigkeit der zu Grunde liegenden Satzlogik.

Wir werden jetzt zeigen, dass es solch eine Anweisung von Wahrheitswerten dazu gibt, so dass alle wahr sein werden: Das Erscheinen in derselben Ordnung in jedem; wir werden eine allgemeine Anweisung zu ihnen durch eine Art "Majoritätsstimme" induktiv definieren: Da es ungeheuer viele Anweisungen (ein für jeden) das Beeinflussen gibt, entweder ungeheuer machen viele wahr, oder ungeheuer machen viele es falsch, und nur begrenzt machen viele es wahr. Im ehemaligen Fall beschließen wir, im Allgemeinen wahr zu sein; in den Letzteren nehmen wir es, um im Allgemeinen falsch zu sein. Dann von den ungeheuer vielen n, für die durch derselbe Wahrheitswert wie in der allgemeinen Anweisung zugeteilt werden, picken wir eine allgemeine Anweisung zu auf dieselbe Mode auf.

Diese allgemeine Anweisung muss zu jedem führen und wahr seitdem zu sein, wenn einer, falsch unter der allgemeinen Anweisung zu sein, auch für jeden n> k falsch sein würde. Aber das widerspricht der Tatsache dass für die begrenzte Sammlung von allgemeinen Anweisungen, die darin erscheinen, es gibt ungeheuer viele n wo die Anweisung, die wahre Matchs die allgemeine Anweisung macht.

Jetzt von dieser allgemeinen Anweisung, die alle wahren macht, bauen wir eine Interpretation der Prädikate der Sprache, die φ wahr macht. Das Weltall des Modells wird die natürlichen Zahlen sein. Jedes i-ary Prädikat sollte auf den naturals genau zutreffen, wenn der Vorschlag in der allgemeinen Anweisung entweder wahr, oder dadurch nicht zugeteilt ist (weil es nie in einigen erscheint).

In diesem Modell ist jede der Formeln durch den Aufbau wahr. Aber das deutet an, dass φ selbst im Modell seit der Reihe über alle möglichen K-Tupel von natürlichen Zahlen wahr ist. So ist φ satisfiable, und wir getan werden.

Intuitive Erklärung

Wir können jeden B als Φ schreiben (x... x, y... y) für einen x-s, den wir "die ersten Argumente" und y-s nennen können, den wir "letzte Argumente" nennen können.

Nehmen Sie B zum Beispiel. Seine "letzten Argumente" sind z, z... z, und für jede mögliche Kombination von k dieser Variablen gibt es einen j, so dass sie als "die ersten Argumente" in B erscheinen. So für großen genug n hat D das Eigentum, dass die "letzten Argumente" von B, in jeder mögliche Kombinationen von k von ihnen, als "die ersten Argumente" in anderem B-s innerhalb von D erscheinen. Für jeden B gibt es einen D mit dem entsprechenden Eigentum.

Deshalb in einem Modell, das den ganzen D-s befriedigt, gibt es Gegenstände entsprechend z, z... und jede Kombination von k von diesen erscheinen als "die ersten Argumente" in einem B, dass für jeden k dieser Gegenstände z... z bedeutend, gibt es z... z, der Φ (z... z, z... z) zufrieden macht. Durch die Einnahme eines Submodells, das nur diese z, z enthält protestiert..., wir haben ein Modell, das φ befriedigt.

Erweiterungen

Erweiterung auf die Prädikat-Rechnung der ersten Ordnung mit der Gleichheit

Gödel hat eine Formel reduziert, die Beispiele des Gleichheitsprädikats zu ohne es auf einer verlängerten Sprache enthält. Seine Methode schließt das Ersetzen einer Formel φ ein, einige Beispiele der Gleichheit mit der Formel enthaltend

:

Hier zeigen Sie die Prädikate an, die in φ (mit ihrem jeweiligen arities) erscheinen, und φ' ist die Formel φ mit allen Ereignissen der Gleichheit, die durch das neue Prädikat Eq ersetzt ist. Wenn diese neue Formel widerlegbar ist, war der ursprüngliche φ ebenso; dasselbe trifft auf satisfiability zu, da wir einen Quotienten nehmen können, Modell der neuen Formel durch das Gleichwertigkeitsbeziehungsdarstellen Eq zu befriedigen. Dieser Quotient ist in Bezug auf die anderen Prädikate bestimmt, und wird deshalb die ursprüngliche Formel φ befriedigen.

Erweiterung auf zählbare Sätze von Formeln

Gödel hat auch den Fall in Betracht gezogen, wo es eine zählbar unendliche Sammlung von Formeln gibt. Mit denselben Verminderungen wie oben ist er im Stande gewesen, nur jene Fälle in Betracht zu ziehen, wo jede Formel des Grads 1 ist und keinen Gebrauch der Gleichheit enthält. Für eine zählbare Sammlung von Formeln des Grads 1 können wir als oben definieren; dann definieren Sie, um der Verschluss dessen zu sein. Der Rest des Beweises ist dann wie zuvor durchgegangen.

Erweiterung auf willkürliche Sätze von Formeln

Wenn es eine unzählbar unendliche Sammlung von Formeln gibt, ist das Axiom der Wahl (oder mindestens eine schwache Form davon) erforderlich. Mit dem vollen AC kann man die Formeln gut-bestellen, und den unzählbaren Fall mit demselben Argument wie das zählbare beweisen, außer mit der transfiniten Induktion. Andere Annäherungen können verwendet werden, um zu beweisen, dass der Vollständigkeitslehrsatz in diesem Fall zu Boolean idealer Hauptlehrsatz, eine schwache Form von AC gleichwertig ist.

• Der erste Beweis des Vollständigkeitslehrsatzes.

• Dasselbe Material wie die Doktorarbeit, außer mit kürzeren Beweisen, mehr kurz gefassten Erklärungen und dem Auslassen der langen Einführung.

Links

• Enzyklopädie von Stanford der Philosophie: "Kurt Gödel" - durch Juliette Kennedy.
• Lebensbeschreibung von MacTutor: Kurt Gödel.