Vollständigkeitssatz von Gödel Gödel's completeness theorem

Die Formel ( ∀ x . R ( x , x )) → (∀ x ∃ y . R ( x , y )) gilt in allen Strukturen (nur die einfachsten 8 sind links gezeigt). Nach Gödels Vollständigkeitsergebnis muss es daher einen natürlichen Deduktionsbeweis haben (rechts gezeigt).

Der Vollständigkeitssatz von Gödel ist ein fundamentaler Satz der mathematischen Logik , der eine Entsprechung zwischen semantischer Wahrheit und syntaktischer Beweisbarkeit in der Logik erster Ordnung herstellt .

Der Vollständigkeitssatz gilt für jede Theorie erster Ordnung : Wenn T eine solche Theorie ist und φ ein Satz (in derselben Sprache) und jedes Modell von T ein Modell von φ ist, dann gibt es einen Beweis (erster Ordnung) für φ unter Verwendung der Aussagen von T als Axiome. Manchmal sagt man dies als "alles Wahre ist beweisbar".

Sie stellt eine enge Verbindung zwischen der Modelltheorie her , die sich damit beschäftigt, was in verschiedenen Modellen wahr ist, und der Beweistheorie, die untersucht , was in bestimmten formalen Systemen formal bewiesen werden kann .

Es wurde erstmals 1929 von Kurt Gödel bewiesen . Es wurde dann 1947 vereinfacht, als Leon Henkin in seiner Ph.D. These, dass der schwierige Teil des Beweises als Modellexistenzsatz (veröffentlicht 1949) präsentiert werden kann. Henkins Beweis wurde 1953 von Gisbert Hasenjaeger vereinfacht .

Vorrunde

Es gibt zahlreiche deduktive Systeme für die Logik erster Ordnung, einschließlich Systeme der natürlichen Deduktion und Systeme des Hilbert-Stils . Allen deduktiven Systemen ist die Vorstellung einer formalen Deduktion gemeinsam . Dies ist eine Folge (oder in einigen Fällen ein endlicher Baum ) von Formeln mit einer speziell bezeichneten Konklusion . Die Definition einer Deduktion ist so, dass sie endlich ist und algorithmisch ( z. B. durch einen Computer oder von Hand) überprüft werden kann , dass eine gegebene Folge (oder ein Baum) von Formeln tatsächlich eine Deduktion ist.

Eine Formel erster Ordnung heißt logisch gültig, wenn sie in jeder Struktur für die Sprache der Formel (dh für jede Zuweisung von Werten an die Variablen der Formel) gilt. Um den Vollständigkeitssatz formal aufzustellen und dann zu beweisen, ist es notwendig, auch ein deduktives System zu definieren. Ein deduktives System heißt vollständig, wenn jede logisch gültige Formel die Konklusion einer formalen Deduktion ist, und der Vollständigkeitssatz für ein bestimmtes deduktives System ist der Satz, dass es in diesem Sinne vollständig ist. Es gibt also gewissermaßen für jedes deduktive System einen anderen Vollständigkeitssatz. Eine Umkehrung der Vollständigkeit ist die Solidität , die Tatsache, dass im deduktiven System nur logisch gültige Formeln beweisbar sind.

Wenn ein bestimmtes deduktives System der Logik erster Ordnung solide und vollständig ist, dann ist es "perfekt" (eine Formel ist genau dann beweisbar, wenn sie logisch gültig ist), also äquivalent zu jedem anderen deduktiven System mit der gleichen Qualität (jeder Beweis in einem System in das andere umgewandelt werden können).

Stellungnahme

Wir legen zunächst ein deduktives System der Prädikatenkalkül erster Ordnung fest und wählen eines der bekannten äquivalenten Systeme. Gödels Originalbeweis ging vom Hilbert-Ackermann-Beweissystem aus.

Gödels Originalformulierung

Der Vollständigkeitssatz besagt, dass, wenn eine Formel logisch gültig ist, es eine endliche Deduktion (einen formalen Beweis) der Formel gibt.

Somit ist das deduktive System "vollständig" in dem Sinne, dass keine zusätzlichen Inferenzregeln erforderlich sind, um alle logisch gültigen Formeln zu beweisen. Eine Umkehrung der Vollständigkeit ist die Solidität , die Tatsache, dass im deduktiven System nur logisch gültige Formeln beweisbar sind. Zusammen mit der Solidität (deren Verifikation einfach ist) impliziert dieser Satz, dass eine Formel genau dann logisch gültig ist, wenn sie die Schlussfolgerung einer formalen Deduktion ist.

