# Logik/Vollständigkeitssatz/Henkin/Textabschnitt
## Definition

Eine Menge $\Gamma$ an $S$-Ausdrücken (über einem Symbolalphabet $S$) heißt maximal widerspruchsfrei, wenn sie widerspruchsfrei ist und wenn jede Hinzunahme eines jeden Ausdrucks $\alpha \notin \Gamma$ die Menge widersprüchlich macht.

## Definition

Man sagt, dass eine Menge $\Gamma$ an $S$-Ausdrücken (über einem Symbolalphabet $S$) Beispiele enthält, wenn es für jeden Ausdruck der Form $\exists x\alpha$ einen $S$-Term $t$ derart gibt, dass
    $\exists x\alpha \rightarrow \alpha {\frac {t}{x}}$
zu $\Gamma$ gehört.
Diese beiden Begriffe sind durch folgende Aussage motiviert.

## Lemma

Es sei $S$ ein Symbolalphabet und $I$ eine $S$-Interpretation auf einer Menge $M$, wobei die Terminterpretation surjektiv sei.
Dann ist die Gültigkeitsmenge $\Gamma =I^{\vDash }$ maximal widerspruchsfrei und enthält Beispiele.

### Beweis

Zunächst ist $\Gamma =I^{\vDash }$ aufgrund des Korrektheitssatzes abgeschlossen unter Ableitungen. Für jeden $S$-Ausdruck $\alpha$ gilt die Alternative: Entweder $\alpha \in \Gamma$ oder $\neg \alpha \in \Gamma$. Insbesondere ist $\Gamma$ widerspruchsfrei. Wenn $\alpha \notin \Gamma$ ist, so ist $\neg \alpha \in \Gamma$ und daher ist $\Gamma \cup \{\alpha \}$ widersprüchlich. Also ist $\Gamma$ maximal widerspruchsfrei. Wir betrachten nun einen Ausdruck der Form $\alpha =\exists x\beta$. Wenn $\alpha \notin \Gamma$ gilt, so gilt $\exists x\beta \rightarrow \beta {\frac {t}{x}}$ in $I$ für jeden Term $t$, da ja der Vordersatz nicht gilt. Wenn hingegen $\alpha \in \Gamma$ gilt, so gibt es aufgrund des semantischen Aufbaus der Gültigkeitbeziehung ein $m\in M$ derart, dass $I{\frac {m}{x}}\vDash \beta$ gilt. Wegen der vorausgesetzten Surjektivität der Belegung gibt es einen Term $t$, der durch $m$ interpretiert wird. Daher gilt nach dem Substitutionslemma $\beta {\frac {t}{x}}$ in $I$. Also gilt $\exists x\beta \rightarrow \beta {\frac {t}{x}}$ in $I$.
$\Box$

## Lemma

Es sei $\Gamma$ eine Menge an $S$-Ausdrücken (über einem Symbolalphabet $S$), die maximal widerspruchsfrei ist. Dann gelten folgende Eigenschaften.

### Beweis

(1). Wegen der Widerspruchsfreiheit kann nicht sowohl $\alpha$ als auch $\neg \alpha$ zu $\Gamma$ gehören. Wenn weder $\alpha$ noch $\neg \alpha$ zu $\Gamma$ gehören, so ist entweder $\Gamma \cup \{\alpha \}$ oder $\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck $\beta$ sowohl
    $\Gamma \cup \{\alpha \}\vdash \beta$
als auch
    $\Gamma \cup \{\neg \alpha \}\vdash \beta$
gelten. Dies bedeutet
    $\Gamma \vdash \alpha \rightarrow \beta$
und
    $\Gamma \vdash \neg \alpha \rightarrow \beta ,$
woraus aufgrund der Fallunterscheidungsregel
    $\Gamma \vdash \beta$
folgt. Dies bedeutet aber, dass $\Gamma$ widersprüchlich ist. (2). Es sei $\Gamma \vdash \alpha$. Nach (1) ist $\alpha \in \Gamma$ oder $\neg \alpha \in \Gamma$. Das zweite kann nicht sein, da sich daraus sofort ein Widerspruch ergeben würde. Also ist $\alpha \in \Gamma$. (3). Die Richtung von links nach rechts folgt aus (2). Es seien also $\alpha ,\beta \in \Gamma$. Da $\alpha \rightarrow {\left(\beta \rightarrow \alpha \wedge \beta \right)}$ nach Aufgabe eine Tautologie ist, folgt $\alpha \wedge \beta \in \Gamma$ nach Teil (2).
$\Box$
Wir werden nun umgekehrt zu Fakt zeigen, dass man zu einer jeden maximal widerspruchsfreien Ausdrucksmenge $\Gamma$, die Beispiele enthält, eine Interpretation konstruieren kann, deren Gültigkeitsmenge mit $\Gamma$ übereinstimmt. Diese Konstruktion, die wir die kanonische Termidentifizierung nennen, geht folgendermaßen.

