titolo

mercoledì, 22 novembre 2017

Versione in miniatura del Teorema di Gödel

di mariano tomatis
pubblicato il 12 aprile 2007

Costruiamo un sistema che utilizzi quattro simboli: D, N, D, N. In questo sistema è possibile costruire varie espressioni accodando opportunamente i simboli.

Ogni espressione x è composta da una qualunque sequenza dei quattro simboli, e può essere vera o falsa.

Inoltre, ognuna può essere dimostrabile o non dimostrabile.

L'unico legame tra verità e dimostrabilità all'interno di questo sistema è questa: "ogni espressione dimostrabile è vera".

Gödel si chiese se valesse anche l'inverso: "ogni espressione vera è dimostrabile?"

Significato del simbolo D

Il simbolo D significa "dimostrabile nel sistema". Così per ogni espressione x (che sia vera o falsa), Dx afferma che l'espressione x è dimostrabile.

Dx è vera se x è dimostrabile.

Tra il simbolo D e la generica espressione x c'è un unico legame: se Dx è vera, x è vera. Infatti Dx vera indica che x è dimostrabile, ma poiché ogni espressione dimostrabile è vera, allora x è vera.

Significato del simbolo N

Il simbolo N significa "non dimostrabile nel sistema". Così per ogni espressione x (che sia vera o falsa), Nx afferma che l'espressione x non è dimostrabile.

Nx è vera se x non è dimostrabile.

Tra il simbolo N e la generica espressione x c'è un unico legame: se Nx è vera, x non è dimostrabile.

E' importante notare che non si è fornita alcuna regola per determinare verità o falsità delle espressioni Dx o Nx: si sono soltanto evidenziate due implicazioni logiche.

Arriva l'autoreferenzialità...

Se facessimo uso soltanto dei primi due simboli (D ed N) non ci sarebbe alcuna possibilità di ottenere espressioni che fanno riferimento a sé stesse. Ad esempio:

DNNN fa riferimento a NNN affermando che quest'ultima è dimostrabile.
NNDND fa riferimento a NDND affermando che quest'ultima non è dimostrabile.
DD fa riferimento a D affermando che quest'ultima è dimostrabile.

L'autoreferenzialità non si può ottenere perché i simboli non lo consentono; in altre parole, nessuna espressione nel sistema presentato è in grado di affermare qualcosa di sé, ma sempre e soltanto di una espressione più breve (escluse le espressioni finali D ed N che non affermano nulla).

Un modo per introdurre nel sistema la capacità di far riferimento a sé stesso è quello di aggiungere i simboli D ed N, il cui significato aggiunge una regola per cui un enunciato può far riferimento ad altri enunciati eventualmente più lunghi di sé.

Significato del simbolo D

Per ogni espressione x nel linguaggio del sistema, Dx afferma che l'espressione xx è dimostrabile.

Si noti che le due espressioni x e xx non hanno alcun legame logico tra di loro: la verità o la dimostrabilità di una non implica in alcun modo la verità o la dimostrabilità dell'altra.

Per definizione, se Dx è vera, xx è vera. Infatti Dx vera indica che xx è dimostrabile, ma poiché ogni espressione dimostrabile è vera, allora xx è vera.

Significato del simbolo N

Simmetricamente, per ogni espressione x nel linguaggio del sistema, Nx afferma che l'espressione xx non è dimostrabile.

Un po' di pratica con il sistema appena presentato:

DNND è un enunciato che afferma che NND è dimostrabile. La prima espressione (4 simboli) fa riferimento ad un'espressione più corta (3 simboli).

NND è un enunciato che afferma che ND non è dimostrabile. La prima espressione (3 simboli) fa riferimento ad un'espressione più corta (2 simboli).

NN è un enunciato che afferma che NN non è dimostrabile. La prima espressione (2 simboli) fa riferimento ad un'espressione della stessa lunghezza (2 simboli).

DNND è un enunciato che afferma che NNDNND è dimostrabile. La prima espressione (4 simboli) fa riferimento ad un'espressione più lunga (6 simboli).

Questo sistema possiede la capacità di far riferimento a sé stesso. Ad esempio l'enunciato DD fa riferimento all'enunciato DD (dunque a sé stesso) affermando che è dimostrabile. Esso può essere tradotto nei termini "Io sono dimostrabile".

Ogni espressione vera è dimostrabile?

Riprendiamo la domanda che si pose Gödel: in questo sistema, ogni espressione vera è dimostrabile?

La risposta è negativa: l'espressione NN è vera ma non dimostrabile. Eccone la dimostrazione:

NN è un enunciato che afferma che NN non è dimostrabile. Essendo autoreferenziale, esso afferma la propria indimostrabilità, e può dunque essere tradotto nei termini "Io non sono dimostrabile".

NN non può essere falso, perché se così fosse sarebbe falsa l'affermazione "Io non sono dimostrabile", dunque sarebbe vera l'affermazione "Io sono dimostrabile".

Ma in questo modo avremmo un enunciato falso dimostrabile, il che va contro le premesse per cui gli enunciati dimostrabili sono tutti veri. Ecco mostrato che non può essere falso. E' dunque certamente vero. E se è vero, è vero quanto afferma: che non è dimostrabile.

NN è quindi contemporaneamente vero e non dimostrabile.

Godel provò che qualunque sistema che vuole essere abbastanza potente da comprendere la possibilità di far riferimento a sé stesso non riesce ad evitare enunciati come NN.

