Aussagenlogik/Vollständigkeitssatz/Allgemeiner Fall mit Zorn/Textabschnitt

Lemma

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann gibt es eine maximal widerspruchsfreie Teilmenge ${}\Gamma '\subseteq L^{V}$, die ${}\Gamma$ enthält.

Beweis

Wir betrachten die Menge

${}M:={\left\{\Delta \subseteq L^{V}\mid \Delta \supseteq \Gamma ,\,\Delta {\text{ widerspruchsfrei }}\right\}}\,$

mit der durch Inklusion gegebenen Ordnung. Wegen ${}\Gamma \in M$ ist diese Menge nicht leer. Es sei ${}N\subseteq M$ eine nichtleere total geordnete Teilmenge. Die Vereinigung

${}\Theta =\bigcup _{\Delta \in N}\Delta \,$

ist ebenfalls widerspruchsfrei, da ein Widerspruch schon aus einer endlichen Teilmenge ableitbar wäre, die ganz in einem der ${}\Delta$ enthalten wäre. Also besitzt die Kette in ${}M$ eine obere Schranke. Nach dem Lemma von Zorn gibt es also in ${}M$ maximale Elemente. Ein solches ist maximal widerspruchsfrei.

$\Box$

Satz

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine widerspruchsfreie Teilmenge der zugehörigen Sprache der Aussagenlogik.

Dann ist ${}\Gamma$ erfüllbar.

Beweis

Nach Fakt (bzw. Fakt im abzählbaren Fall) kann man ${}\Gamma$ zu einer maximal widerspruchsfreien Ausdrucksmenge ${}\Gamma '$ auffüllen. Nach Fakt ist ${}\Gamma '$ erfüllbar, d.h., es gibt eine Wahrheitsbelegung ${}\lambda$ derart, dass unter der zugehörigen Interpretation alle Ausdrücke aus ${}\Gamma '$ gültig sind. Dann sind unter dieser Belegung insbesondere die Ausdrücke aus ${}\Gamma$ gültig.

$\Box$

Die folgende Aussage ist der Vollständigkeitssatz für die Aussagenlogik.

Satz

Es sei ${}V$ eine Menge an Aussagenvariablen und ${}\Gamma \subseteq L^{V}$ eine Teilmenge der zugehörigen Sprache der Aussagenlogik. Es sei ${}\alpha \in L^{V}$.

Dann ist

$\Gamma \vdash \alpha {\text{ genau dann, wenn }}\Gamma \vDash \alpha .$

Beweis

Dass die Ableitungsbeziehung die Folgerungsbeziehung impliziert, wurde bereits im Rahmen der Korrektheitsüberlegungen zu den Ableitungsregeln gezeigt. Für die Umkehrung nehmen wir ${}\Gamma \not \vdash \alpha$ an. Dies bedeutet nach Aufgabe, dass ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei ist. Nach Fakt ist dann auch ${}\Gamma \cup \{\neg \alpha \}$ erfüllbar. Es gibt also eine Wahrheitsbelegung mit ${}I\vDash \Gamma$ und ${}I\vDash \neg \alpha$. Also ist ${}\Gamma \not \vDash \alpha$.

$\Box$