Prädikatenlogik/Vollständigkeitssatz/Fakt/Beweis

Beweis

Die Richtung von rechts nach links ist der Korrektheitssatz. Es sei umgekehrt ${}\Gamma \not \vdash \alpha$. Um zu zeigen, dass auch ${}\Gamma \not \vDash \alpha$ gilt, müssen wir ein Modell angeben, das ${}\Gamma$ erfüllt, aber nicht ${}\alpha$. Die Nichtableitbarkeit ${}\Gamma \not \vdash \alpha$ bedeutet, dass ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei ist, und wir müssen zeigen, dass ${}\Gamma \cup \{\neg \alpha \}$ erfüllbar ist. Nach Fakt gibt es eine widerspruchsfreie Erweiterung ${}S\subseteq S'$ des Symbolalphabets und eine Erweiterung ${}\Gamma '$ von ${}\Gamma \cup \{\neg \alpha \}$, die Beispiele enthält. Nach Fakt gibt es eine maximal widerspruchsfreie ${}S'$-Ausdrucksmenge ${}\Gamma ^{\prime \prime }\supseteq \Gamma '$. Diese enthält mit ${}\Gamma '$ ebenfalls Beispiele. Nach dem Satz von Henkin gibt es eine ${}S'$-Interpretation, die ${}\Gamma ^{\prime \prime }$ erfüllt. Diese Interpretation erfüllt erst recht ${}\Gamma \cup \{\neg \alpha \}$.

Zur bewiesenen Aussage