Warum ist die Menge aller endlichen Teilmengen von N(natürliche Zahlen) abzählbar unendlich?
Weiß jemand die Antwort und eventuell auch wie man das beweisen kann ?
3 Antworten
Du zeigst für jede Zahl n, dass die Menge aller n-elementigen Teilmengen abzählbar ist, und dann ist deine Menge als abzählbare Vereinigung abzählbarer Mengen wieder abzählbar.
Siehe die Antwort von iokii.
-----
Zu jedem n ∈ ℕ₀ ist die Anzahl aller Teilmengen von ℕ, deren größtes Element n ist, endlich.
Die Menge aller endlichen Teilmengen von ℕ ist damit eine abzählbare Vereinigung endlicher Mengen.
-----
Suche eine injektive Abbildung der Menge der endlichen Teilmengen von ℕ in eine bekannt abzählbare Menge, damit ist die Menge der endlichen Teilmengen von ℕ auch höchstens abzählbar.
Z. B. sei p_k die k-te Primzahl (p_0 := 2, p_1 = 3, ...)
Dann bilden wir (M sei die Menge der endlichen Teilmengen von ℕ):
f: M -> ℕ
m |-> Π(k ∈ m) p_k
Wegen der Eindeutigkeit der Primzahlzerlegung ist diese Funktion injektiv
Für eine feste Zahl n ist die Menge aller Teilmengen mit den Zahlen von 1..n endlich. Die Vereinigung von abzahlbar vielen endlichen Mengen ist aber in jedem Fall abzählbar.