In der Mengenlehre, dem Cantor-Bernstein-Schroeder Lehrsatz, genannt nach Georg Cantor, stellen Felix Bernstein und Ernst Schröder, fest, dass, wenn dort Injective-Funktionen und zwischen den Sätzen A und B bestehen, dann dort besteht eine bijektive Funktion. In Bezug auf den cardinality der zwei Sätze bedeutet das dass wenn |A  |B und |B  |A, dann |A = |B; d. h. A und B sind equipollent. Das ist eine nützliche Eigenschaft in der Einrichtung von Grundzahlen.

Der Lehrsatz ist auch bekannt als der Lehrsatz von Schroeder-Bernstein, der Lehrsatz des Kantoren-Bernstein oder der Lehrsatz von Cantor-Schroeder-Bernstein.

Eine wichtige Eigenschaft dieses Lehrsatzes ist, dass er sich auf das Axiom der Wahl nicht verlässt. Jedoch sind seine verschiedenen Beweise nichtkonstruktiv, weil sie vom Gesetz der ausgeschlossenen Mitte, und deshalb zurückgewiesen durch intuitionists abhängen.

Beweis

Dieser Beweis wird Julius König zugeschrieben.

Nehmen Sie ohne Verlust der Allgemeinheit an, dass A und B zusammenhanglos sind. Für irgendwelchen in A oder b in B können wir eine einzigartige zweiseitige Folge von Elementen bilden, die abwechselnd in A und B durch die wiederholte Verwendung sind und Recht zu gehen und und verlassen (wo definiert) zu gehen.

:

Für jeden besonderen a kann diese Folge nach links oder nicht an einem Punkt enden, wo oder nicht definiert wird.

Nennen Sie solch eine Folge (und alle seine Elemente) einen A-Pfropfen, wenn sie an einem Element von A oder einem B-Pfropfen anhält, wenn sie an einem Element von B anhält. Nennen Sie es sonst doppelt unendlich, wenn alle Elemente verschieden oder zyklisch sind, wenn es sich wiederholt.

Durch die Tatsache, dass und Injective-Funktionen sind, ist jeder in A und b in B in genau einer solcher Folge zu innerhalb der Identität, (als ob ein Element in zwei Folgen, alle Elemente nach links vorkommt und nach rechts dasselbe in beiden, definitionsgemäß sein muss).

Durch die obengenannte Beobachtung bilden die Folgen eine Teilung vom ganzen die zusammenhanglose Vereinigung von A und B, folglich genügt es, um eine Bijektion zwischen den Elementen von A und B in jeder der Folgen getrennt zu erzeugen.

Für einen A-Pfropfen ist die Funktion eine Bijektion zwischen seinen Elementen in A und seinen Elementen in B.

Für einen B-Pfropfen ist die Funktion eine Bijektion zwischen seinen Elementen in B und seinen Elementen in A.

Für eine doppelt unendliche Folge oder eine zyklische Folge, entweder oder wird tun.

Vergegenwärtigung

Die Definition von h kann mit dem folgenden Diagramm vergegenwärtigt werden.

Gezeigt sind Teile der (zusammenhanglosen) Sätze A und B zusammen mit Teilen des mappings f und g. Wenn der Satz Ein  B, zusammen mit den zwei Karten, wird als ein geleiteter Graph interpretiert, dann hat dieser zweiteilige Graph mehrere verbundene Bestandteile.

Diese können in vier Typen geteilt werden: Pfade, die sich ungeheuer bis zu beide Richtungen, begrenzte Zyklen sogar der Länge, unendliche Pfade ausstrecken, die im Satz A und unendliche Pfade anfangen, die im Satz B anfangen (ist der Pfad, der das Element im Diagramm durchführt, in beiden Richtungen unendlich, so enthält das Diagramm einen Pfad jedes Typs). Im Allgemeinen ist es nicht möglich, in einer begrenzten Zahl von Schritten zu entscheiden, welchem Typ des Pfads ein gegebenes Element von A oder B gehört.

