Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 17/latex
\setcounter{section}{17}
\zwischenueberschrift{Isomorphie und elementare Äquivalenz im endlichen Fall}
Wir möchten zeigen, dass bei endlichen Mengen die elementare Äquivalenz den Isomorphietyp bereits festlegt. Wir besprechen zunächst einige typische Beispiele, die als Orientierung für den komplexen Beweis dienen sollen.
\inputbeispiel{}
{
Es sei $S$ ein Symbolalphabet, das ausschließlich aus \zusatzklammer {abzählbar unendlich vielen} {} {} Variablen bestehe. Zwei endliche $S$-Mengen \mathkor {} {M} {und} {N} {} sind genau dann elementar äquivalent, wenn sie die gleiche Anzahl an Elementen haben, denn die Elementanzahl kann man durch einen erststufigen Ausdruck aus $L^S$ ausdrücken. In diesem Fall gibt es eine Bijektion zwischen \mathkor {} {M} {und} {N} {} und diese ist ein $S$-\definitionsverweis {Isomorphismus}{}{.}
}
\inputbeispiel{}
{
Das
\definitionsverweis {Symbolalphabet}{}{}
$S$ bestehe
\zusatzklammer {neben Variablen} {} {}
aus einem einstelligen Funktionssymbol $f$. Die Ausdrucksmenge $\Gamma$ bestehe aus einem Satz, der inhaltlich besagt, dass eine erfüllende Menge genau $n$ Elemente besitzen muss, und einen Satz, der besagt, dass die Funktion
\definitionsverweis {bijektiv}{}{}
ist. Ein Modell für $\Gamma$ ist also eine $n$-elementige Menge $M$ zusammen mit einer fixierten
\definitionsverweis {Permutation}{}{}
\maabbdisp {f^M} {M} {M
} {}
auf dieser Menge. Eine Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
der Form
\zusatzklammer {wir schreiben $f$ statt $f^M$} {} {}
\mavergleichskettedisp
{\vergleichskette
{T
}
{ =} { \{ m, f(m), f^2(m) , \ldots , f^{k-1} (m) \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ f^k(m)
}
{ = }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und mit
\mavergleichskette
{\vergleichskette
{ f^{i}(m)
}
{ \neq }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mathbed {i} {}
{1 \leq i \leq k-1} {}
{} {} {} {,}
nennt man Zykel zu $f$ der Länge $k$. Die Menge $M$ ist die
\definitionsverweis {disjunkte Vereinigung}{}{}
von Zykeln unterschiedlicher Länge. Zwei Elemente
\mavergleichskette
{\vergleichskette
{ m,n
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind genau dann elementar äquivalent, wenn sie beide in einem gleichlangen
\zusatzklammer {aber nicht unbedingt im gleichen} {} {}
Zykel liegen: Einerseits lässt sich die Zykellänge $k$ erststufig formalisieren, etwa durch
\mathdisp {f^kx=x \wedge f^{k-1}x \neq x \wedge \ldots \wedge fx \neq x} { , }
wobei die Potenzen ausgeschrieben werden müssen. Andererseits kann man einfach Automorphismen angeben, indem man aus jedem Zykel $Z_j$ ein Element $m_j$ auswählt und dieses auf ein beliebiges Element
\mavergleichskette
{\vergleichskette
{ n_j
}
{ = }{ \psi(m_j)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eines Zykels gleicher Länge schickt, wobei jeder Zykel genau einmal getroffen wird. Durch
\mavergleichskettedisp
{\vergleichskette
{ \psi(f^i(m_j))
}
{ \defeq} {f^i( \psi(m_j))
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
erhält man einen wohldefinierten Automorphismus. Insbesondere kann man einen Automorphismus konstruieren, der $m$ auf $n$ abbildet. Wenn man $m$ auf $n$
\zusatzklammer {elementar äquivalent zu $m$} {} {}
abbilden möchte, so ist dadurch schon bestimmt, wohin man die Elemente aus dem Zyklel zu $m$ abbilden muss. Es muss nämlich
\mavergleichskette
{\vergleichskette
{ \psi(f(m))
}
{ = }{ f (\psi(m))
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{ \psi(f(f(m)))
}
{ = }{ f(f (\psi(m)))
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
u.s.w. gelten.
}
\inputbeispiel{}
{
Wir betrachten das
\definitionsverweis {Symbolalphabet}{}{}
$S$, das neben Variablen aus einer Konstanten $0$ und einem zweistelligen Funktionssymbol $+$ besteht. Wir betrachten die Gruppe
\mathl{\Z/(8)}{} mit der natürlichen
$S$-\definitionsverweis {Struktur}{}{.}
Die
\definitionsverweis {elementaren Äquivalenzklassen}{}{}
sind durch die Ordnung der Elemente gegeben. Die Klassen sind
\mathdisp {\{ \{0\} ,\, \{ 4\},\, \{2,6\}, \{1,3,5,7\} \}} { . }
Bei einen
$S$-\definitionsverweis {Automorphismus}{}{}
auf $\Z/(8)$ müssen die einelementigen Klassen auf sich selbst abgebildet werden, bei den anderen hat man gewisse Freiheiten. Allerdings gibt es Abhängigkeiten zwischen den Wahlmöglichkeiten auf den größeren Klassen. Wenn man $2$ auf $6$ abbilden möchte, so muss man zunächst $6$ auf $2$ abbilden. Wenn man diese partielle Abbildung
\maabbdisp {} {\{0,2,4,6\}} { \{0,1,2,3,4,5,6,7,8\}
} {}
fortsetzen möchte, so muss man beispielsweise $3$ wegen
\mathl{3+3=6 \mapsto 2}{} auf $1$ oder auf $5$ abbilden, die Werte $3$ oder $7$ sind ausgeschlossen.
}
\inputbeispiel{}
{
Es sei $S$ ein
\definitionsverweis {Symbolalphabet}{}{}
und $M$ eine $S$-Struktur mit der Eigenschaft, dass jede
\definitionsverweis {Äquivalenzklasse}{}{}
zur
\definitionsverweis {elementaren Äquivalenz}{}{}
einelementig sei. Wenn $N$ eine weitere, zu $M$ elementar äquivalente $S$-Struktur ist, so hat auch diese einelementige Äquivalenzklassen. Die einzige Möglichkeit für einen
$S$-\definitionsverweis {Isomorphismus}{}{}
\maabb {} {M} {N
} {}
ist dann, ein Element $m$ auf das einzige Element
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
abzubilden, das den entsprechenden charakteristischen Ausdruck erfüllt. Es muss dann allerdings begründet werden, dass es sich wirklich um einen Homomorphismus handelt.
}
Aus den Überlegungen der letzten Vorlesung erhalten wir das folgende Resultat. Im Beweis arbeiten wir mit folgender Definition.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{}
umd $M$ eine
$S$-\definitionsverweis {Struktur}{}{.}
Eine Teilmenge
\mavergleichskette
{\vergleichskette
{ T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
\definitionswort {funktional abgeschlossen}{}
\zusatzklammer {oder eine
\definitionswortpraemath {S}{ Unterstruktur }{}} {} {,}
wenn für jede Konstante
\mavergleichskette
{\vergleichskette
{c
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
das Element $c^M$ zu $T$ gehört und für jedes $k$-stellige Funktionssymbol $f$ und beliebige Elemente
\mavergleichskette
{\vergleichskette
{ m_1 , \ldots , m_k
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
auch
\mathl{f^M(m_1 , \ldots , m_k )}{} zu $T$ gehört.
}
Unter einem \stichwort {formal-zusammengesetzten Funktionssymbol} {}
\zusatzklammer {oder \stichwort {Funktionssymbolbaum} {}} {} {}
versteht man die Elemente der folgenden rekursiv festgelegten Menge
\zusatzklammer {innerhalb der Menge von Stammbäumen} {} {.}
\aufzaehlungzwei {Jedes Funktionssymbol
\zusatzklammer {einschließlich der Konstanten} {} {}
gehört dazu.
} {Wenn $f$ ein $k$-stelliges Funktionssymbol ist und
\mathl{F_1 , \ldots , F_k}{} formal-zusammengesetzte Funktionssymbole, so ist auch der Stammbaum
\zusatzklammer {nicht die Symbolkette} {} {}
\mathl{fF_1 \ldots F_k}{} ein formal-zusammengesetztes Funktionssymbol.
}
Bei einer Interpretation mit Grundmenge $M$ wird ein formal-zusammengesetztes Funktionssymbol $F$ als Hintereinanderschaltung der beteiligten Abbildungen interpretiert, wofür wir wieder $F^M$ schreiben. Eine funktional abgeschlossene Menge ist auch unter jeder formal-zusammengesetzten Funktion abgeschlossen, siehe
Aufgabe 17.8
und zu einer Startmenge
\mavergleichskette
{\vergleichskette
{U
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
besteht die kleinste funktional abgeschlossene Teilmenge, die $U$ enthält, genau aus den Werten der formal-zusammengesetzten Funktionen mit Argumenten aus $U$
\zusatzklammer {man nennt dies die \stichwort {funktionale Hülle} {} von $U$} {} {.}
Wenn man mit einem Element $m$ startet, und nur ein einstelliges Funktionssymbol zur Verfügugn hat, so besteht die funktionale Hülle einfach aus
\mathl{m,f(m),f(f(m)),f(f(f(m))), ...}{.}
\inputfaktbeweis
{Endliches Modell/Elementar äquivalent und isomorph/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $S$ ein Symbolalphabet und es seien
\mathkor {} {M} {und} {N} {}
$S$-\definitionsverweis {Strukturen}{}{,}
wobei $M$ endlich sei.}
\faktfolgerung {Dann sind
\mathkor {} {M} {und} {N} {}
genau dann
\definitionsverweis {elementar äquivalent}{}{,}
wenn sie zueinander isomorph sind.}
\faktzusatz {}
\faktzusatz {}
}
{
Dass eine Isomorphie elementare Äquivalenz impliziert, wurde in
Satz 16.7
bewiesen. Für die Umkehrung seien also die beiden Strukturen elementar äquivalent, und $M$ habe $r$ Elemente. Dann gilt in $M$ die Aussage
\mathdisp {\exists x_1 \exists x_2 \ldots \exists x_r { \left( x_1 \neq x_2 \wedge x_1 \neq x_3 \wedge \ldots \wedge x_1 \neq x_r \wedge x_2 \neq x_3 \wedge \ldots \wedge x_2 \neq x_r \wedge \ldots \wedge x_{r-1} \neq x_r \right) }} { }
und die entsprechende Aussage für
\mathl{r+1}{} gilt nicht. Aufgrund der elementaren Äquivalenz gilt diese Aussage
\zusatzklammer {bzw. die entsprechende Aussage} {} {}
auch
\zusatzklammer {nicht} {} {}
in $N$. D.h. $N$ ist ebenfalls endlich mit $r$ Elementen.
Wir konstruieren nun sukzessive Teilmengen
\mavergleichskette
{\vergleichskette
{ S_j
}
{ \subset }{ S_{j+1}
}
{ \subseteq }{ M
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei die $S_j$
\definitionsverweis {funktional abgeschlossen}{}{}
sind, und Abbildungen
\maabbdisp {\psi_j} {S_j} {N
} {}
mit
\mavergleichskette
{\vergleichskette
{ \psi_{j+1} {{|}}_{S_j}
}
{ = }{ \psi_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und derart, dass die $\psi_j$ für jedes $j$ Isomorphismen zwischen
\mathkor {} {S_j} {und} {T_j = \operatorname{bild} \psi_j} {}
sind.
Wir wählen
\mavergleichskette
{\vergleichskette
{m_1
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
beliebig und setzen $S_1$ als die kleinste, funktional abgeschlossene Teilmenge in $M$ an, die $m_1$ enthält. Nach
Lemma 16.11
gibt es einen Ausdruck $\alpha$ in einer freien Variablen, der die elementare Äquivalenzklasse
\mathl{[m_1]}{} beschreibt. Wir wählen ein Element
\mavergleichskette
{\vergleichskette
{n_1
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus der $\alpha$ entsprechenden Äquivalenzklasse in $N$
\zusatzklammer {und diese ist nicht leer wegen der elementaren Äquivalenz zwischen $M$ und $N$} {} {}
und setzen
\mavergleichskettedisp
{\vergleichskette
{ \psi_1(m_1)
}
{ \defeq} { n_1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Für jedes formal-zusammengesetzte Funktionssymbol $F$ definieren wir
\zusatzklammer {hierbei wird überall $m_1$ bzw. $n_1$ eingesetzt} {} {}
\mavergleichskettedisp
{\vergleichskette
{ \psi_1(F^M(m_1))
}
{ \defeq} { F^N (\psi_1( m_1))
}
{ =} { F^N (n_1)
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Abbildung ist wohldefiniert. Ist nämlich
\mavergleichskettedisp
{\vergleichskette
{m
}
{ =} {F^M(m_1)
}
{ =} {G^M(m_1)
}
{ } {
}
{ } {
}
}
{}{}{,}
so gilt in $M$
\mathdisp {\forall x { \left( \alpha \rightarrow F(x) = G(x) \right) }} { , }
da dies für $m_1$ gilt und daher auch für alle dazu elementar äquivalenten Elemente, und da für die dazu nicht elementar äquivalenten Elemente der Vordersatz nicht gilt. Diese Aussage gilt dann auch bei Interpretation über $N$. Daher ist
\mavergleichskettedisp
{\vergleichskette
{F^N (n_1)
}
{ =} {G^N (n_1)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir müssen zeigen, dass ein Homomorphismus vorliegt. Die Verträglichkeit mit den Funktionssymbolen folgt unmittelbar aus der Definition der Abbildung. Ferner wird jedes Element zu einem Element aus der entsprechenden Äquivalenzklasse abgebildet. Nach
\zusatzklammer {dem Beweis zu} {} {}
Lemma 16.14
und wegen der elementaren Äquivalenz berücksichtigt $\psi$ daher die Relationen. Dies gilt in beide Richtungen, d.h. eine Relation trifft auf ein Tupel genau dann zu, wenn dies auf das Bildtupel zutrifft. Die Abbildung ist injektiv: Zu zwei Elementen
\mavergleichskette
{\vergleichskette
{m,m'
}
{ \in }{S_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es zusammengesetzte Funktionssymbole
\mathkor {} {F} {und} {G} {}
mit
\mavergleichskette
{\vergleichskette
{m
}
{ = }{F^M (m_1)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{m'
}
{ = }{G^M (m_1)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
Bei
\mavergleichskette
{\vergleichskette
{m
}
{ \neq }{m'
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mathdisp {\vDash \forall x { \left( \alpha \rightarrow Fx \neq Gx \right) }} { , }
da dies bei Interpretation von $x$ durch $m_1$ gilt, und diese Aussage gilt auch in $N$. Die Abbildung ist surjektiv auf das Bild, also liegt wegen der Äquivalenz bei den Relationen insgesamt ein Isomorphismus vor.
Es seien nun $S_j$ und $\psi_j$ schon konstruiert und
\mavergleichskette
{\vergleichskette
{ S_j
}
{ \neq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir wählen
\mavergleichskette
{\vergleichskette
{ m_{j+1}
}
{ \in }{ M \setminus S_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und setzen
\mathl{S_{j+1}}{} als die funktionale Hülle von
\mathl{S_j \cup \{m_{j+1} \}}{} an. Wir betrachten die Menge aller Tupel
\mathl{( \beta,a_1 , \ldots , a_k)}{,} wobei
\mavergleichskette
{\vergleichskette
{ \beta
}
{ \in }{ L^S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Ausdruck in den freien Variablen $x_1 , \ldots , x_k$ und $y$ ist und wobei
\mavergleichskette
{\vergleichskette
{ a_1 , \ldots , a_k
}
{ \in }{ S_j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit der Eigenschaft, dass
\mathdisp {I { \frac{ a_1 , \ldots , a_k }{ x_1 , \ldots , x_k } } { \frac{ m_{j+1} }{ y } } \vDash \beta} { }
gilt. Dabei sei $I$ eine fixierte Interpretation auf $M$ und $J$ entsprechend eine Interpretation auf $N$. Es gilt dann insbesondere
\mathdisp {I { \frac{ a_1 , \ldots , a_k }{ x_1 , \ldots , x_k } } \vDash \exists y \beta} { . }
Daher gilt nach
Satz 16.7
\zusatzklammer {angewendet auf den Isomorphismus $\psi_j$ mit
\mavergleichskettek
{\vergleichskettek
{ b_i
}
{ = }{ \psi_j(a_i)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}} {} {}
auch
\mathdisp {J { \frac{ b_1 , \ldots , b_k }{ x_1 , \ldots , x_k } } \vDash \exists y \beta} { , }
und insbesondere gibt es ein
\zusatzklammer {zunächst von $\beta$ abhängiges} {} {}
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mathdisp {J { \frac{ b_1 , \ldots , b_k }{ x_1 , \ldots , x_k } } { \frac{ n }{ y } } \vDash \beta} { . }
Dann gibt es auch ein
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
das man für alle $\beta$ nehmen kann. Für jedes einzelne $\beta$ ist nämlich die erfüllende Elementmenge nicht leer, und wenn der Durchschnitt über alle $\beta$ leer wäre, dann schon für eine endliche Teilmenge und dann auch für die endliche Konjunktion darüber. Es sei
\mathl{n_{j+1}}{} ein solches Element. Wir setzen nun
\mavergleichskettedisp
{\vergleichskette
{\psi_{j+1}(m_{j+1})
}
{ \defeq} {n_{j+1}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und definieren
\mavergleichskettedisp
{\vergleichskette
{\psi_{j+1} (F^M ( a_1 , \ldots , a_k, m_{j+1} ) )
}
{ \defeq} {F^N ( b_1 , \ldots , b_k, n_{j+1} )
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für jedes $k+1$-stellige formal zusammengesetzte Funktionssymbol $F$. Die Wohldefiniertheit von
\mathl{\psi_{j+1}}{,} die Verträglichkeit mit den Funktionssymbolen und mit den Relationssymbolen
\zusatzklammer {in beide Richtungen} {} {}
sowie die Bijektivität und damit die Isomorphieeigenschaft folgt wie oben.
Da $M$ endlich ist, erhalten wir, wenn wir diesen Konstruktionsschritt iterieren, insgesamt eine injektive Abbildung \maabbdisp {\psi} {M} {N } {.} Da \mathkor {} {M} {und} {N} {} gleich viele Elemente besitzen, ist diese auch surjektiv und insgesamt erhalten wir einen Isomorphismus.
Das im Beweis beschriebene Verfahren zur Konsrtuktion eines Isomorphismus ist grundsätzlich konstruktiv.
\zwischenueberschrift{Nichtstandardmodelle}
\inputdefinition
{}
{
Es sei $M$ eine fixierte $S$-\definitionsverweis {Struktur}{}{} \zusatzklammer {das \definitionswort {Standardmodell}{}} {} {} über einem \definitionsverweis {Symbolalphabet}{}{} $S$. Dann nennt man eine weitere $S$-Struktur $M'$, die zu $M$ \definitionsverweis {elementar äquivalent}{}{,} aber nicht zu $M$ $S$-\definitionsverweis {isomorph}{}{} ist, ein \definitionswort {Nichtstandardmodell}{} von $M$.
}
\inputbemerkung
{}
{
So formuliert ist diese Definition für jedes Modell $M$ anwendbar. Man verwendet sie aber eigentlich nur dann, wenn ein wohlbestimmtes \anfuehrung{prominentes}{} Modell $M$ ausgezeichnet ist. Das Standardmodell ist dann in der Regel durch den Kontext festgelegt. Im zahlentheoretischen Kontext ist $\N$ das Standardmodell, die entsprechenden Nichtstandardmodelle heißen \stichwort {Nichtstandardmodelle der Arithmetik} {,} die Untersuchung solcher Modelle heißt \stichwort {Nichtstandardarithmetik} {.} Im analytschen Kontext sind die reellen Zahlen das Standardmodell, die entsprechenden Nichtstandardmodelle heißen \stichwort {Nichtstandardmodelle der reellen Zahlen} {;} man spricht von \stichwort {Nichtstandard\-analysis} {.}
}
Es ist keineswegs selbstverständlich, dass es Nichtstandardmodelle gibt. Dies ergibt sich, und zwar ganz allgemein für jede unendliche Struktur, aus einer Reihe von Überlegungen, die an den Vollständigkeitssatz anschließen. Ein wesentlicher Punkt ist dabei, dass man zwar die Unendlichkeit eines Modells durch ein erststufiges Axiomenschema beschreiben kann, nicht aber erststufig verschiedene Mächtigkeiten unterscheiden kann. Zu
\mathl{n\in \N}{} beschreibt die Aussage
\mavergleichskettedisp
{\vergleichskette
{ \alpha_n
}
{ =} { \exists x_1 \ldots \exists x_n { \left( \wedge_{i \neq j} (x_i \neq x_j) \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
dass es mindestens $n$ verschiedene Elemente gibt
\zusatzklammer {d.h. diese Aussage ist interpretiert in einem Modell $M$ genau dann richtig, wenn $M$ mindestens $n$ Elemente besitzt} {} {.}
Die Ausdrucksmenge
\mavergleichskettedisp
{\vergleichskette
{\Gamma_\infty
}
{ =} { { \left\{ \alpha_n \mid n \in \N \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
beschreibt daher die Unendlichkeit einer Menge. Aufgabe 15.16
zeigt, dass es Nichtstandardmodelle der Arithmetik gibt
\zusatzklammer {siehe auch
Korollar 15.11} {} {}
und
Aufgabe 15.15
zeigt
\zusatzklammer {das Argument werden wir gleich wiederholen} {} {,}
dass es abzählbare Modelle gibt, die zu den reellen Zahlen elementar äquivalent sind. Man spricht von reell-abgeschlossenen Körpern.
\zwischenueberschrift{Reell-abgeschlossene Körper}
\inputbeispiel{}
{
Die Symbolmenge $S$ bestehe aus
\mathl{0,1,+,\cdot}{}
\zusatzklammer {und abzählbar unendlich vielen Variablen} {} {,}
die in den reellen Zahlen $\R$ in natürlicher Weise interpretiert werden. Die Ausdrucksmenge
\mavergleichskettedisp
{\vergleichskette
{\Gamma
}
{ =} {\R^\vDash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist somit widerspruchsfrei. Der Beweis zu
Lemma 15.3
zeigt, dass es dann eine abzählbare Symbol\-erweiterung
\mavergleichskette
{\vergleichskette
{S'
}
{ \supseteq }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und eine $S'$-Ausdrucksmenge $\Gamma'$ gibt, die Beispiele enthält
\zusatzklammer {es ist nicht selbstverständlich, ob $\Gamma$ selbst Beispiele enthält. Da es überabzählbar viele reelle Zahl gibt, liegt nicht jede reelle Zahl im Bild der Terminterpretation, sodass man
Lemma 14.5
nicht anwenden kann} {} {,}
und die nach
Lemma 15.4
zu einer maximal widerspruchsfreien Ausdrucksmenge ergänzt werden kann. Nach dem
Satz von Henkin
gibt es ein erfüllendes Modell, das aus Identifizieren von Termen entsteht. Da die Termmenge abzählbar ist, ist auch dieses Modell abzählbar. Es gibt daher ein abzählbares
\definitionsverweis {Nichtstandardmodell}{}{}
der reellen Zahlen.
}
Die Menge der rationalen Zahlen bilden einen abzählbaren
\definitionsverweis {angeordneten Körper}{}{,}
aber kein Nichtstandardmodell der reellen Zahlen, da ja beispielsweise die Aussage
\mathl{\exists x (x^2=2)}{} in $\R$ gilt, aber nicht in $\Q$. Wichtige erststufige Aussagen, die in $\R$ und damit auch in jedem Nichtstandardmodell gelten, fassen wir in folgender Proposition zusammen.
\inputfaktbeweis
{Reelle Zahlen/Erststufige Aussagen/Fakt}
{Proposition}
{}
{
\faktsituation {Für die
\definitionsverweis {reellen Zahlen}{}{}}
\faktuebergang {gelten folgende Aussagen über dem Symbolalphabet\zusatzfussnote {Um die Lesbarkeit zu erhöhen benutzen wir auch andere Variablennamen} {.} {}
\mavergleichskette
{\vergleichskette
{S
}
{ = }{ \{0,1,+,\cdot ,x_n, n \in \N\}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}}
\faktfolgerung {\aufzaehlungfuenf{Die Axiome eines\zusatzfussnote {Die Beziehung
\mavergleichskette
{\vergleichskette
{u
}
{ \neq }{v
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
wird durch
\mathl{\exists t (t^2= u-v)}{} erklärt. Alternativ kann man die Symbolmenge um $\geq$ ergänzen} {.} {}
\definitionsverweis {angeordneten Körpers}{}{.}
}{Für jedes ungerade
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mathdisp {\forall c_0 \forall c_1 \ldots \forall c_n { \left( { \left( c_n \neq 0 \right) } \rightarrow \exists x { \left( c_nx^n +c_{n-1}x^{n-1} + \cdots + c_1x+c_0 = 0 \right) } \right) }} { . }
}{Für jedes gerade
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt
\mathdisp {\forall x { \left( \exists y { \left( { \left( y^n = x \right) } \vee { \left( y^n = -x \right) } \right) } \right) }} { . }
}{Für jeden $S$-Ausdruck $\alpha$ in einer freien Variablen $x$ gilt
\mathdisp {\exists x \alpha \wedge \exists b \forall x { \left( \alpha \rightarrow x \leq b \right) } \rightarrow \exists s { \left( \forall x { \left( \alpha \rightarrow x \leq s \right) } \wedge \forall c \forall x { \left( \alpha \rightarrow x \leq c \right) } \rightarrow s \leq c \right) }} { . }
}{Für jeden $S$-Ausdruck $\alpha$ in einer freien Variablen $x$ gilt
\mathdisp {{ \left( \exists x \alpha \wedge \exists x \neg \alpha \wedge \forall x \forall y { \left( x \leq y \rightarrow { \left( \alpha\frac{y}{x} \rightarrow \alpha \right) } \right) } \wedge \forall x \forall y { \left( y \leq x \rightarrow { \left( \neg \alpha \frac{y}{x} \rightarrow \neg \alpha \right) } \right) } \right) } \rightarrow \exists s { \left( \forall x { \left( \alpha \rightarrow x \leq s \right) } \wedge \forall x { \left( \neg \alpha \rightarrow x \geq s \right) } \right) }} { . }
}}
\faktzusatz {}
\faktzusatz {}
}
{
\teilbeweis {}{}{}
{(1) ist in der
\definitionsverweis {Axiomatik der reellen Zahlen}{}{}
enthalten.}
{}
\teilbeweis {}{}{}
{(2) folgt aus dem
Zwischenwertsatz,
der Stetigkeit von Polynomen und dem Verhalten von Polynomen von ungeradem Grad gegen
\mathl{\pm \infty}{.}}
{}
\teilbeweis {}{}{}
{(3) folgt aus wiederholter Anwendung von
Satz 7.4 (Analysis (Osnabrück 2014-2016))
und Teil (2).}
{}
\teilbeweis {}{}{}
{(4) ist eine Formulierung von
Satz 7.5 (Analysis (Osnabrück 2014-2016))
für solche Teilmengen, die in der ersten Stufe beschrieben werden können.}
{}
\teilbeweis {}{}{}
{(5) folgt aus dem Dedekindschen Schnittaxiom.}
{}
Diese Eigenschaften
\zusatzklammer {insbesondere die beiden letzten} {} {}
sind ein erststufiger Ersatz für die Vollständigkeit
\zusatzklammer {ähnlich wie das Axiomenschema der Induktion in den erststufigen Peano-Axiomen ein Ersatz für die zweitstufige Induktion der Dedekind-Peano Axiome ist} {} {.}
Das Archimedes-Axiom, also dass es zu jeder reellen Zahl
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{\R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine natürliche Zahl
\mavergleichskette
{\vergleichskette
{n
}
{ \geq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt, lässt sich nicht erststufig charakterisieren, da dies für die natürlichen Zahlen nicht möglich ist. Wir betrachten zu
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
den Ausdruck
\mavergleichskettedisp
{\vergleichskette
{p_n
}
{ =} { \exists x { \left( x \geq n \right) }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei $n$ durch die $n$-fache Addition der $1$ mit sich selbst repräsentiert wird. Eine Aussage wie \anfuehrung{
\mathl{\!\!\exists x \forall n (x \geq n)}{} }{,} was nichtarchimedisch bedeutet
\zusatzklammer {$n$ soll hier eine natürliche Zahl sein} {} {,}
ist nicht erststufig formulierbar.
\inputbeispiel{}
{
Die Symbolalphabet $S$ bestehe aus den Zeichen
\mathl{0,1,+,\cdot}{}
\zusatzklammer {und abzählbar unendlich vielen Variablen} {} {,}
die in den reellen Zahlen $\R$ in natürlicher Weise interpretiert werden. Die Ausdrucksmenge
\mavergleichskettedisp
{\vergleichskette
{\Gamma
}
{ =} {\R^\vDash
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist somit widerspruchsfrei. Wir betrachten für
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
den Ausdruck
\mavergleichskettedisp
{\vergleichskette
{ \beta_n
}
{ =} { x \geq n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es sei $\Gamma'$ die Vereinigung von $\Gamma$ mit
\mathl{{ \left\{ \beta_n \mid n \in \N \right\} }}{.} Jede endliche Teilmenge von $\Gamma'$ ist
\definitionsverweis {erfüllbar}{}{}
\zusatzklammer {nämlich in $\R$} {} {,}
also ist nach
Korollar 15.10
auch $\Gamma'$ erfüllbar. Es gibt also eine $S$-Struktur $M$, in der alle erststufigen Sätze von $\R$ gelten und auch alle
\mavergleichskette
{\vergleichskette
{x
}
{ \geq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
bei geeigneter Belegung gelten, d.h. es gibt ein Element
\mavergleichskette
{\vergleichskette
{ m
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
das jenseits jeder natürlichen Zahl liegt. Insbesondere ist $M$ ein nicht-archimedisch angeordneter Körper.
}
\inputdefinition
{}
{
Ein
\definitionsverweis {angeordneter Körper}{}{}
$K$ heißt
\definitionswort {reell-abgeschlossen}{,}
wenn folgende Eigenschaften gelten.
\aufzaehlungzwei {Jedes nichtnegative Element aus $K$ besitzt eine
\definitionsverweis {Quadratwurzel}{}{}
in $K$.
} {Jedes
\definitionsverweis {Polynom}{}{}
\mavergleichskette
{\vergleichskette
{P
}
{ \in }{ K[X]
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit ungeradem
\definitionsverweis {Grad}{}{}
besitzt in $K$ eine Nullstelle.
}
}
Man kann zeigen, dass ein reell-abgeschlossener Körper $K$ elementar äquivalent zu den reellen Zahlen ist und insbesondere die oben angeführten Eigenschaften besitzt. Eine wichtige Eigenschaft ist ferner, dass
\mathl{K[ { \mathrm i} ]}{} algebraisch abgeschlossen ist
\zusatzklammer {d.h. durch Hinzunahme eines Elementes ${ \mathrm i}$ mit
\mavergleichskette
{\vergleichskette
{ { \mathrm i}^2
}
{ = }{ -1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
wird der Körper algebraisch abgeschlossen} {} {.}
Ein
\zusatzklammer {abzählbares Modell} {} {}
eines reell-abgeschlossenen Körpers sind die reellen algebraischen Zahlen, also alle reellen Zahlen, die Nullstelle eines Polynoms mit rationalen Koeffizienten sind. Dies ist zugleich der kleinste reell-abgeschlossene Körper. Da die Zahlen $\pi$ und $e$ transzendent sind, folgt, dass diese Zahlen nicht erststufig charakterisierbar sind. Eine Besonderheit der Theorie der reell-abgeschlossenen Körper ist, dass es dafür eine Entscheidungsprozedur gibt, d.h. es gibt einen maschinell durchführbaren Algorithmus, die \stichwort {Quantorenelimination} {,} der für jeden Ausdruck $\alpha$ über der erststufigen Sprache zur Symbolmenge
\mathl{\{0,1,+,\cdot, \geq\}}{} entscheidet, ob $\alpha$ aus den Axiomen ableitbar ist
\zusatzklammer {äquivalent, in jedem reell-abgeschlossenen Körper gilt} {} {}
oder nicht. Es gibt also prinzipiell keine erststufig formulierbaren \anfuehrung{substantiellen Probleme}{} für die reellen Zahlen.