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

Beweis

Es sei

$\phi :\mathbb{N}⟶M$

eine surjektive Abbildung. Wir definieren induktiv eine streng wachsende Abbildung

$\psi :\mathbb{N}⟶\mathbb{N}$

derart, dass $\phi \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 $\phi (k)$ nicht zu

$\{\phi (\psi (0)),\phi (\psi (1)),\dots ,\phi (\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

$\phi (\psi (n+1))\notin \{\phi (\psi (0)),\phi (\psi (1)),\dots ,\phi (\psi (n))\}$

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

Zur bewiesenen Aussage