Endliche Mengen/Anzahl/Wohldefiniert/Fakt/Beweis/Aufgabe/Lösung

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

Zur gelösten Aufgabe