Abzählbar unendlich/Bijektion zu N/Fakt/Beweis

Beweis

Es sei

$\varphi \colon \mathbb {N} \longrightarrow M$

eine surjektive Abbildung. Wir definieren induktiv eine streng wachsende Abbildung

$\psi \colon \mathbb {N} \longrightarrow \mathbb {N}$

derart, dass ${}\varphi \circ \psi$ bijektiv ist. Wir setzen ${}\psi (0)=0$ und konstruieren ${}\psi$ induktiv über die Eigenschaft, dass ${}\psi (n+1)$ die kleinste natürliche Zahl ${}k$ ist, für die ${}\varphi (k)$ nicht zu

$\{\varphi (\psi (0)),\varphi (\psi (1)),\ldots ,\varphi (\psi (n))\}$

gehört. Eine solche Zahl gibt es immer, da andernfalls ${}M$ endlich wäre; also gibt es auch eine kleinste solche Zahl. Nach Konstruktion ist ${}\psi (n+1)>\psi (n)$, d.h. ${}\psi$ ist streng wachsend. Da jedes ${}n\in \mathbb {N}$ die Eigenschaft

${}\varphi (\psi (n+1))\notin \{\varphi (\psi (0)),\varphi (\psi (1)),\ldots ,\varphi (\psi (n))\}\,$

erfüllt, ist die Gesamtabbildung ${}\varphi \circ \psi$ injektiv.
Zum Nachweis der Surjektivität sei ${}m\in M$. Wegen der Surjektivität von ${}\varphi$ ist die Faser ${}\varphi ^{-1}(m)$ nicht leer und daher gibt es auch ein kleinstes Element ${}a\in \mathbb {N}$ mit ${}\varphi (a)=m$. Da ${}\psi$ streng wachsend ist, gibt es nur endlich viele Zahlen ${}i\in \{0,1,\ldots ,n\}$ mit ${}\psi (i)<a$. Daher ist ${}\psi (n+1)=a$ und ${}\varphi (\psi (n+1))=\varphi (a)=m$.

Zur bewiesenen Aussage