Cantor-Bernstein-Schröder-Theorem

Cantor-Bernstein-Schröder-Theorem

In der Mengenlehre ist das Cantor-Bernstein-Schröder-Theorem (in der Literatur uneinheitlich auch als Satz von Cantor-Bernstein, als Äquivalenzsatz von Cantor-Bernstein oder auch als Satz von Schröder-Bernstein bezeichnet) eine Aussage über die Mächtigkeiten zweier Mengen. Es ist benannt nach den Mathematikern Georg Cantor, Felix Bernstein und Ernst Schröder und ist ein wichtiges Hilfsmittel beim Nachweis der Gleichmächtigkeit zweier Mengen.

Inhaltsverzeichnis

Satz

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.

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| \le |B| und |B| \le |A| folgt | A | = | B | .

Dabei gilt | A | = | B | genau dann, wenn A und B gleichmächtig sind, und |A| \le |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: A \to B und einer Injektion g: B \to A. Dann existiert eine Bijektion h: A\to B.

Der Äquivalenzsatz wurde 1883 von Georg Cantor formuliert, aber erst 1897 von Felix Bernstein in einem von Cantor geleiteten Seminar und etwa gleichzeitig unabhängig von Ernst Schröder bewiesen.[1][2]

Beweisidee

Wir geben hier eine Beweisidee (zuerst gegeben von Eilenberg?).

Wir definieren die Mengen

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

Für jedes x aus A setzen wir dann


  h(x) := \begin{cases}
    f(x) & \mbox{ falls } x\in C \\
    g^{-1}(x) & \mbox{ falls } x \not\in  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 hAB 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.

Veranschaulichung

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

Beispiel der Definition von h

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: beidseitig unendliche Pfade; endliche Zyklen; unendliche Pfade, die in A beginnen; 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 vorgegebenen Element gehende Pfad hat.

Die oben 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 wir legen uns auf „rückwärts“ fest).

Ein kurzer und leicht verständlicher Beweis findet sich auch in dem Göschenbändchen „Mengenlehre“ von Erich Kamke.

Siehe auch

Einzelnachweise

  1. Oliver Deiser: Einführung in die Mengenlehre. Berlin 2004, ISBN 3-540-20401-6
  2. Patrick Suppes: Axiomatic Set Theory. Dover Publications, 1972, ISBN 0-486-61630-4

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Cantor–Bernstein–Schroeder theorem — In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions f : A → B and g : B → A between the sets A and B , then there exists a bijective …   Wikipedia

  • Satz von Cantor-Bernstein — In der Mengenlehre ist das Cantor Bernstein Schröder Theorem (in der Literatur uneinheitlich auch als Satz von Cantor Bernstein, als Äquivalenzsatz von Cantor Bernstein oder auch als Satz von Schröder Bernstein bezeichnet) eine Aussage über die… …   Deutsch Wikipedia

  • Cantor — ist der Name von Bernard Gerald Cantor (1916–1996), US amerikanischer Unternehmer und Kunstmäzen, Firmengründer der Cantor Fitzgerald Eddie Cantor (1892–1964), US amerikanischer Entertainer Eric Cantor (* 1963), US amerikanischer Politiker Georg… …   Deutsch Wikipedia

  • Bernstein (Begriffsklärung) — Bernstein steht für: Bernstein, ein fossiles Harz Bernstein (Familienname), mehrere Personen mit dem Familienname Bernstein Bernstein (Band), eine Musikgruppe aus Limburg Betty Bernstein, Comicfigur und Maskottchen Bernstein AG,… …   Deutsch Wikipedia

  • Satz von Schröder-Bernstein — In der Mengenlehre ist das Cantor Bernstein Schröder Theorem (in der Literatur uneinheitlich auch als Satz von Cantor Bernstein, als Äquivalenzsatz von Cantor Bernstein oder auch als Satz von Schröder Bernstein bezeichnet) eine Aussage über die… …   Deutsch Wikipedia

  • Controversy over Cantor's theory — In mathematical logic, the theory of infinite sets was first developed by Georg Cantor. Although this work has found wide acceptance in the mathematics community, it has been criticized in several areas by mathematicians and philosophers. Cantor… …   Wikipedia

  • Ernst Schröder — For the actor, see Ernst Schröder (actor). Ernst Schröder (25 November, 1841 Mannheim, Germany – 16 June, 1902 Karlsruhe Germany) was a German mathematician mainly known for his work on algebraic logic. He is a major figure in the history of… …   Wikipedia

  • Georg Cantor — Infobox Scientist name = Georg Ferdinand Ludwig Cantor image width=225px caption = birth date = birth date|1845|3|3 birth place = Saint Petersburg, Russia death date = death date and age|1918|1|6|1845|3|3 death place = Halle, Germany residence =… …   Wikipedia

  • Knaster–Tarski theorem — In the mathematical areas of order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following:: Let L be a complete lattice and let f : L → L be an order preserving function. Then the set …   Wikipedia

  • Aleph null — In der Mathematik verwendet man den aus der Mengenlehre von Cantor stammenden Begriff der Mächtigkeit oder Kardinalität, um den für endliche Mengen verwendeten Begriff der „Anzahl der Elemente einer Menge“ auf unendliche Mengen zu verallgemeinern …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”