Mächtigkeiten
Injektionen und Bijektion eignen sich für den Größenvergleich von beliebigen Mengen:
Notation | Definition | Lesart |
|A| ≤ |B| | ∃f f : A → B injektiv | die Mächtigkeit von A ist kleinergleich der Mächtigkeit von B |
|A| = |B| | ∃f f : A → B bijektiv | A und B sind gleichmächtig |
|A| < |B| | |A| ≤ |B| ∧ |A| ≠ |B| | die Mächtigkeit von A ist kleiner als die Mächtigkeit von B |
|A| = n | |A| = |{ 0, …, n − 1 }| | die Mächtigkeit von A ist n, A ist n-elementig |
Der Vergleich einer Menge mit der Menge ℕ der natürlichen Zahlen führt zu folgenden Begriffen:
Begriff | Definition |
A ist endlich | |A| < |ℕ| |
A ist abzählbar | |A| ≤ |ℕ| |
A ist abzählbar unendlich | |A| = |ℕ| |
A ist (Dedekind-)unendlich | |ℕ| ≤ |A| |
A ist überabzählbar | |ℕ| < |A| |
Eine endliche Menge A ist ausgezeichnet durch:
Ist f : A → A, so sind die Eigenschaften injektiv, surjektiv, bijektiv äquivalent.
Diese Eigenschaft ist bekannt als Schubfachprinzip. Ist dagegen A unendlich, so gibt es eine Injektion f : A → A, die keine Surjektion ist.
Die Elemente einer endlichen Menge lassen sich in der Form a1, …, an aufzählen. Die abzählbare Unendlichkeit einer Menge A bedeutet, dass es eine Aufzählung a0, a1, a2, …, an, … aller Elemente von A gibt. Dagegen bedeutet die Überabzählbarkeit von A, dass für jede Folge a0, a1, …, an, … in A ein a ∈ A existiert, das in der Aufzählung nicht vorkommt.
Die folgende Tabelle enthält einige fundamentale Ergebnisse der Mächtigkeitstheorie:
Ergebnis | Name |
|ℕ| = |ℚ| = |𝔸| | Abzählbarkeit der rationalen und algebraischen Zahlen |
|ℕ| < |ℝ| | Überabzählbarkeit von ℝ |
|ℝ| = |ℝn| | Gleichmächtigkeit verschiedendimensionaler Kontinua |
|A| ≤ |B| ∧ |B| ≤ |A| → |A| = |B| | Satz von Cantor-(Dedekind-)Bernstein |
|A| < |℘(A)| | Satz von Cantor |
|A| ≤ |B| ∨ |B| ≤ |A| | Vergleichbarkeitssatz |