Die Menge der einelementigen Teilmengen von ℕ ist abzählbar.
Ist die Menge der höchstens n-elementigen Teilmengen von ℕ abzählbar, dann ist auch die Menge der höchstens n+1-elemetigen Teilmengen abzählbar (Beweis wie bei Cantors ersten Diagonalargument).
Per vollständiger Induktion folgt, dass die Menge E der endlichen Teilmengen von ℕ abzählbar ist.
Es gibt eine Bijektion zwischen E und C: = {A ⊂ ℕ | ∃U⊂P<∞(ℕ) A = ℕ\U}, der Menge der Teilmengen von ℕ mit endlichen Komplement. Also ist auch C abzählbar.
M = E ∪ C ist als Vereinigung von abzählbaren Mengen ebenfalls abzählbar.
