Matematicamente.it

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$?

$(a,b)\rarr2^a3^b$?

La funzione che hai proposto dovrebbe essere iniettiva, infatti se $f(a,b)=f(c,d)$ allora $2^a3^b=2^c3^d$, quindi $2^{a-c}=3^{d-b}$, dunque $a-c=0$ e $d-b=0$, cioè $(a,b)=(c,d)$.

Tuttavia, non corrisponde alla costruzione "per diagonali" che avevo descritto. Mi chiedevo se fosse possibile trovare un'espressione esplicita della funzione che si costruisce "per diagonali".

Bastava googlare https://en.wikipedia.org/wiki/Pairing_f ... g_function

thedarkhero ha scritto:Tuttavia, non corrisponde alla costruzione "per diagonali" che avevo descritto. Mi chiedevo se fosse possibile trovare un'espressione esplicita della funzione che si costruisce "per diagonali".

Non avevo letto/capito bene. Pensavo volessi una funzione iniettiva qualsiasi.

Si puo' fare, ovviamente: bisogna trovare una formuletta che converta $(r,c)$ in $i$, e per farlo devi costruirti una tabellina iniziale

r,c=>i
0,0=>0
1,0=>1
0,1=>2
2,0=>3
1,1=>4
0,2=>5
...
(nota che $r+c$ e' una costante sulla diagonale).
a seconda se vai a zig/zag, oppure usi qualche altro 'pattern'.

Ma non e' l'unico modo!
C'e' tutta la teoria delle curve che possono ricoprire il piano e poiche' non hanno intersezioni, sono invertibili (curve di hilbert e di peano, cerca su wikipedia).

Nota che che $r+c+1$ e' il numero di celle che compongono la diagonale da $(0,r+c)$ a $(r+c,0)$.
Quindi, banalmente, devi trovare la formuletta che dato $(r,c)$, salta abbastanza celle e poi selezioni la cella del vettore che ti serve. Ho fatto il 95% del lavoro, ti manca il rimanente 5%