Per gli insiemi finiti contare è facile. Con gli insiemi infiniti l'intuizione smette di funzionare: ci sono più numeri naturali che numeri pari? Più frazioni che interi? La risposta, data da Georg Cantor alla fine dell'Ottocento, è sorprendente e ha conseguenze dirette per l'informatica: esistono infiniti di grandezza diversa, e questo implica che ci sono problemi che nessun programma può risolvere.
Confrontare insiemi senza contarli
Due insiemi hanno la stessa cardinalità se esiste una biiezione tra loro, cioè una corrispondenza che associa a ogni elemento del primo esattamente un elemento del secondo, e viceversa, senza lasciare nessuno fuori.
È il modo più primitivo di confrontare quantità: per sapere se in una sala ci sono tante sedie quante persone non serve contarle, basta far sedere tutti e vedere se avanzano sedie o persone. La definizione funziona anche quando contare è impossibile.
Sorprese con gli infiniti numerabili
Un insieme si dice numerabile se ha la stessa cardinalità dei numeri naturali ℕ = {0, 1, 2, …}. In pratica: se i suoi elementi si possono disporre in un elenco infinito, primo, secondo, terzo, in cui ogni elemento compare prima o poi.
I numeri pari
La funzione f(n) = 2n associa 0 → 0, 1 → 2, 2 → 4, e così via. È una biiezione tra ℕ e i numeri pari. Quindi i pari sono «tanti quanti» i naturali, anche se sono un sottoinsieme proprio. Questa è una caratteristica che distingue gli insiemi infiniti: possono avere la stessa cardinalità di una loro parte.
Gli interi
ℤ si può elencare alternando i segni: 0, 1, −1, 2, −2, 3, −3, … Ogni intero compare in una posizione precisa, quindi anche ℤ è numerabile.
I razionali
Qui l'intuizione fa resistenza, perché tra due frazioni qualsiasi ce ne sono infinite altre. Eppure anche ℚ è numerabile. Si dispongono le frazioni positive p/q in una tabella infinita, con p sulle righe e q sulle colonne, e si percorrono le diagonali: prima quelle con p + q = 2, poi p + q = 3, poi p + q = 4, saltando le frazioni non ridotte che rappresentano valori già visti.
1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, …
Ogni frazione positiva compare prima o poi, perché ha una somma p + q finita. Aggiungendo lo zero e i negativi con il trucco dell'alternanza si ottiene un elenco di tutti i razionali.
Le stringhe finite
Anche l'insieme di tutte le stringhe finite su un alfabeto finito è numerabile: si elencano prima quelle di lunghezza 0, poi quelle di lunghezza 1 in ordine alfabetico, poi quelle di lunghezza 2, e così via. Ogni programma per computer è una stringa finita, quindi i programmi possibili sono un'infinità numerabile.
L'argomento diagonale
I numeri reali non sono numerabili. Basta dimostrarlo per i reali tra 0 e 1, e lo si fa per assurdo.
Supponiamo di avere un elenco completo r₁, r₂, r₃, … di tutti i reali in (0, 1), scritti in forma decimale:
r₁ = 0. 5 1 4 0 …
r₂ = 0. 3 3 3 3 …
r₃ = 0. 7 1 8 2 …
r₄ = 0. 0 0 9 1 …
Costruiamo un numero d scegliendo la sua n-esima cifra diversa dalla n-esima cifra di rₙ. Per esempio: se la cifra sulla diagonale è 5, mettiamo 4; altrimenti mettiamo 5. Qui la diagonale è 5, 3, 8, 1, quindi d = 0,4555…
Il numero d differisce da r₁ nella prima cifra, da r₂ nella seconda, da rₙ nell'n-esima. Quindi non è nessuno dei numeri dell'elenco, che dunque non era completo. Contraddizione. (Scegliere solo le cifre 4 e 5 evita l'ambiguità di numeri come 0,1999… = 0,2000….)
Lo stesso schema dimostra un fatto più generale: per ogni insieme A, l'insieme delle parti 𝒫(A) ha cardinalità strettamente maggiore di A. Non esiste un infinito più grande di tutti.
Perché interessa a un informatico
L'insieme dei problemi decisionali sui numeri naturali corrisponde all'insieme dei sottoinsiemi di ℕ, che non è numerabile. I programmi, come visto, sono solo un'infinità numerabile. Quindi esistono problemi per cui nessun programma può dare la risposta: i programmi non bastano a coprirli tutti.
Questo ragionamento non indica quali siano questi problemi; per trovarne uno concreto, come il problema dell'arresto, si usa una versione dell'argomento diagonale applicata ai programmi stessi. Ma già il semplice confronto tra cardinalità mostra che l'incalcolabile non è un'eccezione: è la regola.
In sintesi
- Due insiemi hanno la stessa cardinalità se esiste una biiezione tra loro.
- Pari, interi, razionali e stringhe finite sono tutti numerabili, cioè elencabili.
- I numeri reali non sono numerabili: l'argomento diagonale costruisce sempre un numero mancante.
- Per ogni insieme, l'insieme delle parti è strettamente più grande.
- I programmi sono numerabili, i problemi no: esistono problemi che nessun programma risolve.
