Capitolo 3
INCOMPLETEZZA
1. PRODROMI
L'introduzione allo scritto del 1929 suggeriva le difficoltà connesse
all'equiparazione di coerenza e esistenza, legate in primo luogo all'esclusione
di una possibile dimostrazione della non risolubilità di un problema
matematico rispetto a un sistema formale. Nella relazione al convegno tenutosi
a Königsberg nel 1930, il primo annuncio pubblico del risultato di
incomplezza, per quanto informale, è introdotto da un'analoga considerazione:
i formalisti considerano la richiesta di coerenza equivalente a quella
di correttezza. Così quando al sistema S delle proposizioni dotate
di senso della matematica aggiungiamo il sistema T degli asserti transfiniti,
nell'ottica formalista si intende che, dimostrando un teorema di S attraverso
teoremi di T, esso sarà anche contenutisticamente corretto. L'aggiunta
di assiomi transfiniti non rende dimostrabili teoremi contenutisticamente
falsi.
E' questa la già citata conservatività, richiesta da
Hilbert per l'introduzione di elementi ideali in un dominio di proposizioni
reali. Ma che la coerenza di una proposizione attesti automaticamente la
sua correttezza esige, come osserva Brouwer, che si presupponga la correttezza
contenutistica proprio di questa convinzione; il che costituisce un circolo
vizioso.
La correttezza non coincide con la coerenza. "Se infatti una proposizione
sensata p è dimostrabile in un sistema formale coerente A (per esempio
quello della matematica classica) utilizzando gli assiomi transfiniti,
dalla coerenza di A segue solo che non-p non è formalmente dimostrabile
entro il sistema."1 Si potrebbe però concludere non-p grazie
a considerazioni di tipo contenutistico non formalmente rappresentabili
nel sistema: "e ciò risulterebbe possibile, ed è proprio
questo che vorrei sottolineare, anche se si fosse dimostrata la coerenza
del sistema formale della matematica classica"2.
Non è ozioso insistere su questo passaggio. Esso è strumentale
all'anticipazione del risultato di indecidibilità. Infatti, se si
trovino esempi di proposizioni che, per quanto contenutisticamente vere,
risultino indimostrabili nel sistema formale della matematica classica,
aggiungendo la loro negazione agli assiomi "si ottiene un sistema coerente
in cui risulta dimostrabile una proposizione contenutisticamente falsa"3.
In conclusione: nulla ci garantisce la piena rappresentabilità
delle considerazioni contenutistiche in un sistema formale. Motivo ne è
la non riducibilità del concetto di verità matematica a quello
di dimostrabilità formale. Rispetto al programma hilbertiano significa
che il ragionamento formalista non sostituisce le considerazioni di ordine
infinitario. Piuttosto, scrive Gödel: "il principio euristico della
mia costruzione nei sistemi matematici delle proposizioni indecidibili
di teoria dei numeri è il concetto transfinito per eccellenza di
verità matematica obiettiva, in opposizione a quello di dimostrabilità"4.
Ma il riferimento esplicito a un concetto di verità obiettiva
non compare in Über formal unentscheidbare Sätze der 'Principia
Mathematica' und verwandter Systeme I (1931). Forse Gödel temeva,
come sostiene Solomon Feferman, che l'accettazione dei suoi risultati ne
sarebbe stata compromessa5. Nella temperie filosofica dominata da Hilbert,
egli volle rendere inoppugnabile il suo lavoro, anche per chi avesse rifiutato
il ricorso a metodi non finitari. L'inizio del testo del 1931 reca infatti
l'accento sulla formalizzazione: "lo sviluppo della matematica verso una
sempre maggiore esattezza ha condotto, come è ben noto, alla formalizzazione
di ampie sue parti, di modo che si possa dimostrare basandosi solo su poche
regole meccaniche"6. Dove la parola meccanico si riferisce proprio alla
possibilità di prescindere dal significato della teoria formalizzata.
2. ARITMETIZZAZIONE
Il sistema formale P, in cui Gödel produce la dimostrazione, è
una variante di quello offerto nei Principia Mathematica7. Tale scelta
risponde a una ragione di capienza espressiva, che consente di formalizzare
nel sistema tutti i metodi di dimostrazione in vigore. Sembra ovvia quindi
l'aspettativa della decidibilità di ogni quesito matematico esprimibile
in P; eppure: "esistono problemi relativamente semplici della teoria degli
usuali numeri interi che non possono venire decisi sulla base degli assiomi"8.
Ricordando come Hilbert avesse sollevato la questione della completezza
sintattica per l'aritmetica, essenziale per la portata del discorso è
proprio che le proposizioni indecidibili siano aritmetiche. La lezione
hilbertiana traspare poco dopo, quando Gödel introduce all'idea di
fondo della aritmetizzazione. Come oggetti di studio metamatematico, le
formule e le dimostrazioni di un sistema formale sono successioni finite
di segni primitivi/formule. Essendo indifferente quali oggetti si scelgano
come segni primitivi, possiamo rappresentare tali segni con i numeri naturali.
Vale a dire, tracciamo una corrispondenza biunivoca dagli oggetti del sistema
formale ai numeri naturali, in modo tale da associare a oggetti distinti
numeri diversi.
"Una formula sarà allora una successione finita di numeri naturali
e una figura di dimostrazione sarà una successione finita di successioni
finite di numeri naturali"9. Dunque in virtù della numerazione
di Gödel, mentre la metamatematica 'parla' degli oggetti del sistema
formale, le sue proposizioni vertono, rispetto all'interpretazione, sui
numeri naturali. In tal modo esse sono esprimibili con i segni di PM stesso:
la metateoria cala nella teoria. Ma PM è stato aritmetizzato. Si
crea: "un'immagine isomorfa del sistema PM nel dominio dell'aritmetica
e tutte le argomentazioni metamatematiche possono essere sviluppate altrettanto
bene in questa immagine"10.
Il passo è cruciale: da questo momento in poi si lavorerà
con i numeri naturali, per parlare della teoria elementare dei numeri;
si opererà con gli strumenti della teoria, per ottenere conclusioni,
che incidano sulla metateoria. E si sfrutterà per un fine non finitista
l'intuizione hilbertiana che una prova assoluta di coerenza per l'aritmetica
comporti un'internalizzazione della prova, in quanto PM funge, al tempo
stesso, da metateoria e suo oggetto. "In particolare si può mostrare
che i concetti di 'formula', 'figura di dimostrazione' e 'formula
dimostrabile' possono essere definiti all'interno del sistema PM."11.
Per esemplificare quello che con definibile si intende, Gödel
va direttamente al concetto in gioco nella proposizione indecidibile, quello
di 'formula dimostrabile'. "E' possibile, per esempio, trovare una formula
F(v) di PM con una variabile libera v (il cui tipo è quello di una
successione numerica) tale che F(v), interpretata contenutisticamente,
dica: v è una formula dimostrabile."12 Come si preciserà
più avanti (teorema V), la definibilità è esprimibilità
per numerali di una relazione (concetto) numerica ricorsiva in PM.
Una relazione numerica R(x1,...,xn) è esprimibile nel
nostro sistema se e solo se esiste una formula R(x1,...,xn) con x1,...,xn
variabili libere, tale che per ogni n-upla numerica (x1,..., xn):
se R(x1,...,xn) è vera, allora è dimostrabile nel sistema
R(x1,...,xn);
se R(x1,...,xn) è falsa, allora è dimostrabile nel sistema
~R(x1,...,xn) con x1,...,xn numerali.
Ma questo corrisponde alla decidibilità di una relazione rispetto
al sistema formale. "Diremo che una relazione fra (o una classe di) numeri
naturali R(x1,...,xn) è decidibile se esiste un SEGNO DI RELAZIONE
a n posti" che la esprime13. In particolare ogni relazione ricorsiva è
decidibile (teorema V). Con una digressione, precisiamo che una relazione
numerica R(x1,...,xn) è detta ricorsiva (primitiva) se esiste una
funzione caratteristica f(x1,...,xn) tale che, per ogni x1, x2,....,xn,
R(x1,...,xn) se e solo se f(x1,...,xn) = 0.
Tale funzione è, a sua volta, ricorsiva, vale a dire essa è
l'ultimo termine di una successione finita di funzioni numeriche f1,f2,...,fn
in cui ogni funzione della successione è o la funzione successore,
o una funzione costante o una funzione identità oppure è
composta mediante funzioni precedenti o è ricorsiva rispetto a funzioni
precedenti della successione.
Dell'elenco dei 46 concetti (funzioni/relazioni) che Gödel fornisce
a questo punto, solo il concetto di formula dimostrabile (punto 46) non
è ricorsivo14.
3. LA PROPOSIZIONE INDECIDIBILE
Lavorando nell'immagine isomorfa di PM, chiamiamo con Gödel segno
di classe ciò che rappresenta una formula con esattamente una variabile
libera. Ovvero: un segno di classe è la formula aritmetizzata in
cui, in vece della successione finita di simboli originari, sta una successione
finita di interi. "Assumiamo che i segni di classe siano stati ordinati
in qualche modo in una successione e indichiamo l' n-esimo di essi con
R(n)"15 .
La relazione R, che si suppone di ordine crescente, affida quindi a
ogni segno di classe il posto in base al suo gödeliano. Se a è
l'n-esimo segno di classe, lo si può indicare anche con R(n).
"Con [a; n] indichiamo la formula che si ottiene dal segno di classe
a sostituendo ovunque la variabile libera con il segno che denota il numero
naturale n. Anche la relazione ternaria x = [y;z ] risulta essere definibile
in PM."16
Poiché siamo nell'immagine isomorfa, la relazione ternaria,
che sostanzialmente descrive l'esito dell'operazione di sostituzione, di
cui Gödel si avvarrà per costruire la sua proposizione indecidibile,
dà di fatto il gödeliano di [a ; n]. "Definiamo ora una classe
k di numeri naturali nel modo seguente:
n Î k º 
[R(q); q]
(dove Bew x significa: x è una formula dimostrabile)."17
K è dunque una classe di numeri di Gödel tali che, sostituendone
il numerale a tutte le occorrenze della variabile libera dell'n-esima formula,
si ottenga una proposizione non dimostrabile. La definizione di k comporta
quindi una relazione di non dimostrabilità, per la quale nessun
numero naturale sia il numero di Gödel di una dimostrazione in P di
[R(n); n]. Dato che i concetti di sostituzione e quello di dimostrazione
sono ricorsivi, esisterà un segno di classe S, che con [S ; n] esprima
quanto individuato da k.
Per S = R(q) rispetto all'ordinamento dei segni di classe, [S; q] =
[R(q); q]. "Mostriamo allora che la proposizione [R(q); q] è indecidibile".18
Gödel procede in prima battuta per via strutturale: tanto la dimostrabilità
di [R(q); q] che quella della negazione di [R(q); q] provocano contraddizione.
In seconda battuta si palesa che [R(q); q], per come è stata costruita,
afferma la propria indimostrabilità: quindi è vera.
Assumiamo, per incominciare, che sia dimostrabile [R(q); q]: "allora
risulterebbe anche vera; quindi, sulla base delle definizioni date sopra,
q dovrebbe appartenere a k"19. Data cioè la correttezza della condizione
definitoria per k, per n = q, q Î k. Ma allora: [R(q);q].
Se invece fosse dimostrabile la negazione di [R(q); q], per n = q allora
q non appartiene a k; perciò: Bew[R(q); q].
4. LA CONDIZIONE DI W-COERENZA
"Il metodo di dimostrazione rappresentato può ovviamente essere
applicato a ogni sistema formale che, in primo luogo, qualora venga interpretato
contenutisticamente disponga di sufficienti mezzi espressivi per definire
i concetti che compaiono nel precedente ragionamento (in particolare, il
concetto di 'formula dimostrabile') e in cui, in secondo luogo, ogni formula
dimostrabile risulti contenutisticamente vera"20. Nel prosieguo del testo,
le proprietà di minima del sistema formale si precisano: 1) per
quanto concerne la ricchezza espressiva, nella definibilità ricorsiva
degli assiomi e delle relazioni numeriche. Dall'asserto che ogni relazione
ricorsiva (primitiva) sia aritmetica (teorema VII)21, si arguisce la natura,
ugualmente aritmetica, della proposizione indecidibile (teorema VIII);
2) la correttezza contenutistica è rimpiazzata dalla ipotesi della
omega-coerenza. Per tale condizione, di nessuna formula A(x) con x variabile
libera, saranno dimostrabili tanto ciascuna delle infinite formule A(x)
con x numero naturale, che $(x) ~A(x).
Mentre la condizione di coerenza semplice basta a concludere la non
deducibilità di [R(q); q], assumere come dimostrabile la negazione
di [R(q); q] collude con la w-coerenza. Poiché infatti la w-coerenza
implica la coerenza semplice, e per quest'ultima la correttezza della definizione
per k richiede che, per qualunque n Î k, la formula risultante dalla
sostituzione di n non sia dimostrabile, per n = q la negazione di [R(q);
q] segnerebbe al tempo stesso un caso in cui ciò si nega.
Nel 1936 Barkley J. Rosser (Extensions of some theorems of Gödel
and Church) fornisce una versione del primo teorema di incompletezza, che
non necessita della w-coerenza. A tal fine, egli prospetta una proposizione
indecidibile •, significante che, per ogni numero di Gödel x di
una dimostrazione in P di •, esiste un numero di Gödel z Î
x di una dimostrazione in P di ~•.
Per Gödel invece: se ci limitiamo alla semplice coerenza, pur
non seguendo l'esistenza di una proposizione indecidibile, si ottiene,
in base alla non dimostrabilità di [R(q); q], una proprietà,
quella individuata dal concetto k, per la quale né si può
fornire un controesempio, né si può provare la sua chiusura
universale. Il sistema è allora w-incompleto.
Se aggiungiamo al nostro sistema come nuovo assioma la negazione di
[R(q); q], realizziamo un'estensione P* coerente ma non w-coerente. Coerente:
infatti se l'introduzione del nuovo assioma portasse a contraddizione,
sarebbe dimostrabile la negazione della negazione di [R(q); q], quindi
5. LA STRUTTURA DELL'ANTINOMIA
5.a. Diagonalizzazione
Un ragionamento metamatematico permette di decidere la proposizione indecidibile.
"Dall'osservazione che [R(q);q] dice di se stessa di non essere dimostrabile
segue anche che [R(q);q] è vera, dal momento che [R(q);q] in effetti
non è dimostrabile (essendo indecidibile)."22
[R(q);q] è, in virtù del procedimento di sostituzione
diagonale, autoreferenziale. In effetti, ricordando come [R(q); q] sia
il medesimo di [S ; q], con S segno di classe, di gödeliano q, per
la delimitazione di k, se [S; n], afferma: "n Î k", per [S; q] allora:
"q Î k". [R(q); q] si interpreta così contenutisticamente
in: "la proposizione che risulta sostituendo nella q-esima formula q non
è dimostrabile". Tale proposizione è appunto [R(q); q].
"A dispetto delle apparenze, una tale proposizione non contiene circoli
viziosi, poiché inizialmente essa afferma [soltanto] che una certa
formula ben definita ( cioè quella ottenuta dalla q-esima formula,
secondo l'ordine lessicografico, mediante una certa sostituzione) non è
dimostrabile. Solo successivamente ( e in un certo senso per caso) viene
fuori che questa formula è precisamente quella mediante la quale
era stata espressa la proposizione stessa."23
La diagonalizzazione fu ideata da Cantor (Über eine elementare
Frage der Mannigfaltigkeitslehre, 1890-91) per dimostrare che l'insieme
dei numeri reali ha potenza superiore a quella dei numeri naturali. Infatti,
supponiamo che l'insieme dei numeri reali compreso tra 0 e 1 sia numerabile,
e tracciamo una corrispondenza biunivoca con gli interi:
1 ® 0,157403... 2 ® 0,193217... 3 ® 0,317622... 4 ® 0,893910... ...
Consideriamo il nuovo numero reale, costruito in modo che lo sviluppo decimale differisca dalle cifre sulla diagonale in ogni punto corrispondente. Tale numero non compare nell'elenco, ma è diverso da ognuno dei numeri incolonnati per almeno una cifra decimale. Abbiamo quindi trovato un numero che non è in corrispondenza con un intero. In modo affine per Gödel, dopo avere correlato ogni formula al numero di Gödel della sua dimostrazione, costruiamo l'enunciato, tale per cui, per ogni n, n non è il numero di Gödel della sua dimostrazione/refutazione.
L'autoreferenzialità per diagonalizzazione è stata spesso sfruttata per effetti antinomici. In questo senso, Gödel afferma: "Qualunque antinomia epistemologica potrebbe venire utilizzata per un'analoga dimostrazione di esistenza di proposizioni indecidibili"24. Ma qui il procedimento diagonale serve piuttosto, secondo il ragionamento metamatematico, allo scioglimento dei paradossi.
5.b. L'antinomia di Richard
"Salta immediatamente agli occhi l'analogia fra questo ragionamento e l'antinomia
di Richard; esso è anche strettamente collegato al 'Mentitore'."25
Consideriamo in primo luogo l'antinomia di Richard. Si prenda una lingua,
ad esempio l'italiano, in cui siano definibili le proprietà dei
numeri naturali. Generiamo tutte le definizioni e procediamo a ordinarle
in base al criterio che una definizione preceda l'altra se contiene meno
lettere alfabetiche. A parità di numero di lettere, si privilegia
l'ordine alfabetico interno. In questa successione si associ ora a ogni
definizione il numero intero che ne individua il posto nella serie.
È chiara fin qui la somiglianza con il procedimento di Gödel:
si ordinino i segni di classe "per esempio, in ordine crescente di somma
della successione finita di interi che costituisce il 'segno di classe'
e lessicograficamente a parità di somma"26. Ogni elemento della
successione viene quindi associato al proprio numero di Gödel.
Tornando alla successione di Richard, si aprono due eventualità:
o un numero possiede la proprietà della corrispettiva definizione,
o non la possiede. Chiamiamo richardiano un numero che non gode della proprietà
espressa dalla definizione cui è associato. Anche questa è
una definizione rispetto a una proprietà di numeri naturali; quindi
appartiene alla serie già costituita. Sia k il numero che ne individua
il rango nella serie. K è richardiano?
Ma k è richardiano se e solo se non possiede la proprietà
indicata dalla definizione, con la quale è correlato; cioè
se non è richardiano.
Il paradosso scaturisce da una mancanza di distinzione tra i livelli
del discorso. Le definizioni dovevano riguardare proprietà aritmetiche
degli interi; ma la richardianità non è tale. È qui un nucleo
imperfetto dell'aritmetizzazione. Richard costruisce sulla teoria dei numeri
naturali una metateoria: l'insieme delle definizioni di proprietà
dei numeri naturali.
L'associazione di un numero a ogni definizione dovrebbe consentire
il ritorno della metateoria sulla aritmetica. Così dove Richard
fallisce, Gödel riesce innestando l'aritmetizzazione nella teoria
delle funzioni ricorsive.
5.c. Epimenide o il Mentitore
L'autoreferenzialità ci permette di collegare questo ragionamento
anche all'antinomia del mentitore. Sostituendo in 'questo enunciato è
falso' alla nozione di falso quella di non dimostrabile, pur mantenendo
la costruzione autoreferenziale, Gödel non produce paradosso. La fallacia
non discende quindi dall'autoreferenzialità27, ma dall'uso improprio
del concetto 'vero'. Gödel coglie una differenza essenziale tra i
concetti di 'verità' e di 'dimostrabilità': solo il secondo
è definibile per un sistema all'interno di quel sistema.
In generale è possibile "per ogni proprietà matematica
f che possa essere espressa nel sistema, costruire una proposizione che
dice di sé di possedere questa proprietà. (...) Questa costruzione
può essere eseguita solo se la proprietà f può essere
espressa nel sistema, e la soluzione del paradosso di Epimenide si trova
nel fatto che questa possibilità non si realizza per ogni proprietà
metamatematica"28. Si esamini infatti il seguente caso: A oggi dice: 'ogni
affermazione che A oggi pronuncia è falsa'. Ma A deve specificare
un linguaggio di riferimento B, rispetto cui valga la precedente affermazione.
Cioè 'ogni affermazione che A oggi pronuncia è falsa in B'.
Tuttavia 'affermazione falsa in B' non può essere espressa in B.
Quindi per Gödel "il paradosso può essere considerato una dimostrazione
che 'affermazione falsa in B' non può essere espressa in B"29.
A questo fatto Gödel collega, nelle lezioni tenute a Princeton
nel 1934, direttamente l'esistenza delle proposizioni indecidibili. Generalizzando
il metodo per diagonale, e ponendo ~T come negazione della proprietà
di verità per una proposizione, "potremmo applicare il nostro procedimento
a ~T (S(w,w)) e ottenere ~T (S(zp, zp)), che dice di sé di essere
falsa"30. Poiché S esprime la relazione di sostituzione e p è
il numero di Gödel di ~T (S(w,w)) con zp per Zahl p, S(zp, zp) è
quanto al concetto di "non vero" il corrispettivo della formula descritta
in [(Rq); q] quanto al concetto di 'non Bew'. Ma nel caso della proprietà
espressa da ~T si produce subito contraddizione, poiché la nozione
di verità è, nella logica classica, soggetta al principio
del terzo escluso, quindi una proposizione o è vera o è falsa.
Non così per la nozione di dimostrabilità. "D'altra parte,
SvB(v, zk) è un'affermazione nel sistema del fatto che la formula
con numero k è dimostrabile."31
Questo passo può essere meglio compreso alla luce di quanto
Gödel scrive a Zermelo in una lettera del 12.10.31. La dimostrabilità
può essere definita nel sistema, perché essa è una
proprietà puramente combinatoria, formale. Vale a dire, può
essere considerata in modo esclusivamente sintattico32. Perciò
la classe delle formule dimostrabili è riconducibile, mediante aritmetizzazione,
ai segni di classe del sistema formale. Ma ciò non vale per la proprietà
di correttezza (verità), che al significato si appoggia. "Allora
vediamo che la classe a dei numeri di formule vere non può essere
espressa da una funzione proposizionale del nostro sistema, mentre la classe
b delle formule dimostrabili lo può."33 La classe delle formule
dimostrabili non è coestensiva alla classe delle formule vere; e
poiché ogni formula dimostrabile è vera, b Í a. Perciò
esiste almeno una proposizione A, che è vera ma non dimostrabile.
Essendo tale proposizione vera, nemmeno ~A sarà dimostrabile:
A è indecidibile.
6. IL CONCETTO "VERO"
La dimostrazione qui offerta dell'esistenza di proposizioni indecidibili
in un sistema, non ne fornisce tuttavia alcun esempio specifico. Per questo
motivo forse, l'argomento non compare nello scritto del 1931. La mancanza
di costruibilità, come si legge ancora nella lettera a Zermelo,
lo avrebbe reso vulnerabile agli attacchi degli intuizionisti34.
Ciò consente però di considerare l'incompletezza di un
sistema da due punti di vista: rispetto alla presenza in esso di enunciati
indecidibili; e rispetto alla non definibilità nello stesso di concetti
quale quello di verità. Gödel rinvia per la trattazione più
dettagliata dell'argomento al saggio di Alfred Tarski (1933), il cui obiettivo
è delimitare le condizioni di verità di un enunciato per
un linguaggio oggetto L35.
Tarski pensa in primo luogo di fondare la semantica come parte della
morfologia (sintassi) del linguaggio oggetto, cioè di produrre un
sistema coerente e semanticamente chiuso. Egli si basa su una concezione
semantica di verità come corrispondenza al reale: diciamo che l'enunciato
"la neve è bianca" è vero, se la neve è bianca. Per
la definizione di verità, Tarski richiede che si realizzino due
condizioni:
1) una condizione di adeguatezza materiale, per la quale, dato un
linguaggio L, ogni equivalenza del tipo:
("la neve è bianca" è vero) « la neve è bianca
deve poter essere provata nel metalinguaggio. Il simbolo Wr, che designa
la classe di tutti gli enunciati veri, è, nei termini del metalinguaggio,
così circoscritto mediante lo schema:
x Î Wr « p
con x nome strutturale descrittivo di un enunciato qualunque del linguaggio
oggetto (per esempio l'enunciato "la neve è bianca") e p la traduzione
dell'enunciato stesso nel metalinguaggio. Ogni enunciato vero sarà
deducibile dallo schema;
2) una condizione di correttezza formale, vale a dire la definizione
di verità non deve portare a contraddizioni.
Considerando ora un linguaggio L di ordine infinitario, capace di
esprimere l'aritmetica, Tarski constata che, se l'insieme di tutti i teoremi
della metascienza è non contraddittorio, risulta impossibile pervenire
a una definizione adeguata della verità. Poiché infatti il
metalinguaggio contiene L come sua parte e, accanto a ogni enunciato di
L, il nome che nel metalinguaggio designa quell'enunciato, se si
riuscisse a costruire per L una definizione adeguata di verità,
il metalinguaggio acquisirebbe quel carattere universalistico che, rendendolo
atto a "parlare" di qualsiasi cosa, lo esporrebbe alla genesi di antinomie.
In particolare sarebbe riproducibile l'antinomia del mentitore: per un
enunciato x del linguaggio L, esisteranno nel metalinguaggio una
formula che afferma la verità di x, e una formula che afferma la
falsità di x.
Tarski esibisce la contraddizione cercata, mettendo in corrispondenza,
secondo il metodo di Gödel 31, la classe degli enunciati Wr con una
classe di numeri naturali. Egli considera quindi l'espressione:
(1) 
(in . jn) Ï Wr
che rappresenta nel metalinguaggio il nome di una funzione enunciativa,
con "n" come unica variabile libera. Nella notazione di Tarski il simbolo
i designa una funzione di identità numerica; ne introduce
la quantificazione esistenziale rispetto alla sua prima variabile del terzo
ordine, cioè "n". Tarski correla alla (1) una funzione, equivalente
ad essa per qualsiasi valore di "n", e totalmente espressa in termini aritmetici.
Rappresentando tale funzione con "y(n)", risulta:
(2) (in . jn) Ï Wr se e solo se y(n).
Come elemento della successione ordinata di funzioni j del linguaggio
L, "y(n)" ha un certo indice k, cioè: "y(n)" = jk. Per sostituzione
si ottiene dunque:
(3) (ik . jk) Ï Wr se e solo se y(k).
Ma (ik . jk) indica a sua volta un enunciato di L, cui si
applica la condizione: x Î Wr « p; perciò:
(4) (ik . jk) Î Wr se e solo se y(k).
In conclusione, la riduzione dei concetti semantici a concetti strutturali
si rivela solo parziale. Per i linguaggi 'ricchi' sussiste infatti un impedimento
basilare: sembra impossibile costruire un concetto di soddisfazione generale
e semanticamente univoco, applicabile a tutte le funzioni enunciative.
Per ogni concetto semantico, si può invece formulare un numero infinito
di definizioni parziali, senza alcun mezzo che autorizzi il passaggio automatico
da queste definizioni parziali a una definizione comprensiva. La verità
degli enunciati di L sarà quindi indefinibile in L, ma definibile
in una estensione di quel linguaggio L* al tipo immediatamente più
elevato. Il metalinguaggio deve cioè possedere un ordine più
alto di quello del linguaggio oggetto; pena l'antinomia.
Si veda in proposito la recensione di Gödel Besprechung von Rudolf
Carnap, "Die Antinomien und die Unvollständigkeit der Mathematik":
ogni linguaggio può essere esteso in modo da contenere un concetto
di 'vero', che soddisfa la prerogativa dell'attribuzione autoreferenziale
per tutti gli enunciati del linguaggio originario, ma non per gli enunciati
del linguaggio esteso36.
Così l'insieme dei numeri di Gödel della classe degli enunciati
veri non è uguale a quello della classe dei teoremi. "La vera ragione
per cui l'incompletezza è intrinseca a tutti i sistemi formali per
la matematica consiste nel fatto che è sempre possibile estendere
nel transfinito la formazione di tipi sempre più elevati, mentre
in qualunque sistema formale ne sarà disponibile solo una quantità
al massimo numerabile"37. Se il concetto di verità matematica è
transfinito, stante la relazione di inclusione, tutte le proposizioni dimostrabili
risultano senz'altro vere e, per lo stesso motivo, le proposizioni indecidibili
"diventano decidibili con l'aggiunta di tipi superiori e degli assiomi
corrispondenti; ciò nonostante nei sistemi di ordine superiore possiamo
costruire con lo stesso metodo altre proposizioni indecidibili e così
via"38. Le proposizioni così costruite sono esprimibili nel sistema,
poiché permane nelle estensioni la rappresentabilità delle
funzioni ricorsive primitive, e in particolare di quelle individuate da
Gödel 31. Ma la loro decidibilità resta assegnata a tipi superiori.
Il contrario segnerebbe infatti la avvenuta cattura ricorsiva della proprietà
'vero'. Ne segue che gli assiomi dell'aritmetica, se coerenti, sono essenzialmente
incompleti.
7. IL SECONDO TEOREMA DI INCOMPLETEZZA
La conclusione che [R(q); q] è, oltre che indimostrabile, vera
dà luogo, sotto la condizione della coerenza di P, al secondo teorema
di incompletezza. Se P è coerente, allora la formula W, che esprime
la coerenza di P, non è dimostrabile in P. Poiché infatti
la non dimostrabilità di [R(q); q] è stata ricavata dalla
sola coerenza, vale:
Wid(P) ® 
[R(q); q].
Ma Wid(P): "P è coerente" equivale a: "esiste almeno una formula
non dimostrabile in P", esprimibile come:
($x)(Form(x) & (x)).
Quest'ultima d'altra parte ha già una formula che la rappresenta
ed è la stessa [R(q); q]; quindi:
W ® [R(q); q].
Gödel afferma che W ® [R(q); q] è dimostrabile in P39.
Allora, se fosse dimostrabile W, per modus ponens seguirebbe anche [R(q);
q]: da ciò l'incoerenza del sistema.
Rispetto alle conseguenze di questo risultato per il programma di Hilbert,
Gödel puntualizza nello scritto del 1931 come non si escluda la plausibilità
di una dimostrazione matematica della coerenza dell'aritmetica. Ma tali
dimostrazioni dovrebbero non trovarsi tra quelle già sviluppate.
Il sistema P infatti, come variante di quello dei Principia, è stato
scelto proprio perché in esso risultano formalizzabili tutti i metodi
di dimostrazione in uso. Un'ulteriore indicazione viene dal poscritto alla
relazione di Königsberg. Gödel vi asserisce l'impossibilità
in generale di una dimostrazione di coerenza, nel senso perseguito dai
formalisti, per un sistema in cui siano formalizzabili tutti i metodi finitari
di dimostrazione. "Resta tuttavia dubbio che uno dei sistemi sino ad oggi
noti, per esempio quello dei Principia Mathematica, sia così comprensivo
(o addirittura che possa esistere un sistema siffatto)."40 Con questo
dubbio, si chiarisce che escluso non è tanto il ricorso in sé
a metodi finitari, quanto che abbia senso una dimostrazione di coerenza
assoluta, proprio nell'accezione di internalizzabile nello stesso sistema
di cui si vuole provare la non contraddittorietà.
Il suggerimento all'impiego di metodi non elementari venne accolto
da Gerhard Gentzen, che nel 1936 (Die Widerspruchsfreiheit der reinen
Zahlentheorie) dimostrò la coerenza dell'aritmetica con l'aggiunta
ai principi finitari in uso di una regola di induzione transfinita. La
regola di induzione transfinita è semplicemente la regola di induzione
completa (dal quinto postulato di Peano), estesa dai numeri naturali agli
ordinali transfiniti.
La si può dunque formulare in questi termini: se una proprietà
(o una proposizione) vale per il numero 1, ed è provato che la sua
validità, per ogni numero che precede n, comporta che essa valga
per n, allora tale proprietà vale per tutti i numeri transfiniti.
Il nesso tra la prova di consistenza della teoria dei numeri e la regola
di induzione transfinita è da Gentzen con eleganza evidenziato.
Osservando inizialmente che la correttezza di una dimostrazione dipende
dalla correttezza di altre dimostrazioni più semplici, che ne costituiscono
come delle parti, Gentzen propone di disporre in successione, secondo il
criterio della semplicità, tutte le dimostrazioni dell'aritmetica,
associando a ognuna di esse un numero transfinito.
La necessità di ricorrere a ordinali transfiniti è motivata
dalla constatazione che la correttezza di una certa dimostrazione può
discendere dalla correttezza di infinite altre. Ma se stabiliamo la correttezza
della dimostrazione numero 1, e proviamo inoltre che sono corrette tutte
le dimostrazioni che precedono una dimostrazione avente numero n, questo
implica, di nuovo, la correttezza della n-esima dimostrazione; e con ciò,
per induzione transfinita, in generale di tutta la gerarchia delle dimostrazioni
dell'aritmetica, di cui risulta la consistenza desiderata.
Gentzen ritiene che il procedimento così individuato adempia
alle richieste di costruttività, che accomunano la scuola hilbertiana
a quella intuizionista, mantenendo al tempo stesso l'ideale regolativo
della scelta di metodi finitari. E' infatti possibile circoscrivere la
strategia di impiego e il significato degli ordinali transfiniti, in modo
da evitare rigorosamente ogni riferimento a una loro interpretazione attualista.
I numeri ordinali transfiniti sono infatti generati grazie alla reiterata
applicazione di due sole operazioni:
1) per un numero che già esiste, formarne il successore;
2) per una successione infinita di numeri, formare un nuovo numero,
che segua l'intera successione, e che ne sia il limite.
Le medesime considerazioni giustificano l'applicazione della regola
di induzione transfinita, senza che mai si valichi il confine di una lettura
del concetto di infinito nella chiave del potenziale. Si può infatti
con Gentzen asserire che, se una proposizione vale per il numero 1, e così
pure per il numero 2, 3, ecc., e in definitiva per tutti i numeri naturali,
di conseguenza vale anche per il numero w, che in quanto è limite
per i numeri naturali e insieme primo numero transfinito, sta con ogni
numero naturale n nella relazione d'ordine n < w. Allora la stessa proposizione
si predica di w+1, w+2, ..., w+n, e così di seguito, penetrando
nella catena degli ordinali transfiniti.98
Ritornando a quanto scrive Gödel nel poscritto alla relazione
di Königsberg, "la proposizione che esprime la coerenza del sistema
è una delle proposizioni indecidibili del sistema stesso"41.
Quindi nel rimando al rapporto di inclusione della classe delle proposizioni
dimostrabili nella classe delle proposizioni vere, ciò dovrebbe
legittimare l'uso di concetti ideali, con un ritorno, comunque accettabile
costruttivamente, perché la prova di coerenza relativa che così
si genera è compatibile con i parametri finitari. In una lettera
a Hao Wang, circa la dimostrazione di coerenza dell'ipotesi del continuo,
Gödel scrive: "Una interpretazione di questo genere (come qualsiasi
dimostrazione non finitaria di coerenza) produce una dimostrazione finitaria
di coerenza relativa". E, rispetto ai teoremi di incompletezza: "Di nuovo,
l'uso di questo concetto transfinito (di verità matematica obiettiva)
conduce, in fin dei conti, a risultati dimostrabili finitariamente, per
esempio ai teoremi generali sull'esistenza di proposizioni indecidibili
in sistemi formali coerenti"42.
Ma mentre decade l'equivalenza auspicata da Hilbert tra sintassi e
semantica, il risultato di incompletezza sintattica si trasforma in quello
di incompletezza semantica, passando alla logica dei predicati del secondo
ordine. Poiché il sistema per l'aritmetica diviene ora categorico,
cioè ammette un solo modello, a meno di isomorfismi, riescono indimostrabili,
in quanto indecidibili, proposizioni che sono valide nel modello.
NOTE
1. Gödel, K., "Diskussion zur Grundlegung der Mathematik", (Trascrizione dell'intervento di Gödel al Congresso di Königsberg, 5-7 sett. 1930), pubblicata su Erkenntnis, 2 (1931), pp. 147-151; trad. it. di E. Ballo, "Discussione sulla fondazione della matematica" in Gödel, K., Opere; Vol. I, op. cit., pp. 143-145, cit. da p. 143.
2. Gödel, K., ibidem, pp. 143-144.
3. Gödel, K., ibidem, p. 144.
4. Kurt Gödel a Hao Wang, lettera del 7.12.67, in Wang, H., op. cit., p. 19.
5. "Nonostante le sue convinzioni profonde sulla oggettività del concetto di verità matematica, Gödel temeva che un lavoro che partisse da questo concetto sarebbe stato rifiutato dalla comunità degli studiosi dei fondamenti, dominata com'era dalle idee di Hilbert." (Feferman, S., "Kurt Gödel: Conviction and Caution", Relazione al congresso di Salzburg, 11-16 luglio, 1983, pubblicata in P. Weingartener, C. Pühringer (a cura di), Philosophia Naturalis, 21, Meisenheim/Glan, Anton Hain, 1984, pp. 546-562; rist. in Shanker, S. G. (a cura di), Gödel's Theorem in focus, Croom Helm, London, 1988; trad. it. di P. Pagli, "Kurt Gödel: fede e cautela", in Shanker, S. G. (a cura di), Il teorema di Gödel. Una messa a fuoco, Muzzio, Padova, 1991, pp. 119-141, cit. da p. 133.) Nel testo del '31 Gödel utilizza infatti l'aggettivo 'richtig'('corretto') e non 'wahr' ('vero').
6. Gödel, K., "Über formal unentscheidbare Sätze der 'Principia Mathematica' und verwandter Systeme I", Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198; trad. it. di E. Ballo, "Proposizioni formalmente indecidibili dei 'Principia Mathematica' e di sistemi affini I", in Gödel, K., Opere; Vol. I, op. cit., pp. 111-138, cit. da p. 113. È interessante ricordare che Gödel arrivò ai risultati di incompletezza, mentre cercava una dimostrazione di coerenza dell'Analisi con metodi finitari. Pensando allora di ridurre la coerenza dell'Analisi a quella della teoria dei numeri, si imbatté nel problema di provare, oltre alla coerenza, anche la verità di tale teoria. Da qui, passando all'esame dei paradossi di Richard e del Mentitore, egli si accorse che si poteva costruire un analogo formale di quest'ultima antinomia, con specifiche proprietà autoreferenziali, grazie a una diagonalizzazione interna all'aritmetica. Quindi se la verità della teoria dei numeri fosse definibile nell'aritmetica stessa, potremmo riprodurre in essa una versione rigorosa del Mentitore: l'aritmetica sarebbe allora contraddittoria.
7. P è ottenuto dal sistema dei Principia omettendo la ramificazione dei tipi, aggiungendo gli assiomi di Peano, e considerando come individui i numeri naturali e come primitiva l'operazione di passaggio al successore (n+1).
8. Gödel, K., "Proposizioni formalmente indecidibili dei 'Principia Mathematica' e di sistemi affini I", op. cit., p. 113.
9.Gödel, K., ibidem, p. 114. Gödel associa a ogni segno primitivo di P un numero naturale nel modo seguente:
0 f ~ Ú P ( ) 1 3 5 7 9 11 13
con f iniziale di folgen, successore. Quindi a ogni successione finita di numeri naturali n1, n2, ..., nk, fa corrispondere il singolo numero:
con pk che denota il k-esimo numero primo.10. Gödel, K., ibidem, p. 114, nota 9.
11. Gödel, K., ibidem, p. 114.
12. Gödel, K., ibidem, p. 114.
13. Gödel, K., ibidem, p. 114. Decidibile traduce entscheidungsdefinit.
14.L'elenco comprende tra gli altri i concetti di: assioma; formula; sostituzione; conseguenza immediata. Il concetto espresso al punto 45 con yBx (y è il numero di Gödel di una dimostrazione della formula che ha gödeliano x), rientra nella definizione di quanto indicato al punto 46, cioè: Bew(x)º($y)yBx (la formula che ha numero di Gödel x è dimostrabile se e solo se esiste una sua dimostrazione di godeliano y), dove Bew sta per beweisbar.
15. Gödel, K., ibidem, p. 115.
16. Gödel, K., ibidem, p. 115.
17. Gödel, K., ibidem, p. 115.
18.Gödel, K., ibidem, p. 115. Gödel si premura di osservare che "[R(q); q]" non è la proposizione indecidibile, ma la sua descrizione metamatematica. La formula effettiva, costruita nell'immagine isomorfa di PM, sarà 17 Gen r, ottenuta dalla relazione Q(x,y) º
![[Sb(y con apice 19 e pedice z(y))]](sby.gif){kind=small}
: x non è il numero di Gödel di una dimostrazione
della formula indicata con .Quest'ultima espressione viene
a designare, nell'ambito del calcolo aritmetico formalizzato: "il numero
di Gödel della formula generata dalla formula che ha numero di Gödel
y, sostituendo nella variabile libera con numero 19, il numerale di y".19.Gödel, K., ibidem, p. 115.
20.Gödel, K., ibidem, p. 116.
21.Si dice aritmetica quella relazione che può essere definita mediante le operazioni di addizione e moltiplicazione tra i numeri naturali e le costanti logiche di disgiunzione inclusiva, negazione, quantificazione universale e identità, con quantificazione e identità applicate soltanto ai numeri naturali.
22.Gödel, K., ibidem, p.116.
23.Gödel, K., ibidem, p. 116 nota 15.
24.Gödel, K., ibidem, p. 115, nota 14.
25.Gödel, K., ibidem, p. 115.
26.Gödel, K., ibidem, p. 115, nota 11. Per un confronto dettagliato tra la costruzione dell'enunciato di Gödel e l'antinomia di Richard, si può leggere Agazzi, E., Introduzione ai problemi dell'assiomatica, Vita e Pensiero, Milano, 1961, che in appendice offre la prima traduzione italiana dell'articolo del 1931, preceduto da una chiara legenda sulla notazione usata da Gödel.
27.Rispetto alla interpretazione, sviluppata nei Principia, delle antinomie come violazioni del principio del circolo vizioso, e perciò fallacie riflessive, Gödel commenta: "La soluzione suggerita da Whitehead e Russell, che una proposizione non può fare alcuna affermazione su se stessa, è troppo drastica. Abbiamo visto che possiamo costruire proposizioni che fanno affermazioni su se stesse, e, in verità, si tratta di proposizioni aritmetiche che coinvolgono solo funzioni definite ricorsivamente, e perciò sono senza dubbio affermazioni dotate di senso." Gödel, K., "On undecidable propositions of formal mathematical systems", Princeton (N.J.), Institute for Advanced Studies, 1934; trad. it. di G. Lolli, "Sulle proposizioni indecidibili dei sistemi matematici formali" in Gödel, K., Opere; Vol.I, op. cit., pp. 252-276, citazione da p.268.
28.Gödel, K., ibidem, p. 268. Gödel fornisce qui una enunciazione informale del lemma dell'autoriferimento (o di diagonalizzazione). Se F(n) significa: "la formula che ha numero di Gödel n gode della proprietà f", e n è il numero di N, F(n) º N. Perciò se F(S(x,x)) ha numero di Gödel p, F(p,p) dice di sé di possedere la proprietà f.
29.Gödel, K., ibidem, p. 268.
30.Gödel, K., ibidem, p. 268.
31.Gödel, K., ibidem, p. 268. In questo caso il simbolo S indica un quantificatore esistenziale. La formula equivale quindi alla componente definitoria del concetto n. 46 dello scritto del 1931, cioè per esempio: Bew(zk)º($n)nB(zk).
32."Die Eigenschaft einer Formel, beweisbar zu sein, ist eine rein kombinatorische (formale), bei der es auf die Bedeutung der Zeichen nicht ankommt." (Grattan-Guinness, I., "In memoriam Kurt Gödel: his 1931 correspondence with Zermelo on his incompletability theorem", Historia mathematica, 6 (1979), pp. 294-304, cit. da p. 300.)
33.Gödel, K., "Sulle proposizioni indecidibili dei sistemi matematici formali", op. cit., p. 269. Questo equivale a dire che la classe dei numeri delle proposizioni corrette, a differenza di quella dei numeri delle proposizioni dimostrabili, non è riconducibile a un segno di classe: "Die Klasse W der richtigen Formeln ist niemals mit einem Klassenzeichen desselben System umfangsgleich". (in Grattan-Guinness, I., op. cit., p. 300.)
34."Weil aber B
W, so gilt B Í W d.h. es gibt
eine richtige Formel A, die nicht beweisbar ist. Weil A richtig ist, so
ist auch non-A nicht beweisbar, d.h. A ist unentscheidbar. Dieser Beweis
hat aber den Nachteil, dass er keine Konstruktion des unentscheidbaren
Satzes liefert und intuitionistisch nicht einwandfrei ist." (ibidem, p.
301.)35.Tarski, A., "Der Wahrheitsbegriff in den formalisierten Sprachen", Studia philosophica, Lemberg, 1, (1935), pp. 261-405; trad. tedesca di L. Blaustein dall'originale polacco del 1933; trad. it. dal tedesco, rivista sul testo polacco, "Il concetto di verità nei linguaggi formalizzati", in Rivetti Barbò, F. L'antinomia del mentitore nel pensiero contemporaneo: da Pierce a Tarski, Vita e pensiero, Milano, 1961, pp. 391-677.
36.Poiché la proprietà metamatematica 'vero' non può essere espressa nel sistema, la costruzione autoreferenziale è, come indicato nelle lezioni di Princeton, un uso improprio di quel concetto e, in quanto tale, porta all'antinomia. "Vale a dire, più precisamente, che si assume falsamente che esista un concetto B(vero) per cui per ogni enunciato A la formula
B("A")º A
è dimostrabile. Dall'emergenza delle antinomie si può concludere che un tale concetto B non può essere espresso in alcun linguaggio non contraddittorio." Si vede chiaramente l'applicazione del lemma dell'autoriferimento. Gödel, K. "Besprechung von Rudolf Carnap 193", Zentralblatt für Mathematik und ihre Grenzgebiete, 11 (1935), p. 1; trad. it. di G. Lolli, "Recensione di Carnap 1934", in Opere; Vol. I, op. cit., p. 290.
37.Gödel, K., "Proposizioni formalmente indecidibili dei 'Principia Mathematica' e di sistemi affini I", op. cit., p. 131 nota 48a.
38.Gödel, K. "Über Vollständigkeit und Widerspruchsfreiheit", Ergebnisse eines mathematischen Kolloquiums, 3 (1932) pp. 12-13; trad. it di S. Bozzi, "Su completezza e coerenza",in Opere; Vol I, cit. pp. 170-171.
39.Gödel intendeva dare dettagliata prova della dimostrabilità di W ® [R(q);q] in una successiva parte dello scritto del 1931. Ciò non accadde; una prima dimostrazione venne invece offerta da Hilbert e Bernays nel volume II dei Grundlagen der Mathematik (1939). "Wid", o soltanto "W", sta per widerspruchsfrei.
40.Gödel, K., "Discussione sulla fondazione della matematica", op.cit., p. 145.
41.Gentzen ritiene che con la stessa strategia si possano provare la consistenza dell'analisi e della teoria degli insiemi; tuttavia è necessario, per questo fine, dilatare il segmento degli ordinali utilizzati. Dallo scritto di Gentzen emerge un'immagine della matematica ripartita su tre livelli, ognuno dei quali viene determinato dal modo in cui il concetto di infinito vi occorre. Il livello più basso corrisponde alla teoria elementare dei numeri, dove la dimensione dell'infinito in gioco è quella più scarna di una serie passo per passo estesa, la cui totalità d'insieme rimane sempre in potenza. Il secondo livello abbraccia l'analisi, i cui oggetti, i numeri reali, vengono ora considerati come insiemi infiniti (nel senso in cui ogni insieme sia pensabile come una successione infinita). Al terzo livello, quello della teoria degli insiemi, la complessità raggiunta dal concetto di infinito è massima, poiché qui si ammettono come oggetti, oltre agli insiemi infiniti di oggetti del livello precedente, insiemi di insiemi, ecc. con un'iterazione protratta a piacere.
42.Gödel, K., "Discussione sulla fondazione della matematica", op. cit., p. 145.
43.Kurt Gödel a Hao Wang, 7/12/1967, in Wang, H., op. cit., p.19.