3.2 Beispiele abzählbar unendlicher Mengen

Noch bevor wir im letzten Teilkapitel den Begriff der Gleichmächtigkeit definiert haben, haben wir zwei Beispiele gesehen: $N^{+} \approx N \approx Z$ . Alle Mengen sind gleichmächtig. In diesem Teilkapitel werden wir unintuitivere Beispiele sehen: $N \approx Q$ . Dies scheint absurd! $N$ und $Z$ liegen ja schön der Reihe nach sortiert, sodass sich eine Bijektion durch eine einfach Umordnung erreichen ließ. Die Elemente der Menge $Q$ aber liegen ja nicht säuberlich getrennt, sondern ganz dicht nebeneinander. Aber eins nach dem anderen.

Theorem 3.2.1 Die Mengen $N$ und $N^{2}$ sind gleichmächtig. Mit $N^{2}$ (oder auch $N \times N$ ) bezeichnen wir hier das cartesische Produkt von $N$ mit sich selbst: die Menge aller Paare $(a, b)$ von natürlichen Zahlen.

Die Menge

N

bzw. ein Teil davon.

Die Menge

N \times N

bzw. ein Teil davon.

Beweis. Wir skizzieren eine Bijektion $f : N \times N \to N$ , indem wir für jeden Punkt $(x, y) \in N \times N$ angeben, auf welche natürliche Zahl er abgebildet werden soll:

Wir zerlegen $N \times N$ also in fallende Diagonale und gehen jede Diagonale von rechts unten nach links oben durch. Dadurch können wir die zweidimensionale Gestalt von $N \times N$ "aufdröseln" und dem eindimensionalen $N$ zuordnen. $◻$

Übungsaufgabe 3.2.1 Finden Sie eine explizite Formel für die Funktion $f : N \times N$ aus dem obigen Theorem. Achten Sie erst einmal auf die Werte von $f (x, 0)$ : $f (3, 0) = 6$ und $f (4, 0) = 10$ beispielsweise. Erkennen Sie die blauen Zahlen auf der $x$ -Achse? Haben Sie eine Formel für sie? Finden Sie eine. Dann erweitern Sie die Formel, so dass sie für alle Werte von $(x, y) \in N \times N$ funktioniert!

Übungsaufgabe 3.2.2 Zeigen Sie $Z \times Z \approx Z$ , indem Sie eine ähnliche Aufdröselung finden, jetzt aber mit negativen Zahlen.

Übungsaufgabe 3.2.3 Zeigen Sie ganz allgemein: wenn $A \approx A^{'}$ und $B \approx B^{'}$ , dann gilt auch $A \times B \approx A^{'} \times B^{'}$ .

Übungsaufgabe 3.2.4 Zeigen Sie, dass $N \times N \times N \approx N$ gilt und ganz allgemein: $N^{k} \approx N$ .

Übungsaufgabe 3.2.5 Sei $N^{*}$ die Menge aller endlichen Folgen natürlicher Zahlen, also

\begin{array}{r} N^{*} := {ϵ} \cup N \cup N^{2} \cup N^{3} \cup \dots, \end{array}

wobei

ϵ

die leere Folge (mit 0 Gliedern) bezeichnet. Zeigen Sie

N^{*} \approx N

Rationale Zahlen

Ich will Sie nun davon überzeugen, dass $Q \approx N$ ist, dass es also "gleich viele rationale wie natürliche Zahlen" gibt. Ich beginne mit etwas Einfacherem:

Beobachtung. 3.2.2 Es gibt eine injektive Funktion $f : Q \to N$ .

Beweis. Falls Sie es vergessen haben: eine Funktion $f : A \to B$ heißt injektiv, wenn für alle verschiedenen $a, a^{'} \in A$ auch $f (a) \neq f (a^{'})$ gilt. Wenn $f$ also "kollisionsfrei" ist.

Sei $q \in Q$ eine rationale Zahl. Wir können $q$ als gekürzten Bruch schreiben, also

mit und und . Mit bezeichnen wir den größten gemeinsamen Teiler (greatest common divisor) von und . Wir definieren nun also . Dies ist injektiv: zwei verschiedene rationale Zahlen und haben verschiedene Darstellung als gekürzter Bruch, und somit gilt auch .

