Satz von Cantor-Bernstein-Schröder

Der Satz v​on Cantor-Bernstein-Schröder o​der kurz Äquivalenzsatz i​st ein Satz d​er Mengenlehre über d​ie Mächtigkeiten zweier Mengen. Er i​st nach d​en Mathematikern Georg Cantor (der i​hn als erster formuliert hat), Felix Bernstein s​owie Ernst Schröder (die Beweise veröffentlichten) benannt u​nd wird i​n der Literatur a​uch als Cantor-Bernstein-Schröderscher [Äquivalenz-]Satz, Satz v​on Cantor-Bernstein, Äquivalenzsatz v​on Cantor-Bernstein, Satz v​on Schröder-Bernstein o​der ähnlich bezeichnet. Allerdings w​urde er unabhängig a​uch von Richard Dedekind bewiesen.

Der Satz besagt: Ist e​ine Menge A gleichmächtig z​u einer Teilmenge e​iner zweiten Menge B u​nd ist d​iese zweite Menge B gleichmächtig z​u einer Teilmenge d​er ersten Menge A, s​o sind A u​nd B gleichmächtig.

Der Satz v​on Cantor-Bernstein-Schröder i​st ein wichtiges Hilfsmittel b​eim Nachweis d​er Gleichmächtigkeit zweier Mengen.

Geschichte

Der Äquivalenzsatz w​urde 1887 v​on Georg Cantor formuliert, a​ber erst 1897 v​om 19-jährigen Felix Bernstein i​n einem v​on Georg Cantor geleiteten Seminar u​nd etwa gleichzeitig unabhängig v​on Ernst Schröder bewiesen. Cantor teilte Bernsteins Beweis n​och im gleichen Jahr Émile Borel a​uf dem ersten internationalen Mathematiker-Kongress i​n Zürich mit.[1][2]

Cantors erste Erwähnung des Äquivalenzsatzes, 1887[3]

Cantor h​atte diesen Äquivalenzsatz erstmals i​n seiner philosophischen Abhandlung Mitteilungen z​ur Lehre v​om Transfiniten[3] a​us dem Jahre 1887 (ohne Beweis) mitgeteilt. In seiner großen Arbeit Beiträge z​ur Begründung d​er transfiniten Mengenlehre[4] v​on 1895 h​at Cantor diesen Satz erneut aufgestellt u​nd aus d​em Vergleichbarkeitssatz für Kardinalzahlen gefolgert. Den Vergleichbarkeitssatz konnte Cantor jedoch n​icht beweisen. Er i​st nach Friedrich Moritz Hartogs (Über d​as Problem d​er Wohlordnung, 1915)[5] m​it dem Auswahlaxiom (bzw. Auswahlprinzip o​der Wohlordnungssatz) äquivalent.

Dedekind selbst fand den Beweis des Äquivalenzsatzes (welcher sich in seinem Nachlass fand) bereits am 11. Juli 1887, jedoch publizierte er ihn nicht und teilte ihn auch nicht Cantor mit.[6]
Ernst Zermelo entdeckte Dedekinds Beweis wieder und gab 1908 in seiner Abhandlung Untersuchungen über die Grundlagen der Mengenlehre I[7] einen Beweis, wobei er auf die Dedekindsche Kettentheorie aus Dedekinds Schrift Was sind und was sollen die Zahlen? (1888)[8] zurückgriff. Giuseppe Peano gab einen ähnlichen Beweis, wobei es zu einem Prioritätsstreit mit Zermelo kam. Beide Beweise waren die Folge einer Herausforderung von Henri Poincaré, der um 1905 nach Beweisen verlangte, die ohne vollständige Induktion auskommen. Aufgrund von Poincarés Herausforderung wurde auch der Beweis von Julius König publiziert und weitere Forschung angeregt.

Ernst Schröder h​atte 1896 (Ueber z​wei Definitionen d​er Endlichkeit u​nd G. Cantor’sche Sätze)[9] e​ine Beweisskizze publiziert, d​ie sich allerdings a​ls falsch herausstellte, w​ie Alwin Reinhold Korselt 1911 (Über e​inen Beweis d​es Äquivalenzsatzes)[10] bemerkt hatte; Schröder h​at dort d​en Fehler i​n seinem Beweis bestätigt.

