Amici della Scienza – Notizie & Scoperte

Kurt Gödel: i teoremi di incompletezza

In questo articolo Paul Davies spiega in modo semplice e originale, del tutto accessibile anche a chi non conosce la logica, il noto teorema di incompletezza formulato nel 1931 dal logico-matematico Kurt Gödel (1906-1978), illustrando i paradossi che crea e sottolineando la rilevanza e il peso che esso ebbe sui lavori logici successivi. Il teorema sarà destinato a rivestire un ruolo di primo piano a motivo delle sue influenze sul piano filosofico, fra cui spicca l’impossibilità di costruire un sistema assiomatico completo, poiché al suo interno esisteranno sempre proposizioni indecidibili.

Nonostante la sua superficiale plausibilità, l’interpretazione formalista della matematica ricevette un duro colpo nel 1931. In quegli anni il matematico e logico di Princeton Kurt Gödel dimostrò un teorema fondamentale secondo cui esistevano enunciati matematici di cui nessuna procedura sistematica poteva determinare la verità o la falsità. Questo teorema non lasciava vie d’uscita, perché forniva una dimostrazione irrefutabile che determinate cose, in matematica, sono realmente impossibili, persino in linea di principio. Il fatto che esistano proposizioni indecidibili in matematica provocò un grosso trauma perché sembrava minare gli stessi fondamenti logici della disciplina.

Kurt Godel
Kurt Godel

Il teorema di Gödel sorge da una costellazione di paradossi che circondano l’autoreferenzialità. Consideriamo, come semplice introduzione a questo argomento ingarbugliato, la sconcertante frase: «La presente proposizione è una bugia». Se la proposizione è vera, allora è falsa; e se è falsa, allora è vera. Questi paradossi dell’autoreferenzialità possono essere costruiti facilmente e sono profondamente interessanti; hanno confuso le persone per secoli. Una formulazione medioevale dello stesso dilemma è la seguente:

Socrate: «Ciò che Platone sta per dire è falso».

Platone: «Quello che Socrate ha appena detto è vero».

Il grande matematico e filosofo Bertrand Russell dimostrò che l’esistenza di tali paradossi colpisce al cuore la logica e mina qualunque tentativo diretto di costruire la matematica rigorosamente su un fondamento logico. Gödel adattò alla matematica queste difficoltà insite nel concetto di autoreferenzialità in modo brillante e insolito. Considerò la relazione fra la descrizione della matematica e la matematica stessa. Questa è abbastanza semplice da enunciare, ma richiede un’argomentazione lunga e molto intricata. Per farsi un’idea, si può immaginare di elencare le proposizioni matematiche etichettandole con 1,2,3… Combinare una sequenza di proposizioni in un teorema corrisponde dunque a combinare i numeri naturali che costituiscono le loro etichette. In questo modo le operazioni logiche sulla matematica possono essere fatte corrispondere alle proposizioni matematiche stesse. È questa l’essenza del carattere autoreferenziale della dimostrazione di Gödel. Identificando il soggetto con l’oggetto – proiettando la descrizione della matematica sulla matematica stessa – egli scoprì un paradossale circolo russelliano che conduceva direttamente all’inevitabilità di proposizioni indecidibili. John Barrow ha osservato di sfuggita che se una religione viene definita come un sistema di pensiero che richiede una fede in verità indimostrabili, allora la matematica è la sola religione che può dimostrare di essere tale.

Kurt Godel
M. C. Escher, Mani che disegnano, 1948 Photo credit: maecla.it

L’idea chiave del teorema di Gödel può essere spiegata con l’aiuto di una storiella. In un paese lontano un gruppo di matematici che non avevano mai sentito parlare di Gödel si convinse che esisteva davvero una procedura sistematica per determinare infallibilmente la verità o falsità di qualunque proposizione sensata, e si propose di dimostrarlo. La loro procedura poteva essere eseguita da una persona, o da un gruppo di persone, o da una macchina, o da qualsiasi combinazione di queste tre possibilità. Nessuno sapeva con certezza quale combinazione avessero scelto i matematici, perché il sistema era situato in un grande edificio universitario, piuttosto simile a un tempio, e l’ingresso era vietato al pubblico.

Comunque, il sistema venne chiamato Tom. Per controllare l’abilità di Tom gli venivano sottoposte complesse asserzioni logiche e matematiche di ogni tipo e, dopo il tempo necessario per l’elaborazione, arrivavano puntualmente le risposte: vero, vero, falso, vero, falso… Dopo non molto la fama di Tom si diffuse in tutto il paese. In molti venivano a visitare il laboratorio e aguzzavano sempre di più l’ingegno per formulare problemi sempre più difficili nel tentativo di mettere in difficoltà il sistema. Nessuno ci riuscì.

