Zum Inhalt springen

Endliche Menge/1 bis k/Eins heraus/Fakt/Beweis

Beweis

Wir definieren eine Abbildung

φ:{1,…,ℓ}⟶{1,…,k}∖{z}

durch

φ(x)={x, falls x in der Durchzählung von 1 bis k vor z kommt,x′, falls x gleich z ist oder in der Durchzählung nach z kommt.

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

Die Abbildung ist injektiv: Wenn x und y beide unterhalb von z liegen, so werden beide Elemente auf sich selbst abgebildet. Wenn beide oberhalb von z 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 x unterhalb von z und y oberhalb von z (oder umgekehrt) liegt, so ist erst recht y′ oberhalb von z und somit von x verschieden.

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

u=v′

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