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

${}n=k\,.$

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$, 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 \}$. Nach Induktionsvoraussetzung ist ${}m=\ell$, also auch

${}n=m'=\ell '=k\,.$

$\Box$