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

Aus Wikibooks

Beweisarchiv: Mengenlehre

Charakteristikum unendlicher Mengen
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 · Bild und Urbild
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 .

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.