Kurs:Einführung in die mathematische Logik (Osnabrück 2014)/Vorlesung 15

 Nehmen wir an, dass${\displaystyle {}\Gamma '=\Gamma \cup \{\exists x\alpha \rightarrow \alpha {\frac {z}{x}}\}}$ widersprüchlich ist. Dann kann man aus ${\displaystyle {}\Gamma '}$ jeden Ausdruck ableiten. Es gilt also

${\displaystyle \Gamma '\vdash \psi }$

und damit

${\displaystyle \Gamma \vdash {\left(\exists x\alpha \rightarrow \alpha {\frac {z}{x}}\right)}\rightarrow \psi }$

für jeden Ausdruck ${\displaystyle {}\psi }$. Es gilt also insbesondere

${\displaystyle \Gamma \vdash \neg \exists x\alpha \rightarrow \psi }$

und

${\displaystyle \Gamma \vdash \alpha {\frac {z}{x}}\rightarrow \psi .}$

Wir nehmen nun zusätzlich an, dass ${\displaystyle {}z}$ in ${\displaystyle {}\psi }$ nicht vorkommt. Da ${\displaystyle {}z}$ überhaupt nicht in den anderen Ausdrücken vorkommt, können wir mittelsAxiom 11.1(genauer wegen der inAufgabe *****besprochenen Variante)auf

${\displaystyle \Gamma \vdash \exists x\alpha \rightarrow \psi .}$

schließen. Damit ergibt sich mit der Fallunterscheidungsregel

${\displaystyle \Gamma \vdash \psi ,}$

${\displaystyle {}\Gamma }$

Die Menge ${\displaystyle {}S^{*}}$ definieren wir alsdisjunkte Vereinigung

${\displaystyle {}S^{*}=S\cup V\,,}$

wobei ${\displaystyle {}V}$ eine Variablenmenge ist, die für jeden Ausdruck der Form${\displaystyle {}\exists x\alpha \in L^{S}}$genau eine(neue)Variable enthält, die wir mit ${\displaystyle {}y_{\exists x\alpha }}$ bezeichnen. Wir setzen

${\displaystyle {}\Gamma ^{*}=\Gamma \cup {\left\{\exists x\alpha \rightarrow \alpha {\frac {y_{\exists x\alpha }}{x}}\mid \exists x\alpha \in L^{S}\right\}}\,.}$

Daher ist${\displaystyle {}\Gamma \subseteq \Gamma ^{*}}$und ${\displaystyle {}\Gamma ^{*}}$ enthält ${\displaystyle {}S}$-Beispiele. Es bleibt also die Widerspruchsfreiheit zu zeigen. Wäre ${\displaystyle {}\Gamma ^{*}}$ widerspruchsvoll, so wäre auch eine endliche Teilmenge davon widerspruchsvoll und insbesondere würde es Ausdrücke${\displaystyle {}\alpha _{1},\ldots ,\alpha _{n}\in L^{S}}$derart geben, dass

${\displaystyle \Gamma \cup \{\exists x_{1}\alpha _{1}\rightarrow \alpha _{1}{\frac {y_{\exists x_{1}\alpha _{1}}}{x_{1}}}\}\cup \ldots \cup \{\exists x_{n}\alpha _{n}\rightarrow \alpha _{n}{\frac {y_{\exists x_{n}\alpha _{n}}}{x_{n}}}\}}$

widersprüchlich ist(dabei können die ${\displaystyle {}x_{i}}$ gleich oder verschieden sein).Da bei jeder Hinzunahme eine neue Variable ${\displaystyle {}y_{\exists x_{n}\alpha _{n}}}$ verwendet wird, können wir induktivLemma 15.1anwenden und erhalten die Widersprüchlichkeit von ${\displaystyle {}\Gamma }$.

Wir konstruieren die Folgen${\displaystyle {}S_{n}}$ und ${\displaystyle {}\Gamma _{n}}$sukzessive mit der inLemma 15.2beschriebenen Methode durch

${\displaystyle {}S_{n+1}=(S_{n})^{*}\,}$

und

${\displaystyle {}\Gamma _{n+1}=(\Gamma _{n})^{*}\,.}$

Wäre ${\displaystyle {}\Gamma '}$ widersprüchlich, so würde sich schon aus einer endlichen Teilmenge ein Widerspruch ergeben. Dann wäre schon eines der ${\displaystyle {}\Gamma _{n}}$ widersprüchlich im Widerspruch zuLemma 15.2.

Wie betrachten die Menge

${\displaystyle M={\left\{\Delta \mid \Gamma \subseteq \Delta \subseteq L^{S},\,\Delta {\text{ widerspruchsfreie Ausdrucksmenge}}\right\}}\,}$

aller widerspruchsfreien ${\displaystyle {}S}$-Ausdrucksmengen oberhalb von ${\displaystyle {}\Gamma }$. Es ist ${\displaystyle {}\Gamma \in M}$.Es sei${\displaystyle {}N\subseteq M}$eine nichtleere total geordnete Teilmenge. Die Vereinigung${\displaystyle {}\Delta '=\bigcup _{\Delta \in N}\Delta }$ist ebenfalls eine ${\displaystyle {}S}$-Ausdrucksmenge, die ${\displaystyle {}\Gamma }$ umfasst. Sie ist auch widerspruchsfrei. Würde nämlich ${\displaystyle {}\Delta '\vdash \neg \alpha \wedge \alpha }$ gelten, so könnte man schon aus einer endlichen Teilmenge${\displaystyle {}T\subseteq \Delta '}$einen Widerspruch ableiten. Die Elemente aus ${\displaystyle {}T}$ liegen jeweils in je einem${\displaystyle {}\Delta \in N}$,und da diese eine Kette bilden, gibt es auch ein ${\displaystyle {}{\tilde {\Delta }}}$ mit${\displaystyle {}T\subseteq {\tilde {\Delta }}}$,also wäre ${\displaystyle {}{\tilde {\Delta }}}$ widersprüchlich. Somit sind die Voraussetzungen im Lemma von Zornerfüllt und daher gibt es eine maximale Menge ${\displaystyle {}\Gamma '}$ in ${\displaystyle {}M}$. Diese ist offenbarmaximal widerspruchsfrei.

Da ${\displaystyle {}S}$ abzählbar ist, ist auch ${\displaystyle {}L^{S}}$ abzählbar. Es sei${\displaystyle {}\alpha _{n}}$, ${\displaystyle {}n\in \mathbb {N} }$, eine Abzählung sämtlicher Ausdrücke aus ${\displaystyle {}L^{S}}$. Wir definieren induktiv eine aufsteigende Folge ${\displaystyle {}\Gamma _{n}}$ von Ausdrucksmengen durch${\displaystyle {}\Gamma _{0}=\Gamma }$und

${\displaystyle {}\Gamma _{n+1}={\begin{cases}\Gamma _{n}\cup \{\alpha _{n+1}\},\,{\text{ falls dies widerspruchsfrei ist}}\,,\\\Gamma _{n}{\text{ sonst}}\,.\end{cases}}\,}$

Wir setzen

${\displaystyle {}\Gamma '=\bigcup _{n\in \mathbb {N} }\Gamma _{n}\,.}$

Diese Menge ist widerspruchsfrei, da andernfalls schon eines der ${\displaystyle {}\Gamma _{n}}$ widersprüchlich wäre, was aufgrund der induktiven Definition nicht der Fall ist. Um zu zeigen, dass ${\displaystyle {}\Gamma '}$ maximal widerspruchsfrei ist, sei${\displaystyle {}\alpha \notin \Gamma '}$.Da ${\displaystyle {}\alpha }$ in der Abzählung der Ausdrücke vorkommt, ist${\displaystyle {}\alpha =\alpha _{n}}$für ein gewisses ${\displaystyle {}n}$. Im ${\displaystyle {}n}$-ten Konstruktionsschritt wurde ${\displaystyle {}\alpha _{n}}$ nicht hinzugenommen, sonst wäre${\displaystyle {}\alpha _{n}\in \Gamma _{n}\subseteq \Gamma '}$.Also ist ${\displaystyle {}\Gamma _{n-1}\cup \{\alpha _{n}\}}$ widersprüchlich und damit ist auch ${\displaystyle {}\Gamma '\cup \{\alpha \}}$ widersprüchlich.

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

Dies folgt ausSatz 15.6mit

${\displaystyle {}\Gamma =\emptyset \,.}$

Dies folgt direkt ausSatz 15.6,da die Endlichkeitsbeziehung für das Ableiten nach Definition gilt.

Dies folgt ausFakt *****.Für die Widerspruchsfreiheit ist die Aussage klar, da eine Ableitung eines Widerspruchs nur Bezug auf endlich viele Voraussetzungen nimmt.