La fiducia dei matematici nell’infallibilità di Tom crebbe a tal punto che persuasero il loro re a offrire un premio a chiunque riuscisse a sconfiggere il suo incredibile potere analitico. Un giorno, un viaggiatore che veniva da un altro paese giunse all’università con una busta e chiese di sfidare Tom. Nella busta c’era un pezzo di carta con una proposizione da sottoporgli. La proposizione, che possiamo indicare con «P» («P» sta per «proposizione» o per «paradosso»), diceva semplicemente: «Tom non può dimostrare che questa proposizione è vera».

P venne sottoposta a Tom. Erano passati appena pochi secondi che il sistema entrò in preda a una specie di convulsione. Dopo mezzo minuto un tecnico giunse correndo dal laboratorio con la notizia che Tom era stato disattivato a causa di problemi tecnici. Che cosa era accaduto? Supponiamo che Tom dovesse arrivare alla conclusione che P è vera. Questo significherebbe che la proposizione «Tom non può dimostrare che questa proposizione è vera» sarebbe stata falsificata. Ma se P è falsificata, non può essere vera. Così se Tom risponde «vero» a P, avrà raggiunto una conclusione falsa, contraddicendo la sua vantata infallibilità.

Dunque Tom non può rispondere «vero». Siamo dunque giunti alla conclusione che P è effettivamente vera. Ma nel giungere a questa conclusione abbiamo dimostrato che Tom non può giungere a questa conclusione. Questo significa che noi conosciamo la verità di una proposizione che Tom non può dimostrare. Questa è l’essenza della dimostrazione di Gödel: che esisteranno sempre certe proposizioni vere che non possono essere dimostrate. Il viaggiatore, naturalmente, lo sapeva e non ebbe alcuna difficoltà a costruire P e intascare il premio.

È importante, tuttavia, rendersi conto del fatto che le limitazioni messe in luce dal teorema di Gödel riguardano lo stesso metodo assiomatico di dimostrazione logica, e non una proprietà delle proposizioni che si cerca di dimostrare. Si può sempre trasformare una proposizione vera che è indimostrabile all’interno di un dato sistema di assiomi in un assioma di qualche sistema esteso. Ma allora ci saranno altre proposizioni indimostrabili in questo sistema esteso, e così via.

Kurt Godel
Kurt Godel

Il teorema di Gödel fu una devastante battuta d’arresto per il programma formalista, ma l’idea di una procedura meccanica per indagare le proposizioni matematiche non venne abbandonata completamente. Forse le proposizioni indecidibili sono solo stranezze che possono essere eliminate dalla logica e dalla matematica? Se si trovasse un modo per distinguere le proposizioni decidibili da quelle indecidibili, allora determinare se una qualsiasi proposizione appartenente al primo gruppo sia vera o falsa potrebbe pur sempre essere fattibile.

Ma è possibile formulare una procedura sistematica per riconoscere in modo infallibile le proposizioni indecidibili ed eliminarle? La sfida venne raccolta da Alonzo Church, un collaboratore di von Neumann a Princeton, il quale dimostrò presto che persino questa meta più modesta era irraggiungibile, almeno in un numero finito di passi. In altri termini: si potrebbero fare asserzioni matematiche potenzialmente vere o false, e si potrebbe intraprendere una procedura sistematica per controllare la loro verità o falsità, ma questa procedura non avrebbe mai termine: il risultato non potrebbe mai essere conosciuto. In definitiva:

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

Chi era Kurt Godel

Kurt Gödel nacque da una famiglia di origini tedesche, nel 1906 a Brünn, l’odierna Brno, in Moravia, al tempo parte dell’Impero austro-ungarico. Dopo aver studiato fisica, matematica e filosofia, all’Università di Vienna, prese la cittadinanza austriaca e divenne docente. In quegli anni pubblicò la sua opera intitolata ‘I teoremi dell’incompletezza’. Nel 1933, raggiunse l’Institute of Advanced Study di Princeton nel New Jersey, su invito di Von Neumann. Qui, dopo aver incontrato Einstein ed esserne diventato amico, prese la cittadinanza statunitense e ottenne la docenza allo IAS. Morì a Princeton nel 1978, all’età di settantadue anni.

Biografia di Kurt Gödel – Eduflix Italia

Approfondimento: i teoremi di incompletezza di Gödel

I teoremi di incompletezza di Gödel sono due teoremi di logica matematica che dimostrano i limiti intrinseci di ogni sistema assiomatico formale in grado di modellare l’aritmetica di base. Questi risultati, pubblicati da Kurt Gödel nel 1931, sono importanti sia nella logica matematica sia nella filosofia della matematica.

