Diagonalizzando

Quello che mi piace di alcuni ragionamenti matematici é la loro incredibile eleganza: pochi, semplici passi, ed ecco che vi si presenta una conclusione inopinabile, incontestabile. Non é il risultato bello in sé, ma la maniera in cui ci si giunge, a mio avviso.

Ad esempio, consideriamo un problema che avevamo già affrontato: sono di più i numeri reali o i numeri naturali?
Nota: ricordo che i numeri naturali sono i numeri interi positivi (1,2,3…), mentre i numeri reali sono, in pratica, tutti quelli che possiamo scrivere con uno sviluppo decimale (anche infinito, come nel caso di pigreco).

Una fase cruciale del risolvere un problema é (nonostante sembri banale) porre le domande corrette: una domanda come quella sopra serve veramente a poco, scritta in quella maniera. Poiché sia i naturali che i reali formano due insiemi, potremmo riformulare il tutto cosi’:

Contiene più elementi l’insieme N (dei Naturali) o l’insieme R (dei Reali)? In termini tecnici, quale cardinalità é maggiore, |N| o |R|?

Chiaramente abbiamo fatto un passo avanti, perché ora possiamo avvalerci di tutta la teoria degli Insiemi per rispondere a questa domanda. Visto che non possiamo fisicamente contare gli elementi (altrimenti sarebbe troppo semplice), possiamo leggere da un qualunque testo di algebra che “due insiemi hanno la stessa cardinalità se possiamo associare ad ogni elemento del primo un elemento del secondo“. Questo é anche abbastanza ovvio: se abbiamo due cesti di frutta e, ad esempio, se continuando a tirare fuori un frutto da ciascuno dei due, i due cesti ad un certo momento restano entrambi vuoti, avevano lo stesso numero di frutti al loro interno.

Prima di cimentarci subito con i Reali, proviamo ad applicare questo concetto a due insiemi più facili: i numeri Naturali (N) ed i numeri Interi Z (i numeri naturali più i numeri negativi interi), usando la prima associazione che ci viene in mente:

Z        N

1  –>  1
-1 –>  2
2  –>  3
-2 –>  4

E cosi via. Chiaramente in questa maniera copriamo l’intero insieme dei numeri Interi (in verità, “chiaramente” non esiste in Matematica, e questa affermazione si potrebbe dimostrare per Induzione, ma evitiamo e fidiamoci dell’intuito), quindi possiamo dire che “esistono tanti numeri interi quanti numeri naturali“. Possiamo fare un ragionamento simile anche confrontando numeri Naturali e Razionali (tutti quei numeri che si possono esprimere come una frazione n/m), quindi siamo portati a pensare che ampliando il tutto ai Reali (che, in pratica, sono i Razionali più “un po’” di numeri che non si possono esprimere come frazioni) il discorso rimanga lo stesso.

A questo punto abbiamo bisogno di una dimostrazione leggermente più articolata, chiamata “dimostrazione diagonale di Cantor“. Supponiamo che esista la suddetta relazione fra N ed R: come prima, quindi, potremo scrivere qualcosa come (considerando solo i numeri Reali compresi fra 0 ed 1):

1 -> 0.54656512…
2 -> 0.17985344…
3 -> 0.3365999…
4 -> 0.46953113…
…

I numeri precisi ci interessano poco, l’importante é che queste relazioni esistano (come supposto per ipotesi). A questo punto, consideriamo il seguente numero: prendiamo le cifre sulla “diagonale” dei numeri reali elencati sopra, incrementiamole di uno ed uniamole a formare uno sviluppo decimale:

1 -> 0.54656512…
2 -> 0.17985344…
3 -> 0.3365999…
4 -> 0.46953113…
…

Otteniamo il numero 0.6876… (5+1, 7+1, 6+1, 5+1…). Questo é un numero reale, quindi dovrebbe essere incluso nella lista di prima. Possiamo notare pero’ che, sicuramente:

• Differisce dalla prima riga per la prima cifra decimale.
• Differisce dalla seconda riga per la seconda cifra decimale.
• Differisce dalla terza riga per terza cifra decimale.

Più in generale, differisce dalla riga n-esima per la cifra n-esima: non é uguale a nessun valore elencato prima, quindi abbiamo trovato un numero reale che non é legato a nessun numero naturale! Poiché questo viola la nostra ipotesi, possiamo concludere che l’ipotesi stessa sia falsa: non esiste una relazione biunivoca fra N ed R. Di più: poiché abbiamo trovato un Reale non incluso nella tabella, possiamo dire che “esistono più numeri Reali che numeri Naturali” (peggio: esistono più numeri reali fra 0 ed 1 che numeri naturali)!

Continuando a ragionare su questo risultato: poiché l’insieme dei Naturali é infinito, capiamo che non esiste “un solo” infinito, ma diversi, ciascuno più grande dell’altro! Ci si potrebbe chiedere se la cardinalità di R é un infinito ‘appena più grande‘ della cardinalità dei numeri Naturali, o se esistono altri infiniti “intermedi”. Questo, per quanto vi possa sembrare strano, é uno dei grandi problemi irrisolti della Matematica moderna!

Nota Conclusiva 1: Il ragionamento diagonale di Cantor é stato usato per moltissime altre dimostrazioni, come quella di Incompletezza di Gödel o quella dell’Arresto di Touring, se l’argomento interessa sapete cosa basta: un commento!

Nota Conclusiva 2: Asserire che un’ipotesi sia vera, per poi ottenerne un assurdo e concludere che l’ipotesi iniziale era falsa (come abbiamo fatto prima), o viceversa, viene chiamato in Matematica “reductio ad absurdum”, ed é estremamente comune (e bella, oserei dire).