2b. Die Überabzählbarkeit von ℝ (Lösungen)

Übung 1

(a)	Seien M und N abzählbar unendliche Mengen. Zeigen Sie, dass M ∪ N abzählbar unendlich ist.

(b)	Zeigen Sie, dass die Menge ℕ² = { (n, m) \| n, m  ∈  ℕ } abzählbar unendlich ist.

Lösung zur Übung 1

zu (a):

Da M und N abzählbar unendlich sind, gibt es Bijektionen f : ℕ → N und g : ℕ → M. In Folgennotation ist also

f (0), f (1), f (2), …, f (n), …	eine Aufzählung von M,
g(0), g(1), g(2), …, g(n), …	eine Aufzählung von N.

Die Aufzählung f durchläuft alle Elemente von M (Surjektivität) und enthält keine Wiederholungen (Injektivität). Analoges gilt für g.

Wir erhalten nun eine Aufzählung von M ∪ N wie folgt. Zunächst bilden wir die Folge

(+) f (0), g(0), f (1), g(1), f (2), g(2), …, f (n), g(n), …

Diese Folge durchläuft alle Elemente von M ∪ N (Surjektivität), kann aber Wiederholungen enthalten, da die Mengen M und N nicht notwendig disjunkt sind (es kann M ∩ N ≠ ∅ gelten und sogar der Fall M = N ist nicht ausgeschlossen). Durch Streichen von Wiederholungen in (+) erhalten wir eine Folge

h(0), h(1), h(2), …, h(n), …,

die ebenfalls alle Elemente von M ∪ N durchläuft, aber nun wiederholungsfrei ist (Injektivität). (Da M und N als unendlich vorausgesetzt sind, ist die h-Folge ebenfalls unendlich.) Die so konstruierte Funktion h : ℕ → M ∪ N ist injektiv und surjektiv und damit eine Bijektion. Damit ist M ∪ N abzählbar.

zu (b):

Für jedes (n, m)  ∈  ℕ² nennen wir die natürliche Zahl

g(n, m) = n + m

das Gewicht des Paars (n, m). Wir zählen nun die Elemente des Kreuzprodukts ℕ × ℕ nach ihrem Gewicht wie folgt auf:

(0, 0),(Gewicht 1)

(0, 1), (1, 0),(Gewicht 1)

(0, 2), (1, 1), (2, 0),(Gewicht 2)

…

(0, k), (1, k − 1), …, (k − 1, 1), (k, 0),(Gewicht k)

…

Da jedes Paar ein Gewicht g besitzt und für jedes Gewicht k nur endlich viele Paare das Gewicht k haben, durchläuft die Aufzählung alle Elemente von ℕ² ohne Wiederholungen. Wir erhalten so eine Bijektion f : ℕ → ℕ². Damit ist ℕ² abzählbar unendlich.

Bemerkung: Diagonalaufzählung und Paarungsfunktion

Die Paar mit Gewicht k liegen auf einer Diagonalen im Gitter ℕ × ℕ. Die konstruierte Aufzählung f ist als Cantorsche Diagonalaufzählung von ℕ² bekannt, ihre Umkehrfunktion π = f ⁻¹ heißt das Cantorsche Paarungspolynom. Man kann zeigen, dass

π(n, m) = f ⁻¹(n, m) = ^{(n + m) (n + m + 1)}₂ + n

Zum Beispiel ist

π(2, 0) = ^{(2 + 0) (0 + 2 + 1)}₂ + 2 = 5

Das Paar (2, 0) ist das fünfte Element unserer Aufzählung.

Übung 2

Zeigen Sie, dass es unendliche Teilmengen A₀, A₁, …, A_n, …, n  ∈  ℕ, von ℕ gibt mit den Eigenschaften:

(a)	ℕ = ⋃_{n  ∈  ℕ} A_n (= { k \| es gibt ein n  ∈  ℕ mit k  ∈  A_n }),

(b)	A_n ∩ A_m = ∅ für alle n, m  ∈  ℕ mit n ≠ m.

Erste Lösung (Verwendung von Paaren)

Sei π : ℕ² → ℕ bijektiv (vgl. die obige Übung). Wir setzen für alle n  ∈  ℕ:

A_n = { π(n, m) | m  ∈  ℕ } = { π(n, 0), π(n, 1), π(n, 2), … }

Anschaulich ist A_n die Menge aller natürlichen Zahlen, die in der n-ten Spalte des gemäß π beschrifteten Gitters ℕ × ℕ stehen.

Da π injektiv ist, ist jede Menge A_n unendlich. Ebenfalls aufgrund der Injektivität von π sind die Mengen A_n paarweise disjunkt. Da π surjektiv ist, gibt es für jedes k  ∈  ℕ ein Paar (n, m) mit π(n, m) = k, sodass k  ∈  A_n. Dies zeigt, dass jede natürliche Zahl in genau einer Menge A_n vorkommt. Damit sind die Mengen A₀, A₁, A₂, … wie gewünscht.

