Gödelscher Vollständigkeitssatz

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.

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