5.Der Vergleichbarkeitssatz

Der Vergleichbarkeitssatz, von Cantor lange Zeit vermutet, wurde zum ersten Mal streng bewiesen durch Ernst Zermelo (1904; der Satz ist ein Korollar zum Zermeloschen Wohlordnungssatz). Er beantwortet die an dieser Stelle der Diskussion wohl natürlichste Frage positiv, nämlich: Sind je zwei Mengen in ihrer Mächtigkeit vergleichbar?

 Der Beweis des Satzes ist der härteste Brocken dieser Einführung, und der nicht allzu ehrgeizige Leser kann zunächst nur seine Aussage zur Kenntnis nehmen und den Beweis überschlagen.

Satz (Vergleichbarkeitssatz)

Seien M, N Mengen. Dann gilt |M| ≤ |N| oder |N| ≤ |M|.

Beweis (Technik von Ernst Zermelo und Erhard Schmidt, 1904 und 1908)

Sei 𝒵 = { f | dom(f) = M′ ⊆ M, rng(f) = N′ ⊆ N, f : M′  N′ bijektiv }.

Es genügt zu zeigen:

(◇)  Es existiert ein f  ∈  𝒵 mit dom(f) = M oder rng(f) = N.

Im Fall dom(f) = M ist |M| ≤ |N|, denn dann ist f : M  N injektiv, und im Fall rng(f) = N ist |N| ≤ |M|, denn dann ist f −1 : N  M injektiv.

Die Menge 𝒵 besteht aus Approximationen an das erwünschte Objekt, und wir müssen zeigen, dass ein erwünschtes Objekt f wie in (◇) tatsächlich in 𝒵 vorkommt.

Annahme, ein f wie in (◇) existiert nicht.

Für jedes f  ∈  𝒵 existieren dann xf  ∈  M und yf  ∈  N mit xf  ∉  dom(f) und yf  ∉  rng(f).

Für f  ∈  𝒵 sei

f*  =  f ∪ { (xf, yf) }.

mengenlehre1-AbbID14

Dann ist f*  ∈  𝒵 eine echte Fortsetzung von f um genau ein Element.

Ein T ⊆ 𝒵 heißt eine (nichttriviale) Kette, falls gilt:

T ≠ ∅ und für alle f, g  ∈  T gilt f ⊆ g oder g ⊆ f.

mengenlehre1-AbbID15

Ist T ⊆ 𝒵 eine Kette, so ist

⋃ T  =  { (x, y) | es existiert ein f  ∈  T mit f (x) = y }

wieder ein Element von 𝒵. Genauer gilt:

Ist T eine Kette und h = ⋃ T, so ist

dom(h) = ⋃ { dom(f) | f  ∈  T } , rng(h) = ⋃ { rng(f) | f  ∈  T } ,

und es gilt h(x) = f (x) für alle f  ∈  T und alle x mit x  ∈  dom(f).

Die Vereinigung einer Kette von Approximationen bildet also wieder eine Approximation, und diese setzt alle Approximationen der Kette fort.

Wir fixieren für das Folgende ein beliebiges f 0  ∈  𝒵 (z. B. f 0 = ∅).

Entscheidend ist der folgende Hilfsbegriff.

Ein T ⊆ 𝒵 heißt geschlossen, falls gilt:

(i)

f 0  ∈  T.

(ii)

Für alle f  ∈  𝒵 gilt: f  ∈  T  folgt  f*  ∈  T.

(iii)

Ist T′ ⊆ T eine Kette, so ist ⋃ T′  ∈  T.

Offenbar ist 𝒵 selbst geschlossen. Wir setzen:

T*  =  ⋂ { T ⊆ 𝒵 | T ist geschlossen }.

Dann ist T* geschlossen (!). Insbesondere also f 0  ∈  T*.

Im Folgenden verwenden wir mehrfach: Ist T ⊆ T* geschlossen, so ist T = T*. Dadurch können wir Informationen über die Struktur von T* gewinnen. Das einfachste Beispiel für diese Methode ist:

(+)  Ist f  ∈  T*, so gilt f 0 ⊆ f.

Beweis von (+)

