Beweisen Sie, dass die Menge aller endlichen Teilmengen von N abzählbar ist.

Question

Aufgabe:

Beweisen Sie, dass die Menge aller endlichen Teilmengen von N abzählbar ist.

Problem/Ansatz:

Also \( P(\mathrm{~N}) \) (die Menge aller Teilmengen von \( \mathrm{N} \) ) ist überabzählbar, da die Funktion \( f: \mathrm{N} \rightarrow P(\mathrm{~N}) \) definiert durch \( f(n)=\{n\} \) nicht bijetiv ist, so stehts im Skript.

Wie das ganze nun mit der Menge von ENDLICHEN Teilmengen aussieht, darauf komm ich nicht.

Die Funktion \( f(n)=\{n\} \) müsste ja dann bijektiv sein, also \( |\mathrm{N}|=|P(\mathrm{~N})| \), dann dürfte ja auf jedes Element \( n \in \mathbb{N} \) nur ein Element von \( P(\mathrm{~N}) \) also nur eine Teilmenge abgebildet werden?

Answer 1

Versuche eine Folge \( \left(a_{n}\right)_{n \in \mathrm{N}} \) von endl. Teilmengen von \( \mathrm{N} \) zu konstruieren, so dass alle endl. Teilmengen von \( \mathrm{N} \) in der Folge vorkommen.

Dann ist \( \varphi(n)=a_{n} \) eine bijektion von \( \mathrm{N} \) auf die endlichen Teilmengen von \( \mathrm{N} \)

Wir wollen alle endlichen Mengen in \( \mathbb{N} \) abzählen. Die Idee ist, dass wir die endl. Mengen durch ihr grösstes Element klassifizieren, um sie später abzuzählen. Wir identifizieren nun also alle Mengen die \( k \) als grösstes Element haben mit der Zahl \( k \); oder - ein wenig mathematischer ausgedrückt, wir definieren die Menge:

\( M_{k}:=\{A \subset \mathbb{N} \| A \mid<\infty, \max (A)=k\} \)
Wir haben also ein paar Beispiele:
\( M_{0}:\{0\} \)
\( M_{1}:\{1\},\{0,1\} \)
\( M_{2}:\{2\},\{0,2\},\{1,2\},\{0,1,2\} \)
Wenn wir nun noch die leere Menge betrachten: \{\} dann sehen wir, dass \( M_{2} \) dadurch entsteht, dass wir \( M_{1} \) und \{\} nehmen und die Mengen darin jeweils mit der 2 erweitern:
\( M_{2}=\{2\} \cup\left(\{2\} \cup M_{1}\right) \)

Also hat \( M_{1} \) ein Element, \( M_{2} 2 \) Elemente und \( M_{k} \) hat \( k \) Elemente.

Da alle endlichen Mengen \( M_{k} \) abzhählbar sind und die Menge aller \( M_{k} \) auch abzählbar ist, ist die Vereinigung aller \( M_{k} \) auch abzählbar; und dies sind genau alle endlichen Ungermengen von \( \mathbb{N} \).

Natürlich ist das oben noch kein richtiger Beweis; ich habe eher meinen Gedankengang niedergeschrieben als ich über die Aufgabe nachdachte. Die Grundidee ist, dass du erkennst wie man endliche Mengen induktiv klassifiziert: Durch ihr grösstes Element.

Müsstest du die endlichen Mengen von \( Z \) klassifizieren, würdest du den grössten Betrag eines Elements der Mengen nehmen und du würdest auf ein ähnliches Resultat kommen.

Wenn du magst, kannst du für den Beweis auch ein Lemma beweisen, dass die Vereinigung endlicher Mengen abzählbar ist. Wenn du das hast, kannst du mit dem obigen Argument mehr oder weniger direkt Beweisen, dass die endl. Mengen von N abzählbar sind.