Utente:LucaMoro/prova1

In logica matematica, i teoremi di incompletezza di Gödel sono due famosi teoremi dimostrati da Kurt Gödel nel 1931. Con qualche semplificazione, il primo teorema afferma che:

In ogni formalizzazione coerente della matematica che sia sufficientemente potente da poter assiomatizzare i numeri naturali -- vale a dire, sufficientemente potente da definire l'insieme delle operazioni che portano a definire i numeri naturali -- è possibile costruire una proposizione vera (!) che non può essere né provata né refutata all'interno dello stesso sistema.

Questo teorema esprime uno dei più discussi limiti della matematica, e uno dei più frequentemente fraintesi. È un teorema proprio della logica formale, e in quanto tale può prestarsi facilmente a interpretazioni erronee. Ci sono diversi enunciati apparentemente simili al primo teorema di incompletezza di Gödel, ma che non sono in realtà veri. Questi saranno presentati successivamente nella sezione Fraintendimenti sul teorema di incompletezza di Gödel.

Il secondo teorema di incompletezza di Gödel, che si dimostra formalizzando una parte della dimostrazione del primo teorema all'interno del sistema stesso, afferma che:

Nessun sistema coerente può essere utilizzato per dimostrare la sua stessa coerenza.

Questo risultato ebbe effetti devastanti in quell'approccio filosofico alla matematica noto come programma di Hilbert. David Hilbert riteneva che la coerenza di sistemi formali complessi, come ad esempio quello dell'analisi matematica sul campo dei reali, poteva essere dimostrata scomponendo il sistema in sistemi più semplici. In questo modo, il problema della coerenza di tutta la matematica si sarebbe potuto ricondurre alla coerenza dell'aritmetica elementare. Il secondo teorema di incompletezza di Gödel mostra che, dato che neanche un sistema particolarmente semplice come quello dell'aritmetica elementare può essere utilizzato per provare la sua stessa coerenza, così, a maggior ragione, esso non può essere utilizzato per dimostrare la coerenza di sistemi più potenti.

I teoremi di Gödel sono teoremi di logica del primo ordine, e devono essere collocati in questo contesto. Nella logica formale, tanto gli enunciati matematici quanto le dimostrazioni sono entrambe scritte in un linguaggio simbolico, dove è possibile verificare meccanicamente la validità delle dimostrazioni, e non ci possono essere dubbi sul fatto che un teorema sia conseguenza degli assiomi inizialmente elencati. In teoria, qualsiasi dimostrazione può essere verificata da un computer, e in fatti esistono programmi fatti per controllare la validità delle dimostrazioni o per cercare nuove dimostrazioni (sono chiamati dimostratori automatici dei teoremi).

Per affrontare questo processo, bisogna conoscere e definire gli assiomi di partenza. Ad esempio si può partire da un insieme finito di assiomi, come nella geometria euclidea, oppure, con maggiore generalità, si può consentire che esista un insieme infinito di assiomi. In questo caso, però, deve essere possibile controllare meccanicamente se un qualsiasi enunciato è un assioma di quell'insieme oppure no (si parla in questo caso di schema di assiomi). In informatica si direbbe che esiste un insieme ricorsivo di assiomi. Anche se può sembrare strano immaginare un elenco infinito di assiomi, questo è proprio ciò che si usa nella assiomatizzazione dei numeri naturali: gli assiomi di Peano: il principio di induzione, infatti non è altro che uno schema di assiomi - esso dice che se zero ha una certa proprietà e il successore di qualsiasi numero naturale ha quella proprietà, allora tutti i numeri naturali hanno quella proprietà -. Dato che la proprietà considerata non viene specificata, l'unico modo per dire, nel linguaggio della logica del primo ordine, che ciò vale per tutte le proprietà è considerare un numero infinito di assiomi.

Il primo teorema di incompletezza di Gödel dimostra che qualsiasi sistema che permette di definire i numeri naturali è necessariamente incompleto: esso contiene affermazioni di cui non si può dimostrare né la verità né la falsità.