Wir setzen T = { f  ∈  T* | f 0 ⊆ f }. Dann ist T geschlossen (! ).

Also gilt T = T*, und dies zeigt (+).

Wir wollen zeigen, dass T* eine Kette ist.

Hierzu ist der folgende Hilfsbegriff nützlich:

f  ∈  T* heißt ein Schnitt (von T*), falls für alle g  ∈  T* gilt: g* ⊆ f oder f ⊆ g.

Ist f  ∈  T* ein Schnitt, so gilt die folgende stärkere Eigenschaft:

(✥)  Für alle g  ∈  T* mit g ≠ f gilt: g* ⊆ f oder f* ⊆ g.

mengenlehre1-AbbID16

Ist f ein Schnitt, so zerfällt T* in

A  =  { g  ∈  T* | g ⊆ f } , 

B  =  { g  ∈  T* | f* ⊆ g } ,

C  =  { g  ∈  T* | f ⊂ g, non(f* ⊆ g) }.

Für g  ∈  A, g ≠ f gilt zudem g*  ∈  A, d. h. g* ⊆ f: die *-Operation überspringt also keine Schnitte. Die Aussage (✥) besagt nun, dass für einen Schnitt f sogar C = ∅ gilt, d. h. f* ist die unmittelbare Erweiterung von f in T*. Wir werden mit (✥) zeigen, dass sich die Schnitteigenschaft von f auf f* vererbt.

Beweis von (✥)

Sei T = { g  ∈  T* | g ⊆ f oder f* ⊆ g }.

Dann ist T geschlossen:

zu (i):  Es gilt f0 ⊆ f, also f0  ∈  T.

zu (ii):  Sei g  ∈  T. Dann gilt g ⊆ f oder f* ⊆ g. Wegen f Schnitt gilt zudem g* ⊆ f oder f ⊆ g. Ist f* ⊆ g ⊆ g* oder g* ⊆ f, so ist offenbar g*  ∈  T. Andernfalls ist g ⊆ f und f ⊆ g, also f = g. Also f* ⊆ g*, und damit g*  ∈  T.

zu (iii):  Sei T′ ⊆ T eine Kette, und sei h = ⋃ T′. Wegen T′ ⊆ T gilt

g ⊆ f oder f* ⊆ g  für alle g  ∈  T′.

Ist g ⊆ f für alle g  ∈  T′, so ist h = ⋃ T′ ⊆ f, also h  ∈  T. Ist f* ⊆ g für ein g  ∈  T′, so ist f* ⊆ h, also h  ∈  T.

Also gilt T = T*, und dies genügt für (✥), da f ein Schnitt ist.

Wir setzen nun:

T  =  { f  ∈  T* | f ist ein Schnitt von T* }.

T ist geschlossen:

zu (i):

f0 ist ein Schnitt von T* nach (+).

zu (ii):

Sei f ein Schnitt von T*.

Dann gilt nach (✥) für alle g ≠ f, g  ∈  T*:

g* ⊆ f oder f* ⊆ g.

Dann gilt aber für alle g  ∈  T* wegen f ⊆ f*:

g* ⊆ f* oder f* ⊆ g.

(Dies ist trivial für g = f.)

Also ist f* ein Schnitt von T*, und damit f*  ∈  T.

zu (iii):

Sei T′ ⊆ T eine Kette, und sei h = ⋃ T′. Sei g  ∈  T*. Wir zeigen: g* ⊆ h oder h ⊆ g. Dann ist h ein Schnitt, und somit h  ∈  T. Da jedes f  ∈  T′ ein Schnitt ist, gilt g* ⊆ f oder f ⊆ g für alle f  ∈  T′.

Ist f ⊆ g für alle f  ∈  T′, so gilt h = ⋃ T′ ⊆ g.

Ist g* ⊆ f für ein f  ∈  T′, so gilt g* ⊆ h wegen f ⊆ h für jedes f  ∈  T′.

Also ist T geschlossen, und damit ist T = T*. Also gilt

g* ⊆ f oder f ⊆ g für alle f, g  ∈  T*,

insbesondere ist also T* eine Kette.

