Moriconi - I Teoremi di Gödel

��

��

� ��

��

�� !��"�##$%�&'()

��

��

��

*�� +� ��,��

�-�� ,� ��

�-�� ,��-��

�� ,�� .� �/��!

��0�- ��1/�� +�� -+��!�2��-�� +� �� -�� !

�� 0�� 3��4�� 5�� +� ��!��0�- ��1�� /� ��-��- ��0�- ��-�� +�!�� 6�-��6�-��/��-�� - �+� �+�� /�� - �� +��+�� /��+��7��+�� /��7�� -��7�� -� ��/� ��6�+��- �� +�� -��+� �� -�� +�� !�� 0�8-�� -�� - 6�� -�8-�� +� ��+�� +�� /�� - �� /��- ��-�� +�� !

�-�� 9��-��!�2�� -��-��+� �� !�� /�� /�� /��-��/�� /��-��.:��+�� 6�� +� ��!�;�� -��-��+�� /�0��6-�� +��<��-��<�!

;��8-� �� -�� 8-��/��+� ��7�� +��-��5�-�� -��3��4��/===!�=��!��<��<� ��>��?!�.�!

;��- �� -�� -� �� ,

@A��/�� /�� !��B��-��C/��/��/�$))%/��"�##$%�&'()/��!�D/�===!�=��!��<��<��!

��

� �� E+�� 4��!- ��!��F�.��-��-��"��+��-��;��0��-�� 3�� #G'H�� - ��-��+�� !�I��!�@��-��+� ��0�� +� ��;��!��-�� +� ��+�� +� ��+��+��!��-�8-��+� ��.��-��-+�!��7�� +��-+�� /��+��$))#�B� �� !�3��!�� C��J��+��+��J� ��-+��B��-��"!�K��C/�� $))H/�� !�� "�� #�$��%$��&�'��(/�� ? �.��$))H!

�� 8-��0��-�� !

SWIF – Linee di Ricerca

I TEOREMI DI GODEL

Enrico Moriconi

Versione 1.0

1 Introduzione

I teoremi di Godel costituiscono forse i piu importanti, e senz’altro i piu

noti, risultati ottenuti nel campo di ricerca logico-matematico. Dopo una

faticosa fase di ricezione, sono ormai da tempo diventati parte del “senso

comune” anche in discipline non strettamente tecniche; oppure tecniche, ma

non specificatamente logico-matematiche. Spesso se ne parla discutendone

e valutandone le conseguenze –per la logica, la matematica, i fondamenti

della matematica, la filosofia della matematica, la filosofia della scienza, la

filosofia della mente, le scienze cognitive, . . .– dando per scontato il proces-

so dimostrativo che ne e stato alla base1. Oppure capita che si forniscano

dimostrazioni estremamente generali del teorema, al fine di individuare le

condizioni che una teoria qualsiasi deve soddisfare per dimostrare i risultati

godeliani, con la conseguenza che si perde di vista lo specifico percorso se-

guito da Godel, nel senso che fra queste dimostrazioni e quella originaria si

puo stabilire una relazione analoga a quella esistente fra il teorema canto-

1Si vedano ad esempio Cellucci [1998], Cellucci [2002] e Lolli [1992].

E. Moriconi - I teoremi di Godel - Versione 1.0 715

riano della non-numerabilita del continuo e la dimostrazione di Liouville che

permette di costruire effettivamente numeri trascendenti2

In queste pagine si intende invece cercare di ripercorrere il viaggio

originario di Godel nella convizione che, senza assolutamente voler sminuire

il grande rilievo di quelle generalizzazioni, esso mantenga una notevole fre-

schezza teorica e un notevole interesse euristico. A questo fine, dopo un breve

inquadramento storico, seguiremo i passi compiuti da Kurt Godel, per poi

proporre qualche breve valutazione del significato generale di quei teoremi3.

2 La preistoria

Capire e valutare il significato dei risultati di incompletezza dell’aritmetica,

ottenuti da Godel nel corso del 1930, comunicati nel settembre di quello stesso

anno al famoso Congresso di Konigsberg, e pubblicati nel 19314, richiede

2E questa una tendenza iniziata probabilmente da S. C. Kleene in Kleene [1952]. Su questastessa lunghezza d’onda si veda ad esempio la compatta e senz’altro efficace trattazio-ne in Casari [1997]. Interessanti, a questo proposito, le osservazioni dello stesso Godelin una nota del 1965 quando, a proposito degli “Equivalenti diofantei delle proposizioniindecidibili”, diceva:

Si noti che questo ragionamento puo essere trasferito in modo pienamentepreciso a ogni sistema le cui formule abbiano un ben-definito significato, pur-che gli assiomi e le regole di inferenza siano corrette per questo significato enel sistema sia contenuta l’aritmetica. Si ottiene cosı una prova dell’esistenza

di proposizioni indecidibili in quel sistema, ma nessun particolare esempio diuna proposizione indecidibile (Godel [1986], p.363).

3Non ci occuperemo di molti dei dettagli piu tecnici. Per quest’ultimi, e per molti risultaticonnessi con quelli godeliani, rimandiamo alla trattazione in Bellotti et al. [2001] e allabibliografia lı indicata. Uno sguardo generale sui risultati godeliani lo si trova in Shanker[1991], mentre una raccolta di testi (in traduzione inglese e con utili introduzioni) con-nessi con la memoria godeliana, nonche questa stessa memoria, la si puo trovare in vanHeijenoort [1967]

4Ristampati in Godel [1986].


che essi vengano inquadrati nel quadro teorico determinato dal programma

fondazionale proposto da David Hilbert nel corso degli anni ’20.

2.1 Noncontraddittorieta come garanzia dell’esistenza

Schematicamente, possiamo distinguere tre fasi nella riflessione hilbertiana.

La prima e legata alla natura dell’assiomatica formale, o esistenziale, da lui

proposta con le Grundlagen der Geometrie del 1899. A differenza della assio-

matica classica, euclidea, qui non si procede dichiarando anticipatamente che

cosa siano gli enti di cui la teoria si occupa: la natura di questi risulta infatti

determinata proprio dalla formulazione, per l’appunto fatta dagli assiomi, dei

rapporti che valgono fra quegli enti. Questo significa che non c’e piu alcun

“modello” privilegiato della teoria e che il nesso che lega assiomi e teoremi

e precisamente il nesso di conseguenza logica: di qualsiasi sistema di oggetti

siano veri gli assiomi, di esso saranno veri anche i teoremi. Che cosa siano

“punti”, “rette” e “piani”, che cosa significhi “giacere su”, ecc. e qualcosa

che risulta definito implicitamente dagli assiomi. Chi obietto contro questa

impostazione fu Gottlob Frege che ebbe un breve, ma epistemologicamente

molto importante, scambio epistolare con Hilbert tra la fine dell’800 e l’inizio

del ’900. Il punto sottolineato da Frege era che gli enunciati adottati come

assiomi non potevano svolgere sia il ruolo di assiomi sia quello di definizioni.

Un assioma, infatti, deve essere un enunciato, cioe un’espressione suscettibi-

le di ricevere un valore di verita (e in particolare deve essere un enunciato

vero), ma questo richiede (per la composizionalita) che sia conosciuto il si-

gnificato di tutte le sue parti. Cosa impossibile se in esso compaiono termini

il cui significato non e gia noto. D’altra parte, se quei termini gia possiedono


un significato, indipendentemente e precedentemente al loro comparire negli

enunciati proposti come assiomi, allora che senso ha attribuire a quest’ultimi

anche il ruolo di definizioni? A cio Frege aggiungeva che per lui c’era un solo

modo di provare la noncontraddittorieta di un sistema di assiomi: esibirne

un modello.

Hilbert rispose in maniera molto netta a queste osservazioni. Ribadita

la concezione ipotetico-deduttiva dell’assiomatica, sottolinea poi che

Se assiomi arbitrariamente stabiliti non sono in contraddizione

con tutte le loro conseguenze, allora essi sono veri, allora esistono

gli enti definiti per mezzo di quegli assiomi. Questo e per me il

criterio della verita e dell’esistenza.5

Viene qui stabilita l’equazione fra esistenza e noncontraddittorieta che ca-

ratterizza questa prima fase dell’indagine hilbertiana: l’assunzione da cui

prende le mosse l’assiomatizzazione della geometria (“Siano dati tre sistemi

di enti, il primo lo chiamiamo il sistema dei punti e per essi usiamo le lettere

x, y, z, . . .”) verra per cosı dire scaricata da una prova di noncontradditto-

rieta, la quale dimostra che il sistema degli assiomi e un sistema di pensieri

possibile, cioe che ne esiste almeno un modello (anche se, va detto, non

necessariamente quello inteso)6.

5Risposta di Hilbert a Frege del 29/12/1899, tradotta in Frege [1965], pag. 464.6Su questi temi si possono vedere i miei Moriconi [2001] e Moriconi [2003] e la bibliografiaivi ricordata.


2.2 Le dimostrazioni come “oggetti” di un’indagine matematica

La seconda fase delle indagini hilbertiane e costituita dalla sua reazione alle

antinomie, o paradossi, scoperte all’inizio del secolo. Nella memoria del 1904

Hilbert [1904]7 troviamo i primi elementi di quella che sara la “teoria della

dimostrazione” di Hilbert: non si puo fondare la matematica sulla logica

poiche le due discipline devono invece essere sviluppate insieme assumendo

come dati intuitivamente una serie discreta e concretamente dominabile di

segni:

|, ||, . . .

i cosiddetti “numerali” (Zahlzeichen). La tesi di Hilbert e che il tipo di

evidenza intuitiva necessaria per la manipolazione di questi segni concreti

e cio che deve essere impiegato per fornire la prova di noncontraddittorieta

del sistema degli assiomi. A questo fine, e questa e l’importante novita con-

tenuta in questa memoria, e necessario sottoporre l’oggetto dimostrazione

a un’indagine di tipo matematico. Questa impostazione di evidente sapore

