Satz von Henkin

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 $L_I^S$ erster Stufe. Ist Φ widerspruchsfrei, das heißt, lässt sich kein Ausdruck der Form $\varphi\land\neg\varphi$ 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 ${\mathcal T}^\Phi$ 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 $\Phi \vdash \varphi$ oder $\Phi \vdash \neg\varphi$, das heißt, ist ein Ausdruck nicht aus Φ ableitbar, so ist dessen Negation ableitbar.

Eine Ausdrucksmenge Φ hat Beispiele, wenn zu jedem Ausdruck der Form $\exists x \varphi$ ein Term t der Sprache existiert, so dass $(\exists x \varphi \rightarrow \varphi\frac{t}{x})$ aus Φ ableitbar ist. Dabei steht $\varphi\frac{t}{x}$ für denjenigen Ausdruck, der aus φ entsteht, wenn man die Variable x durch den Term t 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 φ:

${\mathcal T}^\Phi \vDash \varphi \quad \Leftrightarrow \quad \Phi \vdash \varphi$.

Dabei bedeutet ${\mathcal T}^\Phi \vDash \varphi$, dass ${\mathcal T}^\Phi$ ein Modell für φ ist. Insbesondere ist also die Terminterpretation zu Φ auch ein Modell von Φ, das heißt, es gilt ${\mathcal T}^\Phi \vDash \Phi$.

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

• H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN, 3-8274-0130-5, insbesondere Kapitel V, §1.