Dass d​er Satz a​uch ohne Auswahlaxiom beweisbar ist, h​aben Richard Dedekind 1887 u​nd Bernstein 1898 i​n seiner Dissertation gezeigt (Bernsteins Beweis erschien zuerst i​n Borels Leçons s​ur la théorie d​es fonctions[11] u​nd dann nochmals i​n Bernsteins Abhandlung Untersuchungen a​us der Mengenlehre).[12]

Es g​ibt noch zahlreiche weitere Beweise d​es Satzes.[13]

Eine passende Bezeichnung für d​en Äquivalenzsatz wäre Cantor-Dedekindscher Äquivalenzsatz o​der Cantor-Dedekind-Bernsteinscher Äquivalenzsatz. Zudem h​at Bernstein darauf hingewiesen, d​ass Cantor selbst d​ie Bezeichnung „Äquivalenzsatz“ vorgeschlagen habe.[14]

Satz

Das Cantor-Bernstein-Schröder-Theorem lautet:

Sei eine Menge ${\displaystyle A}$ gleichmächtig zu einer Teilmenge einer Menge ${\displaystyle B}$, und sei ${\displaystyle B}$ gleichmächtig zu einer Teilmenge von ${\displaystyle A}$. Dann sind ${\displaystyle A}$ und ${\displaystyle B}$ gleichmächtig.[15][16]

Dabei heißen zwei Mengen gleichmächtig, wenn es eine bijektive Abbildung zwischen ihnen gibt. Ausgedrückt durch die Mächtigkeiten von ${\displaystyle A}$ und ${\displaystyle B}$ lautet das Theorem:

Aus ${\displaystyle |A|\leqq |B|}$ und ${\displaystyle |B|\leqq |A|}$ folgt ${\displaystyle |A|=|B|}$.

Dabei gilt ${\displaystyle |A|=|B|}$ genau dann, wenn ${\displaystyle A}$ und ${\displaystyle B}$ gleichmächtig sind, und ${\displaystyle |A|\leqq |B|}$ gilt genau dann, wenn ${\displaystyle A}$ gleichmächtig zu einer Teilmenge von ${\displaystyle B}$ ist, das heißt, wenn es eine injektive Abbildung von ${\displaystyle A}$ in ${\displaystyle B}$ gibt. Ausgedrückt durch die Eigenschaften von Funktionen lautet das Theorem:

Seien ${\displaystyle A}$ und ${\displaystyle B}$ Mengen mit einer Injektion ${\displaystyle f\colon A\to B}$ und einer Injektion ${\displaystyle g\colon B\to A}$. Dann existiert eine Bijektion ${\displaystyle h\colon A\to B}$.

Beweisidee

Im Folgenden i​st hier e​ine Beweisidee gegeben.

Definiere d​ie Mengen:

${\displaystyle C_{0}:=A\setminus g(B)}$,

${\displaystyle C_{n+1}:=g(f(C_{n}))\quad {\mbox{ für }}n\geqq 0}$,

${\displaystyle C:=\bigcup _{n=0}^{\infty }C_{n}}$.

Für jedes ${\displaystyle x}$ aus ${\displaystyle A}$ setze dann:

${\displaystyle h(x):={\begin{cases}f(x),&\mathrm {falls} \ x\in C,\\g^{-1}(x),&\mathrm {falls} \ x\notin C.\end{cases}}}$

Da im Falle, dass ${\displaystyle x}$ nicht in ${\displaystyle C}$ ist, ${\displaystyle x}$ in ${\displaystyle g(B)}$ liegen muss, gibt es ein eindeutig bestimmtes Element ${\displaystyle g^{-1}(x)}$ und ${\displaystyle h}$ ist eine wohldefinierte Abbildung von ${\displaystyle A}$ nach ${\displaystyle B}$.

Man kann nun zeigen, dass diese Funktion ${\displaystyle h\colon A\to B}$ die gewünschte Bijektion ist.

Beachte, dass diese Definition von ${\displaystyle h}$ nicht konstruktiv ist, d. h., es gibt kein Verfahren, um für beliebige Mengen ${\displaystyle A}$, ${\displaystyle B}$ und Injektionen ${\displaystyle f}$, ${\displaystyle g}$ in endlich vielen Schritten zu entscheiden, ob ein ${\displaystyle x}$ aus ${\displaystyle A}$ in ${\displaystyle C}$ liegt oder nicht. Für spezielle Mengen und Abbildungen kann das natürlich möglich sein.