Il fatto che possano esistere sistemi incompleti non è una scoperta particolarmente sorprendente. Ad esempio, se si elimina il postulato delle parallele dalla geometria euclidea, si ottiene un sistema incompleto (nel senso che il sistema non contiene tutte le proposizioni vere). Un sistema incompleto può semplicemente significare che esso non include tutti gli assiomi necessari.

Ciò che Gödel ha mostrato è che, in molti casi, come nella teoria dei numeri o nell'analisi matematica, non è mai possibile giungere a definire la lista completa degli assiomi. Ogni volta che si aggiunge un enunciato all'insieme degli assiomi, ci sarà sempre un altro enunciato non incluso.

Si possono sempre aggiungere infiniti assiomi; ad esempio, si possono aggiungere tutti gli enunciati veri sui numeri naturali alla lista degli assiomi, ma tale lista non è un insieme ricorsivo. Se si prende un qualsiasi enunciato casuale, non sarà possibile stabilire se esso è o non è un assioma del sistema. Pertanto data una qualsiasi dimostrazione, in generale, non sarà possibile verificarne la correttezza.

Il teorema di Gödel ha un'altra interpretazione esprimibile nel contesto informatico. Nella logica del primo ordine tutti i teoremi sono ricorsivamente enumerabili: ciò significa che è possibile scrivere un algoritmo che possa generare, prima o poi, ogni dimostrazione valida. Ci si può chiedere se questi teoremi soddisfino la proprietà più restrittiva di essere anche ricorsivi. È possibile scrivere un programma per computer in grado di determinare con certezza se una certa affermazione è vera o falsa? Il teorema di Gödel dice che ciò, in generale, non è possibile.

Molti studiosi di logica sostengono che i teoremi di incompletezza di Gödel abbiano definitivamente affossato il programma di David Hilbert volto a costruire un formalismo matematico universale. L'idea generalmente condivisa è che nel secondo teorema si trovi la risposta definitiva che ha dato il colpo di grazia al programma di Hilbert. Comunque taluni pensano che tale risposta si trovi nel primo teorema, e altri ritengono che nessuno dei due conduca a ciò.

L'esistenza di un enunciato indecidibile all'interno di un sistema formale non è un fatto di per sé stesso particolarmente sorprendente.

Nel successivo lavoro congiunto di Gödel e Paul Cohen si trovano esempi concreti di enunciati indecidibili (enunciati che non possono essere né provati né refutati): sia l'assioma della scelta che l'ipotesi del continuo sono indecidibili nella assiomatizzazione tradizionale della teoria degli insiemi. Questi risultati non si basano sul teorema di incompletezza.

Nel 1936, Alan Turing ha dimostrato che il problema dell'arresto— se cioè una Macchina di Turing si arresta eseguendo un certo programma —è indecidibile. Questo risultato fu successivamente generalizzato nel campo delle funzioni ricorsive con il teorema di Rice che mostra come tutti i problemi non banali di decisione sono indecidibili in un sistema completo alla Turing.

Nel 1973 si è dimostrato che il problema di Whitehead della teoria dei gruppi è indecidibile nel sistema della teoria degli insiemi. Nel 1977, Kirby, Paris e Harrington dimostrarono che un enunciato della combinatorica, una variazione del teorema di Ramsey, è indecidibile nella assiomatizzazione dell'aritmetica data dagli assiomi di Peano ma che può essere dimostrato nel sistema più ampio della teoria degli insiemi. Anche il teorema di Kruskal, che trova applicazioni in informatica, è indecidibile a partire dagli assiomi di Peano, ma può essere dimostrato in teoria degli insiemi. Il teorema di Goodstein propone un'affermazione relativamente semplice sui numeri naturali che è indecidibile nell'aritmetica di Peano.

Gregory Chaitin ha formulato enunciati indecidibili nella teoria algoritmica dell'informazione e ha di fatto dimostrato un suo teorema di incompletezza valido in questo settore.

