Mächtigkeitsvergleiche
Licht ins Reich des Unendlichen bringt:
Definition (Mächtigkeitsvergleiche)
Seien A, B Mengen. Wir setzen
| |A| ≤ |B| | falls es gibt ein injektives f : A → B |
| |A| = |B| | falls es gibt ein bijektives f : A → B |
| |A| < |B| | falls |A| ≤ |B| und |A| ≠ |B| |
Wir sagen entsprechend, dass die Mächtigkeit von A kleinergleich (gleich, kleiner) der Mächtigkeit von B ist.
In der Definition wird die Mächtigkeit nur relational (zwischen zwei Mengen) definiert, aber nicht festgelegt, was die Mächtigkeit einer Menge A an sich ist. Dies ist in der Mengenlehre durch Definition der transfiniten Kardinalzahlen möglich, die kanonische Repräsentanten für unendliche Mengen darstellen.
In der neuen Mächtigkeitsnotation bedeutet:
| |A| < |ℕ| | A ist endlich |
| |A| ≤ |ℕ| | A ist abzählbar |
| |ℕ| = |A| | A ist abzählbar unendlich |
| |ℕ| ≤ |A| | A ist (Dedekind-)unendlich |
| |ℕ| < |A| | A ist überabzählbar |
Es gilt
|ℕ| = |ℤ| = |ℕ × ℕ| = |ℚ| = |𝔸| = |Seq|.
Die Überabzählbarkeit von ℝ liest sich nun schlicht als
|ℕ| < |ℝ|.
Über die Struktur der Mächtigkeiten im Unendlichen lassen sich viele Fragen stellen, und die meisten von ihnen sind alles andere als einfach zu beantworten. Ein wichtiges Beispiel ist:
Satz (Satz von Cantor-Bernstein)
Seien A, B Mengen mit |A| ≤ |B| und |B| ≤ |A|. Dann gilt |A| = |B|.
Gegeben sind zwei Injektionen von A nach B bzw. von B nach A. Diese Injektionen müssen wir zu einer Bijektion zwischen A und B verschmelzen. Wir zeigen hierzu folgenden für sich interessanten Hilfssatz, der Methoden unserer Analyse Dedekind-unendlicher Mengen aufgreift:
Satz (Zwischenmengensatz)
Seien D, E, F paarweise disjunkte Mengen, und sei h : D ∪ E ∪ F → F bijektiv. Dann gibt es eine Bijektion h* : E ∪ F → F.
Beweis
Zur Konstruktion von h* betrachten wir alle Orbits (an)n ∈ ℕ = (hn(a))n ∈ ℕ von a ∈ E unter h. Auf diesen injektiven und paarweise disjunkten Orbits verschieben wir um 1, d. h. wir setzen
h*(an) = an + 1 = h(an) für alle a ∈ E und n ≥ 0.
Für alle anderen Elemente b von E ∪ F sei h*(b) = b. Dann ist die Funktion h* : E ∪ F → F bijektiv (Übung).
Wir betrachten alle Orbits von Elementen in E unter der Bijektion h : D ∪ E ∪ F → F, also den Orbit der Menge E. Auf diesem Mengen-Orbit wenden wir h an. Auf dem Rest von E ∪ F verwenden wir die Identität. Es entsteht eine Bijektion h* : E ∪ F → F.
Der Beweis erinnert an die Einbettung von ℕ in eine Dedekind-unendliche Menge. Auch dort hatten wir mit einer Orbit-Verschiebung argumentiert. Das „D“ im Beweis steht sowohl für „Dedekind“ als auch für „delete“, da die Menge D aus D ∪ E ∪ F entfernt wird. Ist |D ∪ E ∪ F| = |F|, so ist die Zwischenmenge E ∪ F der beiden Mengen ebenfalls gleichmächtig zu den beiden Mengen.
Nun können wir ohne weitere Schwierigkeiten zeigen:
Beweis des Satzes von Cantor-Bernstein
Seien f : A → B und g : B → A injektiv. Wir betrachten die Zerlegung
F = g[ f [ A ]], E = g[ B ] − F, D = A − g[ B ]
von A und die Bijektion
h = g ∘ f : D ∪ E ∪ F → F.
Nach dem Zwischenmengensatz gilt
|B| = |g[ B ]| = |E ∪ F| = |F| = |h[ A ]| = |A|.
Zum Beweis des Satzes von Cantor-Bernstein mit der Bijektion h = g ∘ f von A nach F. Gleichfarbige Mengen sind nach Voraussetzung gleichmächtig. Die Gleichmächtigkeit aller beteiligten Mengen ergibt sich aus dem Zwischenmengensatz.
Der Satz von Cantor-Bernstein wurde von Cantor vermutet und von Dedekind und Bernstein unabhängig voneinander bewiesen. Historisch korrekter (aber umständlicher) wäre „Satz von Cantor-Dedekind-Bernstein“.
Der Satz erleichtert in vielen Fällen den Beweis der Gleichmächtigkeit zweier Mengen. Wollen wir |A| = |B| zeigen, so können wir in zwei Schritten
|A| ≤ |B| und |B| ≤ |A|
zeigen. Die Konstruktion zweier Injektionen ist oft einfacher als die Konstruktion einer Bijektion. Die Situation ist vergleichbar mit
| A = B | genau dann, wenn A ⊆ B und B ⊆ A | für Mengen A, B, |
| A ↔ B | genau dann, wenn A → B und B → A | für Aussagen A, B. |
Ein Beispiel ist die Mächtigkeitsaussage |ℝ| = |℘(ℕ)|, die sich mit Hilfe des Satzes von Bernstein aus zwei Injektionen f : ℝ → ℘(ℕ) und g : ℘(ℕ) → ℝ ergibt (Übung).
Ein weiteres fundamentales Ergebnis der Mächtigkeitstheorie ist:
Satz (Vergleichbarkeitssatz von Cantor-Zermelo)
Seien A, B Mengen. Dann gilt |A| ≤ |B| oder |B| ≤ |A|.
Dieser Satz ist weitaus schwieriger zu beweisen als der Satz von Cantor-Bernstein. Im Endlichen ist die Aussage durch die Vergleichbarkeit natürlicher Zahlen klar: „Zähle die Elemente der Mengen und vergleiche die Ergebnisse.“ Ein Zählen im Unendlichen ist möglich, aber die hierzu benötigten transfiniten Zahlen sind nicht leicht zu definieren. Alternativ lässt sich der Vergleichbarkeitssatz mit Hilfe eines allgemeinen ordnungstheoretischen Maximal-Prinzips beweisen. Wir kommen bei der Diskussion des Auswahlaxioms und des Zornschen Lemmas darauf zurück.