Der Satz C definiert enthält oben genau die Elemente, die ein Teil eines unendlichen Pfads sind, der in A anfängt. Die Karte h wird dann auf solche Art und Weise definiert, dass für jeden Pfad sie eine Bijektion nachgibt, die jedes Element im Pfad zu einem Element von B direkt vorher oder danach im Pfad kartografisch darstellt. Für den Pfad, der in beiden Richtungen, und für die begrenzten Zyklen unendlich ist, beschließen wir, jedes Element seinem Vorgänger im Pfad kartografisch darzustellen.

Abwechselnder Beweis

Unten folgt einem abwechselnden Beweis.

Idee vom Beweis: Definieren Sie f in bestimmten Punkten wieder, um es surjective zu machen. Definieren Sie es zuerst auf dem Image von g dafür wieder, um die umgekehrte Funktion von g zu sein. Jedoch könnte das injectivity zerstören, so korrigieren Sie dieses Problem wiederholend, durch das Bilden des Betrags von Punkten hat kleiner, bis zu einem möglichen Minimum, die Verschiebung des Problems "zur Unendlichkeit" und deshalb außer Sicht wiederdefiniert.

Genauer bedeutet das, f unverändert am Anfang auf C zu verlassen: = \GB. Jedoch dann hat jedes Element von fC zwei Vorimages, ein unter f und ein unter g. Verlassen Sie deshalb f unverändert auf der Vereinigung von C und C: = gfC. Jedoch dann hat jedes Element von fC zwei Vorimages, korrigieren Sie das, indem Sie f unverändert auf der Vereinigung von C, C, und C abreisen: = gfC und so weiter. Wenn er f unverändert auf der zählbaren Vereinigung C C und aller dieser C = abreist, behebt gfC das Problem, weil gfC eine Teilmenge von C ist und keine zusätzliche Vereinigung notwendig ist.

Im abwechselnden Beweis, kann als der Satz der n-ten Elemente von A-Pfropfen interpretiert werden (von 0 anfangend).

Tatsächlich, ist der Satz von Elementen, für die nicht definiert wird, der der Satz von Startelementen von A-Pfropfen ist, ist der Satz von Elementen, für die definiert wird, aber nicht, d. h. der Satz der zweiten Elemente von A-Pfropfen und so weiter ist.

Die Bijektion wird als auf und überall sonst definiert, was auf A-Pfropfen und überall sonst, im Einklang stehend der Beweis unten bedeutet.

Beweis: Definieren Sie

:

und

:

Dann für jeden ein  definieren A

:

h (a) =

\begin {Fälle }\

f (a) & \mbox {wenn} a\in C, \\

g^ {-1} (a) & \mbox {wenn} a\notin C.

\end {Fälle }\

</Mathematik>

Wenn nicht in C, dann zu sein, insbesondere nicht in C zu sein. Folglich ein  GB durch die Definition von C. Da g injective ist, wird sein Vorimage g (a) deshalb gut definiert.

Es muss, die folgenden Eigenschaften der Karte h zu überprüfen: Ein  B, um nachzuprüfen, dass es die gewünschte Bijektion ist:

• Surjectivity: Denken Sie jeden b  B. Wenn b  fC, dann gibt es einen  C mit b = f (a). Folglich b = h (a) durch die Definition von h. Wenn b nicht in fC ist, definieren Sie = g (b). Definitionsgemäß C, das ein Können nicht, in C sein. Da fC eine Teilmenge von fC ist, hieraus folgt dass b nicht in jedem fC ist, folglich = g ist (b) nicht in jedem C = gfC durch die rekursive Definition dieser Sätze. Deshalb, nicht in C zu sein. Dann b = g (a) = h (a) durch die Definition von h.
• Injectivity: Da f injective auf A ist, der C umfasst, und g injective auf dem GB ist, das die Ergänzung von C umfasst, genügt es, um zu zeigen, dass die Annahme f (c) = g (a) für c  C und ein  \C zu einem Widerspruch führt (das bedeutet das ursprüngliche Problem, der Mangel an injectivity, der in der Idee vom Beweis oben erwähnt ist, wird durch die kluge Definition von h gelöst). Seitdem c  C, dort besteht eine ganze Zahl n  0 solches dass c  C. Folglich g (f (c)) ist in C und deshalb in C auch. Jedoch, g (f (c)) = g (g (a)) = nicht in C — Widerspruch zu sein.