Ein kurzer u​nd leicht verständlicher Beweis findet s​ich auch i​n dem Göschen-Bändchen Mengenlehre Erich Kamkes.[17]

Veranschaulichung

Beispiel der Definition von h

Veranschaulichen kann man sich die Definition von ${\displaystyle h}$ anhand der nebenstehenden Darstellung.

Dargestellt sind Teile der (disjunkten) Mengen ${\displaystyle A}$ und ${\displaystyle B}$ sowie die Abbildungen ${\displaystyle f}$ und ${\displaystyle g}$. Betrachtet man ${\displaystyle A}$ vereinigt ${\displaystyle B}$ als Graphen, dann zerfällt der Graph in verschiedene Zusammenhangskomponenten. Diese lassen sich in vier Typen einteilen:

1. beidseitig unendliche Pfade;
2. endliche Zyklen;
3. unendliche Pfade, die in ${\displaystyle A}$ beginnen;
4. unendliche Pfade, die in ${\displaystyle B}$ beginnen

(von jedem Typ ist hier einer vertreten, da der Pfad durch das Element ${\displaystyle a}$ beidseitig unendlich sein soll). Es ist aber allgemein nicht in endlich vielen Schritten entscheidbar, welchen Typ der durch ein vorgegebenes Element gehende Pfad hat.

Die im Abschnitt Beweisidee definierte Menge ${\displaystyle C}$ enthält nun genau die Elemente von ${\displaystyle A}$, die Teil eines in ${\displaystyle A}$ beginnenden Pfades sind. Die Abbildung ${\displaystyle h}$ wird so definiert, dass sie innerhalb einer jeden Zusammenhangskomponente eine Bijektion der ${\displaystyle A}$-Elemente auf „im Pfad benachbarte“ ${\displaystyle B}$-Elemente herstellt (dabei hat man bei den beidseitig unendlichen Pfaden und den endlichen Zyklen eine Richtungswahl und man legt sich auf „rückwärts“ fest).

Verallgemeinerung

Das Cantor-Bernstein-Schröder-Theorem erweist s​ich als direkte Folge d​es banachschen Abbildungssatzes.[18][19]

Siehe auch

• Vergleichbarkeitssatz

Literatur

• Felix Bernstein: Untersuchungen aus der Mengenlehre. Buchdruckerei des Waisenhauses, Halle a. S. 1901 (Internet Archive – Inaugural-Dissertation bei David Hilbert).
  • Felix Bernstein: Untersuchungen aus der Mengenlehre. In: Felix Klein, Walther von Dyck, David Hilbert (Hrsg.): Mathematische Annalen. Band 61, Nr. 1. B. G. Teubner, 1905, ISSN 0025-5831, S. 117–155, doi:10.1007/BF01457734 (gdz.sub.uni-goettingen.de [PDF] unveränderte Auflage bis auf einige Verbesserungen sowie Bemerkungen).
• Émile Borel: Leçons sur la théorie des fonctions. Gauthier-Villars et fils, Paris 1898, S. 103 ff. (Textarchiv – Internet Archive).
• Günter Bruns, Jürgen Schmidt: Eine Verschärfung des Bernsteinschen Äquivalenzsatzes. In: Heinrich Behnke, Richard Courant, Heinz Hopf, Gottfried Köthe, Kurt Reidemeister, Bartel L. van der Waerden (Hrsg.): Mathematische Annalen. Band 135, Nr. 3. Springer-Verlag, 1958, ISSN 0025-5831, S. 257–262, doi:10.1007/BF01351802 (gdz.sub.uni-goettingen.de [PDF] eingegangen am 3. Januar 1958).
• Georg Cantor: Grundlagen einer allgemeinen Mannichfaltigkeitslehre. Ein mathematisch-philosophischer Versuch in der Lehre des Unendlichen. Commissions-Verlag von B. G. Teubner, Leipzig 1883 (digital.slub-dresden.de [PDF]).
  • Georg Cantor: Ueber unendliche, lineare Punktmannichfaltigkeiten. 5. In: Felix Klein, Adolph Mayer (Hrsg.): Math. Ann. Band 21, Nr. 4. B. G. Teubner, 1883, ISSN 0025-5831, S. 545–591, doi:10.1007/BF01446819 (gdz.sub.uni-goettingen.de [PDF] Nachdruck; Halle, Oktober 1882).
