1.2 Die Überabzählbarkeit von ℝ

Übung 1

(a)	Seien M und N abzählbar unendliche Mengen. Zeigen Sie, dass M ∪ N abzählbar unendlich ist. [ Hinweis: Orientieren Sie sich am Beweis der Abzählbarkeit von ℤ. ]

(b)	Zeigen Sie, dass die Menge ℕ² = { (n, m) \| n, m  ∈  ℕ } abzählbar ist. [ Hinweis: Orientieren Sie sich am Beweis der Abzählbarkeit von ℚ. ]

Übung 2

Seien A, B, C Mengen derart, dass A − B und A − C endlich sind. Zeigen Sie, dass A − (B ∩ C) endlich ist.

Übung 3

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.

Übung 4

Betrachten Sie den Beweis der Überabzählbarkeit der reellen Zahlen, und definieren Sie statt b_n die Ziffern c_n durch

$c_{n} = { \begin{matrix} 1 & falls a_{n,n} = 0, \\ 0 & falls a_{n,n} \neq 0. \end{matrix}$

Setzen Sie y* = 0, c₀ c₁ c₂ … Geben Sie nun reelle Zahlen x₀, x₁, x₂, … in Dezimaldarstellung an, für die y* = x₀ gilt. Begründen Sie, warum dieses Phänomen für die Zahl x* = 0, b₀ b₁ b₂ … des Beweises nicht auftreten kann.

Übung 5

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.

[ (a) impliziert (b): Wenden Sie wiederholt f auf ein a  ∈  A an, das nicht im Wertebereich von f liegt: a, f (a), f (f (a)), … Konstruieren Sie mit Hilfe dieser Folge eine Injektion g : ℕ → A.

(b) impliziert (a): Plus-Eins-Verschiebung auf ℕ wie beim Hilbertschen Hotel. ]

Übung 6

Zeigen Sie, dass die Menge

M = { (n₁, …, n_k) | k  ∈  ℕ, n_i  ∈  ℕ für alle 1 ≤ i ≤ k }

aller endlichen Tupel natürlicher Zahlen abzählbar ist.

Argumentieren Sie hiermit, dass (1) eine „Universalbibliothek“, die alle denkbaren Bücher enthält, abzählbar ist und dass (2) die reellen Zahlen, deren Nachkommastellen mit Hilfe eines Computerprogramms berechnet werden können, eine abzählbare Menge bilden.

[ Hinweis: Orientieren Sie sich am Beweis der Abzählbarkeit von 𝔸. ]

Übung 7

Beweisen Sie die Übungen 1(b) und die vorangehende Übung, indem Sie Zahlen der Form

2^a · 3^b bzw. p^a₁₁ · … · p^a_k_k

betrachten, mit natürlichen Exponenten a, b, a₁, …, a_k ≥ 1 und Primzahlen p₁ = 2, p₂ = 3, p₃ = 5, p₄ = 7, …

Übung 8

Betrachten Sie unendliche „Worte“ w, die aus den Zeichen a und b gebildet sind, etwa w = ababaaabbaa… Zeigen Sie durch ein Diagonalargument, dass die Menge aller dieser unendlichen Worte nicht abzählbar ist.

Übung 9

Zeigen Sie mit Hilfe der vorangehenden Übung, dass ℘(ℕ) = { A | A ⊆ ℕ } überabzählbar ist.

[ Hinweis: Überführen Sie Teilmengen von ℕ in unendliche 01-Worte. ]

Übung 10

Sei M = { 1, 2, 3, 4, 5 }. Geben Sie eine Funktion f : M → ℘(M) Ihrer Wahl an und bestimmen Sie D = { x  ∈  M | x  ∉  f (x) }.

Übung 11

Zeigen Sie, dass es injektive f : ℝ → ℘(ℕ) und g : ℘(ℕ) → ℝ gibt.

Übung 12

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.

Übung 13

Zeigen Sie:

|℘(℘(ℕ))| = |℘(ℝ)| = |{ f | f : ℝ → ℝ }|.