Matematica, logica e paradossi – Parte I
Un lettore mi ha invitato a parlare di paradossi. Ho accettato in cambio di una sua lista di titoli: I paradossi dalla A alla Z di M. Clark, Labirinti, quadrati magici e paradossi logici di M. Danesi, Il libro dei paradossi di N. Falletta, C’era una volta un paradosso di P. Odifreddi, oltre ai bei libri di M. Gardner*. Avverto e chiedo scusa: questo post e il successivo, per quanto piuttosto complicati, possono offrire solo qualche riflessione ma non spiegazioni compiute.
Il Devoto-Oli recita: “Paradosso: proposizione formulata in apparente contraddizione con l’esperienza comune o con i principi elementari della logica, ma che all’esame critico si dimostra valida”. In matematica i paradossi spesso segnalano parti di una teoria da riformulare o addirittura da rifondare.
La madre di tutti i paradossi è forse l’antinomìa del mentitore: “Questa frase è falsa”, di Epimenide di Creta. Se fosse vera allora sarebbe falsa e viceversa! La chiave è l’autoreferenzialità, il fatto che la frase parli di se stessa. Ritroviamo lo stesso principio millenni dopo in teoria degli insiemi nel paradosso di Russell: 1) assumiamo che un insieme sia specificabile con una descrizione dei suoi elementi; 2) assumiamo che un insieme sia specificato se sappiamo dire quali oggetti gli appartengono e quali no; 3) con queste premesse ci sono insiemi che contengono se stessi (per esempio “l’insieme degli oggetti descrivibili con nove parole italiane”); 4) sia X l’insieme degli insiemi che non contengono se stessi; 5) X contiene se stesso o no? Evidentemente siamo nella stessa situazione paradossale: se X contiene se stesso allora non contiene se stesso e viceversa. Questa idea, comunicata da B. Russell a G. Frege proprio mentre usciva il libro di questi sulla neonata teoria degli insiemi, mise in crisi i fondamenti della teoria stessa e portò a una sua riformulazione.
Gödel escogita una costruzione colossale: codificare con dei numeri i simboli correnti e le stesse operazioni logiche. Associa ad ogni proposizione P un numero intero positivo r(P) e le deduzioni logiche diventano operazioni numeriche. Per dare un’idea, se P1 fosse “le rette r ed s sono parallele” e il suo numero fosse r(P1)=5, se P2 fosse “le rette s e t sono parallele” con r(P2)=3 e se la proprietà transitiva fosse la somma, allora P3 = “le rette r e t sono parallele” avrebbe numero r(P3)=5+3=8 (naturalmente la codifica vera è molto più complicata). Dato un numero, ci possiamo chiedere se è pari, se è un quadrato, se è primo, ecc. Analogamente, la proprietà che un numero corrisponda a una proposizione dimostrabile diventa una sua proprietà aritmetica.
Gödel non codifica la geometria, bensì l’aritmetica; ma allora abbiamo numeri che “parlano”di numeri, si apre la porta dell’autoreferenzialità! Gödel ci si butta a capofitto. Riesce a escogitare una proposizione G che dice “il numero g rappresenta una proposizione non dimostrabile”, dove g=r(G), cioè è il numero che codifica la proposizione G stessa! Questa proposizione è necessariamente vera, altrimenti la sua dimostrazione entrerebbe in contraddizione con se stessa; ma proprio per la sua verità non è dimostrabile.
Con questo trucco geniale Gödel dimostra che un sistema formale F contenente l’aritmetica è incompleto: presenta delle proposizioni vere ma non dimostrabili in F. Ehi, ma noi abbiamo appena dimostrato G! Sì, ma in un sistema formale F’ esterno ad F. In F’ci saranno proposizioni vere ma non dimostrabili in F’ e così via. (Si veda il Cap. 10 di “Anelli nell’io” di D. Hofstadter.)
“Cosa ci viene in tasca?” chiederà qualcuno. Gödel ha indicato il confine di ciò che è dimostrabile da una macchina, così come A. Turing ha mostrato il limite di ciò che è calcolabile. Da Epimenide a Russel a Gödel ci siamo dotati di un “microscopio” con cui indagare tecnicamente, non a chiacchiere, la natura del ragionamento, del vero e del falso.
*Altri lettori consigliano Qual è il titolo di questo libro? di R. Smullyan. Li accontentiamo.