kantiano (la ragione deve sottoporre a critica i suoi strumenti per discriminar-

ne l’uso corretto da quello condannato a un esito antinomico) si concretizza

nella delineazione di un diverso, rispetto a quello tradizionale semantico, mo-

do di mostrare la noncontraddittorieta degli assiomi: bisogna sottoporre le

dimostrazioni –meglio: l’apparato dimostrativo della teoria costituito dagli

assiomi e dalle regole di inferenza– a un’indagine di tipo sintattico dalla quale

deve risultare l’impossibilita di dimostrare una contraddizione. Con riferi-

mento a un sistema di assiomi molto semplice, Hilbert da un esempio del

7Traduzione italiana in Hilbert [1985]


modo di procedere della prova di noncontraddittorieta cosı concepita. Si as-

sume che sia concretamente data la dimostrazione di una contraddizione: su

questa base si fa poi vedere che questa evenienza e impossibile perche questa

proprieta dovrebbe essere conservata risalendo la dimostrazione dalla formu-

la finale attraverso l’applicazione delle regole, fino a arrivare agli assiomi, i

quali, e evidente, non contengono contraddizioni.

Contro questa seconda proposta hilbertiana si levo la critica di Poin-

care, in Poincare [1906], il quale sottolineo che quella procedura impiega

evidentemente il principio di induzione completa; quindi, se il fine e quello

di cercare di provare in questo modo la noncontraddittorieta degli assiomi

aritmetici, uno dei quali e precisamente il principio di induzione completa, si

cade inevitabilmente in un circolo.

2.3 Il programma della conservazione

Nel corso degli anni ’20 Hilbert, coadiuvato da una folta schiera di insigni

matematici 8 formulera la sua terza e definitiva proposta fondazionale in cui

cerco di rispondere all’obiezione di Poincare e anche di valutare in maniera

piu meditata la critica freghiana9. Il primo carattere distintivo di questa

proposta e costituito dalla distinzione di una matematica reale e di una idea-

le10. La prima, detta anche finitista o finitaria, e la matematica combinatoria

e intuitiva (nel senso che non e retta da principi formali) dei numerali. Le

caratteristiche delle affermazioni che si fanno in questo ambito sono la decidi-

8Ricordiamo solo W. Ackermann, P. Bernays e J. von Neumann.9Tra le varie memorie di questi anni ci limitiamo a ricordare Hilbert [1926], che e il testodi una conferenza tenuta nel 1925, e che e tradotta in italiano in Hilbert [1985].

10Talvolta, per riferirci ai due ambiti, useremo i nomi R e I.


bilita e l’effettivita, e i ragionamenti induttivi sono basati sulla costruzione e

scomposizione di quelle figure concrete –sequenze finite di sbarrette– che sono

i numerali: tutti procedimenti che terminano in un tempo finito. Hilbert non

approfondı l’analisi delle procedure della matematica reale, di cui sottolinea

la sicurezza: con esse si possono certo commettere errori, ma non arrivare

a paradossi, cioe a errori prodotti dall’applicazione corretta delle regole. Il

tipo di evidenza intuitiva qui impiegata deriva il suo carattere di affidabilita

dal fatto che gli oggetti cui si applica portano, possiamo dire, “scritto in

faccia” che cosa sono. Non rimandano a altro per una loro giustificazione.

Le affermazioni che si pongono al limite fra matematica reale e matematica

ideale sono gli enunciati aperti, come ad esempio

a+ | = | +a

che sta per la comunicazione del fatto che per qualsiasi sostituzione di un nu-

merale al posto del segno a si ottiene un’affermazione reale vera. Gia negare

un enunciato come il precedente porta nel campo della matematica ideale,

o infinitaria, cui appartengono le usuali affermazioni che fanno riferimento,

tramite la quantificazione, a totalita infinite e a procedure che non neces-

sariamente terminano in un numero finito di passi. A differenza di quanto

succedeva con i numerali, le manipolazioni che facciamo sulle formule del-

la matematica ideale non trovano giustificazione nel significato dei simboli

impiegati: che ∃xA(x) segua da ¬∀x¬A(x) non e giustificato dal significato

intuitivo o informale dei quantificatori, ma riposa sulle regole e sulle definizio-

ni adottate. Diventa quindi fondamentale garantire che tali regole non siano

contraddittorie. Ma in questo periodo Hilbert sposta il fuoco dell’attenzione


dal problema della noncontraddittorieta al problema di mostrare che la ma-

tematica ideale e un’estensione conservativa di quella reale: quello che deve

essere provato, usando i metodi della matematica finitista, e che se un’affer-

mazione reale viene dimostrata con metodi ideali, allora era gia dimostrabile

con i soli strumenti finitisti. I due problemi, quello della noncontraddittorieta

e quello della conservativita di I rispetto a R, sono distinti, se pure stretta-

mente connessi: se ogni enunciato reale dimostrabile in I e finitisticamente

vero, allora, poiche 0 6= 0 non e vero, non e neppure dimostrabile in I che

risulta quindi noncontraddittorio: per la legge dello Pseudo-Scoto, infatti, in

una teoria contraddittoria e dimostrabile qualsiasi enunciato. D’altra parte,

se I e completa rispetto a R, cioe se in I sono dimostrabili tutte le formu-

le che esprimono enunciati reali veri, allora la noncontraddittorieta implica

la conservativita. Infatti, se I e noncontraddittorio allora 0 6= 0 non e un

teorema di I (poiche per ipotesi in I e dimostrabile l’enunciato reale vero

0 = 0): cioe, se (la formula che esprime) un enunciato reale e dimostrabile in

I allora quell’enunciato e finitisticamente vero11.

L’obiezione di Poincare trova qui almeno un abbozzo di risposta: la

proposta fondazionale hilbertiana evita di cadere in un patente circolo poiche

i due principi di induzione sono diversi. Quello proprio di R, cui spetta il

compito di giustificare gli assiomi dell’aritmetica, e ristretto a formule prive

di quantificatori, cioe e del tipo

α(0)α(a) → α(a + 1)

α(b)

11Per un approfondimento dei temi connessi con il programma fondazionale hilbertianorimando al mio Moriconi [1987].


mentre quello di I che deve essere giustificato non ha alcuna restrizione.

E anche l’obiezione di Frege trova una risposta piu drastica, se si

vuole, ma anche piu meditata. Rinunciando all’equazione fra noncontraddit-

torieta e esistenza, Hilbert riconosce che, a differenza di quello che succedeva

con i numerali, le formule della matematica ideale, o infinitaria, contengono

simboli cui non e connesso alcun tipo di evidenza intuitiva: e per questo

che la loro manipolazione necessita di una giustificazione. La soluzione di

Hilbert fu allora quella di aderire alla concezione formalista: le espressio-

ni del linguaggio-oggetto non hanno significato, sono formali nel senso che

l’applicazione delle varie regole richiede solo la possibilita di riconoscere la

forma e l’ordinamennto dei segni usati. Dotate di significato sono invece le

affermazioni della metateoria, in cui si usano le procedure di R.

3 Arriva Godel

Il punto centrale della costruzione godeliana e stato quello di prendere sul

serio, in un certo senso “alla lettera”, il precedente esito delle indagini hil-

bertiane: se sono puri segni, allora li si possono scegliere arbitrariamente.

Si possono ad esempio usare direttamente i numeri interi. Il modo in cui

Godel procedette, riprendendo i progetti leibniziani della ricerca di una ca-

ratteristica e combinatoria universali in grado di generare tutte le verita, e

diventato poi standard e si chiama aritmetizzazione, o anche, direttamente,

godelizzazione della metateoria o sintassi.


3.1 L’aritmetizzazione

Facciamo riferimento a una usuale teoria formale al I ordine dell’aritmetica

che chiameremo PA, contenente come simboli primitivi 0, ′, +, ×, e che agli

assiomi della logica del I ordine con identita aggiunge gli assiomi peaniani

su zero e successore, piu le equazioni ricorsive per somma e prodotto, e in

cui sono disponibili nomi per i numeri naturali12. Assumiamo inoltre di aver

assegnato in un qualche modo un numero naturale g(σ), che possiamo sup-

porre per concretezza dispari, a ogni segno σ del vocabolario primitivo della

teoria. Ovviamente, in modo che a segni distinti siano assegnati numeri (o

godeliani, o codici, come anche usualmente diremo) distinti. Su questa base,

a ogni sequenza finita di segni primitivi del linguaggio della teoria, σ1, . . . , σn,

e quindi in particolare a ogni termine o formula, viene fatto corrispondere il

numero

g(σ1, . . . , σn) = pg(σ1)1 × . . . × p

g(σn)n

dove p1, p2, . . . sono i numeri primi in ordine crescente. Analogamente, a ogni

sequenza finita di sequenze finite di simboli primitivi, diciamo α1, . . . , αn, e

quindi in particolare a ogni sequenza finita di formule che costituisca una

dimostrazione, viene fatto corrispondere il numero

g(α1, . . . , αn) = pg(α1)1 × . . . × pg(αn)

n

facendo in questo modo corrispondere a tutti gli oggetti della teoria un nume-

ro naturale come suo codice o godeliano. Viceversa, dato un numero naturale

12I cosiddetti numerali, dove n e il numerale per il numero naturale n.


qualsiasi, possiamo produrne la scomposizione in fattori primi –che e unica a

meno dell’ordine dei fattori– e, se e un codice, recuperare l’oggetto teorico di

cui lo e13. A questo punto, a insiemi di formule e relazioni tra formule di PA

corrisponderanno insiemi e relazioni numeriche; cioe, gli insiemi dei numeri

che sono i codici di quelle formule e le relazioni fra i numeri che sono i gode-

liani di quelle formule. Godel riuscı poi a dimostrare che in molti casi quegli

insiemi e quelle relazioni ammettono una definizione puramente aritmetica,

che e esprimibile formalmente in PA (preciseremo piu avanti che cosa cio

voglia dire). Come conseguenza di queste operazioni si ha che le asserzio-

ni metateoriche si trasformano in asserzioni numeriche, e dal momento che

