Eine Menge bezeichnet man als abzählbar (oder abzählbar unendlich), wenn sie gleichmächtig zur Menge dernatü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 (i₁,i₂,...,i_n) 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 einerSprache 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 größer als die Menge der berechenbaren Funktionen ist (es könnte ja zwei unterschiedliche Programme geben, die dieselbe Funktion berechnen), sind damit die Zahlenfunktionen abzählbar unendlich.

Beispiel einer überabzählbaren unendlichen Mengen

Die Menge aller reeller Zahlen ist überabzählbar.

Siehe auch

• Mächtigkeit
• Kardinalzahl (Mathematik)
• Unendlichkeit
• Hilberts Hotel