title: Funzione coppia
text: # Funzione coppia
  
  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à
  
  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
  
  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})$
  
  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$
  
  ## Inversione della funzione coppia di Cantor
  
  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$.
      dove ⌊ ⌋ è la funzione di arrotondamento per difetto.
  
  A questo punto per calcolare x e y da z:
  
      a)  $w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor$
      b)  $t={\frac {w^{2}+w}{2}}={\frac {w(w+1)}{2}}$
      $y=z-t$
      $x=w-y$.
  
  ### 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
  
      $y=z-t$ = 1432 − 1431 = 1;
      $x=w-y$ = 53 − 1 = 52;
  