Teoremi di incompletezza di Gödel
Da TecnoLogica.
| Riga 4: | Riga 4: | ||
Tutte le assiomatizzazioni [[coerenza (sistemica)|coerenti]] dell'aritmetica contengono proposizioni [[indecidibilità|indecidibili]]. | Tutte le assiomatizzazioni [[coerenza (sistemica)|coerenti]] dell'aritmetica contengono proposizioni [[indecidibilità|indecidibili]]. | ||
===Secondo teorema di Gödel=== | ===Secondo teorema di Gödel=== | ||
| - | Un [[sistema#sistemi formali|sistema formale]] | + | Un [[sistema#sistemi formali|sistema formale]] coerente non può dimostrare la propria [[coerenza (sistemica)|coerenza]]. |
===Sinonimi=== | ===Sinonimi=== | ||
Teoremi limitativi della [[logica]]. | Teoremi limitativi della [[logica]]. | ||
| Riga 12: | Riga 12: | ||
Questi teoremi affermano che: | Questi teoremi affermano che: | ||
*il modello di aritmetica contiene necessariamente delle proposizioni [[indecidibilità|indecidibili]], e cioè delle affermazioni sui numeri naturali che il sistema non è in grado di classificare né come vere (''teoremi'') né come false (''nonteoremi''); | *il modello di aritmetica contiene necessariamente delle proposizioni [[indecidibilità|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 è [[ | + | *se il modello è [[coerente (sistemica)|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.<br/> | Questi teoremi sono detti ''limitativi della logica'' perché contravvengono a due principi che sembrano appartenere al senso comune.<br/> | ||
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à [[indecidibilità|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 | 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à [[indecidibilità|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 | ||
| Riga 34: | Riga 34: | ||
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. | 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. | ||
| - | Per comprendere l'importanza del secondo teorema, occorre invece fare un altro gruppo di riflessioni. Tutti i ragionamenti che vengono condotti nelle [[scienza|scienze]] sono di tipo [[logica|logico]] e matematico. Ma la matematica (di cui l'aritmetica è un sottoinsieme) è un sistema [[coerenza (sistemica)|coerente]]? Non svilupperà mai teoremi in contraddizione tra loro? Anche se si può riporre la propria ''fiducia'' nell'aritmetica, per affermarne che essa è [[coerenza (sistemica)|consistente]] bisogna dimostrarlo, e per fare questo occorre un sistema formale. | + | Per comprendere l'importanza del secondo teorema, occorre invece fare un altro gruppo di riflessioni. Tutti i ragionamenti che vengono condotti nelle [[scienza|scienze]] sono di tipo [[logica|logico]] e matematico. Ma la matematica (di cui l'aritmetica è un sottoinsieme) è un sistema [[coerenza (sistemica)|coerente]]? Non svilupperà mai teoremi in contraddizione tra loro? Anche se si può riporre la propria ''fiducia'' nell'aritmetica, per affermarne che essa è [[coerenza (sistemica)|consistente]] bisogna dimostrarlo, e per fare questo occorre un sistema formale. Ma l'aritmetica è di per sé uno dei sistemi formali più ''potenti'' che esistono, per cui può sorgere la domanda: l'aritmetica riesce ad autodimostrare la sua [[coerenza (sistemica)|coerenza]]? Il secondo teorema di Gödel afferma di no, e per farlo occorre trovare un secondo sistema complesso quanto il primo. E per dimostrare la coerenza del secondo ne occorrerebbe un terzo, e così via. |
==Voci correlate== | ==Voci correlate== | ||
*[[Completezza (sistemica)]] | *[[Completezza (sistemica)]] | ||
Versione delle 20:41, 10 ott 2011
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.
Per comprendere l'importanza del secondo teorema, occorre invece fare un altro gruppo di riflessioni. Tutti i ragionamenti che vengono condotti nelle scienze sono di tipo logico e matematico. Ma la matematica (di cui l'aritmetica è un sottoinsieme) è un sistema coerente? Non svilupperà mai teoremi in contraddizione tra loro? Anche se si può riporre la propria fiducia nell'aritmetica, per affermarne che essa è consistente bisogna dimostrarlo, e per fare questo occorre un sistema formale. Ma l'aritmetica è di per sé uno dei sistemi formali più potenti che esistono, per cui può sorgere la domanda: l'aritmetica riesce ad autodimostrare la sua coerenza? Il secondo teorema di Gödel afferma di no, e per farlo occorre trovare un secondo sistema complesso quanto il primo. E per dimostrare la coerenza del secondo ne occorrerebbe un terzo, e così via.
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
|