Sei f = ⋃ T*. Dann ist nach (iii) f  ∈  T*, also nach (ii) f*  ∈  T*.

Also ⋃ T* = f ⊂ f* und f*  ∈  T*. Widerspruch!

Also ist die Annahme falsch und es gilt (◇), d. h. es existiert ein f  ∈  𝒵 wie gewünscht.

 Im Beweis wird T* als der Schnitt über die geschlossenen Teilmengen T ⊆ 𝒵 definiert. Im Folgenden wird dann mehrfach benutzt, dass T* keinen überflüssigen Ballast mehr enthält. T* besteht nur noch aus den Elementen von 𝒵, die eine geschlossene Menge einfach haben muss, um geschlossen zu sein. Alles andere fällt bei der Schnittbildung weg, so etwa der Bereich C im Diagramm oben. In geschlossenen Mengen muss zwischen f und f* nichts liegen, und T* verzichtet als spartanische geschlossene Menge auf jeden Schnickschnack.

 Der Beweis enthält wieder eine Definition von Objekten der Form „ein …“, und zwar bei der Definition von xf und yf, und damit bei der Definition von f*; zu Beginn des Beweises wählen wir für jedes f  ∈  𝒵 Zeugen xf und yf aus jeweils nichtleeren von f abhängigen Mengen. Den “*" können wir als eine Funktion auf 𝒵 auffassen, die ein f  ∈  𝒵 auf f*  ∈  𝒵 abbildet.

 Die logisch einwandfreie uniforme Definition von f* für alle f gleich zu Beginn − nicht etwa eine schrittweise Erweiterung von Objekten f „während“ des Beweises −, ist die Idee, die Erhard Schmidt (1876 − 1959) zum Beweis des Satzes beigetragen hat, wie Zermelo in seiner Arbeit von 1904, wo die Technik zum ersten Mal angewendet wird, ausdrücklich festhält (vgl. 2. 5). Der Rest ist, einschließlich der Betonung der Auswahlakte an sich, die „Zutat“ von Ernst Zermelo.

 Der Vergleichbarkeitssatz zeigt den linearen Charakter der Mächtigkeiten und ist Grundvoraussetzung dafür, dass wir − in einem später zu präzisierenden Sinn − |M| als Anzahl, genauer als sogenannte Kardinalzahl ansehen können. Was auch immer wir unter Anzahl verstehen wollen, so ist es doch sicher dieses, dass von zwei Anzahlen eine größergleich der anderen ist.

 Der obige Beweis ist vom Typ: Es existiert ein maximales Objekt für eine bestimmte Eigenschaft. In unserem Fall: ein nicht mehr verlängerbares f  ∈  𝒵. Später werden wir allgemeine und in der Mathematik vielseitig einsetzbare Sätze über die Existenz maximaler Objekte zeigen, das Hausdorffsche Maximalitätsprinzip und das sogenannte Zornsche Lemma, aus denen sich der Vergleichbarkeitssatz dann leicht ableiten lässt.

 Wir halten noch ein Korollar fest, das wir aus der freien Wahl von f 0  ∈  𝒵 gewinnen. Wir können f0  ∈  𝒵 bereits zu Beginn des Beweises fixieren und dann überall mit der Menge 𝒵0 = { f  ∈  𝒵 | f0 ⊆ f } anstelle von 𝒵 arbeiten. Dann zeigt der Beweis:

Korollar

Seien M, N Mengen, M′ ⊆ M, N′ ⊆ N, f 0 : M′  N′ bijektiv.

Dann existiert eine injektive Fortsetzung f von f 0 mit:

dom(f) = M, rng(f) ⊆ N  oder  dom(f) ⊆ M, rng(f) = N.

Ist |M| < |N|, so existiert eine injektive Fortsetzung f von f0 mit f : M  N.

 Es gibt also keine Approximationen f0, die in eine Sackgasse führen würden: Jede solche Approximation lässt sich bis ans Ziel bringen.

Übung

Gilt in der Situation des Korollars lediglich |M| ≤ |N|, so existiert im Allgemeinen keine injektive Fortsetzung f von f 0 mit f : M  N.