Allgemeinere Form

Das Theorem kann allgemeiner als logische Konsequenz ausgedrückt werden . Wir sagen, dass ein Satz s eine syntaktische Folge einer Theorie T ist , bezeichnet mit , wenn s in unserem deduktiven System aus T beweisbar ist. Wir sagen, dass s eine semantische Folge von T ist , bezeichnet mit , falls s in jedem Modell von T gilt . Der Vollständigkeitssatz sagt dann , dass für jede erste Ordnung Theorie T mit einer gut bestellbaren Sprache, und jeder Satz s in der Sprache von T , ${\displaystyle T\vdash s}$${\displaystyle T\models s}$

wenn , dann .${\displaystyle T\models s}$${\displaystyle T\vdash s}$

Da auch die Umkehrung (Gültigkeit) gilt, folgt daraus, dass genau dann , wenn , und damit diese syntaktische und semantische Konsequenz für die Logik erster Ordnung äquivalent sind. ${\displaystyle T\models s}$ ${\displaystyle T\vdash s}$

Dieser allgemeinere Satz wird implizit verwendet, wenn beispielsweise gezeigt wird, dass ein Satz aus den Axiomen der Gruppentheorie beweisbar ist, indem eine beliebige Gruppe betrachtet und gezeigt wird, dass der Satz von dieser Gruppe erfüllt ist.

Gödels ursprüngliche Formulierung wird abgeleitet, indem man den speziellen Fall einer Theorie ohne Axiom nimmt.

Modellexistenztheorem

Der Vollständigkeitssatz kann auch in Bezug auf verstanden werden , Konsistenz , als Folge der Henkin des Modellexistenzsatz . Wir sagen , dass eine Theorie T ist syntaktisch konsistent , wenn kein Satz ist s , so dass beide s und seine Negation ¬ s von beweisbar sind T in unserem deduktiven System. Der Modellexistenzsatz besagt, dass für jede Theorie erster Ordnung T mit einer wohlordenbaren Sprache

wenn syntaktisch konsistent ist, dann hat ein Modell.${\displaystyle T}$${\displaystyle T}$

Eine andere Version mit Verbindungen zum Löwenheim-Skolem-Theorem sagt:

Jede syntaktisch konsistente, abzählbare Theorie erster Ordnung hat ein endliches oder abzählbares Modell.

Mit dem Satz von Henkin kann der Vollständigkeitssatz wie folgt bewiesen werden: Wenn , dann hat keine Modelle. Nach dem Kontrapositiv des Satzes von Henkin ist dann syntaktisch inkonsistent. Ein Widerspruch ( ) ist also im deduktiven System beweisbar . Daher , und dann durch die Eigenschaften des deduktiven Systems, . ${\displaystyle T\models s}$${\displaystyle T\cup\lnot s}$${\displaystyle T\cup\lnot s}$${\displaystyle \bot}$${\displaystyle T\cup\lnot s}$${\displaystyle (T\cup \lnot s)\vdash \bot }$${\displaystyle T\vdash s}$

Als Satz der Arithmetik

Der Modellexistenzsatz und sein Beweis können im Rahmen der Peano-Arithmetik formalisiert werden . Genauer gesagt können wir ein Modell jeder konsistenten effektiven Theorie erster Ordnung T in der Peano-Arithmetik systematisch definieren, indem wir jedes Symbol von T durch eine arithmetische Formel interpretieren, deren freie Variablen die Argumente des Symbols sind. (In vielen Fällen müssen wir als Hypothese der Konstruktion annehmen, dass T konsistent ist, da die Peano-Arithmetik diese Tatsache nicht beweisen kann.) Die durch diese Formel ausgedrückte Definition ist jedoch nicht rekursiv (allerdings ist sie im Allgemeinen , Δ ₂ ).

Folgen

Eine wichtige Konsequenz des Vollständigkeitssatzes ist, dass es möglich ist, die semantischen Konsequenzen jeder effektiven Theorie erster Ordnung rekursiv aufzuzählen , indem man alle möglichen formalen Ableitungen aus den Axiomen der Theorie aufzählt, und daraus eine Aufzählung ihrer Schlussfolgerungen zu erstellen .

Dies steht im Gegensatz zur direkten Bedeutung des Begriffs der semantischen Konsequenz, der alle Strukturen in einer bestimmten Sprache quantifiziert, was eindeutig keine rekursive Definition ist.

