Logik/Vollständigkeitssatz/Henkin/Fakt/Beweis

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.

Zur bewiesenen Aussage