Abzählbarkeit

Eine Menge bezeichnet man als abzählbar (oder abzählbar unendlich), wenn sie gleichmächtig zur Menge der natürlichen Zahlen ist.

Eine Menge A, die höchstens gleichmächtig zu N ist, heißt höchstens abzählbar. Oft jedoch wird abzählbar als höchstens abzählbar definiert, während eine Menge, die gleichmächtig zu N ist, abzählbar unendlich genannt wird. Dies macht die Formulierung vieler Beweise etwas einfacher.

Georg Cantor zeigte mit der so genannten Cantor-Diagonalisierung dass die Menge der rationalen Zahlen abzählbar ist, ebenso jede Menge der Gestalt

Die Menge der reellen Zahlen ist dagegen überabzählbar. Es gibt also keine bijektive Abbildung, die jede reelle Zahl auf je eine natürliche Zahl abbildet.

Siehe auch: Mächtigkeit, Kardinalzahl (Mathematik), Unendlichkeit, Hilberts Hotel