Addition und Multiplikation von Kardinalzahlen
Wir zeigen:
𝔞 + 𝔞 = 𝔞 · 𝔞 = 𝔞 für alle unendlichen Kardinalzahlen 𝔞.
Die Beweisidee ist die des Vergleichbarkeitssatzes. Wie dort sind die dahinterliegenden Ideen im Grunde sehr anschaulich: Wir definieren Approximationen an ein gesuchtes Objekt und zeigen, dass es eine bestmögliche Approximation gibt. Wir benutzen hierbei den allgemeinen „des Pudels Kern“-Satz über die Existenz von Zielen in Zermelosystemen, sodass der Leser, der nicht gerne in die Rolle des Pudels schlüpft, die etwas filzige Approximationstechnik selber nicht zu kennen braucht. (Es ist eine gute Übung, einen der Beweise unten umständlich auszuführen, und sich das mephistophelische Schauspiel von Schmidtscher Auswahl und Zermeloscher Reduzierung von geschlossenen Mengen noch einmal vor Augen zu führen.) Der Leser kann den Rest dieses Abschnitts auch überschlagen: Wir geben im zweiten Abschnitt Beweise von aufregender Transparenz für die Addition und Multiplikation von Kardinalzahlen.
Wir führen den Beweis in der „neuen“ Form mit Kardinalzahlen (|A| = 𝔞). Ein Umschreiben auf die „alte“ relationale Form (|A| = |B|) wäre problemlos. Die Multiplikationsaussage lautet z. B. einfach: Für alle unendlichen Mengen M ist |M × M| = |M|.
Der Beweis gliedert sich in mehrere Zwischenstufen. Zunächst zeigen wir, dass wir eine unendliche Menge immer als „Rechteck“ mit einer abzählbaren Seite darstellen können.
Satz (Zerlegungslemma)
Sei A eine unendliche Menge. Dann gibt es eine Menge B mit
|A| = |B × ℕ|.
Die Idee ist, A durch abzählbare Teilmengen auszuschöpfen, um es in der Form B × ℕ anordnen zu können. Jede dabei verwendete Teilmenge bildet dann eine Spalte der Höhe ℕ in der abschließenden Darstellung als „Rechteck“. Die ersten Elemente der Spalten bilden die Breite des Rechtecks, also die Menge B.
Beweis
Wir setzen
𝒵 = { Z | jedes f ∈ Z ist eine Injektion von ℕ nach A und für alle f, g ∈ Z mit f ≠ g gilt: rng(f) ∩ rng(g) = ∅ }.
Dann ist 𝒵 ein Zermelosystem (!). Wegen |ℕ| ≤ |A| ist 𝒵 ≠ ∅. Sei also Z ein beliebiges Ziel von 𝒵. Dann gilt:
(◇) R = A − ⋃f ∈ Z rng(f) ist endlich.
Hieraus folgt aber:
(◇*) Es existiert ein Z* ∈ 𝒵 mit ⋃f ∈ Z* rng(f) = A.
Beweis von (◇*)
Sei h : m → R bijektiv für ein m ∈ ℕ, und sei g ∈ Z beliebig. Wir definieren g* : ℕ → A durch
Dann ist g* injektiv und rng(g*) = rng(g) ∪ R. Sei
Z* = (Z − { g }) ∪ { g* }.
Dann ist Z* ∈ 𝒵 und ⋃f ∈ Z* rng(f) = A.
Sei nun Z* wie in (◇*). Sei B = { f (0) | f ∈ Z* }. Wir definieren h : B × ℕ → A durch:
h(x, n) = fx(n), wobei fx das eindeutige f ∈ Z* ist mit f (0) = x.
Dann ist h : B × ℕ → A bijektiv.
Mit einem kleinen Trick erhalten wir hieraus schon:
Korollar (abzählbarer Multiplikationssatz)
Sei 𝔞 eine unendliche Kardinalzahl.
Dann gilt 𝔞 · ℵ0 = 𝔞.
Beweis
Sei A eine Menge mit |A| = 𝔞. Nach dem Zerlegungslemma existiert eine Menge B mit |A| = |B × ℕ|. Sei 𝔟 = |B|. Wir haben damit 𝔞 = 𝔟 · ℵ0. Dann gilt wegen ℵ0 · ℵ0 = ℵ0 und der Assoziativität der Multiplikation:
𝔞 = 𝔟 · ℵ0 = 𝔟 · ℵ0 · ℵ0 = 𝔞 · ℵ0.
In der Rechnung der letzten Zeile des Beweises zeigt sich, warum wir im Zerlegungslemma die Menge A nicht durch Paare, sondern durch abzählbare Mengen ausgeschöpft haben: Eine Paarausschöpfung − die zudem ein lästiges einzelnes Element hinterlassen könnte, das sich nicht ganz so leicht einbinden ließe wie ein endlicher Rest in eine ℕ-Ausschöpfung − liefert nur 𝔞 · 2 = 𝔟 · 2 · 2 = 𝔟 · 4, was nicht weiterhilft. 2 · 2 ≠ 2, aber ℵ0 · ℵ0 = ℵ0.
Wegen 𝔞 ≤ 𝔞 + 𝔞 = 𝔞 · 2 ≤ 𝔞 · ℵ0 = 𝔞 für unendliche 𝔞 haben wir:
Korollar (Additionssatz)
Sei 𝔞 eine unendliche Kardinalzahl. Dann gilt 𝔞 + 𝔞 = 𝔞.
Mit Hilfe des Additionssatzes beweisen wir nun den Multiplikationssatz, wieder durch Approximation. Hierzu einige Bemerkungen vorab. Sei B eine Approximation an |A × A| = |A|, d. h. B ⊆ A und |B × B| = |B|.
Ist |B| < |A|, so können wir im Rest A − B eine Kopie C von B finden, denn „B ist klein in A“. Die Kopie fügen wir zu B hinzu und betrachten das Kreuzprodukt von B ∪ C. Dieses zerfällt in vier gleichgroße Teile, und mit Hilfe des Additionssatzes können wir leicht zeigen, dass wir einen Zeugen f für |B × B| = |B| zu einem Zeugen g für |B ∪ C × B ∪ C| = |B ∪ C| fortsetzen können. Die Approximation B ist also keinesfalls bestmöglich, und dies hält die Dinge intern am Laufen.
Ist andernfalls |B| = |A|, so … ? − ja, so sind wir schon fertig, denn in diesem Fall ist |A × A| = |A|, da dies für B gilt, und B und A in bezug auf Kardinalitätsfragen gleichwertig sind. Dies ist eine kleine, aber enorm hilfreiche Beobachtung: Wir müssen nicht ganz A ausschöpfen, es reicht, dass wir eine Approximation B ⊆ A finden mit |B × B| = |B|, die die gleiche Kardinalität wie A hat.
Satz (Multiplikationssatz)
Sei 𝔞 eine unendliche Kardinalzahl. Dann gilt 𝔞 · 𝔞 = 𝔞.
Beweis
Sei A eine Menge mit |A| = 𝔞. Sei
𝒵 = { f | f : B × B → B bijektiv für ein unendliches B ⊆ A }.
Es gilt 𝒵 ≠ ∅ wegen ℵ0 ≤ 𝔞 und ℵ0 · ℵ0 = ℵ0. 𝒵 ist ein Zermelosystem.
Sei also f ∈ 𝒵 ein Ziel von 𝒵. Sei B = rng(f). Dann gilt |B × B| = |B| wegen f ∈ 𝒵. Ist |B| = |A|, so gilt |A × A| = |B × B| = |B| = |A|, und wir sind fertig. Es genügt also, den anderen Fall zum Widerspruch zu führen.
Annahme, es gilt |B| < |A|. Sei dann C ⊆ A − B mit |C| = |B|.
[Ein solches C existiert, denn andernfalls ist |A − rng(f)| < |B|. Aber |B| < |A|, also gilt nach dem Additionssatz
|A| = |A − B| + |B| ≤ |B| + |B| = |B| < |A|, Widerspruch.]
Seien
D = B ∪ C, D1 = B × C,
D2 = C × C, D3 = C × B,
f* = „ein h ⊇ f mit h : D × D → D bijektiv“.
Ein solches h existiert, denn es gilt |D1| = |D2| = |D3| = |B|, also hat nach dem Additionssatz auch D1 ∪ D2 ∪ D3 die Kardinalität |B| = |C|. Also existiert ein
g : D1 ∪ D2 ∪ D3 → C bijektiv.
Also ist f* = f ∪ g : D × D → D bijektiv. Also f* ∈ 𝒵. Dann ist aber f kein Ziel von 𝒵, Widerspruch.
Der hier dargestellte Beweis folgt im Wesentlichen einem Beweis von Max Zorn aus dem Jahre 1944. Die ersten Beweise des Additionssatzes und des Multiplikationssatzes haben unabhängig A. E. Harward 1905 und Gerhard Hessenberg 1906 gegeben, zuvor war 𝔞 = 𝔞 · 𝔞 = 𝔞 + 𝔞 nur für die Spezialfälle ℵ0, 𝔠 und 𝔣 bekannt. Bernstein schreibt in seiner Doktorarbeit 1901, dass ihm Cantor einen Beweis der Gleichung |M × M| = |M| mitgeteilt habe für Mengen M mit einer bestimmten Eigenschaft (E), gibt diesen Beweis aber nicht wieder. Hausdorff stellt 1904 eine äquivalente Behauptung auf, ebenfalls ohne Beweis. Die damals kursierende und naheliegende Beweisidee war die der Verallgemeinerung der Cantorschen Diagonalaufzählung von ℕ2. Mengen M mit der Eigenschaft (E) lassen sich in eine ℕ-ähnliche Form bringen, und es liegt dann nahe, das Produkt M × M über eine Paarungsfunktion diagonal abzuzählen.
Harward und Hessenberg gelangen die ersten strengen Umsetzungen dieser Idee. Ein Jahr später gab Hessenberg einen zweiten Beweis, und 1908 fand Philip Jourdain (1879 − 1921) einen dritten. Wir werden diese Beweise und ihre Geschichte später diskutieren (2.8). Sie alle zeigen den Multiplikationssatz für Mengen, die die Eigenschaft (E) haben. Das allgemeine Resultat folgt dann aus dem Satz von Zermelo, dass in der Tat alle Mengen die Eigenschaft (E) haben. Eigenschaft (E) ist die sog. Wohlordenbarkeit, und der Satz von Zermelo ist der Wohlordnungssatz von 1904, ein historischer Vulkanausbruch, der viel fruchtbaren Boden hinterließ. Der Durchführung des Cantorschen Leitmotivs Wohlordnung widmet sich der zweite Abschnitt, und wir werden auf die Ereignisse kurz nach der Jahrhundertwende dort zurückkommen.
Als Korollar halten wir fest, dass die Addition und Multiplikation im Unendlichen letztendlich trivial ist:
Korollar (Addition und Multiplikation von Kardinalzahlen)
Seien 𝔞, 𝔟 ≠ 0 Kardinalzahlen, und es sei ℵ0 ≤ max(𝔞, 𝔟). Dann gilt
𝔞 + 𝔟 = 𝔞 · 𝔟 = max(𝔞, 𝔟).
Hatten wir auch etwas Mühe mit dem Beweis des Multiplikationssatzes, so bleibt uns dafür die Mühe des Ausrechnens von 𝔞 · 𝔟 für immer erspart.
Aus dem Multiplikationssatz gewinnen wir die folgende Aussage über die Kardinalzahlsumme und über Suprema: Sei 𝔄 eine Menge von unendlichen Kardinalzahlen. Für alle Kardinalzahlen 𝔠 gelte |{ 𝔟 | 𝔟 < 𝔠 }| ≤ 𝔠. Dann gilt:
sup(𝔄) = Σ𝔞 ∈ 𝔄 𝔞.
Denn sei 𝔠 eine Kardinalzahl mit 𝔞 ≤ 𝔠 für alle 𝔞 ∈ 𝔄. Dann gilt:
Σ𝔞 ∈ 𝔄 𝔞 ≤ 𝔠 · |𝔄| ≤ 𝔠 · 𝔠 = 𝔠.
Offenbar ist 𝔞 ≤ Σ𝔞 ∈ 𝔄 𝔞 für alle 𝔞 ∈ 𝔄, und damit ist dann
sup(𝔄) = Σ𝔞 ∈ 𝔄 𝔞.
Wir zeigen unten, dass die Voraussetzung |{ 𝔟 | 𝔟 < 𝔠 }| ≤ 𝔠 für Kardinalzahlen 𝔠 immer erfüllt ist.
Früher hatten wir gezeigt, dass das Entfernen einer abzählbaren Menge die Kardinalität einer unendlichen Menge nicht ändert. Allgemein erhalten wir nun:
Korollar (Subtraktionssatz)
Sei A eine unendliche Menge, und sei B ⊆ A mit |B| < |A|. Dann gilt
|A − B| = |A|.
Beweis
Andernfalls wäre |A| = |B| + |A − B| = max(|B|, |A − B|) < |A|, Widerspruch.
Eine hübsche Anwendung des Multiplikationssatzes ist, dass wir 𝔞𝔟 in vielen Fällen auf 2𝔟 zurückführen können:
Übung (Verkleinern der Basis)
Seien 𝔞, 𝔟 Kardinalzahlen mit 2 ≤ 𝔞 ≤ 𝔟, ℵ0 ≤ 𝔟. Dann gilt 𝔞𝔟 = 2𝔟.
[ 𝔞𝔟 ≤ (2𝔞)𝔟 = 2𝔞 · 𝔟 = 2𝔟. ]
Wir betrachten nun umgekehrt den Fall, dass der Exponent kleiner ist als die Basis. Hier gibt es keine einfache Formel, dafür aber einen interessanten Zusammenhang zwischen 𝔞𝔟 und der Anzahl der 𝔟-großen Teilmengen einer 𝔞-großen Menge. Hierzu:
Definition ([ A ]𝔟, [ A ] ≤ 𝔟, [ A ] < 𝔟)
Sei A eine Menge, und sei 𝔟 ≤ |A|. Dann setzen wir:
| [ A ]𝔟 | = { B ⊆ A | |B| = 𝔟 }, |
| [ A ]≤ 𝔟 | = { B ⊆ A | |B| ≤ 𝔟 }, |
| [ A ]< 𝔟 | = { B ⊆ A | |B| < 𝔟 }. |
Sind A, B Mengen, so gilt BA ⊆ [ B × A ]𝔟, denn jedes f : B → A ist eine Teilmenge von B × A der Mächtigkeit 𝔟 = |B|. Diese Beobachtung ist schon fast die Hälfte des folgenden Satzes:
Satz (𝔞𝔟 und [ A ]𝔟)
Seien A eine unendliche Menge, 𝔞 = |A|, und sei 𝔟 ≤ 𝔞 eine Kardinalzahl.
Dann gilt 𝔞𝔟 = |[ A ]𝔟| = |[ A ]≤ 𝔟|.
Beweis
Sei B eine Menge mit |B| = 𝔟.
Ohne Einschränkung 𝔟 ≠ 0, denn sonst ist BA = [ A ]𝔟 = [ A ]≤ 𝔟 = { ∅ }.
zu 𝔞𝔟 ≤ |[ A ]𝔟| :
Es gilt 𝔞𝔟 = |BA| ≤ |[ B × A ]𝔟| = |[ A ]𝔟| wegen |B × A| = |A|.
zu |[ A ]𝔟| ≤ |[ A ]≤ 𝔟| :
Es gilt [ A ]𝔟 ⊆ [ A ]≤ 𝔟.
zu |[ A ]≤ 𝔟| ≤ 𝔞𝔟 :
Wir definieren h(C) für alle C ⊆ A mit |C| ≤ 𝔟, C ≠ ∅, durch
h(C) = „ein surjektives f : B → C“.
Dann ist h : [ A ]≤ 𝔟 − { ∅ } → BA injektiv. Also (wegen 𝔟 ≠ 0)
|[ A ]≤ 𝔟| = |[ A ]≤ 𝔟 − { ∅ }| ≤ |BA|.