• Georg Cantor: Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. Mit erläuternden Anmerkungen sowie mit Ergänzungen aus dem Briefwechsel Cantor–Dedekind. Hrsg.: Adolf Fraenkel (Lebenslauf); Ernst Zermelo. Verlag von Julius Springer, Berlin 1932 (gdz.sub.uni-goettingen.de).
• Richard Dedekind: Was sind und was sollen die Zahlen? 2., unveränderte Auflage. Friedrich Vieweg & Sohn, Braunschweig 1893 (echo.mpiwg-berlin.mpg.de – Erstausgabe: 1888).
• Richard Dedekind: Gesammelte mathematische Werke. Hrsg.: Robert Fricke, Emmy Noether, Øystein Ore. Band 3. Friedr. Vieweg & Sohn, Braunschweig 1932 (gdz.sub.uni-goettingen.de).
• Friedrich Moritz Hartogs: Über das Problem der Wohlordnung. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Band 76, Nr. 4. B. G. Teubner, 1915, ISSN 0025-5831, S. 438–443, doi:10.1007/BF01458215 (gdz.sub.uni-goettingen.de [PDF] Juli 1914).
• Alwin Reinhold Korselt: Über einen Beweis des Äquivalenzsatzes. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Band 70, Nr. 2. B. G. Teubner, 1911, ISSN 0025-5831, S. 294–296, doi:10.1007/BF01461161 (gdz.sub.uni-goettingen.de [PDF] Ende April 1910).
• Ernst Schröder: Ueber zwei Definitionen der Endlichkeit und G. Cantor’sche Sätze. In: Kaiserliche Leopoldino-Carolinische Deutsche Akademie der Naturforscher (Hrsg.): Nova Acta, Abhandlungen der Kaiserl. Leop.-Carol. Deutschen Akademie der Naturforscher. Band 71, Nr. 6. Johann Ambrosius Barth Verlag, Halle a. S. 1898, S. 303–376 (biodiversitylibrary.org – Februar 1896, eingegangen am 21. Mai 1896).
• Ernst Zermelo: Untersuchungen über die Grundlagen der Mengenlehre. I. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Band 65, Nr. 2. B. G. Teubner, 1908, ISSN 0025-5831, S. 261–281, doi:10.1007/BF01449999 (gdz.sub.uni-goettingen.de [PDF] 30. Juli 1907).
• Arie Hinkis: Proofs of the Cantor-Bernstein theorem, a mathematical excursion. Birkhäuser 2013.

Weblinks

• Martin_Infinite: Der Satz von Schröder-Bernstein ‒ Explizit. Matroids Matheplanet, 19. November 2005, abgerufen am 13. September 2021.

Einzelnachweise

