Satz von Schröder-Bernstein - Schröder–Bernstein theorem

In der Mengenlehre besagt der Schröder-Bernstein-Satz , dass, wenn zwischen den Mengen A und B injektive Funktionen f  : AB und g  : BA existieren, eine bijektive Funktion h  : AB existiert .

In Bezug auf die Kardinalität der beiden Mengen impliziert dies klassisch, dass wenn | A | | B | und | B | | A | , dann | A | = | B | ; das heißt, A und B sind äquipotent . Dies ist eine nützliche Funktion bei der Bestellung von Kardinalzahlen .

Der Satz ist nach Felix Bernstein und Ernst Schröder benannt . Es ist auch als Cantor-Bernstein-Theorem oder Cantor-Schröder-Bernstein bekannt , nach Georg Cantor, der es zuerst ohne Beweis veröffentlichte.

Nachweisen

Königs Definition einer Bijektion h : A  →  B aus gegebenen Beispielinjektionen f : A  →  B und g : B  →  A . Ein Element in A und B wird mit einer Zahl bzw. einem Buchstaben bezeichnet. Die Folge 3 → e → 6 → ... ist ein A- Stopper, was zu den Definitionen h (3) =  f (3) =  e , h (6) =  f (6), ... führt. Die Folge d  → 5 →  f  → ... ist ein B- Stopper, der zu h (5) =  g −1 (5) =  d , ... führt. Die Folge ... →  a  → 1 →  c  → 4 → .. . ist doppelt unendlich und führt zu h (1) =  g −1 (1) =  a , h (4) =  g −1 (4) =  c , .... Die Folge b  → 2 →  b ist zyklisch und führt zu h (2) =  g −1 (2) =  b .

Der folgende Beweis wird Julius König zugeschrieben .

Es sei angenommen , ohne Beschränkung der Allgemeinheit , dass A und B sind disjunkt . Für jedes a in A oder b in B können wir eine einzigartige zweiseitige Folge von Elementen bilden, die abwechselnd in A und B sind , indem wir wiederholt anwenden und von A nach B und und von B nach A gehen (wo definiert; die Inversen und werden in dieser Phase des Beweises als Teilfunktionen verstanden .)

Für ein bestimmtes a kann diese Sequenz links oder nicht an einem Punkt enden, an dem oder nicht definiert ist.

Durch die Tatsache, dass und injektive Funktionen sind, ist jedes a in A und b in B in genau einer solchen Sequenz bis auf Identität: Wenn ein Element in zwei Sequenzen vorkommt, müssen alle Elemente links und rechts in beiden gleich sein , durch die Definition der Sequenzen. Daher bilden die Folgen eine Partition der (disjunkten) Vereinigung von A und B . Daher reicht es aus, eine Bijektion zwischen den Elementen von A und B in jeder der Folgen getrennt zu erzeugen , wie folgt:

Nennen Sie eine Sequenz einen A-Stopper, wenn sie an einem Element von A stoppt , oder einen B-Stopper, wenn sie an einem Element von B stoppt . Nennen Sie es andernfalls doppelt unendlich, wenn alle Elemente verschieden sind, oder zyklisch, wenn es sich wiederholt. Siehe das Bild für Beispiele.

  • Für einen A-Stopper ist die Funktion eine Bijektion zwischen seinen Elementen in A und seinen Elementen in B .
  • Für einen B-Stopper ist die Funktion eine Bijektion zwischen seinen Elementen in B und seinen Elementen in A .
  • Für eine doppelt unendliche Sequenz oder eine zyklische Sequenz ist entweder oder ausreichend ( wird im Bild verwendet).

Geschichte

Der traditionelle Name "Schröder-Bernstein" basiert auf zwei unabhängig voneinander 1898 veröffentlichten Beweisen. Cantor wird oft hinzugefügt, weil er den Satz erstmals 1887 formulierte, während Schröders Name oft weggelassen wird, weil sich sein Beweis als fehlerhaft herausstellte, während der Name von Richard Dedekind , der es zuerst bewiesen hat, ist mit dem Satz nicht verbunden. Cantor hatte nach Bernstein den Namen Äquivalenzsatz vorgeschlagen.

