Teoremi di incompletezza di Gödel
Da TecnoLogica.
Definizioni
Primo teorema di Gödel
Tutte le assiomatizzazioni coerenti dell'aritmetica contengono proposizioni indecidibili.
Secondo teorema di Gödel
Un sistema formale coerente non può dimostrare la propria coerenza.
Sinonimi
Teoremi limitativi della logica.
Descrizione
I due teoremi di incompletezza sono stati elaborati dal matematico austriaco Kurt Gödel allo scopo di dimostrare due caratteristiche di ogni sistema che sia sufficientemente potente da esprimere in sé i concetti di aritmetica, e cioè di quella parte della matematica formata dall'insieme dei numeri naturali ai quali si applicano le operazioni di addizione e moltiplicazione.
Per sufficientemente potente si intende che il sistema in questione deve essere in grado di esprimere gli assiomi di Peano, che stanno alla base dell'aritmetica, e le relative regole di inferenza attraverso un linguaggio formale univoco: deve cioè essere un sistema formale.
Questi teoremi affermano che:
- il modello di aritmetica contiene necessariamente delle proposizioni indecidibili, e cioè delle affermazioni sui numeri naturali che il sistema non è in grado di classificare né come vere (teoremi) né come false (nonteoremi);
- se il modello è completo, da non generare due teoremi in contraddizione tra loro, esso non è in grado di dimostrarlo; in altre parole, per poter dimostrare la coerenza di un sistema occorre costruirne un altro (almeno complesso quanto il primo) che possa farlo.
Questi teoremi sono detti limitativi della logica perché contravvengono a due principi che sembrano appartenere al senso comune.
E' infatti abbastanza plausibile credere che, se è possibile affermare qualcosa di vero sui numeri naturali, allora questa affermazione può diventare un teorema dell'aritmetica; se esso non esiste ancora, allora deve necessariamente esistere un modo - non ancora scoperto - per dimostrarlo. Il primo teorema di Gödel invece dimostra il contrario, e cioè che alcune affermazioni vere sono in realtà indecidibili, cioè non sono teoremi di quel sistema, né tantomeno lo sono le loro negazioni. Si potrebbe quindi pensare che il sistema adottato sia troppo poco potente, ma anche una sua versione più efficiente conterrebbe sempre (altre) proposizioni indecidibili. Ecco un esempio: la proposizione
per ogni numero naturale a, (0+a)=a
ovvero, in termini formali,
è indecidibile, perché non può essere derivata dagli assiomi di Peano, applicando le regole di inferenza dell'aritmetica, anche se è possibile dimostrare tutte le infinite proposizioni[1][2]:
(0+0)=0
(0+1)=1
(0+2)=2
(0+3)=3
...
Erroneamente si potrebbe ritenere possibile aggiungere la proposizione agli assiomi del sistema, ma questo nuovo "super-sistema" conterrebbe altre affermazioni indecidibili, perché è sempre possibile applicare la dimostrazione del primo teorema di incompletezza.
Nonostante la dimostrazione sia stata costruita per un'assiomatizzazione dell'aritmetica, è stato successivamente dimostrato che il teorema è applicabile a qualsiasi sistema, sia formale che nonformale.
Qualsiasi formalizzazione dell'aritmetica è, per il primo teorema, sempre incompleta. Ma almeno è possibile affermare che essa è coerente? Oppure è possibile pensare che un giorno verrà scoperto un teorema che è in contraddizione con un altro? Per il senso comune, l'aritmetica - e la matematica in generale - non può essere incoerente, ma occorre dimostrarlo. Per fare ciò occorre un sistema formale in grado di interpretare in sé l'aritmetica: ma quale sistema è in grado di farlo? Le risposte sono tre:
- utilizzare un sistema esterno che inglobi l'aritmetica e sia in grado di dimostrarne la coerenza;
- utilizzare l'aritmetica stessa, che in questo caso si autodimostrerebbe;
- utilizzare un sistema esterno molto semplice basato su pochi e chiari principi della logica.
La prima eventualità è percorribile, ma il sistema che dimostra l'aritmetica sarebbe complesso almeno quanto l'aritmetica stessa: perché sia valida la dimostrazione, bisognerebbe poi dimostrare la sua coerenza.
La seconda e la terza eventualità non sono percorribili: lo dimostra appunto il secondo teorema di Gödel: un sistema formale non è in grado di dimostrare la sua coerenza, e per farlo bisogna ricorrere ad un sistema esterno complesso almeno quanto il primo.
Voci correlate
Note
- ↑ Questo particolare tipo di incompletezza è detto ω-incompletezza, perché ω in matematica indica il primo numero ordinale infinito.
- ↑ ">[Douglas R. Hofstadter, ''Gödel, Escher, Bach. Un'eterna ghirlanda brillante'', Adelphi 1979.]Douglas R. Hofstadter (1979).
Gödel, Escher, Bach. Un'eterna ghirlanda brillante. Adelphi. Show in Bibliography
|