Zweite Lösung (Verwendung von Primzahlen)

Für alle n ≥ 1 sei wieder z(n) der Zweifaktor von n, d. h. die maximale Anzahl der Zweiteilungen von n ohne Rest. Die Zahl z(n) ist der 2-Exponent der Primfaktorzerlegung von n, wobei z(n) = 0 gesetzt wird, wenn n ungerade ist. Weiter setzen wir z(0) = 0. Damit können wir nun definieren:

A_k = { n  ∈  ℕ | z(n) = k }

Es gilt zum Beispiel

A₀ = { 0 } ∪ { 1, 3, 5, 7, 9, … },

A₁ = { 2, 6, 10, 14, 18, … },

A₂ = { 4, 12, 20, 28, 36, … }.

Da jedes n ≥ 0 einen eindeutigen Wert z(n) besitzt, kommt jede natürliche Zahl in genau einer Menge A_k vor: Für alle n  ∈  ℕ gilt:

n  ∈  A_k genau dann, wenn k = z(n).

Zudem ist jede Menge A_k unendlich , da zum Beispiel

2^k 3⁰, 2^k 3¹, 2^k 3², …

Elemente von A_k sind.

Übung 3

Sei A eine Menge. Zeigen Sie, dass die folgenden Aussagen äquivalent sind:

(a)	Es gibt eine Injektion f : A → A, die nicht surjektiv ist.

(b)	Es gibt eine Injektion g : ℕ → A.

Lösung zur Übung 3

(a) impliziert (b):

Sei f : A → A injektiv, aber nicht surjektiv. Dann gibt es ein a  ∈  A mit a  ∉  rng(f). Wir definieren nun g : ℕ → ℕ rekursiv durch

g(0) = a, g(n + 1) = f (g(n)) für alle n  ∈  ℕ

Dann ist g injektiv. Annahme nicht. Dann gibt es ein kleinstes n mit:

(+) Es gibt ein m > n mit g(n) = g(m).

Sei m wie in (+), und sei m = m′ + 1. Es gilt n > 0, da sonst

a = g(0) = g(m)) = g(m′ + 1) = f (g(m))  ∈  rng(f)

Also gibt es ein n′ mit n = n′ + 1. Dann gilt

f (g(n′)) = g(n′ + 1) = g(n) = g(m) = g(m′ + 1) = f (g(m′))

Da f injektiv ist, gilt g(n′) = g(m′) mit m′ > n′, im Widerspruch zur Minimalität von n.

(b) impliziert (a):

Sei g : ℕ → A injektiv. Sei B = rng(g). Wir definieren h : B → B durch

h(g(n)) = g(n + 1) für alle n  ∈  ℕ

Dann ist h = g ∘ S ∘ g⁻¹ (mit der Nachfolgerfunktion S auf ℕ). Also ist h injektiv als Komposition von Injektionen. Wir definieren nun f : A → A durch

f (a) = h(a) für a  ∈  B, f (a) = a für alle a  ∈  A − B

Dann ist f = h ∪ id_A − B. Also ist f eine injektive Funktion als Vereinigung zweier Injektionen mit disjunkten Definitions- und Wertebereichen.

Übung 4

Wir betrachten die Menge

^ℝℝ = { f : ℝ → ℝ }

aller reellen Funktionen mit Definitionsbereich ℝ. Zeigen Sie:

(a)	Es gibt eine Injektion F : ℝ → ^ℝℝ.

(b)	Es gibt keine Surjektion F : ℝ → ^ℝℝ.

Bemerkung

Damit gilt |ℕ| < |ℝ| < |^ℝℝ|. Es gibt also, im Sinne der Mächtigkeitstheorie, mehr reelle Zahlen als natürliche Zahlen, und weiter mehr reelle Funktionen als reelle Zahlen.

Lösung zur Übung 4

zu (a):

Wir definieren F : ℝ → ^ℝℝ wie folgt. Für alle x  ∈  ℝ setzen wir

F(x) = const_x = „die Funktion f : ℝ → ℝ mit f (y) = x für alle y  ∈  ℝ“

Die Funktion F ordnet also jeder reellen Zahl x die konstante reelle Funktion mit dem konstanten Wert x zu.

Die Funktion F ist injektiv. Denn seien x, y  ∈  ℝ mit F(x) = F(y). Dann gilt

x = F(x)(0) = F(y)(0) = y

Dies zeigt, dass F injektiv ist.

zu (b):

Sei F : ℝ → ^ℝℝ beliebig. Wir konstruieren eine Funktion d : ℝ → ℝ mit d  ∉  rng(F). Zur Definition von d setzen wir

d(x) = F(x)(x) + 1 für alle x  ∈  ℝ

Ist nun x  ∈  ℝ beliebig, so gilt d ≠ F(x), da die Funktionen d und F(x) an der Stelle x nach Konstruktion verschieden sind. Dies zeigt, dass d  ∈  ^ℝℝ kein Element des Wertebereichs von F ist. Damit ist F nicht surjektiv.