Godel, teorema di

Godel, teorema di

Gödel, teorema di teorema che riguarda l’incompletezza di un’ampia classe di teorie formali, tra cui la teoria formale dell’aritmetica (→ aritmetica, sistema formale per la). Costituisce il fondamentale contributo di K. Gödel alla logica del Novecento. Si tratta in realtà di due teoremi che concernono: a) l’incompletezza delle teorie formali, b) l’impossibilità di dimostrare all’interno delle teorie formali la loro coerenza. Il primo risultato comporta, quindi, che in una teoria formale di uno specificato tipo esiste sempre una proposizione non dimostrabile né refutabile; il secondo comporta l’impossibilità per l’aritmetica di dimostrare la propria coerenza al proprio interno, utilizzando cioè i suoi stessi simboli e regole, e, quindi, l’impossibilità di dimostrare la propria coerenza per ogni altra sottoteoria dell’aritmetica stessa.

Il contributo di Gödel, apparso in un suo articolo pubblicato nel 1931 con il titolo Über formal unentscheidbare Sätze der «Principia mathematica» und verwandter Systeme (Sulle proposizioni formalmente indecidibili dei «Principia mathematica» e di sistemi affini), si inserisce nel contesto delle questioni attorno al programma razionalista di D. Hilbert il quale, per superare la cosiddetta crisi dei → fondamenti della matematica, emersa in seguito alle riflessioni di B. Russell e all’enunciazione della sua antinomia (→ Russell, antinomia di), si era prefissato di dimostrare la non contraddittorietà dei sistemi di assiomi delle diverse teorie matematiche, in particolare dell’aritmetica, il cui assetto formale era considerato la base di tutte le altre teorie. Tale illusione razionalista venne messa in crisi appunto dai due teoremi di incompletezza di Gödel.

Il primo teorema di Gödel afferma che «se un sistema di assiomi S dell’aritmetica è coerente, cioè non contiene contraddizioni, allora S non è sintatticamente completo», ossia in S esiste una formula A tale che né A né la sua negazione (indicata con il simbolo ￢A) sono dimostrabili. Ciò significa che se si vuole un sistema di assiomi da cui non si possano dedurre contraddizioni, allora bisogna rinunciare all’idea che in esso si possano derivare tutte le proposizioni vere dell’aritmetica; esisteranno necessariamente delle proposizioni indecidibili, che non possono essere né dimostrate né refutate. In particolare, Gödel fa riferimento all’aritmetica formalizzata secondo gli assiomi di Peano come teoria del primo ordine. Il nucleo su cui si fonda la dimostrazione del primo teorema di Gödel è il concetto di autoreferenzialità. Per comprendere in che modo l’autoreferenzialità sia alla base della dimostrazione del primo teorema di Gödel bisogna considerare che, grazie al procedimento di gödelizzazione, è possibile associare a ogni formula aritmetica il suo numero di Gödel (→ Gödel, numero di). Generalizzando tale procedimento, ogni affermazione riguardante l’aritmetica può essere espressa come formula aritmetica; quindi si può costruire una formula aritmetica G che corrisponda all’affermazione «la formula G non è dimostrabile». A questo punto, in analogia con la situazione descritta dal → paradosso del mentitore, la formula G non è né dimostrabile né refutabile, infatti:

• se G (la quale afferma che G non è dimostrabile) è dimostrabile, allora G non è dimostrabile;

• se G non è dimostrabile, allora la formula G è dimostrabile.

Pertanto, se si vuole che la teoria formale alla base dell’aritmetica sia coerente, cioè non si derivino in essa contraddizioni, allora al suo interno non è possibile dimostrare la formula G, altrimenti si avrebbe come conseguenza la dimostrabilità della formula non G (quindi l’incoerenza della teoria).

Utilizzando tale argomentazione Gödel arriva al risultato che esistono formule aritmetiche vere le quali non sono però dimostrabili nell’aritmetica stessa. Se esiste una formula vera ƒ che non può essere dimostrata in un sistema coerente di assiomi S, allora risulta naturale considerare un nuovo sistema di assiomi S′ costituito dagli assiomi di S a cui viene aggiunta la formula ƒ (quindi, S′ = S + ƒ); tuttavia, anche in questo nuovo sistema, sempre per il primo teorema di Gödel, è possibile trovare una formula ƒ″ che sia vera ma non dimostrabile. Dato che questo procedimento può essere iterato, si ha, come conseguenza, che ogni estensione di un sistema assiomatico S è sintatticamente incompleta; a volte si esprime ciò dicendo che l’aritmetica è essenzialmente incompleta.

La dimostrazione del primo teorema di Gödel si basa sull’esistenza della formula indecidibile G che viene costruita ad hoc per provare l’incompletezza sintattica del sistema di assiomi. In seguito lo stesso Gödel, collaborando con P. Cohen, individuò altri esempi di enunciati indecidibili; per esempio, l’assioma della → scelta e l’ipotesi del → continuo sono indecidibili nella teoria degli insiemi formalizzata dagli assiomi di Zermelo-Fraenkel.

Un ulteriore sviluppo dell’incompletezza sintattica dell’aritmetica è espresso dal secondo teorema di Gödel secondo il quale «se un sistema di assiomi S dell’aritmetica è coerente, allora la sua coerenza non è dimostrabile nell’ambito del sistema S»; ciò significa che l’aritmetica, con l’utilizzo dei suoi mezzi, non può dimostrare la propria consistenza. L’importanza di questo risultato risiede nel fatto che l’aritmetica, cioè l’insieme delle proposizioni riguardanti i numeri naturali, è alla base dell’intero impianto costruttivo della matematica; pertanto, affermare che non è possibile dimostrare la coerenza dell’aritmetica utilizzando metodi basati sull’aritmetica stessa equivale a dire che esiste un limite invalicabile al processo di formalizzazione e di costruzione su basi logiche dell’insieme delle teorie matematiche. Tale limite si esprime affermando che per dimostrare la coerenza di un sistema formale bisogna necessariamente utilizzare metodi più complessi di quelli del sistema considerato. La coerenza di un qualsiasi linguaggio può quindi essere dimostrata solo ricorrendo a un → metalinguaggio che utilizzi strutture più articolate. Ogni teoria ha bisogno pertanto di una metateoria e non esiste alcuna teoria ultima che fondi tutte le altre, inclusa sé stessa, perché altrimenti sarebbe autoreferenziale. Per questo motivo i teoremi di Gödel hanno determinato lo spostamento dell’indagine dall’ambito fondazionale ad altri ambiti, quale quello delle definizioni costruttive e della calcolabilità effettiva degli oggetti matematici.