backup del Post

Uno dei blog di .mau.

12/12/2011 Uncategorized , ,

Arriva Gödel!

Riassunto della puntata precedente: i matematici erano assolutamente convinti che fosse possibile trovare un sistema formale che permettesse di generare automaticamente tutte e sole le proposizioni vere. Inizialmente si pensava che il sistema formale fosse quello della geometria, come specificato da Euclide; poi la scoperta delle geometrie non euclidee ha fatto scegliere una linea di attacco diversa, che ha portato prima alla scelta dell’aritmetica e infine alla teoria degli insiemi. Russell ha fatto però notare come la definizione ingenua di insieme come “le cose che condividono una certa proprietà” portava ai paradossi, e così con Whitehead ha creato un sistema rigidamente compartimentato (i “tipi”) per impedire il problema alla base dei paradossi, cioè l’autoreferenzialità. A questo punto arriva il giovane Kurt Gödel.

Prima di continuare, però, aggiungo ancora due parole sull’autoreferenzialità e su come i Principia Mathematica l’avessero voluta tenere fuori: questo sarà molto importante nel seguito. Russell e Whitehead hanno definito una gerarchia infinita di tipi, affermando che gli insiemi di tipo 0 non possono contenere al loro interno altri insiemi ma solo elementi, quelli di tipo 1 possono contenere anche insiemi ma solo di tipo 0, quelli di tipo 2 solo insiemi di tipo 0 e 1, e via contando. Tra l’altro il concetto di “insieme di tutti gli insiemi” in questa teoria non esiste; si parla in questo caso di classe, che è un modo per dire “qualcosa che sembra un insieme ma non lo è, perché sennò arrivano i paradossi”. Una prova ontologica in meno per l’esistenza di un Dio panteista…

Nonostante tutto il lavoro che aveva fatto, il duo britannico non era ancora riuscito a dimostrare il suo punto fondamentale: che cioè il linguaggio formale in cui erano scritti i Principia Mathematica dava un sistema coerente (non si può mai dedurre una formula falsa applicando le sue regole) e completo (una qualunque formula vera ha una sua deduzione dagli assiomi con una catena finita di inferenze logiche). Nel 1929 si ebbe un primo, parziale, risultato positivo: un giovane austriaco dimostrò che il calcolo dei predicati del primo ordine era completo, e quindi in esso ogni formula logicamente corretta era dimostrabile in un tempo finito.

Ma che cos’è il calcolo dei predicati del primo ordine, mi chiederete? Semplice. Avete presente tutti i sillogismi tipo “se quando piove uso l’ombrello e adesso piove, allora adesso uso l’ombrello”? Bene, si parte da queste frasi, quindi con i connettori logici ∧ (in italiano “e”), ∨ (in italiano “o”, per la precisione “almeno una delle due possibilità”), ¬ (in italiano “non”), ⇒ (in italiano “implica”); e ci si aggiungono i quantificatori, che sono due: ∀, che significa “per ogni” e infatti gli americani l’hanno disegnato come una A (all) rovesciata, ed ∃, che significa “esiste un” ed è stato disegnato come una E (exist) rovesciata. I quantificatori permettono di usare delle variabili, che sono appunto elementi che possono essere scelti a piacere. Così una frase italiana come “ogni numero è divisibile per 2” si traduce nella proposizionexy (y + y = x). Che la proposizione sia vera oppure falsa dipende naturalmente dal contesto in cui gli elementi si trovano (l’universo): supponendo implicitamente che il simbolo “+” abbia il significato di somma (altrimenti la proposizione non sarebbe una codifica corretta…), se usiamo i numeri naturali essa è falsa, mentre se usiamo i reali è vera. Ma dal punto di vista della logica non è così importante; ripeto che quello che dice il teorema di completezza (il nome ufficiale) è che se la formula è logicamente corretta allora si poteva dimostrare che discende dalle regole sintattiche, lasciando da parte la semantica.

Certo, non si era ancora al risultato vagheggiato da Hilbert, quello della sua frase «Wir müssen wissen, wir werden wissen» (noi dobbiamo sapere, e noi sapremo): già solo l’aritmetica non poteva essere formalizzata con la logica dei predicati del prim’ordine, perché per catturare l’induzione occorre avere un numero infinito di assiomi, o se preferite uno “schema di assiomi” dove quello che viene quantificato non è necessariamente una singola variabile, ma può essere un qualunque sottoinsieme degli elementi dell’universo. Insomma, il solito infinito che fa capolino. Ma era comunque un risultato promettente, e si poteva considerarlo un punto di partenza. Chi era il giovane dottorando che l’aveva dimostrato? Beh, Kurt Gödel. Come avrete capito, Gödel era uno che con la logica ci dava dentro bene, soprattutto considerando che aveva preso a studiarla seriamente da solo un anno… Ci vollero ben altri due anni prima di pubblicare il famoso articolo Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I.