PA contiene una formalizzazione dell’aritmetica diventa possibile esprimere

le asserzioni metateoriche con cui parliamo di PA all’interno della stessa

PA, cioe al livello del suo linguaggio. Si determina una “doppia vita” dei

numeri: oggetti di PA e codici. Grazie all’aritmetizzaione, enunciati me-

tateorici diventano enunciati teorici, da una parte, e, dall’altra, e possibile

che enunciati numerici rappresentino, utilizzando la chiave del codice adot-

tato, asserzioni metateoriche su PA. La possibilita che questa commistione

di teoria e metateoria –rifiutata, va ricordato, da Hilbert– apre e quella di

costruire enunciati che parlino di se stessi. Sono, queste, le situazioni di au-

toreferenzialita che sono alla base delle cosiddette antinomie semantiche, e

lo stesso Godel sottolinea l’analogia fra il suo ragionamento e l’antinomia di

13Non ci interessano qui i dettagli di questa corrispondenza, che ci limitiamo a richiedereiniettiva. Si puo notare che i codici dei simboli primitivi sono numeri dispari; quelli deitermini e delle formule sono pari (poiche contengono il fattore 2), ma con l’esponentedel primo fattore dispari (in quanto codice di un simbolo primitivo), mentre quelli delledimostrazioni sono pure pari, ma con l’esponente del primo fattore pari (in quanto codicedi una formula).


Richard. In effetti, esaminare piu da vicino questa analogia e molto utile per

evidenziare lo schema del ragionamento godeliano14.

3.2 L’antinomia di Richard

Per ottenere l’antinomia di Richard consideriamo le espressioni della lingua

italiana che definiscono proprieta di numeri naturali. Ovviamente, queste so-

no tante quanti sono i numeri naturali: ci sara la prima, la seconda, . . .. Sup-

poniamo di averle ordinate, ad esempio lessicograficamente, nella sequenza

infinita

E1, E2, . . . , En, . . . (1)

Per m, n numeri naturali arbitrari ha senso chiedersi se m possieda o meno

la proprieta espressa da En. Nel senso che comprendiamo le condizioni di

verita dell’affermazione che attribuisce la proprieta espressa da En al numero

naturale m. Scriveremo, rispettivamente, En(m) e ¬(En(m)). Consideriamo

a questo punto la proprieta numerica espressa da “il numero n non possiede

la proprieta espressa da En”, cioe

¬(En(n)) (2)

Poiche anche questa e una proprieta numerica espressa in italiano, e poiche

(1) enumera tutte le proprieta numeriche espresse in italiano, (2) deve coin-

cidere con una delle proprieta della sequenza (1). Poniamo sia la r-esima:

14Questa indagine fu condotta per la prima volta in Hilbert and Bernays [1939], dove vienefornita anche la prima dettagliata esposizione dei risultati godeliani. Questa impostazionela si ritrova in Mostowski [1952]. Per ulteriori indicazioni si possono vedereMariani andMoriconi [1984] e Bellotti et al. [2001].


cio significa che per ogni n, le condizioni Er(n) e ¬(En(n)) coincidono. Cio

che vale per ogni n, varra in particolare per r, e quindi otteniamo la seguente

contraddizione15:

Er(r) sse ¬(Er(r)) (3)

3.3 Il ragionamento di Godel

Risulta istruttivo cercare di ricostruire questa antinomia nel linguaggio for-

male della teoria PA, a proposito della quale assumiamo che sia noncontrad-

dittoria. Ovviamente, invece delle espressioni della lingua italiana, avremo

formule con una variabile individuale libera di PA16. Anche queste sono una

totalita numerabile ordinabile nella sequenza infinita

α1(x1), α2(x2), . . . , αn(xn), . . . (1∗)

Procedendo nella ricostruzione dell’antinomia, dovremmo ora esprimere in

PA la formula ¬(αn[xn/n])17 , cioe

n non possiede la proprieta espressa dalla formula αn(xn) (2∗)

15Dove con “sse” abbreviamo, come usuale, l’espressione “se e solo se”.Ricordiamo che l’antinomia di Richard e un tipico esempio di ragionamento impredicati-

vo: la proprieta Er e definita con riferimento alla sequenza (1), di cui poi lei stessa risultaessere un membro. Cioe, e definita facendo riferimento a una totalita cui lei stessa appar-tiene, e quindi, in un certo senso, e definita in termini di se stessa. Per una discussione diquesto tipo di definizioni si puo vedere il classico Fraenkel et al. [1973].

16Cioe, formule del tipo α(x), con cui si esprimono proprieta numeriche; come, ad esempio,“x e pari”, “x e composto, “x e divisibile per 23”, . . .

17Con l’espressione (αn[xn/n]) ci si riferisce alla formula che si ottiene dalla formula α(xn)sostituendo la sua variabile individuale libera xn con il numerale di n, cioe con n.


Ma qui si presenta subito una difficolta: (2*), come il precedente (2), risul-

ta immediatamente comprensibile perche utilizziamo il concetto intuitivo di

verita. Ma questa via non e percorribile entro PA, dove quel concetto non e

disponibile. Possiamo cercare di superare questa difficolta utilizzando, come

sostituto rigoroso del concetto di verita, quello di dimostrabilita entro PA.

Invece di (2*) avremmo allora:

l’enunciato αn[xn/n] non e dimostrabile in PA (2 ∗ ∗)

A questo punto, per continuare il processo di ricostruzione dell’antinomia,

bisognerebbe identificare (2**) con una delle proprieta espresse dalle formule

di (1*). Si incontra qui una seconda difficolta, dovuta al fatto che mentre

PA e una teoria formale dei numeri, e quindi le sue affermazioni concernono

proprieta e relazioni numeriche, in (2**) compaiono espressioni che non de-

notano insiemi o relazioni numeriche, ma nozioni metateoriche: “enunciato”,

“dimostrabile”, “sostituzione”, . . .. Entra qui in gioco il ruolo fondamentale

svolto dall’aritmetizzazione della metateoria: grazie ad essa, infatti, all’in-

sieme degli enunciati corrisponde l’insieme dei numeri che sono codici di

enunciati; al fatto che un enunciato sia dimostrabile, cioe al fatto che sia

l’ultimo membro di una sequenza finita di formule che costituisce una dimo-

strazione di PA, (Godel riuscı ingegnosamente a far vedere che) corrisponde

un relazione numerica, diciamo DimPA(m, n), che vale fra due numeri sse il

primo e il codice di una dimostrazione della formula di cui il secondo e il co-

dice; all’operazione di sostituzione che produce l’enunciato αn[xn/n] (Godel

riuscı ingegnosamente a far vedere che) corrisponde una funzione numerica,


diciamo st(p, q), tale che se p e q sono, rispettivamente, i codici di (αn(xn))

e di n (cioe, se p = g(αn(xn)) e q = g(n)), produce come valore il codice

dell’enunciato αn[xn/n], . . .

Come abbiamo gia detto, Godel riuscı a dimostrare che in molti casi

questi insiemi, relazioni e funzioni numeriche possono essere espresse formal-

mente in PA, anche se questa teoria contiene come primitivi solo la costante

zero e le funzioni di successore, addizione e moltiplicazione. Assumendo di

aver fatto tutto cio, possiamo formulare (2**) nel modo seguente:

¬∃yDimPA(y, st(n, n)) (2***)

Poiche (2***) e una formula con una variabile individuale libera, e quindi

costituisce la definizione aritmetica di una proprieta aritmetica, deve esistere

in (1*) una formula che esprime in PA la proprieta (2***). Supponiamo

che sia r il suo godeliano. Il passo conclusivo consiste nell’applicazione della

diagonale, cioe nella sostituzione dell’unica variabile libera della formula di

godeliano r con l’r-esimo numerale, ottenendo cosı

¬∃yDimPA(y, st(r, r)) (3*)

Come abbiamo visto, l’antinomia di Richard si concludeva con una contrad-

dizione: cosa possiamo invece dire di (3*)? Questo enunciato asserisce che

non esiste alcuna dimostrazione in PA della formula ottenuta dalla formula

di godeliano r –cioe, da (2***)– sostituendo la sua unica variabile libera con

il numerale del suo stesso codice. Ora, riflettendo su quanto fatto, si vede


che l’enunciato che fa questa asserzione e l’enunciato su cui questa asserzione

viene fatta coincidono, sono entrambi (3*). Quindi, (3*) asserisce la propria

indimostrabilita in PA.

Potrebbe (3*) essere dimostrabile in PA? No, poiche altrimenti sa-

rebbe intuitivamente falsa (in quanto afferma, abbiamo appena visto, la pro-

pria indimostrabilita). Se quindi assumiamo che i teoremi di PA siano in-

tuitivamente veri, abbiamo che non esiste in PA alcuna dimostrazione di

(3*).

Potrebbe la negazione di (3*) essere dimostrabile in PA? No, poiche

questo implicherebbe (per la noncontraddittorieta assunta di PA) l’indimo-

strabilita, e quindi la verita intuitiva, di (3*). Avremmo allora che in PA

sarebbe dimostrabile la negazione di un enunciato intuitivamente vero: il che

e di nuovo impossibile.

A differenza dell’antinomia di Richard, dunque, l’esito della costruzio-

ne godeliana non e antinomico, non ci imbattiamo cioe in una contraddizione,

ma nell’esistenza di un enunciato indecidibile. L’asimmetria dell’esito finale

dipende dal fatto che mentre per la verita vale il terzo escluso (un enuncia-

to o e vero o non e vero, e in questo secondo caso e allora falso), lo stesso

non vale per la dimostrabilita. Cioe, e certamente vero che un enunciato

o e dimostrabile o non e dimostrabile. Ma in questo secondo caso non c’e

alcun motivo perche l’enunciato debba allora essere refutabile, cioe debba

essere dimostrabile la sua negazione. Questo succede solo nelle teorie che

sono sintatticamente complete: cosa che PA evidentemente non e.


3.4 Debiti pagati

