Abzählbarkeit

Eine Menge bezeichnet man als abzählbar (oder abzählbar unendlich), wenn sie die gleiche Mächtigkeit hat wie die Menge der natürlichen Zahlen.

Der mathematische Begriff „Mächtigkeit“ (oder „Kardinalität“) einer Menge verallgemeinert den von endlichen Mengen bekannten Begriff der Anzahl.

Definition

Es gibt zwei leicht unterschiedliche Definitionen des Begriffs „abzählbar“:

Eine Menge $A$ heißt abzählbar, wenn sie die gleiche Mächtigkeit hat wie $\mathbb{N}$ oder wie eine Teilmenge von $\mathbb{N}$ . Der Begriff „abzählbar“ umfasst dann auch die endlichen Mengen. Abzählbare nicht endliche Mengen heißen in dieser Terminologie abzählbar unendlich.
Eine Menge $A$ heißt abzählbar, wenn sie die gleiche Mächtigkeit wie $\mathbb{N}$ hat. Als Zusammenfassung für endliche und abzählbare Mengen wird dann der Begriff höchstens abzählbar verwendet.

Von Fall zu Fall macht die eine oder die andere Definition die Formulierung eines Beweises etwas einfacher. Im Folgenden wird nur die zweite Definition verwendet.

Georg Cantor zeigte mit der so genannten Cantor-Diagonalisierung, dass die Menge der rationalen Zahlen abzählbar ist, ebenso jede Menge der Gestalt $\mathbb{Z}^n$ (Tupel ganzer Zahlen).

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.

Beispiele abzählbar unendlicher Mengen

Natürliche Zahlen

Die Menge der natürlichen Zahlen ( $\mathbb{N}$ ) 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: Nämlich genau diese Zahl selbst. Damit kann man die Menge der natürlichen Zahlen abzählen.

Ganze Zahlen

Die Menge der ganzen Zahlen ( $\mathbb{Z}$ ) ist abzählbar unendlich, eine Abzählung ist beispielsweise gegeben durch

$n$	1	2	3	4	5	6	7	8	…
$f(n)$	0	1	−1	2	−2	3	−3	4	…

Man kann diese Abbildung und ihre Umkehrabbildung auch durch Formeln wie

f(n)=(-1)^n\cdot\left\lfloor\frac n2\right\rfloor

beschreiben; darauf kommt es jedoch nicht an, die bloße Existenz genügt.

Die Menge aller Paare natürlicher Zahlen

Auch die Menge aller Paare $(i,j)$ ( $\mathbb{N} \times \mathbb{N}$ ) 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_1, i_2, \ldots, i_n)$ natürlicher Zahlen ( $\mathbb{N}^n$ ) ist ebenfalls abzählbar unendlich. Das zeigt man wiederum durch Anwendung der Cantorsche Paarungsfunktion.

Die Menge aller rationalen Zahlen

Auch die Menge $\mathbb{Q}$ aller rationaler Zahlen, also die Menge aller Brüche, ist abzählbar unendlich: Die Abbildung $\mathbb{N}_0^3\rightarrow\mathbb{Q}$ , $(i, j, k)\mapsto$ ist surjektiv, also ist die Mächtigkeit von $\mathbb{Q}$ höchstens so groß wie die von $\mathbb{N}_0^3$ . Da es einerseits unendlich viele Brüche gibt, und andererseits die Menge $\mathbb{N}_0^3$ abzählbar unendlich ist, ist auch $\mathbb{Q}$ abzählbar unendlich.

Die Menge der Wörter über einem Alphabet

Durch die Anwendung der sogenannten Standardnummerierung über das Alphabet $\Sigma$ kann man auch die Wörter 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 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 aller reeller Zahlen $\mathbb{R}$ ist überabzählbar (siehe auch Kontinuumshypothese).

Eigenschaften

Jede aufzählbare Menge ist auch abzählbar.

Siehe auch

Mengenlehre

Gourt Home::Gourt :: Abzählbarkeit