## Konstruktion

Es sei $\Gamma$ eine Menge an $S$-Ausdrücken (über einem Symbolalphabet $S$), die abgeschlossen unter Ableitungen ist. Dann definiert man auf der Menge aller $S$-Terme eine Äquivalenzrelation durch
    $t\sim s{\text{ genau dann, wenn der Ausdruck }}t=s{\text{ zu }}\Gamma {\text{ gehört}}.$
Es sei $M$ die Menge der Termklassen (also die Menge der Äquivalenzklassen zu dieser Äquivalenzrelation). Auf $M$ definiert man für jedes $n$-stellige Relationssymbol $R$ eine $n$-stellige Relation $R^{M}$ durch
    $R^{M}([t_{1}],[t_{2}],\ldots ,[t_{n}]){\text{ genau dann, wenn der Ausdruck }}Rt_{1}t_{2}\cdots t_{n}{\text{ zu }}\Gamma {\text{ gehört}}$
und für jedes $n$-stellige Funktionssymbol $f$ eine $n$-stellige Funktion $f^{M}$ durch
    $f^{M}([t_{1}],[t_{2}],\ldots ,[t_{n}]):=[ft_{1}t_{2}\cdots t_{n}]\,.$
Konstanten werden als
    $c^{M}:=[c]\,$
interpretiert.
Wir müssen natürlich zunächst zeigen, dass wirklich eine Äquivalenzrelation vorliegt und dass die Relationen und Funktionen wohldefiniert sind.

## Lemma

Es sei $\Gamma$ eine Menge an $S$-Ausdrücken (über einem Symbolalphabet $S$), die abgeschlossen unter Ableitungen ist.
Dann liefert die in Fakt beschriebene Konstruktion eine Äquivalenzrelation auf der Menge aller Terme und wohldefinierte Relationen bzw. Funktionen auf der Menge der Termklassen.

### Beweis

Eine Äquivalenzrelation liegt aufgrund von Axiom (1) und Fakt (1), (2) vor, da ja $\Gamma$ nach Voraussetzung abgeschlossen unter Ableitungen ist und insbesondere alle syntaktischen Tautologien enthält.
Es sei $M$ die Menge der Äquivalenzklassen, die wir in diesem Zusammenhang Termklassen nennen. Es sei $R$ ein $n$-stelliges Relationssymbol. Es sei $([s_{1}],\ldots ,[s_{n}])$ ein $n$-Tupel aus Termklassen, die einerseits durch das Termtupel $(s_{1},\ldots ,s_{n})$ und andererseits durch das Termtupel $(t_{1},\ldots ,t_{n})$ repräsentiert werde. Es gilt also $s_{i}\sim t_{i}$ bzw. $s_{i}=t_{i}\in \Gamma$. Wenn nun $Rs_{1}\ldots s_{n}$ zu $\Gamma$ gehört, so folgt aus Fakt (4) auch $Rt_{1}\ldots t_{n}\in \Gamma$. Unter den gleichen Voraussetzungen folgt mit Fakt (3) die Zugehörigkeit $fs_{1}\ldots s_{n}=ft_{1}\ldots t_{n}\in \Gamma$ und somit
    $[fs_{1}\ldots s_{n}]=[ft_{1}\ldots t_{n}]\,,$
also die Wohldefiniertheit der Funktion.
$\Box$

## Lemma

Es sei $\Gamma$ eine Menge an $S$-Ausdrücken (über einem Symbolalphabet $S$), die abgeschlossen unter Ableitungen ist.
Dann gilt für die Interpretation $(M,\beta )$, wobei $M$ die in Fakt beschriebene Menge aus Termklassen (mit der natürlichen Interpretation $I$ von Konstanten, Funktionssymbolen und Relationssymbolen) und $\beta$ die natürliche Belegung $\beta (x)=[x]$ für Variablen ist, die Beziehung
für alle Terme $t$.

