Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 5/latex
\setcounter{section}{5}
\zwischenueberschrift{Das Lemma von Zorn}
Wir möchten im Folgenden zeigen, dass eine widerpruchsfreie Menge
\mathl{\Gamma \subseteq L^V}{} von Aussagen nicht nur bei einer abzählbaren Aussagevariablenmenge $V$ zu einer maximal widerspruchsfreien Aussagenmenge aufgefüllt werden kann, sondern dass dies bei einer beliebigen Variablenmenge möglich ist. Bei einer Variablenmenge mit einer großen Mächtigkeit gibt es im Allgemeinen kein konstruktiv durchführbares Auffüllungsverfahren; es gibt lediglich Existenzaussagen, dass es solche maximal widerspruchsfreien Mengen geben muss. Diese Existenzaussagen beruhen auf stärkeren mengentheoretischen Konzepten, nämlich auf dem \stichwort {Auswahlaxiom} {} und dem \stichwort {Lemma von Zorn} {.}
\inputaxiom
{}
{
Es sei $I$ eine Menge und
\mathbed {M_i} {}
{i \in I} {}
{} {} {} {,}
eine Familie von nichtleeren Mengen $M_i$. Dann gibt es eine Abbildung
\maabbdisp {f} {I} { \bigcup_{i \in I} M_i
} {}
mit
\mavergleichskette
{\vergleichskette
{f(i)
}
{ \in }{ M_i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Das Auswahlaxiom ist intuitiv einleuchtend, da es lediglich die Existenz eines Tupels
\mathl{(f(i): i \in I)}{} garantiert, wobei es für jedes $i$ im Allgemeinen viele Kandidaten gibt. Da jedes $M_i$ nicht leer ist, gibt es zu einem festen $i$ mindestens ein
\mathl{f(i) \in M_i}{.} Der Inhalt des Auswahlaxiomes ist, dass man diese Elemente als Werte einer Abbildung realisieren kann. Die Abbildung wählt also in jeder der Mengen ein Element aus. Das Auswahlaxiom ist ein starkes Axiom mit teilweise überraschenden
\zusatzklammer {und manchmal kontraintuitiven} {?} {}
Konsequenzen.
Das Lemma von Zorn wird für geordnete Mengen formuliert. Wir erinnern an die relevanten Definitionen.
\inputdefinition
{}
{
Eine
\definitionsverweis {Relation}{}{}
$\preccurlyeq$ auf einer Menge $I$ heißt \definitionswort {Ordnungsrelation}{} oder \definitionswort {Ordnung}{,} wenn folgende drei Bedingungen erfüllt sind.
\aufzaehlungdrei{Es ist
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für alle
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt stets
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Aus
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt
\mavergleichskette
{\vergleichskette
{i
}
{ = }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
Diese Eigenschaften heißen \stichwort {Reflexivität} {,} \stichwort {Transitivität} {} und \stichwort {Antisymmetrie} {.} Eine Menge mit einer fixierten Ordnung heißt \stichwort {geordnete Menge} {.} Eine Ordnung heißt \stichwort {total} {}
\zusatzklammer {oder \stichwort {linear} {}} {} {,}
wenn
\mavergleichskette
{\vergleichskette
{i
}
{ \preccurlyeq }{j
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
oder
\mavergleichskette
{\vergleichskette
{j
}
{ \preccurlyeq }{i
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für je zwei Elemente
\mavergleichskette
{\vergleichskette
{i,j
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt. Die reellen Zahlen $\R$ sind mit der üblichen Ordnung $\leq$ total geordnet, die
\definitionsverweis {Potenzmenge}{}{}
\mathl{\mathfrak {P} \, (M )}{} zu einer Menge $M$ ist mit der Inklusion $\subseteq$ eine nicht total geordnete Menge. Die Menge der natürlichen Zahlen mit der Teilbarkeitsbeziehung als Ordnungsrelation ist ebenfalls nicht total geordnet.
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{.}
Ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {größtes Element}{} von $I$, wenn
\mavergleichskette
{\vergleichskette
{y
}
{ \preccurlyeq }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{.}
Ein Element
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {maximal}{}
\zusatzklammer {in $I$} {} {}
oder ein \definitionswort {maximales Element}{}
\zusatzklammer {von $I$} {} {,}
wenn es kein Element
\mathbed {y \in I} {}
{y \neq x} {}
{} {} {} {,}
mit
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt.
}
Bei einer total geordneten Menge fallen diese beiden Begriffe zusammen. Ein größtes Element ist, wenn es existiert, eindeutig bestimmt, maximale Elemente im Allgemeinen nicht.
\inputdefinition
{}
{
Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
und
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{ I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge. Ein Element
\mavergleichskette
{\vergleichskette
{s
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt \definitionswort {obere Schranke}{} für $J$, wenn
\mavergleichskette
{\vergleichskette
{ y
}
{ \preccurlyeq }{s
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
für jedes
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{J
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}
Die folgende Aussage heißt Lemma von Zorn.
{Lemma von Zorn/Obere Schranke/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei
\mathl{(I,\preccurlyeq)}{} eine
\definitionsverweis {geordnete Menge}{}{}
mit der Eigenschaft, dass jede
\definitionsverweis {total geordnete}{}{}
Teilmenge
\mavergleichskette
{\vergleichskette
{J
}
{ \subseteq }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {obere Schranke}{}{}
in $I$ besitzt.}
\faktfolgerung {Dann gibt es in $I$
\definitionsverweis {maximale Elemente}{}{.}}
\faktzusatz {}
\faktzusatz {}
{Diese Aussage kann man aus dem Auswahlaxiom herleiten; der Beweis ist aber ziemlich kompliziert und wenig erhellend, sodass wir auf ihn verzichten.}
Da die leere Menge total geordnet ist, kann insbesondere die Menge $I$ nicht leer sein. Dies wird manchmal in Formlierungen des Lemmas extra mitaufgeführt. Häufig nennt man die total geordneten Teilmengen auch \stichwort {Ketten} {.}
Eine geordnete Menge, die die Voraussetzung des Lemmas erfüllt, in der also jede Kette eine obere Schranke besitzt, heißt
\definitionsverweis {induktiv geordnet}{}{.}
Das Lemma von Zorn ist ein grundlegender mengentheoretischer Sachverhalt, der zum Auswahlaxiom äquivalent ist. Wir geben einige typische Beispiele, wie man mittels des Lemmas von Zorn die Existenz von gewissen mathematischen Objekten nachweisen kann.
\inputdefinition
{}
{
Eine Teilmenge ${\mathfrak a}$ eines
\definitionsverweis {kommutativen Ringes}{}{}
$R$ heißt \definitionswort {Ideal}{,} wenn die folgenden Bedingungen erfüllt sind:
\aufzaehlungdrei{
\mavergleichskette
{\vergleichskette
{0
}
{ \in }{ {\mathfrak a}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Für alle
\mavergleichskette
{\vergleichskette
{a,b
}
{ \in }{ {\mathfrak a}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist auch
\mavergleichskette
{\vergleichskette
{a+b
}
{ \in }{ {\mathfrak a}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Für alle
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{ {\mathfrak a}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{r
}
{ \in }{R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist auch
\mavergleichskette
{\vergleichskette
{ra
}
{ \in }{ {\mathfrak a}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
\inputdefinition
{}
{
Ein
\definitionsverweis {Ideal}{}{}
${\mathfrak m}$ in einem
\definitionsverweis {kommutativen Ring}{}{}
$R$ heißt \definitionswort {maximales Ideal}{,} wenn
\mavergleichskette
{\vergleichskette
{ {\mathfrak m}
}
{ \neq }{ R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist und wenn es zwischen ${\mathfrak m}$ und $R$ keine weiteren Ideale gibt.
}
\inputfaktbeweis
{Kommutativer Ring/Maximales Ideal/Existenz/Fakt}
{Lemma}
{}
{
\faktsituation {In einem
\definitionsverweis {kommutativen Ring}{}{}
\mavergleichskette
{\vergleichskette
{R
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}}
\faktfolgerung {gibt es
\definitionsverweis {maximale Ideale}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir betrachten die Menge
\mavergleichskettedisp
{\vergleichskette
{M
}
{ \defeq} {{ \left\{ I \subseteq R \mid 1 \not\in I , \, \text{Ideal in } R \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Menge enthält das Nullideal $0$ und ist somit nicht leer. Wir wollen das
Lemma von Zorn
auf $M$
\zusatzklammer {mit der Inklusion als Ordnungsrelation} {} {}
anwenden. Dazu sei
\mavergleichskette
{\vergleichskette
{N
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {total geordnete}{}{}
Teilmenge. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{I
}
{ \defeq} { \bigcup_{J \in N} J
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Man zeigt nun, dass $I$ ein Ideal ist, das nicht die $1$ enthält. Also gehört es zu $M$ und es bildet eine obere Schranke für $N$. Das Lemma von Zorn liefert dann maximale Elemente in $M$, und dies sind maximale Ideale.
Eine Variante dieser Aussage ist, dass jedes Ideal
\mavergleichskette
{\vergleichskette
{{\mathfrak a}
}
{ \subseteq }{ R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
das nicht die $1$ enthält, in einem maximalen Ideal enthalten ist. Für verhältnismäßig einfache Ringe kann man die Existenz maximaler Ideale auch ohne das Lemma von Zorn sichern. Das Lemma von Zorn etabliert aber auch in überraschenden Situationen die Existenz von maximalen Idealen, wie das folgende Beispiel zeigt.
\inputbeispiel{}
{
Wir betrachten die Menge
\mavergleichskettedisp
{\vergleichskette
{R
}
{ \defeq} { \R^\N
}
{ =} { { \left\{ { \left( x_n \right) }_{n \in \N } \mid \text{reelle Folge} \right\} }
}
{ } {
}
{ } {
}
}
{}{}{.}
Diese Menge ist mit komponentenweiser Addition und Multiplikation ein kommutativer Ring
\zusatzklammer {mit der konstanten Nullfolge bzw. Einsfolge als $0$ und $1$} {} {.}
Zu jedem festen
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist die Menge
\mavergleichskettedisp
{\vergleichskette
{I_k
}
{ =} { { \left\{ { \left( x_n \right) }_{n \in \N } \in R \mid x_k = 0 \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ein maximales Ideal. Die Idealeigenschaft kann man unmittelbar nachprüfen, die Maximalität ergibt sich daraus, dass ein größeres Ideal
\mavergleichskettedisp
{\vergleichskette
{I_k
}
{ \subset} {I
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ein Element
\mavergleichskette
{\vergleichskette
{y
}
{ = }{ { \left( y_n \right) }_{n \in \N }
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{y_k
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
enthält. Dann ist
\mavergleichskettedisp
{\vergleichskette
{ { \frac{ 1 }{ y_k } } y + { \left( 1 - { \frac{ 1 }{ y_k } } y \right) }
}
{ =} { 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ 1 - { \frac{ 1 }{ y_k } } y
}
{ \in }{ I_k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und daher ist
\mavergleichskette
{\vergleichskette
{1
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Mit dieser Konstruktion bekommt man also direkt maximale Ideale. Die
\definitionsverweis {Restklassenkörper}{}{}
zu diesen maximalen Idealen sind
\zusatzklammer {isomorph zu} {} {}
$\R$, der Restklassenhomomorphismus ist einfach die Projektion auf die $k$-te Komponente.
Wir betrachten nun das Ideal
\mavergleichskettedisp
{\vergleichskette
{ I
}
{ =} { { \left\{ { \left( x_n \right) }_{n \in \N } \mid x_n \neq 0 \text{ für endlich viele } n \in \N \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
das ist also die Menge aller Folgen, die bis auf endlich viele Glieder mit der Nullfolge übereinstimmen. Es gibt daher nach
\zusatzklammer {einer Variante von} {} {}
Lemma 5.9
maximale Ideale ${\mathfrak m}$ mit
\mavergleichskettedisp
{\vergleichskette
{I
}
{ \subseteq} { {\mathfrak m}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es ist
\mavergleichskettedisp
{\vergleichskette
{ {\mathfrak m}
}
{ \not\subseteq} { I_k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
da die Folge, die an der $k$-ten Stelle eine $1$ und sonst überall eine $0$ stehen hat, links dazu gehört, aber nicht rechts. Ein solches maximales Ideal kann man nicht explizit beschreiben. Selbst wenn man sich auf Folgen beschränkt, die lediglich die beiden Werte
\mathkor {} {0} {oder} {1} {}
annehmen, so ist kein explizites Verfahren bekannt, zu bestimmen, ob die Folge zu ${\mathfrak m}$ gehören soll oder nicht. Für jede Folge mit unendlich vielen Nullen und mit unendlich vielen Einsen gibt es ein solches maximales Ideal ${\mathfrak m}$, das diese Folge enthält, und auch eines, das sie nicht enthält.
Die Restklassenkörper zu einem solchen maximalen Ideal sind nicht isomorph zu $\R$. Die dabei auftretenden Körper sind vielmehr der Gegenstand der sogenannten \stichwort {Nichtstandardanalysis} {.}
}
\inputdefinition
{}
{
Es sei $X$ ein
\definitionsverweis {topologischer Raum}{}{.}
Ein System $F$ aus offenen Teilmengen von $X$ heißt \definitionswort {Filter}{,} wenn folgende Eigenschaften gelten
\zusatzklammer {\mathlk{U,V}{} seien offen} {} {.}
\aufzaehlungdrei{
\mavergleichskette
{\vergleichskette
{X
}
{ \in }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Mit
\mavergleichskette
{\vergleichskette
{U
}
{ \in }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{U
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist auch
\mavergleichskette
{\vergleichskette
{V
}
{ \in }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Mit
\mavergleichskette
{\vergleichskette
{U
}
{ \in }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{V
}
{ \in }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist auch
\mavergleichskette
{\vergleichskette
{U \cap V
}
{ \in }{ F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
\inputdefinition
{}
{
Ein
\definitionsverweis {topologischer Filter}{}{}
$F$ heißt \definitionswort {Ultrafilter}{,} wenn
\mavergleichskette
{\vergleichskette
{ \emptyset
}
{ \notin }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und wenn $F$ maximal mit dieser Eigenschaft ist.
}
{Topologischer Raum/Filter/Ultrafilter/Existenz/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $X$ ein
\definitionsverweis {topologischer Raum}{}{}
und $F$ ein
\definitionsverweis {topologischer Filter}{}{}
auf $X$ mit
\mavergleichskette
{\vergleichskette
{ \emptyset
}
{ \notin }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann gibt es einen
\definitionsverweis {Ultrafilter}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ \supseteq }{F
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 5.9. }
Wir beweisen den \stichwort {Satz von Hamel} {} über die Existenz von Vektorraumbasen als eine weitere Anwendung des Lemmas von Zorn. Eine
\definitionsverweis {Basis}{}{}
eines
\definitionsverweis {Vektorraumes}{}{}
über einem Körper ist ein
\definitionsverweis {linear unabhängiges}{}{} \definitionsverweis {Erzeugendensystem}{}{.}
Für endlich erzeugte Vektorräume
\zusatzklammer {wie den $\R^n$} {} {}
ist dieser Satz auch ohne das Lemma von Zorn direkt beweisbar. Das Problem sind Vektorräume ohne endliches Erzeugendensystem, beispielsweise die Menge der reellen Zahlen als Vektorraum über den rationalen Zahlen oder der oben betrachtete Folgenraum.
\inputfaktbeweis
{Vektorraum/Satz von Hamel/Fakt}
{Satz}
{}
{
\faktsituation {}
\faktvoraussetzung {Jeder
\definitionsverweis {Vektorraum}{}{}}
\faktfolgerung {besitzt eine
\definitionsverweis {Basis}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei $V$ ein Vektorraum über einem Körper $K$. Es sei
\mavergleichskettedisphandlinks
{\vergleichskettedisphandlinks
{M
}
{ =} { { \left\{ T \subseteq V \mid \text{ Die Elemente aus } T \text{ sind linear unabhängig} \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Die leere Menge gehört zu $M$, also ist $M$ nicht leer. Es sei
\mavergleichskette
{\vergleichskette
{N
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine total geordnete Teilmenge. Wir behaupten, dass
\mavergleichskettedisp
{\vergleichskette
{S
}
{ =} { \bigcup_{T \in N} T
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ebenfalls linear unabhängig ist und daher eine obere Schranke von $N$ in $M$ bildet. Andernfalls gäbe es nämlich eine endliche Teilmenge
\mavergleichskette
{\vergleichskette
{E
}
{ \subseteq }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
deren Elemente linear abhängig sind, und es gäbe auch ein
\mavergleichskette
{\vergleichskette
{T
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
das $E$ umfasst und daher selbst linear abhängig wäre. Nach dem
Lemma von Zorn
besitzt $M$ also maximale Elemente, d.h. es gibt eine Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die linear unabhängig ist und derart, dass es keine echt größere linear unabhängige Teilmenge von $V$ gibt. Wir behaupten, dass $T$ auch ein
\definitionsverweis {Erzeugendensystem}{}{}
von $V$ ist. Es sei dazu
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Bei
\mavergleichskette
{\vergleichskette
{v
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sind wir fertig. Bei
\mavergleichskette
{\vergleichskette
{v
}
{ \notin }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mathl{T \cup \{v\}}{} linear abhängig, d.h. es gibt eine Linearkombination
\mavergleichskettedisp
{\vergleichskette
{ \sum_{i=1}^n c_i t_i +cv
}
{ =} { 0
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit Elementen
\mavergleichskette
{\vergleichskette
{t_i
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und Koeffizienten
\mavergleichskette
{\vergleichskette
{c_i,c
}
{ \in }{K
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die nicht alle $0$ sind. Dabei kann $c$ nicht $0$ sein, da sonst eine lineare Abhängigkeit zwischen Elementen aus $T$ vorliegen würde. Also kann man $v$ als Linearkombination der
\mathl{t_1 , \ldots , t_n}{} ausdrücken.
\inputdefinition
{}
{
Eine
\definitionsverweis {totale Ordnung}{}{}
$\preccurlyeq$ auf einer Menge $M$ heißt
\definitionswort {Wohlordnung}{,}
wenn jede nichtleere Teilmenge
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {kleinstes Element}{}{}
besitzt.
}
Beispielsweise sind die natürlichen Zahlen wohlgeordnet, die reellen Zahlen nicht, siehe
Aufgabe 5.19.
Da eine totale Ordnung vorliegt, stimmen jeweils die Begriffe kleinstes Element und minimales Element überein. Die folgende Aussage heißt \stichwort {Wohlordnungssatz} {.} Er folgt aus dem Auswahlaxiom und ist zu diesem und zum Lemma von Zorn äquvalent. Wir verzichten auf einen Beweis.
\inputfakt{Mengentheorie/Wohlordnungssatz/Fakt}{Satz}{}
{
\faktsituation {}
\faktvoraussetzung {Auf jeder Menge $M$}
\faktfolgerung {gibt es eine
\definitionsverweis {Wohlordnung}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
Auch diese Aussage ist lediglich eine Existenzaussage. Es ist im Allgemeinen nicht möglich, explizit eine Wohlordnung zu konstruieren. Auf den reellen Zahlen ist keine Wohlordnung bekannt.
\zwischenueberschrift{Der Vollständigkeitssatz der Aussagenlogik II}
\inputfaktbeweis
{Aussagenlogik/Vollständigkeitssatz/Auffüllungsstrategie/Zorn/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}}
\faktfolgerung {Dann gibt es eine
\definitionsverweis {maximal widerspruchsfreie}{}{}
Teilmenge
\mavergleichskette
{\vergleichskette
{\Gamma'
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die $\Gamma$ enthält.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir betrachten die Menge
\mavergleichskettedisp
{\vergleichskette
{M
}
{ \defeq} { { \left\{ \Delta \subseteq L^V \mid \Delta \supseteq \Gamma , \, \Delta \text{ widerspruchsfrei } \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit der durch Inklusion gegebenen
\definitionsverweis {Ordnung}{}{.}
Wegen
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist diese Menge nicht leer. Es sei
\mavergleichskette
{\vergleichskette
{N
}
{ \subseteq }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine nichtleere total geordnete Teilmenge. Die Vereinigung
\mavergleichskettedisp
{\vergleichskette
{ \Theta
}
{ =} { \bigcup_{\Delta \in N} \Delta
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist ebenfalls widerspruchsfrei, da ein Widerspruch schon aus einer endlichen Teilmenge ableitbar wäre, die ganz in einem der $\Delta$ enthalten wäre. Also besitzt die Kette in $M$ eine obere Schranke. Nach dem
Lemma von Zorn
gibt es also in $M$ maximale Elemente. Ein solches ist
\definitionsverweis {maximal widerspruchsfrei}{}{.}
\inputfaktbeweis
{Aussagenlogik/Vollständigkeitssatz/Widerspruchsfrei/Erfüllbar/Beliebiger Fall/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
\definitionsverweis {widerspruchsfreie}{}{}
Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}}
\faktfolgerung {Dann ist $\Gamma$
\definitionsverweis {erfüllbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Nach Lemma 5.17 \zusatzklammer {bzw. Lemma 4.9 im abzählbaren Fall} {} {} kann man $\Gamma$ zu einer maximal widerspruchsfreien Ausdrucksmenge $\Gamma'$ auffüllen. Nach Lemma 4.8 ist $\Gamma'$ erfüllbar, d.h., es gibt eine \definitionsverweis {Wahrheitsbelegung}{}{} $\lambda$ derart, dass unter der zugehörigen \definitionsverweis {Interpretation}{}{} alle Ausdrücke aus $\Gamma'$ gültig sind. Dann sind unter dieser Belegung insbesondere die Ausdrücke aus $\Gamma$ gültig.
Die folgende Aussage ist der \stichwort {Vollständigkeitssatz für die Aussagenlogik} {.}
\inputfaktbeweis
{Aussagenlogik/Vollständigkeitssatz/Beliebiger Fall/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ \subseteq }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine Teilmenge der zugehörigen
\definitionsverweis {Sprache der Aussagenlogik}{}{.}
Es sei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann ist
\mathdisp {\Gamma \vdash \alpha \text{ genau dann, wenn } \Gamma \vDash \alpha} { . }
}
\faktzusatz {}
\faktzusatz {}
}
{
Dass die Ableitungsbeziehung die Folgerungsbeziehung impliziert, wurde bereits im Rahmen der Korrektheitsüberlegungen zu den Ableitungsregeln gezeigt. Für die Umkehrung nehmen wir
\mathl{\Gamma \not\vdash \alpha}{} an. Dies bedeutet nach
Aufgabe 4.5,
dass
\mathl{\Gamma \cup \{\neg \alpha \}}{}
\definitionsverweis {widerspruchsfrei}{}{}
ist. Nach
Satz 5.18
ist dann auch
\mathl{\Gamma \cup \{\neg \alpha \}}{} erfüllbar. Es gibt also eine Wahrheitsbelegung mit
\mathl{I \vDash \Gamma}{} und
\mathl{I \vDash \neg \alpha}{.} Also ist $\Gamma \not\vDash \alpha$.
\inputfaktbeweis
{Aussagenlogik/Vollständigkeitssatz/Tautologie/Fakt}
{Korollar}
{}
{
\faktsituation {Es sei $V$ eine Menge an
\definitionsverweis {Aussagenvariablen}{}{}
und
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{L^V
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann ist
\mathdisp {\vdash \alpha \text{ genau dann, wenn } \vDash \alpha} { . }
}
\faktzusatz {Ein Ausdruck ist also eine
\definitionsverweis {semantische Tautologie}{}{}
genau dann, wenn es eine
\definitionsverweis {syntaktische Tautologie}{}{}
ist.}
\faktzusatz {}
}
{
Dies ist der Spezialfall von
Satz 5.19
bei
\mavergleichskette
{\vergleichskette
{\Gamma
}
{ = }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}