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 ${\displaystyle \pi }$ fra l'insieme prodotto ${\displaystyle \mathbb {N} \times \mathbb {N} }$ e l'insieme dei numeri naturali ${\displaystyle \mathbb {N} }$:

${\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .}$

L'esistenza di tali funzioni dimostra che la cardinalità dei due insiemi ${\displaystyle \mathbb {N} }$ e ${\displaystyle \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 ${\displaystyle \mathbb {Z} }$ e dei numeri razionali ${\displaystyle \mathbb {Q} }$ è uguale alla cardinalità di ${\displaystyle \mathbb {N} }$.

Inoltre componendo più volte una funzione coppia, è possibile costruire delle applicazioni biunivoche fra qualunque potenza dei naturali ${\displaystyle \mathbb {N} ^{k}}$ e ${\displaystyle \mathbb {N} }$. Questa tecnica è molto usata anche nella teoria della calcolabilità.

La funzione coppia di Cantor è una funzione coppia così definita:

${\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}.}$

L'immagine ${\displaystyle \pi (k_{1},k_{2})}$ della funzione coppia si indica solitamente con ${\displaystyle \langle k_{1},k_{2}\rangle }$.

Questa definizione può essere generalizzata in modo da ottenere la funzione tupla di Cantor

${\displaystyle \pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N} }$

in questo modo:

${\displaystyle \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:

${\displaystyle \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 ${\displaystyle 0}$ al posti di ${\displaystyle 1}$

Supponiamo sia dato z definito come segue

${\displaystyle z=\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+y}$

e si vogliano trovare x e y. Definiamo alcune variabili intermedie:

${\displaystyle w=x+y}$

${\displaystyle t={\frac {w(w+1)}{2}}={\frac {w^{2}+w}{2}}}$

${\displaystyle z=t+y}$

dove t è il numero triangolare di w. Se risolviamo l'equazione di secondo grado

${\displaystyle w^{2}+w-2t=0}$

per w in funzione di t, otteniamo

${\displaystyle w={\frac {{\sqrt {8t+1}}-1}{2}}}$

che è una funzione strettamente crescente e sempre definita per valori di t reali non negativi. Da

${\displaystyle t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}}}$

otteniamo che

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

e quindi

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

b)     ${\displaystyle t={\frac {w^{2}+w}{2}}={\frac {w(w+1)}{2}}}$

${\displaystyle y=z-t}$

${\displaystyle x=w-y}$.

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

${\displaystyle y=z-t}$ = 1432 − 1431 = 1;

${\displaystyle x=w-y}$ = 53 − 1 = 52;

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

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica