Beweisen Sie Beispiel \( 2.26 \) (b) des Skriptes anhand der Definition der Abzählbarkeit:
Ist \( \emptyset \neq A \subset M \) und \( M \) abzählbar. Dann ist auch \( A \) abzählbar.
Beispiel.
(a) Klar: Endliche Mengen sind abzählbar.
(b) Ist \( \emptyset \neq A \subset M \) und \( M \) abzählbar. Dann ist auch \( A \) abzählbar. Somit ist jede Teilmenge von \( \mathbb{N} \) abzählbar, wie z.B. \( \{2,4,6,8, \ldots\} \) (Übung).
(c) Sei \( M \) die Menge der Folgen in \( \{0,1\} \), d.h.
\( \left(a_{n}\right)_{n \in \mathbb{N}} \in M \quad \Leftrightarrow \quad \forall n \in \mathbb{N}: a_{n} \in\{0,1\} \)
Dann ist \( M \) überabzählbar. Nehmen wir an dies ist nicht der Fall, dann ist \( M \) darstellbar durch \( M:\left\{b_{1}, b_{2}, b_{3}, \ldots\right\} \) mit \( b_{j}=\left(a_{j 1}, a_{j 2}, a_{j 3}, \ldots\right) \) und \( a_{j k} \in\{0,1\} \)
Setze
\( a_{n}:=\begin{array}{r} 1, \text { falls } a_{n n}=0 \\ 0, \text { falls } a_{n n}=1 \end{array} \)
Nach Definition gilt \( \left(a_{n}\right)_{n \in \mathbb{N}} \in M \). Also muss es ein \( m \in \mathbb{N} \) geben mit
\( \left(a_{m 1}, a_{m 2}, \ldots\right)=b_{m}=\left(a_{n}\right)=\left(a_{1}, a_{2}, \ldots\right) \)
d.h. insbesondere \( a_{m m}=a_{m} . \) Widerspruch!