Gödelscher Vollständigkeitssatz

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 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.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Gödelscher Vollständigkeitssatz aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung