Kurs:Einführung in die mathematische Logik (Osnabrück 2021)/Vorlesung 15/latex
\setcounter{section}{15}
\zwischenueberschrift{Auffüllungsstrategien}
Die weitere Strategie zum Beweis des Vollständigkeitssatzes ist nun, eine widerspruchsfreie Ausdrucksmenge zu einer maximal widerspruchsfreien Ausducksmenge, die Beispiele enthält, aufzufüllen, und so ein erfüllendes Modell mit Hilfe
des Satzes von Henkin
zu bekommen. Dabei betrachten wir zunächst das Problem, Beispiele hinzuzunehmen. Es sei $\Gamma$ eine widerspruchsfreie Ausdrucksmenge über dem Alphabet $S$. Zu jedem Ausdruck $\alpha$ müssen wir einen Ausdruck der Form
\mathl{\exists x \alpha \rightarrow \alpha \frac{t}{x}}{} mit einem gewissen Term $t$ hinzunehmen. Das Problem ist hierbei, dass bei ungeeigneter Wahl von $t$ die Hinzunahme dieses Ausdrucks $\Gamma$ widersprüchlich machen könnte. Es gibt keine Garantie, dass es überhaupt einen $S$-Term $t$ gibt, mit dem man $\Gamma$ widerspruchsfrei erweitern kann. Von daher wählt man eine andere Strategie, indem man simultan das Symbolalphabet erweitert und den hinzuzunehmenden Existenzausdruck mit einem neuen \anfuehrung{unbelasteten}{} Term ansetzt.
\inputfaktbeweis
{Logik/Vollständigkeitssatz/Auffüllung mit einem Beispiel/Neue Termvariable/Widerspruchsfreiheit/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ eine
\definitionsverweis {widerspruchsfreie}{}{}
Menge an
$S$-\definitionsverweis {Ausdrücken}{}{}
\zusatzklammer {über einem
\definitionsverweis {Symbolalphabet}{}{}
$S$} {} {.}}
\faktfolgerung {Es sei $z$ ein weiteres Variablensymbol, das nicht zu $S$ gehört, und sei $\alpha$ ein $S$-Ausdruck. Dann ergibt die Hinzunahme von
\mathl{\exists x \alpha \rightarrow \alpha \frac{z}{x}}{} zu $\Gamma$ eine ebenfalls widerspruchsfreie Ausdrucksmenge
\zusatzklammer {über dem Symbolalphabet
\mavergleichskettek
{\vergleichskettek
{ S'
}
{ = }{ S \cup \{z\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {.}}
\faktzusatz {}
\faktzusatz {}
}
{
Nehmen wir an, dass
\mavergleichskette
{\vergleichskette
{ \Gamma'
}
{ = }{ \Gamma \cup \{\exists x \alpha \rightarrow \alpha { \frac{ z }{ x } } \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
widersprüchlich ist. Dann kann man aus $\Gamma'$ jeden Ausdruck ableiten. Es gilt also
\mathdisp {\Gamma' \vdash \psi} { }
und damit
\mathdisp {\Gamma \vdash { \left( \exists x \alpha \rightarrow \alpha \frac{z}{x} \right) } \rightarrow \psi} { }
für jeden Ausdruck $\psi$. Es gilt also insbesondere
\mathdisp {\Gamma \vdash \neg \exists x \alpha \rightarrow \psi} { }
und
\mathdisp {\Gamma \vdash \alpha \frac{z}{x} \rightarrow \psi} { . }
Wir nehmen nun zusätzlich an, dass $z$ in $\psi$ nicht vorkommt. Da $z$ überhaupt nicht in den anderen Ausdrücken vorkommt, können wir mittels
Axiom 11.2
\zusatzklammer {genauer wegen der in
Aufgabe 11.22
besprochenen Variante} {} {}
auf
\mathdisp {\Gamma \vdash \exists x \alpha \rightarrow \psi} { . }
schließen. Damit ergibt sich mit der Fallunterscheidungsregel
\mathdisp {\Gamma \vdash \psi} { , }
im Widerspruch zur Widerspruchsfreiheit von $\Gamma$.
\inputfaktbeweis
{Logik/Vollständigkeitssatz/Auffüllung mit Beispielen/Einzelschritt/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ eine
\definitionsverweis {widerspruchsfreie}{}{}
Menge an
$S$-\definitionsverweis {Ausdrücken}{}{}
\zusatzklammer {über einem
\definitionsverweis {Symbolalphabet}{}{}
$S$} {} {.}}
\faktfolgerung {Dann gibt es eine Symbolerweiterung
\mavergleichskette
{\vergleichskette
{ S^*
}
{ \supseteq }{ S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und eine widerspruchsfreie $S^*$-Ausdrucksmenge
\mavergleichskette
{\vergleichskette
{ \Gamma^*
}
{ \supseteq }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart, dass es zu jedem Ausdruck
\mavergleichskette
{\vergleichskette
{ \exists x \alpha
}
{ \in }{L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen Term $t$
\zusatzklammer {über $S^*$} {} {}
derart gibt, dass
\mavergleichskettedisp
{\vergleichskette
{ \exists x \alpha \rightarrow \alpha \frac{t}{x}
}
{ \in} {\Gamma^*
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.}
\faktzusatz {}
\faktzusatz {}
}
{
Die Menge $S^*$ definieren wir als
\definitionsverweis {disjunkte Vereinigung}{}{}
\mavergleichskettedisp
{\vergleichskette
{ S^*
}
{ =} { S \cup V
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei $V$ eine Variablenmenge ist, die für jeden Ausdruck der Form
\mavergleichskette
{\vergleichskette
{ \exists x \alpha
}
{ \in }{L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
genau eine
\zusatzklammer {neue} {} {}
Variable enthält, die wir mit
\mathl{y_{\exists x \alpha }}{} bezeichnen. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ \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
\mavergleichskette
{\vergleichskette
{ \Gamma
}
{ \subseteq }{ \Gamma^*
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und $\Gamma^*$ enthält $S$-Beispiele. Es bleibt also die Widerspruchsfreiheit zu zeigen. Wäre $\Gamma^*$ widerspruchsvoll, so wäre auch eine endliche Teilmenge davon widerspruchsvoll und insbesondere würde es Ausdrücke
\mavergleichskette
{\vergleichskette
{ \alpha_1 , \ldots , \alpha_n
}
{ \in }{ L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart geben, dass
\mathdisp {\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
\zusatzklammer {dabei können die $x_i$ gleich oder verschieden sein} {} {.}
Da bei jeder Hinzunahme eine neue Variable
\mathl{y_{\exists x_n \alpha_n }}{} verwendet wird, können wir induktiv
Lemma 15.1
anwenden und erhalten die Widersprüchlichkeit von $\Gamma$.
\inputfaktbeweis
{Logik/Vollständigkeitssatz/Auffüllung mit Beispielen/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ eine
\definitionsverweis {widerspruchsfreie}{}{}
Menge an
$S$-\definitionsverweis {Ausdrücken}{}{}
\zusatzklammer {über einem
\definitionsverweis {Symbolalphabet}{}{}
$S$} {} {.}}
\faktfolgerung {Dann gibt es eine aufsteigende Folge von Symbolmengen
\mathdisp {S_n \subseteq S_{n+1} \text{ mit } S_0=S} { }
und eine Folge von aufsteigenden
$S_n$-\definitionsverweis {Ausdrucksmengen}{}{}
\mathdisp {\Gamma_n \subseteq \Gamma_{n+1} \text{ mit } \Gamma_0= \Gamma} { }
derart, dass zum Symbolalphabet
\mavergleichskette
{\vergleichskette
{ S'
}
{ = }{\bigcup_{n \in \N} S_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die $S'$-Ausdrucksmenge
\mavergleichskettedisp
{\vergleichskette
{\Gamma'
}
{ =} { \bigcup_{n \in \N} \Gamma_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
widerspruchsfrei ist und Beispiele enthält.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir konstruieren die Folgen
\mathkor {} {S_n} {und} {\Gamma_n} {}
sukzessive mit der in
Lemma 15.2
beschriebenen Methode durch
\mavergleichskettedisp
{\vergleichskette
{S_{n+1}
}
{ =} {(S_n)^*
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{\Gamma_{n+1}
}
{ =} {(\Gamma_n)^*
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wäre $\Gamma'$ widersprüchlich, so würde sich schon aus einer endlichen Teilmenge ein Widerspruch ergeben. Dann wäre schon eines der $\Gamma_n$ widersprüchlich im Widerspruch zu
Lemma 15.2.
Wir wenden uns nun dem Problem zu, wie man eine widerspruchsfreie Ausdrucksmenge zu einer maximal widerspruchsfreien Menge ergänzen kann. Wie im entsprechenden Beweis der Aussagenlogik verwenden wir das Lemma von Zorn, wobei wir im abzählbaren Fall noch eine Beweisvariante angeben, die ohne das Lemma von Zorn auskommt.
\inputfaktbeweis
{Logik/Vollständigkeitssatz/Maximalisierung/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ eine
\definitionsverweis {widerspruchsfreie}{}{}
Menge an
$S$-\definitionsverweis {Ausdrücken}{}{}
\zusatzklammer {über einem
\definitionsverweis {Symbolalphabet}{}{}
$S$} {} {.}}
\faktfolgerung {Dann gibt es eine maximal widerspruchsfreie $S$-Menge $\Gamma'$ mit
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{\Gamma'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wie betrachten die Menge
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{M
}
{ =} { { \left\{ \Delta \mid \Gamma \subseteq \Delta \subseteq L^S , \, \Delta \text{ widerspruchsfreie Ausdrucksmenge} \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
aller widerspruchsfreien $S$-Ausdrucksmengen oberhalb von $\Gamma$. Es ist
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{ N
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine nichtleere total geordnete Teilmenge. Die Vereinigung
\mavergleichskette
{\vergleichskette
{ \Delta'
}
{ = }{\bigcup_{\Delta \in N} \Delta
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist ebenfalls eine $S$-Ausdrucksmenge, die $\Gamma$ umfasst. Sie ist auch widerspruchsfrei. Würde nämlich
\mathl{\Delta' \vdash \neg \alpha \wedge \alpha}{} gelten, so könnte man schon aus einer endlichen Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\Delta'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen Widerspruch ableiten. Die Elemente aus $T$ liegen jeweils in je einem
\mavergleichskette
{\vergleichskette
{ \Delta
}
{ \in }{ N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
und da diese eine Kette bilden, gibt es auch ein $\tilde{\Delta}$ mit
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\tilde{\Delta}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
also wäre $\tilde{\Delta}$ widersprüchlich. Somit sind die Voraussetzungen im
Lemma von Zorn
erfüllt und daher gibt es eine maximale Menge $\Gamma'$ in $M$. Diese ist offenbar
\definitionsverweis {maximal widerspruchsfrei}{}{.}
Wir besprechen eine Variante der vorstehenden Auffüllung für den Fall eines abzählbaren Symbolalphabets, die das Lemma von Zorn vermeidet und im Wesentlichen
\zusatzklammer {siehe die Einschränkung weiter unten} {} {}
konstruktiv ist. Man beachte, dass die oben durchgeführte Aufnahme von Beispielen bei einem abzählbaren Ausgangs\-alphabet wieder abzählbare Symbolalphabete liefert und dies auch bei der abzählbaren Wiederholung dieses Prozesses wie in
Lemma 15.3
der Fall ist.
\inputfaktbeweis
{Logik/Vollständigkeitssatz/Maximalisierung/Abzählbarer Fall/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $\Gamma$ eine
\definitionsverweis {widerspruchsfreie}{}{}
Menge an
$S$-\definitionsverweis {Ausdrücken}{}{}
über einem
\definitionsverweis {abzählbaren}{}{}
\definitionsverweis {Symbolalphabet}{}{}
$S$.}
\faktfolgerung {Dann gibt es eine maximal wider\-spruchsfreie $S$-Menge $\Gamma'$ mit
\mavergleichskette
{\vergleichskette
{ \Gamma
}
{ \subseteq }{ \Gamma'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die man durch sukzessive Hinzunahme von einzelnen Ausdrücken erhalten kann.}
\faktzusatz {}
\faktzusatz {}
}
{
Da $S$ abzählbar ist, ist auch $L^S$ abzählbar. Es sei
\mathbed {\alpha_n} {}
{n \in \N} {}
{} {} {} {,}
eine Abzählung sämtlicher Ausdrücke aus $L^S$. Wir definieren induktiv eine aufsteigende Folge $\Gamma_n$ von Ausdrucksmengen durch
\mavergleichskette
{\vergleichskette
{\Gamma_0
}
{ = }{\Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{\Gamma_{n+1}
}
{ =} { \begin{cases} \Gamma_n \cup \{ \alpha_{n+1} \},\, \text{ falls dies widerspruchsfrei ist}\, , \\ \Gamma_n \text{ sonst}\, .\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ \Gamma'
}
{ =} { \bigcup_{n \in \N} \Gamma_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Menge ist widerspruchsfrei, da andernfalls schon eines der $\Gamma_n$ widersprüchlich wäre, was aufgrund der induktiven Definition nicht der Fall ist. Um zu zeigen, dass $\Gamma'$ maximal widerspruchsfrei ist, sei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \notin }{ \Gamma'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Da $\alpha$ in der Abzählung der Ausdrücke vorkommt, ist
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ \alpha_n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für ein gewisses $n$. Im $n$-ten Konstruktionsschritt wurde $\alpha_n$ nicht hinzugenommen, sonst wäre
\mavergleichskette
{\vergleichskette
{ \alpha_n
}
{ \in }{\Gamma_n
}
{ \subseteq }{ \Gamma'
}
{ }{
}
{ }{
}
}
{}{}{.}
Also ist
\mathl{\Gamma_{n-1} \cup \{ \alpha_n\}}{} widersprüchlich und damit ist auch
\mathl{\Gamma' \cup \{ \alpha \}}{} widersprüchlich.
Die vorstehende Variante sieht auf den ersten Blick konstruktiver aus, als sie ist. Das Problem ist die Entscheidung, ob
\mathl{\Gamma_n \cup \{ \alpha_{n+1} \}}{} widerspruchsfrei ist. Dafür gibt es
\zusatzklammer {anders als bei der Aussagenlogik} {} {}
kein algorithmisches Verfahren, siehe beispielsweise
Satz 21.2.
\zwischenueberschrift{Der Vollständigkeitssatz}
Die folgende Aussage ist der \stichwort {Vollständigkeitssatz} {.}
\inputfaktbeweis
{Prädikatenlogik/Vollständigkeitssatz/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{,}
$\Gamma$ eine Menge an
$S$-\definitionsverweis {Ausdrücken}{}{}
und $\alpha$ ein weiterer $S$-Ausdruck.}
\faktfolgerung {Dann gilt
\mathl{\Gamma \vDash \alpha}{} genau dann, wenn
\mathl{\Gamma \vdash \alpha}{} gilt.}
\faktzusatz {}
\faktzusatz {}
}
{
Die Richtung von rechts nach links ist der
Korrektheitssatz.
Es sei umgekehrt
\mathl{\Gamma \not \vdash \alpha}{.} Um zu zeigen, dass auch
\mathl{\Gamma \not\vDash \alpha}{} gilt, müssen wir ein Modell angeben, das $\Gamma$ erfüllt, aber nicht $\alpha$. Die Nichtableitbarkeit
\mathl{\Gamma \not \vdash \alpha}{} bedeutet, dass
\mathl{\Gamma \cup \{\neg \alpha \}}{}
\definitionsverweis {widerspruchsfrei}{}{}
ist, und wir müssen zeigen, dass
\mathl{\Gamma \cup \{\neg \alpha \}}{}
\definitionsverweis {erfüllbar}{}{}
ist. Nach
Lemma 15.3
gibt es eine widerspruchsfreie Erweiterung
\mavergleichskette
{\vergleichskette
{S
}
{ \subseteq }{S'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
des Symbolalphabets und eine Erweiterung $\Gamma'$ von
\mathl{\Gamma \cup \{\neg \alpha\}}{,} die
\definitionsverweis {Beispiele enthält}{}{.}
Nach
Lemma 15.4
gibt es eine
\definitionsverweis {maximal widerspruchsfreie}{}{}
$S'$-Ausdrucksmenge
\mavergleichskette
{\vergleichskette
{ \Gamma^{\prime \prime}
}
{ \supseteq }{ \Gamma'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Diese enthält mit $\Gamma'$ ebenfalls Beispiele. Nach dem
Satz von Henkin
gibt es eine
$S'$-\definitionsverweis {Interpretation}{}{,}
die
\mathl{\Gamma^{\prime \prime}}{} erfüllt. Diese Interpretation erfüllt erst recht
\mathl{\Gamma \cup \{\neg \alpha \}}{.}
Für Tautologien ergibt sich der folgende Spezialfall.
\inputfaktbeweis
{Prädikatenlogik/Vollständigkeitssatz/Tautologieversion/Fakt}
{Korollar}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein $S$-Ausdruck.}
\faktfolgerung {Dann ist $\alpha$ genau dann eine
\definitionsverweis {ableitbare Tautologie}{}{,}
wenn $\alpha$
\definitionsverweis {allgemeingültig}{}{}
ist.}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt aus
Satz 15.6
mit
\mavergleichskettedisp
{\vergleichskette
{\Gamma
}
{ =} {\emptyset
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
{Prädikatenlogik/Vollständigkeitssatz/Erfüllbar und widerspruchsfrei/Fakt}
{Korollar}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $\Gamma$ eine Menge an
$S$-\definitionsverweis {Ausdrücken}{}{.}}
\faktfolgerung {Dann ist $\Gamma$ genau dann
\definitionsverweis {widerspruchsfrei}{}{,}
wenn $\Gamma$
\definitionsverweis {erfüllbar}{}{}
ist.}
\faktzusatz {}
\faktzusatz {}
{In dieser Form haben wir den Vollständigkeitssatz bewiesen. Diese Aussage ergibt sich aber auch als Spezialfall von Satz 15.6, wenn man für $\alpha$ eine widersprüchliche Aussage ansetzt.}
Das folgende Korollar, der sogenannte \stichwort {Endlichkeitssatz} {,} demonstriert, dass der Vollständigkeitssatz keineswegs selbstverständlich ist. Es sei eine Folgerungsbeziehung
\mathl{\Gamma \vDash \alpha}{} bewiesen, also gezeigt, dass jede Interpretation, die $\Gamma$ erfüllt, auch $\alpha$ erfüllen muss. Dabei sei $\Gamma$ unendlich, man denke etwa an ein unendliches Axiomenschema, wie es im Induktionsschema der erststufigen Peano-Arithmetik vorliegt. Ist es vorstellbar, dass in einem Beweis irgendwie auf all diese unendlich vielen Voraussetzungen Bezug genommen wird?
\inputfaktbeweis
{Prädikatenlogik/Endlichkeitssatz/Fakt}
{Korollar}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{,}
$\Gamma$ eine Menge an
$S$-\definitionsverweis {Ausdrücken}{}{} und $\alpha$ ein weiterer $S$-Ausdruck.}
\faktfolgerung {Dann gilt
\mathl{\Gamma \vDash \alpha}{} genau dann, wenn es eine endliche Teilmenge
\mavergleichskette
{\vergleichskette
{ \Gamma_e
}
{ \subseteq }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt mit
\mathl{\Gamma_e \vDash \alpha}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt direkt aus Satz 15.6, da die Endlichkeitsbeziehung für das \definitionsverweis {Ableiten}{}{} nach Definition gilt.
\inputfaktbeweis
{Prädikatenlogik/Endlichkeitssatz für Erfüllbarkeit/Fakt}
{Korollar}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $\Gamma$ eine Menge an
$S$-\definitionsverweis {Ausdrücken}{}{.}}
\faktvoraussetzung {Es sei jede endliche Teilmenge
\mavergleichskette
{\vergleichskette
{ \Gamma_e
}
{ \subseteq }{ \Gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionsverweis {erfüllbar}{}{.}}
\faktfolgerung {Dann ist $\Gamma$ erfüllbar.}
\faktzusatz {}
\faktzusatz {}
}
{
Dies folgt aus Korollar 15.8. Für die Widerspruchsfreiheit ist die Aussage klar, da eine Ableitung eines Widerspruchs nur Bezug auf endlich viele Voraussetzungen nimmt.
Als ein weiteres Korollar zum Vollständigkeitssatz führen wir die Existenz von Peano-Halbringen an, die nicht archimedisch geordnet sind und daher nicht isomorph zum Standardmodell $\N$ sind. Die erststufigen Peano-Axiome charakterisieren also nicht die natürlichen Zahlen.
\inputfaktbeweis
{Peano-Halbring/Nichtarchimedische Modelle/Existenz/Fakt}
{Korollar}
{}
{
\faktsituation {}
\faktfolgerung {Es gibt
\definitionsverweis {Peano-Halbringe}{}{,}
die nicht zu $\N$ isomorph sind, also nicht die
\definitionsverweis {zweitstufigen Dedekind-Peano-Axiome}{}{}
erfüllen.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $\Gamma$ die Menge der aus den erststufigen Peano-Axiomen ableitbaren Ausdrücke. Wir betrachten die Ausdrücke
\mathl{\alpha_n}{} mit
\mavergleichskettedisp
{\vergleichskette
{ \alpha_n
}
{ =} { \neg { \left( x = 1+1 + \cdots + 1 \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei rechts die $n$-fache formale Summe der $1$ mit sich selbst steht. Es sei
\mavergleichskettedisp
{\vergleichskette
{\Delta
}
{ =} { { \left( \Gamma \cup \bigcup_{n \in \N} \{ \alpha_n \} \right) }^\vdash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Menge ist widerspruchsfrei, da jede endliche Teilmenge davon widerspruchsfrei ist, da sie in $\N$ mit einer hinreichend großen Belegung für $x$ erfüllbar ist. Nach
Korollar 15.10
ist also auch $\Delta$ erfüllbar, und es sei $M$ ein erfüllendes Modell. Es gibt dann in $M$ ein Element
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wodurch $x$ belegt wird. Dieses $m$ ist dann von allen natürlichen Zahlen, die in $M$ natürlicherweise eingebettet sind, verschieden, und somit ist
\mavergleichskette
{\vergleichskette
{M
}
{ \neq }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}