Cantors erste Aussage des Theorems (1887)
  • 1887 Cantor veröffentlicht den Satz, jedoch ohne Beweis.
  • 1887 Am 11. Juli beweist Dedekind den Satz (ohne sich auf das Auswahlaxiom zu verlassen ), veröffentlicht aber weder seinen Beweis noch teilt er Cantor davon mit. Ernst Zermelo entdeckte Dedekinds Beweis und veröffentlichte 1908 seinen eigenen Beweis basierend auf der Kettentheorie aus Dedekinds Aufsatz Was sind und was sollen die Zahlen?
  • 1895 Cantor stellt den Satz in seiner ersten Arbeit über Mengenlehre und transfinite Zahlen fest. Er erhält sie als einfache Folge der linearen Ordnung der Kardinalzahlen. Letzteren Satz, der 1915 als äquivalent zum Auswahlaxiom von Friedrich Moritz Hartogs nachgewiesen wurde , konnte er jedoch nicht beweisen .
  • 1896 verkündet Schröder einen Beweis (als Folgerung eines Satzes von Jevons ).
  • 1897 Bernstein , ein 19-jähriger Student im Cantor's Seminar, präsentiert seinen Beweis.
  • 1897 Fast gleichzeitig, aber unabhängig findet Schröder einen Beweis.
  • 1897 Nach einem Besuch von Bernstein beweist Dedekind den Satz unabhängig ein zweites Mal.
  • 1898 Bernsteins Beweis (der sich nicht auf das Auswahlaxiom stützt) wird von Émile Borel in seinem Buch über Funktionen veröffentlicht. (Mitteilt von Cantor auf dem Internationalen Mathematikerkongress 1897 in Zürich.) Im selben Jahr erscheint der Beweis auch in Bernsteins Dissertation.
  • 1898 Schröder veröffentlicht seinen Beweis, der jedoch 1902 (kurz vor Schröders Tod) von Alwin Reinhold Korselt als fehlerhaft nachgewiesen wird (von Schröder bestätigt), aber Korselts Aufsatz wird erst 1911 veröffentlicht.

Beide Beweise von Dedekind basieren auf seinen berühmten Memoiren von 1888 Was sind und was sollen die Zahlen? und leiten sie als Korollar einer Aussage ab, die der Aussage C in Cantors Arbeit entspricht, die A  ⊆  B  ⊆  C und | . lautet A | = | C | impliziert | A | = | B | = | C |. Cantor beobachtete diese Eigenschaft bereits 1882/83 während seines Studiums der Mengenlehre und der transfiniten Zahlen und verließ sich daher (implizit) auf das Auswahlaxiom .

Voraussetzungen

Der Beweis von Cantor aus dem Jahr 1895 stützte sich praktisch auf das Auswahlaxiom, indem er das Ergebnis als Folge des Wohlordnungssatzes herleitete . Der obige Beweis von König zeigt jedoch, dass das Ergebnis auch ohne Verwendung des Auswahlaxioms bewiesen werden kann.

Auf der anderen Seite verwendet Königs Beweis das Prinzip der ausgeschlossenen Mitte , um die Analyse in Fällen durchzuführen, so dass dieser Beweis in der konstruktiven Mengenlehre nicht funktioniert . Mehr noch, aus der konstruktiven Mengenlehre allein (dh Verzicht auf das Prinzip der ausgeschlossenen Mitte) kann überhaupt kein Beweis geführt werden, da das Schröder-Bernstein-Theorem das Prinzip der ausgeschlossenen Mitte impliziert. Daher akzeptieren Intuitionisten das Theorem nicht.

Es gibt auch einen Beweis, der den Fixpunktsatz von Tarski verwendet .

Siehe auch

Anmerkungen

Verweise

Externe Links