Die rationalen Zahlen sind abzählbar

Satz (Abzählbarkeit der rationalen Zahlen)

ℚ ist abzählbar.

Beweis

Für q  ∈  ℚ seien N(q)  ∈  ℕ der Nenner und Z(q)  ∈  ℕ der Zähler des gekürzten Bruches |q|, wobei |q| = q für q ≥ 0, |q| = − q für q < 0.

Wir setzen für n  ∈  ℕ

A_n = { q  ∈  ℚ | N(q) + Z(q) = n }.

Dann ist jedes A_n abzählbar (sogar endlich), und

ℚ = ⋃_{n  ∈  ℕ} A_n.

Also ist ℚ abzählbar.

Hinter diesem Beweis steht die folgende „Spiralaufzählung“ des ℤ²-Gitters. Für n  ∈  ℕ setzen wir:

A′_n = { (a, b)  ∈  ℝ² | |a| + |b| = n }

Die Mengen A′_n sind Quadrate im ℝ² mit den Ecken (n, 0), (0, n), (−n, 0), (0, −n). Vom Nullpunkt ausgehend können wir nun die Schnittpunkte dieser Quadrate mit dem ℤ²-Gitter „spiralförmig“ aufzählen. Der Leser kann leicht die ersten Brüche einer solchen Aufzählung ermitteln.

Viele andere Arten von Aufzählungen von ℚ sind denkbar, etwa Abzählungen nach dem Maximum von Zähler und Nenner eines gekürzten Bruches, was dem um 45 Grad gedrehten Bild oben entsprechen würde. Beschränken wir uns auf rationale Zahlen q mit 0 ≤ q ≤ 1, und ordnen wir bei gleichem Maximum nach aufsteigenden Zählern, so beginnt die Liste wie folgt:

⁰₁ ¹₁ ¹₂ ¹₃ ²₃ ¹₄ ³₄ ¹₅ ²₅ ³₅ ⁴₅ ¹₆ ⁵₆ ¹₇ …

In dieser algebraischen Form ist die Abzählbarkeit von ℚ einleuchtend. Überraschender ist sie, wenn man sich ℚ als Teilmenge der Zahlengeraden ℝ vorstellt. Die Punkte von ℚ sind dicht gesät in ℝ:

Übung

ℚ ist dicht in ℝ, d. h. für alle x, y  ∈  ℝ mit x < y existiert ein q  ∈  ℚ mit x < q < y.

[ Verwenden Sie z. B. Dezimalbruchentwicklungen von x, y, und interpolieren Sie eine Zahl q mit abbrechender Dezimalbruchentwicklung, also ein q  ∈  ℚ.]

Hausdorff (1914):

„Die Äquivalenz der Menge der ganzen Zahlen mit der doch viel umfassenderen der rationalen Zahlen gehört mit zu den Tatsachen der Mengenlehre, die bei erster Bekanntschaft den Eindruck des Erstaunlichen, ja Paradoxen hervorrufen: namentlich wenn man das geometrische Bild (die Zuordnung zwischen Zahlen und Punkten der geraden Linie) vor Augen hat und sich einerseits die in endlichen Abständen isoliert liegenden ‚ganzzahligen‘ Punkte, andererseits die über die ganze Linie wie ein Staub von mehr als mikroskopischer Feinheit verteilten ‚rationalen‘ Punkte vergegenwärtigt.“

Aus der Dichtheit von ℚ in ℝ zu schließen, dass auch ℝ abzählbar ist, ist zwar auf den ersten Blick verführerisch, aber unstatthaft: Zwei geordnete Mengen als gleichgroß zu bezeichnen, wenn zwischen zwei verschiedenen Punkten der einen immer Punkte der anderen liegen, wäre kein guter Größenbegriff, und dieser Begriff hat mit der Existenz von Bijektionen i. A. nichts zu tun. (Der Autor erhält regelmäßig Zuschriften, in denen die Abzählbarkeit von ℝ durch „ℚ ist dicht in ℝ“ bewiesen wird. Daher dieser vorbeugende Absatz.)