Außerdem macht es den Begriff der "Beweisbarkeit" und damit des "Theorems" zu einem klaren Konzept, das nur von dem gewählten Axiomensystem der Theorie abhängt und nicht von der Wahl eines Beweissystems.

Beziehung zu den Unvollständigkeitssätzen

Die Unvollständigkeitssätze von Gödel zeigen, dass es inhärente Beschränkungen für das gibt, was innerhalb einer gegebenen Theorie erster Ordnung in der Mathematik bewiesen werden kann. Die "Unvollständigkeit" in ihrem Namen bezieht sich auf eine andere Bedeutung von vollständig (siehe Modelltheorie – Verwendung der Kompaktheits- und Vollständigkeitssätze ): Eine Theorie ist vollständig (oder entscheidbar), wenn jeder Satz in der Sprache von entweder beweisbar ( ) oder widerlegbar ( ) ist. . ${\displaystyle T}$${\displaystyle S}$${\displaystyle T}$${\displaystyle T\vdash S}$${\displaystyle T\vdash \neg S}$

Das erste Unvollständigkeitstheorem besagt, dass alles, was konsistent und effektiv ist und Robinson-Arithmetik (" Q ") enthält, in diesem Sinne unvollständig sein muss, indem explizit ein Satz konstruiert wird, der nachweislich weder beweisbar noch widerlegbar ist . Das zweite Unvollständigkeitstheorem erweitert dieses Ergebnis, indem es zeigt, dass es so gewählt werden kann, dass es die Konsistenz seiner selbst ausdrückt . ${\displaystyle T}$${\displaystyle S_{T}}$${\displaystyle T}$${\displaystyle S_{T}}$${\displaystyle T}$

Da in nicht widerlegt werden kann , impliziert der Vollständigkeitssatz die Existenz eines Modells von in dem falsch ist. Tatsächlich ist ein Satz Π ₁ , dh er besagt, dass eine finitistische Eigenschaft für alle natürlichen Zahlen gilt; Wenn es also falsch ist, dann ist eine natürliche Zahl ein Gegenbeispiel. Wenn dieses Gegenbeispiel innerhalb der natürlichen Standardzahlen existierte, würde seine Existenz darin widerlegt werden ; aber der Unvollständigkeitssatz hat gezeigt, dass dies unmöglich ist, daher darf das Gegenbeispiel keine Standardzahl sein, und daher muss jedes Modell, in dem falsch ist, Nichtstandardzahlen enthalten . ${\displaystyle S_{T}}$${\displaystyle T}$${\displaystyle T}$${\displaystyle S_{T}}$${\displaystyle S_{T}}$${\displaystyle S_{T}}$${\displaystyle T}$${\displaystyle T}$${\displaystyle S_{T}}$

Tatsächlich ist das Modell jeder Theorie, die Q enthält, erhalten durch die systematische Konstruktion des Existenzsatzes des arithmetischen Modells, immer kein Standard mit einem nicht-äquivalenten Beweisbarkeitsprädikat und einer nicht-äquivalenten Art, seine eigene Konstruktion zu interpretieren, so dass diese Konstruktion ist nicht rekursiv (da rekursive Definitionen eindeutig wären).

Auch wenn if zumindest geringfügig stärker als Q ist (zB wenn es Induktion für beschränkte Existenzformeln enthält), dann zeigt der Satz von Tennenbaum , dass es keine rekursiven Nicht-Standard-Modelle gibt. ${\displaystyle T}$

Beziehung zum Kompaktheitssatz

Der Vollständigkeitssatz und der Kompaktheitssatz sind zwei Eckpfeiler der Logik erster Ordnung. Während keiner dieser Sätze vollständig effektiv bewiesen werden kann, kann jeder effektiv aus dem anderen gewonnen werden.

Der Kompaktheitssatz besagt, dass, wenn eine Formel φ eine logische Konsequenz einer (möglicherweise unendlichen) Menge von Formeln Γ ist, sie eine logische Konsequenz einer endlichen Teilmenge von ist. Dies ist eine unmittelbare Konsequenz des Vollständigkeitssatzes, da in einer formalen Ableitung von φ nur eine endliche Anzahl von Axiomen aus erwähnt werden kann und die Korrektheit des deduktiven Systems dann impliziert, dass φ eine logische Konsequenz dieser endlichen Menge ist. Dieser Beweis des Kompaktheitssatzes geht ursprünglich auf Gödel zurück.

Umgekehrt ist es für viele deduktive Systeme möglich, den Vollständigkeitssatz als effektive Konsequenz des Kompaktheitssatzes zu beweisen.

