Der Satz von Cantor-Bernstein

Der Mächtigkeitsvergleich ist offenbar reflexiv und transitiv. Die Schreibweise suggeriert zudem die Antisymmetrie, d. h. die Gültigkeit der folgenden Implikation:

|M| ≤ |N| und |N| ≤ |M| impliziert |M| = |N|. (Satz von Cantor-Bernstein)

Der Beweis dieser Aussage ist eine nichttriviale Angelegenheit. Wir müssen zwei gegebene Injektionen

f₁ : M → N und f₂ : N → M

zu einer Bijektion f : M → N verschmelzen. Dass dies letztendlich doch in einer relativ einfachen und dazu auch konstruktiven Art und Weise möglich ist, gehört zu den Juwelen der Mathematik. Als Korollar erhalten wir, dass der Mächtigkeitsvergleich |M| ≤ |N| die Strukturmerkmale einer partiellen Ordnung besitzt.

Cantor hat den Satz lange vermutet, aber keinen Beweis gesehen. Beweise wurden dann von Dedekind, Bernstein, Zermelo und anderen gefunden. Der folgende Beweis stammt von Dedekind. Es genügt für das folgende, wenn der Leser die Problemstellung des Satzes von Cantor-Bernstein zur Kenntnis nimmt. Der Beweis ist für diejenigen gedacht, die an dieser Stelle ein anspruchsvolleres Ergebnis studieren möchten.

Wir beweisen zunächst ein verwandtes Resultat, aus welchem wir dann den eigentlichen Satz leicht ableiten können.

Satz (Satz von Cantor-Bernstein, Inklusionsform)

Seien A, B, C paarweise disjunkte Mengen, und sei

f : A ∪ B ∪ C → A bijektiv.

Dann gibt es Bijektionen

b : A ∪ B ∪ C → A ∪ B,

b′ : A ∪ B → A.

Anders formuliert: Alle Mengen, die bzgl. der Inklusion zwischen zwei gleichmächtigen Mengen liegen, sind gleichmächtig mit diesen Mengen.

Beweis

Wir setzen:

Z = ⋂ { D ⊆ A ∪ C | C ⊆ D, f [ D ] ⊆ D }.

Die Menge des Schnitts ist nichtleer, da die Menge D = A ∪ C die geforderten Eigenschaften hat. Es gilt zudem C ⊆ Z, denn C ist eine Teilmenge jeder Menge D der Schnittbildung.

Weiter gilt:

(+) f[ Z ] = Z − C.

Beweis von (+)

Es gilt f[ Z ] ⊆ Z, denn ist x  ∈  Z, so ist f (x)  ∈  D für alle D wie in der Schnittbildung, also f (x)  ∈  Z. Wegen rng(f) ⊆ A ist also f[ Z ] ⊆ Z − C.

Sei nun x  ∈  Z − C beliebig. Dann ist Z − { x } eine echte Teilmenge von Z und eine Obermenge von C. Nach Definition von Z ist also das Bild f[ Z − { x } ] keine Teilmenge von Z − { x }. Wegen

f[ Z − { x } ] ⊆ f[ Z ] ⊆ Z

gibt es also ein y  ∈  Z − { x } mit f (y) = x. Also ist x  ∈  f[ Z ].

Nach (+) ist f|Z : Z → Z − C bijektiv, und damit ist

b = f|Z ∪ id_{(A ∪ B) − Z}

eine Bijektion von A ∪ B ∪ C nach A ∪ B.

Schließlich ist dann b′ = f ∘ b⁻¹ eine Bijektion von A ∪ B nach A.

Wir erhalten hieraus ohne weitere Schwierigkeiten:

Korollar (Satz von Cantor-Bernstein)

Seien g₁ : M → N und g₂ : N → M injektiv.

Dann existiert eine Bijektion g : M → N.

Beweis

Wir definieren:

A = rng(g₂ ∘ g₁), B = rng(g₂) − A, C = M − rng(g₂).

Dann sind A, B, C paarweise disjunkt, und es gilt

M = A ∪ B ∪ C.

Weiter ist g₂ ∘ g₁ : A ∪ B ∪ C → A bijektiv. Nach dem Satz gibt es ein bijektives b : M → A ∪ B. Aber es gilt A ∪ B = rng(g₂), und damit ist

g₂⁻¹ ∘ b : M → N

bijektiv.

Als Nächstes zeigen wir den nach dem Satz von Cantor-Bernstein zweiten Hauptsatz der elementaren Mächtigkeitstheorie: Die Potenzmenge einer Menge M ist immer von größerer Mächtigkeit als die Mächtigkeit von M selbst. Dieser starke Satz hat einen überraschend kurzen und einfachen Beweis, der als Cantorsches Diagonalverfahren bekannt ist.

Satz (Satz von Cantor)

Sei M eine Menge, und sei f : M → ℘(M) eine Funktion.

Dann ist f nicht surjektiv. Genauer gilt: Sei

D = { x  ∈  M | x  ∉  f (x) }.

Dann gilt D  ∉  rng(f).

Beweis

Annahme, D  ∈  rng(f). Sei dann x*  ∈  M mit f (x*) = D. Für alle x  ∈  M gilt nach Definition von D:

x  ∈  D gdw x  ∉  f (x).

Speziell gilt also für x*:

x*  ∈  D gdw x*  ∉  f (x*).

Wegen f (x*) = D haben wir also:

x*  ∈  D gdw x*  ∉  D,

Widerspruch.

Korollar

Für alle Mengen M gilt |M| < |℘(M)|.

Beweis

Nach dem Satz von Cantor gilt |M| ≠ |℘(M)|. Die injektive Funktion f : M → ℘(M) mit f (x) = { x } für alle x  ∈  M zeigt, dass |M| ≤ |℘(M)|.

Der Leser ist beim Studium des Beweises vielleicht an die Russell-Zermelo-Antinomie erinnert worden. In der Tat war Cantors allgemeiner Satz die Quelle für Russells Konstruktion der Klasse R = { x | x  ∉  x }. Genaueres diskutieren wir in den Übungen.

Es gibt auch noch einen dritten Hauptsatz der elementaren Mächtigkeitstheorie: Für alle Mengen M und N gilt |M| ≤ |N| oder |N| ≤ |M|. Je zwei Mengen sind also in ihrer Mächtigkeit vergleichbar. Diese Aussage ist richtig, lässt sich aber nur mit weitergehenden Hilfsmitteln beweisen, und wir können auf diesen Vergleichbarkeitssatz für Mächtigkeiten hier nicht weiter eingehen.