# Funzione coppia

In matematica si definisce funzione coppia una funzione che associa ad ogni coppia ordinata di numeri naturali un numero naturale con corrispondenza uno a uno; è quindi un'applicazione biiettiva $\pi$ fra l'insieme prodotto $\mathbb {N} \times \mathbb {N}$ e l'insieme dei numeri naturali $\mathbb {N}$:
    $\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .$

## Utilizzo per il calcolo delle cardinalità

L'esistenza di tali funzioni dimostra che la cardinalità dei due insiemi $\mathbb {N}$ e $\mathbb {N} \times \mathbb {N}$ è la stessa.
Utilizzando opportune funzioni da comporre alla funzione coppia, è possibile dimostrare che anche la cardinalità degli insiemi dei numeri interi $\mathbb {Z}$ e dei numeri razionali $\mathbb {Q}$ è uguale alla cardinalità di $\mathbb {N}$.
Inoltre componendo più volte una funzione coppia, è possibile costruire delle applicazioni biunivoche fra qualunque potenza dei naturali $\mathbb {N} ^{k}$ e $\mathbb {N}$. Questa tecnica è molto usata anche nella teoria della calcolabilità.

## Funzione coppia di Cantor

La funzione coppia di Cantor è una funzione coppia così definita:
    $\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}.$
L'immagine $\pi (k_{1},k_{2})$ della funzione coppia si indica solitamente con $\langle k_{1},k_{2}\rangle$.
Questa definizione può essere generalizzata in modo da ottenere la funzione tupla di Cantor
    $\pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N}$
in questo modo:
    $\pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})$
Nel calcolo dell'enumerazione di una funzione calcolabile (in informatica teorica) si usa una versione leggermente modificata della funzione coppia di Cantor:
    $\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}+1.$
ottenuta enumerando a partire da $0$ al posti di $1$

## Inversione della funzione coppia di Cantor

Supponiamo sia dato z definito come segue
    $z=\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+y$
e si vogliano trovare x e y. Definiamo alcune variabili intermedie:
    $w=x+y$
    $t={\frac {w(w+1)}{2}}={\frac {w^{2}+w}{2}}$
    $z=t+y$
dove t è il numero triangolare di w. Se risolviamo l'equazione di secondo grado
    $w^{2}+w-2t=0$
per w in funzione di t, otteniamo
    $w={\frac {{\sqrt {8t+1}}-1}{2}}$
che è una funzione strettamente crescente e sempre definita per valori di t reali non negativi. Da
    $t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}}$
otteniamo che
    $w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1$
e quindi
    $w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor$.
    dove ⌊ ⌋ è la funzione di arrotondamento per difetto.
A questo punto per calcolare x e y da z:
    a)  $w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor$
    b)  $t={\frac {w^{2}+w}{2}}={\frac {w(w+1)}{2}}$
    $y=z-t$
    $x=w-y$.

### Esempio

Per calcolare π(x, y) = 1432 = z
Calcoliamo w con la formula a)
    8 × 1432 = 11456,
    11456 + 1 = 11457,
    √11457 = 107.037,
    107.037 − 1 = 106.037,
    106.037 ÷ 2 = 53.019,
    ⌊53.019⌋ = 53,
quindi w = 53;
Calcoliamo la t con la formula b)
    53 × (53 + 1) = 2862,
    2862 ÷ 2 = 1431,
quindi t = 1431;
Ed infine
    $y=z-t$ = 1432 − 1431 = 1;
    $x=w-y$ = 53 − 1 = 52;