Dunque qualche verità sfuggirà sempre al processo di dimostrazione: ci sarà sempre qualche verità non dimostrabile.

Se, invece, un sistema non sarà così potente da comprendere l'autoreferenzialità, per questo stesso motivo non sarà completo e dunque gli sfuggiranno sempre alcune verità.

Nota importante

Il lettore potrebbe trovarsi un po' spiazzato perché non nel sistema definito non è fornita alcuna regola per definire la verità o la falsità delle espressioni; in effetti è così: non c'è alcun bisogno di definire un criterio del genere; è sufficiente definire alcune implicazioni logiche tra verità e dimostrabilità per mettere in luce l'incompletezza di un sistema autoreferenziale.

E' spontaneo chiedersi "DN è vero o falso?", ma la risposta è ininfluente.

Esso afferma che N è dimostrabile, e per sapere se l'espressione DN è vera o falsa dovrei prima determinare la verità o falsità di N; al simbolo N isolato, però, non è stato ancora attribuito alcun significato. Non c'è dunque alcun modo, nel sistema presentato finora, di determinare se DNNDNDNNND sia vero o falso (e così per molti altri enunciati). La cosa sorprendente, però, è che non c'è alcun bisogno di definire un criterio di verità per il fine che ci siamo posti, ossia per trovare una verità indimostrabile. NN, infatti, è chiaramente vera e indimostrabile, anche se non si è data alcuna regola per determinare verità e falsità dei simboli D, N, D, N!

Conseguenze e riflessioni

Sulle conseguenze del Teorema di Gödel ha scritto un interessante commento Piergiorgio Odifreddi, qui riportato:

Le conseguenze del teorema di Gödel per l'epistemologia della matematica ci sono, ma sono limitate e meno estese di quanto si suole in genere affermare, soprattutto negli scritti divulgativi. Il teorema dice che gli usuali sistemi formali della matematica che contengano una minima parte dell'aritmetica sono incompleti, nel senso che non possono dimostrare tutte le verità esprimibili nel linguaggio della teoria. E' dunque in gioco l'incompletezza, che riguarda l'insieme di tutte le possibili verità, da quelle più stupide e superficiali a quelle più profonde.
In realtà, i matematici non sono mai stati interessati a tutte le (infinite) verità, ma solo ad un piccolo numero (finito) di esse, significative da qualche punto di vista particolare. Il teorema di Gödel non dice nulla sulla indimostrabilità o indecidibilità di queste singole affermazioni, in particolare sui principali problemi aperti della matematica: parla solo dell'indecidibilità della maggior parte delle affermazioni. Il che non significa affatto che quelle interessanti in teoria o in pratica non possano poi risultare decidibili in un senso o nell'altro (ad esempio, per qualche tempo si e' pensato che il cosiddetto teorema di Fermat potesse essere vero ma indimostrabile, e poi lo si e' invece dimostrato). In sintesi, il teorema di Godel riguarda quanto si possa sapere della verità matematica (e la risposta è "poco"), ma non dice cosa (non) si possa sapere.
Le limitazioni del teorema di Godel non sono comunque più devastanti di quelle di Cantor o di Turing, che hanno rispettivamente dimostrato che quasi tutti i numeri reali non si possono definire, e quasi tutte le funzioni di numeri interi non si possono calcolare. Il che non impedisce che noi continuiamo ad interessarci ai pochi numeri reali definibili (fra i quali ci sono, per forza di cose, tutti quelli noti, dai razionali a pi greco), o delle poche funzioni calcolabili (fra le quali ci sono tutte quelle che possono calcolare i computer, e dunque tutte quelle di interesse per l'informatica teorica o pratica).
In ogni caso, voler estendere il teorema di Gödel ad altri ambiti che non sono i suoi propri è pericoloso, e può generare fraintendimenti. Tanto per cominciare, non lo si può neppure estendere a tutti i sistemi matematici: ad esempio, la teoria elementare della geometria è completa, come ha dimostrato Tarski, e dunque le limitazioni di Gödel richiedono in modo essenziale l'aritmetica. Non parliamo poi delle estensioni ad ambiti che non sono neppure strettamente matematici, dalla fisica alla politica. La mia opinione è che in questi campi sia meglio lasciar perdere i teoremi di Gödel, e considerare limitazioni intrinseche, dal Principio di Indeterminazione di Heisenberg e il Teorema di Bell nel primo caso, ai Teoremi di Arrow e Sen nel secondo.
Ciò detto, è innegabile che tutti questi risultati dimostrino che ci sono limiti alla conoscenza, e che la "verità" si possa soltanto approssimare in maniera estremamente ristretta. Ma questo può turbare soltanto coloro che credevano che si potesse sapere tutto. Per me l'interesse dei teoremi limitativi non sta nel fatto che essi mostrino limiti alla conoscenza matematica dell'universo, ma che lo dimostrino in maniera matematica! In altre parole, il pensiero formale sarà pure limitato, ma fra le sue limitazioni non c'è quella di non sapere di essere limitato! Conoscere i propri limiti, non è forse l'espressione più alta della consapevolezza?"

(Questa pagina è liberamente ispirata a Satana, Cantor e l'infinito di Raymond Smullyan)

Articolo visualizzato 1843 volte

Questo sito non rappresenta una testata giornalistica in quanto non viene aggiornato con cadenza periodica
né è da considerarsi un mezzo di informazione o un prodotto editoriale ai sensi della legge n.62/2001.
Praestigiator è curato da Mariano Tomatis