Come ho scritto, il progetto hilbertiano consisteva nel dimostrare – “metadimostrare”, oserei dire – come gli assiomi dell’aritmetica permettessero di dimostrare tutte le proposizioni vere… e naturalmente il viceversa, cioè che non si potesse dimostrare una proposizione falsa: questa seconda possibilità sarebbe deleteria, perché da una singola proposizione falsa e dimostrabile si può ricavare di tutto. Un aneddoto su Bertrand Russell racconta di come fu sfidato a dimostrare che lui fosse il papa, se 1 fosse stato uguale a 2. Russell subito rispose “io e il papa siamo due persone: ma se 1=2 allora siamo una persona sola e quindi io sono il papa!”. Credo che il buon vecchio Bertie si fosse inventato da solo la storiella per farsi pubblicità, ma non importa. Insomma, il sacro Graal dei matematici era l’uguaglianza Vero = Dimostrabile; bastava ottenerla per l’aritmetica, perché le altre parti della matematica erano già state riportate ad essa. Il Credo del Matematico, come spiega Douglas Hofstadter in Anelli nell’io, recita insomma

 X è vero perché c’è una dimostrazione di X;
X è vero e quindi c’è una dimostrazione di X;

La prima frase corrisponde ad affermare la consistenza dell’aritmetica, mentre la seconda ne deifinsce la completezza.

Come ha fatto Gödel per infrangere questo sogno? Tradotto in linguaggio corrente, ha dimostrato come partendo da un sistema di assiomi A comprendente almeno quelli di base dell’aritmetica si poteva sempre costruire un’affermazione del tipo «io non sono dimostrabile nel sistema di assiomi A». La parola “io” si riferisce all’affermazione stessa, se la cosa non fosse sufficientemente chiara: ricorda un po’ il paradosso del mentitore, vero? Vediamo il significato – se lo si può chiamare così – di questa affermazione. Se fosse dimostrabile, allora arriviamo immediatamente a un assurdo, perché sarebbe allo stesso tempo dimostrabile e non dimostrabile; se invece non lo fosse, allora sarebbe vera e quindi avremmo mostrato come non tutte le affermazioni vere sono dimostrabili. Insomma, ci manca qualcosa. Certo, potremmo pensare di aggiungere quell’affermazione alla lista iniziale degli assiomi e ottenere un nuovo sistema A’ più ampio e sperabilmente completo: ma proprio come nel caso dell’argomento diagonale di Cantor la terribile trappola gödeliana scatterebbe ancora, e quindi si potrebbe costruire una nuova affermazione del tipo «io non sono dimostrabile nel sistema di assiomi A’». Inutile: non si scampa.

Detta così in effetti è un po’ troppo facile: Gödel nel suo articolo spiega esattamente come si costruisce l’affermazione di cui sopra, ma il tutto diventa troppo tecnico per essere spiegato qua. Le idee alla base della dimostrazione però sono abbastanza semplici; nel prossimo post (l’ho già pronto, solo che mi sono accorto che postarlo qui sotto era troppo, così ho diviso in due parti il testo) proverò a scriverle sotto forma di ricetta, mischiando essenzialmente la descrizione hofstadteriana che trovate nel capitolo 10 di Anelli nell’io e la voce di Wikipedia, e aggiungendoci parecchio di mio perché sennò non ci capivo nulla. Inutile dire che il buon Doug racconta il tutto in modo molto più divertente e pieno di giochi di parole… anche nella traduzione italiana. Inutile anche dire che la voce di Wikipedia è stata scritta da uno che non si rende conto che esiste qualcuno al mondo che non ha studiato logica: tutto torna, ma solo dopo aver battuto abbastanza forte la testa contro il muro… Spero insomma che il mio schema risulterà un po’ più comprensibile!

2 to “Arriva Gödel!”

Trackbacks/Pingbacks

  1. […] ← Arriva Gödel! Cinque bastano → Search for: […]

  1. Il primo teorema di incompletezza di Gödel | backup del Post says...

    […] ← Arriva Gödel! Cinque bastano → Search for: […]

  2. Il primo teorema di incompletezza di Gödel says...

    This Article was mentioned on xmau.com

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.