Beweisarchiv: Mengenlehre: Mächtigkeiten (Kardinalzahlen): Kardinalität und Bijektionen

Aus Wikibooks
Wechseln zu: Navigation, Suche

Beweisarchiv: Mengenlehre

Injektivität Surjektivität Bijektivität: Faktoren - Komposition - Linksinverse - Linkskürzbarkeit - Rechtsinverse - Rechtskürzbarkeit
Verkettungen: Assoziativgesetz der Hintereinanderausführung
Mächtigkeiten (Kardinalzahlen): lineare Ordnung - Kardinalität und Bijektionen - Potenzmenge
Deskriptive Mengenlehre: Satz von Young
Rechenregeln für Mengenoperationen: Assoziativgesetze - Distributivgesetze - Differenzgesetze - Grundeigenschaften der Inklusion - De Morgansche Regeln für Mengen
Ordinalzahlen: Ordinalzahlen enthalten sich nicht selbst als Element - Elemente von Ordinalzahlen sind Ordinalzahlen - Durchschnitte von Ordinalzahlen sind Ordinalzahlen - Wohlordnung der Klasse aller Ordinalzahlen - Ordinalzahlen bilden eine echte Klasse - Der Nachfolger einer Ordinalzahl ist Ordinalzahl - Vereinigungen von Ordinalzahlen sind Ordinalzahlen - Limes- und Nachfolgerzahlen - Äquivalenz verschiedener Definitionen
Sätze die in ZF Äquivalent zum Auswahlaxiom sind: Alternative Darstellung des Auswahlaxioms - Wohlordnungssatz - Lemma von Zorn


Sind Mengen, so schreiben wir , falls es eine injektive Abbildung gibt. Wir schreiben bzw. sagen, dass und gleichmächtig sind, falls und .

Inhaltsverzeichnis

Satz[Bearbeiten]

Zwei Mengen sind genau dann gleichmächtig, wenn es eine Bijektion gibt.

Beweis[Bearbeiten]

Falls es eine Bijektion gibt, ist klar, dass gilt, da sowohl die Abbildung als auch deren Umkehrung injektiv ist.

Es gelte jetzt , und zwar seien und injektiv. Wir definieren jetzt eine Abbildung wie folgt: Sei und dann rekursiv . Sei .

  • Ist , so setze .
  • Ist , so folgt insbesondere , wir können somit setzen.

Diese Abbildung ist injektiv: Es gelte für zwei Elemente .

  • Ist und , so ergibt sich mit ein Widerspruch.
  • Der Fall und ist ebenso ausgeschlossen.
  • Ist und , so folgt , also .
  • Ist weder und , so folgt .

Die Abbildung ist aber auch surjektiv: Sei beliebig.

  • Ist für ein , so folgt nach Definition von , dass sogar gilt. Folglich ist für ein und .
  • Ansonsten gilt .

Folglich ist eine Bijektion.

Satz[Bearbeiten]

Sei so gilt, dass

Beweis[Bearbeiten]

Für den Fall, dass ist die Aussage trivial, also betrachten wir nur den Fall, dass .

Da . Bilde nun eine Abbildung

Da surjektiv ist folgt die Behauptung.