Bemerken Sie, dass die obengenannte Definition von h im Sinn nichtkonstruktiv ist, dass dort keine allgemeine Methode besteht, in einer begrenzten Zahl von Schritten, für irgendwelche gegebenen Sätze A und B und Einspritzungen f und g zu entscheiden, ob ein Element A in C nicht liegt. Für spezielle Sätze und Karten dieser könnte natürlich möglich sein.

Ursprünglicher Beweis

Ein früherer Beweis durch den Kantoren hat sich, tatsächlich, auf dem Axiom der Wahl durch das Schließen des Ergebnisses als eine Folgeerscheinung des gut bestellenden Lehrsatzes verlassen. Das über Shows gegebene Argument, dass das Ergebnis bewiesen werden kann, ohne das Axiom der Wahl zu verwenden.

Außerdem gibt es einen einfachen Beweis, der den festen Punkt-Lehrsatz von Tarski verwendet.

Geschichte

Da es häufig der Fall in der Mathematik ist, widerspiegelt der Name dieses Lehrsatzes seine Geschichte nicht aufrichtig.

Der traditionelle Name "Schröder-Bernstein" basiert auf zwei 1898 veröffentlichten unabhängig Beweisen.

Kantor wird häufig hinzugefügt, weil er zuerst den Lehrsatz 1895, festgesetzt

hat

während der Name von Schröder häufig weggelassen wird, weil sich sein Beweis erwiesen hat, rissig gemacht zu werden

während der Name des Mathematikers, der es zuerst bewiesen hat, mit dem Lehrsatz nicht verbunden wird.

In Wirklichkeit war die Geschichte mehr kompliziert:

• 1887 beweist Richard Dedekind den Lehrsatz, aber veröffentlicht es nicht.
• 1895 Georg Cantor setzt den Lehrsatz in seiner ersten Zeitung auf der Mengenlehre und den transfiniten Zahlen fest (als eine leichte Folge der geradlinigen Ordnung von Grundzahlen, die er dabei war, später zu beweisen).
• 1896 Ernst Schröder gibt einen Beweis (als eine Folgeerscheinung einer allgemeineren Behauptung) bekannt.
• 1897 Felix Bernstein, ein junger Student im Seminar des Kantoren, präsentiert seinen Beweis.
• 1897 Nach einem Besuch durch Bernstein, Dedekind beweist es unabhängig ein zweites Mal.
• 1898 der Beweis von Bernstein wird von Émile Borel in seinem Buch auf Funktionen veröffentlicht. (Mitgeteilt vom Kantoren auf dem 1897-Kongress in Zürich.)

Beide Beweise von Dedekind basieren auf seiner berühmten Biografie War sind und war sollen sterben Zahlen?

und leiten Sie es als eine Folgeerscheinung eines Vorschlags ab, der zur Behauptung C in der Zeitung des Kantoren gleichwertig ist:

:

Ein \subset B \subset C \quad\textrm {und }\\Viererkabel |A | = | C | \qquad\Rightarrow\qquad |A | = | B | = | C|

</Mathematik>

Kantor hat dieses Eigentum schon in 1882/83 während seiner Studien in der Mengenlehre und den transfiniten Zahlen beobachtet

und deshalb (implizit) sich auf das Axiom der Wahl verlassend.

Siehe auch

• Isomorphismus-Lehrsatz von Myhill
• Lehrsatz von Schröder-Bernstein für messbare Räume
• Lehrsätze von Schröder-Bernstein für Maschinenbediener-Algebra
• Eigentum von Schröder-Bernstein

Zeichen

Peter Schmitt hat die Geschichtsabteilung zu Citizendium beigetragen, den TakuyaMurata in diesen Artikel kopiert hat.

• Beweise aus DEM BUCH, p. 90. Internationale Standardbuchnummer 3-540-40460-0
• MathPath - Erklärung und Bemerkungen auf dem Beweis des Lehrsatzes des Kantoren-Bernstein
• Papiere auf der Geschichte des Lehrsatzes des Kantoren-Bernstein

Links

• Citizendium: Lehrsatz von Schröder-Bernstein und Eigentum von Schröder-Bernstein