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 fra l'insieme prodotto e l'insieme dei numeri naturali :

Utilizzo per il calcolo delle cardinalità L'esistenza di tali funzioni dimostra che la cardinalità dei due insiemi e è la stessa.

Utilizzando opportune funzioni da comporre alla funzione coppia, è possibile dimostrare che anche la cardinalità degli insiemi dei numeri interi e dei numeri razionali è uguale alla cardinalità di .

Inoltre componendo più volte una funzione coppia, è possibile costruire delle applicazioni biunivoche fra qualunque potenza dei naturali e . Questa tecnica è molto usata anche nella teoria della calcolabilità.

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

L'immagine della funzione coppia si indica solitamente con .

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

in questo modo:

Nel calcolo dell'enumerazione di una funzione calcolabile (in informatica teorica) si usa una versione leggermente modificata della funzione coppia di Cantor:

ottenuta enumerando a partire da al posti di

Inversione della funzione coppia di Cantor Supponiamo sia dato z definito come segue

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

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

per w in funzione di t, otteniamo

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

otteniamo che

e quindi . dove ⌊ ⌋ è la funzione di arrotondamento per difetto.

A questo punto per calcolare x e y da z: a)     b)    

.

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 = 1432 − 1431 = 1; = 53 − 1 = 52;

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

Collegamenti esterni

Categoria:Teoria degli insiemi