Funzione coppia

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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

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

A questo punto per calcolare x e y da z:

a)    
b)    
.

Esempio[modifica | modifica wikitesto]

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

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

Collegamenti esterni[modifica | modifica wikitesto]

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