Gödelscher Vollständigkeitssatz

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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 \Gamma\ wahr macht, nennt man ein Modell von \Gamma\ . Eine Formel \varphi ist eine semantische Folgerung aus \Gamma\ (in Zeichen \Gamma \vDash \varphi), wenn \varphi in jedem Modell von \Gamma\ wahr ist.

Herleitungen: Ein Hilbert-Kalkül ist durch Axiome und Schlussregeln gegeben. Die wichtigste Schlussregel ist dabei der modus ponens: Von den Formeln \varphi und \varphi \rightarrow \psi darf man zu \psi\ übergehen. Eine Formel \varphi ist aus einer Formelmenge \Gamma\ herleitbar (in Zeichen \Gamma \vdash \varphi), wenn es eine endliche, mit \varphi endende Folge von Formeln gibt, wobei für jedes Glied der Folge gilt: es ist ein Axiom oder ein Element von \Gamma\ oder es wird mit einer Schlussregel aus früheren Gliedern der Folge gebildet.

Der Satz[Bearbeiten]

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 \Gamma und für jede Formel \varphi gilt:
\varphi folgt genau dann aus \Gamma, wenn \varphi im Kalkül aus \Gamma hergeleitet werden kann.

Verwendet man \vDash als Zeichen für die semantische Folgerung und \vdash für die Herleitbarkeit im Kalkül, ergibt sich die kurze Formulierung:

\Gamma \vDash \varphi \Longleftrightarrow \Gamma \vdash \varphi

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 \varphi gilt:
\varphi ist genau dann allgemeingültig, wenn \varphi im Kalkül bewiesen werden kann.

In Zeichen lautet diese Fassung kurz:

 \vDash \varphi \Longleftrightarrow \ \vdash \varphi

Sie ist ein Spezialfall der obigen Aussage, wobei die Formelmenge \Gamma leer ist.

Es ist wichtig, sich zu vergegenwärtigen, dass Vollständigkeit eine Eigenschaft eines Kalküls ist. Das Symbol \vdash für die Herleitbarkeit ist also eigentlich eine Abkürzung für \vdash_{K}, wobei  K 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[Bearbeiten]

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 \Gamma\ , dass aus ihr kein Widerspruch im Kalkül hergeleitet werden kann (formal: Es gibt keine Formel \varphi mit \Gamma \vdash \varphi und \Gamma \vdash \neg \varphi).

Die Existenz des Modells wird bewiesen, indem mithilfe des Satzes von Lindenbaum eine gegebene konsistente Formelmenge \Gamma\ 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 \exists x \varphi(x) auch \varphi(c) (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 \Gamma\ .

Dann lässt sich die Vollständigkeit leicht zeigen: Angenommen, es gilt zwar \Gamma \vDash \varphi, aber nicht \Gamma \vdash \varphi. 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 \Gamma \cup \{\neg \varphi\} konsistent und hat nach dem Satz von Henkin ein Modell. In diesem Modell ist aber nun \varphi falsch, im Widerspruch zur Voraussetzung, dass \varphi in allen Modellen von \Gamma\ wahr ist.

Bedeutung[Bearbeiten]

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[Bearbeiten]

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:

Literatur[Bearbeiten]