# Endliche Mengen/Anzahl/Wohldefiniert/Textabschnitt
## Lemma

Es sei $k\neq 0$ eine natürliche Zahl mit dem Vorgänger $\ell$, es sei also $k=\ell ^{\prime }$. Es sei $z\in \{1,\ldots ,k\}$ ein fixiertes Element.
Dann gibt es eine bijektive Abbildung zwischen $\{1,\ldots ,\ell \}$ und $\{1,\ldots ,k\}\setminus \{z\}$.

### 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.
$\Box$

## Satz

Wenn $M$ eine Menge ist und wenn
    $\varphi \colon {\{1,\ldots ,n\}}\longrightarrow M$
und
    $\psi \colon \{1,\ldots ,k\}\longrightarrow M$
bijektive Abbildungen sind,
so ist
Die Anzahl einer endlichen Menge ist also wohldefiniert.

### Beweis

Es seien die bijektiven Abbildungen
    $\varphi \colon {\{1,\ldots ,n\}}\longrightarrow M$
und
    $\psi \colon \{1,\ldots ,k\}\longrightarrow M$
gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Fakt (3) wieder bijektiv ist, ist auch
    $\psi ^{-1}\circ \varphi \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}$
bijektiv. Wir müssen also nur die endlichen Standardmengen ${\{1,\ldots ,n\}}$ untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung
    $\theta \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}$
vorliegt, dass dann
    $n=k\,$
ist. Dies zeigen wir durch Induktion nach $n$. Wenn $n=0$ ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch $k=0$. Es seien nun $n,k$ nicht $0$, sodass sie also jeweils einen Vorgänger haben. Es sei $m$ der Vorgänger von $n$ und $\ell$ der Vorgänger von $k$. Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen
    $z=\theta (n)\in \{1,\ldots ,k\}\,.$
Dann gibt es nach der Herausnahme von $n$ bzw. $z$ eine bijektive Abbildung
    $\{1,\ldots ,m\}={\{1,\ldots ,n\}}\setminus \{n\}\longrightarrow \{1,\ldots ,k\}\setminus \{z\}.$
Nach Fakt gibt es eine bijektive Abbildung zwischen $\{1,\ldots ,\ell \}$ und $\{1,\ldots ,k\}\setminus \{z\}$. Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen $\{1,\ldots ,m\}$ und $\{1,\ldots ,\ell \}$. Nach Induktionsvoraussetzung ist $m=\ell$, also auch
    $n=m'=\ell '=k\,.$
$\Box$