3.3 Mengen, die so groß wie $R$ sind

Im letzten Kapitel haben wir viele Mengen kennengelernt, die abzählbar unendlich sind, also gleichmächtig mit $N$ . Hier werden wir nun erkunden, welche Mengen gleichmächtig mit $R$ sind. In der mathematischen Fachsprache sagt man: sie haben die Kardinalität des Kontinuums. Das Wort Kardinalität steht hier für Anzahl der Elemente (bzw. den Größenbegriff bei unendlichen Mengen), und Kontinuum steht für die reellen Zahlen. Im nächsten Kapitel werden wir zeigen, dass es "echt mehr" reelle Zahlen gibt als natürliche; dass also $R$ nicht abzählbar ist. Aber eins nach dem anderen.

Beobachtung 3.3.1 Es gilt $R \approx (0, 1)$ , wobei $(0, 1)$ das offene Einheitsintervall ist.

Beweis. Wir können eine Bijektion explizit hinschreiben:

\begin{aligned} f : R & \to (0, 1) \\ x & \mapsto \frac{e^{x}}{e^{x} + 1} \end{aligned}

Mit etwas reeller Analysis kann man nun zeigen:

$f$ ist stetig.
$f$ ist streng monoton (z.B. weil $f^{'} (x) > 0$ gilt).
$lim_{x \to - \infty} f (x) = 0$ und $lim_{x \to \infty} f (x) = 1$ .

Und somit ist $f$ eine Bijektion von $R$ auf den Wertebereich von $f$ , also $(0, 1)$ .

◻

Übungsaufgabe 3.3.1 Zeigen Sie $R \approx R^{+}$ .

Übungsaufgabe 3.3.2 Zeigen Sie, dass $R_{0}^{+} \approx R^{+}$ gilt. Sie müssen "die 0 verschwinden lassen".

Übungsaufgabe 3.3.3 Zeigen Sie, dass $[0, 1]$ , $[0, 1)$ , $(0, 1]$ und $(0, 1)$ alle gleichmächtig sind.

Wir führen nun eine neue Notation ein: ${0, 1}^{N}$ ist die Menge aller unendlichen Folgen von $0$ und $1$ . Formal gesehen bezeichnet man für zwei Mengen $A$ und $B$ mit der Notation $A^{B}$ die Menge aller Funktionen $ϕ : B \to A$ . Ein Element aus ${0, 1}^{N}$ wäre demnach eien Funktion $ϕ : N \to {0, 1}$ . Diese Objekte entsprechen genau den unendlichen $0 / 1$ -Folgen, nämlich $ϕ (0) ϕ (1) ϕ (2) ϕ (3) \dots$ . Der Unterschied ist rein syntaktisch. Es ist allerdings bequemer, sich ein $ϕ \in {0, 1}^{N}$ als unendliche $0 / 1$ -Folge vorzustellen.

Theorem 3.3.2 $R \approx {0, 1}^{N}$ .

Beweis. Die Beweisidee ist einfach, allerdings gehen erst einmal ein paar Dinge schief, die man wieder flicken muss. Da laut Übungsaufgabe 2.3.3 $R \approx [0, 1)$ gilt, reicht es, eine Bijektion $f : [0, 1) \to {0, 1}^{N}$ zu konstruieren. So geht's:

Jede Zahl $0 \leq x < 1$ lässt sich als (unendliche) Binärzahl $(x)_{2}$ schreiben, beispielsweise

\begin{array}{r} {(\frac{1}{3})}_{2} = 0.01010101 \dots \end{array}

Wir erhalten nun unsere unendliche $0 / 1$ -Folge, indem wir die führende Null und den Punkt abschneiden: $f (1 / 3) = 010101 \dots$ . Das geht für jede Zahl in $[0, 1)$ : $f (1 / 2) = 100000 \dots$ , $f (1 / 4) = 010000 \dots$ .

Die konstruierte Funktion $f$ ist injektiv: zwei verschiedene $0 \leq x < y < 1$ haben verschiedene Binärdarstellung und werden somit zu zwie verschiedenen $0 / 1$ -Folgen. Leider ist sie nicht surjektiv: die Binärdarstellung einer reellen Zahl hört nie mit $11111 \dots$ auf. Statt $0.001111111 \dots$ würden wir einfach $0.0100000 \dots$ schreiben. Das entspricht dem Phänomen in der Dezimalschreibweise, dass $0.99999999 \dots$ und $1.000000 \dots$ die gleiche Zahl repräsentieren. Die "kanonische" Repräsentierung ist allerdings immer die mit einem unendlichen Schweif an Nullen, nie mit Neunen (oder in Binär: Einsen). Definieren wir also $X$ , die Menge aller $0 / 1$ -Folgen mit einem unendlichen Schweif an Einsen:

\begin{array}{r} X := {a_{1} a_{2} a_{3} \dots \in {0, 1}^{N} | \exists n \geq 1 : a_{i} = 1 \forall i \geq n} \end{array}

Unsere Funktion $f$ ist eine Bijektion von $[0, 1)$ nach ${0, 1}^{N} ∖ X$ . Um daraus eine Bijektion $g : [0, 1) \to {0, 1}^{N}$ zu bauen, müssen wir die Lücken füllen, die $f$ lässt - also $X$ .

Übungsaufgabe 3.3.4 Sei $Y := {a_{1} a_{2} a_{3} \dots \in {0, 1}^{N} | \exists n \geq 1 : a_{i} = 0 \forall i \geq n}$ die Menge aller $0 / 1$ -Folgen mit einem unendlichen Schweif von Nullen. Offensichtlich gilt $X \approx Y$ .

Zeigen Sie, dass $Y \approx X \cup Y$ gilt.

Übungsaufgabe 3.3.5 Verwenden Sie die vorherige Übungsaufgabe, um $Y$ zu verdoppeln und somit eine Bijektion von $[0, 1) \to {0, 1}^{N}$ zu konstruieren. Vielleicht hilft Ihnen folgendes Bild:

Als nächstes zeigen wir, dass gilt. Dies ist schon erstaunlich: der Zahlenstrahl und die zweidimensionale Ebene sollen also gleichviele Elemente haben!

Theorem 3.3.3 Es gilt .

Beweis. Mithilfe von Theorem 2.3.2 geht das ganz einfach. Da gilt, reicht es nämlich, eine Bijektion zu konstruieren. Ein Element von besteht aus zwei unendlichen -Folgen:

Wir müssen dieses Folgenpaar nun in eine Folge codieren. Ganz klar:

Dies ist die gewünschte Bijektion

Aus der Funktion aus Theorem 2.3.3 können wir eine (fast) bijektive Funktion bauen. Wir nehmen zwei Zahlen , schreiben sie in Binärdarstellung und vereinigen sie dann per Reißverschlussverfahren zu einer Zahl, z.B.

Um herauszufinden, um welche Zahl es sich bei handelt, multiplizieren wir sie mit 64:

Sie erreicht alle Zahlen bis auf diejenigen mit einem unendlichen Schweif von Einsen. Sie ist hochgradig nichtstetig. Dennoch können wir versuchen, sie zu plotten:

Als nächstes versuche ich, die Umkehrfunktion zu skizzieren. Das ist etwas schwierig, weil nicht stetig ist. Was macht ? Sie betrachtet in Binärdarstellung und dröselt dann die unendlich vielen Nachkommastellen auf. Die ungeraden bilden , die geraden bilden . Beispielsweise für gilt

also .

Beobachtung 3.3.4 Die Funktion bildet

auf ab,
auf ,
auf und
auf .

Beweis. Wir zeigen den ersten Punkt. Sei und . Dann hat die Binärdarstellung . Die ersten beiden Bits nach dem Komma sind , und somit sind die jeweils ersten Bits von und auch 0, was bedeutet. Punkt 2 bis 4 folgen aus ähnlichen Überlegungen.

Wenn wir also von nach wandern lassen, dann bewegt sich von links unten nach links oben, springt dann nach rechts unten und bewegt sich nach rechts oben. Grafisch stelle ich das wie folgt (und etwas unbeholfen) dar:

Beachten Sie, dass die Verbindungslinien zwischen den Kreisen Sprünge sind, also Unstetigkeitsstellen von . Innerhalb der Viertelintervalle (also z.B. innerhalb von ) sieht der Graph wieder ganz ähnlich aus. Hier sehen Sie die ersten paar Schritte dieser "Verfeinerung".

Wir wissen nun, dass gilt. Ebenso können wir für jedes zeigen. Wie sieht es aber mit aus? Das ist die Menge aller Funktionen oder, etwas freundlicher formuliert, die Menge aller unendlichen Folgen reeller Zahlen: .

Theorem 3.3.5 .

Beweis. Da gilt, reicht es, zu zeigen, dass

gilt. Interpretieren wir die rechte Seite: das sind unendliche Folgen von "Dingern", und jedes Ding ist wiederum eine unendliche Folge von 0/1. Wir können uns jedes Ding als (unendliche) Zeile vorstellen und erhalten somit eine in beiden Richtungen unendliche Tabelle. Wenn also eine unendliche -Folge ist und und das -te Bit der -ten Folge, dann sieht unsere Tabelle so aus:

Wir wollen jetzt eine Bijektion definieren. Dafür wenden wir den gleichen Trick an wie in dem Beweis, dass ist: wir zerlegen die Tabelle in Diagonalen und arbeiten jede separat ab:

Schließlich definieren wir unsere Folge :

Wir haben also die Beweisidee von recycelt. Diese Beobachtung motiviert den folgenden, etwas kurz angebundenen Beweis:

Zweiter Beweis. Um zu zeigen, dass gilt, rechnen wir:

Dürfen wir das? Dürfen wir Rechenregeln wie so einfach anwenden? Noch grundlegender, und das ist auch ein Punkt im ersten Beweis, den ich unter den Teppich gekehrt habe: Zwar wissen wir bereits, dass . Folgt aber daraus bereits, dass ? Erstens also: dürfen wir mit Plus, Mal und Hoch wie gewohnt rechnen? Und dürfen wir in den resultierenden Ausdrücken equipotente Mengen austauschen?

Bevor wir das als Theorem formulieren, überlegen wir uns kurz, was denn die Analoga zu den arithmetischen Operationen sind. Am klarsten ist die Multiplikation: die Zahlenmultiplikation hat als mengentheoretisches Analog das Cartesische Produkt , die Menge aller Paare mit . Die Exponentiation hat als Analog , die Menge aller Funktionen . Was ist das Analog zur Addition? Die Vereinigung wäre zu kurz gegriffen, weil ja zum Beispiel fünf Elemente hat, aber nur drei. Das "richtige" Analog ist die disjunkte Vereinigung , die die Elemente von erst einmal "markiert", um sie von denen von unterscheidbar zu machen. Somit wäre also eine Menge der Kardinalität 5. Formal kann man so definieren;

Theorem 3.3.6 (mit Kardinalzahlen rechnen). Es gelten die üblichen Rechenregeln:

sowie Kommutativität und Assoziativität von und .

Als zweites gilt, dass wir in so einem "mengentheoretisch-arithmetischen" Ausdruck eine Menge durch eine äquipotente Menge ersetzen können:

Theorem 3.3.7 Seien Mengen und . Dann gilt

(und natürlich auch ).
(und natürlich auch ).
.
.

Beachten Sie, dass ich Punkt 3 und 4 nicht zu einem Punkt zusammengefasst habe. Punkt 4 folgt nämlich nicht unmittelbar aus Punkt 3 sondern erfordert einen separaten Beweis.

Übungsaufgabe 3.3.6 Beweisen Sie so viele Punkte von Theorem 2.3.6 und Theorem 2.3.7, wie Sie wollen.

Hinweis. Die Beweise sind alle nicht wirklich schwierig. Sie müssen nur aufpassen, dass Sie sich nicht in der Notation verlieren.

Die Partialordnung .

Wir betrachten , die Potenzmenge von , also die Menge aller Teilmengen.

Übungsaufgabe 3.3.7 Zeigen Sie, dass gilt.

Die Elemente von , also Teilmengen , sind nach Inklusion geordnet: . Somit ist eine Partialordnung. Eine Kette in einer Partialordnung ist eine Menge , in der alle Elemente paarweise vergleichbar sind. In diesem konkreten Beispiel heißt das: und für alle gilt oder . Erinnern Sie sich: und sind hier Mengen natürlicher Zahlen, und ist eine Menge von Mengen natürlicher Zahlen. Eine Antikette in einer Partialordnung ist eine Teilmenge , in der je zwei Elemente unvergleichbar sind. In diesem Beispiel heißt das: , und für alle mit gilt und . Hier ist ein Beispiel für eine unendliche Kette:

Diese Kette hat zufälligerweise die Form , d.h., die Elemente der Kette sind schön sortiert, von klein nach groß. Dies muss nicht so sein: sei die Menge der Vielfachen von . Dann gilt , die Elemente sind also in "absteigender" Reihenfolge sortiert. Beide Beispiele haben einen "Anfangspunkt". Das muss aber nicht so sein: sei .

Wenn wir ganz links noch hinschreiben und ganz rechts noch , dann haben wir ein weiteres, eventuell ungewohntes Phänomen: das Element in der Kette hat keinen eindeutigen Nachfolger. Egal, welches mit Sie wählen, sie finden immer noch ein dazwischen: .

Definition 3.3.8 (Dichte Partialordnung) Eine Partialordnung heißt dicht, wenn es für alle mit ein gibt mit .

Ein klassisches Beispiel für eine dichte Ordnung ist . Wenn , dann ist . Sie finden also immer etwas dazwischen. Die Ordnung ist nicht dicht: zwischen und finden Sie nichts. Die Partialordnung ist nicht dicht: es gilt , aber es gibt keine Menge zwischen den beiden.

Übungsaufgabe 3.3.8 Finden Sie in eine Kette , so dass dicht ist. Also: eine Menge , so dass für alle mit entweder oder gilt (d.h. soll eine Kette sein) und zusätzlich ein mit (oder ).

3.3 Mengen, die so groß wie R sind

Die Partialordnung .

3.3 Mengen, die so groß wie $R$ sind