Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 4/latex
\setcounter{section}{4}
\zwischenueberschrift{Die Ableitungsbeziehung}
Die syntaktische Entsprechung zur Folgerungsbeziehung ist die folgende Ableitungsbeziehung.
\inputdefinition
{}
{
Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$ und sei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Man sagt, dass $\alpha$ aus $\Gamma$ \definitionswort {ableitbar}{} ist, geschrieben
\mathdisp {\Gamma \vdash \alpha} { , }
wenn es endlich viele Ausdrücke
\mavergleichskette
{\vergleichskette
{ \alpha_1 , \ldots , \alpha_n
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart gibt, dass
\mathdisp {\vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \alpha} { }
gilt.
}
Die vorgegebene Ausdrucksmenge $\Gamma$ kann endlich oder unendlich sein, in der Ableitungsbeziehung kommen aber stets nur endlich viele Ausdrücke aus $\Gamma$ vor
\zusatzklammer {eine \anfuehrung{unendliche Konjunktion}{} ist gar nicht definiert} {} {.}
Die Menge der aus einer gegebenen Ausdrucksmenge $\Gamma$ ableitbaren Ausdrücke bezeichnet man mit $\Gamma^\vdash$, also
\mavergleichskettedisp
{\vergleichskette
{ \Gamma^\vdash
}
{ =} { { \left\{ \alpha \in L^V \mid \Gamma \vdash \alpha \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wegen
\mathl{\vdash \alpha \rightarrow \alpha}{}
\zusatzklammer {nach
Lemma 3.11} {} {}
gilt
\mavergleichskette
{\vergleichskette
{ \Gamma
}
{ \subseteq }{ \Gamma^\vdash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ = }{ \Gamma^\vdash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sagt man, dass $\Gamma$ \stichwort {abgeschlossenen unter Ableitungen} {} ist. Die aus der leeren Menge ableitbaren Ausdrücke sind gerade die
\zusatzklammer {syntaktischen} {} {}
Tautologien.
Aus den \zusatzklammer {Grund- oder abgeleiteten} {} {} Tautologien ergeben sich direkt Regeln für die Ableitungsbeziehung.
{Aussagenlogik/Ableitungsbeziehung/Regeln/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$.}
\faktfolgerung {Dann gelten folgende Regeln für die
\definitionsverweis {Ableitungsbeziehung}{}{}
\zusatzklammer {dabei seien \mathlk{\alpha, \beta, \gamma, \alpha_i}{} Aussagen} {} {.}
\aufzaehlungsieben{Konjunktionsregel:
\mathl{\Gamma \vdash \alpha \wedge \beta}{} genau dann, wenn
\mathl{\Gamma \vdash \alpha}{} und
\mathl{\Gamma \vdash \beta}{.}
}{Kettenschlussregel: Wenn
\mathl{\Gamma \vdash \alpha \rightarrow \beta}{} und
\mathl{\Gamma \vdash \beta \rightarrow \gamma}{,} dann auch
\mathl{\Gamma \vdash \alpha \rightarrow \gamma}{.}
}{Modus ponens: Wenn
\mathl{\Gamma \vdash \alpha}{} und
\mathl{\Gamma \vdash \alpha \rightarrow \beta}{,} dann ist auch
\mathl{\Gamma \vdash \beta}{.}
}{Wenn
\mathl{\Gamma \vdash \alpha}{,} so auch
\mathl{\Gamma \vdash \beta \rightarrow \alpha}{.}
}{Wenn
\mathl{\Gamma \vdash \alpha_1 , \ldots , \Gamma \vdash \alpha_n}{} und
\mathl{\Gamma \vdash \alpha_1 \wedge \ldots \wedge \alpha_n \rightarrow \beta}{,} dann auch
\mathl{\Gamma \vdash \beta}{.}
}{Widerspruchsregel: Wenn
\mathl{\Gamma \vdash \alpha}{} und
\mathl{\Gamma \vdash \neg \alpha}{,} dann auch
\mathl{\Gamma \vdash \beta}{.}
}{Fallunterscheidungsregel: Wenn
\mathl{\Gamma \vdash \alpha \rightarrow \beta}{} und
\mathl{\Gamma \vdash \neg \alpha \rightarrow \beta}{,} dann auch
\mathl{\Gamma \vdash \beta}{.}
}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 4.3. }
\inputdefinition
{}
{
Eine Ausdrucksmenge
\mavergleichskette
{\vergleichskette
{ \Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$ heißt
\definitionswort {widersprüchlich}{,}
wenn es einen Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathkor {} {\Gamma \vdash \alpha} {und} {\Gamma \vdash \neg \alpha} {}
gibt. Eine nicht widersprüchliche Ausdrucksmenge heißt \stichwort {widerspruchsfrei} {.}
}
Nach Lemma 4.2 (6) kann man aus einer widersprüchlichen Aussagenmenge jede Aussage ableiten.
\zwischenueberschrift{Der Vollständigkeitssatz der Aussagenlogik I}
Wir zeigen, dass für die Aussagenlogik die Ableitbarkeitsbeziehung mit der Folgerungsbeziehung übereinstimmt. Im Beweisaufbau orientieren wir uns an dem Vollständigkeitssatz für die Prädikatenlogik, der deutlich schwieriger ist und der später folgen wird.
\inputdefinition
{}
{
Eine Teilmenge
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zu einer Menge $V$ an
\definitionsverweis {Aussagenvariablen}{}{}
heißt
\definitionswort {maximal widerspruchsfrei}{,}
wenn $\Gamma$
\definitionsverweis {widerspruchsfrei}{}{}
ist und jede echt größere Menge
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subset }{\Gamma'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
widersprüchlich ist.
}
{Aussagenlogik/Interpretation/Maximal widerspruchsfrei/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $L^V$ die Sprache der Aussagenlogik zu einer Aussagenvariablenmenge $V$ und es sei $\lambda$ eine
\definitionsverweis {Wahrheitsbelegung}{}{}
der Variablen mit zugehöriger
\definitionsverweis {Interpretation}{}{}
$I$.}
\faktfolgerung {Dann ist $I^\vDash$
\definitionsverweis {maximal widerspruchsfrei}{}{.}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 4.9. }
\inputfaktbeweis
{Aussagenlogik/Maximal widerspruchsfrei/Eigenschaften/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {maximal widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}}
\faktuebergang {Dann gelten folgende Aussagen.}
\faktfolgerung {\aufzaehlungvier{Für jedes
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist entweder
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{ \neg \alpha
}
{ \in }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mathl{\Gamma \vdash \alpha}{} folgt
\mathl{\alpha \in \Gamma}{.}
}{Es ist
\mathl{\alpha \wedge \beta \in \Gamma}{} genau dann, wenn
\mathl{\alpha \in \Gamma}{} und
\mathl{\beta \in \Gamma}{.}
}{Es ist
\mathl{\alpha \rightarrow \beta \in \Gamma}{} genau dann, wenn
\mathl{\alpha \not\in \Gamma}{} oder
\mathl{\beta \in \Gamma}{.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
\teilbeweis {}{}{}
{(1). Wegen der Widerspruchsfreiheit können nicht sowohl $\alpha$ als auch
\mathl{\neg \alpha}{} zu $\Gamma$ gehören. Wenn weder $\alpha$ noch
\mathl{\neg \alpha}{} zu $\Gamma$ gehören, so ist entweder
\mathl{\Gamma \cup \{ \alpha \}}{} oder
\mathl{\Gamma \cup \{ \neg \alpha \}}{} widerspruchsfrei. Wären nämlich beide widersprüchlich, so würde für einen beliebigen Ausdruck $\beta$ sowohl
\mathdisp {\Gamma \cup \{ \alpha \} \vdash \beta} { }
als auch
\mathdisp {\Gamma \cup \{ \neg \alpha \} \vdash \beta} { }
gelten. Dies bedeutet
nach Aufgabe 4.4
\mathdisp {\Gamma \vdash \alpha \rightarrow \beta} { }
und
\mathdisp {\Gamma \vdash \neg \alpha \rightarrow \beta} { , }
woraus aufgrund der
Fallunterscheidungsregel
\mathdisp {\Gamma \vdash \beta} { }
folgt. Dies bedeutet aber, dass $\Gamma$ widersprüchlich ist.}
{}
\teilbeweis {}{}{}
{(2). Es sei
\mathl{\Gamma \vdash \alpha}{.} Nach (1) ist
\mathkor {} {\alpha \in \Gamma} {oder} {\neg \alpha \in \Gamma} {.}
Das zweite kann nicht sein, da sich daraus sofort ein Widerspruch ergeben würde. Also ist
\mathl{\alpha \in \Gamma}{.}}
{}
\teilbeweis {}{}{}
{(3) folgt aus (2) und der
Konjunktionsregel.}
{}
\teilbeweis {}{}{}
{(4). Aufgrund von (1) und
Aufgabe *****
müssen wir die Äquivalenz
\mathl{\neg { \left( \alpha \rightarrow \beta \right) } \in \Gamma}{} genau dann, wenn
\mathl{\alpha \in \Gamma}{} und
\mathl{\neg \beta \in \Gamma}{} zeigen. Dies ergibt sich aus (3).}
{}
\inputfaktbeweis
{Aussagenlogik/Ausdrucksmenge abgeschlossen und Alternative für Variablen/Maximal widerspruchsfrei/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Ausdrucksmenge in der
\definitionsverweis {Sprache der Aussagenlogik}{}{}
zu einer Aussagenvariablenmenge $V$. Es sei $\Gamma$
\definitionsverweis {widerspruchsfrei}{}{,}
abgeschlossen unter Ableitungen und für jede Aussagenvariable
\mathl{p \in V}{} gelte
\mathl{p \in \Gamma}{} oder
\mathl{\neg p \in \Gamma}{.}}
\faktfolgerung {Dann ist $\Gamma$
\definitionsverweis {maximal widerspruchsfrei}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir zeigen zuerst durch Induktion über den Aufbau der Sprache, dass für jedes
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Alternative
\mathkor {} {\alpha \in \Gamma} {oder} {\neg \alpha \in \Gamma} {}
gilt. Daraus folgt die maximale Widerspruchsfreiheit. Für
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ p
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Aussagenvariable ist dies Teil der Voraussetzung. Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ \neg \beta
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt wegen
\mathl{\vdash \neg { \left( \neg \beta \right) } \leftrightarrow \beta}{}
die Aussage aus der Induktionsvoraussetzung, da $\Gamma$ abgeschlossen unter Ableitungen ist. Es sei nun
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ \beta \wedge \gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei
\mathkor {} {\beta \in \Gamma} {und} {\gamma \in \Gamma} {}
ist wegen der Ableitungsabgeschlossenheit auch
\mathl{\beta \wedge \gamma \in \Gamma}{.} Wenn hingegen
\mathl{\beta \notin \Gamma}{} ist, so folgt nach der Induktionsvoraussetzung
\mathl{\neg \beta \in \Gamma}{.} Aufgrund der Tautologie
\mathl{\vdash \neg \beta \rightarrow \neg { \left( \beta \wedge \gamma \right) }}{} ergibt sich
\mathl{\neg \alpha = \neg { \left( \beta \wedge \gamma \right) } \in \Gamma}{.} Der Beweis für die Implikation verläuft ähnlich, siehe
Aufgabe 4.10.
Zum Nachweis, dass $\Gamma$ maximal widerspruchsfrei ist, sei
\mathl{\alpha \notin \Gamma}{} angenommen. Nach dem, was wir eben bewiesen haben, gilt dann
\mathl{\neg \alpha \in \Gamma}{.} Dann ist aber
\mavergleichskette
{\vergleichskette
{ \alpha, \neg \alpha
}
{ \in }{ \Gamma \cup \{ \alpha \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und somit ist diese erweiterte Menge widersprüchlich.
Oben haben wir gesehen, dass Interpretationen maximal widerspruchsfreie Ausdrucksmengen liefern. Davon gilt auch die Umkehrung.
\inputfaktbeweis
{Aussagenlogik/Vollständigkeitssatz/Maximal widerspruchsfrei/Erfüllbar/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {maximal widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}}
\faktfolgerung {Dann ist $\Gamma$
\definitionsverweis {erfüllbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Da $\Gamma$ maximal widerspruchsfrei ist, gilt
nach Lemma 4.6 (1)
für jede Aussagenvariable die Alternative
\mavergleichskette
{\vergleichskette
{p
}
{ \in }{\Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{\neg p
}
{ \in }{\Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir betrachten die Wahrheitsbelegung
\mavergleichskettedisp
{\vergleichskette
{\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
\mavergleichskettedisp
{\vergleichskette
{I^\vDash
}
{ =} {\Gamma
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
was wir über den Aufbau der Sprache beweisen. Der Induktionsanfang ist durch die gewählte Belegung gesichert, der Induktionsschritt folgt aus
Lemma 4.6.
\zwischenueberschrift{Auffüllungsstrategien}
Wir wollen zeigen, dass jede widerspruchsfreie Ausdrucksmenge erfüllbar ist. Die Strategie ist hierbei, sie zu einer maximal widerspruchsfreien Ausdrucksmenge aufzufüllen und dann die vorstehende Aussage anzuwenden. Wir unterscheiden die beiden Fälle, wo die Aussagenvariablenmenge abzählbar ist und den allgemeinen Fall einer beliebigen Aussagenvariablenmenge. Letzteres erfordert stärkere mengentheoretische Hilfsmittel, nämlich das Lemma von Zorn.
\inputfaktbeweis
{Aussagenlogik/Vollständigkeitssatz/Abzählbar/Auffüllungsstrategie/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $V$ eine
\definitionsverweis {abzählbare}{}{}
Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}}
\faktfolgerung {Dann kann man $\Gamma$ durch sukzessive Hinzunahme von entweder
\mathl{p_n}{} oder
\mathl{\neg p_n}{} und durch Abschluss unter der
\definitionsverweis {Ableitungsbeziehung}{}{}
zu einer maximal widerspruchsfreien Teilmenge
\mavergleichskette
{\vergleichskette
{\Gamma'
}
{ \supseteq }{\Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergänzen.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei
\mathbed {p_n} {}
{n \in \N_+} {}
{} {} {} {,}
eine
\zusatzklammer {surjektive, aber nicht notwendigerweise injektive} {} {}
Aufzählung der Aussagenvariablen. Die Voraussetzung bedeutet, dass
\mavergleichskette
{\vergleichskette
{ \Gamma_0
}
{ \defeq }{ \Gamma^\vdash
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
keinen Widerspruch enthält. Wir konstruieren eine
\zusatzklammer {endliche oder abzählbar unendliche} {} {}
Folge von aufsteigenden widerspruchsfreien Teilmengen
\mavergleichskette
{\vergleichskette
{\Gamma_n
}
{ \subseteq }{\Gamma_{n+1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei in $\Gamma_n$ für jede Variable
\mathbed {p_i} {}
{1 \leq i \leq n} {}
{} {} {} {,}
die Alternative entweder
\mavergleichskette
{\vergleichskette
{p_i
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{\neg p_i
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt. Das Konstruktionsverfahren definieren und diese Aussage beweisen wir durch Induktion über
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Für $\Gamma_0$ ist dies richtig. Es sei
\mathl{\Gamma_n}{} schon konstruiert. Bei
\mavergleichskette
{\vergleichskette
{p_{n+1}
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{\neg p_{n+1}
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
setzen wir
\mavergleichskettedisp
{\vergleichskette
{\Gamma_{n+1}
}
{ \defeq} { \Gamma_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wegen der Widerspruchsfreiheit von $\Gamma_n$ können nicht sowohl
\mathkor {} {p_{n+1}} {als auch} {\neg p_{n+1}} {}
zu $\Gamma_n$ gehören. Wenn weder
\mathl{p_{n+1}}{} noch
\mathl{\neg p_{n+1}}{} zu $\Gamma_n$ gehören, so setzen wir
\mavergleichskettedisp
{\vergleichskette
{\Gamma_{n+1}
}
{ \defeq} { { \left( \Gamma_n \cup {p_{n+1} } \right) }^\vdash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
\zusatzklammer {man könnte genauso gut
\mathl{\neg p_{n+1}}{} hinzunehmen} {} {.}
Nach Konstruktion ist
\mathl{\Gamma_{n+1}}{} abgeschlossen unter der Ableitungsbeziehung und erfüllt die
\zusatzklammer {Oder} {} {-}Alterna\-tive für alle Variablen
\mathbed {p_i} {}
{i \leq n +1} {}
{} {} {} {.}
Wenn
\mathl{\Gamma_{n+1}}{} widersprüchlich wäre, so gelte insbesondere
\mathl{\Gamma_n \cup \{ p_{n+1} \} \vdash \neg p_{n+1}}{.} Dann würde aber auch
\mathl{\Gamma_n \vdash p_{n+1} \rightarrow \neg p_{n+1}}{} gelten und somit nach der Fallunterscheidungsregel auch
\mathl{\Gamma_n \vdash \neg p_{n+1}}{,} also
\mavergleichskette
{\vergleichskette
{\neg p_{n+1}
}
{ \in }{\Gamma_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
im Widerspruch zu dem Fall, in dem wir uns befinden. Daher liegt für die Aussagenvariablen auch die Entweder-Oder-Alternative vor.
Mit dieser induktiven Definition setzen wir
\mavergleichskettedisp
{\vergleichskette
{\Gamma'
}
{ \defeq} { \bigcup_{n \in \N} \Gamma_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Menge $\Gamma'$ ist widerspruchsfrei, da andernfalls schon eines der $\Gamma_n$ einen Widerspruch enthalten würde, und auch abgeschlossen unter Ableitungen, da dies für die einzelnen $\Gamma_n$ gilt und eine Ableitung nur endlich viele Voraussetzungen besitzt. Ferner gilt für jedes
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Alternative
\mathkor {} {p_n \in \Gamma'} {oder} {\neg p_n \in \Gamma'} {.}
Damit sind die Voraussetzungen von
Lemma 4.7
erfüllt und $\Gamma'$ ist maximal widerspruchsfrei.
\inputbeispiel{}
{
Wir betrachten die Aussagenvariablenmenge
\mathl{\{p_1,p_2,p_3, \ldots \}}{} und die Ausdrucksmenge
\mavergleichskettedisp
{\vergleichskette
{\Gamma
}
{ =} {\{p_1 \rightarrow p_2,\, p_2 \rightarrow p_3,\, p_3 \rightarrow p_4,\, \ldots \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese wollen wir zu einer
\definitionsverweis {maximal widerspruchsfreien}{}{}
Menge gemäß
Lemma 4.9
ergänzen. Wenn wir im ersten Schritt $p_1$ hinzunehmen, so ergibt sich sukzessive
\mathl{p_i \in \Gamma_1}{} für alle
\mathl{i \in \N}{.} Es ist dann $\Gamma_1$ schon maximal widerspruchsfrei. Wählt man hingegen im ersten Schritt
\mathl{\neg p_1}{,} so gehört weder
\mathkor {} {p_2} {noch} {\neg p_2} {}
zu $\Gamma_1$. Beim zweiten Schritt hat man dann die Freiheit, ob man
\mathkor {} {p_2} {oder} {\neg p_2} {}
zur Definition von $\Gamma_2$ hinzunimmt, und so weiter.
}