Funzione coppia

Da Wikipedia, l'enciclopedia libera.

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à[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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)


Attenzione: 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

(Fonte: Linguaggi Modelli Complessita' - Ausiello, D'Amore, Gambosi)

Inversione della funzione coppia di Cantor[modifica | modifica sorgente]

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 .

A questo punto per calcolare x e y da z:

 w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor
 t = \frac{w^2 + w}{2}
 y = z - t
 x = w - y .

Collegamenti esterni[modifica | modifica sorgente]


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