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;

Bibliografia

• Ausiello, D'Amore, Gambosi, Linguaggi Modelli Complessità

Collegamenti esterni

• Le funzioni coppia nel sito Mathworld, su mathworld.wolfram.com.