I teoremi sono ampiamente, ma non universalmente, interpretati come dimostranti che il programma di Hilbert per trovare un insieme completo e coerente di assiomi per tutta la matematica è impossibile.

Il primo teorema di incompletezza di Gödel apparve per la prima volta come “Teorema VI” nel documento del 1931 di Gödel ” Sulle proposizioni formalmente inderogabili di Principia Mathematica e Sistemi correlati I”. Le ipotesi del teorema furono migliorate poco dopo da J. Barkley Rosser (1936) usando il trucco di Rosser . Il teorema risultante (che incorpora il miglioramento di Rosser) può essere parafrasato in inglese come segue, dove “sistema formale” include l’ipotesi che il sistema sia effettivamente generato.

Primo Teorema di incompletezza: “In ogni formalizzazione coerente della matematica che sia sufficientemente potente da poter assiomatizzare la teoria elementare dei numeri naturali — vale a dire, sufficientemente potente da definire la struttura dei numeri naturali dotati delle operazioni di somma e prodotto — è possibile costruire una proposizione sintatticamente corretta che non può essere né dimostrata né confutata all’interno dello stesso sistema.“.

Secondo teorema di incompletezza di Gödel mostra che, sotto ipotesi generali, questa affermazione coerenza canonica Cons ( F ) non sarà dimostrabile in F . Il teorema è apparso per la prima volta come “Teorema XI” nel documento del 1931 di Gödel ” Proposte formalmente inderogabili in Principia Mathematica e sistemi correlati I “. Nella seguente dichiarazione, il termine “sistema formalizzato” include anche un’ipotesi che F sia effettivamente assiomatizzato.

Secondo Teorema di Incompletenezza: “Nessun sistema, che sia abbastanza coerente ed espressivo da contenere l’aritmetica, può essere utilizzato per dimostrare la sua stessa coerenza.

Questo teorema è più forte del primo teorema di incompletezza perché l’affermazione costruita nel primo teorema di incompletezza non esprime direttamente la coerenza del sistema. La dimostrazione del secondo teorema di incompletezza si ottiene formalizzando la dimostrazione del primo teorema di incompletezza all’interno del sistema F stesso.

Implicazioni: 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.

 

Riferimenti e approfondimenti

  1. Kurt Gödel, 1931, “Über unentscheidbare formale Sätze der Principia Mathematica und verwandter Systeme, I”, Monatshefte für Mathematik und Physik , v. 38 n. 1, pp. 173-198.
  2. 1931, “Über unentscheidbare formale Sätze der Principia Mathematica und verwandter Systeme, I”, in Solomon Feferman , ed., 1986. Kurt Gödel Collected works, vol. I . Oxford University Press, pp. 144-195. ISBN  978-0195147209 . Il tedesco originale con una traduzione inglese di fronte, preceduta da una nota introduttiva di Stephen Cole Kleene
  3. 1951, “Alcuni teoremi di base sui fondamenti della matematica e le loro implicazioni”, in Solomon Feferman , ed., 1995. Kurt Gödel Collected works, vol. III , Oxford University Press, pp. 304-323. ISBN 978-0195147223
  4. Di Gödel incompletezza Teoremi su In Our Time alla BBC
  5. Voce di Kurt Gödel di Juliette Kennedy nella Stanford Encyclopedia of Philosophy , 5 luglio 2011.
  6. I Teoremi di incompletezza di Gödel sono stati introdotti da Panu Raatikainen nella Stanford Encyclopedia of Philosophy , l’11 novembre 2013.
  7. Logica paraconsistente § Aritmetica e teorema di Gödel nella Stanford Encyclopedia of Philosophy
  8. Douglas Hofstadter, “Gödel, Escher, Bach: un’eterna ghirlanda brillante”, Adelphi (ISBN 88-459-0755-4)
  9. E. Nagel, J.R. Newman, “La prova di Gödel”, Universale Bollati Boringhieri (ISBN 88-339-0309-5)
  10. John L. Casti, Werner DePauli, “Gödel, l’eccentrica vita di un genio”, Raffaello Cortina (ISBN 88-7078-711-7)
  11. 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
  12. Italo Aimonetto, “Il fondamento del teorema di Gödel: da Peano a Frege e Russell” – Rivista Filosofia – Torino
  13. B. Rosser: Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic, 1 (1936), N1, pp. 87–91
  14. Hao Wang: A Logical Journey: From Gödel to Philosophy Bradford Books (January 10, 1997) ISBN 0-262-23189-1
  15. Francesco Berto, Tutti pazzi per Godel, Laterza (ISBN 978-88-420-8590-4)

Lascia una recensione

avatar

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.

  Subscribe  
Notificami