Definition der Abzählbarkeit Beweisen. Teilmengen von abzählbaren Mengen sind abzählbar

Question

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!

Comments

Verrätst du auch noch die Def. der Abzählbarkeit aus der Vorlesung?

Answer 1

Antwort mit KI erzeugt

Definition der Abzählbarkeit Beweisen

Um den Beweis anzugehen, dass Teilmengen abzählbarer Mengen ebenfalls abzählbar sind, müssen wir zuerst verstehen, was Abzählbarkeit bedeutet. Eine Menge \(M\) wird als *abzählbar unendlich* bezeichnet, wenn es eine Bijektion (eine-eindeutige Zuordnung) von \(M\) zu den natürlichen Zahlen \(\mathbb{N}\) gibt. Ist eine Menge endlich oder abzählbar unendlich, so wird sie insgesamt als abzählbar betrachtet.

Beweis

Gegeben ist eine Menge \(M\), die abzählbar ist, und eine nichtleere Teilmenge \(A \subset M\). Unser Ziel ist es zu zeigen, dass \(A\) auch abzählbar ist.

Da \(M\) abzählbar ist, gibt es eine injektive Funktion \(f: \mathbb{N} \rightarrow M\), die jeder natürlichen Zahl \(n\) ein einzigartiges Element in \(M\) zuordnet. Da \(A\) eine Teilmenge von \(M\) ist, beinhaltet \(A\) einige oder alle Elemente von \(M\), möglicherweise in einer anderen Reihenfolge.

1. Fall 1: \(A\) ist endlich.

Wenn \(A\) endlich ist, dann gibt es eine natürliche Zahl \(n\) so, dass wir eine Zuordnung von \(1\) bis \(n\) zu jedem Element in \(A\) schaffen können. Dies macht \(A\) trivialerweise abzählbar.

2. Fall 2: \(A\) ist unendlich.

Wenn \(A\) unendlich ist, konstruieren wir eine Zuordnung zur Menge der natürlichen Zahlen. Da \(A \subset M\) und \(M\) abzählbar ist, betrachten wir nur die Elemente von \(M\), die in \(A\) enthalten sind.

Wir definieren eine Funktion \(g: \mathbb{N} \rightarrow A\), indem wir \(g(n) = f(m_n)\), wobei \(m_n\) die \(n\)-te natürliche Zahl ist, für die \(f(m_n) \in A\). Diese Zahl existiert, da \(A\) nicht leer ist und \(f\) eine surjektive Abbildung von \(\mathbb{N}\) auf \(M\) darstellt. Mit anderen Worten, wir "überspringen" einfach die Elemente in \(M\), die nicht in \(A\) enthalten sind, wenn wir die Funktion \(g\) konstruieren.

Diese Funktion \(g\) ist injektiv, denn wenn \(g(n) = g(m)\), dann bedeutet dies, dass \(f(n) = f(m)\), da \(g(n) = f(m_n)\) und \(g(m) = f(m_m)\) für entsprechende \(m_n\) und \(m_m\) in \(\mathbb{N}\). Da \(f\) jedoch als bijektiv angenommen wird, folgt daraus, dass \(n = m\).

Somit haben wir gezeigt, dass für jede nichtleere Teilmenge \(A\) einer abzählbaren Menge \(M\) eine injektive Funktion von \(\mathbb{N}\) zu \(A\) existiert, was bedeutet, dass \(A\) abzählbar ist.

Zusammenfassend halten wir fest: Jede nichtleere Teilmenge \(A\) einer abzählbaren Menge \(M\) ist entweder endlich oder unendlich abzählbar, abhängig davon, ob \(A\) selbst endlich oder unendlich ist. In jedem Fall erfüllt \(A\) die Bedingung der Abzählbarkeit.