Der Satz von Henkin, benannt nach Leon Henkin, ist ein Satz aus der mathematischen Logik. Er beschäftigt sich mit der Frage, wann die Terminterpretation zu einer vorgegebenen Menge von Ausdrücken einer Prädikatenlogik erster Stufe ein Modell dieser Menge ist. Dieser Satz führt sowohl zu einem alternativen Beweis des Gödelschen Vollständigkeitssatzes als auch zu einem Beweis des Satzes von Löwenheim-Skolem.
Es sei eine vorgegebene Menge von Ausdrücken einer Sprache erster Stufe. Ist widerspruchsfrei, das heißt, lässt sich kein Ausdruck der Form daraus ableiten, so sichert der Gödelsche Vollständigkeitssatz die Existenz eines Modells. Auf Leon Henkin geht die Idee zurück, zur Konstruktion die Terminterpretation heranzuziehen. Dazu ist zunächst zu klären, unter welchen Voraussetzungen die Terminterpretation ein Modell für die Ausdrucksmenge ist. Zum Satz von Henkin, der genau diese Frage zum Gegenstand hat, sind zwei Definitionen erforderlich.
Eine Ausdrucksmenge heißt negationstreu, wenn für jeden Ausdruck gilt, dass oder , das heißt, ist ein Ausdruck nicht aus ableitbar, so ist dessen Negation ableitbar.
Eine Ausdrucksmenge hat Beispiele, wenn zu jedem Ausdruck der Form ein Term der Sprache existiert, so dass aus ableitbar ist. Dabei steht für denjenigen Ausdruck, der aus entsteht, wenn man die Variable durch den Term ersetzt. Die Ausdrucksmenge kann also zu jeder Existenzbehauptung ein Beispiel vorweisen.
- Satz von Henkin: Ist eine Ausdrucksmenge, die widerspruchsfrei und negationstreu ist und Beispiele enthält, so gilt für jeden Ausdruck :
Dabei bedeutet , dass ein Modell für ist. Insbesondere ist also die Terminterpretation zu auch ein Modell von , das heißt, es gilt .
Widerspruchsfreie Mengen sind in der Regel weder negationstreu noch enthalten sie Beispiele. Um den Satz von Henkin zum Beweis der Existenz eines Modells in Anwendung zu bringen, muss man die Ausdrucksmenge und die Symbolmenge so erweitern, dass die Voraussetzungen für diese erweiterte Situation erfüllt sind. Das ist Henkins Beweis des Vollständigkeitssatzes. Ist die Symbolmenge von Anfang an höchstens abzählbar, so ist auch die erweiterte Symbolmenge höchstens abzählbar. Da dann auch die Menge der Terme höchstens abzählbar ist, stellt die Terminterpretation nach dem Satz von Henkin ein höchstens abzählbares Modell dar und man erhält leicht den Satz von Löwenheim-Skolem.
Literatur Bearbeiten
- Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. 4. Aufl. Spektrum Akademischer Verlag, Heidelberg 1998, ISBN 3-8274-0130-5, insbesondere Kapitel V, §1.