Endliche Mengen/Anzahl/Wohldefiniert/Fakt/Beweis2

Beweis

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. 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\,.$

Seien nun ${}n,k$ nicht ${}0$, so dass 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 \}$. Mit dieser Überlegung kann man die beiden Zahlen ${}n$ und ${}k$ durch ihre jeweiligen Vorgänger ${}m$ und ${}\ell$ ersetzen und damit um eins kleiner machen (die Existenz der bijektiven Abbildung bleibt erhalten). Diese Überlegung kann man so lange wiederholen, bis eine der reduzierten Zahlen gleich ${}0$ ist. Dann muss aber nach der Eingangsüberlegung die andere reduzierte Zahl ebenfalls gleich ${}0$ sein. Dann stimmen auch die sukzessiven Nachfolger überein und insbesondere ist ${}n=k$.

Zur bewiesenen Aussage