\documentclass[12pt] {article} \usepackage[german]{babel} \usepackage[latin1]{inputenc} \usepackage{amsthm} % \advance\textwidth 1cm \advance\textheight 1cm % \usepackage{helvetic} \usepackage{mathrsfs} \usepackage{amsmath} \usepackage{amssymb} % \def\xx#1\par{\par\centerline{\bf #1}\par} % \def\yy#1:{\par\noindent{\bf #1:}} \theoremstyle{remark} \def\zz#1 {\newtheorem{#1}[thm]{#1}} \newtheorem{thm}{Theorem} \renewcommand{\thethm}{} \zz Satz \zz Definition \zz {Satz von Cantor} \zz {Satz von Cantor, schwache Form} \zz {Satz von Cantor, starke Version} \zz Beispiel \renewcommand{\P}{{\mathscr P}} \newcommand{\B}{{\mathscr B}} \newcommand{\N}{{\Bbb N}} \newcommand{\R}{{\Bbb R}} \newcommand{\C}{{\Bbb C}} \newcommand{\Q}{{\Bbb Q}} \newcommand{\E}{{\mathscr E}} \renewcommand{\c}{{\mathfrak c}} \author{Martin Goldstern} \title{Mengenlehre: Hierarchie der Unendlichkeiten} \date{} \begin{document} \maketitle % \section*{Was ist Mengenlehre ?} Mengenlehre ist ein Teilgebiet der mathematischen Logik. Wie die Logik überhaupt spielt die Mengenlehre mehrere Rollen: Man kann sie als philosophisches {\em "`Fundament"' der Mathematik} auf\null fassen, man kann die Sprache der Mengenlehre als {\em universelle Sprache der Mathematik} benutzen (letztendlich sprechen Gruppentheoretiker, Funktionalanalytiker, Kombinatoriker etc.\ alle von Strukturen, die aus Mengen aufgebaut sind), und man kann die Mengenlehre einfach als eines von vielen {\em mathematischen Gebieten} sehen, auf welchem mit rein mathematischen (also nicht etwa philosophischen) Methoden Strukturen analysiert werden. Wie in jedem Gebiet der reinen Mathematik gibt es hier Definitionen, Sätze, und Beweise. \def\ignore#1{}\ignore{\small Fragestellungen in der Mengenlehre sind oft ursprünglich durch außerlogische Probleme motiviert worden, insbesondere durch Fragen aus der Topologie, Analysis, Maßtheorie, Funktionalanalysis und Algebra. Auf Beispiele möchte ich hier nicht näher eingehen, man findet sie in der Literatur etwa unter den Schlagworten descriptive set theory, real-valued measurable, automatic continuity, Whitehead problem, und andere.} Auf diesen "`innermathematischen"' Aspekt der Mengenlehre möchte ich mich hier konzentrieren. Was ist nun das Objekt der mengentheoretischen Forschung? \section*{Aktuell oder potentiell ?} Die Aufgabe der Mengenlehre ist es, das Unendliche mit mathematischen Mitteln zu erforschen. Was man unter dem "`Unendlichen"' versteht, ist in der Mathematik nicht kanonisch festgelegt. Die Mathematiker nehmen hier einen pragmatischen Standpunkt ein: erlaubt ist das, was praktisch ist. Einige Beispiele: \begin{enumerate} \item In der elementaren Zahlentheorie zum Beispiel spielt dieser Begriff überhaupt keine Rolle. Wenn überhaupt, so übernimmt die Zahl 0 die Rolle von $\infty$, denn $0$ ist im Teilerverband (also in der partiellen Ordnung, die durch die Teilbarkeitsrelation der natürlichen Zahlen gegeben wird --- wir definieren $m\le k \Leftrightarrow $ $m$ ist ein Teiler von $k$), das größte Element. \item In der projektiven ebenen Geometrie versteht man unter "`unendlich"' einfach eine willkürlich gewählte Gerade, deren Punkte man als "`unendlich ferne Punkte"' oder "`Richtungen"' interpretiert. \item In der reellen Analysis gibt es zwei "`unendlich große"' Objekte, nämlich $+\infty $ und $-\infty$. Der Begriff "`unendlich"' wird hier exakt durch die Definition des Grenzwertes formalisiert. \item In der komplexen Analysis erweist es sich meistens als sinnvoll (und oft als möglich), mit nur einem Wert "`unendlich"' zu rechnen. \end{enumerate} In den ersten beiden Beispielen ist das Unendliche (in der jeweiligen Interpretation) "`aktuell unendlich"' -- das Unendliche wird hier als Objekt der Theorie selbst betrachtet, in den anderen beiden Beispielen steht das "`potentiell Unendliche"' im Vordergrund, das Unendliche als Umschreibung für einen unendlichen Prozess. In der Mengenlehre untersuchen wir einen Begriff des Aktual-Unendlichen. Die Geburtsstunde der Mengenlehre schlug in jenem Moment, als Georg Cantor entdeckte, dass es es verschiedene "`Gr"oßen"' von unendlichen Mengen gibt. Die Begriffe "`abz"ahlbar"' und "`"ub\-er\-ab\-z"ahl\-bar"' sind den Lesern wohl schon bekannt, das ist aber noch l"angst nicht alles. Es gibt eine unendliche Skala von unendlichen "`Kardinalit"aten"', und diese Skala ist nicht nur unendlich lang, sondern sogar \"uberabz\"ahlbar --- wie lang genau, das kann hier noch nicht formuliert werden, dazu müssen wir erst eine eigene Sprache schaffen. \section*{Gleichm\"achtigkeit} Die grundlegende Definition, die es erlaubt, unendliche Mengen nach ihrer Größe zu unterscheiden, ist folgende: \begin{Definition} $A \approx B$, in Worten: "`$A$ ist gleichmächtig mit $B$"', genau dann, wenn es eine bijektive Abbildung von $A$ nach $B$ gibt. \end{Definition} Wenn $A$ endlich ist, dann bedeutet $A \approx B$: "`$B$ hat genau so viele Elemente wie $A$"'. Der Begriff "`gleichmächtig"' verallgemeinert also den Begriff "`gleich viele Elemente"', den wir aus der Welt der endlichen Mengen kennen. ACHTUNG! Bei unendlichen Mengen kann es durchaus vorkommen ({\sl tat\-säch\-lich kommt es {\em immer} vor}\footnote{Bei meinem Vortrag über dieses Thema im Rahmen eines "`Didaktiktags"' an der Universität Wien wurde ich auch über die Rolle des Auswahlaxioms befragt. Da es sich bei dem vorliegenden Artikel nur um eine recht oberflächliche Einführung in Ideen der Mengenlehre handelt, möchte ich auf das Thema Auswahlaxiom hier nicht näher eingehen. Als Markierung für den Eingeweihten werde ich aber bei jedem Satz, der das Auswahlaxiom zum Beweis braucht, einen {\sl speziellen Zeichensatz} verwenden.}), dass eine Menge $A$ zu einer echten Teilmenge $B \subset A$ gleichmächtig ist. Zum Beispiel sind die Mengen $A = \{0,1,2,3\ldots \,\}$ und $B= \{1,2,3\ldots \,\}$ gleich\-mäch\-tig, weil die Abbildung $n\mapsto n+1$ eine Bijektion ist. \footnote{An dieser Stelle hört man in der einen oder anderen Form immer wieder die Frage: Ja, aber was passiert am Ende? Wohin wird das letzte Element von $A$ abgebildet?% Ist $B$ nicht etwas kürzer? } Dies kann bei endlichen Mengen natürlich nicht auftreten. Für unendliche Mengen treten aber noch viel seltsamere Situationen auf: Es kann vorkommen, dass eine Menge $A$ gleichmächtig mit $A \times A = \{ (x,y): x,y\in A\}$ ist. {\sl (Tatsächlich tritt dies sogar immer auf)} Ich überlasse es dem Leser, nachzurechnen, dass die Abbildung $(m,n) \mapsto 2^n\cdot(2k+1)-1$ eine Bijektion von $\N\times \N$ nach $\N$ ist. Man kann auch eine explizite Bijektion von $\R\times \R$ nach $\R$ angeben, also: \begin{quote} Die Ebene ist gleichmächtig mit der Geraden! \end{quote} Die angeführte Definition der Gleichmächtigkeit liefert auch gleich eine mögliche formale Definition des Begriffs "`unendliche Menge"'. Wenn man davon ausgeht, dass die natürlichen Zahlen ein bereits bekannter Begriff sind, kann man definieren: \begin{Definition} Eine Menge $A$ heißt endlich, wenn es eine natürliche Zahl $n\in\N$ gibt, sodass $A$ und $\{k\in \N: 1 \le k\le n\}$ gleichmächtig sind. Andernfalls heißt die Menge $A$ unendlich. \end{Definition} {\small Man kann das Begriffspaar endlich/unendlich aber auch ohne Rückgriff die natürlichen Zahlen definieren. Man definiert zB eine Menge $A$ als T-endlich\footnote{Diese Definition geht auf Alfred Tarski zurück}, wenn ihre Potenzmenge $\P(A)$ die folgende Eigenschaft hat: \begin{quote} Jede nichtleere Teilmenge $\B \subseteq \P(A)$ hat ein (bezüglich der Inklusion $\subseteq$) maximales Element. \end{quote} Endliche Mengen (im oben definierten Sinn) sind sicher T-endlich, denn jede nichtleere Menge $\B \subseteq \P(A)$ hat mindestens ein Element $C$, welches bezüglich seiner Kardinalität größtmöglich ist, dieses $C$ muss dann auch bezüglich $\subseteq$ maximal sein. Umgekehrt ist jede T-endliche Menge $A$ wirklich endlich. Sei nämlich $\B \subseteq \P(A)$ die Menge aller endlichen Teilmengen von $A$. Da $A$ T-endlich ist, hat $\B$ ein maximales Element $A'$. $A'$ ist also endlich, und es muss $A'=A$ gelten, sonst bekommt man leicht einen Widerspruch zur Maximalität von $A'$. Die beiden angeführten scheinbar verschiedenen Definitionen von "`endlich"' und "`T-endlich"' führen also auf denselben Begriff. } \section*{Satz von Cantor} Die Relation $\approx$ ist natürlich eine Äquivalenzrelation (reflexiv, symmetrisch, transitiv). Die Aufgabe \begin{quote} Erforsche das Unendliche (mit mathematischen Mitteln)! \end{quote} kann man nun folgendermaßen präzisieren: \begin{quote} Untersuche die Äquivalenzklassen der Relation "`gleichmächtig"'! \end{quote} Zunächst gibt es für jede natürliche Zahl $n$ die Klasse der Mengen, die genau $n$ Elemente enthalten. Diese Klassen, die also nur endliche Mengen enthalten, wollen wir im Folgenden beiseite lassen. Interessant wird die Gleichmächtigkeitsrelation mit folgendem Satz: \begin{Satz von Cantor, schwache Form} Es gibt zwei unendliche Mengen $A$ und $B$, sodass $A\not\approx B$. \end{Satz von Cantor, schwache Form} In Anbetracht des oben zitierten Satzes (die Ebene hat "`genau so viele"' Elemente wie die Gerade), ist es zunächst nicht offensichtlich, wie man zwei "`verschieden große"' Mengen konstruieren kann.\footnote{Achtung! Wenn man von einer Menge $B$ weiß, dass sie gleichmächtig mit einer echten Teilmenge von $A$ ist, dann hat man NOCH NICHT bewiesen, dass $A \not \approx B$. Es genügt nicht, zu zeigen, dass es irgendeine nicht-Bijektion von $A$ nach $B$ gibt, man muss zeigen, dass es keine Bijektion gibt.} \subsection*{Beweis des Satzes von Cantor} Sei $\P(\N)$ die Potenzmenge von $\N$, also die Menge aller Teilmengen von $\N$. Wir zeigen, dass eine Abbildung $f:\N \to\P(\N)$ niemals surjektiv sein kann. Daher ist $\N\not\approx \P(\N)$. Sei also eine Abbildung $f:\N \to\P(\N)$ gegeben. {\small [Objekte von der Form $f(n)$ sind also immer Teilmengen von $\N$]} Um zu zeigen, dass $f$ nicht surjektiv sein kann, werden wir eine Menge $A \in \P(\N)$ (also $A \subseteq \N$) finden, die nicht im Wertebereich von $f$ liegt. Wir werden zeigen, dass die Menge $$ A_f:= \{ n\in \N: n\notin f(n) \}$$ sicher nicht im Wertebereich von $f$ liegen kann.\footnote{An dieser Stelle empfehle ich dem Leser, selbst zu zeigen, dass die Annahme $A_f = f(k)$ auf einen Widerspruch führt --- einen selbstgefundenen Beweis versteht er/sie möglicherweise besser als den in den folgenden Absätzen präsentierten.} Um zum Beispiel zu zeigen, dass $A_f \not= f(23)$ ist, genügt es, eine einzige natürliche Zahl $z = z_{f,23}$ zu finden, die zwar Element von $A_f$ ist, aber nicht von $f(23)$. Es würde auch genügen, eine einzige Zahl $z $ zu finden, die die umgekehrte Bedingung erfüllt, also: $z \notin A_f$ aber $z\in f(23)$. \\ Es stellt sich heraus, dass die Zahl $z=23$ eine der beiden Anforderungen erfüllt, also entweder in $A_f\setminus f(23)$ oder in $f(23) \setminus A_f$ liegt. Wenn nämlich $23\in f(23)$, dann ist (nach Definition von $A_f$) $23\notin A_f$. Wenn aber $23\notin f(23)$, dann ist (wiederum nach Definition von $A_f$) $23\in A_f$. Diese Argumentation funktioniert aber für jede andere Zahl $k$ an der Stelle von 23 auch --- $A_f$ kann also nicht von der Form $f(k)$ sein. Also ist $f$ nicht surjektiv. Damit ist der Beweis abgeschlossen. {\small [Man könnte nun hoffen, dass $A_f$ vielleicht die einzige Menge ist, die nicht im Bild von $f$ auftritt, und statt der Funktion $f$ die Funktion $g$ mit $g(0)= A_f$, $g(1) = f(0)$, $g(2) = f(1)$, etc, betrachten --- der Wertebereich der Funktion $g$ umfasst den gesamten Wertebereich von $f$, und er enthält überdies noch die Menge $A_f$. --- Das hilft aber nichts: auch zur Funktion $g$ kann man (wie ja zu {\bf jeder} Funktion von $\N$ nach $\P(\N)$) eine Menge $A_g$ konstruieren, die nicht im Wertebereich von $g$ vorkommt.]} Zur Illustration dieses Beweises betrachen wir als Beispiel die folgende Abbildung $f$, die zB der Zahl $0$ die Menge aller nat\"urlichen Zahlen zuordnet, dann der Zahl 1 die leere Menge, dann die ungeraden Zahlen, die Primzahlen, usw. \ialign{& \hfil$#$ \hfil\cr \qquad f(0) = \{ & 0, & 1, & 2, & 3, & 4, & 5, & 6, & 7, & 8, & \ldots & \}\cr \qquad f(1) = \{ & & & & & & & & & & \ldots & \}\cr \qquad f(2) = \{ & & 1, & & 3, & & 5, & & 7, & & \ldots & \}\cr \qquad f(3) = \{ & & & 2, & 3, & & 5, & & 7, & & \ldots & \}\cr \qquad f(4) = \{ & 0, & & 2, & & 4, & & 6, & & 8, & \ldots & \}\cr &&& \ldots \cr } Eine Menge $A$, die sicher nicht im Wertebereich von $f$ liegt, bekommt man, nun, wenn man in obigem Diagramm entlang der Diagonale geht: {\catcode`!\active \def!#1{{\bf #1}} \ialign{& \hfil$#$ \hfil\cr \qquad f(0) = \{ & !0, & 1, & 2, & 3, & 4, & 5, & 6, & 7, & 8, & \ldots & \}\cr \qquad f(1) = \{ & & !\_ & & & & & & & & \ldots & \}\cr \qquad f(2) = \{ & & 1, & !\_ & 3, & & 5, & & 7, & & \ldots & \}\cr \qquad f(3) = \{ & & & 2, & !3, & & 5, & & 7, & & \ldots & \}\cr \qquad f(4) = \{ & 0, & & 2, & & !4, & & 6, & & 8, & \ldots & \}\cr &&& \ldots \cr }} \noindent und das Komplement bildet, aus $\{0, \ \ \ 3, 4, \ldots\}$ entsteht $A= \{\ \ 1, 2, \ \ \ \ , \ldots \}$, und sicherlich ist $A \not=f(0)$ (weil ja $0\in f(0)$, aber $0 \notin A$). Ebenso erh"alt man $A\not= f(1)$, etc. Dieser Beweis, den man aus offensichtlichen Gründen auch als "`Diagonalisierung"' bezeichnet, ist also ganz analog zum Beweis, dass die Menge der reellen Zahlen "uberabz"ahlbar ist. Dieser Beweis zeigt aber noch viel mehr als die oben genannte schwache Form: \begin{Satz von Cantor, starke Version} F\"ur jede Menge $A$ gilt: $A\not\approx\P(A)$. \end{Satz von Cantor, starke Version} Anmerkung: Der oben gegebene Beweis ist natürlich nur für unendliche Mengen $A$ interessant. Für endliche Mengen $A$ funktioniert er zwar auch, doch liefert eine kombinatorische Überlegung viel mehr Information: Wenn $A$ $n$ Elemente hat, dann hat $\P(A)$ $2^n$ Elemente. \section*{Vergleich von Mächtigkeiten} Die {\em Kardinalität} oder {\em Mächtigkeit} einer Menge $A$ ist die Äquivalenz\-klasse der Menge $A$ bezüglich der Relation $\approx$. Zum Beispiel ist die Kardinalität einer Einermenge $\{a\}$ die Klasse aller Einermengen. Da es unhandlich ist, mit so großen Klassen zu rechnen, verwenden wir stattdessen "`Kardinalzahlen"': Aus jeder Kardinalität wählen wir einen kanonischen Repräsentanten. ZB wählen wir aus der Klasse der Einermengen die Menge $\{0\}$ als Repräsentanten aus, aus der Klasse der Zweiermengen die Menge $\{0,1\}$. \\ Diese Repräsentanten nennen wir dann {\em Kardinalzahlen}. Für jede Menge $A$ schreiben wir $|A|$ für die Kardinalzahl (manchmal auch für die Kardinalität) von $A$. Es gilt also: \begin{quote} $A\approx B$ genau dann, wenn $|A| = |B|$. \end{quote} Wir wollen nun die Struktur der Klasse aller Kardinalzahlen untersuchen. \begin{Definition} $A\lesssim B$ ($B$ ist mächtiger als $A$, $A$ ist schmächtiger als $B$) ist definiert durch: \begin{quote} Es gibt eine injektive Abbildung $f:A\to B$ \end{quote} oder äquivalent: $A$ ist gleichmächtig mit einer Teilmenge von $B$ (nicht notwendigerweise mit einer echten Teilmenge). \end{Definition} \begin{Beispiel} Es gilt stets: $A \lesssim \P(A)$, denn die Abbildung $ f: A\to \P(A)$, $a\in A \ \mapsto \{a \} \in \P(A)$ ist offensichtlich injektiv. \end{Beispiel} Es ist klar, dass $\lesssim$ eine transitive Relation ist. Weiters ist klar, dass die Beziehung $\lesssim $ nur von den $\approx$-Äquivalenzklassen abhängt, d.h.: Wenn $A\approx A'$, $B \approx B'$, dann ist $A\lesssim B$ mit $A' \lesssim B'$ äquivalent. Es ist nicht ganz offensichtlich (aber doch beweisbar), dass $\lesssim$ (modulo der Relation $\approx$) antisymmetrisch ist, d.h.: \newtheorem{CSB}[thm]{Satz von Cantor, Schr\"oder und Bernstein} \begin{CSB} Wenn $A\lesssim B$ und $B \lesssim A$, dann $A\approx B$. {\small [Mit anderen Worten: Wenn es injektive Abbildungen $f:A \to B$ und $g:B \to A$ gibt, dann gibt es eine Bijektion $h:A \to B$. $h$ lässt sich sogar mehr oder weniger explizit aus $f$ und $g$ konstruieren.]} \end{CSB} Daher werden die Kardinalitäten (bzw die Kardinalzahlen) durch die Relation $\lesssim$ partiell geordnet. Statt $A\lesssim B$ schreiben wir daher auch $|A|\le |B|$. \bigskip {\sl Aber es gilt noch mehr: \newtheorem{Vgl}[thm]{Satz \"uber die Vergleichbarkeit} \begin{Vgl} \sl Für alle Mengen $A$, $B$ gilt: $A\lesssim B $ oder $B \lesssim A$. \end{Vgl} } "`Oder"' ist hier (wie in der Mathematik üblich) im einschließenden Sinne zu verstehen. Nach dem Satz von Cantor, Schr\"oder und Bernstein können die beiden Alternativen nur dann gleichzeitig auftreten, wenn $A \approx B$. \\ Wenn nur die Alternative $A\lesssim B$ gilt (also $B\not\lesssim A$ oder äquivalent: $B\not\approx A$), dann schreiben wir $|A|< |B|$. {\sl Daher induziert die Relation $\simeq$ auf den Kardinalitäten oder Kardinalzahlen eine lineare Ordnung. Diese Ordnung hat überdies noch die Eigenschaft, dass jedes ihrer Elemente $\kappa$ einen direkten Nachfolger $\kappa^+$ hat. % , und dass jede Teilmenge dieser Ordnung eine kleinste % obere Schranke hat. } \section*{Abzählbare Mengen} Den Anfang der Ordnung der Kardinalitäten kennen wir: 0 = die Kardinalzahl der leeren Menge, $1= 0^+$ ist die Kardinalzahl jeder Einermenge, etc. Mit ${\aleph_0} $ ("`Aleph 0"') oder auch $\beth_0$ ("`Beth\footnote{$\aleph$ und $\beth$ sind die ersten beiden Buchstaben des hebr\"aischen Alphabets. $\aleph$ ist überdies der erste Buchstabe des hebräischen Ausdrucks "`e\"\i n sof"', was "`es gibt kein Ende"' bedeutet.} 0"') bezeichnen wir die Kardinalzahl von $\N$, oder die Kardinalität jeder abzählbaren Menge. {\small (Eine Menge $A$ heißt abzählbar, wenn es eine Bijektion $f:\N\to A$ gibt.)} Statt "`Kardinalität (Kardinalzahl) der Menge der \dots"' sagen wir auch informell "`Anzahl der \dots"'. ZB gilt $|\Q|= \aleph_0$, d.h., es gibt eine Bijektion von $\N $ nach $\Q$.\footnote{Mit den bis jetzt zitierten Sätzen lässt sich dies auch einfach beweisen: $\N\lesssim \Q$ ist trivial, ebenso $\Q \lesssim \N\times \N \approx \N$. Also $\N\lesssim \Q\lesssim \N$, daher $\Q\approx \N$. Man kann aber auch eine explizite Bijektion angeben.} Diesen Sachverhalt beschreiben wir durch die Worte \begin{quote} Die Kardinalität der Menge der rationalen Zahlen ist ${\aleph_0}$. \end{quote} oder: \begin{quote} Es gibt ${\aleph_0} $ viele (= "`abzählbar viele"') rationale Zahlen. \end{quote} Ebenso kann man leicht zeigen: Es gibt nur ${\aleph_0} $ viele endliche Teilmengen von $\N$: Sei $\E$ die Menge der endlichen Teilmengen von $\N$, dann m\"ussen wir wir eine injektive Abbildung von $\E$ nach $\N$ angeben. Sei $p_0 < p_1 < p_2 < p_3 < \cdots $ eine unendliche Folge von Primzahlen, dann ist es leicht zu sehen, dass die Abbildung $F: \E\to \N$, definiert durch $$ F(E) = \prod_{i\in E} p_i \qquad \qquad \mbox{ für $E \in \E$} $$ injektiv ist. Abzählbare Mengen kommen überall in der Mathematik vor. $\aleph_0 = \beth_0$ ist nicht nur die Anzahl der natürlichen Zahlen, der Primzahlen, der rationalen Zahlen, der algebraischen Zahlen, der Polynome mit rationalen Koeffizienten, der $7\times 7$-Matrizen über $\Q$, sondern auch die Kardinalität vieler endlich erzeugter Objekte, wie zB der freien Gruppe mit 1104 Erzeugenden, oder der Menge aller Computerprogramme. Weiters tritt $\aleph_0$ oft als Kardinalität einer (in gewissem Sinn) "`erzeugenden"' Teilmenge von größeren Strukturen auf: die reellen Zahlen und viele andere interessante topologische Räume haben eine abzählbare dichte Teilmenge, viele interessante Hilbert\-räume haben eine abzählbare Hilbert\-basis, etc. \section*{Die reellen Zahlen} Die Menge der reellen Zahlen ist überabzählbar\footnote{Achtung: Unter jeder sinnvollen Definition des Wortes "`definierbar"' gibt es nur abzählbar viele definierbare reelle Zahlen (weil es nur abzählbar viele Definitionen gibt --- eine Definition muß ja durch einen endliche Zeichenkette in irgendeinem endlichen Alphabet beschrieben werden). Daher gibt es jedenfalls auch "`undefinierbare"' reelle Zahlen. Das mag paradox erscheinen -- wie kann man beweisen, dass es etwas gibt, dessen Existenz man nicht "`explizit"' belegen kann? \endgraf Auf philosophische Antworten auf diese ontologische Frage möchte ich hier nicht eingehen; in der (klassischen) mathematischen Logik erledigt sich diese Frage durch die "`richtige"' (oder jedenfalls "`praktische"') Verwendung des Begriffs "`es gibt"'.} (d.h., unendlich aber nicht abzählbar.) Wieviele reelle Zahlen gibt es? Diese Frage beantwortet der folgenden Satz nur zum Teil: \begin{Satz} Die folgenden Mengen haben alle dieselbe Mächtigkeit: \begin{enumerate} \item $\R$, die Menge der reellen Zahlen \item $(0,1)$, das offene reelle Einheitsintervall \item $[0,1]$, das abgeschlossene reelle Einheitsintervall \item $\N^\N$, die Menge aller Folgen natürlicher Zahlen \item $\{0,1\}^ \N$, die Menge aller $\{0,1\}$-Folgen \item $\P(\N)$, die Menge aller Mengen natürlicher Zahlen \item $\P_\infty(\N)$, die Menge aller unendlichen Mengen natürlicher Zahlen \item Die Menge aller Borelmengen der reellen Zahlen. \item Die Menge aller Funktionen von $\N$ nach $\R$. \item Die Menge aller Funktionen von $\Q$ nach $\R$. \item Die Menge aller gleichm\"a"sig stetigen Funktionen von $\Q\cap[0,1] $ nach $\R$. \item Die Menge aller stetigen Funktionen von $\R$ nach $\R$. \end{enumerate} \end{Satz} \subsubsection*{Partieller Beweis:} $(-\frac\pi2, \frac\pi2) \approx (0,1)\lesssim [0,1] \lesssim \R$ ist trivial. Eine Bijektion zwischen $\R$ und $(-\frac\pi2, \frac\pi2) $ kann man mit Hilfe der tangens-Funktion bilden. \\ $\{0,1\}^\N \approx \P(\N)$ beweist man mit Hilfe von charakteristischen Funktionen. $\{0,1\}^\N \lesssim \R$ kann man der Dezimalbruchentwicklung zeigen, genauer: die Funktion $$(a_0, a_1, \ldots) \in \{0,1\}^\N \ \mapsto \ \sum_i \frac{a_i}{10^i}$$ ist injektiv. Mit Hilfe der Bin\"arentwicklung kann man eine injektive Funktion von $(0,1)$ nach $\{0,1\}^\N$ finden. \\ $\{0,1\}^\N\lesssim \N^\N$ ist klar, und $\N^\N \lesssim \R$ lässt sich zB mit Hilfe von Kettenbruchentwicklungen zeigen. \\ Nach Anwendung des Satzes von Cantor, Schr\"oder und Bernstein sind damit die Gleichmächtigkeiten der unter 1--6 genannten Mengen nachgewiesen. Der Rest ist eine Spur komplizierter und wird dem ambitionierten Leser überlassen. \vskip 1cm Wir schreiben $\beth_1$, manchmal auch $2^ {\aleph_0}$ ["`zwei hoch aleph 0"'] oder $\c$ ["`Fraktur c"', "`Kontinuum"'] für die Kardinalität aller dieser Mengen. Also $$ |\R| = |[0,1]| = |(0,1)| = \cdots =|\P(\N)| = \beth_1$$ Wir haben also $|\N|= {\beth_0} $, $|\P(\N)|=\beth_1$, und nach dem Satz von Cantor ist $\beth_0 <\beth_1$. Viele unendliche Strukturen, die in der Mathematik vorkommen, haben Kardinalität $\c$: Natürlich die reellen oder komplexen Zahlen ($\R$, $\C$), ebenso $\R^n$ oder $\C^ n$ und überhaupt alle separablen Banachräume (die mehr als ein Element haben), sowie die oben unter 1--12 genannten Mengen. \section*{Die $\beth$-Hierarchie} Wir kennen bereits $\beth_0 = \aleph_0 = |\N|$ und $\beth_1 = |\P(\N)| = |\R|$. Ebenso definieren wir nun $\beth_2 = |\P(\P(\N))| = |\P(\R)|$. $\beth_2$ ist zum Beispiel die Kardinalität von $\P(\R)$, von $\P(\P(\N))$, oder von $\N \cup \P(\N) \cup \P(\P(\N))$. $\beth_2$ ist auch die Anzahl aller Funktionen von $\R$ nach $\R$, oder auch nur der Riemann-integrierbaren Funktionen. Allgemein definieren wir $\beth_n$ als die Kardinalität jener Menge, die man erhält, wenn man den Potenzmengenoperator $n$ Mal auf die Menge $\N$ anwendet. Man kann zeigen, dass man so eine unendliche streng wachsende Folge von Kardinalzahlen bekommt: $\beth_0 < \beth_1 <\cdots $. Es gibt aber noch viel größere Mengen! Betrachten wir die Menge $$ B := \ \N \cup \P(\N) \cup \P(\P(\N)) \cup \cdots $$ Mit $\beth_\omega$ bezeichnen wir die Kardinalität dieser Menge $B$. Offensichtlich ist $\N\lesssim B$, $\P(\N) \lesssim B$, \dots \\ Daher auch $\beth_0 = | \N | < |\P(\N)| = \beth_1 \le | B|$, also $\beth_0 < \beth_\omega $. Ebenso erhalten wir $\beth_1 < \beth_\omega $, etc. Es stellt sich heraus, dass $\beth_\omega $ die kleinste Kardinalzahl ist, die größer als alle $\beth_n$ ist. % $\beth\omega$ hat keinen Vorgänger. Mit $\beth_\omega $ ist es aber noch lange nicht aus. $\beth_{\omega+1}$ ist die Kardinalität der Potenzmenge $\P(B)$ der oben betrachteten Menge $B$, davon können wir wieder die Potenzmenge bilden (deren Kardinalität heißt dann $\beth_{\omega+2}$, etc. Bis jetzt haben wir also abzählbar viele Kardinalzahlen kennengelernt. Tatsächlich gibt es aber viel mehr: Es gibt mindestens $\beth_1$ viele Kardinalzahlen, also sicher überabzählbar viele. (D.h.\ formal: es gibt eine injektive Abbildung $f$, deren Definitionsbereich die Menge $\R$ oder sonst eine Menge mit Kardinalität $\beth_1 $ ist, und deren Funktionswerte lauter Kardinalzahlen sind.) \\ Ebenso gilt: Es gibt mehr als $\beth_2$ viele Kardinalzahlen. Sogar mehr als $\beth_\omega $ viele, etc.! \section*{Die $\aleph$-Skala} Wir wissen bereits: \begin{Satz von Cantor} $A < \P(A)$ gilt für alle Mengen $A$. \end{Satz von Cantor} % ($A \lesssim \P(A)$ läßt sich leicht mit der Abbildung $F: a\in % A\mapsto \{a \} \in \P(A)$ zeigen.) Daher gilt: Zu jeder Kardinalität gibt es eine größere. Man kann sogar Folgendes zeigen: \sl \begin{Satz} \sl Zu jeder Kardinalität (Kardinalzahl) gibt es einen "`Nachfolger"', d.h.\ eine "`nächstgrößere"'. Weiters gilt: Jede Menge von Kardinalzahlen hat eine kleinste obere Schranke. \end{Satz} Die erste unendliche Kardinalzahl bezeichnen wir mit ${\aleph_0} $. Die nächstgrößere mit ${\aleph_1}$, die nächstgrößere mit ${\aleph_2}$, etc. $\aleph_2$ hat also die Eigenschaft, genau zwei Vorgänger zu haben, d.h.: es gibt genau zwei unendliche Kardinalzahlen, die kleiner als ${\aleph_2}$ sind. Mit ${\aleph_\omega} $ beweichnen wir die erste Kardinalzahl, die größer als alle ${\aleph_n} $ ist. Äquivalent könnte man auch definieren: ${\aleph_\omega} $ ist die erste Kardinalzahl, die unendliche viele Vorgänger hat. \subsection*{Charakterisierung der $\aleph$s} Die Kardinalzahl $\aleph_0$ lässt sich als kleinste {\bf unendliche} Kardinalzahl auch so charakterisieren: \begin{quotation} \rm \noindent Für eine Menge $A$ ist $|A|= \aleph_0$ genau dann, wenn folgendes gilt: \begin{itemize} \item $A$ ist unendlich \item Für alle $B \subseteq A$ gilt: Entweder $B$ ist endlich, oder $B\approx A$. \end{itemize} \end{quotation} Ähnlich lässt sich $\aleph_1$ als kleinste {\bf überabzählbare} Kardinalzahl so charakterisieren: \begin{quotation} \noindent Für eine Menge $A$ ist $|A|= \aleph_1$ genau dann, wenn folgendes gilt: \begin{itemize} \item $A$ ist unendlich und nicht abzählbar \item Für alle $B \subseteq A$ gilt: Entweder $B$ ist höchstens abzählbar (d.h., endlich oder abzählbar unendlich), oder $B\approx A$. \end{itemize} \end{quotation} \rm \subsection*{Vergleich von $\beth$ und $\aleph$} Wir wissen bereits, dass $\beth_1 > \beth_0 = {\aleph_0} $. Daher ist $\beth_1 \ge {\aleph_1}$. Ist $\beth_1 = {\aleph_1} $? Dies ist mit den üblichen Axiomen der Mengenlehre nicht entscheidbar. Das heißt: \begin{enumerate} \item[(1)] Es gibt keinen Beweis dafür, dass $\beth_1 = {\aleph_1} $ ist. \item[(2)] Es gibt keinen Beweis dafür, dass $\beth_1 > {\aleph_1} $ ist. \end{enumerate} (Diese beiden Aussagen, d.h.\ (1) und (2), sind allerdings sehr wohl beweisbar, aber nicht trivial.) \section*{Kontinuumshypothese} Die oben aufgetauchte Frage "`Ist $\beth_1= \aleph_1$?"' lässt sich auch so umschreiben und präzisieren: \begin{itemize} \item Gibt es Kardinalitäten, die zwischen $\beth_0$ und $\beth_1$ liegen? \item Wenn ja, wie viele? Eine? (Das hieße ${\beth_0} = {\aleph_0} < {\aleph_1} < {\aleph_2} = \beth _1 $) Oder vielleicht zwei? (Dann wäre ${\beth_0} = {\aleph_0} < {\aleph_1} < {\aleph_2} < {\aleph_3} = \beth _1 $) Oder 2000? Oder abzählbar viele? $\beth_1$ viele? (Jedenfalls nicht mehr als $ \beth_1$ viele!) \end{itemize} \bigskip Die folgenden Fragen haben alle dieselbe Antwort: \begin{enumerate} \item Gibt es eine Kardinalität, die zwischen $\beth_0$ und $\beth_1$ liegt? \item Gibt es eine Menge $A \subseteq \R$, die zwar über\-ab\-zähl\-bar ist, aber noch nicht $ A\approx \R$ erfüllt? \item Ist $\beth_1 > \aleph_1$ ? \end{enumerate} Die {\em Kontinuumshypothese (abgekürzt: CH)} sagt, dass die Antwort "`nein"' lautet. \subsection*{Wir seh'n betroffen \dots } Wie schon erwähnt, ist CH ist nicht beweisbar. D.h., es gibt keine explizite Bijektion von einer Menge der Größe $\aleph_1$ auf $\R$. CH ist auch nicht widerlegbar. D.h., es gibt keine explizit beschreibbare Menge $A \subseteq \R$, die zwar überabzählbar aber noch $<\R$ ist. Es gibt also ganz konkrete Fragen, die (mit Hilfe der üblichen mengentheoretischen Axiome) nicht beantwortet werden können. {\small (So wie auch etwa das Parallelenaxiom nicht mit Hilfe der übrigen Axiome der euklidischen Geometrie beweisbar oder widerlegbar ist.)} Im Hinblick auf den Gödelschen Un\-voll\-stän\-dig\-keits\-satz ist das aber nicht verwunderlich: \\ {\bf Jedes} mathematische System\footnote{das gewisse Minimalanforderungen erfüllt --- als Schlagworte seien hier nur die Entscheidbarkeit des Axiomensystems und die Repräsentierbarkeit der Arithmetik genannt} ist "`unvollständig"', d.h.\ es wird immer (im betrachteten System formulierbare) Fragen geben, die (im betrachteten System) nicht beantwortet werden können! \section*{Quellengeplätscher} Die angeführten Ideen, Definitionen und Sätze sollen nur als Appetitanreger für weitere Lektüre dienen. Wo findet man nun weiterführende Lehrbücher? \newcommand{\xa}[1]{{\bf #1}} \newcommand{\xt}[1]{{\it #1}} \xa{P.~Halmos} ist berühmt für seine allgemeinverständlichen Lehrbücher. Sein Buch \xt{Naive Mengenlehre} ist für den Anfänger leicht zu lesen, erzählt aber nur wenig über die eigentlichen Sätze und Probleme der Mengenlehre, sondern begnügt sich damit, zu erklären, wie die mengentheoretische Sprache in der mathematischen Wirklichkeit angewendet werden kann. (Auswahlaxiom und Ordinalzahlen kommen allerdings schon vor.) Begleitend dazu empfiehlt sich das Buch \xt{Exercises in Set Theory} von \xa{L.E.Sigler}, in dem Übungsaufgaben gestellt und auch gelöst werden. Das Buch \xt{Mengenlehre I} von \xa{J.~Schmidt} erklärt recht breit und ver\-ständ\-lich die grundlegenden mengentheoretischen Konzepte. Das Buch \xt{Basic Set Theory} von \xa{A.~Levy} ist trotz seines bescheidenen Titels wohl zu umfangreich für den Anfänger. Hochinteressant (aber noch schwieriger) finde ich das Buch \xt{Foundations of Set Theory}, wo die Autoren \xa{Y.~Bar-Hillel, A.~Fraenkel und A.~Levy} auch auf die Antinomien und auf philosophische Probleme eingehen. Die erste Hälfte des Buchs \xt{Intermediate Set Theory} von \xa{F.R.~Drake und D.~Singh} halte ich auch für Anfänger recht lesbar. Der Umfang des ausgezeichneten Buchs \xt{Set theory: An introduction to independence proofs} von \xa{K.~Kunen} liegt um viele Größenordungen über dem, was hier präsentiert wurde. Dennoch würde ich dem ambitionierten Leser zumindest das Vorwort und das erste Kapitel dieses Buchs sehr empfehlen. \end{document}