Kurs:Analysis (Osnabrück 2013-2015)/Teil I/Vorlesung 10/latex
\setcounter{section}{10}
\zwischenueberschrift{Mächtigkeiten}
Zwei Kinder, die noch nicht zählen können, sitzen im Sandkasten und wollen wissen, wer von ihnen mehr Buddelsachen dabei hat. Sie lösen das Problem, indem beide gleichzeitig je eine Sache aus ihrem Besitz aus dem Sandkasten hinauswerfen, und dies so lange wiederholen, bis ein Kind keine Sachen mehr im Sandkasten hat. Wenn das andere Kind noch Sachen übrig hat, so hat dieses insgesamt mehr Buddelsachen, andernfalls haben sie gleichviel. Dies ist die Grundidee für den Begriff der gleichmächtigen Menge.
\inputdefinition
{}
{
Zwei Mengen \mathkor {} {L} {und} {M} {} heißen \stichwort {gleichmächtig} {,} wenn es eine \definitionsverweis {bijektive Abbildung}{}{} \maabbdisp {\varphi} {L} {M} {} gibt.
}
\inputfaktbeweis
{Zwei Mengen/Mächtigkeitsbeziehung/Injektiv und Surjektiv/Fakt}
{Lemma}
{}
{
\faktsituation {Es seien
\mathkor {} {M} {und} {N} {} zwei Mengen.}
\faktuebergang {Dann sind die folgenden Aussagen äquivalent.}
\faktfolgerung {\aufzaehlungzwei {$N$ ist leer oder es gibt eine
\definitionsverweis {surjektive Abbildung}{}{}
\maabbdisp {\varphi} {M} {N
} {.}
} {Es gibt eine
\definitionsverweis {injektive Abbildung}{}{}
\maabbdisp {\psi} {N} {M
} {.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
$(1) \Rightarrow (2)$. \fallunterscheidungzwei {Wenn $N$ leer ist, so kann man die
\definitionsverweis {leere Abbildung}{}{}
\maabb {} {\emptyset} {M
} {}
nehmen.}
{Es sei also
\mavergleichskette
{\vergleichskette
{N
}
{ \neq }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei
\maabbdisp {\varphi} {M} {N
} {}
\definitionsverweis {surjektiv}{}{.}
Zu jedem
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es ein
\mavergleichskette
{\vergleichskette
{x
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ \varphi(x)
}
{ = }{ y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wir wählen für jedes $y$ ein solches $x_y$
aus und definieren $\psi$ durch
\maabbeledisp {\psi} {N} {M
} {y} {\psi(y) = x_y
} {.}
Wegen
\mavergleichskette
{\vergleichskette
{ \varphi(\psi(y))
}
{ = }{ y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist $\psi$
\definitionsverweis {injektiv}{}{.}}
$(2) \Rightarrow (1)$. Es sei nun eine injektive Abbildung
\maabbdisp {\psi} {N} {M
} {}
gegeben. Diese induziert eine Bijektion zwischen $N$ und dem
\definitionsverweis {Bild}{}{}
von $\psi$, sei
\maabb {\theta} {N} { \operatorname{bild} \psi
} {}
diese Abbildung.
\fallunterscheidungzwei {Wenn $N$ leer ist, so sind wir fertig.}
{Es sei also
\mavergleichskette
{\vergleichskette
{ N
}
{ \neq }{ \emptyset
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und sei
\mavergleichskette
{\vergleichskette
{c
}
{ \in }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein fixiertes Element. Wir definieren
\maabbdisp {\varphi} {M} {N
} {}
durch
\mavergleichskettedisp
{\vergleichskette
{ \varphi(x)
}
{ =} { \begin{cases} \theta^{-1} (x),\, \text{ falls } x \in \operatorname{bild} \psi\, , \\ c \text{ sonst} \, . \end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Diese Abbildung ist wegen
\mavergleichskette
{\vergleichskette
{ \varphi( \theta(y))
}
{ = }{ y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
surjektiv.}
\zwischenueberschrift{Endliche Mengen}
\inputdefinition
{}
{
Eine Menge $M$ heißt \definitionswort {endlich}{} mit $n$ Elementen, wenn es eine \definitionsverweis {Bijektion}{}{} \maabbdisp {} {\{ 1 , \ldots , n \}} {M} {} gibt.
}
Die natürliche Zahl $n$ ist dabei nach
Aufgabe 2.5
eindeutig bestimmt und heißt die \stichwort {Anzahl} {}
\zusatzklammer {oder die \stichwort {Kardinalität} {}} {} {}
der Menge. Sie wird mit
\mathl{{ \# \left( M \right) }}{} oder mit
\mathl{\betrag { M }}{} bezeichnet. Die bijektive Abbildung
\maabbdisp {} {\{1 , \ldots , n \}} {M
} {}
kann man eine \stichwort {Nummerierung} {} der Menge $M$ nennen. Eine Menge besitzt also $n$ Elemente, wenn man sie mit den natürlichen Zahlen von $1$ bis $n$ durchnummerieren kann. Zwei endliche Mengen
\mathkor {} {M} {und} {N} {,}
für die es eine Bijektion
\maabbdisp {} {M} {N
} {}
gibt, besitzen die gleiche Anzahl. Dies beruht einfach darauf, dass diese Bijektion verknüpft mit der bijektiven Nummerierung wieder eine Bijektion ist. Eine Menge, die nicht endlich ist, für die es also keine Bijektion mit
\mathl{{ \{ 1 , \ldots , n \} }}{} für kein $n$ gibt, heißt \stichwort {unendlich} {.}
\inputfaktbeweis
{Endliche Menge/Schubfachprinzip/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $M$ eine
\definitionsverweis {endliche Menge}{}{}
mit $m$ Elementen und $N$ eine endliche Menge mit $n$ Elementen.}
\faktvoraussetzung {Es sei
\mavergleichskette
{\vergleichskette
{m
}
{ > }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}}
\faktfolgerung {Dann gibt es keine
\definitionsverweis {injektive Abbildung}{}{}
\maabbdisp {} {M} {N
} {.}}
\faktzusatz {}
\faktzusatz {}
}
{
Wir nehmen an, dass es eine injektive Abbildung
\maabbdisp {\varphi} {M} {N
} {}
gibt. Es sei
\mavergleichskette
{\vergleichskette
{T
}
{ = }{\varphi(M)
}
{ \subseteq }{ N
}
{ }{
}
{ }{
}
}
{}{}{}
das
\definitionsverweis {Bild}{}{}
von $M$ unter der Abbildung $\varphi$. Dann ergibt sich eine Bijektion
\maabbdisp {\tilde{\varphi}} {M} {T
} {,}
da sich die Injektivität überträgt und da eine Abbildung immer surjektiv auf ihr Bild ist. Daher haben
\mathkor {} {M} {und} {T} {}
gleich viele Elemente. Nach
Aufgabe 10.1
ist die Anzahl einer Teilmenge stets kleiner oder gleich der Anzahl der Menge. Also ist
\mavergleichskette
{\vergleichskette
{m
}
{ \leq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
im Widerspruch zur Voraussetzung.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {TooManyPigeons.jpg} }
\end{center}
\bildtext {} }
\bildlizenz { TooManyPigeons.jpg } {} {McKay} {en Wikipedia} {CC-by-sa 3.0} {}
Die vorstehende Aussage heißt \stichwort {Schubfachprinzip} {}
\zusatzklammer {oder \stichwort {Taubenschlagprinzip} {}} {} {.}
Es besagt, dass wenn man $m$ Tauben auf $n$ Plätze verteilt mit
\mavergleichskette
{\vergleichskette
{m
}
{ > }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
dass dann in mindestens einem Platz mindestens zwei Tauben landen.
{Endliche Menge/Gleiche Anzahl/Injektiv ist surjektiv/Fakt}
{Lemma}
{}
{
Seien \mathkor {} {M} {und} {N} {} \definitionsverweis {endliche Mengen}{}{} mit $n$ Elementen. Dann sind für eine Abbildung \maabbdisp {F} {M} {N } {} die Begriffe \definitionsverweis {injektiv}{}{,} \definitionsverweis {surjektiv}{}{} und \definitionsverweis {bijektiv}{}{} äquivalent.
{ Siehe Aufgabe 10.3. }
\zwischenueberschrift{Abzählbare Mengen}
Durch den Mächtigkeitsbegriff wird eine Hierarchie auch in die Welt der unendlichen Mengen gebracht. Die zu den natürlichen Zahlen gleichmächtigen Mengen sind die \anfuehrung{kleinsten}{} unendlichen Mengen. Dies sind die sogenannten \anfuehrung{abzählbar unendlichen}{} Mengen.
\inputdefinition
{}
{
Eine Menge $M$ heißt \definitionswort {abzählbar}{,} wenn sie leer ist oder wenn es eine \definitionsverweis {surjektive Abbildung}{}{} \maabbdisp {\varphi} {\N} {M } {} gibt.
}
Nicht abzählbare Mengen nennt man im Allgemeinen \stichwort {überabzählbar} {.} Aufgrund von Lemma 10.2 ist die Abzählbarkeit von $M$ gleichbedeutend damit, dass es eine injektive Abbildung \maabb {} {M} {\N } {} gibt. Beim Nachweis der Abzählbarkeit arbeitet man aber meistens mit der oben angegebenen Definition.
Endliche Mengen sind natürlich abzählbar. Die natürlichen Zahlen sind ab\-zählbar unendlich.
\inputdefinition
{}
{
Eine Menge $M$ heißt \definitionswort {abzählbar unendlich}{,} wenn sie \definitionsverweis {abzählbar}{}{,} aber nicht \definitionsverweis {endlich}{}{} ist.
}
\inputfaktbeweis
{Abzählbar unendlich/Bijektion zu N/Fakt}
{Lemma}
{}
{
\faktsituation {}
\faktfolgerung {Eine Menge $M$ ist genau dann
\definitionsverweis {abzählbar unendlich}{}{,} wenn es eine
\definitionsverweis {Bijektion}{}{} zwischen $\N$ und $M$ gibt.}
\faktzusatz {}
\faktzusatz {}
}
{
Es sei
\maabbdisp {\varphi} {\N} {M
} {}
eine
\definitionsverweis {surjektive Abbildung}{}{.}
Wir definieren
\definitionsverweis {induktiv}{}{}
eine
\definitionsverweis {streng wachsende Abbildung}{}{}
\maabbdisp {\psi} {\N} {\N
} {}
derart, dass
\mathl{\varphi \circ \psi}{}
\definitionsverweis {bijektiv}{}{}
ist. Wir setzen
\mavergleichskette
{\vergleichskette
{ \psi(0)
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und konstruieren $\psi$ induktiv über die Eigenschaft, dass
\mathl{\psi(n+1)}{} die kleinste natürliche Zahl $k$ ist, für die
\mathl{\varphi(k)}{} nicht zu
\mathdisp {\{\varphi(\psi(0)), \varphi(\psi(1)) , \ldots , \varphi(\psi(n)) \}} { }
gehört. Eine solche Zahl gibt es immer, da andernfalls $M$ endlich wäre; also gibt es auch eine kleinste solche Zahl. Nach Konstruktion ist
\mavergleichskette
{\vergleichskette
{ \psi(n+1)
}
{ > }{ \psi(n)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
d.h. $\psi$ ist
\definitionsverweis {streng wachsend}{}{.}
\teilbeweis {}{}{}
{Da jedes
\mavergleichskette
{\vergleichskette
{n
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
die Eigenschaft
\mavergleichskettedisp
{\vergleichskette
{ \varphi( \psi(n+1))
}
{ \notin} { \{\varphi(\psi(0)), \varphi(\psi(1)) , \ldots , \varphi(\psi(n)) \}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
erfüllt, ist die Gesamtabbildung
\mathl{\varphi \circ \psi}{}
\definitionsverweis {injektiv}{}{.}}
{}
\teilbeweis {}{}{}
{Zum Nachweis der Surjektivität sei
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wegen der Surjektivität von $\varphi$ ist die
\definitionsverweis {Faser}{}{ (also die Urbildmenge zu diesem Element)}
\mathl{\varphi^{-1}(m)}{} nicht leer und daher gibt es auch ein kleinstes Element
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{ \N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ \varphi(a)
}
{ = }{ m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Da $\psi$ streng wachsend ist, gibt es nur endlich viele Zahlen
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{ \{ 0,1 , \ldots , n \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{ \psi(i)
}
{ < }{ a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Daher ist
\mavergleichskette
{\vergleichskette
{ \psi(n+1)
}
{ = }{ a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \varphi(\psi(n+1))
}
{ = }{ \varphi(a)
}
{ = }{ m
}
{ }{
}
{ }{
}
}
{}{}{.}}
{}
D.h. insbesondere, dass alle abzählbar unendlichen Mengen gleichmächtig sind.
\inputfaktbeweis
{Produkt von abzählbaren Mengen/Abzählbar/Fakt}
{Lemma}
{}
{
\faktsituation {Seien
\mathkor {} {M_1} {und} {M_2} {}
\definitionsverweis {abzählbare}{}{} Mengen.}
\faktfolgerung {Dann ist auch die
\definitionsverweis {Produktmenge}{}{}
\mathl{M_1 \times M_2}{}
\definitionsverweis {abzählbar}{}{.}}
\faktzusatz {Insbesondere ist das Produkt
\mathl{\N \times \N}{} abzählbar.}
\faktzusatz {}
}
{
\teilbeweis {}{}{}
{Wir beweisen zuerst den Zusatz. Die Abbildung
\maabbeledisp {} {\N \times \N} { \N
} {(k,\ell)} {2^k (2\ell+1)
} {,}
ist
\definitionsverweis {injektiv}{}{,}
da für jede positive natürliche Zahl $n$ die Zweierpotenz $2^k$, die sie teilt, und der ungerade komplementäre Teiler eindeutig bestimmt sind
\zusatzklammer {das
\definitionsverweis {Bild}{}{}
der Abbildung ist $\N_+$} {} {.}
Daher ist die Produktmenge nach
Lemma 10.2
\definitionsverweis {abzählbar}{}{.}}
{} \teilbeweis {}{}{}
{Für den allgemeinen Fall seien abzählbare Mengen
\mathkor {} {M_1} {und} {M_2} {}
gegeben.
\fallunterscheidungzwei {Wenn eine davon leer ist, so ist auch die Produktmenge leer und somit abzählbar.}
{Es seien also
\mathkor {} {M_1} {und} {M_2} {}
nicht leer und seien
\mathkor {} {\varphi_1: \N \rightarrow M_1} {und} {\varphi_2: \N \rightarrow M_2} {}
\definitionsverweis {surjektive}{}{}
Abbildungen. Dann ist auch die
\definitionsverweis {Produktabbildung}{}{}
\maabbdisp {\varphi=\varphi_1 \times \varphi_2} {\N \times \N} {M_1 \times M_2
} {}
surjektiv. Nach der Vorüberlegung gibt es eine surjektive Abbildung
\maabbdisp {} {\N} {\N \times \N
} {,}
sodass es insgesamt eine surjektive Abbildung
\maabb {} {\N} {M_1 \times M_2
} {}
gibt.}
}
{}
\inputfaktbeweis
{Abzählbare Vereinigung abzählbarer Mengen/Abzählbar/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $I$ eine
\definitionsverweis {abzählbare}{}{}
\definitionsverweis {Indexmenge}{}{}
und zu jedem
\mavergleichskette
{\vergleichskette
{i
}
{ \in }{I
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sei $M_i$ eine abzählbare Menge.}
\faktfolgerung {Dann ist auch die
\zusatzklammer {disjunkte} {} {}
\definitionsverweis {Vereinigung}{}{}\zusatzfussnote {Wenn die $M_i$ Teilmengen einer festen Obermenge sind, so ist die Vereinigung in dieser Menge zu nehmen und im Allgemeinen nicht disjunkt. Wenn es sich um Mengen handelt, die nichts miteinander zu tun haben, so ist mit Vereinigung die disjunkte Vereinigung gemeint} {.} {}
\mathl{\bigcup_{i \in I} M_i}{} abzählbar.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir können annehmen, dass sämtliche $M_i$ nicht leer sind. Es gibt dann
\definitionsverweis {surjektive Abbildungen}{}{}
\maabbdisp {\varphi_i} {\N} {M_i
} {.}
Daraus konstruieren wir die Abbildung
\maabbeledisp {\varphi} {I \times \N} { \bigcup_{i \in I} M_i
} {(i,n)} { \varphi_i(n)
} {,}
die offensichtlich surjektiv ist. Nach
Lemma 10.9
ist die
\definitionsverweis {Produktmenge}{}{}
\mathl{I \times \N}{} abzählbar, also gilt das auch für das
\definitionsverweis {Bild}{}{}
unter $\varphi$, und dieses ist die Vereinigung.
Wir ziehen einige wichtige Konsequenzen über die Abzählbarkeit von Zahlbereichen. Man beachte, dass die natürlichen Inklusionen
\mathl{\N \subset \Z \subset \Q}{} nicht bijektiv sind. Die Bijektionen, die es zwischen $\N$ einerseits und
\mathkor {} {\Z} {bzw.} {\Q} {}
andererseits aufgrund der folgenden Aussagen gibt, respektieren nicht die Rechenoperationen.
{Z/Abzählbar/Fakt}
{Lemma}
{}
{
\faktsituation {Die Menge der
\definitionsverweis {ganzen Zahlen}{}{}}
\faktfolgerung {ist
\definitionsverweis {abzählbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 10.4. }
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Diagonal_argument.svg} }
\end{center}
\bildtext {Die Abzählbarkeit der positiven rationalen Zahlen.} }
\bildlizenz { Diagonal argument.svg } {} {Cronholm144} {Commons} {CC-by-sa 3.0} {}
{Q/Abzählbar/Fakt}
{Satz}
{}
{
\faktsituation {Die Menge der
\definitionsverweis {rationalen Zahlen}{}{}}
\faktfolgerung {ist
\definitionsverweis {abzählbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 10.5. }
\zwischenueberschrift{Die Überabzählbarkeit der reellen Zahlen}
\inputfaktbeweis
{R/Überabzählbar/Fakt}
{Satz}
{}
{
\faktsituation {Die Menge der
\definitionsverweis {reellen Zahlen}{}{} $\R$}
\faktfolgerung {ist nicht
\definitionsverweis {abzählbar}{}{.}}
\faktzusatz {}
\faktzusatz {}
}
{
Nehmen wir an, die Menge der reellen Zahlen sei
\definitionsverweis {abzählbar}{}{,} dann ist insbesondere auch das
\definitionsverweis {Einheitsintervall}{}{}
\mathl{[0,1[}{} abzählbar. Es sei also
\maabbdisp {\psi} {\N_+} {[0,1[
} {}
eine
\definitionsverweis {surjektive Abbildung}{}{.}
Wir betrachten die reellen Zahlen als Ziffernfolgen im Dreiersystem: Jede reelle Zahl
\mavergleichskette
{\vergleichskette
{r
}
{ \in }{[0,1[
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
besitzt eine eindeutig bestimmte Darstellung als
\definitionsverweis {Reihe}{}{}
\mavergleichskettedisp
{\vergleichskette
{r
}
{ =} { \sum_{k = 1}^\infty z_k(r) 3^{-k}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
wobei die $k$-te Nachkommaziffer
\mavergleichskette
{\vergleichskette
{ z_k(r)
}
{ \in }{ \{ 0,1,2 \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist und wobei nicht
\definitionsverweis {fast alle}{}{ (das bedeutet alle bis auf endlich viele)}
Ziffern gleich $2$ sind
\zusatzklammer {sonst hätte man keine Eindeutigkeit} {} {.}
Wir definieren nun eine reelle Zahl durch
\mavergleichskette
{\vergleichskette
{s
}
{ = }{\sum_{k = 1}^\infty b_k 3^{-k}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{b_k
}
{ =} { \begin{cases} 0 , \text{ falls } ( \psi(k) )_k = 1 \text{ oder } 2, \\ 1,\, \text{ falls } (\psi(k))_k = 0 \, .\end{cases}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
Wir behaupten, dass diese Zahl $s$ nicht in der Aufzählung $\psi$ vorkommt. Für jedes
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{\N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist nämlich
\mavergleichskettedisp
{\vergleichskette
{ \psi(k)
}
{ \neq} { s
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
da
\mathl{\psi(k)}{} sich nach Konstruktion von $s$ an der $k$-ten Nachkommastelle unterscheidet. Also ist $\psi$ doch nicht surjektiv.
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {1925_kurt_gödel.png} }
\end{center}
\bildtext {Kurt Gödel bewies 1938, dass die Hinzunahme der Kontinuumshypothese zur Zermelo-Fraenkelschen Mengenlehre einschließlich Auswahlaxiom
\zusatzklammer {ZFC} {} {}
diese nicht widersprüchlich macht. Man kann aber nicht beweisen, dass ZFC widerspruchsfrei ist. Auch das hat Gödel bewiesen.} }
\bildlizenz { 1925 kurt gödel.png } {} {Kl833x9} {Commons} {PD} {}
\inputbemerkung
{}
{
Ist jede
\definitionsverweis {überabzählbare Menge}{}{}
\mavergleichskette
{\vergleichskette
{T
}
{ \subseteq }{\R
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionsverweis {gleichmächtig}{}{}
zu $\R$? Die \stichwort {Kontinuumshypothese} {} behauptet, dass dies gilt. Diese Frage berührt die mengentheoretischen Grundlagen der Mathematik; es hängt nämlich von der gewählten Mengenlehre ab, ob dies gilt oder nicht, man kann es sich also aussuchen. Anders als beim \stichwort {Auswahlaxiom} {,} ohne dessen Akzeptanz eine Vielzahl von mathematischen Schlüssen nicht möglich wäre und die Mathematik ziemlich anders aussehen wüde, ist es für praktische Zwecke unerheblich, wofür man sich entscheidet.
}
Mit einem ähnlichen \zusatzklammer {Diagonal} {} {-}Argument wie im Beweis zu Satz 10.13 kann man zeigen, dass die Potenzmenge einer Menge stets eine größere Mächtigkeit als die Menge besitzt.
\inputfaktbeweis
{Menge/Potenzmenge/Übermächtigkeit/Fakt}
{Satz}
{}
{
\faktsituation {Es sei $M$ eine Menge und
\mathl{\mathfrak {P} \, (M )}{} ihre
\definitionsverweis {Potenzmenge}{}{.}}
\faktfolgerung {Dann besitzt
\mathl{\mathfrak {P} \, (M )}{} eine größere
\definitionsverweis {Mächtigkeit}{}{}
als $M$.}
\faktzusatz {}
\faktzusatz {}
}
{
Wir nehmen an, dass es eine surjektive Abbildung
\maabbeledisp {F} {M} { \mathfrak {P} \, (M ) } {x} {F(x) } {,}
gibt, und müssen dies zu einem Widerspruch führen. Dazu betrachten wir
\mavergleichskettedisp
{\vergleichskette
{ T
}
{ =} { { \left\{ x \in M \mid x \notin F(x) \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Da dies eine Teilmenge von $M$ ist, muss es wegen der Surjektivität ein
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
geben mit
\mavergleichskettedisp
{\vergleichskette
{ F(y)
}
{ =} { T
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es gibt nun zwei Fälle, nämlich
\mathkor {} {y \in F(y)} {oder} {y \not\in F(y)} {.} Im ersten Fall ist also
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
und damit, nach der Definition von $T$, auch
\mavergleichskette
{\vergleichskette
{y
}
{ \notin }{ F(y)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
Widerspruch. Im zweiten Fall ist, wieder aufgrund der Definition von $T$,
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
und das ist ebenfalls ein Widerspruch.