Nei paragrafi precedenti abbiamo spesso utilizzato espressioni come “assu-

miamo di aver fatto questo o quello . . .” oppure “preciseremo piu avanti cosa

cio voglia dire”. Per delineare il filo del ragionamento godeliano abbiamo

cioe dato per fatte certe operazioni e per comprese certe nozioni. Sapendo

ora dove tutto andava a parare, diventa doveroso cercare di colmare almeno

alcune delle precedenti lacune. Tra queste sono fondamentali le due seguenti:

1. abbiamo assunto che la funzione “st” e la relazione diadica “DimPA”

ammettano definizioni puramente aritmetiche;

2. abbiamo fatto ricorso al concetto di “intuitivamente vero” e alle pro-

prieta di PA di dimostrare solo enunciati intuitivamente veri e di non

dimostrare la negazione di enunciati intuitivamente veri.

E opportuno, per vedere come Godel ha affrontato queste due difficolta, pre-

cisare in primo luogo il concetto di “esprimibilita” nella teoria PA. Diciamo

che una relazione n-adica R e formalmente rappresentabile in PA se esiste

una formula α di PA con n variabili libere x1, . . . , xn tale che valgono le

affermazioni seguenti:

se vale R(n1, . . . , nn) allora ⊢PA α(x1/n1, . . . , xn/nn) (1)

se non vale R(n1, . . . , nn) allora ⊢PA ¬α(x1/n1, . . . , xn/nn) (2)

Diciamo che α rappresenta formalmente R se valgono (1) e (2). Se vale solo

(1) diciamo che R e semi-rappresentabile in PA tramite α. A questo pun-


to, una relazione e detta (semi-)esprimibile in PA se e formalmemte (semi-

)rappresentabile in PA. Si definisce poi l’esprimibilita di una funzione n-aria

f trattandola come una relazione (n + 1)-adica e imponendo che valgano (1)

e l’ovvia condizione di univocita. Ora, la via scelta da Godel per esibire la

rappresentabilita di gran parte delle nozioni metateoriche fu di mostrare che

quelle funzioni e relazioni –una volta diventate, grazie all’aritmetizzazione,

funzioni e relazioni numeriche– erano funzioni e relazioni ricorsive primitive,

diciamo per brevita RP. Le funzioni RP sono un sottoinsieme proprio di una

classe di funzioni, le funzioni ricorsive o ricorsive generali, caratterizzate dal

fatto di essere effettivamente calcolabili, nel senso che per ogni argomento

il computo del relativo valore si compie attraverso una serie finita di passi,

ognuno dei quali determina univocamente il successivo.

3.4.1 Le funzioni ricorsive

Fra le molte possibili caratterizzazioni del concetto di funzione effettivamen-

te calcolabile, quella fatta in termini di funzioni ricorsive segue la caratte-

rizzazione assiomatica dell’aritmetica fatta da Dedekind e Peano. I concetti

primitivi qui sono lo zero (“0”), il successore (“”’), lo schema di definizione

per ricorsione primitiva 18 e il principio di induzione19.

A queste che sono le componenti strettamente matematiche della de-

18Dove la funzione n + 1-aria f e detta definita per ricorsione primitiva a partire da duefunzioni gia note g e h, rispettivamente n-aria e n + 2-aria, se valgono:

f(x1, . . . , xn, 0) = g(x1, . . . , xn) (1)

f(x1, . . . , xn, y′) = h(x1, . . . , xn, y, f(x1, . . . , xn, y)). (2)

19La forma in cui quest’ultimo viene inglobato nella precisazione del concetto di proceduraeffettiva e quella equivalente del principio del numero piu piccolo. Supponiamo che g sia


finizione di funzione ricorsiva, si aggiunge poi un minimo di capacita mani-

polativa dei simboli: quella di identificare un dato termine entro una data

sequenza 20 , e quella di riempire i posti di argomento di una funzione gia

nota con i valori di altre funzioni anch’esse gia note 21.

Possiamo allora definire l’insieme delle funzioni ricorsive come il piu

piccolo insieme che contiene le seguenti funzioni iniziali

1. la funzione costante zero: 0

2. la funzione di successore: ’

3. per ogni n e k, k ≤ n, la funzione di proiezione Πnk

ed e chiuso sotto la composizione, la ricorsione primitiva e la µ-ricorsione.

Le funzioni effettivamente utilizzate da Godel furono quelle ottenibi-

li solo con composizione e ricorsione primitiva e appunto per questo sono

chiamate le funzioni ricorsive primitive.

una funzione gia nota a (n + 1) argomenti, e supponiamo che per essa valga che:

∀x1 . . . ∀xn∃y(g(x1, . . . , xn, y) = 0),

allora diciamo che f e definita per ricorsione sul minimo, o µ-ricorsione, se vale:

f(x1, . . . , xn) = µy(g(x1, . . . , xn, y) = 0).

Cioe, il valore della f e il piu piccolo y per cui la g si azzera, e che debba esistere almenouno di questi valori e garantito dall’ipotesi fatta su g.

20Il che vuol dire che consideriamo effettivamente calcolabili tutte le funzioni Πnk tali che

Πnk (x1, . . . , xk, . . . , xn) = xk

per k ≤ n.21Se la funzione h a m-argomenti e le funzioni g1, . . . , gm a n argomenti sono note, allora

accettiamo come effettiva la funzione a n argomenti, diciamo f , che si ottiene grazieall’operazione di sostituzione che produce la seguente configurazione:

f(x1, . . . , xn) = h(g1(x1, . . . , xn), . . . , gm(x1, . . . , xn))

e si dice che la funzione f e ottenuta per sostituzione o composizione da h e g1, . . . , gm.


3.4.2 Il lemma di Godel

L’utilizzazione metateorica delle funzioni RP e motivata dal modo in cui pro-

cede la costruzione di una teoria formale: molte nozioni metateoriche, come

ad esempio quella di “essere una formula” e quella di “essere una deriva-

zione”, sono infatti effettivamente decidibili. Nel senso che le regole della

teoria permettono di decidere con una procedura effettiva se una sequenza

finita di (sequenze finite di) segni del vocabolario primitivo sia una formula

(rispettivamente, una derivazione). La possibilita di usare le funzioni RP

per esplicitare questo carattere di effettivita (di alcune) delle nozioni e ope-

razioni metateoriche e data dall’aritmetizzazione della metateoria. Si dira

dunque che le operazioni e le proprieta metateoriche sono rappresentabili

ricorsivamente se esse possono essere rappresentate in termini di funzioni e

predicati RP22 sui codici degli elementi in questione. Con una serie di 45

definizioni Godel fece vedere che molti predicati e operazioni aritmetici as-

sociati –tramite l’aritmetizzazione– alle operazioni e proprieta metateoriche

sono RP. Sono in particolare RP le operazioni associate ai connettivi logici;

sono RP le nozioni di formula, assioma, conseguenza immediata tramite una

regola di inferenza, . . . , e RP e l’operazione di sostituzione st e la relazione

diadica DimPA23

22Noi abbiamo detto che cosa sia una funzione RP; un predicato e detto RP se tale e lasua funzione caratteristica, cioe la funzione che assume valore 1 per gli argomenti di cui ilpredicato vale e valore 0 per quelli di cui non vale.

23Non e invece RP la nozione di teorema, diciamo TeorPA, definita nel modo seguente:

TeorPA(x) =df ∃yDimPA(y, x)

in quanto e ottenuta da una relazione RP tramite una quantificazione esistenziale illimita-

ta. Insiemi di questo tipo sono chiamati semi-effettivi o, piu precisamente, ricorsivamente

enumerabili, intendendo che esiste una funzione RP (o piu in generale ricorsiva) il cuicodominio enumera (eventualmente con ripetizioni) gli elementi dell’insieme. Nel caso


Successivamente, Godel dimostra che anche se PA possiede solo zero,

successore, addizione e moltiplicazione, tutte le funzioni e i predicati RP

sono formalmente rappresentabili in PA. E questo il cosiddetto “lemma

di Godel” con il quale, in un certo senso, si chiude il cerchio: le nozioni

metateoriche diventano, grazie all’aritmetizzazione, nozioni numeriche; molte

di queste sono RP; tutte le funzioni e tutti i predicati RP sono rappresentabili

formalmente nella teoria PA; quindi, una parte rilevante della metateoria e

rappresentabile formalmente entro la teoria rendendo cosı possibili situazioni

di autoriferimento. Aggiungiamo che la ricorsivita primitiva, e quindi la

rappresentabilita formale in PA, di DimPA(y, st(n, n)) –cioe della relazione

che entra nella costituzione dell’enunciato indecidibile– deriva dal fatto di

essere stata ottenuta per sostituzione a partire dalla relazione DimPA e dalla

funzione st, ambedue RP; e la sostituzione e appunto una delle procedure

che portano da funzioni e predicati RP a funzioni e predicati RP.

3.4.3 Proprieta di PA

Fra le proprieta che PA deve possedere perche si possa ottenere il teorema di

Godel finora abbiamo esplicitamente formulato e usato solo la rappresenta-

bilita formale delle funzioni e dei predicati RP24, cosa che viene usualmente

particolare di TeorPA(x) la procedura ricorsiva e data dalla macchina dimostrativa delsistema che produce una dopo l’altra tutte le formule dimostrabili del sistema. Il carat-tere di semi-effettivita consiste nel fatto che non e disponibile una procedura analoga perenumerare il complemento dell’insieme, per cui se una certa formula e un teorema primao poi comparira nell’enumerazione, ma se non e ancora comparsa a un certo punto disviluppo dell’enumerazione non possiamo dire che non e un teorema (cioe, non possiamodire che non comparira mai): nulla esclude che possa comparire prolungando ancora unpo’ l’enumerazione.

24In realta si dimostra che un predicato e esprimibile in PA sse e ricorsivo, ma per il nostroragionamento e sufficiente limitarsi al caso dei RP. Per dettagli si veda Bellotti et al. [2001].


indicata dicendo che la teoria e “sufficientemente adeguata” o “sufficiente-

