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