Endliche Mengen/Anzahl/Wohldefiniert/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen



Lemma  

Es sei eine natürliche Zahl mit dem Vorgänger , es sei also . Es sei ein fixiertes Element.

Dann gibt es eine bijektive Abbildung zwischen und .

Beweis  

Wir definieren eine Abbildung

durch

Dies ist eine wohldefinierte Abbildung, da die Bilder echt unterhalb von oder echt oberhalb von liegen, niemals aber gleich sind, und da maximal der Nachfolger von , also erreicht wird.

Die Abbildung ist injektiv: Wenn und beide unterhalb von liegen, so werden beide Elemente auf sich selbst abgebildet. Wenn beide oberhalb von liegen, so werden beide auf ihren Nachfolger abgebildet, und das Nachfolgernehmen ist injektiv (dies ist die Eigenschaft, dass der Vorgänger eindeutig bestimmt ist). Wenn unterhalb von und oberhalb von (oder umgekehrt) liegt, so ist erst recht oberhalb von und somit von verschieden.

Die Abbildung ist auch surjektiv. Die Zahlen echt unterhalb von werden durch sich selbst erreicht und die Zahlen echt oberhalb von (und unterhalb von einschließlich ) kann man als

mit oberhalb von (einschließlich ) und echt unterhalb von , also maximal gleich schreiben. Insgesamt ist also eine Bijektion.




Satz  

Wenn eine Menge ist und wenn

und

bijektive Abbildungen sind,

so ist

Die Anzahl einer endlichen Menge ist also wohldefiniert.

Beweis  

Seien die bijektiven Abbildungen

und

gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Fakt  (3) wieder bijektiv ist, ist auch

bijektiv. Wir müssen also nur die endlichen Standardmengen untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung

vorliegt, dass dann

ist. Dies zeigen wir durch Induktion nach . Wenn ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch . Seien nun nicht , so dass sie also jeweils einen Vorgänger haben. Es sei der Vorgänger von und der Vorgänger von . Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen

Dann gibt es nach der Herausnahme von bzw. eine bijektive Abbildung

Nach Fakt gibt es eine bijektive Abbildung zwischen und . Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen und . Nach Induktionsvoraussetzung ist , also auch