Aussagenlogik/Vollständigkeitssatz/Vorbereitungen/Abzählbar/Textabschnitt

Definition

Eine Teilmenge ${}\Gamma \subseteq L^{V}$ zu einer Menge ${}V$ an Aussagenvariablen heißt maximal widerspruchsfrei, wenn ${}\Gamma$ widerspruchsfrei ist und jede echt größere Menge ${}\Gamma \subset \Gamma '$ widersprüchlich ist.

Lemma

Es sei ${}L^{V}$ die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$ und es sei ${}\lambda$ eine Wahrheitsbelegung der Variablen mit zugehöriger Interpretation ${}I$.

Dann ist ${}I^{\vDash }$ maximal widerspruchsfrei.

Beweis

Siehe Aufgabe.

$\Box$

Lemma

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

1. Für jedes ${}\alpha \in L^{V}$ ist entweder ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$.
2. Aus ${}\Gamma \vdash \alpha$ folgt ${}\alpha \in \Gamma$.
3. Es ist ${}\alpha \wedge \beta \in \Gamma$ genau dann, wenn ${}\alpha \in \Gamma$ und ${}\beta \in \Gamma$.
4. Es ist ${}\alpha \rightarrow \beta \in \Gamma$ genau dann, wenn ${}\alpha \not \in \Gamma$ oder ${}\beta \in \Gamma$.

Beweis

(1). Wegen der Widerspruchsfreiheit können nicht sowohl ${}\alpha$ als auch ${}\neg \alpha$ zu ${}\Gamma$ gehören. Wenn weder ${}\alpha$ noch ${}\neg \alpha$ zu ${}\Gamma$ gehören, so ist entweder ${}\Gamma \cup \{\alpha \}$ oder ${}\Gamma \cup \{\neg \alpha \}$ widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck ${}\beta$ sowohl

$\Gamma \cup \{\alpha \}\vdash \beta$

als auch

$\Gamma \cup \{\neg \alpha \}\vdash \beta$

gelten. Dies bedeutet nach Aufgabe

$\Gamma \vdash \alpha \rightarrow \beta$

und

$\Gamma \vdash \neg \alpha \rightarrow \beta ,$

woraus aufgrund der Fallunterscheidungsregel

$\Gamma \vdash \beta$

folgt. Dies bedeutet aber, dass ${}\Gamma$ widersprüchlich ist.
(2). Es sei ${}\Gamma \vdash \alpha$. Nach (1) ist ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$. Das zweite kann nicht sein, da sich daraus sofort ein Widerspruch ergeben würde. Also ist ${}\alpha \in \Gamma$.
(3) folgt aus (2) und der Konjunktionsregel.
(4). Aufgrund von (1) und Aufgabe müssen wir die Äquivalenz ${}\neg {\left(\alpha \rightarrow \beta \right)}\in \Gamma$ genau dann, wenn ${}\alpha \in \Gamma$ und ${}\neg \beta \in \Gamma$ zeigen. Dies ergibt sich aus (3).

$\Box$

Lemma

Es sei ${}\Gamma \subseteq L^{V}$ eine Ausdrucksmenge in der Sprache der Aussagenlogik zu einer Aussagenvariablenmenge ${}V$. Es sei ${}\Gamma$ widerspruchsfrei, abgeschlossen unter Ableitungen und für jede Aussagenvariable ${}p\in V$ gelte ${}p\in \Gamma$ oder ${}\neg p\in \Gamma$.

Dann ist ${}\Gamma$ maximal widerspruchsfrei.

Beweis

Wir zeigen zuerst durch Induktion über den Aufbau der Sprache, dass für jedes ${}\alpha \in L^{V}$ die Alternative ${}\alpha \in \Gamma$ oder ${}\neg \alpha \in \Gamma$ gilt. Daraus folgt die maximale Widerspruchsfreiheit. Für ${}\alpha =p$ eine Aussagenvariable ist dies Teil der Voraussetzung. Bei ${}\alpha =\neg \beta$ folgt wegen ${}\vdash \neg {\left(\neg \beta \right)}\leftrightarrow \beta$ die Aussage aus der Induktionsvoraussetzung, da ${}\Gamma$ abgeschlossen unter Ableitungen ist. Es sei nun ${}\alpha =\beta \wedge \gamma$. Bei ${}\beta \in \Gamma$ und ${}\gamma \in \Gamma$ ist wegen der Ableitungsabgeschlossenheit auch ${}\beta \wedge \gamma \in \Gamma$. Wenn hingegen ${}\beta \notin \Gamma$ ist, so folgt nach der Induktionsvoraussetzung ${}\neg \beta \in \Gamma$. Aufgrund der Tautologie ${}\vdash \neg \beta \rightarrow \neg {\left(\beta \wedge \gamma \right)}$ ergibt sich ${}\neg \alpha =\neg {\left(\beta \wedge \gamma \right)}\in \Gamma$. Der Beweis für die Implikation verläuft ähnlich, siehe Aufgabe.

Zum Nachweis, dass ${}\Gamma$ maximal widerspruchsfrei ist, sei ${}\alpha \notin \Gamma$ angenommen. Nach dem, was wir eben bewiesen haben, gilt dann ${}\neg \alpha \in \Gamma$. Dann ist aber ${}\alpha ,\neg \alpha \in \Gamma \cup \{\alpha \}$ und somit ist diese erweiterte Menge widersprüchlich.

$\Box$

Oben haben wir gesehen, dass Interpretationen maximal widerspruchsfreie Ausdrucksmengen liefern. Davon gilt auch die Umkehrung.

Lemma

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

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

Beweis

Da ${}\Gamma$ maximal widerspruchsfrei ist, gilt nach Fakt  (1) für jede Aussagenvariable die Alternative ${}p\in \Gamma$ oder ${}\neg p\in \Gamma$. Wir betrachten die Wahrheitsbelegung

${}\lambda (p)={\begin{cases}1\,,{\text{ falls }}p\in \Gamma \,,\\0\,,{\text{ falls }}\neg p\in \Gamma \,,\end{cases}}\,$

mit der zugehörigen Interpretation ${}I$. Wir behaupten

${}I^{\vDash }=\Gamma \,,$

was wir über den Aufbau der Sprache beweisen. Der Induktionsanfang ist durch die gewählte Belegung gesichert, der Induktionsschritt folgt aus Fakt.

$\Box$