Uno dei primi problemi sospettati di essere indecidibili fu il [problema della parola per i gruppi]], proposto da Max Dehn nel 1911, secondo cui esiste un gruppo finitamente generato che non possiede nessun algoritmo in grado di stabilire se due parole sono equivalenti. Solo nel 1952 si è dimostrata l'indecidibilità di questo problema.

L'ampia discussione suscitata dal primo teorema di incompletezza di Gödel ha anche prodotto numerosi fraintendimenti. In questa sezione vengono chiarificate le più comuni interpretazioni erronee:

1. Il teorema non implica che ogni sistema di assiomi abbastanza interessante sia incompleto. Ad esempio la geometria euclidea può essere assiomatizzata in modo da essere un sistema completo. (Di fatti, gli assiomi originali di Euclide si avvicinano molto all'essere una assiomatizzazione completa. Gli assiomi mancanti esprimono proprietà talmente ovvie che se ne è notata la mancanza solamente nel momento in cui è sorta l'esigenza di scrivere dimostrazioni formali.)
2. Il teorema si applica solamente a quei sistemi che consentono di definire i numeri naturali come un insieme. Non è sufficiente che il sistema contenga i numeri naturali. È anche necessario che, utilizzando gli assiomi del sistema e la logica del primo ordine, si possa esprimere il concetto "${\displaystyle x}$ è un numero naturale". Esistono numerosi sistemi che contengono i numeri naturali e che sono completi. Ad esempio sia i numeri reali che i numeri complessi hanno assiomatizzazioni complete.

Le conseguenze dell'incompletezza influenzano la filosofia della matematica, e in particolare alcune sue scuole di pensiero, come il formalismo, che basa la definizione dei suoi principi sulla logica formale. Il primo teorema può essere parafrasato dicendo che "non è possibile costruire un sistema assiomatico omnicomprensivo che sia allo stesso tempo in grado di provare tutte le verità matematiche, e nessuna falsità."

D'altro canto, da un punto di vista strettamente formalista, questa parafrasi dovrebbe essere considerata priva di senso, perché presuppone che la "verità" e la "falsità" matematiche siano concetti ben definiti in senso assoluto, e non concetti relativi a ciascun specifico sistema formale.

La seguente riformulazione del secondo teorema è ancor più sconcertante per chi si occupa dei fondamenti della matematica:

Se un sistema assiomatico può dimostrare la sua stessa coerenza, allora esso deve essere incoerente.

Pertanto, per poter stabilire la coerenza di un sistema S, è necessario utilizzare un altro sistema T. Ma una dimostrazione in T non è del tutto convincente a meno che la coerenza di T non sia già stata stabilita senza usare il sistema S. Ad esempio, la coerenza degli assiomi di Peano per i numeri naturali può essere dimostrata nella teoria degli insiemi, ma non nella sola teoria dei numeri naturali. Ciò fornisce una risposta negativa al problema numero 2 del famoso elenco di David Hilbert sulle più importanti questioni aperte della matematica (noto come elenco dei Problemi di Hilbert).

In linea di principio i teoremi di Gödel lasciano ancora qualche speranza: potrebbe essere possibile creare un algoritmo generale che determina, per un dato enunciato, se esso sia indecidibile oppure no, permettendo in questo modo ai matematici di evitare del tutto le proposizioni indecidibili. Comunque, la risposta negativa data all'entscheidungsproblem mostra che tale algoritmo non può esistere.

Alcuni studiosi ritengono che un enunciato, che non può essere dimostrato all'interno di un sistema deduttivo, può essere ben dimostrabile con l'uso di un metalinguaggio. E che ciò che non può essere dimostrato in quel metalinguaggio può probabilmente essere dimostrato tramite un meta-metalinguaggio. Questo processo, in teoria, può essere riprodotto ad infinitum in modo ricorsivo. Se ci si richiama a una specie di super Teoria dei Tipi con un assioma di Riducibilità -- che con un procedimento induttivo si estende all'intero universo stratificato dei linguaggi -- sarebbe possibile, di volta in volta, aggirare l'ostacolo dell'incompletezza.

