Funzione coppia
# 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;