mente potente”. Ma, come ricordato nella seconda lacuna messa in luce nel

paragrafo 3.4, abbiamo fatto altre due assunzioni su PA. La prima e un’as-

sunzione di correttezza (tutto cio che e dimostrabile e vero) e viene rim-

piazzata nel ragionamento godeliano dall’assunzione, piu debole, che PA sia

noncontraddittoria. La seconda (non devono essere dimostrabili le negazioni

di enunciati intuitivamenti veri) viene rimpiazzta dall’assunzione che PA sia

ω-noncontraddittoria: dove una teoria e ω-noncontraddittoria se non esiste

alcuna formula α con una variabile libera x tale che sia possibile dimostrare,

da una parte, α[x/n] per ogni n ∈ N , e, dall’altra,¬∀xα(x). E opportuno

sottolineare che la nozione di ω-noncontraddittorieta e una versione sintat-

tica di quella semantica della categoricita: equivale infatti a postulare che

gli oggetti del dominio siano costituiti da tutti e soli i numeri naturali, gli

oggetti designati dai numerali25.

Un terzo gruppo di condizioni che la teoria PA deve soddisfare sono

le cosiddette condizioni di derivabilita, che concernono la relazione DimPA

e che furono esplicitate per la prima volta in Hilbert and Bernays [1939] e

successivamente precisate da Lob in Lob [1955]. Si tratta delle tre seguenti

25Come mostrato da Rosser in Rosser [1936], con una modificazione della definizione dellarelazione di dimostrabilita, la nozione di ω-noncontraddittorieta poteva essere eliminata infavore della semplice noncontraddittorieta. Si veda Bellotti et al. [2001] per una discussionegenerale del significato di questo risultato.


condizioni:

⊢PA α ⇒ ⊢PA TeorPA(g(α)) (D1)

⊢PA TeorPA(g(α)) → TeorPA(g(TeorPA(g(α)))) (D2)

⊢PA TeorPA(g(α)) → (TeorPA(g(α → β)) → TeorPA(g(β))) (D3)

E abbastanza agevole controllare che gli “usuali” sistemi formali soddisfano

queste tre condizioni. Consideriamo solo la prima. Se α e dimostrabile in

PA, cioe se vale

⊢PA α

allora, per definizione, esiste una dimostrazione di α in PA. Possiamo allora

calcolare il codice di questa dimostrazione e supponiamo che sia t, dove t e

un termine chiuso. Per la rappresentabilita della relazione di dimostrazione,

vale allora

⊢PA DimPA(t, g(α))

Per logica, da cio segue

⊢PA ∃xDimPA(x, g(α))

Cioe, ancora per definizione,

⊢PA TeorPA(g(α)) (1)

come desiderato26.

26Per una discussione delle altre due condizioni, anche relativamente alle teorie dotate di


3.5 I due teoremi di incompletezza

Come abbiamo visto nella ricostruzione di 3.3, l’enunciato indecidibile di

Godel, chiamiamolo γ, equivale all’asserzione della propria indimostrabilita.

La formula da cui prende le mosse il ragionamento di Godel, chiamiamola

γ(n) e infatti

¬∃yDimPA(y, st(n, n)). (1)

Questa formula afferma l’indimostrabilita della formula ottenuta dalla for-

mula di codice n sostituendo la sua unica variabile libera con il numerale

del suo stesso codice. Come ogni formula, anche questa avra un suo codice:

supponiamo che sia g(¬∃yDimPA(y, st(n, n))) = r e consideriamo

¬∃yDimPA(y, st(r, r)) (2)

Questa formula chiusa, che abbiamo chiamato γ, asserisce la propria indimo-

strabilita, infatti vale

⊢PA g(γ) = st(r, r) (3)

Quindi vale

⊢PA γ ↔ ¬∃yDimPA(y, st(r, r)) (4)

o se si preferisce

⊢PA γ ↔ ¬TeorPA(g(γ)) (5)

La costruzione di γ costituisce l’applicazione particolare di una piu generale

procedura la cui ammissibilita e sanzionata dal cosiddetto lemma di diago-

una relazione di dimostrabilita alla Rosser, si veda Bellotti et al. [2001].


nalizzazione, la cui prima formulazione sembra essere quella contenuta nel

paragrafo 35 di Carnap [1934].

Lemma 3.1 Sia α(x) una formula di PA contenente solo la x come variabile

libera. Allora esiste un enunciato δ tale che

⊢PA δ ↔ α(g(δ))

Dimostrazione Data α(x), consideriamo la formula α(st(x, x)). Sia d il suo

numero di Godel e chiamiamo δ la formula chiusa α(st(d, d)). Per le scelte

fatte, quest’ultima formula e equivalente a α(st(g(α(st(x, x))), d)). Da cio,

calcolando la funzione st, otteniamo α(g(α(st(d, d)))), che e quanto cercato.

2

Si noti che per ottenere l’enunciato indecidibile γ basta applicare il

Lemma alla formula ¬TeorPA(x). E evidente la parentela fra il lemma e il

teorema di ricorsione dimostrato da Kleene nel 1936, essendo entrambi risul-

tati di punto fisso, ma quello che va sottolineato e che Godel dimostro i suoi

teoremi non solo precedentemente allo sviluppo della vera e propria teoria

della ricorsione –sviluppo che fu anzi in parte non indifferente determinato

dai suoi teoremi–, ma anche prima che fossero noti i suddetti risultati. In un

certo senso, possiamo dire che egli individuo precisamente il caso particola-

re di quei risultati che serviva per dimostrare il teorema di incompletezza;

teorema che a questo punto possiamo dimostrare rigorosamente.

Teorema 3.2 Sia γ l’enunciato prima costruito e per il quale vale l’equiva-


lenza

⊢PA γ ↔ ¬TeorPA(g(γ))

allora se PA e noncontraddittoria γ non e dimostrabile in PA e se PA e

ω-noncontraddittoria allora γ non e neanche refutabile in PA, cioe non e

dimostrabile ¬γ.

Dimostrazione Ragioniamo per assurdo. Supponiamo che γ sia dimostra-

bile in PA. Per (D1) abbiamo allora

⊢PA TeorPA(g(γ))

Ma cio, insieme con l’equivalenza caratterizzante γ, per logica ci da che allora

in PA sarebbe dimostrabile ¬γ, contro la noncontraddittorieta di PA.

Da quanto appena dimostrato segue, per la effettivita della relazione

di dimostrabilita, che per ogni n vale

⊢PA ¬DimPA(n, g(γ))

Da cio, insieme con l’ipotesi della ω-noncontraddittorieta di PA, segue l’in-

dimostrabilita di ∃yDimPA(y, g(γ)), che altro non e che la negazione di γ.

2

Il secondo teorema di incompletezza concerne l’indimostrabilita, entro

PA, dell’enunciato che asserisce la noncontraddittorieta di PA. Ci sono vari

enunciati che esprimono la noncontraddittorieta di PA; uno di questi e ad


esempio

⊢PA DimPA(x, g(α)) → ¬DimPA(z, g(¬α)).

che chiamiamo WF . Intuitivamente, l’indimostrabilita di WF segue facil-

mente considerando che la prima meta del teorema 3.2 stabilisce che se PA

e noncontraddittoria allora γ non e dimostrabile, cioe non esiste alcun y che

sia il codice di una dimostrazione in PA di γ, cioe, sempre argomentando

intuitivamente, γ. Cioe, stabilisce che WF ⇒ γ. Se quindi fosse dimostrabile

l’enunciato che asserisce la noncontraddittorieta di PA sarebbe dimostrabile,

per modus ponens, anche γ, contro il primo teorema di incompletezza.

Formalizzare il precedente ragionamento intuitivo richiede particolare

cura e richiede piu precisamente che si usino tutte e tre le condizioni di deriva-

bilita, il che significa che per dimostrare il secondo teorema di incompletezza

deve essere garantito che la definizione della nozione di dimostrabilita sia tale

da riprodurre e rendere formalmente dimostrabili le principali proprieta del

concetto metateorico di cui esso intendeva costituire la controparte forma-

lizzata. Non e questa la sede per riprodurre tale dimostrazione27, mentre e

agevolmente ottenibile un altro importante risultato strettamente connesso

con quello godeliano: il teorema di Tarski sulla indefinibilita della verita.

Riflettiamo ancora sul teorema 3.2: esso segnala una sfasatura fra il concetto

di dimostrabilita e quello di verita. L’enunciato γ, infatti, e tale che ne lui ne

la sua negazione sono dimostrabili, ma, per il terzo escluso, uno dei due deve

essere vero. Come si spiega questa situazione? Una risposta venne appunto

dal risultato tarskiano. Premettiamo la definizione di cosa voglia dire che

27La si puo vedere in Bellotti et al. [2001].


una teoria possiede una definizione di verita: diciamo, con Tarski, che una

formula υ(x) con una variabile libera e una definizione di verita per PA se

per ogni α di PA vale

⊢PA υ(g(α)) ↔ α. (3)

Possiamo a questo punto dimostrare il seguente

Teorema 3.3 Se PA e noncontraddittoria allora non possiede una defini-

zione di verita relativa agli enunciati aritmetici.

Dimostrazione Ragioniamo per assurdo assumendo che PA possieda una

definizione di verita υ(x). Consideriamo allora la formula ¬υ(st(x, x)). Co-

me tutte le formule avra un codice, supponiamo che sia t e consideriamo

l’enunciato ¬υ(st(t, t)). Poiche questo e l’enunciato che si ottiene dall’enun-

ciato di godeliano t sostituendo la sua unica variabile libera con il suo stesso

godeliano, per le proprieta della funzione st vale ovviamente

⊢PA g(¬υ(st(t, t))) = st(t, t). (4)

D’altra parte, per (3) vale

⊢PA υ(g(¬υ(st(t, t)))) ↔ ¬υ(st(t, t)). (5)

Ma da (5) grazie a (4) otteniamo infine

⊢PA υ(st(t, t)) ↔ ¬υ(st(t, t)). (6)


