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 $⟨k_1,k_2⟩$.

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,\dots ,k_{n-1},k_n):=\pi ({\pi }^{(n-1)}(k_1,\dots ,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=⟨x,y⟩=\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\le z=t+y<t+(w+1)=\frac{(w+1{)}^2+(w+1)}{2}$

otteniamo che

$w\le \frac{\sqrt{8z+1}-1}{2}<w+1$

e quindi

$w=\lfloor \frac{\sqrt{8z+1}-1}{2}\rfloor$.

dove ⌊ ⌋ è la funzione di arrotondamento per difetto.

A questo punto per calcolare x e y da z:

a)     $w=\lfloor \frac{\sqrt{8z+1}-1}{2}\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

• Template:Cita web