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

Utilizzo per il calcolo delle cardinalità[modifica | modifica wikitesto]

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

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

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

.

A questo punto per calcolare x e y da z:

.

Bibliografia[modifica | modifica wikitesto]

  • Ausiello, D'Amore, Gambosi, Linguaggi Modelli Complessita

Collegamenti esterni[modifica | modifica wikitesto]

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