La contraddizione ottenuta ci fa rigettare l’ipotesi per assurdo e cio conclude

la dimostrazione. 2

Il teorema di Tarski sulla indefinibilita delle verita spiega la sfasatura

prima rilevata fra questa nozione e quella della dimostrabilita facendoci sa-

pere che mentre quest’ultima e semi-esprimibile in PA, la nozione di verita

non e invece neanche definibile in PA. Questa situazione viene usualmente

commentata dicendo che mentre il teorema di Godel stabilisce una limitazio-

ne alle capacita deduttive di una teoria formale in grado di esprimere almeno

l’aritmetica, quello di Tarski ne limita invece le capacita espressive.

Talvolta il primo teorema di incompletezza viene frainteso e considera-

to un risultato di indecidibilita; ma si tratta appunto di un fraintendimento:

l’enunciato γ e effettivamente indecidibile, ma questo fatto non e sufficiente

per dichiarare la teoria PA indecidibile. A questo fine e infatti necessario

che abbia una risposta negativa la domanda che e propria del problema della

decisione: esiste una procedura effettiva che per ogni enunciato α permette di

rispondere in un tempo finito, e con una serie di passi ognuno dei quali deter-

mina il successivo, se l’enunciato sia o no un teorema? Si noti che il problema

della decisione per γ ha una ovvia soluzione: sı, la procedura esiste e il suo

esito e no! D’altra parte, l’indecidibilita di PA sara dimostrata cinque anni

piu tardi da A. Church28. E inoltre opportuno osservare che anche se noi ab-

biamo fatto riferimento alla teoria PA, il primo teorema di incompletezza e

dimostrabile per ogni estensione di PA che sia noncontraddittoria e effettiva

(il che significa che in tale estensione e ancora sempre decidibile il concet-

28In Church [1936a] e Church [1936b]. Per dettagli si veda Bellotti et al. [2001].


to di dimostrazione). Questo viene talvolta espresso dicendo che PA e non

solo incompleta sintatticamente, ma anche incompletabile. D’altra parte, il

risultato godeliano e dimostrabile anche per una teoria, il cosiddetto sistema

di Robinson, che e una sottoteoria finita di PA, in quanto non contiene lo

schema d’assiomi di induzione completa.

Pur essendo un risultato di natura sintattica, il primo teorema di

incompletezza ha un’importante conseguenza di natura semantica. Consi-

deriamo l’aritmetica al secondo ordine, diciamo PA2. Ovviamente il primo

teorema di incompletezza e dimostrabile anche in questo ambiente: esistera

quindi anche qui un enunciato indecidibile, diciamo γ∗. Consideriamo ora

le due teorie che si ottengono da PA2 aggiungendo una volta γ∗ e l’altra

¬γ∗. Queste due teorie sono noncontraddittorie, se lo e PA2. Se quindi

avessero entrambe un modello avremmo una contraddizione con il fatto che,

lo ha dimostrato R. Dedekind alla fine dell’Ottocento29, PA2 e categorica:

i due modelli, infatti, non potrebbero essere certo isomorfi dato che uno ve-

rificherebbe γ∗ e l’altro ¬γ∗. La via d’uscita da questa contraddizione sta

nel riconoscimento del fatto che la logica del secondo ordine non e seman-

ticamente completa. E infatti il teorema di completezza semantica che al

primo ordine connette la noncontraddittorieta con l’esistenza di un modello.

L’incompletezza sintattica dell’aritmetica al primo ordine produce l’incom-

pletezza semantica della logica al secondo ordine, per cui si puo dire che

Godel e colui che nel 1929 ha dimostrato che la logica del primo ordine e

semanticamente completa e nel 1930 che quella del secondo ordine (e di ogni

altro ordine superiore) e semanticamente incompleta.

29Per una dimostrazione si puo vedere Bellotti et al. [2001].


Quest’ultima osservazione e rilevante anche per un altro fatto. Come

abbiamo piu volte segnalato, il teorema di Godel e giustamente chiamato un

teorema di incompletezza, nel senso che si dimostra che esiste un enuncia-

to ne dimostrabile ne refutabile in PA, e quindi questa teoria e incompleta

sintatticamente. Naturalmente, va ricordato, in quanto teoria del I ordi-

ne, per PA vale il teorema di completezza semantica, dimostrato da Godel

l’anno prima, il che significa che tale teoria, incompleta rispetto alla verita

aritmetica e completa rispetto alla verita logica. Questo fatto e ovvio, ma

importante perche ci dice che il risultato godeliano e rilevante non solo per

il programma di Hilbert, ma anche per quello logicista di Frege e Russell:

la significativa distinzione stabilita tra verita logica e verita aritmetica, in-

fatti, rappresenta certo un non banale ostacolo per la tesi che non esistano

ne nozioni ne principi inferenziali specificatamente matematici, ma che siano

tutti formulabili utilizzando solo nozioni e procedure logiche. L’ovvieta di

questo rilievo deriva dal fatto che si rapporta al I ordine, in cui gli assiomi

aritmetici vengono aggiunti a quelli logici, mentre Frege si muoveva a livello

del II ordine. Ma a questo livello diventa allora pertinente il rilievo sulla

incompletezza semantica della logica del II ordine: la mancanza di una pro-

cedura di dimostrazione completa per la logica del II ordine mette infatti in

questione, indipendentemente dal paradosso di Russell, la possibilita della

riduzione logicista.


4 Di nuovo Hilbert

Come si ricordera, all’interno della proposta fondazionale hilbertiana, nel pa-

ragrafo 2.3 avevamo distinto un “programma della noncontraddittorieta” da

un piu generale “programma della conservazione”. Se il primo puo essere

identificato con il compito di dimostrare la formula WF , il secondo e formu-

labile dicendo che si tratta di dimostrare in R che se un enunciato reale α e

dimostrabile in I, o, possiamo dire, in PA, allora e gia dimostrabile anche

in R; in simboli

⊢R TeorPA(α) → α.

Cosı formulato, il programma hilbertiano si rivela un caso particolare –in

quanto ristretto a enunciati reali– del piu generale problema di dimostrare

la correttezza di una teoria: la teoria dimostra solo enunciati veri; cioe, del

problema di dimostrare che vale il cosiddetto Principio di Riflessione

⊢PA TeorPA(g(α)) → α. (PRFPA)

Come si disse nel paragrafo 2.3, data la particolare specie di evidenza pri-

vilegiata da Hilbert, quella finitista, i due problemi risultano, benche con-

cettualmente distinti, estensionalmente equivalenti; in generale vale che la

noncontraddittorieta e un caso particolare del principio di riflessione, quello

in cui PRFPA e ristretto a formule Π01. Queste precisazioni erano opportu-

ne perche tradizionalmente si riteneva che solo il secondo teorema di Godel

concernesse il programma di Hilbert, mentre sono invece rilevanti entrambi.

Il primo teorema di incompletezza colpisce infatti il programma della con-


servazione: questo dipende dal fatto che l’enunciato indecidibile γ di Godel

soddisfa, per definizione:

⊢PA ¬TeorPA(g(γ)) → γ,

se poi valesse PRFPA si avrebbe anche

⊢PA TeorPA(g(γ)) → γ,

e quindi, per logica,

⊢PA γ,

contro, appunto, il primo teorema di incompletezza. Contro il program-

ma della noncontraddittorieta si indirizza invece esplicitamente il secondo

teorema godeliano. Ed e anche opportuno osservare che il secondo teore-

ma di incompletezza, che concerne il programma della noncontraddittorieta

(un caso particolare, abbiamo visto, di quello della conservazione), coinvolge

proprieta piu raffinate, come testimoniato dal fatto che la sua dimostrazione

richiede tutte e tre le condizioni di derivabilita, delle nozioni intuitive che

non quelle usate nella dimostrazione del primo teorema di incompletezza, il

quale si riferisce al piu generale programma della conservazione e richiede

solo la prima condizione di derivabilita.

5 Dopo Godel

Tra i molti temi che sono stati oggetto di indagine in maniera piu o meno

strettamente collegata con i risultati godeliani ci limitiamo a accennare bre-


vemente alla ricerca di enunciati indecidibili che, a differenza di γ e WF ,

non siano di natura metamatematica, ma possiedano un contenuto di diretto

significato matematico30.

Il primo esempio di un tale enunciato apparve nel 1936 per opera di G.

Gentzen31: si tratta del principio di induzione transfinita fino al primo ǫ nu-

mero, mediante il quale egli fornı una dimostrazione di noncontraddittorieta

per l’aritmetica. Si tratta di un principio che puo essere espresso, ma non

dimostrato nell’aritmetica. In Gentzen [1943] Gentzen dimostro direttamen-

te32 che tutti i principi di induzione strettamente piu deboli dell’ǫ-induzione

sono equivalenti al principio di induzione usuale, mentre l’ǫ-induzione non

e dimostrabile nell’aritmetica. Ecco dunque un primo esempio di un enun-

ciato indipendente dagli usuali assiomi aritmetici e non ottenuto tramite la

codificazione della metateoria.

Vari altri esempi di enunciati aritmetici non prodotti tramite aritme-

tizzazione furono trovati a partire dagli anni ’70 del secolo appena concluso.

Di questi accenniamo solo brevemente al primo, costruito da J. Paris e L.

Harrington e pubblicato in Paris and Harrington [1977]. La procedura adot-

tata consistette nel produrre un enunciato ϕ e due modelli di PA tali che

in uno di essi l’enunciato risulta vero e nell’altro falso. Gia formulare questo

enunciato ϕ presenta qualche complicazione. Cominciamo dicendo che se X e

un insieme di naturali e n un naturale indichiamo con [X]n la famiglia di tutti

30Cioe, sia γ sia WF sono enunciati numerici, ovviamente, ma in quanto tali non han-no alcun particolare significato. Questo lo ottengono se vengono letti, tramite il codicedell’aritmetizzazione, come enunciati metateorici.

31In Gentzen [1936].32Indirettamente, cio gia seguiva dal fatto che quel principio permetteva di dimostrare la

