Es sei

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

eine surjektive Abbildung. Wir definieren induktiv eine streng wachsende Abbildung

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

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

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

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

${\displaystyle {}n\in \mathbb {N} }$

${\displaystyle \varphi (\psi (n+1))\not \in \{\varphi (\psi (0)),\varphi (\psi (1)),\ldots ,\varphi (\psi (n))\}}$

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