Abzählbare Menge

In der Mengenlehre wird eine Menge  als abzählbar unendlich bezeichnet, wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen . Dies bedeutet, dass es eine Bijektion zwischen  und der Menge der natürlichen Zahlen gibt, die Elemente der Menge  also „durchnummeriert“ werden können.

Zu den höchstens abzählbaren Mengen zählen neben den abzählbar unendlichen Mengen auch die endlichen Mengen. Die Verwendung des Begriffes abzählbar ist nicht einheitlich. Er kann je nach Definition sowohl abzählbar unendlich als auch höchstens abzählbar bedeuten.

Eine Menge, die weder endlich noch abzählbar unendlich ist, wird als überabzählbar bezeichnet.

Die Mächtigkeit einer abzählbar unendlichen Menge wird – als Kardinalzahl – mit  (gesprochen: alef null) bezeichnet, etwa gilt . Zu dieser Bezeichnung siehe auch Aleph-Funktion.

Beispiele abzählbar unendlicher Mengen

Natürliche Zahlen 
Die Menge der natürlichen Zahlen  ist per Definition abzählbar unendlich, da sie dieselbe Mächtigkeit wie sie selbst besitzt.

Primzahlen 
Die Menge der Primzahlen  ist ebenfalls abzählbar unendlich, da sie eine Teilmenge der natürlichen Zahlen und nach dem Satz von Euklid auch unendlich ist.

Ganze Zahlen 
Die Menge der ganzen Zahlen  ist abzählbar unendlich, eine Abzählung ist beispielsweise durch die Funktion

gegeben mit der Wertetabelle: 

Die Beispiele Primzahlen und ganze Zahlen zeigen, dass bei einer unendlichen Grundmenge sowohl echte Teilmengen als auch Obermengen dieselbe Mächtigkeit besitzen können wie die Grundmenge, im Gegensatz zu den Verhältnissen bei endlichen Mengen.

Paare natürlicher Zahlen 
Auch die Menge aller Paare  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  bijektiv eine natürliche Zahl  zuordnet. Damit kann man alle Zahlenpaare eindeutig nummerieren und somit abzählen.

n-Tupel natürlicher Zahlen 
Die Menge aller -Tupel  natürlicher Zahlen  ist ebenfalls abzählbar unendlich. Das zeigt man wiederum durch -malige Anwendung der Cantorschen Paarungsfunktion.

Rationale Zahlen 
Georg Cantor zeigte mit dem so genannten ersten Diagonalargument, dass die Menge der rationalen Zahlen abzählbar ist, ebenso jede Menge der Gestalt  (Tupel ganzer Zahlen).

Die Abbildung ,  ist surjektiv, also ist die Mächtigkeit von  höchstens so groß wie die von . Da es einerseits unendlich viele Brüche gibt und andererseits die Menge  abzählbar unendlich ist, ist auch  abzählbar unendlich.

Mit der Stern-Brocot-Folge kann in einfacher Weise eine Bijektion zwischen ℕ und ℚ angegeben werden, was die Abzählbarkeit der rationalen Zahlen ebenfalls beweist.

Algebraische Zahlen 
Eine algebraische Zahl ist Nullstelle eines Polynoms  mit ganzzahligen Koeffizienten. Die Höhe von  sei definiert als .

Zu jeder vorgegebenen Höhe  gibt es nur endlich viele Polynome, welche wiederum nur endlich viele Nullstellen besitzen; für jedes dieser k hat mit  das Polynom  die Nullstelle . Wird  als die Menge aller dieser Nullstellen gesetzt, dann ist die Menge  der algebraischen Zahlen die Vereinigung .

Als abzählbare Vereinigung endlicher Mengen ist  daher abzählbar. Da  andererseits  enthält, ist  abzählbar unendlich.

Wörter über einem Alphabet 
Durch die Anwendung der sogenannten Standardnummerierung über das Alphabet  kann man auch die Wörter einer Sprache im Sinne der Mathematik abzählen.

Berechenbare 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 Menge 
Die Menge der reellen Zahlen ist dagegen überabzählbar. Das bedeutet, dass es keine bijektive Abbildung gibt, die jede reelle Zahl auf je eine natürliche Zahl abbildet, siehe Cantors zweites Diagonalargument.

Eigenschaften 
 Jede Teilmenge einer (höchstens) abzählbaren Menge ist (höchstens) abzählbar.
 Die Vereinigung zweier (höchstens) abzählbarer Mengen ist (höchstens) abzählbar.
 Allgemeiner ist jede Vereinigung einer abzählbaren Anzahl von (höchstens) abzählbaren Mengen wieder (höchstens) abzählbar.
 Das kartesische Produkt zweier (höchstens) abzählbaren Mengen ist (höchstens) abzählbar.
 Gibt es eine Surjektion von der Menge  der natürlichen Zahlen auf die Menge , so ist  höchstens abzählbar.
 Jede aufzählbare Menge ist höchstens abzählbar.

Siehe auch 
 In der Topologie erfüllen „kleine“ topologische Räume ein Abzählbarkeitsaxiom.
 Kardinalzahl (Mathematik)

Einzelnachweise 

Mengenlehre