Eine Menge bezeichnet man als abzählbar (oder abzählbar unendlich), wenn sie gleichmächtig zur Menge der natürlichen Zahlen ist.
Mathematiker sprechen von der Kardinalität oder Mächtigkeit einer Menge, verallgemeinern damit den von endlichen Mengen bekannten Begriff der Anzahl. Diese Begriffe werden dadurch notwendig, dass anders, als im Fall endlicher Mengen, der Fall hier komplizierter ist. Georg Cantor schrieb bahnbrechende Arbeiten auf diesem Gebiet.
Definition
Eine Menge A, die höchstens gleichmächtig zu 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 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 . (Also Tupel ganzer Zahlen).
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.
Beispiele abzählbar unendlicher Mengen
Natürliche Zahlen
Die Menge der natürlichen Zahlen ( ) ist abzählbar unendlich:
Die Unendlichkeit ist klar: Man denke sich eine größte Zahl n, dann findet man sofort eine noch größere Zahl n+1 die ebenfalls in der Menge der natürlichen Zahlen liegt.
Man kann auch jeder Zahl aus der Menge der natürlichen Zahlen in eindeutiger, umkehrbarer Weise (also bijektiv) eine natürliche Zahl zuordnen. Dafür benötigt man zwar unendlich lange und auch unendlich große Zahlen, aber es ist prinzipiell möglich. Damit kann man die Menge der natürlichen Zahlen abzählen.
Die Menge aller Paare natürlicher Zahlen
Auch die Menge aller Paare (i,j) ( ) von zwei natürlichen Zahlen ist abzählbar unendlich.
Die Unendlichkeit ist wiederum offensichtlich. Schwieriger ist die Frage der Abzählbarkeit. Dafür nutzt man die Cantorsche Paarungsfunktion, die jedem Zahlenpaar (i,j) bijektiv eine natürliche Zahl k zuordnet. Damit kann man alle Zahlenpaare eindeutig nummerieren und somit abzählen.
Die Menge aller n-Tupel natürlicher Zahlen
Die Menge aller n-Tupel natürlicher Zahlen ( ) ist ebenfalls abzählbar unendlich. Das zeigt man wiederum durch Anwendung der Cantorschen Paarungsfunktion.
Die Menge aller rationalen Zahlen
Auch die Menge aller rationalen Zahlen ( ), also aller Zahlen, die sich durch einen Bruch darstellen lassen, ist abzählbar unendlich:
Man definiert eine Zahl durch die drei Zahlen in folgender Weise: . Damit erhält man einen 3-Tupel natürlicher Zahlen. Die Menge der 3-Tupel der natürlichen Zahlen ist abzählbar.
Im logischen Schluß sind damit auch alle n-Tupel rationaler Zahlen abzählbar unendlich.
Die Menge der Worte über einem Alphabet
Durch die Anwendung der sogenannten Standardnummerierung über das Alphabet kann man auch die Worte einer Sprache im Sinne der Mathematik abzählen.
Die Menge aller berechenbaren Zahlenfunktionen
Die Menge aller berechenbaren Zahlenfunktionen ist abzählbar unendlich. Man kann eine Standardnummerierung aller denkbaren Bandprogramme angeben. Da die Menge der Bandprogramme gerade die Menge der berechenbaren Funktionen ist, sind damit die Zahlenfunktionen abzählbar unendlich.
Beispiel einer überabzählbaren unendlichen Mengen
Die Menge aller reeller Zahlen ist überabzählbar.