Occorre notare che i teoremi di Gödel sono applicabili solamente a quei sistemi assiomatici sufficientemente potenti.

"Sufficientemente potenti" vuol dire che la teoria contiene un numero sufficiente di regole aritmetiche per consentire la costruzione della codifica necessaria alla dimostrazione del primo teorema di incompletezza. In pratica, tutto ciò che si richiede sono alcune regole elementari riguardanti l'addizione e la moltiplicazione, come ad esempio avviene nella formalizzazione nella aritmetica Q di Robinson. Esistono sistemi assiomatici ancora più deboli che sono coerenti e completi, ad esempio l'aritmetica di Presburger, in cui si può dimostrare qualsiasi enunciato vero del primo ordine che riguarda la sola addizione.

Il sistema assiomatico può consistere di un numero infinito di assiomi (come nell'aritmetica del primo ordine di Peano), ma, per poter applicare il teorema di Gödel, deve esistere un algoritmo che sia effettivamente in grado di verificare la correttezza delle dimostrazioni. Ad esempio, l'insieme di tutti gli enunciati del primo ordine che sono veri nel modello dei numeri naturali forma un sistema è completo; Qui, il teorema di Gödel non si può applicare perché non esiste una procedura efficace in grado di decidere se un certo enunciato sia o non sia un assioma. Infatti, questo fatto è proprio una conseguenza del primo teorema di incompletezza di Gödel.

Un altro esempio di una teoria specificata in modo tale che ad essa non si possa applicare il primo teorema di Gödel può essere costruito nel seguente modo. Si ordinano tutti i possibili enunciati sui numeri naturali prima per lunghezza, e poi seguendo l'ordinamento lessicografico. Si parte da un sistema assiomatico inizialmente equivalente al sistema degli assiomi di Peano. Si scorre poi la lista degli enunciati uno ad uno e, se non si può dimostrare la verità o la falsità dell'enunciato corrente sulla base degli assiomi correnti, lo si aggiunge al sistema. In questo modo si costruisce un sistema che è coerente e sufficientemente potente, ma non ricorsivamente enumerabile.

Gödel stesso dimostrò una versione dei precedenti teoremi che è tecnicamente leggermente più povera, mentre la prima dimostrazione dei teoremi nella forma qui presentata è stata fornita da J. Barkley Rosser nel 1936.

Fondamentalmente, la dimostrazione del primo teorema consiste nella costruzione, all'interno di un sistema assiomatico formale, di una certa affermazione p a cui si può dare la seguente interpretazione meta-matematica:

p = "Questa affermazione non può essere dimostrata"

In questa veste, essa può essere vista come una moderna variante del paradosso del mentitore. Diversamente dall'affermazione del mentitore, p non fa riferimento diretto a sé stessa; la precedente interpretazione può solamente essere formulata dall'esterno del sistema formale.

Se il sistema formale è coerente, la prova di Gödel mostra che p (e la sua negazione) non possono essere dimostrate nel sistema. Pertanto p è "vera" (p dice che non può essere dimostrata, e non può essere dimostrata) ma non può essere formalmente dimostrata nel sistema. Si noti che aggiungere p all'elenco degli assiomi non aiuterebbe a risolvere il problema: ci sarebbe un'altra, simile affermazione di Gödel costruibile nel il sistema allargato.

Secondo Roger Penrose questa (presunta) differenza tra "ciò che può meccanicamente essere dimostrato" e "ciò che può essere riconosciuto come vero dagli uomini" mostra che l'intelligenza umana non ha una natura algoritmica. Questa convinzione è sottoscritta anche da JR Lucas in Minds, Machines and Gödel.

Questa opinione non è generalmente condivisa perché, come ha sostenuto Marvin Minsky, l'intelligenza umana può commettere errori e può comprendere affermazioni che sono in realtà incoerenti o false. Ciò nonostante, Marvin Minsky ha raccontato che Kurt Gödel gli disse personalmente della sua convinzione nel fatto che gli esseri umani possiedono una modalità intuitiva, non solo computazionale, per arrivare alla verità e che quindi il suo teorema non pone limiti a ciò che può essere riconosciuto come vero dall'uomo.

L'opinione secondo cui il teorema mostrerebbe la capacità degli uomini di trascendere la logica formale può anche essere messa in questione nel seguente modo: non è possibile sapere se l'affermazione p è vera o no, perché non si sa, e non è possibile stabilirlo, se il sistema è coerente. Quindi, in pratica, non è possibile conoscere alcuna verità esterna al sistema. Tutto ciò che si può conoscere è la verità della seguente affermazione:

O p non è dimostrabile nel sistema, oppure il sistema non è coerente.

Questa affermazione può facilmente essere dimostrata all'interno del sistema. Infatti, tale dimostrazione sarà ora schematicamente delineata.

Il problema principale che deve essere affrontato per sviluppare l'idea di dimostrazione precedentemente formulata è il seguente: per costruire un enunciato p che sia equivalente a "p non può essere dimostrato", p deve in qualche modo contenere un riferimento a p, ovvero a sé stesso, il che potrebbe dare facilmente origine ad un processo infinito di autoreferenziamento. Il geniale stratagemma di Gödel, utilizzato successivamente anche da Alan Turing per risolvere il Entscheidungsproblem, è il seguente.

Per cominciare, ad ogni formula o enunciato che può essere formulato nel sistema è assegnato un numero univoco, chiamato il suo numero di Gödel. Ciò è fatto in modo che si possa facilmente effettuare una conversione meccanica tra le formule e i relativi numeri di Gödel, e viceversa. Dato che il sistema considerato è abbastanza potente da poter operare con i numeri, sarà ora possibile operare allo stesso modo anche con le formule.

Una formula F(x) che contiene una sola variabile libera x è chiamata forma dichiarativa. Quando a x si sostituisce uno specifico numero, la forma dichiarativa si trasforma in una enunciato, potenzialmente vero o falso, che può essere o non essere dimostrabile nel sistema. Le forme dichiarative non sono enunciati e quindi non possono essere dimostrate vere o false. Comunque, ogni forma dichiarativa F(x) ha un suo numero di Gödel che si può denotare con la scrittura G(F). La scelta della variabile libera utilizzata nell'espressione F(x) non è rilevante per l'assegnazione del numero di Gödel G(F).

A partire da una analisi attenta degli assiomi e delle regole del sistema, si può costruire una forma dichiarativa P(x) che traduce il seguente concetto: x è il numero di Gödel di un enunciato che può essere dimostrato nel sistema. Formalmente: P(x) può essere dimostrata se x è il numero di Gödel di un enunciato dimostrabile, e la sua negazione ~P(x) può essere dimostrata se non lo è.

(Anche se la precedente descrizione può essere ritenuta sufficiente a delineare lo schema della dimostrazione, essa è tecnicamente non del tutto accurata. Si veda l'articolo di Gödel per l'esposizione del problema e quello di Rosser per la sua risoluzione. La parola chiave è "omega-coerenza".)

A questo punto interviene l'idea risolutiva: chiamiamo auto-indimostrabile una formula che afferma meta-maticamente la propria non dimostrabilità. Applicando questa definizione, una forma dichiarativa F(x) è auto-indimostrabile se la forma F, applicata al suo stesso numero di Gödel, non è dimostrabile. Questo concetto può essere definito formalmente, dato che si può costruire una forma dichiarativa SU(z) la cui interpretazione dice che z è il numero di Gödel di una forma dichiarativa auto-indimostrabile. Formalmente, SU(z) è definita come: z = G(F) per qualche formula particolare F(x), e y è il numero di Gödel dell'enunciato F(G(F)), e ~P(y). A questo punto, l'enunciato cercato p, precedentemente introdotto può essere definito come:

p = SU(G(SU)).

Intuitivamente, quando ci si chiede se p è vero, ci si pone la domanda: "La proprietà di essere auto-indimostrabile di per sè stessa auto-indimostrabile?" Tutto ciò ricorda molto da vicino il paradosso del barbiere che racconta di quel barbiere che rade unicamente quelle persone che non si radono da sole: chi rade il barbiere?

Assumiamo ora che il nostro sistema assiomatico sia coerente.

Se p fosse dimostrabile, allora SU(G(SU)) sarebbe vero, e per la definizione di SU, z = G(SU) sarebbe il numero di Gödel di una forma proposizionale auto-indimostrabile. Pertanto SU sarebbe auto-indimostrabile, e ciò implica, per la stessa definizione di auto-indimostrabilità che SU(G(SU)) non è dimostrabile, ma questo è il nostro enunciato p: p non è dimostrabile. Questa contraddizione porta a concludere che p non può essere dimostrabile.

Se la negazione di p= SU(G(SU)) fosse dimostrabile, allora per la definizione di SU ciò significherebbe che z = G(SU) non è il numero di Gödel di una forma auto-indimostrabile, il che implica che SU non è auto-indimostrabile. Per la definizione di auto-indimostrabilità, si conclude che SU(G(SU)) è dimostrabile, e quindi p è dimostrabile. Ancora una volta si giunge a una contraddizione. Quest'ultima contraddizione implica che anche la negazione di p non può essere dimostrata.

Quindi l'enunciato p non può essere né dimostrato né confutato all'interno del nostro sistema.

Sia p l'enunciato indecidibile costruito prima, e si assuma che la coerenza del sistema sia dimostrabile all'interno del sistema stesso. Precedentemente si è mostrato che se il sistema è coerente, allora p non è dimostrabile. La dimostrazione di questa implicazione può essere formalizzata nel sistema stesso, e quindi l'affermazione "p non è dimostrabile", o "non P(p)" può essere dimostrata nel sistema.

Ma quest'ultima affermazione è equivalente allo stesso enunciato p (e questa equivalenza può essere dimostrata nel sistema), quindi p può essere dimostrato nel sistema. Questa contraddizione implica che il sistema deve essere incoerente.

• Coerenza logica
• Auto-referenza
• Logicismo
• Paradosso di Berry
• Paradosso di Richard
• Paradosso di Russell
• Menti, Macchine e Gödel
• Teroema di Löb

• Kurt Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198. Translated in van Heijenoort: From Frege to Gödel. Harvard University Press, 1971.
• J.R. Lucas: Minds, Machines and Gödel
• Kārlis Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
• Voce su "Kurt Gödel" in MacTutor History of Mathematics Archive
• Articoli e saggi del Prof. Piergiorgio Odifreddi: Il teorema di Gödel e l'I.A.
• Articoli e saggi del Prof. Piergiorgio Odifreddi: Metamorfosi di un teorema
• Articoli e saggi del Prof. Piergiorgio Odifreddi: Godel's mathematics of philosophy (pdf in inglese)
• Articoli e saggi del Prof. Piergiorgio Odifreddi: Gödel for children (pdf in inglese) (broken link)
• Versione in miniatura (per non addetti ai lavori) del teorema di incompletezza a cura di Mariano Tomatis
• Hilbert's second problem (English translation)

• Douglas Hofstadter, "Gödel, Escher, Bach: un'eterna ghirlanda brillante", Adelphi (ISBN 88-459-0755-4)
• E. Nagel, J.R. Newman, "La prova di Gödel", Universale Bollati Boringhieri (ISBN 88-339-0309-5)
• John L. Casti, Werner DePauli, "Gödel, l’eccentrica vita di un genio", Raffaello Cortina (ISBN 8870787117)
• P. Pasolini, "Il teorema di Gödel di fronte alla logica, alla cibernetica e all'assoluto" - Rivista Nuova Umanità n. 1, Ed. Città Nuova, Roma
• Italo Aimonetto, "Il fondamento del teorema di Gödel: da Peano a Frege e Russell" - Rivista Filosofia - Torino
• B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91
• Hao Wang: A Logical Journey: From Gödel to Philosophy Bradford Books (January 10, 1997) ISBN 0262231891

L'articolo sarà inserito in "Categoria:Logica matematica" (doppia parentesi quadra)