Satz von Cantor-Bernstein-Schröder

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Mengenlehre ist der Satz von Cantor-Bernstein-Schröder oder kurz Äquivalenzsatz (in der Literatur uneinheitlich auch als Cantor-Bernstein-Schröderscher [Äquivalenz-]Satz, Satz von Cantor-Bernstein, Äquivalenzsatz von Cantor-Bernstein, Satz von Schröder-Bernstein oder Ähnliches bezeichnet) eine Aussage über die Mächtigkeiten zweier Mengen. Der nach den Mathematikern Georg Cantor, Felix Bernstein und Ernst Schröder benannte Äquivalenzsatz (obwohl sich beim Beweis Richard Dedekind ebenfalls sehr verdient gemacht hat) ist ein wichtiges Hilfsmittel beim Nachweis der Gleichmächtigkeit zweier Mengen.

Geschichte[Bearbeiten]

Der Äquivalenzsatz wurde 1887 von Georg Cantor formuliert, aber erst 1897 vom 19-jährigen Felix Bernstein in einem von Georg Cantor geleiteten Seminar und etwa gleichzeitig unabhängig von Ernst Schröder bewiesen. Cantor teilte Bernsteins Beweis noch im gleichen Jahr Émile Borel auf dem ersten internationalen Mathematiker-Kongress in Zürich mit.[1][2]

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

