Il teorema di Gödel ovvero i teoremi limitativi dell’aritmetica

Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook

I teoremi d’incompletezza di Gödel del 1931 sono i risultati più profondi e spettacolari conseguiti dalla logica del Novecento. Il primo teorema afferma che la teoria formale dell’aritmetica, se coerente, contiene una proposizione indecidibile; il secondo teorema aggiunge che l’aritmetica non può dimostrare con i propri mezzi la sua coerenza. 

L’intuizione di Gödel

Kurt Gödel

Appendice agli atti del Secondo convegno di epistemologia delle scienze esatte di Königsberg 

Un sistema formale si dice completo se ogni proposizione esprimibile con i suoi simboli è formalmente decidibile a partire dagli assiomi, vale a dire se per ogni proporzione A di quel tipo esiste una catena deduttiva finita che si sviluppa secondo le regole del calcolo logico la quale comincia con certi assiomi e finisce o con la proposizione A o con la proposizione non-A. Un sistema S si dice completo rispetto a una certa classe K di proposizioni se per lo meno tutte le proposizioni di K sono decidibili a partire dagli assiomi S.

Ciò che viene mostrato nel lavoro citato è che non esiste alcun sistema con un numero finito di assiomi che sia completo anche soltanto rispetto alle proposizioni aritmetiche; dove per “proposizioni aritmetiche” devono intendersi quelle proposizioni in cui gli unici concetti che vi figurano sono, oltre a +, ., e = (addizione, moltiplicazione e identità riferite a numeri naturali), i connettivi logici del calcolo proposizionale e i simboli per il quantificatore universale e per quello esistenziale, riferiti questi, peraltro, solo a variabili che variano sopra i numeri naturali (nelle proposizioni aritmetiche, quindi, non compaiono assolutamente variabili diverse da quelle per numeri naturali).

Persino in quei sistemi che hanno un numero infinito di assiomi esistono sempre proposizioni aritmetiche indecidibili, purché la “regola che determina gli assiomi” soddisfi a certe condizioni (molto generali).

Da quanto detto risulta in particolare che tutti i sistemi formali della matematica finora conosciuti - per esempio, quello dei Principia Mathematica (ivi compresi gli assiomi di riducibilità, dell’infinito e di scelta) oppure quelli assiomatici per la teoria degli insiemi di Zermelo-Fraenkel e di von Neumann, o ancora i sistemi formali della scuola hilbertiana - contengono proposizioni aritmetiche indecidibili.

in Grande antologia filosofica, diretta da M.F. Sciacca e M. Schiavone, Milano, Marzorati, 1978

Al congresso internazionale dei matematici di Bologna nel 1928, David Hilbert aveva incluso, tra i problemi irrisolti nell’ambito della ricerca sui fondamenti della matematica, il problema della completezza (semantica) della logica del primo ordine e quello della completezza (sintattica) di un sistema formale per l’aritmetica, cioè il cuore stesso della matematica. Entrambi i problemi furono risolti – positivamente per la logica del primo ordine (1930), ma negativamente per l’aritmetica (1931) – nel giro di un paio d’anni dal giovane austriaco Kurt Gödel, unanimemente considerato il più importante logico del Novecento. La completezza semantica di una teoria logica non va confusa con la completezza sintattica di un sistema formale: un sistema di assiomi ha la proprietà di essere sintatticamente completo se ogni sua formula è dimostrabile oppure è refutabile. Nel gennaio del 1931 appare sui Monatshefte fur Mathematik und Physik, una memoria intitolata Über formal unentscheidbare Sätze der “Principia Mathematica” und verwandter Systeme (Sulle proposizioni formalmente indecidibili dei “Principia Mathematica” e di sistemi affini), in cui Gödel non solo dimostra che l’aritmetica è sintatticamente incompleta (ammesso che sia coerente), ma che essa è incompletabile. Il 7 settembre 1930 Gödel aveva già annunciato questo risultato durante il convegno di Königsberg sui fondamenti della matematica.

Critica della ragion formale

Gödel inizia la sua esposizione analizzando i Principia Mathematica di Whitehead e Russell e la teoria assiomatica degli insiemi di Zermelo-Freankel. Egli osserva che la formalizzazione permette di svolgere le dimostrazioni seguendo poche regole meccaniche (gli assiomi e le regole di inferenza del sistema formale stesso). “Si potrebbe pensare” – scrive lo stesso Gödel – “che questi assiomi e regole di inferenza siano sufficienti per decidere tutte le questioni matematiche che possono essere formalmente espresse all’interno degli stessi sistemi. In realtà sarà dimostrato che questo non è vero, ma che esistono problemi relativamente semplici che non possono essere decisi dagli assiomi.” In altre parole, indicando la teoria formale dell’aritmetica con PA (“aritmetica di Peano”, dal nome del matematico italiano Giuseppe Peano) e con “|–” la relazione di dimostrabilità (PA |– A vuol dire che A è dimostrabile in PA; altrimenti, scriveremo PA |/–A), il primo teorema d’incompletezza afferma: se PA è coerente, allora è incompleto, ossia esiste un enunciato G nel linguaggio di PA, tale che né PA |– G né PA |–¬G.

In altre parole, esiste un enunciato formalmente indecidibile in PA.

