Cosa è il teorema di incompletezza di Gödel?

Nonostante la sua superficiale plausibilità, l'interpretazione formalista della matematica ricevette un duro colpo nel 1931. In quegli anni il matematico e logico di Princeton Kurt Gödel dimostrò un teorema fondamentale secondo cui esistevano enunciati matematici di cui nessuna procedura sistematica poteva determinare la verità o la falsità. Questo teorema non lasciava vie d'uscita, perché forniva una dimostrazione irrefutabile che determinate cose, in matematica, sono realmente impossibili, persino in linea di principio. Il fatto che esistano proposizioni indecidibili in matematica provocò un grosso trauma perché sembrava minare gli stessi fondamenti logici della disciplina.

Il teorema di Gödel sorge da una costellazione di paradossi che circondano l'autoreferenzialità. Consideriamo, come semplice introduzione a questo argomento ingarbugliato, la sconcertante frase: «La presente proposizione è una bugia». Se la proposizione è vera, allora è falsa; e se è falsa, allora è vera. Questi paradossi dell'autoreferenzialità possono essere costruiti facilmente e sono profondamente interessanti; hanno confuso le persone per secoli. Una formulazione medioevale dello stesso dilemma è la seguente:

Socrate: «Ciò che Platone sta per dire è falso».

Platone: «Quello che Socrate ha appena detto è vero».

Il grande matematico e filosofo Bertrand Russell dimostrò che l'esistenza di tali paradossi colpisce al cuore la logica e mina qualunque tentativo diretto di costruire la matematica rigorosamente su un fondamento logico. Gödel adattò alla matematica queste difficoltà insite nel concetto di autoreferenzialità in modo brillante e insolito. Considerò la relazione fra la descrizione della matematica e la matematica stessa. Questa è abbastanza semplice da enunciare, ma richiede un'argomentazione lunga e molto intricata. Per farsi un'idea, si può immaginare di elencare le proposizioni matematiche etichettandole con 1,2,3... Combinare una sequenza di proposizioni in un teorema corrisponde dunque a combinare i numeri naturali che costituiscono le loro etichette. In questo modo le operazioni logiche sulla matematica possono essere fatte corrispondere alle proposizioni matematiche stesse. È questa l'essenza del carattere autoreferenziale della dimostrazione di Gödel. Identificando il soggetto con l'oggetto – proiettando la descrizione della matematica sulla matematica stessa – egli scoprì un paradossale circolo russelliano che conduceva direttamente all'inevitabilità di proposizioni indecidibili. John Barrow ha osservato di sfuggita che se una religione viene definita come un sistema di pensiero che richiede una fede in verità indimostrabili, allora la matematica è la sola religione che può dimostrare di essere tale.

L'idea chiave del teorema di Gödel può essere spiegata con l'aiuto di una storiella. In un paese lontano un gruppo di matematici che non avevano mai sentito parlare di Gödel si convinse che esisteva davvero una procedura sistematica per determinare infallibilmente la verità o falsità di qualunque proposizione sensata, e si propose di dimostrarlo. La loro procedura poteva essere eseguita da una persona, o da un gruppo di persone, o da una macchina, o da qualsiasi combinazione di queste tre possibilità. Nessuno sapeva con certezza quale combinazione avessero scelto i matematici, perché il sistema era situato in un grande edificio universitario, piuttosto simile a un tempio, e l'ingresso era vietato al pubblico. Comunque, il sistema venne chiamato Tom. Per controllare l'abilità di Tom gli venivano sottoposte complesse asserzioni logiche e matematiche di ogni tipo e, dopo il tempo necessario per l'elaborazione, arrivavano puntualmente le risposte: vero, vero, falso, vero, falso... Dopo non molto la fama di Tom si diffuse in tutto il paese. In molti venivano a visitare il laboratorio e aguzzavano sempre di più l'ingegno per formulare problemi sempre più difficili nel tentativo di mettere in difficoltà il sistema. Nessuno ci riuscì. La fiducia dei matematici nell'infallibilità di Tom crebbe a tal punto che persuasero il loro re a offrire un premio a chiunque riuscisse a sconfiggere il suo incredibile potere analitico. Un giorno, un viaggiatore che veniva da un altro paese giunse all'università con una busta e chiese di sfidare Tom. Nella busta c'era un pezzo di carta con una proposizione da sottoporgli. La proposizione, che possiamo indicare con «P» («P» sta per «proposizione» o per «paradosso»), diceva semplicemente: «Tom non può dimostrare che questa proposizione è vera».

P venne sottoposta a Tom. Erano passati appena pochi secondi che il sistema entrò in preda a una specie di convulsione. Dopo mezzo minuto un tecnico giunse correndo dal laboratorio con la notizia che Tom era stato disattivato a causa di problemi tecnici. Che cosa era accaduto? Supponiamo che Tom dovesse arrivare alla conclusione che P è vera. Questo significherebbe che la proposizione «Tom non può dimostrare che questa proposizione è vera» sarebbe stata falsificata. Ma se P è falsificata, non può essere vera. Così se Tom risponde «vero» a P, avrà raggiunto una conclusione falsa, contraddicendo la sua vantata infallibilità. Dunque Tom non può rispondere «vero». Siamo dunque giunti alla conclusione che P è effettivamente vera. Ma nel giungere a questa conclusione abbiamo dimostrato che Tom non può giungere a questa conclusione. Questo significa che noi conosciamo la verità di una proposizione che Tom non può dimostrare. Questa è l'essenza della dimostrazione di Gödel: che esisteranno sempre certe proposizioni vere che non possono essere dimostrate. Il viaggiatore, naturalmente, lo sapeva e non ebbe alcuna difficoltà a costruire P e intascare il premio.

È importante, tuttavia, rendersi conto del fatto che le limitazioni messe in luce dal teorema di Gödel riguardano lo stesso metodo assiomatico di dimostrazione logica, e non una proprietà delle proposizioni che si cerca di dimostrare (o di refutare). Si può sempre trasformare una proposizione vera che è indimostrabile all'interno di un dato sistema di assiomi in un assioma di qualche sistema esteso. Ma allora ci saranno altre proposizioni indimostrabili in questo sistema esteso, e così via.

Il teorema di Gödel fu una devastante battuta d'arresto per il programma formalista, ma l'idea di una procedura meccanica per indagare le proposizioni matematiche non venne abbandonata completamente. Forse le proposizioni indecidibili sono solo stranezze che possono essere eliminate dalla logica e dalla matematica? Se si trovasse un modo per distinguere le proposizioni decidibili da quelle indecidibili, allora determinare se una qualsiasi proposizione appartenente al primo gruppo sia vera o falsa potrebbe pur sempre essere fattibile. Ma è possibile formulare una procedura sistematica per riconoscere in modo infallibile le proposizioni indecidibili ed eliminarle? La sfida venne raccolta da Alonzo Church, un collaboratore di von Neumann a Princeton, il quale dimostrò presto che persino questa meta più modesta era irraggiungibile, almeno in un numero finito di passi. In altri termini: si potrebbero fare asserzioni matematiche potenzialmente vere o false, e si potrebbe intraprendere una procedura sistematica per controllare la loro verità o falsità, ma questa procedura non avrebbe mai termine: il risultato non potrebbe mai essere conosciuto.