noncontraddittorieta dell’aritmetica. Per dettagli si puo vedere Mariani and Moriconi[1984].


i sottoinsiemi di X di cardinalita n. Una funzione C : [X]n −→ c, dove c e un

naturale identificato con l’insieme dei suoi predecessori {0, . . . , c−1}, e detta

una funzione di coloritura. Con questa terminologia possiamo enunciare il

seguente teorema dimostrato nel 1929 da F. P. Ramsey:

Teorema 5.1 Siano n e c numeri interi positivi: per ogni funzione di colo-

ritura

C : [N ]n −→ c

esiste un sottoinsieme infinito Y di N che e omogeneo per C, nel senso che

la funzione C ristretta a [Y ]n e costante.

Il significato del teorema 5.1 non e affatto immediato e possiamo ren-

derlo un po’ piu intuitivo osservando che, per il caso in cui n sia uguale a 1,

dice che se un insieme infinito viene diviso in un numero finito di parti allora

almeno una parte e infinita. Il teorema 5.1 ha una versione finita che ora

enunciamo:

Teorema 5.2 Siano s, n e c numeri naturali con s ≥ n + 1. Allora esiste

un numero R(s, n, c) tale che per ogni r ≥ R(s, n, c), per ogni insieme X di

cardinalita r e per ogni funzione di coloritura

C : [X]n −→ c

esiste un insieme Y omogeneo per C e di cardinalita almeno s.

Il teorema 5.2 puo essere dimostrato in PA. Per formulare l’enunciato

indecidibile ϕ abbiamo bisogno di un altro concetto ancora, quello di un


insieme di naturali che e relativamente grande: questo e un insieme la cui

cardinalita e maggiore o uguale del piu piccolo membro dell’insieme. Ad

esempio, l’insieme {3, 6, 89, 123} e relativamente grande, mentre l’insieme

{6, 89, 123} no. L’enunciato indecidibile ϕ formulato da Paris e Harrington

e una modificazione di 5.2, ottenuta aggiungendo la richiesta che l’insieme

omogeneo Y sia relativamente grande. Di per se, non e certo immediatamente

chiaro il significato di questa aggiunta. In ogni caso, Paris e Harrington fecero

vedere che ϕ e vera nel modello standard dei naturali, ma che esiste anche un

modello dei naturali in cui e falsa: quindi, si ha che ϕ e indipendente dagli

assiomi di PA.

L’enunciato ϕ, a differenza di quello godeliano, e un enunciato chia-

ramente numerico, anzi combinatorio, e diversa e anche la procedura dimo-

strativa: non piu sintattica, ma semantica, come nella tradizione geometrica

(la dimostrazione di indipendenza dell’assioma delle parallele, ad esempio)

e insiemistica (la dimostrazione di indipendenza dell’assioma di scelta e del-

l’ipotesi del continuo). Un’ulteriore differenza risiede nella complessita dei

due enunciati: quello godeliano e del tipo ∀xα(x), dove α(x) e decidibile,

cioe ricorsivo primitivo; ϕ e invece del tipo ∀x∃yα(x, y), per α(x, y) decidibi-

le. Di questa stessa complessita, o di complessita maggiore, sono anche altri

enunciati indecidibili successivamente individuati (e sui quali non ci soffer-

meremo33), per cui si puo dire che quello costruito da Godel risulta il piu

semplice enunciato indecidibile finora costruito.

33Per informazioni si puo vedere Kaye [1991].


6 I teoremi di Godel e la discussione sul meccanicismo

Concludiamo con alcuni brevi cenni circa la discussione sulle potenzialita

della mente umana, discussione profondamente rinnovata dall’introduzione di

quelle macchine simboliche che sono le macchine di Turing (d’ora in poi MT)

e che ha coinvolto, e tuttora coinvolge, i teoremi godeliani d’incompletezza.

Le domande intorno a cui gira la discussione sono, in primo luogo, se si

possa dire che la mente umana funziona come un sistema formalizzato e, in

secondo luogo, se il programma di una MT costituisca un modello adeguato

della mente umana.

Alla tesi che una MT possa fare qualsiasi cosa che la mente umana puo

fare, il filosofo Lucas controbatte che le abilita della mente umana sono sem-

pre superiori a quelle di una macchina, sostanzialmente sulla base del fatto

che mentre l’enunciato γ risulta indecidibile per quella particolare macchina

che e PA, la mente umana puo invece argomentare –procedendo secondo

la linea intuitiva da noi seguita in 3.3– a favore della verita dell’enunciato

γ. Questo implicherebbe che nessun programma di computer e in grado di

rappresentare adeguatamente la mente umana: un qualsiasi programma per

generare le verita aritmetiche puo infatti essere rappresentato da un sistena

formale del tipo di PA, sistema formale che sara noncontraddittorio se tale

era il programma. A questo punto qualsiasi persona in grado di compren-

dere la natura del sistema formale puo riconoscere la verita dell’enunciato

indecidibile, mentre questo fatto non sara mai tra i fatti in uscita del siste-

ma formale34. Contro l’argomentazione di Lucas sono state sollevate varie

34L’argomentazione di Lucas e in realta piu complicata, ma in ultima analisi il punto e quelloesposto. Per dettagli si veda Lucas [1961], Anderson [1964] e Penrose [1994].


obiezioni, la piu cogente delle quali sembra quella imperniata sul fatto che

essa usa l’assunzione della noncontraddittorieta di PA, assunzione che pero,

per il secondo teorema di incompletezza, e destinata a rimanere tale. Quello

che si dovrebbe dire, quindi, e che la verita di γ e dimostrabile da una teoria

che sia in grado di trattare la semantica attraverso la nozione di verita (che

pero, come sappiamo dal teorema 3.3, il teorema di Tarski, non e definibile

in PA). Cioe, una teoria in cui sia dimostrabile la verita di γ e una teoria

cui si e aggiunta una dichiarazione di infinito: sia essa un modello di PA,

attraverso la definizione di verita al secondo ordine, sia invece l’affermazione

sintattica della noncontraddittorieta. E non e immediato vedere come questa

dichiarazione, in una qualunque delle due forme suddette, sia disponibile per

una mente finita.

Rinunciamo senz’altro a seguire l’intricato dibattito che si e sviluppa-

to a partire da questi temi, e che e ormai parte importante della disciplina

chiamata Intelligenza Artificiale35. Vale invece la pena ricordare che Godel

stesso, negli anni ’50, intervenne su questi temi cercando di argomentare a

favore della tesi secondo cui le leggi del pensiero non sono meccaniche, ma

secondo una linea diversa da quella appena rammentata. Nella famosa Gibbs

Lecture, tenuta il 26 dicembre del 1951, egli sottolinea che l’incompletabilita

della matematica risulta particolarmente evidente dal secondo teorema di in-

completezza, quello concernente l’indimostrabilita dell’enunciato che esprime

la noncontraddittorieta di PA. Il suo ragionamento e il seguente:

The second theorem [. . .] makes it impossible that someone should

35Oltre ai testi gia citati, si possono vedere Benacerraf [1967], Chihara [1972], Dennett [1978],Putnam [1960] e Smart [1961]


set up a certain well-defined system of axioms and rules and

consistently make the following assertion about it: All of these

axioms and rules I perceive (with mathematical certitude) to be

correct, and moreover I believe that they contain all of mathema-

tics. If someone makes such a statement he contradicts himself.

For if he perceives the axioms under consideration to be correct,

he also perceives (with the same certainty) that they are consi-

stent. Hence he has a mathematical insight not derivable from

his axioms36.

Per meglio precisare il suo punto, subito dopo egli distingue la ma-

tematica oggettiva (il sistema di tutte le proposizioni matematiche vere) da

quella soggettiva (il sistema di tutte le proposizioni matematiche dimostra-

bili), e precisa che e solo la prima che non puo essere catturata da un well-

defined system of correct axioms: l’enunciato che stabilisce che il sistema e

noncontraddittorio e infatti vero, ma non dimostrabile (per il secondo teore-

ma di incompletezza, appunto). Questa distinzione, tuttavia, sposta in un

certo senso il problema: l’incompletabilita della matematica oggettiva segue

dal primo teorema di incompletezza (per il terzo escluso, o l’enunciato inde-

cidibile o la sua negazione deve essere vero) e, ovviamente, dal teorema di

Tarski. Quello che e qui propriamente in discussione e invece il sistema della

matematica soggettiva, a proposito della quale Godel osserva infatti che non

e esclusa la possibilita che esista una regola finita che produca tutti gli assio-

mi della matematica soggettiva, anche se resta comunque esclusa, e questa

volta effettivamente per il secondo teorema di incompletezza, la possibilita di

36Godel [1995] pagg. 308-309.


conoscere, con certezza matematica, che tutte le proposizioni prodotte dalla

regola sono corrette. Cioe, mentre il ragionamento antimeccanicista (di Lucas

e altri) usa l’enunciato indecidibile di Godel come prova del fatto che nessun

algoritmo, nessuna MT, e adeguato per rappresentare le capacita aritmetiche

umane, qui si utilizza il fatto che la costruzione dell’enunciato indecidibile e

l’appurarne la verita presuppongono la possibilita di “guardare” il sistema

formale dal di fuori nella sua interezza; questa e infatti la condizione perche

sia possibile procedere alla sua aritmetizzazione, a sua volta condizione della

diagonalizzazione che produce l’enunciato indecidibile. La conclusione che

viene in questo modo avanzata e che non e esclusa la possibilita che esista un

sistema formale in grado di codificare tutte le capacita aritmetiche umane,

ma noi non saremmo in grado di contemplarlo dal di fuori per poter procede-

re alla sua aritmetizzazione. In altre parole, non si puo escludere che esista

un algoritmo in grado di codificare tutta la conoscenza matematica umana,

ma anche se esistesse sarebbe comunque fuori della nostra portata. In altre

parole ancora, l’estensione del concetto “conoscenza (aritmetica) effettiva”

