Gödelscher Vollständigkeitssatz
Der Gödelsche Vollständigkeitssatz (benannt nach Kurt Gödel) ist der Hauptsatz der mathematischen Logik. Er zeigt für den Hilbert-Kalkül (ein formales System der Prädikatenlogik erster Stufe) die Korrektheit und Vollständigkeit: Jeder Satz, der semantisch aus einer Formelmenge folgt, lässt sich mit den Schlussregeln des Systems aus der Formelmenge herleiten, und umgekehrt. Für die Logik erster Stufe sind also syntaktische und semantische Folgerung gleichbedeutend.
Grundbegriffe
Formeln: Zunächst muss eine Menge von Konstanten-, Funktions- und Relationssymbolen festgelegt werden. Neben diesen Symbolen stehen dann aussagenlogische Junktoren, die Quantoren, das Gleichheitszeichen sowie Variablen zum Formelaufbau zur Verfügung.
Semantik:
Eine Struktur ist eine nichtleere Menge, in der die Konstanten-, Funktions- und
Relationssymbole durch Elemente, Funktionen und Relationen interpretiert werden.
Zu einer Interpretation gehört außerdem eine Belegung der Variablen mit Werten
aus der Struktur. Eine Formel ist allgemeingültig, wenn sie in jeder
Interpretation wahr ist. Eine Interpretation, die jede Formel aus einer
Formelmenge
wahr macht, nennt man ein Modell von
.
Eine Formel
ist eine semantische Folgerung aus
(in Zeichen
),
wenn
in jedem Modell von
wahr ist.
Herleitungen:
Ein Hilbert-Kalkül ist durch Axiome und Schlussregeln gegeben. Die wichtigste
Schlussregel ist dabei der modus
ponens: Von den Formeln
und
darf man zu
übergehen. Eine Formel
ist aus einer Formelmenge
herleitbar (in Zeichen
),
wenn es eine endliche, mit
endende Folge von Formeln gibt, wobei für jedes Glied der Folge gilt: es ist ein
Axiom oder ein Element von
oder es wird mit einer Schlussregel aus früheren Gliedern der Folge gebildet.
Der Satz
Kurt Gödel bewies 1929 den Vollständigkeitssatz im Wesentlichen in der folgenden Form:
- Es gibt einen Kalkül
der Prädikatenlogik
erster Stufe derart, dass für jede Formelmenge
und für jede Formel
gilt:
folgt genau dann aus
, wenn
im Kalkül aus
hergeleitet werden kann.
Verwendet man
als Zeichen für die semantische Folgerung und
für die Herleitbarkeit im Kalkül, ergibt sich die kurze Formulierung:
Der Schluss von rechts nach links bedeutet die Korrektheit des Kalküls: Alles, was sich mit dem Kalkül aus vorgegebenen Annahmen herleiten lässt, folgt auch wirklich logisch aus diesen Annahmen. Jeder sinnvolle Logikkalkül muss diese Forderung erfüllen.
Der Schluss von links nach rechts ist die eigentliche Vollständigkeit: Es wird behauptet, dass zu jedem Satz, der aus einer Menge von vorgegebenen Annahmen logisch folgt, tatsächlich ein Beweis aus diesen Annahmen im Kalkül existiert.
Eine abgeschwächte Fassung des Vollständigkeitssatzes wird oft so formuliert:
- Es gibt einen Kalkül der Prädikatenlogik erster Stufe derart, dass für
jede Formel
gilt:
ist genau dann allgemeingültig, wenn
im Kalkül bewiesen werden kann.
In Zeichen lautet diese Fassung kurz:
Sie ist ein Spezialfall der obigen Aussage, wobei die Formelmenge
leer ist.
Es ist wichtig, sich zu vergegenwärtigen, dass Vollständigkeit eine
Eigenschaft eines Kalküls ist. Das Symbol
für die Herleitbarkeit ist also eigentlich eine Abkürzung für
,
wobei
den Kalkül bezeichnet. Zum Beweis des Satzes muss ein konkreter Kalkül angegeben
werden. Gödel hat dies mit einem Hilbert-Kalkül, bestehend aus Axiomen und
Schlussregeln, getan. Ebenfalls vollständig ist zum Beispiel der von Gerhard Gentzen
eingeführte Sequenzenkalkül.
Beweisidee
Gödel bewies den Satz ursprünglich, indem er das Problem auf die Vollständigkeit für eine eingeschränkte Klasse von Formeln reduzierte, für die die Vollständigkeit dann auf die Vollständigkeit der Aussagenlogik zurückgeführt werden kann. Heute wird meist ein von Leon Henkin 1949 veröffentlichter Beweis benutzt. Dazu wird zunächst folgender Satz bewiesen:
- Jede konsistente Formelmenge hat ein Modell.
Konsistenz
ist dabei ein syntaktischer Begriff und bedeutet für eine Formelmenge ,
dass aus ihr kein Widerspruch im Kalkül hergeleitet werden kann (formal: Es gibt
keine Formel
mit
und
).
Die Existenz des Modells wird bewiesen, indem mithilfe des Satzes von
Lindenbaum eine gegebene konsistente Formelmenge
zu einer sogenannten maximalkonsistenten Menge erweitert wird, die keine
konsistente echte Obermenge hat. Dann wird die Sprache durch sogenannte
Henkinkonstanten erweitert und die Formelmenge so erweitert, dass für
jede Formel der Form
auch
(c eine Henkinkonstante) enthalten ist. Dann gibt es nach dem Satz von Henkin eine Terminterpretation,
deren Grundmenge aus den Termen der Sprache besteht und die alle Elemente der
entstehenden Formelmenge erfüllt, und damit auch die ursprüngliche konsistente
Formelmenge
.
Dann lässt sich die Vollständigkeit leicht zeigen: Angenommen, es gilt zwar
,
aber nicht
.
Der Kalkül hat die Eigenschaft, dass man die Negation einer aus einer
konsistenten Formelmenge nicht herleitbaren Formel zu der Formelmenge
hinzunehmen kann, und die Konsistenz dabei erhalten bleibt. Im vorliegenden Fall
ist also
konsistent und hat nach dem Satz von Henkin ein Modell. In diesem Modell ist
aber nun
falsch, im Widerspruch zur Voraussetzung, dass
in allen Modellen von
wahr ist.
Bedeutung
Dass sich das inhaltliche logische Folgern durch Ableitungen in einem rekursiven Kalkül vollständig abbilden lässt, ist eine herausragende Eigenschaft der Prädikatenlogik erster Stufe. Diese Vollständigkeit gilt für viele andere Logiken nicht, zum Beispiel nicht für die Prädikatenlogik höherer Stufe.
Der Kompaktheitssatz, ein zentraler Satz der Modelltheorie, ergibt sich als Korollar aus dem Vollständigkeitssatz.
Im Rahmen des Hilbertprogramms (zur Schaffung eines widerspruchsfreien und vollständigen Kalküls für die Mathematik) schien der Satz zunächst ein Schritt zum Ziel zu sein. Das Programm scheiterte allerdings, weil Gödel mit seinem Unvollständigkeitssatz zeigen konnte, dass eine genügend ausdrucksstarke Theorie nicht jeden wahren Satz beweisen kann. (Man beachte, dass sich der Unvollständigkeitssatz auf eine andere Art von Vollständigkeit bezieht als der hier vorgestellte Vollständigkeitssatz.)
Stellung in der Mengenlehre
Für abzählbare (oder allgemeiner: wohlgeordnete) Mengen von Symbolen lässt sich der Vollständigkeitssatz aus den Axiomen der Zermelo-Fraenkel-Mengenlehre ohne Auswahlaxiom beweisen. Der Beweis für beliebige Symbolmengen lässt sich mit dem Auswahlaxiom führen, der Satz ist allerdings nicht äquivalent zum Auswahlaxiom, sondern (relativ zu den Axiomen der Mengenlehre ohne Auswahlaxiom) u.a. zu:
- Ultrafilterlemma
- Kompaktheitssatz
- Satz von Lindenbaum
- Darstellungssatz für Boolesche Algebren
Literatur
- Hans Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, Heidelberg 2007, ISBN 3-8274-1691-4.
- K Gödel: Über die Vollständigkeit des Logikkalküls. In: University Of Vienna. (Hrsg.): Dissertation. 1929.



© biancahoegel.de
Datum der letzten Änderung: Jena, den: 19.06. 2021