Der Satz von Cantor-Bernstein (Äquivalenzsatz)
Den Zusammenhang von |A| = |B| und |A| ≤ |B| klärt der folgende Äquivalenzsatz. Cantor hatte diesen Satz bereits 1883 formuliert. Bewiesen wurde er dann erst in einem von Cantor geleiteten Seminar in Halle im Jahre 1897 von dem damals 19-jährigen Felix Bernstein, der die Arbeiten von Cantor studiert und dabei seinen Beweis entdeckt hatte. Cantor hatte in der Zeit seiner schöpferischen Höchstleistungen in Halle keine Schüler um sich. Die mathematischen Zentren waren damals Göttingen und Berlin. Hätte man dort von Anfang an die Mengenlehre in ihrer Bedeutung erkannt, wären wahrscheinlich Beweise des Äquivalenz- und Vergleichbarkeitssatzes viel früher gefunden worden. Cantor musste alles alleine machen. Schüler hätten ihn gestützt, nicht nur im Auffinden von Beweisen, sondern auch durch die bloße Möglichkeit zur Diskussion über offene und interessante Fragen der Mengenlehre. Ein einziger kluger Kopf, der Cantor dazu bewegt hätte, sein Wissen um die „Paradoxien der Mengenlehre“ genauer zu formulieren, hätte genügt, um einen Übergang der Mathematik in ihr modernes Zeitalter einzuleiten, ohne dass dabei Porzellan zerschlagen worden wäre. Verlassen wir aber diese, wie der Logiker Georg Kreisel sicherlich sagen würde, „Kaffeehausdiskussion“ und wenden uns dem Beweis des Satzes von Cantor-Bernstein zu.
Vorbemerkungen zum folgenden Beweis
Unser Beweis des Satzes von Cantor-Bernstein verwendet die natürlichen Zahlen ℕ und die rekursive Definition von Objekten: Es wird eine Folge
o0, o1, o2, …
von Objekten konstruiert. Bei der Definition von on darf dabei auf alle oi mit i < n zurückgegriffen werden. Der Leser betrachte als Beispiel die Definition der Fakultät n! für n ∈ ℕ: Man setzt 0! = 1 und definiert dann für n ∈ ℕ rekursiv (n + 1)! = n! · (n + 1).
So wie man Objekte durch Rekursion definieren kann, kann man Beweise durch Induktion führen: Man will zeigen, dass eine Aussage A(n) für alle natürlichen Zahlen gilt. Hierzu genügt es zu zeigen:
(1) | A(0) gilt (Induktionsanfang). |
(2) | Für alle n ∈ ℕ gilt: Aus der Gültigkeit von A(n) folgt die Gültigkeit von A(n + 1) (Induktionsschritt von n nach n + 1). |
Eine wichtige Variante des Induktionsschritts ist: (2′) Für alle n ∈ ℕ gilt: Aus der Gültigkeit von A(m) für alle m < n folgt die Gültigkeit von A(n). Oft reicht die erste Form, zuweilen ist die zweite Form, bei der man im Induktionsschritt alles, was man „bereits bewiesen“ hat, mitführt, von Vorteil. Zudem liefert (2′) den Induktionsanfang (1) kostenlos mit.
In der Mengenlehre lässt sich beweisen, dass rückbezügliche Definitionen und induktives Beweisen gerechtfertigt sind; für jetzt nehmen wir diese Verfahren als legitim an, wie es auch sonst überall in der Mathematik geschieht. (Vgl. hierzu auch die Diskussion in 2. 7.)
Ernst Zermelo hat 1908 den Bernsteinschen Beweis so umgestaltet, dass dabei die natürlichen Zahlen und die Rekursion vermieden werden können. Da die einfache Idee des Beweises, auf die es uns hier ankommt, dabei eher verwischt wird, gehen wir den anderen Weg. Der Äquivalenzsatz zählt wieder zu den Sätzen, deren „Grund der Gültigkeit“ man vor Augen sehen kann, diesmal allerdings wohl nur durch genaues Studium eines Beweises. Der Satz besagt: Aus |M| ≤ |N| und |N| ≤ |M| folgt |N| =|M|, d. h. wenn es Injektionen f : M → N und g : N → M gibt, so gibt es auch eine Bijektion
h : M → N.
Dies ist keineswegs klar.
Wir beweisen vorab einen Satz, dessen Aussage der Intuition sehr entgegen kommt, und aus dem sich der Satz von Cantor-Bernstein in wenigen Zeilen ergibt. Dieser vorbereitende Satz besagt, dass eine zwischen zwei gleichmächtigen Mengen N ⊆ M bzgl. der Inklusion „eingezwickte“ dritte Menge N′ ebenfalls zu N und M gleichmächtig ist. Das Gefühl sagt uns, dass dies gelten sollte.
Satz (Inklusionssatz)
Seien M, N Mengen mit N ⊆ M und |N| = |M|. Weiter sei N′ eine Menge mit N ⊆ N′ ⊆ M. Dann gilt |N′| = |M| [ = |N| ].
Anders formuliert:
Seien A, B, C paarweise disjunkte Mengen mit |A ∪ B ∪ C| = |A|.
Dann gilt auch |A ∪ B ∪ C| = |A ∪ B|.
Beweis
Die Äquivalenz der beiden Aussagen ist klar: Wir setzen
A = N, B = N′ − N, C = M − N′,
und in der anderen Richtung
N = A, N′ = A ∪ B, M = A ∪ B ∪ C.
Wir zeigen die A-B-C-Formulierung. Sei also
f : A ∪ B ∪ C → A bijektiv.
Wir setzen C0 = C und definieren rekursiv:
Cn + 1 = f ″Cn für n ∈ ℕ.
Wir bilden also fortwährend die Bilder von C unter der Abbildung f.
Das folgende Diagramm veranschaulicht die Situation:
Es gilt für alle n ≥ 1: Cn ⊆ A wegen Cn ⊆ rng(f) = A.
Weiter sind die Mengen C0 , C1 , C2 , … paarweise disjunkt, wofür die Injektivität von f und C0 ∩ A = ∅ verantwortlich ist. Obwohl wir diese Aussage für den Beweis nicht brauchen, ist es nützlich, sie sich klar zu machen; zudem rechtfertigt sie obiges Diagramm.
Beweis der Aussage „für alle m > n ist Cn ∩ Cm = ∅“ durch Induktion nach n.
Induktionsanfang n = 0:
Für m ≥ 1 gilt wegen Cm ⊆ A, dass
C0 ∩ Cm = ∅.
Induktionsschritt von n nach n + 1:
Annahme, es gibt ein
x ∈ Cn + 1 ∩ Cm + 1 = f″Cn ∩ f″Cm für ein m > n.
Dann ist aber f −1(x) ∈ Cn ∩ Cm, im Widerspruch zur Induktionsvoraussetzung. Also gilt Cn + 1 ∩ Cm + 1 = ∅ für alle m > n.
Sei nun
C* = ⋃n ∈ ℕ Cn.
Wir definieren nun eine Funktion h : A ∪ B ∪ C → A ∪ B durch:
Dann ist offenbar h injektiv und rng(h) = A ∪ B.
Also h : A ∪ B ∪ C → A ∪ B bijektiv wie gewünscht.
Die Funktion h macht das folgende: Wir bilden C0 bijektiv durch f auf die Menge C1 = f″C0 ab. Die Elemente von C1 schicken wir bijektiv nach C2, dann schicken wir die Elemente von C2 bijektiv nach C3 usw., wobei wir immer f zum Transport verwenden. Für alle n ist f : Cn → Cn + 1 bijektiv und es gilt
h|C* = f|C* : C* → C* − C0
bijektiv.
Auf der ganzen Restmenge (A − ⋃n ≥ 1 Cn) ∪ B ist h die Identität, und damit ist diese Restmenge trivialerweise Teil des Wertebereichs.
Im Grunde ist es ein einfacher Satz.
Bei der Untersuchung der verschiedenen Möglichkeiten, Unendlichkeit zu definieren, werden uns ganz ähnliche Ideen noch einmal begegnen. Wir werden dort die Orbits x, f (x), f (f (x)), … von Punkten x unter injektiven Funktionen genauer studieren.
Übung
(i) | Seien A ⊆ B ⊆ C ⊆ D, |A| = |C|, |B| = |D|. Dann gilt |A| = |D|. |
(ii) | Sei I = { x ∈ ℝ | 0 < x ≤ 1 }, und sei R = { x ∈ I | die ersten 100 Nachkommastellen von x (in der kanonischen Dezimaldarstellung) sind 0, 1, 2 oder 3 }. Dann gilt |R| = |I|. |
(iii) | Seien A, B, C Mengen mit |A| = |A ∪ B|, |A| = |A ∪ C|, wobei die Mengen B und C nicht notwendig disjunkt sind. Dann gilt |A| = |A ∪ B ∪ C|. |
Cantor (1883b, § 13):
„Hat man irgendeine wohldefinierte Menge M von der zweiten Mächtigkeit, eine Teilmenge M′ von M und eine Teilmenge M″ von M′ und weiß man, dass die letztere M″ gegenseitig eindeutig abbildbar ist auf die erste M, so ist immer auch die zweite M′ gegenseitig eindeutig abbildbar auf die erste und daher auch auf die dritte.
… es scheint mir aber höchst bemerkenswert und ich hebe es daher ausdrücklich hervor, dass dieser Satz allgemeine Gültigkeit hat, gleichviel welche Mächtigkeit der Menge M zukommen mag. Darauf will ich in einer späteren Abhandlung näher eingehen und alsdann das eigentümliche Interesse nachweisen, welches sich an diesen allgemeinen Satz knüpft.“
Wir erhalten nun sofort:
Korollar (Äquivalenzsatz von Cantor-Bernstein)
Seien M, Q Mengen mit |M| ≤ |Q| und |Q| ≤ |M|.
Dann gilt |M| = |Q|.
Beweis
Seien f : M → Q injektiv und g : Q → M injektiv.
Sei N = rng(g ∘ f), N′ = rng(g).
Dann gilt N ⊆ N′ ⊆ M und |N| = |M|, denn g ∘ f : M → N ist bijektiv.
Nach dem Satz oben ist also |N′| = |M|.
Aber es gilt |Q| = |N′|, denn g : Q → rng(g) = N′ ist bijektiv.
Also |Q| = |N′| = |M|.
Mit Hilfe des Satzes kann man die Aufgabe:
(+) Zeige |A| = |B|.
in die beiden in vielen Fällen einfacheren Teilaufgaben
(+1) Zeige |A| ≤ |B| und (+2) Zeige |B| ≤ |A|.
zerlegen (vgl. A = B gdw A ⊆ B und B ⊆ A).
Ernst Zermelos Beweis (veröffentlicht 1908, brieflich mitgeteilt an David Hilbert 1905 und Henri Poincaré (1854 − 1912) 1906) ohne natürliche Zahlen behandeln wir in folgender Übung. Zermelo beruft sich bei seinem Beweis auf Dedekind. In der Tat hatte Dedekind bereits 1887 einen Beweis des Äquivalenzsatzes gefunden, diesen aber nicht klar herausgestellt − er ist heute im Nachlaßteil seiner „Gesammelten Werke“ zu finden [Dedekind 1930 − 1932, Band III, S. 447ff]. Unabhängig wurde dieser Beweis auch entdeckt von Peano 1906 und Alwin Korselt (1864 − 1947) 1911.
Übung
Wir zeigen den Inklusionssatz, wie oben folgt dann der Äquivalenzsatz.
Sei f : A ∪ B ∪ C → A bijektiv, wobei A, B, C paarweise disjunkt.
Wir setzen Z = ⋂ { D ⊆ A ∪ C | C ⊆ D und für alle x ∈ D ist f (x) ∈ D }.
(i) | Es gilt C ⊆ Z und für alle x ∈ Z ist f (x) ∈ Z. |
(ii) | Ist x ∈ Z − C, so ist f −1(x) ∈ Z. Folglich f″Z = Z − C. |
(iii) | Definiere h : A ∪ B ∪ C → A ∪ B durch h(x) = f (x), falls x ∈ Z, h(x) = x, falls x ∉ Z. Dann ist h : A ∪ B ∪ C → A ∪ B bijektiv. |
[De facto gilt Z = C* mit C* wie im Beweis oben und die konstruierten Bijektionen h sind dieselben. Z wird hier aber „von oben“ als Schnitt definiert; der Aufbau von Z = C* „von unten“ (induktiv) gibt sicher ein klareres Bild von Z.]
Wir geben nun noch einen weiteren Beweis des Satzes von Cantor-Bernstein, der 1906 von Julius König (1849 − 1913) gefunden wurde. Im Grunde konstruieren wir die gleiche Bijektion wie oben, aber der Beweis erzeugt eine etwas andere Vorstellung von dieser Bijektion. Der Inklusionssatz wird nicht verwendet.
Weiterer Beweis des Satzes von Cantor-Bernstein
Seien f : M → Q und g : Q → M injektiv. Ohne Einschränkung seien M und Q disjunkt.
[Andernfalls ersetze M durch M × { 0 } und Q durch Q × { 1 } und modifiziere f und g entsprechend; ein bijektives h′ : M × { 0 } → Q × { 1 } liefert dann auch ein bijektives h : M → Q. Der Beweis funktioniert auch direkt für beliebige M und Q. Aber für das innere Auge (und für Skizzen) ist der Fall M ∩ Q = ∅ ästhetischer.]
Wir suchen wieder eine Bijektion h : M → Q. Hierzu klassifizieren wir die Elemente x aus M nach dem Typ der durch sie laufenden f-g-Urbildkette: Sei x ∈ M. Wir setzen x0 = x und definieren solange wie möglich:
x1 = g−1(x0),
x2 = f −1(g−1(x0)) = f −1(x1),
x3 = g−1(x2),
x4 = f −1(x3), …
Allgemein setzen wir
solange die Urbilder existieren.
Ist xn für alle n ∈ ℕ definiert, so sagen wir: x ist vom Typ I.
Ist das letzte definierte xn ∈ M, d. h. g−1(xn) existiert nicht, so sagen wir:
x ist vom Typ II.
Ist das letzte definierte xn ∈ Q, d. h. f −1(xn) existiert nicht, so sagen wir:
x ist vom Typ III.
Offenbar kann ein x nicht von zwei verschiedenen Typen zugleich sein.
Der Leser verfolge an einer Skizze den Ziehharmonika-Kurs x = x0, x1, x2, … der Urbilder von x unter den Abbildungen f und g. Dieser Kurs kann abbrechen − u. U. schon bei x0 −, weil f und g nicht notwendig surjektiv sind. Er kann unendlich sein, z. B. für den Fall g(f (x)) = x; hier lautet die Urbildfolge
x, f (x), x, f (x), …
Eine Urbildfolge eines x vom Typ I kann natürlich auch aus unendlich vielen paarweise verschiedenen Elementen bestehen.
Wir setzen nun für x ∈ M:
Dann ist h : M → Q die gewünschte Bijektion, wovon der Leser sich mit Freuden überzeugt.
Auch h : M → Q mit h(x) = f (x), falls x vom Typ II, h(x) = g−1(x), falls x vom Typ I oder III wäre eine Bijektion von M nach Q. Auf Typ I könnte man weiter auch doppelt verschieben: h(x) = f (f (x)), usw. Wichtig ist nur, dass wir die schließlich endenden Urbildketten gemäß ihrem Ende in M oder Q unterschiedlich behandeln.
Schließlich kann man den Satz von Cantor-Bernstein auch mit einem auf Bronisław Knaster und Alfred Tarski zurückgehenden Fixpunktsatz beweisen, wobei hier der Fixpunktsatz interessanter ist als seine Anwendung auf den Äquivalenzsatz, die im Grunde nur den Beweis von Dedekind-Zermelo wiederholt. Wir behandeln diesen Ansatz in der folgenden Übung.
Übung
Sei M eine Menge. Eine Funktion g : ℘(M) → ℘(M) heißt monoton, falls für alle x, y ∈ ℘(M) gilt: x ⊆ y folgt g(x) ⊆ g(y). Ein Element x von M heißt ein Fixpunkt von g, falls g(x) = x gilt.
(i) | Seien M eine Menge und g : ℘(M) → ℘(M) monoton. Dann existiert ein kleinster Fixpunkt von f, d. h. es gibt ein y ∈ ℘(M) mit: g(y) = y und für alle x ⊆ y gilt g(x) ≠ x. [Wir setzen y = ⋂ { x ⊆ M | g(x) ⊆ x } (es gilt z. B. g(M) ⊆ M).] |
(ii) | Zeigen Sie den Inklusionssatz (und damit den Satz von Cantor-Bernstein) mit Hilfe eines kleinsten Fixpunktes einer geeignet definierten monotonen Funktion. [Sei D = A ∪ B ∪ C und f : D → A bijektiv. Wir definieren g : ℘(D) → ℘(D) durch g(x) = f″x ∪ C. Dann ist g monoton. Der kleinste Fixpunkt von g ist gerade unser früheres C*.] |
Analog existiert für ein monotones g : ℘(M) → ℘(M) ein ⊆-größter Fixpunkt. Für die monotone Funktion g in (ii) ist (A ∪ B ∪ C) − B* der größte Fixpunkt von g, wobei B* analog zu C* definiert ist, also B = ⋃n ∈ ℕ Bn mit B0 = B, Bn + 1 = f″Bn. Weiter ist die Funktion h′ : D → A ∪ B mit h′(x) = f (x) für x ∉ B*, h′(x) = x für x ∈ B* bijektiv. Hier ist also der Anteil der Identität kleiner, falls kleinster und größter Fixpunkt verschieden sind, d. h. falls B* ∪ C* ≠ D. Alle bekannten „elementaren“ Beweise des Satzes von Cantor-Bernstein konstruieren letztendlich eine der Abbildungen h oder h′.
Die obigen Beweise des Satzes von Cantor-Bernstein sind zwar trickreich, insgesamt aber weniger abstrakt als etwa der sehr übersichtliche und einfache Beweis, dass aus der Existenz einer Surjektion f : A → B die Existenz einer Injektion g : B → A folgt. Ein „ein …“ wird hier nirgendwo gebraucht. Während sonst, wie wir sehen werden, im Bereich der Mächtigkeitstheorie Vermutungen mit den schwersten Geschützen solange angeschossen werden, bis sie sich endlich beweisen oder widerlegen lassen, genügt zum Beweis des Satzes von Cantor-Bernstein eine letztendlich simple trojanische Kriegslist.
Wir verweisen den Leser auf [Deiser 2008] und [Rautenberg 1987] für weitere historische Bemerkungen und Beweise des Satzes.