Teoremi di incompletezza di Gödel

Da TecnoLogica.

(Differenze fra le revisioni)
 
(10 revisioni intermedie non mostrate.)
Riga 1: Riga 1:
 +
<bibimport/>
==Definizioni==
==Definizioni==
===Primo teorema di Gödel===
===Primo teorema di Gödel===
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]] completo non può dimostrare la propria [[completezza (sistemica)|completezza]].
+
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]].
==Descrizione==
==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 <math>\mathbb{N}_0</math> dei numeri naturali.<br/>
+
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 <math>\mathbb{N}_0</math> dei numeri naturali ai quali si applicano le operazioni di addizione e moltiplicazione.<br/>
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 [[regola di inferenza|regole di inferenza]] attraverso un linguaggio formale univoco: deve cioè essere un [[sistema#sistemi formali|sistema formale]].<br/>
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 [[regola di inferenza|regole di inferenza]] attraverso un linguaggio formale univoco: deve cioè essere un [[sistema#sistemi formali|sistema formale]].<br/>
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 falsi (''nonteoremi''); in altre parole non è in grado di dire se queste affermazioni sono vere o sono false;
+
*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 è [[completezza (sistemica)|completo]], cioè tale che tutte le affermazioni vere dell'aritmetica sono dei teoremi del sistema, esso non è in grado di dimostrarlo; in altre parole, per poter dimostrare la completezza di un sistema occorre costruirne un altro (almeno complesso quanto il primo) che possa farlo.
+
*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/>
 +
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
 +
 
 +
'''per ogni numero naturale ''a'', (0+''a'')=''a'''''
 +
 
 +
ovvero, in termini formali,
 +
 
 +
<math>\mathcal{8}a:(0+a)=a</math>
 +
 
 +
è indecidibile, perché non può essere derivata dagli assiomi di Peano, applicando le [[regola di inferenza|regole di inferenza]] dell'aritmetica, anche se è possibile dimostrare tutte le infinite proposizioni<ref>Questo particolare tipo di [[completezza (sistemica)|incompletezza]] è detto ω-incompletezza, perché ω in matematica indica il primo numero ordinale infinito.</ref><ref name=EGB>"><bib id="Hofstadter 1979">Douglas R. Hofstadter, ''Gödel, Escher, Bach. Un'eterna ghirlanda brillante'', Adelphi 1979.</bib></ref>:
 +
 
 +
<poem>
 +
(0+0)=0
 +
(0+1)=1
 +
(0+2)=2
 +
(0+3)=3
 +
...</poem>
 +
 
 +
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.<br/>
 +
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 è [[coerenza (sistemica)|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#sistemi formali|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.<br/>
 +
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==
 +
*[[Completezza (sistemica)]]
 +
*[[Indecidibilità]]
 +
*[[Logica]]
 +
*[[Sistema]]
 +
==Note==
 +
<references/>
 +
[[Categoria:Epistemologia]]
{{Footer}}
{{Footer}}

Versione attuale delle 05:55, 11 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 LaTeX: \mathbb{N}_0 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,

LaTeX: \mathcal{8}a:(0+a)=a

è 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:

  1. utilizzare un sistema esterno che inglobi l'aritmetica e sia in grado di dimostrarne la coerenza;
  2. utilizzare l'aritmetica stessa, che in questo caso si autodimostrerebbe;
  3. 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

  1. Questo particolare tipo di incompletezza è detto ω-incompletezza, perché ω in matematica indica il primo numero ordinale infinito.
  2. ">[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
La consultazione di TecnoLogica è preordinata alla lettura delle avvertenze

Ogni contributore è responsabile dei propri inserimenti.
Il progetto è opera di Luca Buoninconti © 2011-2024.

Strumenti personali