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

Beweis

Wir definieren eine Abbildung

$\varphi \colon \{1,\ldots ,\ell \}\longrightarrow \{1,\ldots ,k\}\setminus \{z\}$

durch

$\varphi (x)={\begin{cases}x\,,{\text{ falls }}x{\text{ in der Durchzählung von }}1{\text{ bis }}k{\text{ vor }}z{\text{ kommt}}\,,\\x^{\prime }\,,{\text{ falls }}x{\text{ gleich }}z{\text{ ist oder in der Durchzählung nach }}z{\text{ kommt}}\,.\end{cases}}\,$

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 ${}\ell$, 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^{\prime }$ 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^{\prime }\,$

mit ${}v$ oberhalb von ${}z$ (einschließlich ${}z$) und echt unterhalb von ${}k$, also maximal gleich ${}\ell$ schreiben. Insgesamt ist ${}\varphi$ also eine Bijektion.

Zur bewiesenen Aussage