1.10 Mächtigkeitsvergleiche

Definition (Mächtigkeitsbegriffe)

Mächtigkeitsvergleich

Für Mengen A, B definieren wir:

|A| ≤ |B|, falls es gibt eine Injektion f : A → B,

|A| = |B|, falls es gibt eine Bijektion f : A → B,

|A| < |B|, falls |A| ≤ |B| und |A| ≠ |B|.

Gilt |A| ≤ |B| (|A| < |B|), so sagen wir, dass die Mächtigkeit von A kleinergleich (kleiner) der Mächtigkeit von B ist. Gilt |A| = |B|, so sagen wir, dass A und B gleichmächtig sind oder die gleiche Mächtigkeit besitzen.

Endlichkeit, Unendlichkeit, Abzählbarkeit, Überabzählbarkeit

Eine Menge A heißt

endlich,	falls \|A\| < \|ℕ\|,
abzählbar,	falls \|A\| ≤ \|ℕ\|,
unendlich,	falls \|ℕ\| ≤ \|A\|,
abzählbar unendlich,	falls \|A\| = \|ℕ\|,
überabzählbar,	falls \|ℕ\| < \|A\|.

Die Mächtigkeit von A ist kleinergleich der Mächtigkeit von B, falls es eine Injektion von A nach B gibt. Anschaulich passt dann die Menge A in die Menge B hinein. Aus dem Mächtigkeitsvergleich |A| ≤ |B| folgt alles Weitere, denn die Gleichmächtigkeit |A| = |B| ist äquivalent zu |A| ≤ |B| und |B| ≤ |A| (Satz von Cantor-Bernstein). Insgesamt ergibt sich aus den Abbildungseigenschaften „injektiv, surjektiv, bijektiv“ eine Größenlehre für Mengen ohne Verwendung von Zahlen.

Die Abbildungseigenschaften „injektiv, surjektiv, bijektiv“ sind geeignet, zwei Mengen ihrer Größe nach zu vergleichen, ohne ihre Elemente zählen zu müssen. Anschaulich bedeutet |A| ≤ |B|, dass jedes Element von A einen Partner in B findet, wenn ein geschickter Vermittler f die Zuordnung übernimmt. Die Gleichmächtigkeit |A| = |B| bedeutet, dass die Elemente von A mit den Elementen von B vollständig gepaart werden. Und |A| < |B| bedeutet, dass eine Partnerfindung wie in |A| ≤ |B| möglich ist, aber jede Partnerfindung einsame b in B zurücklässt.

Die Endlichkeit einer Menge A ist äquivalent dazu, dass A in der Form A = { a₁, …, a_n } mit paarweise verschiedenen a_k geschrieben werden kann (wobei n = 0 für A = ∅ zugelassen ist). Man schreibt dann auch |A| = n. Für endliche Mengen gilt:

Dirichletsches Schubfach- oder Taubenschlagprinzip

Sind A, B endlich mit |A| = |B| und ist f : A → B, so sind äquivalent:

(a) f : A → B ist injektiv, (b) f : A → B ist surjektiv, (c) f : A → B ist bijektiv.

Die Bezeichnung „Schubfachprinzip“ lässt sich wie folgt illustrieren:

Beispiel

Verteilt man n Kugeln a₁, …, a_n auf m < n Fächer, so gibt es ein Fach, das mindestens zwei Kugeln enthält. Denn sonst wäre f : { a₁, …, a_n } → { 1, …, n } mit f (a_k) = „die Fachnummer von a_k“ injektiv, aber wegen m < n nicht surjektiv.

Diese Ergebnisse sind anschaulich klar. Große Überraschungen bergen dagegen die unendlichen Mengen. Man kann zeigen:

|ℕ| = |ℤ| = |ℚ| = |ℕ²| = |ℕ³| = |⋃_{n  ∈  ℕ} ℕⁿ|,

wobei die letzte Menge die Menge aller endlichen Tupel natürlicher Zahlen ist und damit über eine geeignete Zahlenkodierung von Buchstaben und Satzzeichen jedes Buch (aufgefasst als Zeichenfolge) als Element enthält. Eine Universalbibliothek, die alle Bücher enthält, ist abzählbar. Dagegen zeigt man in der Analysis, dass die reellen Zahlen überabzählbar sind: |ℕ| < |ℝ|. Dieses Ergebnis kann man auch so formulieren:

Jede Folge x₀, x₁, x₂, …, x_n, … reeller Zahlen lässt eine reelle Zahl aus.

Ebenso gilt |ℝ| < |ℝ^ℝ|, sodass gilt:

Jede Familie (f_x)_{x  ∈  ℝ} reeller Funktionen f_x : ℝ → ℝ lässt eine reelle Funktion aus.

Es gibt also auch im Unendlichen verschiedene Mächtigkeitsstufen. Wichtige allgemeine Ergebnisse der Mächtigkeitstheorie, die für alle Mengen A, B gelten, sind:

|A| < |℘(A)| (Satz von Cantor)

|A| ≤ |B| und |B| ≤ |A| impliziert |A| = |B| (Satz von Cantor-Bernstein)

|A| ≤ |B| oder |B| ≤ |A| (Vergleichbarkeitssatz von Cantor-Zermelo)

Während die beiden ersten Sätze trickreich, aber elementar bewiesen werden können, müssen zum Beweis des Vergleichbarkeitssatzes schwere Geschütze aufgefahren werden. Der Satz ist äquivalent zum Auswahlaxiom, das wir nun besprechen werden.