2. Incompletezza
2.2. Formulazioni dei teoremi di incompletezza
Consideriamo ora alcune formulazioni dei due teoremi di incompletezza. In G¨odel 1930b possiamo leggere:45
... se agli assiomi di Peano aggiungiamo la logica dei Principia Mathematica ... e l’assioma di scelta otteniamo un sistema formale S per cui valgono i seguenti teoremi: I. il sistema S non `e completo; cio`e esso contiene propo- sizioni A per le quali non `e dimostrabile n´e A n´e ¬A e, in particolare, esso contiene problemi indecidibili della semplice struttura ∃xF (x) dove x varia sui numeri naturali. II. Persino se ammettiamo tutti gli strumenti logici dei Principia Mathematica nella metamatematica, non esiste una dimostrazione di noncontraddittoriet`a per il sistema S.
In questo articoletto il primo teorema di incompletezza viene formulato per un particolare sistema formale, tuttavia viene poi generalizzato nel senso che:46
... il teorema I vale anche per tutte le estensioni ω-consistenti del sistema T che si ottengono aggiungendo un numero infinito di assiomi, purch´e la classe di assiomi aggiunta sia decidibile.
Le condizioni che vengono qui presentate come sufficienti affinch´e un sistema formale T sia incompleto sono tre:
1. T deve essere un’estensione di un opportuno sistema formale per l’a- ritmetica (cio`e deve essere un sistema capace di esprimere alcuni fatti aritmetici elementari);
2. T deve essere ω-consistente ossia tale che non esista nessun predicato P (x) del linguaggio di T tale che:
(a) per ogni numero naturale n, T ` P (n), e (b) T ` ∃x¬P (x);
3. T pu`o avere un numero finito di assiomi oppure un numero infinito di assiomi purch´e l’insieme degli assiomi sia decidibile.
In G¨odel 1931 il primo teorema di incompletezza viene invece formulato cos`ı:47
Teorema VI. Per ogni classe k ricorsiva, ω-consistente di formule esistono segni di classe ricorsivi r tali che n´e vGenr n´e Neg(vGenr) appartengono a Flg(k) (dove v `e la variabile libera di r).
Ci`o significa che per ogni sistema formale T ω-consistente, i cui assiomi co- stituiscano una classe decidibile esistono formule non quantificate R(x) tali che n´e ∀xR(x) n´e ¬∀xR(x) appartiene all’insieme dei teoremi di T. Detto ancor pi`u semplicemente: per ogni sistema formale T basato su di un insieme ω-consistente e decidibile di assiomi, esistono formule puramente universali che il sistema formale T non dimostra n´e refuta. Per usare le parole di G¨odel sempre nel suo 1931, in ogni sistema formale definito come sopra: “esistono
46Cf. G¨odel 1930b in G¨odel 1986, pag. 142. 47Cf. G¨odel 1986, pag. 172.
problemi relativamente semplici di teoria degli interi che non possono esse- re decisi sulla base degli assiomi”.48 Il secondo teorema di incompletezza, sempre in G¨odel 1931 recita cosı:49
Teorema XI. Sia k una qualsiasi classe ricorsiva e consistente di formule; allora la formula proposizionale che stabilisce che k `e consistente non `e k- dimostrabile.
Ossia, in ogni sistema formale noncontraddittorio e basato su un insieme decidibile di assiomi, la proposizione che ne stabilisce la noncontradditto- riet`a non `e dimostrabile e quindi fa parte dell’insieme delle proposizioni formalmente indecidibili del sistema.
Sempre nell’articolo del ’31 G¨odel osserva che nella dimostrazione del pri- mo teorema di incompletezza si usano solo tre propriet`a del sistema formale T in questione:
1. il fatto che gli assiomi e le regole di T siano decidibili e cio`e che l’insieme dei codici (numeri di G¨odel)50 degli assiomi e delle regole del sistema sia definibile ricorsivamente;
2. il fatto che ogni relazione ricorsiva (primitiva) sia rappresentabile (cio`e definibile) nel sistema T;
3. il fatto che il sistema T sia ω-consistente.
Dunque qui le condizioni di applicabilit`a del primo teorema di incompletezza vengono precisate nel senso che alla decidibilit`a dell’insieme degli assiomi vien sostituita la definibilit`a ricorsiva dell’insieme (dei numeri di G¨odel) degli assiomi ed alla richiesta che T sia un’estensione di un’opportuno sistema formale per l’aritmetica si sostituisce la condizione di rappresentabilit`a o definibilit`a delle relazioni ricorsive (primitive) nel sistema T.
Nelle lezioni di Princeton del ’34 i due teoremi di incompletezza non ven- gono formulati esplicitamente e distintamente, tuttavia nel primo paragrafo G¨odel scrive:51
48Cf. G¨odel 1986, pag. 144. 49Cf. G¨odel 1986, pag. 192.
50Da qui in avanti col termine “g¨odeliano” o “numero di G¨odel” di un certo simbolo
(rispettivamente, di una certa successione di simboli o di una successione di successioni di simboli) del linguaggio L di un certo sistema formale T, intendiamo un numero naturale n che corrisponde a quel simbolo (rispettivamente, a quella successione di simboli o a quella successione di successioni di simboli), sulla base di un’opportuna codifica effettiva del linguaggio L.
Dimostreremo ... che (sotto condizioni da precisare) un sistema in cui sono esprimibili tutte le proposizioni dell’aritmetica come formule sensate non `e completo.
Alle “condizioni” che un sistema formale deve soddisfare affinch´e gli si pos- sano applicare gli argomenti di incompletezza G¨odel dedica qui un intero paragrafo. Nel paragrafo 6 di G¨odel 1934 troviamo ben sei condizioni, ossia: 1. fissata una certa codifica (g¨odelizzazione) dei simboli del linguaggio del sistema formale T, la classe degli assiomi e la “relazione di conseguenza immediata” devono essere ricorsive;
2. ci deve essere una certa successione di formule ben-formate ϕn tali che
la relazione fra il numero naturale n e il numero di G¨odel di ϕn sia
ricorsiva;
3. ci devono essere simboli ¬, x, y tali che ad ogni relazione ricorsiva R in due variabili corrisponda una formula R∗(x, y) di T tale che, se p e q stanno nella relazione R allora, se indichiamo con dpe e dqe i numeri di G¨odel di p e q, si ha:
T ` R∗(dpe , dqe),
mentre se p e q non stanno nella relazione R, allora: T ` ¬R∗(dpe , dqe);
4. ci deve essere un simbolo ∀ tale che se T ` ∀xR(x), dove R `e un simbolo che rappresenta una relazione ricorsiva, allora, per ogni numero naturale n,
T ` R(dne)
dove dne indica il termine che sta per il numero di G¨odel che rappresenta il numero naturale n nel sistema T;
5. il sistema deve essere noncontraddittorio nel senso che, se R∗ `e un simbolo che rappresenta una relazione binaria ricorsiva R, allora non si d`a il caso che:
T ` R∗(dpe , dqe) e
6. T deve inoltre essere ω-consistente nel senso che se P∗ `e un simbolo che rappresenta una relazione ricorsiva unaria P allora non si d`a il caso che:
T ` ¬∀xP∗(x), e per ogni numero naturale n:
T ` P∗(d0e), T ` P∗(d1e), T ` P∗(d2e), ... ... T ` P∗(dne) ...
Come abbiamo visto, al di l`a delle differenze formali delle varie enunciazioni dei risultati di incompletezza, quello che le contraddistingue maggiormen- te sono le condizioni di applicabilit`a dei teoremi. Su tali condizioni G¨odel continu`o a riflettere e a lavorare anche molti anni dopo la pubblicazione dei teoremi di incompletezza, probabilmente in quanto era proprio su quel terreno che si giocava la maggiore o minore generalit`a di quei risultati.
Ulteriori ricerche gi`a a partire dagli anni ’30 ad opera di Hilbert e Bernays portarono all’individuazione, nell’ambito della dimostrazione rigorosa del se- condo teorema di incompletezza, delle cosiddette “condizioni di derivabilit`a” oggi note anche come “condizioni di L¨ob” che il predicato di dimostrabilit`a Bew deve soddisfare.
Nel corso degli anni ’50 Georg Kreisel, Solomon Feferman, Andrzej Mo- stowski ed altri individuarono dei predicati di dimostrabilit`a sulla base dei quali non era possibile dimostrare il secondo teorema di incompletezza, con- fermando quindi che le attenzioni g¨odeliane per le condizioni di applicabilit`a dei suoi risultati erano tutt’altro che immotivate.
2.3. La strategia dimostrativa
Per illustrare brevemente la strategia usata da G¨odel nella dimostrazione del suo primo teorema di incompletezza, ci serviremo qui dell’inedito G¨odel *1931d, databile orientativamente nei primi anni Trenta, che costituisce forse lo schema espositivo di una conferenza divulgativa. In effetti fra il gennaio 1931 e l’aprile 1934 G¨odel tenne varie conferenze sull’incompletezza ad esem- pio a Vienna (il 15 gennaio 1931), a Bad Elster (il 15 settembre 1931), a New York (il 18 aprile 1934) e a Washington (il 20 aprile 1934).
In G¨odel *1931d il primo teorema di incompletezza viene enunciato nella sua forma pi`u semplice e lineare ossia:52
Ogni sistema formale con un numero finito di assiomi che contenga l’aritme- tica dei numeri naturali `e incompleto.
Il risultato viene poi opportunamente generalizzato come segue:53
Lo stesso vale anche per sistemi con infiniti assiomi purch´e la regola per gli assiomi (cio`e la legge sulla base della quale viene generato l’insieme infinito degli assiomi) sia costruttiva (in un senso che pu`o essere completamente precisato).
Infine G¨odel aggiunge un’importante osservazione a proposito della natura costruttiva del primo risultato di incompletezza:54
Per ogni sistema formale che soddisfi le assunzioni enunciate si pu`o specificare in modo effettivo una proposizione indecidibile e la proposizione cos`ı costruita appartiene all’aritmetica dei numeri naturali.
Ossia, non solo si pu`o dimostrare che, in linea di principio, tutti i sistemi for- mali ω-consistenti, sufficientemente potenti e basati su un insieme di assiomi ricorsivo sono incompleti, ma per essi `e possibile fornire una dimostrazio- ne costruttiva di questa incompletezza mediante un particolare esempio di proposizione che non pu`o essere n´e dimostrata n´e refutata sulla base degli assiomi.
G¨odel traccia poi le linee essenziali della dimostrazione di questo risultato. 1. Per prima cosa si fissa una codifica del linguaggio L di un certo sistema formale T e cio`e si attribuisce un numero naturale distinto ad ogni
52Cf. G¨odel 1995, pag. 30. 53Cf. G¨odel 1995, pag. 30. 54Cf. G¨odel 1995, pag. 32.
simbolo del linguaggio in modo tale da poter determinare per ogni simbolo il suo numero e viceversa per ogni numero naturale se esso codifica qualche simbolo del linguaggio e quale. La codifica permetter`a di assegnare un numero non solo ai simboli primitivi ma anche ad ogni successione finita di simboli e ad ogni successione finita di successioni finite di simboli. Dunque la codifica o g¨odelizzazione fornir`a anche una numerazione delle formule e delle dimostrazioni del sistema formale T. 2. Ad ogni nozione sintattica riguardante il sistema T (ad esempio, essere una formula, essere un assioma, essere derivabile mediante una regola di inferenza, essere un teorema) verr`a associata, mediante la codifica di cui sopra, una nozione aritmetica. In tal modo, la sintassi di T diventa esprimibile aritmeticamente e visto che T, per definizione, deve contenere un’opportuna porzione di aritmetica, le nozioni sintattiche e metamatematiche di T risulteranno esprimibili in T stessa.
G¨odel porta come esempio di relazione metamatematica relativa a T esprimibile in T, la relazione “la formula ϕ `e derivabile dalla formula ψ mediante le regole di inferenza”. Ad essa, spiega l’autore, corrisponder`a la relazione aritmetica R la quale sussiste fra i numeri naturali m e n se e solo se la formula di numero di G¨odel n `e derivabile dalla formula di numero di G¨odel m.
3. Si considerano poi tutte le formule di T con una sola variabile libera ed un loro ordinamento basato sui numeri ad essi assegnati:
ϕ1(x), ϕ2(x), ϕ3(x), ...
4. Si definisce quindi la classe K come:
n ∈ K ↔ ¬BewT(ϕn(n)),
dove BewT(ϕn(n)) sta per “la formula ϕn(n) `e dimostrabile in T”.
Questa classe K, definita in termini del predicato di derivabilit`a BewT risulta essere dimostrabilmente aritmetica, cio`e c’`e una classe espri- mibile mediante somma, prodotto, connettivi e quantificatori che `e “coestensiva con K”.
5. Dall’ipotesi secondo cui T `e un’estensione di un’opportuna parte del- l’aritmetica, segue che fra le formule della successione ϕ1(x), ϕ2(x), ...
ce ne sar`a una ϕk(x) tale che:
ϕk(x) ↔ x ∈ K
e quindi tale che:
ϕk(n) ↔ ¬BewT(ϕn(n))
per qualsiasi numero naturale n. 6. In particolare, per n = k, avremo che:
ϕk(k) ↔ ¬BewT(ϕk(k)).
7. Ora sappiamo che, se si avesse che: T ` ϕk(k),
allora si avrebbe anche che:
T ` ¬BewT(ϕk(k))
ossia, informalmente parlando, se ϕk(k) fosse dimostrabile in T, allora
in T si dimostrerebbe anche che ϕk(k) non `e dimostrabile in T. Se
si assume che T sia corretto, cio`e che dimostri solo cose vere, allora avremo che ϕk(k) `e dimostrabile in T e, ad un tempo, che ϕk(k) non `e
dimostrabile in T, ma ci`o `e assurdo. 8. Analogamente, se:
T ` ¬ϕk(k),
allora:
T ` BewT(ϕk(k))
e quindi, sempre sotto l’ipotesi della correttezza del sistema T, otter- remmo che sia ϕk(k) che ¬ϕk(k) sono dimostrabili in T. Assurdo.
Dunque possiamo concludere che la proposizione ϕk(k) `e formalmente
indecidibile sulla base degli assiomi del sistema formale T. G¨odel puntualizza che:55
Nella dimostrazione si `e tacitamente assunto che ogni proposizione dimostra- bile in T sia vera. Come un’attenta ricerca mostra, questa assunzione pu`o essere rimpiazzata da un’altra molto pi`u debole la quale richiede solo poco pi`u della noncontraddittoriet`a del sistema considerato.
Chiaramente qui l’autore st`a alludendo all’ipotesi di ω-consistenza, la qua- le a sua volta, come dimostrato in Rosser 1936, pu`o essere ulteriormente indebolita alla semplice noncontraddittoriet`a.
Negli scritti di G¨odel, non si trova lo svolgimento dettagliato della dimo- strazione del secondo teorema di incompletezza. Sia nell’articolo del ’31 che nelle lezioni del ’34 l’argomento `e solo accennato nei seguenti termini.56
Sia ϕk(k) la proposizione formalmente indecidibile costruita come so-
pra per un certo sistema formale T sufficientemente potente. Sia W idT la proposizione che esprime la noncontraddittoriet`a di T nei seguenti termini:
∀x∀y∀z¬(B(x, y) ∧ B(z, N eg(y)))
dove B(x, y) sta per “x `e (il numero di G¨odel di) una dimostrazione della formula di (numero di G¨odel) y” e N eg(y) sta per “il numero di G¨odel della negazione della formula (di numero di G¨odel) y”. Essendo W idT un’afferma- zione del fatto che il sistema T `e noncontraddittorio, col primo teorema di incompletezza si `e dimostrato che:
∀x∀y∀z¬(B(x, y) ∧ B(z, N eg(y))) → ∀x¬B(x, ϕk(k)).
Ma se fosse dimostrabile W idT, allora avremmo che per modus ponens sareb- be dimostrabile ∀x¬B(x, ϕk(k)) e quindi ϕk(k), il che `e impossibile. Dunque,
conclude G¨odel, W idT non `e dimostrabile in T a meno che T “non contenga una contraddizione”.