non puo a sua volta essere oggetto di una conoscenza effettiva.

Quello che e invece possibile e che ci si renda conto della verita di cia-

scuna proposizione prodotta, una dopo l’altra, per ogni numero finito di esse.

Per dare un’idea di una situazione del tipo di quella cui fa qui riferimento

Godel si pensi al diverso comportamento del quantificatore universale, a se-

conda che sia in posizione teorica o metateorica, nel caso del primo teorema

di incompletezza. Da una parte infatti, per la effettivita della relazione di

dimostrabilita in PA, e per il primo teorema di incompletezza, abbiamo che


per ogni n vale: ⊢PA ¬DimPA(n, g(γ))

Non vale invece, poiche sarebbe un’affermazione equivalente alla dimostrabi-

lita dell’enunciato indecidibile γ:

⊢PA ∀n¬DimPA(n, g(γ)).

Qui stiamo parlando di possibilita, ma Godel procede e osserva che se real-

mente esistesse una tale regola, vorrebbe allora dire che

the human mind (in the realm of pure mathematics) is equiva-

lent to a finite machine that, however, is unable to understand

completely its own functioning37

sottolineando che qui non e in questione la comprensione del funzionamento

fisico del meccanismo del pensiero, ma della tesi secondo cui questo mec-

canismo produce solo e sempre risultati corretti. Evidentemente, qui Godel

assume come ovvio che se una macchina intende completamente il suo proprio

funzionamento, allora deve poter essere in grado di riconoscerne la correttez-

za. In ogni caso, l’incapacita qui in questione conduce Godel a sostenere

che la matematica oggettiva sarebbe allora incompleta non solo nel senso di

non essere contenuta in nessun sistema assiomatico ben determinato, ma nel

senso che esisterebbero problemi circa i numeri naturali che non potrebbero

essere decisi da nessuna dimostrazione matematica concepibile dalla mente

umana.

37Godel [1995] pagg. 309-310.


L’esistenza di enunciati indecidibili di questo tipo viene quindi da lui

interpretata come una prova della seguente alternativa:

Either mathematics is incompletable in this sense, that its evident

axioms can never be comprised in a finite rule, that is to say, the

human mind (even within the realm of pure mathematics) infini-

tely surpasses the powers of any finite machine, or else there exist

absolutely unsolvable diophantine problems of the type specified.38

Cioe,

o la mente umana non e meccanica (nel senso che sorpassa in-

finitamente le capacita di qualsiasi macchina finita), oppure i

numeri naturali non sono una nostra costruzione (nel senso che

non esistono conoscenze sulle nostre proprie costruzioni che ci

siano per principio precluse)39.

E bisogna aggiungere che non e esclusa per lui la possibilita che entrambi i

membri della disgiunzione siano veri, nel qual caso la sua tesi sembra ten-

dere verso l’affermazione della non meccanicita della mente umana e della

oggettivita, nel senso platonista, della verita matematica.

L’enunciazione di questo dilemma (o meglio: trilemma) sembra a

Godel un fatto stabilito matematicamente, ma di grande interesse filoso-

fico. Questa tesi, tuttavia, e sembrata a molti problematica e di difficile

valutazione. Noi qui ci limitiamo a osservare, in conclusione, che pur pre-

scindendo dall’ambiguita insita nell’identificare la (una) mente umana con

38Godel [1995] pag. 310.39Anche pertinente per queste discussioni e il volume Webb [1980].


una macchina finita, con una MT, o comunque dal sostenere che possa essere

rappresentata (ma come?) da una MT, resta il fatto che l’assunzione sulla

cui base si muove Godel e lungi dall’essere ovvia. Assumere che riconoscere

la correttezza del proprio funzionamento faccia parte della conoscenza del

funzionamento stesso, cosı come l’assunzione che possiamo completamente

descrivere e decidere le proprieta delle nostre costruzioni, quasi un richiamo

del vichiano verum ipsum factum, sono infatti difficilmente valutabili, anche

per il livello di generalita in cui si muove Godel, e sembrano in ultima analisi

il frutto di una sovrapposizione fra i concetti, o meglio: fra due particolari

interpretazioni dei concetti di “ricorsivamente enumerabile” e di “ricorsivo’.

Riferimenti bibliografici

Anderson, A. R. (Ed.) (1964). Minds and Machines. Prentice Hall.

Bellotti, L., E. Moriconi, and L. Tesconi (2001). Computabilita. Lambda-

definibilita, ricorsivita, indecidibilita. Roma: Carocci.

Benacerraf, P. (1967). God, the Devil, and Godel. The Monist 51, 9–32.

Carnap, R. (1934). Logische Syntax der Sprache. Wien: Schr. z. wiss.

Weltauff. Trad. it. di A. Pasquinelli. Silva editore, Milano 1966.

Casari, E. (1997). Introduzione alla logica. Torino: UTET.

Cellucci, C. (1998). Le ragioni della logica. Roma-Bari: Laterza.

Cellucci, C. (2002). Filosofia e matematica. Roma-Bari: Laterza.


Chihara, C. (1972). On Alleged Refutations of Mechanism Using Godel’s

Incompleteness Results. Journal of Philosophy 69, 507–526.

Church, A. (1936a). A Note on the Entscheidunsproblem. The Journal of

Symbolic Logic 1, 40–41.

Church, A. (1936b). An Unsolvable Problem of Elementary Number Theory.

American Journal of Mathematics 58, 345–363.

Dennett, D. C. (1978). The abilities of men and machines. In Brain-

storms: Philosophical Essays on Mind and Psychology. Cambridge, MA:

MIT Press.

Fraenkel, A., Y. Bar-Hillel, and A. Levy (1973). Foundations of Set Theory.

Amsterdam: North-Holland.

Frege, G. (1965). Logica e aritmetica. Torino: Boringhieri. A cura di C.

Mangione.

Gentzen, G. (1936). Die Widerspruchsfreiheit der reine Zahlentheorie.

Mathematische Annalen 112, 493–565. Trad. ingl. in Szabo [1969].

Gentzen, G. (1943). Beweibarkeit und Unbeweisbarkeit von Anfangsfallen

der transfinite Induktion in der reine Zahlentheorie. Mathematische

Annalen 119, 140–161. Trad. ingl. in Szabo [1969].

Godel, K. (1986). Collected Works.Volume I (Publications 1929-1936). New

York - Oxford: Oxford University Press - Clarendon Press. S. Feferman et

al. edts.


Godel, K. (1995). Collected Works.Volume III (Unpublished essays and lec-

tures). New York - Oxford: Oxford University Press - Clarendon Press. S.

Feferman et al. edts.

Hilbert, D. (1904). Uber die Grundlagen der Logik und der Arithmetik. In

Verhand. des Dritten Inter. Math.-Kong. in Heidelberg. English translation

in van Heijenoort [1967].

Hilbert, D. (1926). Uber das Unendliche. Math. Ann. 95. English translation

in van Heijenoort [1967].

Hilbert, D. (1985). Ricerche sui Fondamenti della Matematica. Napoli:

Bibliopolis. A cura di V. M. Abrusci.

Hilbert, D. and P. Bernays (1939). Grundlagen der Mathematik, Volume II.

Berlin: Springer. Second enriched edition in 1970.

Kaye, R. (1991). Models of Peano Arithmetic. Oxford: Clarendon Press.

Kleene, S. C. (1952). Introduction to Metamathematics. Princeton: Van

Nostrand.

Lob, M. H. (1955). Solution of a Problem of L. Henkin. The Journal of

Symbolic Logic 20, 115–118.

Lolli, G. (1992). Incompletezza. Saggio su Kurt Godel. Bologna: Il Mulino.

Lucas, J. R. (1961). Minds, Machines and Godel. Philosophy 36, 112–127.

Ristampato in Anderson [1964].


Mariani, M. and E. Moriconi (1984). Coerenza e completezza delle teorie

elementari. Pisa: ETS.

Moriconi, E. (1987). La teoria della dimostrazione di Hilbert. Napoli:

Bibliopolis.

Moriconi, E. (2001). Tra coerenza e categoricita: una mappa delle nozioni

logiche fondamentali. In Materiali per un lessico della ragione. Pisa: ETS.

A cura di M. Barale.

Moriconi, E. (2003). On the Meaning of Hilbert’s Consistency Problem

(Paris,1900). Synthese 137.

Mostowski, A. (1952). Sentences Undecidable in Formalized Arithmetic.

Amsterdam: North-Holland.

Paris, J. and L. Harrington (1977). A Mathematical Incompleteness in Peano

Arithmetic. In J. Barwise (Ed.), Handbook of Mathematical Logic, pp.

1133–1142. Amsterdam: North-Holland.

Penrose, R. (1994). The Emperor’s New Mind. Concerning Computers,

Minds, and the Laws of Physics. Oxford-New York-Melbourne: Oxford

University Press.

Poincare, H. (1906). Les mathematiques et la logique. Revue de metaphysique

et de morale 14, 17–34.

Putnam, H. (1960). Minds and machines. In S. Hook (Ed.), Dimensions of

Mind: A Symposium. New York: Macmillan.


Rosser, J. B. (1936). Extension of Some Theorems of Godel and Church.

The Journal of Symbolic Logic 1, 87–91.

Shanker, S. (Ed.) (1991). Il teoema di Godel: una messa a fuoco. Padova:

Muzzio Editore.

Smart, J. (1961). Godel’s theorem, Church’s theorem and mechanism.

Synthese 13, 105–110.

Szabo, M. E. (Ed.) (1969). The Collected Papers of G. Gentzen. Amsterdam:

North-Holland.

van Heijenoort, J. (Ed.) (1967). From Frege to Godel: a source book in

mathematical logic, 1879-1931. Cambridge, Mass.: Harvard University

Press.

Webb, J. C. (1980). Mechanism, Mentalism, and Metamathematics. An

Essay on Finitism. Dordrecht: D. Reidel Publishing Company.

Moriconi - I Teoremi di Gödel

Documents

Transcript of Moriconi - I Teoremi di Gödel