Abzählbar

Mengen, deren Elemente man eins zu eins den natürlichen Zahlen 0, 1, 2, 3, ... zuordnen kann, heißen abzählbar. Man kann die Elemente gewissermaßen erschöpfend mit den natürlichen Zahlen abzählen. "Erschöpfend" heißt, dass jedes Element der Menge irgendwann an die Reihe kommt.

Beispiel: Die Menge aller (nicht leeren) Zeichenketten, die man aus den Buchstaben von a bis z bilden kann (wobei jeder Buchstabe beliebig oft verwendet werden darf), ist abzählbar, denn man kann die Zeichenketten aufsteigend nach ihrer Länge und bei gleicher Länge alphabetisch ordnen und in dieser Reihenfolge abzählen.

Dass man beim Abzählen der Elemente mit 0 beginnt und nicht (wie beim "normalen" Zählen im Endlichen) mit 1, liegt daran, dass die 0 üblicherweise zu den natürlichen Zahlen gerechnet wird. Beim Abzählen unendlich vieler Elemente ist es aber unerheblich, ob man mit 0 oder 1 beginnt.

Ein nicht so offensichtliches Beispiel für eine abzählbare Menge ist Q,  die Menge aller rationalen Zahlen (Bruchzahlen). Jede rationale Zahl hat eine eindeutige Darstellung als gekürzter Bruch, wenn wir das Vorzeichen ausschließlich im Zähler zulassen. Die rationalen Zahlen lassen sich also in einem zweidimensionalen Schema anordnen, wobei der Nenner je Zeile konstant bleibt und der Zähler betragsmäßig wächst. Die Elemente in diesem Schema können dann diagonalenweise mit den natürlichen Zahlen abgezählt werden.

Dieser Beweis der Abzählbarkeit von Q ist auch als "Cantors erstes Diagonalargument" bekannt.