Funzione coppia

funzione che associa ad ogni coppia ordinata di numeri naturali un numero naturale con corrispondenza uno a uno
(Reindirizzamento da Funzione coppia di Cantor)

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

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 CantorModifica

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 CantorModifica

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)      
 
 .

EsempioModifica

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;

BibliografiaModifica

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

Collegamenti esterniModifica

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