Questo teorema è tutto incentrato sulla possibilità dell’aritmetica di rappresentare la propria sintassi. Il punto di partenza della dimostrazione è dunque la codifica della metateoria di PA entro PA, vale a dire la rappresentazione univoca di ogni enunciato di PA come stringa finita di numeri naturali e di ogni derivazione come stringa finita di stringhe finite di numeri naturali. La codifica di ogni ente sintattico del formalismo di PA è effettiva, perché dipende esclusivamente dalla sua struttura; in particolare, per questa codifica Gödel si serve di funzioni ricorsive primitive. Attraverso questo procedimento tecnico chiamato gödelizzazione – che Gödel stesso ammetterà di avere ripreso da Leibniz – ogni asserzione metateorica relativa a PA diventa automaticamente un’asserzione che concerne numeri naturali. L’idea guida della dimostrazione consiste allora nell’allestire una sorta di paradosso del mentitore all’interno dell’aritmetica, costruendo un enunciato G che esprime formalmente la proprietà: “G non è dimostrabile in PA”. Fissato un modello di PA, l’enunciato G oppure l’enunciato ¬G deve essere vero. In particolare, l’enunciato G – poiché asserisce la propria indimostrabilità e non è dimostrabile in PA – è vero nel modello più intuitivo, quello usuale di PA, per il quale 0, succ, +, x e = sono rispettivamente interpretati come il numero naturale 0, la funzione successore, l’addizione, la moltiplicazione e l’uguaglianza. (E tuttavia, va osservato che esistono anche modelli di PA in cui G è falsa: infatti, applicando il teorema di completezza semantica, dall’indimostrabilità di G in PA segue che G non è conseguenza logica di PA, ossia che non tutti i modelli di PA sono anche modelli di G.) Naturalmente non è possibile ovviare a questa situazione semplicemente aggiungendo la formula G oppure la sua negazione ¬G agli assiomi originali di PA, perché così facendo si ripresenterebbe il medesimo fenomeno: una nuova formula G’ mostrerebbe l’incompletezza della teoria comprendente questa estensione. Dunque, la coerenza e la completezza di PA sono proprietà fra loro incompatibili.

Il secondo teorema d’incompletezza afferma l’impossibilità di dimostrare la coerenza di PA all’interno della teoria stessa, se PA è coerente. Formalmente:

se PA è coerente, allora PA |/– Coer_PA,

dove Coer_PA è l’enunciato formalizzato che asserisce la coerenza di PA.

Questo significa che per dimostrare la coerenza dell’aritmetica dobbiamo per forza usare strumenti all’esterno dell’aritmetica, cioè inferenze che non sono formalizzabili in PA.

Enunciati aritmetici genuini

L’enunciato G del primo teorema d’incompletezza è piuttosto esplicito ma sicuramente artificiale. Già nel 1930, in occasione del Congresso di Königsberg, John von Neumann aveva interrogato Gödel in merito all’esistenza di enunciati indecidibili che fossero puramente aritmetici. Il problema di trovare enunciati con un genuino contenuto aritmetico, indecidibili in PA viene sistematicamente indagato a partire dagli anni Settanta del Novecento: nel 1977, Jeff Paris e Leo Harrington esibiscono una variante del teorema di Ramsey finito; negli anni Ottanta, Paris e Laurie Kirby dimostrano l’indecidibilità in PA del teorema di Goodstein e Harvey Friedman l’indecidibilità in PA di una variante del teorema di Kruskal, un risultato fondamentale di combinatoria, ricco di importanti applicazioni anche in informatica teorica (per esempio, si applica al problema della terminazione di sistemi di riscrittura). Ma il primo esempio matematicamente soddisfacente di un enunciato indipendente da PA, è fornito da Gödel stesso e molto tempo prima. Nel 1958 egli introduce il sistema T, un’estensione di λ-calcolo semplice, con tipi primitivi per numeri naturali e booleani, e mostra che il teorema di normalizzazione forte per il sistema T è un enunciato indipendente da PA.

Conseguenze filosofiche

Da un punto di vista propriamente filosofico, i teoremi d’incompletezza mettono in discussione l’efficacia di un’impostazione della matematica su base assiomatica: non solo gli assiomi originali dell’aritmetica non riescono a includere tutte le informazioni che avrebbero dovuto auspicabilmente convogliare, ma aumentando l’insieme degli assiomi questa discontinuità tra verità e dimostrabilità rimane invariata. Secondo il logico Emil Post, l’incompletezza è la più lampante testimonianza della creatività del pensiero matematico: “questa conclusione deve inevitabilmente portare a un rovesciamento, almeno parziale, di tutto l’orientamento assiomatico del tardo Ottocento e del primo Novecento, con un ritorno al significato e alla verità come elementi intrinseci alla matematica”. Quel che è certo, è che i due teoremi d’incompletezza decretano il duplice fallimento del progetto fondazionale del logicismo e del formalismo: il primo teorema infirma il progetto logicista di Gottlob Frege e poi di Bertrand Russell di esprimere tutti i concetti matematici in termini di concetti logici, e quindi di ridurre la verità matematica alla verità logica: come può la prima essere riducibile alla seconda, se esistono delle verità matematiche (cioè verità logiche, per il logicismo) collocate oltre la soglia della dimostrabilità?

Il secondo teorema d’incompletezza aggiunge che è irrealizzabile anche il più sofisticato programma di Hilbert che tenta di dimostrare la coerenza dell’aritmetica basandosi su metodi tutti “interni” (algoritmici o combinatori), un po’ come se un parlamento votasse per la propria immunità. E tuttavia se i risultati di Gödel ci conducono a una drastica e profonda revisione del ruolo della formalizzazione nell’attività matematica, va aggiunto che essi mostrano che la formalizzazione è una nozione sufficientemente potente da indicarci i propri stessi limiti: da questa prospettiva, la proposta formalista di Hilbert pone un problema, un problema profondo, e riesce a risolverlo brillantemente con i propri mezzi, sia pure contro se stesso.