Il fatto che si possa costruire una funzione iniettiva $f : NN^2 \to NN$ è noto.
Una costruzione classica consiste nello scrivere gli elementi di $NN^2$ in forma tabellare in modo che in corrispondenza della riga $n$ e della colonna $m$ della tabella si trovi l'elemento $(n,m)$, quindi si considerano le diagonali della matrice a partire da quella che contiene solo l'elemento $(0,0)$, passando poi a quella che contiene gli elementi $(1,0)$ e $(0,1)$ e così via. Si pone $f(0,0)=0$, $f(1,0)=1$, $f(0,1)=2$ e così via, costruendo così una funzione iniettiva $f : NN^2 \to NN$.
Questa rappresenta un po l'idea della costruzione della funzione $f$, ma si può arrivare ad una espressione esplicita per $f$?