Logik/Vollständigkeitssatz/Henkin/Fakt/Beweis

Beweis

Es sei $M$ das konstruierte Modell zu $\mathrm{\Gamma }$ und $I$ die zugehörige Interpretation mit der natürlichen Belegung für die Variablen. Wir zeigen die Äquivalenz

$\alpha \in \mathrm{\Gamma }\text{ genau dann, wenn }I\models \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 $R{t}_1\dots t_n$. Im ersten Fall ist  $s=t\in \mathrm{\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\models s=t$.

Im zweiten Fall ist  $R{t}_1\dots t_n\in \mathrm{\Gamma }$  - nach Konstruktion von $M$ und $R^M$ - äquivalent zu $R^M([t_1],\dots ,[t_n])$, und dies ist äquivalent zu $I\models R{t}_1\dots t_n$.

Es sei nun die Aussage für alle Ausdrücke vom Rang $\le r$ bewiesen und sei $\alpha$ ein Ausdruck vom Rang $r+1$. Wir betrachten die mögliche Struktur von $\alpha$ gemäß Definition. Bei

$\alpha =\mathrm{\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 \mathrm{\Gamma }$  ist nach Fakt  (3) äquivalent zur gemeinsamen Zugehörigkeit  ${\beta }_1,{\beta }_2\in \mathrm{\Gamma }$.  Nach Induktionsvoraussetzung bedeutet dies $I\models {\beta }_1$ und $I\models {\beta }_2$. Dies bedeutet wiederum $I\models {\beta }_1\wedge {\beta }_2$ aufgrund der Modellbeziehung. Bei

$\alpha =\mathrm{\exists }x\beta$

besitzt wieder $\beta$ einen kleineren Rang. Die Zugehörigkeit  $\alpha \in \mathrm{\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 \mathrm{\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\models \beta \frac{t}{x}$. Nach dem Substitutionslemma ist dies äquivalent zu $I\frac{I(t)}{x}\models \beta$ bzw. $I\frac{[t]}{x}\models \beta$ wegen Fakt. Dies ist äquivalent zu $I\models \mathrm{\exists }x\beta$ aufgrund der Modellbeziehung und der Surjektivität der Termabbildung.

Zur bewiesenen Aussage