Enumerazione di Cantor
dei Razionali positivi

Stefano Berardi

Riassunto. Scriviamo una formula per calcolare l'i-esimo elemento della enumerazione di Cantor delle coppie di numeri naturali. A partire da essa, generiamo l'enumerazione dei razionali positivi.

Le enumerazioni di cui parliamo in questa nota furono utilizzate da Cantor per provare che le coppie di numeri naturali (insieme N⨯N) e i numeri razionali positivi (insieme Q+) formano insiemi numerabili, ovvero in corrispondenza 1-1 con l'insieme dei numeri naturali. Questo risultato, semplice per un matematico, è, a prima vista, estremamente anti-intuitivo. Immaginiamo infatti di disporre interi e razionali non negativi su di una semiretta: tra un intero e il successivo, per esempio tra 0 e 1 ci sono infiniti numeri razionali. Eppure, è possibile porre in corrispondenza uno-a-uno gli interi non negativi e i razionali, dunque i primi sono tanti quanto i secondi.
Definiremo sia un programma che calcoli tale enumerazioni, sia una loro rappresentazione nel piano cartesiano, con l'idea che disegni e grafici ci aiutino a comprendere il paradosso.

1. Un'enumerazione delle coppie di numeri naturali

Prima di scrivere una enumerazione dei numeri razionali, cominciamo a scrivere una enumerazione delle coppie di numeri naturali. Dato che i numeri razionali sono rappresentabili in forma di frazioni, e le frazioni sono coppie di numeri naturali, partendo da una enumerazione delle coppie di numeri naturali definiremo poi una enumerazione dei razionali (positivi).
Definiremo una formula Cantor[i] che calcoli l'i-esima coppia di numeri naturali, nella enumerazione di Cantor di tali coppie. L'enumerazione di Cantor enumerazione inizia con una coppia di somma 0, poi considera 2 coppie di somma 1, poi 3 coppie di somma 2, e così via:
              (0,0),  (0,1), (1,0), (0,2), (1,1), (2,0),  (0,3), (1,2), (2,1), (3,0), ...

Il primo passo è definire un'operazione SC[i], che calcoli la somma della coppia numero i (numerando a partire da 0). La lista delle somme delle coppie, ovvero dei valori di SC[0], SC[1], SC[2], ..., è:
               0,   1,1,   2,2,2,   3,3,3,3,   ...
  (con 0 ripetuto 1 volta, 1 ripetuto 2 volte, 2 ripetuto 3 volte e così via). Questa successione per scrivere i valori da 0 a n ha bisogno di 1+2+3+4+...+(n+1) posti, dunque (n+1)(n+2)/2 posti, numerati da 0 a f(n)=(n+1)(n+2)/2 - 1. L'elemento di posto i della successione è il valore di SC[i]. Per calcolare tale valore, dobbiamo trovare il minimo intero n>=i, ovvero il minimo n tale che i sia compreso tra 0 e f(n). Dato che f è crescente continua sui reali positivi, è sufficente risolvere l'equazione f(n) = i e prendere il primo intero >= della soluzione.

Scartiamo la soluzione negativa, e definiamo SC[i] uguale alla seconda (arrotondata per eccesso).

Elenchiamo i primi valori di SC[i] per controllare che siamo della forma voluta.

Possiamo ora definire un'operazione Cantor[i] che costruisce la coppia di posto i nell'enumerazione di Cantor. Sia c = SC[i] = la somma della coppia (a,b) di posto i. Le (c+1) coppie di somma c sono (0,c), (1,c-1), (2,c-2), ..., (c,0); la coppia (a,b) è una di esse. L'ultima coppia, (c,0), si trova nel posto di indice f[c]. Le c precedenti si trovano in uno dei c posti precedenti ad esso. Il secondo indice della coppia, b, varia da c a 0, e vale 0 in f[c]. Il valore di b scende di 1 ad ogni passo verso destra, quindi in generale b vale (f[c]-i), cioè la distanza tra il posto i in cui si trova (a,b), ed f[c]. Il primo indice, a, vale (c-b) (dato che a+b deve fare c).

Costruiamo ora la tabella dei primi cento valori di i e disegnamone il grafico, una linea che percorre una e una sola volta i punti del piano con coordinate due numeri naturali. Notiamo che Mathematica rappresenta le coppie con la notazione {a,b} (quella che noi usiamo per gli insiemi) anzichè (a,b).

Disegnamo la corrispondenza 1-1 così ottenuta: vediamo che l'enumerazione di Cantor segue un cammino tortuoso nel piano per poter raggiungere tutte le coppie di interi non negativi.

2. Un'enumerazione dei razionali positivi.

Definiremo ora, a partire dall'enumerazione senza ripetizioni delle coppie, l'enumerazione senza ripetizione dei razionali positivi. Occorre enumerare le frazioni a/b con a,b>0 e ridotte a minimi termini, per evitare di elencare lo stesso razionale due volte.

Definiamo quindi una operazione Ratio, che rimpiazza le  coppie {a,b} con a=0 oppure b=0 oppure a, b non coprimi con un punto ".", altrimenti rimpiazza {a,b} con a/b.

Applicando Ratio a ogni coppia nell'enumerazione di Cantor, e quindi eliminando tutti i punti "." inseriti, otteniamo una enumerazione dei razionali senza ripetizioni.

Vediamo ora la lista di razionali ottenuta applicando il procedimento descritto sopra alle prime 20 coppie nell'enumerazione di Cantor.

Calcoliamo ora la lista dei razionali ottenuti a partire dalle prime 1000 coppie. Disegnamone il grafico, associando al razionale r di posizione j nella lista il punto di coordinate (j,r) del piano.

Contiamo quanti rationali positivi che abbiamo trovato (saranno meno di 1000, dato che alcune coppie sono state cancellate).

Vediamo ora quale razionale corrisponde al posto i della enumerazione. Consideriamo tale corrispondenza come una funzione e disegnamone il grafico. In ascissa indichiamo il posto occupato nella lista dei razionali, e in ordinata il razionale contenuto in tale posto. Vediamo come la funzione vada su e giù, seguendo un numero potenzialmente infinito di percorsi diversi per poter raggiungere ogni razionale positivo.