Wir haben nun also eine Injektion . Mit Übungsaufgabe 2.2.3 und Theorem 2.2.1 gilt , und somit gibt es eine Bijektion . Die Verknüpfung ist nun die gewünschte injektive Funktion von nach .

Dies ist leider keine Bijektion: das Paar beispielsweise wird nie vorkommen, weil nicht gekürzt ist.

Beobachtung: 3.2.3 Es gibt eine injektive Funktion .

Beweis. Dies ist ganz einach: da gilt, können wir jedes einfach bei sich belassen. Die Funktion

ist die gewünschte Injektion. Man nennt so eine Funktion auch die Einbettung von in .

Wir sind nun also in der sonderbaren Situation, dass wir eine injektive Funktion haben, die aber nicht alle ausfüllt, also nicht surjektiv ist. Gleichzeitig haben wir , die injektiv ist aber auch nicht surjektiv. Bei bleiben also manche natürlichen Zahlen ungenutzt, bei bleiben rationale Zahlen ungenutzt. Können wir und irgendwie kombinieren, um eine bijektive Funktion zu erschaffen? Die Antwort lautet ja, das geht immer, ist nicht ganz trivial zu beweisen, heißt Schröder-Bernstein-Theorem, und wir werden das im Teilkapitel ... beweisen. Vorerst behelfen wir uns mit ad-hoc-Methoden.

Theorem 3.2.4 Es gilt .

Beweis. Wir definieren eine Bijektion , indem wir die Beweisidee von Theorem 2.2.1 wiederholen. Wir zeichnen schematisch, löschen aber die Paare , die nicht einem gekürzten Bruch entsprechen.

Die Punkte sind die Elemente von . Die schwarzen Punkte sind jene Punkte mit . Diese stehen nun in Bijektion mit den rationalen Zahlen. Die entsprechenden rationalen Zahlen habe ich daneben geschrieben - die negativen habe ich aus Gründen der Übersichtlichkeit weggelassen. Sie befinden sich spiegelverkehrt auf der linken Seite. Wir müssen nun eine Aufzählung der schwarzen Punkte finden, also eine Bijektion von in die Menge der schwarzen Punkte:

Das funktioniert natürlich: wir überspringen einfach die gelöschten Punkte. Wir können allerdings nicht bequem eine geschlossene Formel dafür angeben. Auf dem "fünften Hütchen", das von nach läuft, sind zum Beispiel alle Punkte bis auf schwarz, was daran liegt, dass eine Primzahl ist und somit alle mit und teilerfremd sind. Streng genommen müssten wir uns davon überzeugen, dass unendlich viele schwarze Punkte übrigbleiben. Das ist aber einfach, weil alle Punkte der Form der Zahl entsprechen, und das ist ja ein gekürzter Bruch.

Endliche Strings

Erinnern wir uns an

, die Menge aller endlichen Bitstrings. Die Menge ist ganz klar unendlich, weil sie zum Beispiel

enthält. Ist sie abzählbar unendlich?

Theorem 3.2.5 Es gilt .

Beweis. Hier ist eine Idee: wir interpretieren den Bitstring als -stellige Binärzahl, also

Leider geht das schief, weil , , etc. alle auf abgebildet werden. Ebenso , , und so weiter. Wir könnten uns behelfen und dem String eine 1 voranstellen, also beispielsweise

Formal also

Eine äquivalente Interpretation: wir sortieren erst einmal die Bitstrings nach ihrer Länge. Dann gehen wir lexicographisch durch, also von bis . Diese Reihenfolge durchläuft ganz und ordnet jedem Bitstring eine natürliche Zahl zu. Also:

Das haut nicht ganz hin, weil die nie drankommt. In der Tat stellt die obige Tabelle eine Bijektion dar. Dies ist leicht korrigiert, indem wir 1 abziehen: die Funktion

ist eine Bijektion von nach .

Geht das auch mit mehr als zwei Symbolen?

Übungsaufgabe 3.2.6 Definieren Sie eine Bijektion von ^* nach .

Weil das "Alphabet" die Größe hat, können Sie sich mit einem kleinen Taschenspielertrick behelfen. Schwieriger wird es mit . Zeigen Sie, dass gilt.

Zeigen Sie ganz allgemein: wenn eine endliche Menge ist, dann gilt .