|
admin
Webmaster
Regione: Italy
Prov.: Pisa
Città: Capannoli
24834 Messaggi |
 Inserito il - 14/06/2008 : 11:47:54
|
Il teorema di Gödel
di Dario Palladino
Dipartimento di Filosofia, Università di Genova
Il teorema di incompletezza di Gödel del 1931 è ritenuto il più importante risultato della logica del ventesimo secolo. In realtà, come vedremo, i teoremi di incompletezza di Gödel sono due, e a essi abitualmente ci si riferisce come al primo e al secondo teorema di incompletezza (e, quando si parla del teorema di Gödel, ci si riferisce al primo dei due). Si tratta di risultati così significativi che, ancora oggi, a più di settant'anni dalla loro dimostrazione, sono al centro dell'attenzione di studiosi di varie discipline.
Il teorema di Gödel si riferisce a un sistema formale per l'aritmetica, ossia a un sistema assiomatico per la teoria dei numeri naturali in cui sono esplicitati, accanto ai concetti primitivi e agli assiomi, gli strumenti logici con i quali si conducono le dimostrazioni. Le ricerche logiche, infatti, hanno consentito di elaborare dei veri e propri calcoli logici mediante i quali è possibile formalizzare le dimostrazioni matematiche e associare alle usuali teorie matematiche la loro versione formale, in cui sono esplicitati anche i procedimenti deduttivi, e quindi trasformarle in sistemi assiomatici formalizzati.
La formalizzazione di una teoria matematica non ha lo scopo di sostituire le usuali dimostrazioni condotte nella pratica matematica, ma consente di fornire una definizione esplicita, induttivamente controllabile, di cosa è un “teorema di una teoria e, quindi, di studiare problemi non affrontabili se non si è esplicitato l'apparato deduttivo della teoria stessa. In altri termini, la formalizzazione consente di “caratterizzare” l'insieme dei teoremi di una teoria, e permette così di dimostrare proposizioni che fanno riferimento alla teoria nella sua totalità. E il teorema di Gödel rientra in questa categoria di risultati. Tra l'altro, in base a un altro fondamentale risultato di Gödel del 1930, il teorema di completezza della logica dei predicati, in ogni teoria formalizzata al primo ordine, sono teoremi tutte (e sole) le conseguenze logiche degli assiomi. Va inoltre tenuto presente che, come è noto, le teorie formali sono suscettibili di svariate interpretazioni: hanno, come si usa dire, molteplici modelli.
Indichiamo con AF un sistema formale per l'aritmetica del primo ordine (ad esempio quello che formalizza l'aritmetica di Peano): esso ha un'interpretazione standard in base alla quale gli assiomi sono veri nell'insieme N dei numeri naturali. L'idea che ha guidato Gödel per ottenere il suo teorema deriva dalla celebre “antinomia del mentitore”, che si può formulare come segue: una persona dice: "“Io sto mentendo". Se la persona mente, allora dice il vero. Se dice il vero, allora mente.
Ebbene, la strategia di Gödel è stata quella di riformulare all'interno di un sistema formale quale AF l'antinomia del mentitore con riferimento alla dimostrabilità (e indimostrabilità) anziché alla verità (e falsità). Il primo teorema di incompletezza si può così formulare: se AF è coerente (ossia non si può dimostrare in AF una fomula e la sua negazione), allora AF è sintatticamente incompleto, ossia esiste una formula chiusa G tale che in AF non è dimostrabile né G né la negazione di G.
La formula chiusa G individuata da Gödel è tale che la sua interpretazione standard risulta: "“G non è dimostrabile in AF"”. Si può allora ragionare a livello intuitivo come segue. a) Se G fosse dimostrabile in AF, allora sarebbe vera nell'interpretazione standard, e quindi sarebbe vero che G non è dimostrabile in AF. Ne segue che G non è dimostrabile in AF. b) Se non G fosse dimostrabile in AF, allora nell'interpretazione standard non G sarebbe vera, e pertanto sarebbe vero che G è dimostrabile in AF, in contraddizione con la coerenza di AF. Quindi non G non è dimostrabile in AF.
Il problema principale risolto da Gödel è stato quello di costruire la formula chiusa G con la proprietà richiesta, ossia che affermi, nell'interpretazione standard, la propria indimostrabilità. Le formule di AF sono stringhe di simboli e, nell'interpretazione stadard, divengono proposizioni relative ai numeri naturali. Per costruire G occorre che la proprietà di "“essere dimostrabile"” di una formula possa essere espressa come una proprietà numerica. Questo fondamentale passo è stato realizzato da Gödel mediante il procedimento detto di “aritmetizzazione della sintassi che consente, in sostanza, di esprimere proprietà relative al sistema formale mediante formule di AF. In estrema sintesi, si associa univocamente a ogni formula un numero, e quindi alle proprietà delle formule si fanno corrispondere proprietà numeriche. Dato che AF è un sistema formale per l'aritmetica, in esso si formalizzano le proprietà dei numeri e, quindi, oltre alle usuali proprietà aritmetiche (quali ad esempio "“essere pari”, "“essere primo", ”...) si formalizzano quelle che "“traducono"” le proprietà delle formule (quale appunto "“essere dimostrabile"”). In tal modo si può costruire la formula G la quale "“corrisponde"” alla sua stessa indimostrabilità.
Il secondo teorema di incompletezza si può formulare come segue: Se AF è coerente, allora la sua coerenza non può essere dimostrata in AF.
Illustriamo schematicamente alcune delle principali conseguenze dei teoremi di Gödel.
1) La conseguenza più immediata del primo teorema di incompletezza di Gödel è che vi sono “verità aritmetiche” non dimostrabili in AF. In una qualsiasi interpretazione, e in particolare in quella standard, è vera G oppure è vera non G, ed entrambe non sono dimostrabili. In entrambi i casi vi è una formula vera non dimostrabile in AF. Nell'interpretazione standard, tra l'altro, è vera G in quanto, come si è detto, l'interpretazione standard di G è “G non è dimostrabile”, che è vera proprio per quanto dimostrato da Gödel. Vi sono quindi proprietà vere non dimostrabili, e quindi il sistema formale AF non è in grado di giustificare tutte le verità aritmetiche”.
2) Quanto osservato in (1) non mette in luce un difetto limitato al sistema formale AF. In generale, infatti, se una verità” non è dimostrabile, appare del tutto naturale assumerla come nuovo assioma. Ebbene, in questo caso, per il sistema formale così ampliato si può ripetere inalterata la dimostrazione di Gödel, ottenendo una nuova “verità aritmetica” non dimostrabile. In altri termini, il teorema di Gödel non stabilisce l'incompletezza sintattica del solo AF, ma anche di un qualsiasi sistema formale che estende AF. In realtà le cose andrebbero ulteriormente precisate, nel senso che il teorema di Gödel si estende a tutti i sistemi formali assiomatizzabili che estendono AF, ossia tali che è controllabile algoritmicamente il loro sistema di assiomi. D'altra parte, un sistema non assiomatizzabile non è “sotto controllo” (non possiamo neppure decidere quali sono i suoi assiomi) e, quindi, è praticamente inutile a fini matematici. È in questo senso che si ha la vera e propria limitazione dei sistemi formali: non è possibile individuare alcun sistema formale assiomatizzabile in grado di giustificare tutte le “verità aritmetiche. Vi è quindi una scollatura insanabile fra ciò che è dimostrabile e ciò che è vero nell'aritmetica (e in quasi tutte le altre principali teorie matematiche). Si è tuttavia dimostrato, ad esempio, che sono sintatticamente complete teorie del primo ordine che formalizzano parti limitate dell'aritmetica (ad esempio l'aritmetica dell'addizione, senza la moltiplicazione) e che lo è la (versione formale della) geometria euclidea (teorema di Tarski).
3) Dal fatto che G non è dimostrabile in AF segue, per il teorema di completezza della logica dei predicati del primo ordine, che G non è conseguenza logica di AF. Ciò significa che esiste un'interpretazione del linguaggio di AF che rende veri gli assiomi di AF e falsa G. Tale modello di AF non può essere isomorfo a N (poiché in N, come si è prima osservato, è vera G e in modelli isomorfi sono vere le stesse formule). Pertanto AF non è categorico, ossia ha modelli non isomorfi tra loro. Tale risultato, che non vale solo per AF ma anche per le sue estensioni, indica che non è possibile caratterizzare con un sistema formale del primo ordine la struttura dell'insieme N dei numeri naturali.
4) Il secondo teorema di incompletezza di Gödel ha segnato la fine del “periodo d'oro” della ricerca sui fondamenti della matematica e, in particolare, del programma di Hilbert”. All'inizio del secolo scorso ha assunto particolare rilevanza il problema della non contraddittorietà delle teorie matematiche. Si erano infatti trovate delle contraddizioni (o antinomie) che minavano alla base la teoria degli insiemi di Cantor e furono proposte varie assiomatizzazioni in grado di evitarle. Il passaggio all'assiomatica formalizzata è stato motivato proprio dall'esigenza di avere un “controllo” sui teoremi di una teoria in grado di consentire la dimostrazione della sua coerenza. E non è un caso che i calcoli logici, come ancora oggi vengono insegnati nei corsi universari, sono stati elaborati nell'ambito delle ricerche condotte dal matematico David Hilbert per ottenere la prova della non contraddittorietà delle teorie matematiche. Il primo obiettivo che Hilbert si era proposto era dimostrare la non contraddittorietà della più semplice delle teorie matematiche, ossia l'aritmetica (per poi estenderla alle teorie più complesse quali l'analisi, la geometria e la teoria degli insiemi). Ebbene, il secondo teorema di incompletezza di Gödel ha sancito proprio l'impossibilità di raggiungere tale obiettivo: la coerenza di un sistema formale quale AF non può essere ottenuta sfruttando tutti gli strumenti contenuti in AF stesso (e quindi, a maggior ragione, con gli strumenti più deboli ai quali Hilbert intendeva far ricorso). In parole più semplici: l'aritmetica non può garantire la sua coerenza.
5) Se da un lato il teorema di Gödel ha sancito la fine del programma fondazionale di Hilbert, dall'altro ha segnato l'inizio di nuove ricerche. I risultati limitativi, assai frequenti in matematica (ad esempio: non si può esprimere il rapporto fra diagonale e lato di un quadrato come rapporto fra numeri naturali, non si può costruire con riga e compasso il quadrato equivalente ad un cerchio ecc.), per essere ottenuti, richiedono lo studio di nuovi ambiti di ricerca che consentono una crescita delle conoscenze. I teoremi di ödel sono stati all'origine di importanti ricerche logiche e, come si è accennato, hanno aperto nuovi settori di indagine, prima fra tutti la teoria della computabilità che, oltre a costituire il quadro teorico in cui si svolgono le recenti discipline informatiche, ha applicazioni in molteplici settori quali le recenti scienze cognitive, la linguistica computazionale, la “filosofia della mente”.
Per concludere, il teorema di incompletezza (sintattica) di Gödel può ulteriormente essere rafforzato in quanto è stato dimostrato successivemente che sistemi come AF sono “indecidibili”, ossia non si può stabilire mediante un algoritmo quali formule del suo linguaggio sono teoremi e quali non lo sono. Il fatto che i teoremi sono controllabili induttivamente consente di “generarli uno dopo l'altro, ma non consente, in generale, di stabilire se una data formula F è o non è un teorema: se F viene “generata” è un teorema, ma, se F non è stata ancora ottenuta, non si può sapere se verrà generata in futuro (se è un teorema) o se non sarà mai generata (se non è un teorema). Ebbene, le ricerche in teoria della computabilità hanno consentito di “dimostrare” che il problema di decidere se F è o non è un teorema di AF non può essere risolto algoritmicamente.
|
|
![[AmadeuX BiblioForum]](https://www.amadeux.it/forum/immagini/amadeuxcomm1.jpg "[AmadeuX BiblioForum]")
Il teorema di Gödel