Die Ineffektivität des Vollständigkeitssatzes kann nach dem Vorbild der umgekehrten Mathematik gemessen werden . Bei Betrachtung über eine abzählbare Sprache sind die Vollständigkeits- und Kompaktheitssätze äquivalent zueinander und äquivalent zu einer schwachen Form der Wahl, die als schwaches Königs-Lemma bekannt ist , wobei die Äquivalenz in RCA ₀ beweisbar ist (eine auf Induktion beschränkte Variante der Peano-Arithmetik zweiter Ordnung über Σ ⁰ ₁ Formeln). Das schwache Königs-Lemma ist in ZF, dem System der Zermelo-Fraenkel-Mengentheorie ohne Wahlaxiom, beweisbar, und damit sind die Vollständigkeits- und Kompaktheitssätze für abzählbare Sprachen in ZF beweisbar. Allerdings ist die Situation anders , wenn die Sprache beliebig große Mächtigkeit ist seitdem, obwohl die Vollständigkeit und Kompaktheit Theoreme beweisbar äquivalent bleiben miteinander in ZF, sie sind auch beweisbar äquivalent zu einer schwachen Form des Axiom der Wahl bekannt als die Ultrafiltrations Lemma . Insbesondere kann keine Theorie, die ZF erweitert, weder den Vollständigkeits- noch den Kompaktheitssatz über beliebige (möglicherweise überzählige) Sprachen beweisen, ohne auch das Ultrafilter-Lemma auf einer Menge derselben Kardinalität zu beweisen.

Vollständigkeit in anderen Logiken

Der Vollständigkeitssatz ist eine zentrale Eigenschaft der Logik erster Ordnung , die nicht für alle Logiken gilt. Die Logik zweiter Ordnung zum Beispiel hat keinen Vollständigkeitssatz für ihre Standardsemantik (aber hat die Vollständigkeitseigenschaft für die Henkin-Semantik ), und die Menge logisch gültiger Formeln in der Logik zweiter Ordnung ist nicht rekursiv aufzählbar. Das gleiche gilt für alle Logiken höherer Ordnung. Es ist möglich, solide deduktive Systeme für Logiken höherer Ordnung zu erzeugen, aber kein solches System kann vollständig sein.

Der Satz von Lindström besagt, dass die Logik erster Ordnung die stärkste Logik ist (unter gewissen Einschränkungen), die sowohl Kompaktheit als auch Vollständigkeit erfüllt.

Ein Vollständigkeitssatz kann für die Modallogik oder die Intuitionistische Logik in Bezug auf die Kripke-Semantik bewiesen werden .

Beweise

Gödels ursprünglicher Beweis des Satzes ging davon aus, das Problem auf einen Spezialfall für Formeln in einer bestimmten syntaktischen Form zu reduzieren und diese Form dann mit einem Ad-hoc- Argument zu behandeln.

In modernen Logiktexten wird Gödels Vollständigkeitssatz normalerweise mit Henkins Beweis bewiesen , anstatt mit Gödels ursprünglichem Beweis. Der Beweis von Henkin konstruiert direkt ein Termmodell für jede konsistente Theorie erster Ordnung. James Margetson (2004) entwickelte einen computerisierten formalen Beweis unter Verwendung des Isabelle- Theorembeweisers. Auch andere Beweise sind bekannt.

Siehe auch

• Unvollständigkeitssätze von Gödel
• Originalbeweis des Gödelschen Vollständigkeitssatzes

Weiterlesen

• Gödel, K (1929). "Über die Vollständigkeit des Logikkalküls" . Doktorarbeit. Universität Wien. Cite Journal erfordert |journal=( Hilfe ) Der erste Beweis des Vollständigkeitssatzes.
• Gödel, K (1930). „Die Vollständigkeit der Axiome des logischen Funktionenkalküls“. Monatshefte für Mathematik . 37 (1): 349–360. doi : 10.1007/BF01696781 . JFM  56.0046.04 . S2CID  123343522 . Dasselbe Material wie die Dissertation, nur mit kürzeren Beweisen, prägnanteren Erläuterungen und dem Weglassen der langen Einleitung.

Externe Links

• Stanford Encyclopedia of Philosophy : „ Kurt Gödel “ – von Juliette Kennedy .
• MacTutor-Biografie: Kurt Gödel.
• Detlovs, Vilnis und Podnieks, Karlis, „ Einführung in die mathematische Logik “.