Logik/Vollständigkeitssatz/Auffüllung mit Beispielen/Einzelschritt/Fakt/Beweis

Beweis

Die Menge ${}S^{*}$ definieren wir als disjunkte Vereinigung

${}S^{*}=S\cup V\,,$

wobei ${}V$ eine Variablenmenge ist, die für jeden Ausdruck der Form ${}\exists x\alpha \in L^{S}$ genau eine (neue) Variable enthält, die wir mit ${}y_{\exists x\alpha }$ bezeichnen. Wir setzen

${}\Gamma ^{*}=\Gamma \cup {\left\{\exists x\alpha \rightarrow \alpha {\frac {y_{\exists x\alpha }}{x}}\mid \exists x\alpha \in L^{S}\right\}}\,.$

Daher ist ${}\Gamma \subseteq \Gamma ^{*}$ und ${}\Gamma ^{*}$ enthält ${}S$-Beispiele. Es bleibt also die Widerspruchsfreiheit zu zeigen. Wäre ${}\Gamma ^{*}$ widerspruchsvoll, so wäre auch eine endliche Teilmenge davon widerspruchsvoll und insbesondere würde es Ausdrücke ${}\alpha _{1},\ldots ,\alpha _{n}\in L^{S}$ derart geben, dass

$\Gamma \cup \{\exists x_{1}\alpha _{1}\rightarrow \alpha _{1}{\frac {y_{\exists x_{1}\alpha _{1}}}{x_{1}}}\}\cup \ldots \cup \{\exists x_{n}\alpha _{n}\rightarrow \alpha _{n}{\frac {y_{\exists x_{n}\alpha _{n}}}{x_{n}}}\}$

widersprüchlich ist (dabei können die ${}x_{i}$ gleich oder verschieden sein). Da bei jeder Hinzunahme eine neue Variable ${}y_{\exists x_{n}\alpha _{n}}$ verwendet wird, können wir induktiv Fakt anwenden und erhalten die Widersprüchlichkeit von ${}\Gamma$.

Zur bewiesenen Aussage