Benutzer:Jürgen-Michael Glubrecht/Mächtigkeit

Aus Wikibooks
Zur Navigation springen Zur Suche springen

Wann sind zwei Mengen gleich groß?[Bearbeiten]

Äquivalenzsatz von Cantor-Bernstein-Schröder[Bearbeiten]

Satz (Äquivalenzsatz von Cantor-Bernstein-Schröder)

Ist schmächtiger als und schmächtiger als , dann sind und gleichmächtig:

Dieser Satz liefert ein weiteres Kriterium dafür, wie die Gleichmächtigkeit zweier Mengen bewiesen werden kann. Indem nämlich zwei Funktionen angegeben werden: und . Wir beweisen den Satz in mehreren Schrtten und zeigen zunächst die Äquivalenz mit dem Zwischenmengensatz.[1]

Satz (Zwischenmengensatz)

Liegt eine Menge zwischen einer Menge und einem injektiven Bild von , so sind und gleichmächtig.

Wir zeigen zunächst, dass der Äquivalenzsatz und der Zwischenmengensatz äquivalent sind:

Satz

Beweis

"": Es gelte der Äquivalenzsatz von Cantor-Bernstein-Schröder. Weiterhin sei und es gelte . Setze , dann bildet Injektiv in ab. Mit dem Satz von Cantor-Bernstein-Schröder folgt .

"": Gelte nun der Zwischenmengensatz, sowie injektiv und Injektiv. Dann ist auch die Verkettung injektiv und es gilt: . Mit dem Zwischenmengensatz folgt . ✔

Für den Beweis des Zwischenmengensatzes definieren wir noch eine spezielle Halbordnung:

Definition (Spezielle Halbordnung)

Es sei eine Funktion von in . Dann ist die Menge der Fixpunkte von . Für zwei beliebige Funktionen und ist die Relation wie folgt definiert:

besagt, dass mehr Fixpunkte als hat, aber ansonsten mit übereinstimmt.

Aufgabe: Zeige, dass eine Halbordnung ist.

Zu zeigen ist, ist reflexiv, transitiv und antisymmetrisch.

reflexiv: Es gilt und , also auch .

transitiv: Gelte und . Dann folgt und . Daraus ergibt sich . Für ist kein Fixpunkt von und auch kein Fixpunkt von . Also folgt und somit .

antisymmetrisch: Gelte und . Dann gilt und also . Daher stimmen beide Funktionen überein und es gilt: .

Die Beweisidee ist folgende: wir betrachten alle injektiven Funktionen , die zwar mehr Fixpunkte haben als die gegebene Funktion , aber ausserhalb dieser Fixpunkte mit übereinstimmen. Je mehr Fixpunkte diese Funktionen haben, desto weniger Funktionswerte stimmen mit überein. Unter diesen Funktionen gibt es (hoffentlich) welche, deren Bildbereich weitere Elemente von umfasst. Diese müssen Fixpunkte sein, denn ansonsten sind keine Abweichungen von erlaubt. Wenn es unter den betrachteten Funktionen eine gibt, in deren Bildbereich alle Elemente von liegen, haben wir eine Bijektion gefunden.

Beweis (Zwischenmengensatz, Äquivalenzsatz)

Sei nun und gelte . Sei weiterhin:

ist die Menge aller injektiven Funktionen , die mehr Fixpunkte als haben. Es gilt , denn ist nach Voraussetzung Injektiv, und es gilt . Wir definieren:

ist die Fixpunktmenge aller Funktionen aus . Es gilt , denn wenn gibt es ein dessen Fixpunkt ist und da gilt . Wir definieren schliesslich die gesuchte Bijektion:

, da injektiv ist, und es gilt nach Definition von :

()  

Da ja , wie oben gezeigt, gilt . Wir zeigen nun: . Seien und gelte . Sind , dann folgt . Sind folgt aus der Injektivität von . Bleibt als letzter Fall und . Dann gibt es mit und es folgt: mit der Injektivität von . Insgesamt haben wir gezeigt:

Als letzten Schritt beweisen wir, dass surjektiv auf ist und zeigen dazu . Wir definieren die Funktion wie folgt:

ist injektiv wegen der Injektivität von . Weiterhin gilt , denn hat allenfalls mehr Fixpunkte als und für gilt . Mit folgt daraus wegen wegen der Transitivität von . Insgesamt haben wir gezeigt: . Daraus folgt mit () und mit der Antisymmetrie von ergibt sich . Nach Definition von gilt und mit der Gleichheit folgt . Das ist aber nur möglich, wenn gilt, also: . Also:

, also:

Damit ist der Beweis des Zwischenmengensatzes und des Äquivalenzsatzes von Cantor-Bernstein-Schröder beendet. ✔

Beispiel[Bearbeiten]

Wir verwenden die Bezeichnungen wie im Beweis des Zwischenmengensatzes.

Beispiel (Zwischenmengensatz)

Es sei die Menge der natürlichen Zahlen, die Menge der natürlichen Zahlen größer oder gleich und die Funktion, die jede Zahl um 2 erhöht. ist injektiv und es gilt:

ist eine echte Obermenge von , denn die ist kein Bild unter . Wir definieren folgendermassen:

ist injektiv und alle ungeraden Zahlen sind Fixpunkte. Auf den geraden Zahlen stimmt mit überein. Da keine Fixpunkte hat, gilt also . somit gilt . Da ist, ist eine Bijektion auf .

Mehr Fixpunkte als kann aber keine Funktion aus haben, denn die geraden Zahlen können keine Fixpunkte sein. Das folgt durch Induktion: ist kein Fixpunkt, denn , tritt also nicht als Bild auf. Sei nun gerade und nach Induktionsvoraussetzung kein Fixpunkt. Dann ist das Bild von aber . Also kann auch kein Fixpunkt sein. Daher ist in diesem Beispiel tatsächlich die Funktion, deren Existenz im Beweis gezeigt wird.

Cantor-Bernstein-Schröder.png

Vertiefung zum Thema Mächtigkeit[Bearbeiten]

Wir haben definiert, dass zwei Mengen und genau dann gleichmächtig sind, wenn es zwischen ihnen eine bijektive Abbildung gibt: . Die Relation ist eine Äquivalenzrelation auf der Klasse aller Mengen.

Hinweis

Die Klasse aller Mengen ist zu groß für eine Menge, sie ist eine echte Klasse, vgl. "Axiomatische Mengenlehre".

Frage: Zeige dass eine Äquivalenzrelation ist.

Um zu zeigen, dass eine Relation eine Äquivalenzrelation ist, müssen wir zeigen, dass sie reflexiv, symmetrisch und transitiv ist. Im folgenden seien beliebige Mengen.

Reflexiv: Die Identitätsabbildung ist eine Bijektion der Menge auf sich. Also gilt .

Symmetrisch: Gelte . Dann gibt es eine bijektive Abbildung . Daher ist die Umkehrfunktion ebenfalls bijektiv und bildet die Menge auf die Menge ab: . Also gilt .

Transitiv: Gelte und . Dann gibt es bijektive Abbildungen und . Die Komposition dieser beiden Abbildungen ist als Komposition zweier bijektiven Abbildungen ebenfalls bijektiv und bildet auf ab: . Also gilt . ✔

Da die Relation eine Äquivalenzrelation ist, zerfällt die Klasse aller Mengen unter dieser Relation in Äquivalenzklassen gleichmächtiger Mengen. Da diese Äquivalenzklassen ebenfalls echte Klassen sind, geht man zu einem Repräsentantensystem über, den sogenannten Kardinalzahlen:

Definition (Kardinalzahlen)

Die Kardinalzahlen sind Mengen und bilden ein Repräsentantensystem für die Äquivalenzklassen gleichmächtiger Mengen.

bezeichnet die Kardinalzahl, die zu der Äquivalenzklasse von gehört.

Anmerkung: Die Schreibweise sollte nicht mit den mit den Betragsstrichen oder der Determinantenfunktion aus der Linearen Algebra verwechselt werden.

Definition (Ordnung der Kardinalzahlen)

Die folgende Definition ist repräsentantenunabhängig:

Es ist leicht zu zeigen, dass die Relation reflexiv und transitiv ist. Die Antisymmetrie folgt mit dem Äquivalenzsatz von Cantor-Bernstein-Schröder. ist also eine Halbordnung. Mit dem Auswahlaxiom kann man zeigen, dass eine Totalordnung ist:

Satz

ist eine Totalordnung auf den Kardinalzahlen.

Kardinalzahlen lassen sich also der Größe nach vergleichen. Sie sind verallgemeinerte natürliche Zahlen, die die Mächtigkeit einer Menge beschreiben. Im Fall einer endlichen Menge ist ihre Kardinalzahl nichts anderes als die Anzahl ihrer Elemente. Die endlichen Kardinalzahlen sind also die natürlichen Zahlen . Beispielsweise ist und .

Die unendlichen Kardinalzahlen werden mit bezeichnet (der Buchstabe Aleph ist der erste Buchstabe des hebräischen Alphabets).

ist die kleinste Mächtigkeit, die eine unendliche Menge haben kann: man kann zeigen, dass jede unendliche Menge eine Mächtigkeit größer oder gleich besitzt. Außerdem hat Cantor im Satz von Cantor gezeigt, dass jede Potenzmenge mächtiger als ihre zugrunde liegende Menge ist. Man kann zeigen, dass ist. Es stellt sich nun die Frage, ob es eine Menge gibt, die mächtiger als , aber weniger mächtig als ist. Cantor vermutete, dass dies nicht der Fall ist, konnte seine Vermutung aber nicht beweisen. Diese Vermutung wird Kontinuumshypothese genannt. Es stellte sich jedoch heraus, dass diese Hypothese in der Mengenlehre mit den Axiomen von Zermelo-Fraenkel einschliesslich Auswahlaxiom weder beweisbar noch widerlegbar ist.

  1. Wolfgang Rautenberg, Uber den Cantor-Bernsteinschen Aquivalenzsatz, Berlin 2007,[PDF]