1. Oliver Deiser: Einführung in die Mengenlehre. Die Mengenlehre Georg Cantors und ihre Axiomatisierung durch Ernst Zermelo. 3., korrigierte Auflage. Springer-Verlag, Berlin/Heidelberg 2010, ISBN 3-540-20401-6, S. 71, 501, doi:10.1007/978-3-642-01445-1 (eingeschränkte Vorschau in der Google-Buchsuche).
2. Patrick Suppes: Axiomatic Set Theory. 1. Auflage. Dover Publications, New York 1972, ISBN 0-486-61630-4, S. 95 f. (eingeschränkte Vorschau in der Google-Buchsuche).
3. Georg Cantor: Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. Mit erläuternden Anmerkungen sowie mit Ergänzungen aus dem Briefwechsel Cantor–Dedekind. Hrsg.: Adolf Fraenkel [Lebenslauf], Ernst Zermelo. Verlag von Julius Springer, Berlin 1932, S. 378–439, dort S. 413 (gdz.sub.uni-goettingen.de).
4. Georg Cantor: Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. Mit erläuternden Anmerkungen sowie mit Ergänzungen aus dem Briefwechsel Cantor–Dedekind. Hrsg.: Adolf Fraenkel [Lebenslauf], Ernst Zermelo. Verlag von Julius Springer, Berlin 1932, Satz B, S. 285 (gdz.sub.uni-goettingen.de).
5. Friedrich M. Hartogs: Über das Problem der Wohlordnung. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Band 76, Nr. 4. B. G. Teubner, 1915, ISSN 0025-5831, S. 438–443, doi:10.1007/BF01458215 (gdz.sub.uni-goettingen.de [PDF] Juli 1914).
6. Richard Dedekind: Gesammelte mathematische Werke. Hrsg.: Robert Fricke, Emmy Noether, Øystein Ore. Band 3. Friedr. Vieweg & Sohn, Braunschweig 1932, Kap. 62, S. 447–449 (GDZ – 11.07.1887).
7. Ernst Zermelo: Untersuchungen über die Grundlagen der Mengenlehre. I. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Band 65, Nr. 2. B. G. Teubner, 1908, ISSN 0025-5831, S. 261–281, doi:10.1007/BF01449999 (gdz.sub.uni-goettingen.de [PDF] 30. Juli 1907).
8. Richard Dedekind: Was sind und was sollen die Zahlen? 2., unveränderte Auflage. Friedr. Vieweg & Sohn, Braunschweig 1893 (echo.mpiwg-berlin.mpg.de – Erstausgabe: 1888).
9. Ernst Schröder: Ueber zwei Definitionen der Endlichkeit und G. Cantor’sche Sätze. In: Kaiserliche Leopoldino-Carolinische Deutsche Akademie der Naturforscher (Hrsg.): Nova Acta. Band 71, Nr. 6. Johann Ambrosius Barth Verlag, Halle a. S. 1898, S. 303–376 (biodiversitylibrary.org – Februar 1896, eingegangen am 21. Mai 1896).
10. Alwin R. Korselt: Über einen Beweis des Äquivalenzsatzes. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Band 70, Nr. 2. B. G. Teubner, 1911, ISSN 0025-5831, S. 294–296, doi:10.1007/BF01461161 (gdz.sub.uni-goettingen.de [PDF] Ende April 1910).
11. Émile Borel: Leçons sur la théorie des fonctions. Gauthier-Villars et fils, Paris 1898, S. 103 ff. (Textarchiv – Internet Archive).
12. Felix Bernstein: Untersuchungen aus der Mengenlehre. Buchdruckerei des Waisenhauses, Halle a. S. 1901 (archive.org – Inaugural-Dissertation bei David Hilbert).
    Felix Bernstein: Untersuchungen aus der Mengenlehre. In: Felix Klein, Walther von Dyck, David Hilbert (Hrsg.): Math. Ann. Band 61, Nr. 1. B. G. Teubner, 1905, ISSN 0025-5831, S. 117–155, doi:10.1007/BF01457734 (gdz.sub.uni-goettingen.de [PDF] unveränderte Auflage bis auf einige Verbesserungen sowie Bemerkungen).
13. Das Buch von Hinkis (2013) untersucht etwa 30 Beweise, alle vor 1973
14. Felix Hausdorff: Grundzüge der Mengenlehre. In: Egbert Brieskorn, Srishti D. Chatterji u. a. (Hrsg.): Gesammelte Werke. 1. Auflage. Band 2. Springer-Verlag, Berlin / Heidelberg 2002, ISBN 3-540-42224-2, S. 587 (eingeschränkte Vorschau in der Google-Buchsuche). Original von 1914
15. Rudolf Lipschitz: Grundlagen der Analysis. In: Grundlagen der Analysis. 1. Auflage. Band 1. Max Cohen & Sohn (Friedrich Cohen) Verlag, Bonn 1877.
16. Arthur Moritz Schoenflies: Die Entwickelung der Lehre von den Punktmannigfaltigkeiten. In: Guido Hauck, August Gutzmer (Hrsg.): Jahresbericht der Deutschen Mathematiker-Vereinigung. Band 8, Nr. 2. B. G. Teubner, 1900, ISSN 0012-0456 (DigiZeitschriften).
17. Erich Kamke: Mengenlehre (= Sammlung Göschen. Band 999 [a]). 7. Auflage. Walter de Gruyter & Co., Berlin/New York 1971, ISBN 3-11-003911-7, § 10, S. 34–36.
18. Heinz Lüneburg: Kombinatorik. In: Elemente der Mathematik vom höheren Standpunkt aus. 1. Auflage. Band 6. Birkhäuser Verlag, Basel u. a. 1971, ISBN 3-7643-0548-7, S. 66.
19. Heinz Lüneburg: Tools and Fundamental Constructions of Combinatorial Mathematics. 1. Auflage. BI Wissenschaftsverlag, Mannheim u. a. 1989, ISBN 3-411-03194-8, S. 349.