# 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

$\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.

### 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$