Il teorema di incompletezza

Questo teorema si può enunciare come segue:

Se un sistema formale S è consistente, allora l'enunciato C(S) che ne esprime la consistenza non è dimostrabile in S.

Dimostrazione

Una volta stabilito il teorema precedente, questo segue quasi banalmente (se - come sempre - non vogliamo essere troppo rigorosi).
Basta osservare che il teorema di indecidibilità ci dice che C(S) implica V, cioè ci dice che se S è consistente allora esiste un enunciato V vero ma non dimostrabile in S. Ora, se si dimostrasse C(S), si dimostrerebbe anche V, ma questo è escluso proprio dal primo teorema...
Semplice in modo sconcertante, vero?

Breve discussione

A dispetto della 'semplicità', questo di Gödel è un risultato della massima importanza: da quando la teoria degli insiemi di Cantor cominciò ad avere successo, verso la fine del secolo scorso, molti matematici cominciarono ad usarne le tecniche, anche utilizzando considerazioni implicanti insiemi infiniti. Al comparire, all'inizio del secolo, dei primi paradossi (o antinomie, quella di Russel è del 1902) i matematici cominciarono a pensare che qualcosa fosse sfuggito loro di mano, e si diedero ad una ricerca volta a garantire che i fondamenti della loro scienza fossero (e rimanessero) indenni da simili contraddizioni intrinseche.
Lo stesso Russel, insieme a Whitehead, cominciò a scrivere un'opera monumentale nella quale le regole iniziali dovevano essere scelte con cura proprio per evitare che potessero sorgere paradossi. Quest'opera è Principia Mathematica, citata proprio da Gödel nel titolo del suo lavoro come esempio di sistema formale intrinsecamente incompleto!
Un altro tentativo fu fatto da uno dei matematici più influenti di questo periodo, David Hilbert, che propose un programma che doveva garantire matematicamente la consistenza del sistema. Secondo questo programma occorreva appunto trovare una dimostrazione 'matematica' della consistenza della matematica (o di almeno di alcune sue aree). È proprio quanto Gödel dimostra essere impossibile!

Attenzione: questo fatto non ha niente a che vedere con una presunta impossibilità assoluta di dimostrare la consistenza di un sistema formale con metodi che lo trascendano! Nel 1936 Gentzen riuscirà a dimostrare che l'aritmetica è consistente, ma utilizzando metodi che non sono in alcun modo rappresentabili aritmeticamente. Ma se vogliamo essere rompiscatole fino in fondo, il problema con simili dimostrazioni è che utilizzano ipotesi che non sono in sé più 'certe' della stessa consistenza del sistema che si vuole dimostrare consistente...

Insomma, il lavoro di Gödel non lascia spazio a chi vorrebbe considerare la matematica solo un 'gioco' formale completo, consistente in modo formalmente dimostrabile.
Ma questo fatto lascia maggior libertà al matematico, che ormai sa non poter esistere alcun sistema formale che possa imprigionare le sue intuizioni. Il procedimento di ricerca della verità è un fatto creativo, non sempre e solo riducibile ad un puro gioco formale. A me personalmente (e - ne sono certo - a tanti altri) questa cosa fa piacere.

E per finire...

Per finire, una chicca: un bell'enunciato indecidibile servito caldo caldo!
Devo anche questo a Penrose che, nella prefazione alla riedizione inglese del suo capolavoro The Emperor's New Mind presenta questo enunciato facilmente comprensibile, della cui verità (con un po' di pazienza) ci si riesce a convincere, ma che è indecidibile nell'ambito dell'ordinaria aritmetica!

Prendiamo un numero qualsiasi ed esprimiamolo come somma di potenze di 2, eventualmente trasformando in potenze di due anche gli esponenti. Ad esempio:

3 = 21 + 1

Ora applichiamo ripetutamente questa semplice procedura:

(a) incrementiamo la 'base' di 1
(b) sottraiamo 1

ottenendo:

31 + 1
31

ripetiamo (trascurando l'esponente '1'):

4
4-1=3=3x40

dove ho esplicitamente scritto la 'base' raggiunta, in questo caso '4', che, per ottenere il corretto risultato '3', deve essere elevata all'esponente '0' (ricordo che, per ogni a, a0=1). Importante osservare che da qui in poi la nuova base (che, per l'operazione (a) si incrementa di uno ad ogni passo) non avrà più alcuna influenza sul numero raggiunto ('3' in questo caso) che d'ora in poi non potrà fare altro che diminuire di uno ad ogni passo, in virtù dell'operazione (b). Continuiamo:

3x50
3x50-1=2.

Ci convinciamo senza troppa difficoltà che il nostro numero di partenza alla fine arriva a zero. Questo è vero per qualunque numero di partenza, in virtù del ragionamento 'informale' scritto sopra in grassetto. Se vuoi fare l'esperimento col numero 4=22 ti puoi convincere in prima persona che il ragionamento è giusto; armati però di pazienza: si incomincia con 27=33 e si continua con 26=27-1=2x32+2x3+2 che diventa, applicando l'operazione (a), 2x42+2x4+2=42 che, per (b), diventa 41=42-1=2x42+2x4+1 e proseguendo si ottiene 61=2x52+2x5+1 e poi 60, 84, 83, 110... ma prima di poter ragionare come ho fatto poco fa, il numero diventa tanto grande che occorrerebbero la bellezza di 121.210.625 cifre per esprimerlo in notazione decimale!

Ma quello che è veramente notevole è che questo enunciato rappresenta un enunciato indecidibile per la normale procedura di induzione che si utilizza nell'aritmetica ordinaria.

Tengo a osservare esplicitamente che, a dispetto della sua indecidibilità, questo enunciato non solo è vero, ma abbiamo a disposizione ben tre(!) modi per dimostrarlo! Vediamoli:

  1. In fondo Goodstein il suo teorema l'ha dimostrato! Ha usato una tecnica non riconducibile alla normale procedura di induzione, ma l'ha dimostrato rigorosamente, anche se al di fuori dell'ordinaria aritmetica.

  2. Kirby e Paris hanno dimostrato che il teorema di Goodstein è una affermazione di Gödel per il 'sistema formale' della procedura di induzione aritmetica. Segue che, se noi crediamo alla validità di questa procedura, crediamo anche (con le stesso grado di certezza, per così dire) al teorema di Goodstein.
    (Nella terminologia utilizzata nella dimostrazione data qui, il nostro programma D 'equivale' alla procedura di induzione aritmetica e l'affermazione "il programma Pk(k) non termina" 'equivale' all'enunciato del teorema di Goodstein. Se credo nella validità di D, credo anche all'affermazione "il programma Pk(k) non termina").

  3. Ci convinciamo che il teorema è vero seguendo il discorso (informale) fatto in precedenza. Credo di poter affermare che chiunque (anche chi è dotato di poco intuito matematico) possa venir convinto da quel ragionamento, purché lo capisca. Naturalmente è lecito richiedere una dimostrazione rigorosa, e qui sopra ne ho indicate due.

Credo che il tipo di ragionamento citato nell'ultimo punto qui sopra sia un bell'esempio di quell'intuizione della quale i ragionamenti basati sui sistemi formali sono e resteranno per sempre privi. E seguendo ancora una volta Penrose, credo che ne resteranno privi a lungo (o forse per sempre) anche i computer, per nostra fortuna!

Ma è davvero così?

Va detto che questa conclusione è forse un po' troppo ottimistica: lo stesso Gödel afferma (pag. 310 dei Collected Works III, Oxford University Press, 1995. Evidenziazioni mie):

O la matematica è inesauribile nel senso che i suoi assiomi evidenti non possono mai essere ricompresi in una regola finita, il che vuol dire che la mente umana (anche nel regno della pura matematica) sorpassa infinitamente i poteri di qualsiasi macchina finita, oppure esistono problemi [matematici] assolutamente irrisolvibili.

Quindi, o la mente ha davvero una natura non algoritmica e le conclusioni di Penrose ed altri circa l'intelligenza artificiale sono corrette oppure l'affermazione di Gödel 'esistono problemi [matematici] assolutamente irrisolvibili' significa che la mente è equivalente ad una macchina di Turing, cioè ad un sistema finito di assiomi (ma sempre nell'ipotesi di coerenza), ma tale che non può arrivare a comprendere assolutamente tutto, proprio perché, come in tutti i sistemi formali coerenti, contiene al suo (nostro...) interno delle affermazioni vere ma indecidibili. Questo non esclude la possibilità di un computer con le nostre stesse capacità. E forse/purtroppo anche di maggiori...


Home