Cantor hatte diesen Äquivalenzsatz erstmals in seiner philosophischen Abhandlung Mitteilungen zur Lehre vom Transfiniten[3] aus dem Jahre 1887 (ohne Beweis) mitgeteilt. In seiner großen Arbeit Beiträge zur Begründung der transfiniten Mengenlehre[4] von 1895 hat Cantor diesen Satz erneut aufgestellt und aus dem Vergleichbarkeitssatz für Kardinalzahlen gefolgert. Den Vergleichbarkeitssatz konnte Cantor jedoch nicht beweisen. Er ist nach Friedrich Moritz Hartogs (Über das Problem der Wohlordnung, 1915)[5] mit dem Auswahlaxiom (bzw. Auswahlprinzip oder 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.

Ernst Schröder hatte 1896 (Ueber zwei Definitionen der Endlichkeit und G. Cantor’sche Sätze)[9] eine Beweisskizze publiziert, die sich allerdings als falsch herausstellte, wie Alwin Reinhold Korselt 1911 (Über einen Beweis des Äquivalenzsatzes)[10] bemerkt hatte; Schröder hat dort den Fehler in seinem Beweis bestätigt.

Dass der Satz auch ohne Auswahlaxiom beweisbar ist, haben Richard Dedekind 1887 und Bernstein 1898 in seiner Dissertation gezeigt (Bernsteins Beweis erschien zuerst in Borels Leçons sur la théorie des fonctions[11] und dann nochmals in Bernsteins Abhandlung Untersuchungen aus der Mengenlehre).[12]

Ein passende Bezeichnung für den Äquivalenzsatz wäre Cantor-Dedekindscher Äquivalenzsatz oder Cantor-Dedekind-Bernsteinscher Äquivalenzsatz. Zudem hat Bernstein darauf hingewiesen, dass Cantor selbst die Bezeichnung „Äquivalenzsatz“ vorgeschlagen habe.[13]

Satz[Bearbeiten]

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

Sei eine Menge A gleichmächtig zu einer Teilmenge einer Menge B, und sei B gleichmächtig zu einer Teilmenge von A. Dann sind A und B gleichmächtig.[14][15]

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

Aus |A| \leqq |B| und |B| \leqq |A| folgt |A| = |B|.

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

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

Beweisidee[Bearbeiten]

Im Folgenden ist hier eine Beweisidee gegeben.

Definiere die Mengen:

 C_0 := A \setminus g(B),
 C_{n+1} := g(f(C_n))\quad \mbox{ für } n\geqq 0,
 C := \bigcup_{n=0}^\infty C_n.

Für jedes x aus A setze dann:


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 x nicht in C ist, x in g(B) liegen muss, gibt es ein eindeutig bestimmtes Element g^{-1}(x) und h ist eine wohldefinierte Abbildung von A nach B.

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

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

Ein kurzer und leicht verständlicher Beweis findet sich auch in dem Göschen-Bändchen Mengenlehre Erich Kamkes.[16]

Veranschaulichung[Bearbeiten]

Beispiel der Definition von h

Veranschaulichen kann man sich die Definition von h anhand der nebenstehenden Darstellung.

Dargestellt sind Teile der (disjunkten) Mengen A und B sowie die Abbildungen f und g. Betrachtet man A vereinigt 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 A beginnen;
  4. unendliche Pfade, die in B beginnen

(von jedem Typ ist hier einer vertreten, da der Pfad durch das Element 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 C enthält nun genau die Elemente von A, die Teil eines in A beginnenden Pfades sind. Die Abbildung h wird so definiert, dass sie innerhalb einer jeden Zusammenhangskomponente eine Bijektion der A-Elemente auf „im Pfad benachbarte“ 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[Bearbeiten]

Das Cantor-Bernstein-Schröder-Theorem erweist sich als direkte Folge des banachschen Abbildungssatzes.[17][18]

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  •  Felix Bernstein: Untersuchungen aus der Mengenlehre. Buchdruckerei des Waisenhauses, Halle a. S. 1901 (Inaugural-Dissertation bei David Hilbert, Internet Archive).
 Felix Bernstein: Untersuchungen aus der Mengenlehre. In: Felix Klein, Walther von Dyck, David Hilbert (Hrsg.): Mathematische Annalen. Bd. 61, Nr. 1, B. G. Teubner, Leipzig 1905, ISSN 0025-5831, S. 117–155 (unveränderte Auflage bis auf einige Verbesserungen sowie Bemerkungen, PDF).
  •  Émile Borel: Leçons sur la théorie des fonctions. Gauthier-Villars et fils, Paris 1898, S. 103 ff. (Internet Archive).
 Georg Cantor: Ueber unendliche, lineare Punktmannichfaltigkeiten. 5. In: Felix Klein, Adolph Mayer (Hrsg.): Math. Ann. 21, Nr. 4, B. G. Teubner, Leipzig 1883, ISSN 0025-5831, S. 545–591 (Nachdruck; Halle, Oktober 1882, PDF).
  •  Friedrich Moritz Hartogs: Über das Problem der Wohlordnung. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Bd. 76, Nr. 4, B. G. Teubner, Leipzig 1915, ISSN 0025-5831, S. 438–443 (Juli 1914, PDF).
  •  Alwin Reinhold Korselt: Über einen Beweis des Äquivalenzsatzes. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Bd. 70, Nr. 2, B. G. Teubner, Leipzig 1911, ISSN 0025-5831, S. 294–296 (Ende April 1910, PDF).
  •  Ernst Zermelo: Untersuchungen über die Grundlagen der Mengenlehre. I. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Bd. 65, Nr. 2, B. G. Teubner, Leipzig 1908, ISSN 0025-5831, S. 261–281 (30. Juli 1907, PDF).

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  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. a b  Georg Cantor, Adolf Fraenkel (Lebenslauf); Ernst Zermelo (Hrsg.): Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. Mit erläuternden Anmerkungen sowie mit Ergänzungen aus dem Briefwechsel Cantor–Dedekind. Verlag von Julius Springer, Berlin 1932, S. 378–439, dort 413 (GDZ).
  4.  Georg Cantor, Adolf Fraenkel (Lebenslauf); Ernst Zermelo (Hrsg.): Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. Mit erläuternden Anmerkungen sowie mit Ergänzungen aus dem Briefwechsel Cantor–Dedekind. Verlag von Julius Springer, Berlin 1932, Satz B, S. 285 (GDZ).
  5.  Friedrich M. Hartogs: Über das Problem der Wohlordnung. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Bd. 76, Nr. 4, B. G. Teubner, Leipzig 1915, ISSN 0025-5831, S. 438–443 (Juli 1914, PDF).
  6.  Richard Dedekind, Robert Fricke, Emmy Noether, Øystein Ore (Hrsg.): Gesammelte mathematische Werke. Bd. 3, Friedr. Vieweg & Sohn, Braunschweig 1932, Kap. 62, S. 447–449 (11.07.1887, GDZ).
  7.  Ernst Zermelo: Untersuchungen über die Grundlagen der Mengenlehre. I. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Bd. 65, Nr. 2, B. G. Teubner, Leipzig 1908, ISSN 0025-5831, S. 261–281 (30. Juli 1907, PDF).
  8.  Richard Dedekind: Was sind und was sollen die Zahlen? Friedr. Vieweg & Sohn, Braunschweig 1888 (ECHO: 2., unveränderte Auflage, 1893).
  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. Bd. 71, Nr. 6, Johann Ambrosius Barth Verlag, Halle a. S. 1898, S. 303–376 (Februar 1896, eingegangen am 21. Mai 1896, online).
  10.  Alwin R. Korselt: Über einen Beweis des Äquivalenzsatzes. In: Felix Klein, Walther von Dyck, David Hilbert, Otto Blumenthal (Hrsg.): Math. Ann. Bd. 70, Nr. 2, B. G. Teubner, Leipzig 1911, ISSN 0025-5831, S. 294–296 (Ende April 1910, PDF).
  11.  Émile Borel: Leçons sur la théorie des fonctions. Gauthier-Villars et fils, Paris 1898, S. 103 ff. (Internet Archive).
  12.  Felix Bernstein: Untersuchungen aus der Mengenlehre. Buchdruckerei des Waisenhauses, Halle a. S. 1901 (Inaugural-Dissertation bei David Hilbert, Internet Archive).
     Felix Bernstein: Untersuchungen aus der Mengenlehre. In: Felix Klein, Walther von Dyck, David Hilbert (Hrsg.): Math. Ann. Bd. 61, Nr. 1, B. G. Teubner, Leipzig 1905, ISSN 0025-5831, S. 117–155 (unveränderte Auflage bis auf einige Verbesserungen sowie Bemerkungen, PDF).
  13.  Felix Hausdorff: Grundzüge der Mengenlehre. In: Egbert Brieskorn, Srishti D. Chatterji u. a. (Hrsg.): Gesammelte Werke. 1. Auflage. Bd. 2, Springer-Verlag, Berlin/Heidelberg 2002, ISBN 3-540-42224-2, S. 587 (eingeschränkte Vorschau in der Google-Buchsuche). Original von 1914
  14.  Rudolf Lipschitz: Grundlagen der Analysis. In: Grundlagen der Analysis. 1. Auflage. 1, Max Cohen & Sohn (Friedrich Cohen) Verlag, Bonn 1877.
  15.  Arthur Moritz Schoenflies: Die Entwickelung der Lehre von den Punktmannigfaltigkeiten. In: Guido Hauck, August Gutzmer (Hrsg.): Jahresbericht der Deutschen Mathematiker-Vereinigung. Bd. 8, Nr. 2, B. G. Teubner, Leipzig 1900, ISSN 0012-0456 (DigiZeitschriften/DigiZeitschriften).
  16.  Erich Kamke: Mengenlehre (= Sammlung Göschen. Bd. 999 [a]). 7. Auflage. Walter de Gruyter & Co., Berlin/New York 1971, ISBN 3-11-003911-7, § 10, S. 34–36.
  17.  Heinz Lüneburg: Kombinatorik. In: Elemente der Mathematik vom höheren Standpunkt aus. 1. Auflage. Bd. 6, Birkhäuser Verlag, Basel u. a. 1971, ISBN 3-7643-0548-7, S. 66.
  18.  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.