### Beweis

Wir führen Induktion über den Aufbau der Terme, wobei der Induktionsanfang unmittelbar durch die natürliche Belegung gesichert ist. Die Aussage gelte nun für Terme $t_{1},\ldots ,t_{n}$ und $f$ sei ein $n$-stelliges Funktionssymbol. Dann ist
    $I(ft_{1}\ldots t_{n})=f^{M}(I(t_{1}),\ldots ,I(t_{n}))=f^{M}([t_{1}],\ldots ,[t_{n}])=[ft_{1}\ldots t_{n}]\,.$
$\Box$
Die folgende Aussage heißt Satz von Henkin . Er wird durch Induktion über den sogenannten Rang eines Ausdrucks bewiesen.

## Satz

Es sei $\Gamma$ eine Menge an $S$-Ausdrücken (über einem Symbolalphabet $S$), die maximal widerspruchsfrei ist und Beispiele enthält.
Dann ist die in Fakt gegebene Interpretation ein Modell für $\Gamma$.
Insbesondere ist $\Gamma$ erfüllbar.

### Beweis

Es sei $M$ das konstruierte Modell zu $\Gamma$ und $I$ die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz
    $\alpha \in \Gamma {\text{ genau dann, wenn }}I\vDash \alpha$
für alle Ausdrücke $\alpha$, durch Induktion über den Rang der Ausdrücke. Zum Induktionsanfang sei der Rang von $\alpha$ gleich $0$, also $\alpha$ atomar. D.h. $\alpha$ ist entweder von der Form $s=t$ oder $Rt_{1}\ldots t_{n}$. Im ersten Fall ist $s=t\in \Gamma$ äquivalent zu $s\sim t$ bzw. $[s]=[t]$ in $M$. Dies ist nach Fakt äquivalent zu $I(s)=I(t)$ und das bedeutet $I\vDash s=t$.
Im zweiten Fall ist $Rt_{1}\ldots t_{n}\in \Gamma$ - nach Konstruktion von $M$ und $R^{M}$ - äquivalent zu $R^{M}([t_{1}],\ldots ,[t_{n}])$, und dies ist äquivalent zu $I\vDash Rt_{1}\ldots t_{n}$.
Es sei nun die Aussage für alle Ausdrücke vom Rang $\leq r$ bewiesen und sei $\alpha$ ein Ausdruck vom Rang $r+1$. Wir betrachten die mögliche Struktur von $\alpha$ gemäß Definition. Bei
    $\alpha =\neg \beta \,$
ergibt sich die Äquivalenz aus der Induktionsvoraussetzung ($\beta$ hat kleineren Rang als $\alpha$) und Fakt (1). Bei
    $\alpha =\beta _{1}\wedge \beta _{2}\,$
besitzen die beiden Bestandteile kleineren Rang als $\alpha$. Die Zugehörigkeit $\alpha \in \Gamma$ ist nach Fakt (3) äquivalent zur gemeinsamen Zugehörigkeit $\beta _{1},\beta _{2}\in \Gamma$. Nach Induktionsvoraussetzung bedeutet dies $I\vDash \beta _{1}$ und $I\vDash \beta _{2}$. Dies bedeutet wiederum $I\vDash \beta _{1}\wedge \beta _{2}$ aufgrund der Modellbeziehung. Bei
    $\alpha =\exists x\beta \,$
besitzt wieder $\beta$ einen kleineren Rang. Die Zugehörigkeit $\alpha \in \Gamma$ ist aufgrund der Eigenschaft, Beispiele zu enthalten und aufgrund von Axiom äquivalent zur Existenz eines Terms $t$ und der Zugehörigkeit $\beta {\frac {t}{x}}\in \Gamma$. Die Substitution von $\beta$ nach $\beta {\frac {t}{x}}$ verändert nach Aufgabe nicht den Rang. Wir können also auf $\beta {\frac {t}{x}}$ die Induktionsvoraussetzung anwenden und erhalten die Äquivalenz zu $I\vDash \beta {\frac {t}{x}}$. Nach dem Substitutionslemma ist dies äquivalent zu $I{\frac {I(t)}{x}}\vDash \beta$ bzw. $I{\frac {[t]}{x}}\vDash \beta$ wegen Fakt. Dies ist äquivalent zu $I\vDash \exists x\beta$ aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.
$\Box$