LA PROVA DI GÖDEL

La geometria non euclidea di Bernhard Riemann può essere rappresentata da un modello cuclideo.
Il piano di Riemann diventa la superficie di una sfera di Euclide, punti del piano diventano punti di questa superficie, linee rette nel piano diventano cerchi massimi.
Cosí, una porzione del piano di Riemann limitata da segmenti di rette, viene rappresentata come una porzione di sfera limitata da archi di cerchi massimi.
Due segmenti di retta nel piano di Riemann corrispondono a due archi di cerchi massimi sulla sfera di Euclide, e questi ultimi, se prolungati, di fatto si incontrano, contrariamente al postulato delle parallele nella geometria euclidea.

A prima vista, questa dimostrazione dell’autocompatibilità della geometria riemanniana può sembrare conclusiva. Ma un’analisi piú profonda mostra il contrario. Se si riflette attentamente, si scopre che il problema è stato solo spostato. La dimostrazione cerca di stabilire la coerenza della geometria riemanniana facendo appello alla coerenza di quella euclidea. Si può concludere allora solo questo: la geometria riemanniana è coerente se la geometria euclidea è coerente. L’autorità di Euclide viene cioè invocata per dimostrare la coerenza di un sistema che pone in forse la validità esclusiva del sistema di Euclide stesso. Il problema a cui non si può sfuggire è questo: gli assiomi del sistema euclideo sono fra loro compatibili?
Una risposta a tale quesito, consacrata, come abbiamo visto, da una lunga tradizione, è che gli assiomi euclidei sono veri e quindi tra loro compatibili. Questa risposta, oggi, non è piú considerata accettabile. Ritorneremo su questo punto e spiegheremo perché è insoddisfacente. Un’altra risposta è che gli assiomi sono in armonia con la nostra esperienza, sia pur limitata, dello spazio e che noi siamo giustificati a estrapolare dal particolare all’universale. Tuttavia, sebbene molti aspetti possano indurci a propendere per questa idea, la nostra dimostrazione risulterebbe ancora logicamente incompleta. Se anche, cioè, tutti i fatti finora osservati fossero in accordo con gli assiomi, sussisterebbe sempre la possibilità che un fatto non ancora osservato possa contraddirli e distruggere così la loro pretesa universalità. Le considerazioni di carattere induttivo possono dimostrare soltanto che gli assiomi sono plausibili o probabilmente veri.
Hllbert, ciononostante, tentò un’altra strada per giungere alla soluzione, facendo appello alla geometria analitica di Cartesio. Secondo questa interpretazione, gli assiomi di Euclide vengono trasformati in verità algebriche. Per esempio, nel caso degli assiomi concernenti la geometria piana, conveniamo che l’espressione “punto” corrisponda a una coppia di numeri; l’espressione “linea retta”, a una relazione (lineare) tra numeri espressa mediante un’equazione di primo grado a due incognite; l’espressione “circonferenza”, a una relazione tra numeri espressa mediante un’equazione di secondo grado, di una certa forma, e così via. L’affermazione geometrica che due punti distinti determinano in modo unico una retta, viene trasformata nella verità algebrica che due coppie distinte di numeri determinano in modo unico una relazione lineare; il teorema geometrico che una retta incontra una circonferenza al piú in due punti, equivale al teorema algebrico che una coppia di due equazioni simultanee a due incognite (una delle quali è lineare e l’altra è quadratica, con una certa forma) determina al piú due coppie di numeri reali; e cosí via. In breve, l’autocompatibilità dei postulati euclidei viene provata mostrando che essi sono soddisfatti da un modello algebrico. Questa maniera di dimostrare l’autocompatibilità è potente ed efficace. Eppure, anch’essa non regge all’obiezione fatta prima. Ancora una volta, infatti, un problema riguardante un certo dominio viene risolto spostandolo in un altro dominio. L’argomentazione di Hilbert per provare la coerenza dei postulati geometrici prova soltanto che se l’algebra è coerente anche il sistema della geometria è tale. La dimostrazione dipende ovviamente dalla supposta coerenza di un altro sistema, e non è quindi una dimostrazione “assoluta”.
Nei vari tentativi di risolvere il problema della compatibilità vi è una difficoltà sempre presente, la quale consiste nel fatto che gli assiomi vengono interpretati mediante modelli composti da un numero infinito di elementi. Ciò rende impossibile abbracciare i modelli con un numero finito di osservazioni, per cui la verità degli assiomi stessi è messa in dubbio. Nelle argomentazioni induttive per provare la verità della geometria euclidea, un numero finito di fatti osservati, riguardanti lo spazio, è verosimilmente in accordo con gli assiomi. Ma la conclusione che tali argomentazioni cercano di stabilire implica un’estrapolazione da un insieme di dati finito a uno infinito. Come si può giustificare questo salto? La difficoltà si riduce, per non dire che si elimina, quando è possibile escogitare un modello appropriato che contenga solo un numero finito di elementi. Il modello del triangolo, che abbiamo usato per dimostrare la coerenza dei cinque postulati riguardanti le classi K ed L, è finito; ed è relativamente semplice determinare, con un’osservazione diretta, se tutti gli elementi del modello soddisfano realmente i postulati, e quindi se sono veri (e, allora, compatibili). Spieghiamo questo punto. Esaminando, uno alla volta, tutti i vertici del triangolo, possiamo vedere se due qualunque di essi stanno soltanto su un lato. In questa maniera proviamo che il primo postulato è vero. Dal momento che tutti gli elementi del modello, come pure le relazioni esistenti fra essi, possono essere sottoposti a un’osservazione diretta e completa, e dal momento che la probabilità di commettere degli errori in tale osservazione è praticamente nulla, la compatibilità dei postulati, in questo caso, non può essere soggetta a un dubbio genuino.
Sfortunatamente, la maggior parte dei sistemi di postulati che costituiscono i fondamenti di importanti rami della matematica non può essere tradotta in modelli finiti. Pensiamo al postulato dell’aritmetica elementare che asserisce che ogni intero ha un immediato successore che differisce da qualsiasi intero precedente. È evidente che il modello necessario a verificare l’insieme cui appartiene questo postulato non può essere finito, ma deve contenere infiniti elementi. Ne segue che la verità dell’insieme (e, quindi, la sua coerenza) non può essere stabilita mediante un’osservazione completa di un numero limitato di elementi. A quanto pare, abbiamo imboccato un vicolo cieco. Modelli finiti sono sufficienti, in linea di principio, a stabilire la coerenza di certi insiemi (finiti) di postulati; ma questi sono di scarsa importanza matematica. Modelli non finiti, necessari per interpretare la maggior parte dei sistemi di postulati di una certa importanza matematica, possono essere descritti soltanto in termini generali; e non possiamo dimostrare affatto che le descrizioni siano esenti da contraddizioni nascoste.
Si sarebbe tentati di suggerire, a questo punto, che possiamo essere sicuri della compatibilità di quelle formulazioni in cui modelli non finiti siano descritti mediante nozioni trasparentemente “chiare” e “distinte”. Ma la storia del pensiero non è stata mai molto gentile con la teoria delle idee chiare e distinte, o con la dottrina della conoscenza intuitiva implicita in tale teoria. In certi settori della ricerca matematica, nei quali le ipotesi riguardanti insiemi infiniti hanno un posto centrale, sono venute alla luce contraddizioni radicali, nonostante la chiarezza intuitiva dei concetti compresi nelle ipotesi e nonostante l’apparente coerenza delle costruzioni concettuali fatte. Tali contraddizioni (tecnicamente chiamate “antinomie”) sono emerse nella teoria dei numeri infiniti, sviluppata da Georg Cantor nel diciannovesimo secolo; e la comparsa di queste contraddizioni ha dimostrato inequivocabilmente che l’apparente chiarezza anche di un concetto così elementare come quello di classe (o aggregato) non garantisce la coerenza di un qualsiasi particolare sistema costruito su di essa. Poiché la teoria matematica delle classi, la quale studia le proprietà e le relazioni di aggregati, o insiemi di elementi, viene spesso usata come fondamento di altri settori della matematica, e in particolare dell’aritmetica elementare, ha un senso ben preciso chiedersi se contraddizioni simili a quelle incontrate nella teoria delle classi infinite siano presenti nella formulazione di altri rami della matematica.
A questo proposito, Bertrand Russell ha costruito una contraddizione all’interno della logica elementare stessa, che è precisamente analoga alla contraddizione per la prima volta sviluppatasi nella teoria di Cantor delle classi infinite. L’antinomia di Russell può essere enunciata nel modo seguente. Le classi sembrano essere di due tipi: quelle che non contengono se stesse come membri, e quelle che contengono se stesse. Una classe si dirà “normale” se, e solo se, non contiene se stessa come membro; altrimenti si dirà “non normale”. Un esempio di classe normale è la classe dei matematici, in quanto evidentemente la classe stessa non è un matematico e non è perciò un membro di se stessa. Un esempio di classe non normale è la classe di tutti gli oggetti pensabili, in quanto la classe di tutti gli oggetti pensabili è essa stessa pensabile ed è perciò un membro di se stessa. Per definizione, “N” stia per la classe di tutte le classi normali. Ci domandiamo se N stessa è una classe normale. Se N è normale, essa e un membro di se stessa (in quanto, per definizione, N contiene tutte le classi normali); ma, in questo caso, N è non normale, perché, per definizione, una classe che contiene se stessa come membro è non normale. D’altra parte, se N è non normale, essa è un membro di se stessa (per definizione di non normale); ma, in questo caso, N è normale, perché, per definizione, i membri di N sono le classi normali. In breve, N è normale se, e solo se, N è non normale. Ne segue che l’affermazione “N è normale“ è contemporaneamente vera e falsa. Questa inevitabile contraddizione nasce da un uso avventato della nozione, apparentemente limpida, di classe. Altri paradossi furono scoperti successivamente, e ciascuno di essi era costruito mediante modi familiari e apparentemente convincenti di ragionare. I matematici finirono con l’accorgersi che, nello sviluppo di sistemi coerenti, la familiarità e la chiarezza intuitiva sono delle canne troppo fragili per appoggiarvici.
Abbiamo visto l’importanza del problema della compatibilità, e abbiamo fatto conoscenza dei metodi classici per risolverlo con l’aiuto di modelli. Abbiamo mostrato come, nella maggior parte dei casi, il problema richieda l’uso di modelli non finiti, la descrizione dei quali può celare essa stessa delle incoerenze. Dobbiamo quindi concludere che, se il metodo dei modelli è uno strumento matematico di grandissimo valore, esso, tuttavia, non fornisce una risposta definitiva al problema che ci siamo proposti di risolvere.

Note al capitolo 2

Nota 1.Si è tradotto il termine inglese consistency con “coerenza” o “autocompatibilità” (nel senso di “compatibilità intrinseca”) quando era riferito a un insieme di proposizioni o a un sistema considerati come un tutto unico, e con “compatibilità” o “compatibilità reciproca” quando era riferito alle parti che costituiscono un sistema. [N. d. t.]

Nota 2.La ragione principale di questa asserita mancanza di “autoevidenza” sembra essere stato il fatto che l’assioma delle parallele afferma qualche cosa sulle regioni infinitamente remote dello spazio. Euclide definisce le linee parallele come rette in un piano le quali, “prolungate indefinitamente nelle due direzioni”, non si incontrano mai. D’accordo con ciò, dire che due linee sono parallele equivale ad affermare che le due linee non si incontrano neanche “all’infinito”. Ma gli antichi avevano familiarità con linee che, sebbene non si incontrassero in alcuna regione finita del piano, tuttavia si incontravano “all’infinito”. Tali linee sono dette “asintotiche”. Cosí, per esempio, un’iperbole è asintotica ai suoi assi. Non era perciò intuitivamente evidente agli antichi geometri che per un punto esterno a una data retta si potesse tracciare soltanto una retta la quale non incontrasse quella data, neppure all’infinito.

Nota 3.Cosí, nel 1899, l’aritmetica dei numeri cardinali fu assiomatizzata dal matematico italiano Giuseppe Peano. Cinque sono i suoi assiomi. Essi sono formulati con l’ausilio di tre termini non definiti, dei quali si suppone la familiarità. I termini sono: numero, zero e successore immediato di. Gli assiomi di Peano possono enunciarsi cosí:

1) lo zero è un numero;

2) il successore immediato di un numero è un numero;

3) lo zero non è successore immediato di alcun numero;

4) due numeri qualsiasi hanno un diverso successore immediato;

5) ogni proprietà di cui gode lo zero e il successore immediato di ogni numero che gode della proprietà data, appartiene a tutti i numeri. Quest’ultimo assioma esprime quello che spesso viene chiamato il “principio di induzione matematica”.

Nota 4. In un linguaggio piú tecnico, i termini primitivi sono “implicitamente” definiti dagli assiomi, e tutto ciò che non è compreso nelle definizioni implicite è inessenziale per la dimostrazione dei teoremi.

Ernst Nagel e James R. Newman
La prova di Gödel
3. Prove assolute di compatibilità

Le limitazioni inerenti all’uso dei modelli nelle dimostrazioni di compatibilità, e il crescente timore che le formulazioni classiche di parecchi sistemi matematici potessero nascondere delle contraddizioni interne, condussero ad affrontare il problema in maniera nuova. Hilbert propose un’alternativa delle dimostrazioni “relative” di compatibilità. Egli pensò di costruire dimostrazioni “assolute”, mediante le quali l’autocompatibilità di un sistema avrebbe potuto essere provata senza ricorrere all’autocompatibilità di un altro sistema. Dobbiamo spendere qualche parola su questo tentativo per prepararci ulteriormente a comprendere la scoperta di Gödel.
Il primo passo da compiere nella costruzione di una dimostrazione assoluta consiste, come concepì Hilbert, nella completa formalizzazione di un sistema deduttivo. Si tratta, cioè, di svuotare di ogni significato le espressioni presenti nel sistema, le quali devono essere considerate come semplici segni. È necessario, poi, enunciare un insieme di regole, chiaramente precisate, per sapere come combinare e manipolare questi segni. Lo scopo di un tale procedimento è di costruire un sistema di segni (chiamato un “calcolo”) che non nasconda nulla e che contenga soltanto ciò che noi introduciamo in esso esplicitamente. I postulati e i teoremi di un sistema completamente formalizzato sono “catene“ (o lunghe sequenze finite) di simboli senza significato, costruite secondo le regole date per combinare i segni elementari del sistema in complessi piú ampi. Inoltre, quando un sistema è stato completamente formalizzato, la deduzione dei teoremi dai postulati non è altro che la trasformazione (conforme alle regole) di un insieme di tali “catene” in un altro insieme di “catene”. In questa maniera viene eliminato il pericolo di usare modi di ragionamento incontrollati. La formalizzazione è difficile e complicata, ma serve a uno scopo importante. Essa rivela, con obiettiva chiarezza, la struttura e il funzionamento di un sistema, come il modello delle parti essenziali di una macchina. Quando un sistema è stato formalizzato, le relazioni logiche fra le proposizioni matematiche diventano visibili; si possono osservare gli aspetti strutturali delle varie “catene” di segni “senza significato”, come esse si compongano e si adattino fra loro, e così via.
Una pagina piena di simboli “senza significato” di una tale matematica formalizzata non afferma nulla: non è altro che un disegno o un mosaico astratto, dotato di una determinata struttura. Nonostante ciò, è ancora, evidentemente, possibile descrivere le configurazioni di un tale sistema e fare delle affermazioni riguardo alle configurazioni stesse e alle varie relazioni che sussistono fra loro. Per esempio, si può dire che una “catena” ha un aspetto piacevole, o che assomiglia a un’altra “catena”, o che una “catena” sembra essere costituita da altre tre “catene”, e così via. Tali affermazioni hanno ovviamente un senso e possono fornire importanti informazioni sul sistema formale. È necessario però osservare, a questo proposito, che tali affermazioni dotate di significato, riguardo a sistemi matematici senza significato (o formalizzati), evidentemente non appartengono al sistema dato. Appartengono invece a quella che Hllbert denominò “metamatematica”: al linguaggio, cioè, che descrive dall’esterno la matematica. Le proposizioni metamatematiche sono proposizioni intorno ai segni che intervengono in un sistema matematico formalizzato (cioè un calcolo), intorno al tipi e alle disposizioni di tali segni quando vengono combinati per formare catene piú lunghe di simboli, chiamate “formule”, o intorno alle relazioni fra le formule che si possono ottenere come conseguenze delle regole di manipolazione specificate.
Alcuni esempi aiuteranno a comprendere la distinzione di Hilbert fra la matematica (cioè un sistema di segni senza significato) e la metamatematica (cioè affermazioni, dotate di significato, intorno alla matematica, ai segni che intervengono nel calcolo, alla loro disposizione e alle loro relazioni). Consideriamo l’espressione 2 + 3 = 5 Essa appartiene alla matematica (all’aritmetica) ed è composta interamente di segni aritmetici elementari. Al contrario, l’affermazione ‘2 + 3 = 5’ è una formula aritmetica asserisce qualche cosa sull’espressione scritta. Questa affermazione non esprime un fatto aritmetico e non appartiene al linguaggio formale dell’aritmetica; appartiene alla metamatematica, perché attribuisce il carattere di una formula a una certa catena di segni aritmetici. La seguente affermazione appartiene alla metamatematica:

se il segno ‘=’ ha da essere usato in una formula aritmetica, esso deve essere accompagnato, sia a destra che a sinistra, da espressioni numeriche.

Questa proposizione esprime una condizione necessaria per usare un certo segno aritmetico nelle formule aritmetiche: una formula aritmetica deve possedere una certa struttura se contiene quel segno.
Consideriamo ora le tre formule

X=X

0=0

0 ¹ 0

Ciascuna di esse appartiene alla matematica (all’aritmetica), poiché ciascuna di esse è costruita interamente con segni aritmetici. Al contrario, l’affermazione ‘x’ è una variabile appartiene alla metamatematica, perché caratterizza un certo segno aritmetico come appartenente a una classe di segni ben determinata (la classe delle variabili). Ancora, la seguente affermazione appartiene alla metamatematica:

la formula ‘0 = 0’ è deducibile dalla formula ‘x = x’ sostituendo il numerale ‘0’ al posto della variabile ‘x’.

Essa specifica in quale maniera una certa formula aritmetica può essere ottenuta da un’altra formula, e quindi descrive come le due formule siano legate l’una all’altra. Similmente, l’affermazione ‘0 ¹ 0’ non è un teorema appartiene alla metamatematica, in quanto afferma che una certa formula non è deducibile dagli assiomi dell’aritmetica, e quindi asserisce che non sussiste una certa relazione fra le formule del sistema sopra scritte. Infine, appartiene alla metamatematica l’affermazione l’aritmetica è autocompatibile (cioè, non è possibile dedurre dagli assiomi dell’aritmetica due formule formalmente contraddittorie: per esempio, le formule ‘0 = 0’ e ‘0 ¹ 0’). Essa è evidentemente un’affermazione sull’aritmetica, e asserisce che coppie di formule di un certo tipo non hanno una specifica relazione con le formule che costituiscono gli assiomi dell’aritmetica.[1]
Può darsi che il lettore trovi la parola “metamatematica” poco simpatica e il suo concetto poco chiaro. Non vogliamo certo sostenere che la parola sia bella, ma il suo concetto apparirà chiaro a tutti quando si pensi che viene adoperato nel caso particolare di una distinzione ben nota: la distinzione, cioè, fra l’oggetto che si studia e un discorso intorno all’oggetto stesso. La proposizione “tra i falaropi il maschio cova le uova” appartiene al campo studiato dagli zoologi, cioè alla zoologia; ma se noi diciamo che questa affermazione sui falaropi dimostra che la zoologia è irrazionale, la nostra affermazione non riguarda i falaropi, ma la frase e la scienza cui questa appartiene; si tratta di metazoologia. Se noi diciamo che l’id è piú potente dell’ego, parliamo di qualche cosa che appartiene alla psicoanalisi; ma se critichiamo questa affermazione come priva di significato e indimostrabile, la nostra critica appartiene alla metapsicoanalisi. Cosi anche nel caso della matematica e della metamatematica. I sistemi formali costruiti dai matematici appartengono alla categoria denominata “matematica”; la descrizione, la discussione e la teorizzazione dei sistemi appartengono alla categoria denominata “metamatematica”.
L’importanza, nel nostro campo, di comprendere a fondo la distinzione fra matematica e metamatematica non sarà mai abbastanza sottolineata. Quando essa non è stata rispettata, sono sorte delle confusioni e dei paradossi. Quando il suo significato è stato rettamente inteso, è stato possibile mettere in chiara evidenza la struttura logica del ragionamento. Il merito di questa distinzione è quello di implicare una precisa modificazione dei vari segni che intervengono nella costruzione di un calcolo formale, libero da ipotesi nascoste e da associazioni di significati non pertinenti. Inoltre, essa esige le definizioni esatte delle operazioni e delle regole logiche della costruzione e della deduzione matematica, le quali, spesso, sono state applicate dai matematici senza un’esplicita coscienza della loro natura.
Hilbert comprese il nocciolo della questione, e fu sulla distinzione tra un calcolo formale e la sua descrizione che egli basò il suo tentativo di costruire delle prove “assolute” di compatibilità. Sostanzialmente, egli pensò di sviluppare un metodo che fornisse prove di compatibilità che non fossero soggette ad alcun dubbio logico genuino (si pensi all’uso dei modelli finiti per dimostrare la compatibilità di un certo insieme di postulati), e ciò mediante l’analisi di un numero finito di caratteristiche strutturali delle espressioni presenti in calcoli completamente formalizzati. L’analisi consiste nel notare i vari tipi di segni che intervengono in un calcolo, nell’indicare in quale maniera questi possano venir combinati in formule, nel prescrivere la maniera con la quale si possono ottenere delle formule da altre formule, e nello stabilire se formule di un dato tipo sono derivabili da altre mediante regole di operazione esplicitamente enunciate. Hllbert era convinto che fosse possibile dare a ogni calcolo matematico l’aspetto di una specie di disegno “geometrico” di formule, nel quale le formule possedessero, l’una rispetto all’altra, un numero finito di relazioni strutturali. Egli, quindi, sperava di riuscire a mostrare, esaminando tutte queste proprietà strutturali delle espressioni di un sistema, l’impossibilità di ottenere formule formalmente contraddittorie dagli assiomi di certi calcoli. Un requisito essenziale del programma di Hilbert, nella sua concezione originale, è che le dimostrazioni di compatibilità si basano soltanto su quei procedimenti che non fanno appello a un numero infinito di proprietà strutturali delle formule o a un numero infinito di operazioni con le formule. Tali procedimenti vengono chiamati “finitistici”; e una dimostrazione di compatibilità che soddisfi questo requisito - viene chiamata “assoluta”. Una dimostrazione “assoluta” raggiunge il suo obiettivo usando un minimo di principi di inferenza, e non presuppone l’autocompatibilità di qualche altro insieme di assiomi. Una dimostrazione assoluta dell’autocompatibilità dell’aritmetica - se si potesse costruirne una - mostrerebbe perciò, mediante un procedimento metamatematico finitistico, che due formule contraddittorie, quali “0=0” e la sua negazione formale “~ (0 = 0)” - dove il segno “~” significa “non” - non possono essere dedotte dagli assiomi (o da altre formule) usando regole di inferenza esplicite.[2]
Può essere utile, a titolo illustrativo, paragonare la metamatematica, come teoria dimostrativa, alla teoria degli scacchi. Gli scacchi si giuocano con trentadue pezzi di data forma, su una scacchiera suddivisa in sessantaquattro quadretti, sulla quale i pezzi vengono mossi secondo regole fisse. Il giuoco si può svolgere, evidentemente, senza assegnare una qualche “interpretazione” ai pezzi o alle loro varie posizioni sulla scacchiera, sebbene una tale interpretazione possa essere data, se lo si desidera. Per esempio, si può convenire che una data pedina rappresenti un reggimento di un esercito, che un dato quadratino della scacchiera rappresenti una certa regione geografica, e cosí via. Ma una tale convenzione (o interpretazione) non è usuale; né i pezzi, né i quadratini, né le posizioni dei pezzi sulla scacchiera hanno un significato che sta al di fuori del giuoco stesso. In questo senso, i pezzi e le varie configurazioni sulla scacchiera sono “senza significato”. Un tale gioco, così, è analogo a un calcolo matematico formalizzato. I pezzi e i quadratini della scacchiera corrispondono ai segni elementari del calcolo; le posizioni permesse dei pezzi sulla scacchiera, alle formule del calcolo; le posizioni iniziali dei pezzi, agli assiomi o alle formule iniziali del calcolo; le posizioni successive dei pezzi, alle formule dedotte dagli assiomi (cioè, ai teoremi); e le regole del gioco, alle regole di inferenza (o deduzione) del calcolo. Questo parallelismo può essere continuato ulteriormente. Sebbene le configurazioni dei pezzi sulla scacchiera, come le formule del calcolo, siano “senza significato”, le proposizioni riguardanti tali configurazioni, come le proposizioni metamatematiche riguardanti le formule, sono perfettamente dotate di significato. Una proposizione appartenente ai metascacchi può asserire, per esempio, che vi sono venti mosse iniziali possibili per il bianco, o che, data una certa configurazione dei pezzi sulla scacchiera, il bianco matta in tre mosse. Inoltre, teoremi generali dei “metascacchi” possono venir dimostrati con ragionamenti che implicano solo un numero finito di configurazioni possibili sulla scacchiera. Il teorema del “metascacchi” sul numero di mosse iniziali possibili del bianco può essere provato secondo questa linea; e così pure il teorema che, se il bianco ha solo due cavalli e il re, e il nero solo il re, è impossibile che il bianco dia scacco matto al nero. Questi e altri teoremi dei “metascacchi” sono suscettibili, in altre parole, di essere dimostrati con metodi finitistici di ragionamento: esaminando, cioè, l’una dopo l’altra, ciascuna delle configurazioni, in numero finito, che possono determinarsi sotto certe condizioni date. L’obiettivo della teoria di Hilbert, similmente, era di dimostrare, mediante tali metodi finitistici, l’impossibilità di dedurre certe formule contraddittorie in un dato calcolo matematico.

Note al capitolo 3

Nota 1.È qui opportuno far notare come le proposizioni metamatematiche che compaiono nel testo non contengano, come loro parti costituenti, alcuno dei segni e delle formule matematiche contenuti negli esempi. Questa affermazione, a prima vista, sembra ovviamente falsa, in quanto i segni e le formule sono chiaramente visibili. Ma, se si esaminano le proposizioni metamatematiche con occhio critico, ci si accorge che abbiamo ragione. Le proposizioni metamatematiche, infatti, contengono i nomi di certe espressioni aritmetiche, ma non le espressioni aritmetiche stesse. La distinzione è sottile ma valida e importante. È piú corretto, infatti, che una frase, come prescrive la lingua inglese, non contenga letteralmente gli oggetti a cui si riferiscono le espressioni della frase stessa, ma soltanto i nomi di tali oggetti. Evidentemente, quando parliamo di una città non introduciamo la città stessa nella frase, ma soltanto il nome della città; e, similmente, se desideriamo dire qualche cosa intorno a una parola (o a un altro segno linguistico), non è la parola stessa (o il segno) che può comparire nella frase, ma solo il nome di quella parola (o di quel segno). È piú corretto stabilire convenzionalmente che il nome di un’espressione linguistica venga costruito ponendo delle virgolette semplici alle estremità di essa. Il nostro testo usa questa convenzione. È corretto scrivere Chicago è una città popolosa. Ma è sbagliato scrivere Chicago è trisillaba. Per esprimere correttamente ciò che vogliamo dire, questa frase deve essere scritta cosí: ‘Chicago’ è trisillaba. Parimenti, è sbagliato scrivere x = 5 è un equazione. Dobbiamo, invece, esprimerci cosí: ‘X = 5’ è un’equazione.

Nota 2.Hilbert non precisò esattamente quali procedimenti metamatematici fossero da considerarsi finitistici. Nella versione originale del suo programma i requisiti di una dimostrazione assoluta di compatibilità erano piú stretti che nelle successive interpretazioni del programma da parte dei membri della sua scuola.

Ernst Nagel e James R. Newman
La prova di Gödel
4. La codificazione sistematica della logica formale

Vi sono ancora due passi da compiere prima di affrontare la prova di Gödel. Dobbiamo far vedere come e perché nacquero i Principia mathematica di Whitehead e Russell; vogliamo pure dare una breve esemplificazione del processo di formalizzazione di un sistema deduttivo - sceglieremo un passo dei Principia - e spiegare come la sua compatibilità assoluta possa essere dimostrata.
Ordinariamente tali dimostrazioni, anche quando si tratta di dimostrazioni matematiche conformate alle esigenze comunemente accettate del rigore professionale, soffrono di un importante difetto. Esse contengono principi (o regole) di deduzione non esplicitamente formulati, di cui, frequentemente, i matematici non hanno coscienza. Consideriamo la dimostrazione di Euclide che non vi e un numero primo più grande di tutti (un numero primo è un numero divisibile, senza resto, soltanto per l’unità e per se stesso). L’argomentazione, messa nella forma di una reductio ad absurdum, si articola come segue.
Supponiamo, contro la tesi, che esista un numero primo piú grande di tutti. Chiamiamolo ‘x’. Allora:

1) x è il numero primo piú grande di tutti;

2) formiamo il prodotto di tutti i numeri primi minori o eguali a x, e aggiungiamo i al prodotto, ciò porta a un nuovo numero y dato da y = (2 × 3 × 5 × 7 × ... × x)+ i;

3) se y è un numero primo, allora x non è il numero primo piú grande di tutti, dato che, ovviamente, y è maggiore di x;

4) se y non è un numero primo, allora di nuovo x non è il numero primo piú grande: infatti, se y non è un numero primo, esso deve possedere un divisore primo z; e z deve essere differente da ciascuno dei numeri primi 2, 3 9 5, 7, .... x, minori o eguali a x, quindi z deve essere un numero primo maggiore di x;

5) ma y o è un numero primo o è un numero composto;

6) quindi x non è il numero primo piú grande di tutti;

7) non esiste un numero primo piú grande di tutti.
Abbiamo mostrato solo le linee principali della dimostrazione. E possibile far vedere, però, che nel costruire la dimostrazione sono essenziali diverse regole di inferenza e teoremi di logica. Alcuni di questi appartengono alla parte piú elementare della logica formale, altri ad alcuni rami piú complessi; per esempio, sono presenti regole e teoremi che appartengono alla “teoria della quantificazione”. Questa teoria studia le relazioni esistenti fra proposizioni che contengono particelle “quantificanti” quali ‘tutti’, ‘qualche’, e loro sinonimi. Mostreremo un teorema elementare della logica e una regola di inferenza, ambedue ausili necessari ma silenziosi della dimostrazione.
Osserviamo il punto 5) della dimostrazione. Di dove proviene? La risposta è: dal teorema logico (o verità necessaria) ‘o p è vero, o non p è vero’, [1] dove ‘p’ viene chiamata una variabile proposizionale.
Ma come otteniamo il punto 5) da questo teorema? La risposta è: usando la regola di inferenza nota come la “regola di sostituzione per le variabili proposizionali”, secondo la quale è possibile dedurre una proposizione da un’altra contenente tali variabili sostituendo una qualsiasi proposizione (in questo caso, ‘y è un numero primo’) ovunque compare una variabile distinta (in questo caso, la variabile ‘p’). L’uso di queste regole e di questi teoremi logici è, come abbiamo detto, molto frequentemente null’altro che un’azione inconscia. E l’analisi che li rivela, anche in dimostrazioni relativamente semplici come quelle di Euclide, dipende dai progressi nella teoria della logica compiuti soltanto negli ultimi cento anni.[2]
Come il Monsieur Jourdain di Molière, che parlò in prosa tutta la vita senza saperlo, i matematici hanno ragionato per almeno due millenni senza accorgersi di tutti i principi che stavano alla base del loro lavoro. La vera natura dei mezzi della loro arte è divenuta chiara solo in tempi recenti.
Per quasi duemila anni la codificazione aristotelica delle forme valide di deduzione fu universalmente riguardata come completa e non suscettibile di essenziali miglioramenti. Ancora nel 1787, il filosofo tedesco Immanuel Kant poteva dire che dai tempi di Aristotele la logica formale “non è stata capace di fare un solo passo, e che, secondo tutte le apparenze, è un corpo dottrinario chiuso e completo”. Il fatto è che la logica tradizionale è seriamente incompleta e non riesce neppure a dare una giustificazione di molti principi di inferenza usati nei ragionamenti matematici più elementari [3].
La rinascita degli studi sulla logica iniziò, nel tempi moderni, con la pubblicazione, nel 1847, del libro The Mathematical Analyslis of Logic di George Boole. La preoccupazione principale di Boole e dei suoi immediati successori fu di sviluppare un’algebra della logica (si veda, per esempio, la tabella 1) la quale fornisce una notazione precisa per trattare tipi di deduzione piú generali e piú vari di quelli contemplati dai principi della logica tradizionale. Supponiamo che, in una certa università, la classe degli studenti che si laureano con la lode sia composta esattamente di ragazzi che studiano matematica e di ragazze che non studiano tale materia. Come è costituita la classe di coloro che studiano matematica, in termini delle altre classi di studenti menzionate? La risposta non è facile da trovare se si usa soltanto l’apparato della logica tradizionale. Ma con l’aiuto dell’algebra di Boole si può facilmente dimostrare che la classe di coloro che studiano matematica consiste esattamente di ragazzi che si laureano con la lode e di ragazze che non si laureano con la lode.
Un’altra linea di ricerca, strettamente connessa con gli studi dei matematici del diciannovesimo secolo sui fondamenti dell’analisi, si affiancò al programma di Boole. Questo nuovo sviluppo mirava a descrivere la matematica pura come un capitolo della logica formale, e ricevette la sua classica formulazione nel Principia mathematica di Whitehead e Russell, nel 1910. I matematici del diciannovesimo secolo riuscirono ad “aritmetizzare” l’algebra e quello che si soleva chiamare il “calcolo infinitesimale”, mostrando come le varie nozioni impiegate nell’analisi matematica siano definibili esclusivamente in termini aritmetici (cioè, in termini di numeri interi e di operazioni aritmetiche su di essi). Per esempio, invece di accettare il numero immaginario Ö( - 1) come una “entità”, in certa maniera misteriosa, si giunse a definirla come una coppia ordinata di numeri interi (0,1) sui quali possono venir compiute certe operazioni di “ addizione “ e di “ moltiplicazione “. Similmente, il numero irrazionale Ö2 fu definito come l’elemento di separazione di due certe classi di numeri razionali, cioè come l’elemento di separazione fra la classe dei numeri razionali il cui quadrato è minore di 2 e la classe dei numeri razionali il cui quadrato è maggiore di 2. Ciò che Russell (e, prima di lui, il matematico tedesco Gottlob Frege) pensavano di dimostrare era che tutte le nozioni aritmetiche possono essere definite con idee puramente logiche, e che tutti gli assiomi dell’aritmetica possono essere dedotti da un piccolo numero di proposizioni fondamentali verificabili come pure verità logiche.
Facciamo un esempio. La nozione di classe appartiene alla logica generale. Due classi sono dette “simili” se vi è una corrispondenza biunivoca fra i loro membri, la nozione di una tale corrispondenza essendo spiegabile in termini di altre idee logiche. Una classe che possegga un solo elemento vien detta “classe unità” (per esempio, la classe dei satelliti del pianeta terra); e il numero cardinale 1 può essere definito come la classe di tutte le classi simili a una classe unità. Definizioni analoghe possono darsi degli altri numeri cardinali, e le varie operazioni aritmetiche, come l’addizione e la moltiplicazione, possono essere definite mediante nozioni della logica formale. Una proposizione aritmetica, come ‘1 + 1 = 2’, può dunque essere considerata come una traduzione condensata di una proposizione contenente solo espressioni appartenenti alla logica generale; e tali proposizioni puramente logiche sono deducibili, come si può mostrare, da certi assiomi logici.
I Principia mathematica apparvero, così, come un progresso verso la soluzione finale del problema dell’autocompatibilità dei sistemi matematici, e di quelli aritmetici in particolare, riducendo il problema a quello della coerenza della logica formale stessa. Se, infatti, gli assiomi dell’aritmetica sono semplici trascrizioni dei teoremi della logica, il problema se gli assiomi dell’aritmetica siano fra loro compatibili è equivalente al problema se gli assiomi fondamentali della logica siano fra loro compatibili.
La tesi di Russell e di Frege, secondo la quale la matematica non è altro che un capitolo della logica, non ha incontrato, per diversi motivi particolari, l’universale consenso dei matematici. Inoltre, come abbiamo già notato, le antinomie della teoria di Cantor dei numeri transfiniti possono essere ripetute all’interno della logica stessa, a meno che non vengano prese speciali precauzioni atte a impedire una tale eventualità. Ma le precauzioni adottate nel Principia mathematica per girare intorno alle antinomie sono atte a escludere tutte le forme di costruzioni contraddittorie? Non lo si può affermare con troppa leggerezza. Perciò la riduzione di Frege e di Russell dell’aritmetica alla logica non fornisce una risposta conclusiva al problema della compatibilità: infatti il problema si caratterizza in una forma piú generale. Ma, lasciando da parte la validità della tesi di Frege e Russell, due aspetti dei Principia si sono dimostrati di inestimabile valore per uno studio ulteriore del problema della compatibilità. I Principia forniscono un sistema notevolmente ampio di notazioni, con l’aiuto delle quali tutte le proposizioni della matematica pura (e dell’aritmetica, in particolare) possono essere codificate in una maniera generale; e rendono esplicite la maggior parte delle regole di inferenza formale usate nelle dimostrazioni matematiche (in certi casi, queste regole furono meglio precisate e completate). I Principia, in sostanza, crearono gli strumenti essenziali per investigare l’intero sistema dell’aritmetica come calcolo non dotato di interpretazione, vale a dire, come sistema di segni senza significato, le cui formule (o “catene”) vengono combinate e trasformate secondo regole di operazione ben definite.

Note al capitolo 4

Nota 1.D’ora in avanti sopprimeremo l’espressione “è vero” in tutti i casi di questo genere, per ottenere una maggiore semplicità formale. [N. d. t.]

Nota 2.Analizziamo il ragionamento che fa passare al punto 6) dai punti 3), e 5), nella dimostrazione di Euclide. Designiamo le lettere ‘p’, ‘q’ ed ‘r’ come “variabili proposizionali”, in quanto al posto di esse si possono sostituire delle proposizioni. Inoltre, per economia di spazio, scriviamo le espressioni condizionali del tipo ‘se p allora q’ nella forma ‘p É q’, e denominiamo l’espressione a sinistra del segno ‘É ’ 1’“antecedente”, e l’espressione alla sua destra il “conseguente”. Similmente, scriviamo ‘p Ú q’ come abbreviazione della formula alternativa ‘o p o q’.
Vi è un teorema della logica elementare che si scrive (p É r) É [ (p É r) É ((p Ú q) É r) ]. Si può dimostrare che esso esprime una verità necessaria. Il lettore si accorgerà che questa formula afferma in maniera piú compatta ciò che è espresso dalla seguente proposizione molto piú lunga: se (se p allora r), allora [se (se q allora r), allora (se (o p o q) allora r)]. Come è stato già fatto osservare, esiste una regola di inferenza, in logica, chiamata la regola di sostituzione per le variabili proposizionali. Secondo questa regola, una proposizione S₂ segue logicamente da una proposizione S₁ che contiene delle variabili proposizionali, se la prima è ottenuta dalla seconda sostituendo uniformemente delle proposizioni qualsiasi al posto delle variabili. Se applichiamo questa regola al teorema ora menzionato sostituendo ‘y è un numero primo’ al posto di ‘p’, ‘y è un numero composto’ al posto di ‘q’, e ‘x non è il numero primo piú grande di tutti’ al posto di ‘r’, otteniamo la seguente espressione:

(y è un numero primo É x non è il numero primo piú grande di tutti)É [ (y è un numero composto É x non è il numero primo piú grande di tutti) É ((y è un numero primo Ú è un numero composto) É x non è il numero primo piú grande di tutti)].

Nota 3.Per esempio, dei principi impliciti nella seguente deduzione: 5 è maggiore di 3; quindi il quadrato di 5 è maggiore del quadrato di 3.

TABELLA 1

Tutti i gentiluomini sono educati.

Nessun banchiere è educato.

Nessun gentiluomo è banchiere.

	g Ì e
	b Ì e
\	g Ì b

ge = 0

be = 0

gb = 0

La logica simbolica fu inventata, verso la metà del secolo diciannovesimo, dal matematico inglese George Boole. Nello schema riportato, un sillogismo è tradotto nella sua notazione in due maniere diverse. Nel gruppo di formule superiore, il simbolo ‘Ì’ significa “è contenuto in’. Cosí, ‘g Ì e’ vuol dire che la classe dei gentiluomini è compresa nella classe delle persone educate. Nel gruppo inferiore di formule, due lettere vicine significano la classe delle cose che hanno tutte e due le caratteristiche. Per esempio, ‘be’ significa la classe degli individui che sono banchieri e sono educati; e l’equazione ‘b e= 0’ dice che questa classe non ha membri. Una lineetta sotto una lettera significa “non”. (‘e’, per esempio, significa non educato.) Infine, il segno \significa ‘ne segue che’.

Ernst Nagel e James R. Newman
La prova di Gödel
5. Un esempio di dimostrazione assoluta di compatibilità valida

Dobbiamo ora affrontare il secondo obiettivo che ci eravamo proposti all’inizio del capitolo precedente, e familiarizzarci con un importante, sebbene facilmente comprensibile, esempio di dimostrazione assoluta di compatibilità. Assimilando questa prova, il lettore sarà in una posizione migliore per apprezzare il significato dell’articolo di Gödel del 1931.
Faremo vedere come una piccola parte dei Principia, la logica elementare delle proposizioni, possa venir formalizzata. Ciò comporta la conversione di un sistema frammentario in un calcolo di segni senza interpretazione. Svilupperemo, quindi, una dimostrazione assoluta di compatibilità.

La formalizzazione procede secondo quattro fasi.

Primo,
viene preparato un catalogo completo dei segni che si useranno nel calcolo: il suo vocabolario. Nel caso della logica delle proposizioni (spesso chiamata calcolo proposizionale), il vocabolario (o la lista dei “segni elementari ”) è estremamente semplice. Esso consiste di segni variabili e di segni costanti.
Le variabili possono essere sostituite da proposizioni e vengono perciò chiamate “Variabili proposizionali”. Esse vengono indicate dalle lettere ‘p’, ‘q’, ‘r’, ecc. I segni costanti sono “ connettivi proposizionali ” oppure segni d’interpunzione. I connettivi proposizionali sono:

‘~’ che significa ‘non’;
‘Ú’ che significa‘oppure’;
‘É’che significa ‘se ... allora...’;
‘.’ che significa ‘e’.
I segni d’interpunzione sono le parentesi tonde; ‘(’ e ‘)’.
Secondo,
vengono scritte le “regole di formazione”. Esse stabiliscono quali delle combinazioni possibili fra i segni del vocabolario sono accettabili come “formule” (cioè, come proposizioni). Le regole si possono pensare come costituenti la grammatica del sistema. Le regole di formazione sono fatte in maniera tale che combinazioni di segni elementari, che normalmente avrebbero la forma di proposizioni, vengono chiamate formule. Ciascuna variabile proposizionale conta pure come una formula. Inoltre, se la lettera ‘S’ sta per una formula, la sua negazione formale, ~ (S), sta pure per una formula. Similmente, se S₁ ed S₂ sono formule, anche (S₁)Ú(S₂), (S₁)É(S₂) e (S₁).(S₂) lo sono. Ciascuna delle seguenti espressioni è una formula: ‘p’, ‘ ~ (p)’, ‘(p) É (q)’, ‘((q) Ú ((r)) É (p)’. Ma né ‘(p)( ~ (q))’, né ‘((p) É (q)) Ú’ sono delle formule: la prima perché, mentre ‘(p)’ e ‘( ~ (q))’ sono formule, non compare alcun connettivo proposizionale fra esse; la seconda perché il connettivo ‘Ú’ non è preceduto e seguito, come la regola richiede, da formule [1].
Terzo,
vengono definite le “regole di trasformazione”. Esse descrivono la struttura precisa delle formule da cui sono derivabili altre formule di data struttura. Di fatto, queste regole sono le regole di inferenza.
Vengono adottate due regole di trasformazione
regola di sostituzione (per le variabili proposizionali).
Da una formula contenente delle variabili proposizionali è sempre permesso derivare un’altra formula sostituendo uniformemente delle formule alle variabili. È inteso che, quando si sostituisce una variabile in una formula, la stessa sostituzione deve essere fatta ogni volta che compare quella variabile. Per esempio, supponendo che sia stato dimostrato che ‘p É p’, possiamo sostituire alla variabile ‘p’ la formula ‘q’ ottenendo ‘q É q’; oppure possiamo sostituire la formula ‘p Ú q’, ottenendo ‘(pÚq) É (pÚq)’. Oppure, se sostituiamo a ‘p’ delle frasi normali nella nostra lingua, possiamo ottenere da ‘pÉp proposizioni come le seguenti: ‘le rane fanno rumore É le rane fanno rumore’; ‘(i pipistrelli sono ciechi Ú i pipistrelli mangiano i topi) É (i pipistrelli sono ciechi Ù i pipistrelli mangiano i topi)’. D’altra parte, supponiamo che la formula ‘(p É q) É ( ~q É ~p)’ sia stata dimostrata, e, che noi decidiamo di sostituire alla variabile ‘p’ la formula ‘r’ e alla variabile ‘q’ la formula ‘p Ú r’. Con questa sostituzione, non possiamo ottenere la formula ‘(r É (p Ú r)) É ( ~ q É ~ r)’, perché non abbiamo sostituito la variabile ‘q’ ovunque compariva. La sostituzione corretta porge ‘(r É (p Ú r)) É (~(p Ú r) É ~ r)’[2].
la regola di separazione (o modus ponens).
Da due formule della forma S₁ ed S₁É S₂ è sempre possibile dedurre la formula S₂. Per esempio, dalle due formule ‘p Ú ~p’ e ‘(p Ú ~p) É (p É p)’, possiamo dedurre ‘p É p’ .
Quarto,
certe formule vengono scelte come assiomi (o “proposizioni primitive”). Esse costituiscono il fondamento dell’intero sistema.
Useremo l’espressione “teoremi del sistema” per denotare qualsiasi formula che possa essere dedotta dagli assiomi applicando successivamente le regole di trasformazione. Con l’espressione “prova” (o “dimostrazione” formale intenderemo una sequenza finita di formule, ciascuna delle quali è un assioma o può essere dedotto dalle formule precedenti della sequenza mediante le regole di trasformazione [3].
Gli assiomi del calcolo (sostanzialmente quelli dei Principia) sono le seguenti quattro formule:

1) (p Ú p) É p o, nel linguaggio ordinario, se p o p allora p; se (Enrico VIII era un uomo grossolano oppure Enrico VIII era un uomo grossolano) allora Enrico VIII era un uomo grossolano;
2) p É (p Ú q) cioè, se p allora o p o q; se la psicoanalisi è di moda allora (la psicoanalisi è di moda oppure le pillole per il mal di testa costano poco);
3) (pÚ q) É (q Ú p) cioè, se p o q allora q o p; se (o Immanuel Kant era puntuale o Hollywood è peccaminosa) allora (o Hollywood è peccaminosa o Immanuel Kant era puntuale);
4) (pÉ q)É ((r Ú p)) É (r Ú q)) cioè, se (se p allora q) allora [se (o r o p) allora (o r o q)]. se (se le anitre si muovono goffamente, allora 5 è un numero primo), allora [se (o Churchill beve brandy o le anitre si muovono goffamente), allora (o Churchill beve brandy o 5 è un numero primo)
Nella colonna di sinistra abbiamo scritto gli assiomi, insieme con la loro traduzione nel linguaggio normale. Nella colonna a destra abbiamo dato un esempio per ciascun assioma. La goffaggine della ‘traduzione’, specialmente nel caso dell’ultimo assioma, convincerà il lettore dei vantaggi insiti nell’uso di uno speciale simbolismo nella logica formale. È importante osservare, inoltre, che le frasi senza senso usate come esempi da sostituire negli assiomi, e il fatto che nelle proposizioni condizionali le conseguenze non sono in relazione sensata con le premesse, non pregiudicano affatto la validità delle connessioni logiche asserite negli esempi.

Ciascuno degli assiomi può sembrare “ovvio” e banale. Ciononostante, è possibile derivare da essi, con l’aiuto delle regole di trasformazione esposte, una classe infinitamente ampia di teoremi che sono ben lontani dall’essere ovvi e banali. Per esempio, la formula

‘[(p É q)É (( r É s) É t)] É [(u É ((r É s) É t)) É ((p É u) É (s É t))]’ può essere dedotta come teorema. Per il momento, però, non ci interessiamo di derivare dei teoremi dagli assiomi. Il nostro obiettivo è di dimostrare che questo insieme di assiomi non è contraddittorio; vogliamo provare cioè, “assolutamente”, che è impossibile, usando le regole di trasformazione, dedurre dagli assiomi una certa formula S insieme con la sua negazione formale ~S.
Ora, si può dimostrare che ‘p É ( ~ p É q)’ (in parole: ‘se p, allora se non p allora q’) è un teorema del calcolo. (Accetteremo questo come un dato di fatto, senza riportare la dimostrazione.) Supponiamo, quindi, che una certa formula S come pure la sua contraddittoria ~ S siano deducibili dagli assiomi. Sostituendo S alla variabile ‘p’ nel teorema (come è lecito in base alla regola di sostituzione), e applicando due volte la regola di separazione, sarebbe deducibile la formula ‘q’[4]. Ma, se la formula costituita dalla variabile ‘q’ è dimostrabile, ne segue immediatamente che, sostituendo una qualsiasi formula al posto di ‘q’, qualsiasi formula è deducibile dagli assiomi. Appare cosí chiaramente che, se la formula S insieme con la sua contraddittoria ~S fosse deducibile dagli assiomi, qualsiasi formula sarebbe deducibile dagli assiomi. In breve, se il calcolo non è autocompatibile, ogni formula è un teorema, il che equivale a dire che da un insieme contraddittorio di assiomi è possibile dedurre una qualsiasi formula. Ma questo risultato ha un inverso: infatti, se non ogni formula è un teorema (cioè, se vi è almeno una formula che non è derivabile dagli assiomi), allora il calcolo è autocompatibile. Il problema, allora, è di dimostrare che vi è almeno una formula che non può essere dedotta dagli assiomi.
La maniera di condurre la dimostrazione è di applicare il ragionamento metamatematico al sistema che ci sta dinanzi. Il procedimento è molto elegante. Esso consiste nel trovare una caratteristica o una proprietà strutturale delle formule che soddisfi alle seguenti tre condizioni:

1) la proprietà deve essere comune a tutti e quattro gli assiomi (per esempio, una tale proprietà è quella di contenere non piú di venticinque segni elementari, ma tale proprietà non soddisfa alla condizione seguente);

2) la proprietà deve essere “ereditaria” per le regole di trasformazione: cioè, se tutti gli assiomi hanno tale proprietà, una qualsiasi formula correttamente dedotta da essi, mediante le regole di trasformazione, deve possederla anch’essa; dato che ogni formula cosí dedotta è, per definizione, un teorema, questa condizione stabilisce, sostanzialmente, che ogni teorema deve possedere quella proprietà;

3) la proprietà non deve appartenere a ogni formula che può essere costruita usando solo le regole di formazione: cioè, dobbiamo cercare di trovare almeno una formula che non possiede le proprietà in questione.
Se noi risolviamo positivamente questo triplo compito, abbiamo una dimostrazione assoluta dell’autocompatibilità del sistema. Il ragionamento si articola piú o meno così: la proprietà ereditaria si trasmette dagli assiomi a tutti i teoremi; ma se si riesce a trovare una configurazione di segni che risponde ai requisiti per essere una formula del sistema e che, ciononostante, non possiede la proprietà ereditaria specificata, allora questa formula non può essere un teorema. Possiamo dire le cose in un’altra maniera: se una formula manca di una caratteristica invariabilmente ereditata dagli assiomi, non può essere di fatto una loro conseguenza. Ma, se si scopre una formula che non è un teorema, abbiamo dimostrato l’autocompatibilità del sistema; infatti, come abbiamo appena notato, se il sistema non fosse coerente, ogni formula potrebbe essere dedotta dagli assiomi, cioè ogni formula sarebbe un teorema. In breve, l’esistenza di una singola formula senza la proprietà ereditaria risolve il problema.
Individuiamo una proprietà del genere richiesto. Scegliamo la proprietà di essere una “tautologia”. Nel linguaggio ordinario, usualmente si dice che una locuzione è tautologica se contiene una ridondanza e se dice la stessa cosa due volte con parole diverse. Per esempio: ‘Giovanni è il padre di Carlo e Carlo è il figlio di Giovanni’. In logica, però, una tautologia è definita come una proposizione che non esclude alcuna possibilità logica. Per esempio: ‘O piove o non piove’. Un’altra maniera di dire le cose è che una tautologia è “vera in ogni mondo possibile”. Nessuno dubita che, a prescindere dallo stato reale del tempo (cioè a prescindere dal fatto che la proposizione piove, sia vera o falsa), la proposizione ‘o piove o non piove’ è necessariamente vera.
Noi useremo questa nozione per definire la tautologia nel nostro sistema. Notiamo, innanzitutto, che ogni formula è costruita con costituenti elementari ‘p’, ‘q’, ‘r’, ecc. Una formula è una tautologia se è invariabilmente vera, a prescindere dal fatto che i suoi costituenti elementari siano veri o falsi. Cosi, nel primo assioma ‘(p Ú p) É p’, l’unico costituente elementare è ‘p’; ma non fa alcuna differenza se ‘p’ si suppone sia vero o falso: il primo assioma è vero in entrambi i casi. Lo si può vedere se sostituiamo a ‘p’ la proposizione ‘il monte Rainier è alto ventimila piedi’; otteniamo cosí, come esempio del primo assioma, la proposizione ‘se o il monte Rainier è alto ventimila piedi o il monte Rainier è alto ventimila piedi, allora il monte Rainier è alto ventimila piedi’. Il lettore si accorgerà subito, senza alcuna difficoltà, che questa lunga proposizione è vera, anche se non sapesse se la frase costitutiva ‘il monte Rainier è alto ventimila piedi’ è vera oppure no. Ovviamente, quindi, il primo assioma è una tautologia, cioè “vero in ogni mondo possibile”. Si può dimostrare facilmente che ciascuno degli assiomi rimanenti è anche una tautologia.
Successivamente, è possibile provare che la proprietà di essere una tautologia è ereditaria per le regole di trasformazione, cosicché ogni formula correttamente dedotta dagli assiomi (cioè, ogni teorema) deve essere una tautologia.[5]
Si è visto che la proprietà di essere una tautologia soddisfa a due delle tre condizioni summenzionate; ora siamo pronti per compiere il terzo passo. Dobbiamo cercare una formula che appartenga al sistema (cioè, sia costruita con i segni che si trovano nel vocabolario e secondo le regole di formazione), ma che non possa essere un teorema (cioè, non possa essere dedotta dagli assiomi), in quanto non dotata delle proprietà di essere una tautologia. Questa ricerca non è molto difficile. Per esempio, ‘p Ú q’ ha le proprietà richieste. Ha l’aspetto di un papero, ma in realtà è un anatroccolo: non appartiene alla famiglia. È una formula, ma non un teorema. Evidentemente non è una tautologia. Un esempio di sostituzione (o interpretazione) lo rivela immediatamente. Possiamo ottenere, per sostituzione delle variabili in ‘p Ú q’, la proposizione ‘Napoleone morì di cancro o Bismarck gradiva una tazza di caffè’. Questa non è una verità logica, perché sarebbe falsa se entrambe le proposizioni che intervengono in essa fossero false; e, anche se è una proposizione vera, non è vera a prescindere dalla falsità o dalla verità delle sue proposizioni costituenti (si ricordi quanto è stato detto piú sopra a proposito della tautologia).
Abbiamo così raggiunto il nostro obiettivo. Abbiamo trovato almeno una formula che non è un teorema. Una tale formula non potrebbe esistere se gli assiomi fossero contraddittori. Conseguentemente, non è possibile dedurre dagli assiomi del calcolo proposizionale una formula e la sua negazione. In breve, abbiamo dato una dimostrazione assoluta dell’autocompatibilità del sistema [6].
Prima di lasciare il calcolo proposizionale, dobbiamo parlare di un’ultima cosa. Dato che ogni teorema di questo calcolo è una tautologia, una verità logica, è naturale domandarci se, inversamente, ogni verità logica esprimibile mediante il vocabolario del calcolo (cioè, ogni tautologia) è anche un teorema (cioè, è derivabile dagli assiomi). La risposta è affermativa, sebbene la dimostrazione sia troppo lunga per essere riportata in questa sede. Il punto che ci interessa, però, non dipende dalla nostra conoscenza della dimostrazione. Si tratta del fatto che, alla luce di questa conclusione, gli assiomi sono sufficienti a generare tutte le formule tautologiche, cioè tutte le verità logiche esprimibili nell’ambito del sistema. Assiomi di tale tipo si dicono “completi”.
Ora, spesso è di interesse fondamentale determinare se un sistema assiomatizzato è completo. Infatti, uno dei motivi principali per l’assiomatizzazione delle varie parti della matematica è stato quello di stabilire un insieme di ipotesi iniziali dalle quali fossero deducibili tutte le proposizioni vere in un certo campo di ricerca. Quando Euclide assiomatizzò la geometria elementare, evidentemente egli scelse i suoi assiomi in modo che fosse possibile dedurre da essi tutte le verità geometriche, quelle che già erano state stabilite e quelle che si sarebbero scoperte in futuro. Di passaggio, è interessante notare come Euclide abbia avuto un profondo intuito nel trattare il suo famoso assioma delle parallele come un’ipotesi logicamente indipendente dagli altri suoi assiomi. Infatti, come fu dimostrato in seguito, quest’assioma non può essere dedotto dalle altre ipotesi, cosicché senza di esso l’insieme degli assiomi è incompleto.
Ancora recentemente, si riteneva come ovvio che si potesse mettere insieme un insieme completo di assiomi per ogni ramo della matematica. In particolare, i matematici credevano che l’insieme proposto per l’aritmetica, nel passato, fosse di fatto completo, o che, nel caso peggiore, potesse essere reso completo semplicemente aggiungendo un numero finito di assiomi a quelli già esistenti. La scoperta dell’impossibilità di realizzare un tale programma è uno del risultati piú importanti di Gödel.

Note al capitolo 5

Nota 1.Quando non vi è possibilità di confusione, i segni d’interpunzione (cioè le parentesi) possono essere tralasciate. Cosí, invece di scrivere ‘~(p)’, è sufficiente scrivere ‘~p’; e invece di ‘(p) É (q)’, semplicemente ‘p É q’.

Nota 2.Esempio di sostituzione nella formula ‘(p É q) É ( ~q É ~p)’ della variabile ‘p’ con la formula ‘r’ e della variabile ‘q’ con la formula ‘(p Ú r)’.

Nota 3.Ne segue immediatamente che gli assiomi devono essere considerati dei teoremi.

Nota 4.‘p É ( ~ p É q)’. Sostituendo S a ‘p’, otteniamo: S É (~S É q). Da questa e dalla S che supponiamo sia dimostrabile, otteniamo, con la regola di separazione, ~S É q. Finalmente, dato che ~S si suppone pure dimostrabile, usando la regola di separazione ancora una volta, otteniamo: q.

Nota 5.Si può ragionare nella maniera seguente. La proprietà di essere una tautologia è stata definita in termini di vero e falso. Queste nozioni, ovviamente, implicano un riferimento a qualche cosa al di fuori del calcolo formale. Perciò, il procedimento sopra descritto offre, in effetti, un’interpretazione del calcolo, fornendo un modello del sistema. Cosí facendo, gli autori non hanno mantenuto la loro promessa di definire una proprietà delle formule in termini di pure caratteristiche strutturali delle formule stesse. Sembra che la difficoltà notata nel capitolo 2 - che le dimostrazioni di compatibilità che sono basate su modelli, e che partono dalla verità degli assiomi per giungere alla loro reciproca compatibilità, spostino semplicemente il problema - non sia stata, dopo tutto, evitata con successo. Perché allora chiamare la prova “assoluta” anziché relativa?
Questa obiezione è giusta se si riferisce all’esposizione del nostro libro. Ma noi abbiamo adottato questa forma per non opprimere il lettore non abituato con una presentazione altamente astratta che avrebbe fornito una dimostrazione intuitivamente opaca. Poiché il lettore piú avventuroso può desiderare di essere messo di fronte alle cose come stanno, di vedere una definizione non abbellita la quale non sia passibile delle obiezioni in questione, daremo la dimostrazione rigorosa.
Ricordiamo che una formula del calcolo è una delle lettere usate come variabili proposizionali (che abbiamo dianzi chiamate formule elementari) o un composto di queste lettere, dei segni usati come connettivi proposizionali, e di parentesi. Conveniamo di includere ogni formula elementare in una delle due classi mutuamente esclusive ed esaurienti K₁ e K₂. Formule non elementari vengono incluse in queste classi secondo le convenzioni seguenti:

1) una formula avente la forma S₁ Ú S₂ è posta nella classe K₂ se S₁ ed S₂ sono entrambe in K₁; altrimenti viene posta in K₂

2) una formula avente la forma S₁ É S₂ viene posta in K₂ se S₁ è in K₁ ed S₂ in K₂; altrimenti viene posta in K₁

3) una formula avente la forma S₁.S₂ viene posta in K₁, se S₁ ed S₂ sono entrambe in K₁; altrimenti viene posta in K₂

4) una formula avente la forma ~S₁ viene posta in K₂, se S₁ è in K₁, altrimenti viene posta in K₁

S`₁`	S`₂`	S`₁` Ú S`₂`	S`₁` É S`₂`	S`₁` . S`₂`	~S`₁`
K`₁`	K`₁`	K`₁`	K`₁`	K`₁`	K`₁`
K`₁`	K`₂`	K`₁`	K`₂`	K`₂`	K`₁`
K`₂`	K`₁`	K`₁`	K`₁`	K`₂`	K`₂`
K`₂`	K`₂`	K`₂`	K`₁`	K`₂`	K`₂`

Definiamo ora la proprietà di essere una tautologia: una formula è una tautologia se, e solo se, essa si trova nella classe K₁, a prescindere da quale delle due classi contenga i suoi costituenti elementari. È chiaro che la proprietà di essere una tautologia viene descritta, in questa maniera, senza usare un qualsiasi modello o interpretazione del sistema. Siamo in grado di scoprire se una formula è una tautologia oppure no semplicemente confrontando la sua struttura con le convenzioni sopra fatte.
Un tale esame mostra che ciascuno dei quattro assiomi è una tautologia. Un procedimento conveniente è quello di costruire una tabella che elenchi tutte le maniere possibili in cui i costituenti elementari dì una data formula possono essere posti nelle due classi. Da questa tabella possiamo determinare, per ciascuna possibilità, a quale classe appartengono i costituenti non elementari della formula data, e a quale classe la formula intera appartiene.

assioma 1): p Ú p) É p

p	(p Ú p)	(pÚp)Ép
K`₁`	K`₁`	K`₁`
K`₂`	K`₂`	K`₁`

La prima colonna di tale tabella riporta i modi possibili di classificare l’unico elemento costituente dell’assioma. La seconda colonna assegna il costituente non elementare a una classe, in base alla convenzione 1). L’ultima colonna assegna l’assioma stesso a una classe, in base alla convenzione 2). Quest’ultima colonna mostra che il primo assioma appartiene alla classe K₁, a prescindere dalla classe in cui viene posto l’unico costituente elementare. L’assioma è quindi una tautologia.

assioma 2): p É (p Ú q)

p	q	(p Ú q)	p É (p Ú q)
K`₁`	K`₁`	K`₁`	K`₁`
K`₁`	K`₂`	K`₁`	K`₂`
K`₂`	K`₂`	K`₁`	K`₁`
K`₂`	K`₂`	K`₂`	K`₁`

Le prime due colonne di tale tabella elencano le quattro maniere possibili di classificare i due costituenti elementari dell’assioma. La terza colonna assegna il costituente non elementare a una classe, in base alla convenzione 1). L’ultima colonna ha la stessa funzione per l’assioma stesso, in base alla convenzione 2). Quest’ultima colonna, di nuovo, mostra che il secondo assioma appartiene alla classe K₁ per ciascuna delle quattro maniere possibili in cui i costituenti elementari possono essere classificati. L’assioma è quindi una tautologia.

In maniera simile si può mostrare che gli altri due assiomi sono delle tautologie.
Daremo anche la dimostrazione che la proprietà di essere una tautologia è ereditaria per la regola di separazione. (La dimostrazione che è ereditaria per la regola di sostituzione viene lasciata al lettore.) Supponiamo che due formule S₁ ed S₁ É S₂ siano entrambe delle tautologie; vogliamo mostrare che in tal caso S₂ è una tautologia. Supponiamo che S₂ non sia una tautologia. Allora, almeno per una classificazione dei suoi costituenti elementari, S₂ apparterrà a K₂. Ma, per ipotesi, S₁ è una tautologia, per cui apparterrà a K₁ per tutte le classificazioni dei suoi costituenti elementari, e, in particolare, per la classificazione che implica l’appartenenza di S₂ a K₂. In base a ciò, per quest’ultima classificazione, S₁ É S₂ deve appartenere a K₂, per la convenzione 2). Questo però, contraddice l’ipotesi che S₁ É S₂ sia una tautologia. Di conseguenza, S₂ deve essere una tautologia, se vogliamo evitare tale contraddizione. La proprietà di essere una tautologia viene quindi trasmessa, dalla regola di separazione, dalle premesse alle conclusioni deducibili da esse mediante la detta regola.
Ed ora un commento finale sulla definizione di tautologia data precedentemente. Le due classi K₁ e K₂ usate nella dimostrazione, possono essere interpretate come le classi delle proposizioni vere e false, rispettivamente. Ma il risultato e la dimostrazione, come abbiamo visto, non dipendono in alcuna maniera da tale interpretazione, anche se l’esposizione viene piú facilmente compresa quando le due classi vengono identificate in tal modo.

Nota 6.Il lettore può trovare utile la seguente ricapitolazione della dimostrazione:

1) ogni assioma del sistema è una tautologia;

2) la proprietà di essere una tautologia è ereditaria;

3) ogni formula correttamente dedotta dagli assiomi (cioè, ogni teorema) è anche una tautologia;

4) quindi ogni formula che non sia una tautologia non è un teorema;

5) si trova una formula (per esempio, ‘p Ú q’) che non è una tautologia;

6) questa formula non è, quindi, un teorema;

7) ma, se gli assiomi fossero contraddittori, ogni formula sarebbe un teorema;

8) quindi, gli assiomi sono coerenti.

Ernst Nagel e James R. Newman
La prova di Gödel
6. L’idea della rappresentazione e il suo uso in matematica

Il calcolo proposizionale è un esempio di sistema matematico per il quale gli obiettivi della teoria hilbertiana sono perfettamente realizzati. In realtà, questo calcolo codifica solo una piccola parte della logica formale, e il suo vocabolario e il suo apparato formale non sono sufficienti per sviluppare neanche l’aritmetica elementare. Il programma di Hilbert, tuttavia, non è così limitato. Esso può essere realizzato con successo per sistemi piú ampi, i quali, come si può dimostrare con ragionamenti metamatematici, sono coerenti e completi. Per esempio, si possiede una dimostrazione assoluta dell’autocompatibilità di un sistema aritmetico che ammette l’addizione dei numeri cardinali ma non la moltiplicazione. Ma il metodo finitistico di Hilbert è abbastanza potente da dimostrare la coerenza di un sistema come i Principia, il cui vocabolario e il cui apparato logico sono adatti a esprimere l’intera aritmetica e non soltanto un frammento di essa? Tentativi ripetuti di costruire una tale dimostrazione non ebbero successo; e la pubblicazione del lavoro di Gödel nel 1931 mostrò, finalmente, che tutti questi sforzi operanti all’interno degli stretti limiti del programma originale di Hilbert sono destinati a fallire.
Che cosa stabili Gödel, e in quale maniera dimostrò i suoi risultati? Le sue conclusioni principali sono di due tipi. In primo luogo (per quanto questo non sia l’ordine usato da Gödel), egli mostrò che è impossibile dare una dimostrazione metamatematica della coerenza di un sistema abbastanza ampio da contenere l’aritmetica, a meno che la dimostrazione non usi delle regole d’inferenza per certi aspetti essenzialmente differenti dalle regole di trasformazione usate nella deduzione del teoremi nel sistema dato. Una tale dimostrazione, a dire il vero, può possedere un grande valore e una grande importanza. Però, se il tipo di ragionamento in essa usato è basato su regole d’inferenza molto piú potenti delle regole del calcolo aritmetico, cosí che la coerenza delle ipotesi nel processo ragionativo possa essere messa in dubbio come la coerenza dell’aritmetica, la dimostrazione riporterebbe soltanto una vittoria apparente: un drago ucciso solo per crearne un altro. In ogni caso, se la dimostrazione non è finitistica, essa non realizza l’obiettivo del programma di Hilbert; e le argomentazioni di Gödel rendono molto improbabile che una dimostrazione finitistica della coerenza dell’aritmetica possa essere costruita.
La seconda conclusione principale di Gödel è anche piú sorprendente e rivoluzionaria della prima, in quanto dimostra una fondamentale limitazione delle possibilità del metodo assiomatico. Gödel mostrò che i Principia, o qualsiasi altro sistema nel cui ambito possa venir sviluppata l’aritmetica, è essenzialmente incompleto. In altre parole, dato un insieme qualsiasi di assiomi aritmetici, vi sono delle proposizioni aritmetiche logicamente vere le quali non possono essere dedotte dall’insieme. Questo punto cruciale merita un’illustrazione. La matematica abbonda di proposizioni generali, alle quali non si è mai trovata un’eccezione, che hanno resistito a tutti i tentativi di dimostrazione. Un esempio classico è noto come “teorema di Goldbach”, e afferma che ogni numero pari è la somma di due numeri primi. Non si è mai trovato un numero pari che non fosse la somma di due numeri primi, ma nessuno è riuscito a trovare una dimostrazione che la congettura di Goldbach si applichi, senza eccezione, a tutti i numeri pari. Questo, quindi, è un esempio di proposizione aritmetica che può essere vera, ma non derivabile dagli assiomi dell’aritmetica. Supponiamo, ora, che l’idea di Goldbach sia universalmente vera, per quanto non deducibile dagli assiomi. Che cosa si può dire della possibilità che, in tale eventualità, gli assiomi vengano modificati o completati in maniera tale che proposizioni finora indimostrate (come quella di Goldbach, nella nostra ipotesi) possano venir dedotte dal sistema modificato? I risultati di Gödel provano che, anche se l’ipotesi fosse corretta, tale possibilità non porterebbe alcun rimedio sostanziale alla difficoltà. Vale a dire, se anche gli assiomi dell’aritmetica fossero aumentati di un numero indefinito di altri assiomi veri, vi sarebbero sempre altre verità aritmetiche. formalmente non deducibili dall’insieme piú ampio. Tali proposizioni vere potrebbero, come vedremo, essere dimostrate mediante una forma di ragionamento metamatematico sul sistema aritmetico. Ma un tale procedimento non soddisfa al requisito che il calcolo debba essere, per così dire, autocontenuto, e che le verità in questione debbano essere mostrate come conseguenze formali degli assiomi specificati del sistema. Vi è, quindi, una limitazione inerente al metodo assiomatico in quanto metodo di sistematizzazione dell’intera aritmetica.
Come giunse Gödel alle sue conclusioni? Fino a un certo punto, la struttura di questo argomento è modellata, come egli stesso fece osservare, sul tipo di ragionamento impiegato in una delle antinomie logiche nota come “paradosso di Richard”, dal nome del matematico francese Jules Richard che per primo la propose nel 1905. Descriveremo questo paradosso.
Consideriamo un linguaggio in cui le proprietà puramente aritmetiche dei numeri cardinali possano essere formulate e definite. È chiaro che, se si vogliono evitare circoli viziosi o regressi all’infinito, certi termini che si riferiscono a proprietà aritmetiche non possono essere definiti esplicitamente - in quanto non possiamo definire tutto e dobbiamo partire da qualche cosa - sebbene essi possano, presumibilmente, essere compresi in altro modo. Per i nostri scopi, non importa quali siano i termini non definiti o “primitivi”; possiamo supporre, per esempio, di conoscere ciò che intendiamo con ‘un intero è divisibile per un altro intero’, ‘un intero è il prodotto di due interi’, e cosí via. La proprietà di essere un numero primo può venir definita così: ‘non divisibile da altri interi che non siano l’unità o se stesso’; la proprietà di essere un quadrato perfetto potrebbe essere definita in questa maniera: ‘essere il prodotto di un intero per se stesso’; e così via.
Possiamo vedere come ciascuna definizione contenga solo un numero finito di parole, e perciò solo un numero finito di lettere dell’alfabeto. Stando così le cose, le definizioni possono essere ordinate in una serie: una definizione precederà un’altra se il numero di lettere della prima è minore del numero di lettere della seconda; e, se due definizioni hanno lo stesso numero di lettere, l’una precederà l’altra in base all’ordine alfabetico delle lettere in ciascuna di esse. Nell’ambito di questa ordinazione, a ciascuna definizione corrisponderà un numero intero unico, che rappresenterà il posto che la definizione occupa nella serie. Per esempio, la definizione con il numero piú piccolo di lettere corrisponderà al numero 1, la definizione successiva al numero 2, ecc.
Dato che ogni definizione è associata a un unico intero, può accadere che, in certi casi, l’intero possegga proprio la proprietà presente nella definizione con la quale è correlato l’intero stesso [1]. Supponiamo, per esempio, che l’espressione ‘non divisibile per alcun intero diverso dall’unità e da se stesso’ sia correlata con il numero d’ordine 17; ovviamente lo stesso numero 17 ha la proprietà definita dall’espressione. D’altra parte, supponiamo che l’espressione ‘essere il prodotto di un intero per se stesso’ sia correlata con il numero d’ordine 15; evidentemente 15 non possiede la proprietà definita dall’espressione. Descriveremo tale stato di cose dicendo che il numero 15 ha la proprietà di essere richardiano, e - nel primo esempio - dicendo che il numero 17 non ha la proprietà di essere richardiano. Piú generalmente, conveniamo che ‘x è richardiano’ sia un modo conciso di dire ‘x non possiede la proprietà definita dall’espressione alla quale è correlato il numero x nell’insieme serialmente ordinato delle definizioni’.
Veniamo ora a un aspetto curioso ma caratteristico di quella definizione che è il paradosso di Richard. La definizione della proprietà di essere richardiano descrive chiaramente una proprietà numerica degli interi. L’espressione stessa, perciò, appartiene alla serie di definizioni suesposte. Ne segue che l’espressione è correlata a un intero indicante il suo posto nella serie. Supponiamo sia n tale numero. Ci domandiamo (ricordandoci dell’antinomia di Russell): n è richardiano? Il lettore può, senza dubbio anticipare la fatale contraddizione che ci minaccia. Infatti, n è richardiano se, e solo se, non possiede la proprietà definita dall’espressione con la quale n è correlato (cioè, se non ha la proprietà di essere richardiano). Brevemente, n è richardiano se, e solo se, n è non richardiano; cosicché la proposizione ‘n è richardiano’ è insieme vera e falsa.
Vogliamo ora sottolineare che la contraddizione, in un certo senso, è un inganno prodotto dal fatto che il giuoco non è stato condotto correttamente. Un’ipotesi, tacita ma essenziale, presente nell’ordinamento seriale delle definizioni è stata dimenticata lungo la dimostrazione, quando è risultato conveniente. Si era convenuto di considerare le definizioni delle proprietà puramente aritmetiche degli interi, proprietà che possono essere formulate con l’aiuto di nozioni quali l’addizione aritmetica, la moltiplicazione, ecc. Ma in seguito, senza che ce ne accorgessimo, siamo stati disposti ad accettare una definizione nella serie la quale fa riferimento alla notazione usata nella formulazione delle proprietà aritmetiche. Piú specificatamente, la definizione della proprietà di essere richardiano non appartiene alla serie, quale la si intendeva all’inizio, perché la definizione in esame implica nozioni metamatematiche quali il numero di lettere (o segni) contenute nelle espressioni. Possiamo evitare il paradosso di Richard distinguendo attentamente fra proposizioni nell’ambito dell’aritmetica (le quali non si riferiscono affatto a un qualsiasi sistema di notazione) e proposizioni intorno a qualche sistema di notazioni nel quale sia codificata l’aritmetica.
Il ragionamento fatto nella costruzione del paradosso di Richard è ovviamente fallace. La costruzione, ciononostante, suggerisce che forse è possibile “rappresentare” o “rispecchiare” affermazioni metamatematiche intorno a un sistema formale sufficientemente ampio, nel sistema stesso. L’idea della “rappresentazione” è ben nota e ha una parte fondamentale in molti rami della matematica. Essa viene usata, evidentemente, nella costruzione delle ordinarie proiezioni, nelle quali figure tracciate su una sfera sono proiettate su un piano, in modo che le relazioni tra le figure piane rispecchino le relazioni fra le figure sulla sfera. Viene pure usata nella geometria analitica, la quale traduce la geometria nell’algebra, cosicché le relazioni geometriche vengono rappresentate mediante relazioni algebriche. Il lettore ricorderà la discussione fatta nel capitolo 2, in cui si spiegava come Hilbert avesse usato l’algebra per dimostrare la compatibilità del suoi assiomi geometrici. Ciò che in realtà fece Hilbert fu di rappresentare la geometria con l’algebra. La rappresentazione ha una parte importante anche in fisica matematica dove, per esempio, certe relazioni fra le proprietà della corrente elettrica sono rappresentate nel linguaggio dell’idrodinamica. La rappresentazione è pure presente quando viene costruito un modello pilota prima di procedere alla costruzione della macchina reale, quando una piccola superficie alare viene osservata nelle sue proprietà aerodinamiche in una galleria a vento, o quando un apparecchio da laboratorio costituito da circuiti elettrici viene usato per studiare le relazioni fra grandi masse in movimento. Un esempio notevolmente significativo è mostrato nella [vedi Fig. 3], la quale illustra un tipo di rappresentazione che interviene in un ramo della matematica noto come geometria proiettiva.
La caratteristica fondamentale della rappresentazione è che una struttura astratta di relazioni valide in un dominio di “oggetti” si può dimostrare valida tra “oggetti” (normalmente di tipo diverso dal primo) di un altro dominio. Fu questa caratteristica che stimolò Gödel a costruire la sua prova. Se delle proposizioni metamatematiche riguardanti un sistema formalizzato dell’aritmetica potessero, come egli sperava, essere tradotte in (o rappresentate da) proposizioni aritmetiche all’interno del sistema stesso, si otterrebbe un vantaggio notevole nel facilitare le dimostrazioni metamatematiche. Infatti, proprio come è piú semplice trattare con formule algebriche rappresentanti (o rispecchianti) intricate relazioni geometriche [vedi Fig. 3]tra curve e superfici nello spazio, che non con le relazioni geometriche stesse, allo stesso modo è piú semplice trattare con le controparti aritmetiche (o “immagini speculari”) di complesse relazioni logiche, che non con le relazioni logiche stesse.
Lo sfruttamento della nozione di rappresentazione è la chiave dell’argomentazione del famoso articolo di Gödel. Seguendo lo stile del paradosso di Richard, ma evitando attentamente l’incongruenza implicita nella costruzione richardiana, Gödel mostrò che proposizioni metamatematiche intorno a un calcolo aritmetico formalizzato possono veramente rappresentarsi con formule aritmetiche del calcolo stesso. Come spiegheremo in dettaglio nel prossimo capitolo, egli escogitò un metodo di rappresentazione tale che né la formula aritmetica corrispondente a una certa proposizione metamatematica vera intorno alla formula stessa, né la formula aritmetica corrispondente alla negazione di tale proposizione, sono dimostrabili all’interno del calcolo. Dato che una di queste formule aritmetiche deve codificare una verità aritmetica e, d’altra parte, non è derivabile dagli assiomi, gli assiomi sono incompleti. Il metodo della rappresentazione permise a Gödel di costruire una formula aritmetica corrispondente alla proposizione metamatematica ‘il calcolo è coerente’ e di mostrare che questa formula non è dimostrabile all’interno del calcolo. Ne segue che tale proposizione metamatematica non può essere dimostrata a meno che non vengano usate delle regole di inferenza le quali non possono essere rappresentate nel calcolo: cosicché, nella dimostrazione della proposizione, devono essere impiegate delle regole la cui propria coerenza può essere messa in dubbio come la coerenza dell’aritmetica stessa. Gödel stabili queste fondamentali conclusioni usando una forma particolarmente ingegnosa di rappresentazione.

Note al capitolo 6

Nota 1.Questa è la stessa cosa che accadrebbe se la parola ‘corto’ apparisse in una lista di parole, e noi caratterizzassimo ciascuna parola, della lista con la proprietà descrittiva “corto” o “lungo”. La parola ‘corto’ sarebbe caratterizzata da “corto”.

Fig. 3 - illustra il teorema di Pappo

(a)

se A, B, C sono tre punti distinti qualsiasi di una linea retta I, ed A', B', C' tre punti qualsiasi di un'altra linea retta II, i tre punti R, S, T determinati dalle coppie di linee rette AB' e A'B, BC' e B'C, CA' e C'A, rispettivamente, sono collineari, cioè, giacciono sulla linea retta III.

(b)

illustra il “duale” del teorema (a): se A, B, C sono tre linee rette qualsiasi, distinte, appartenenti al punto I, e A', B', C' altre tre linee rette distinte, qualsiasi, appartenenti al punto Il, le tre linee rette R, S, T determinate dalle coppie di punti AB' e A'B, BC' e B'C, CA' e C'A, rispettivamente, sono “copuntuali”, cioè, appartengono al punto III.

Le due figure hanno la stessa struttura astratta, sebbene, in apparenza, esse siano sensibilmente diverse. La figura (a) è legata alla figura (b) in questa maniera: punti della prima corrispondono a linee rette della seconda, mentre linee della prima corrispondono a punti della seconda. Di fatto, (b) è una rappresentazione di (a): un punto di (b) rappresenta (o è 1’“immagine speculare” di) una linea di (a), mentre una linea di (b) rappresenta un punto di (a).

Ernst Nagel e James R. Newman
La prova di Gödel
7- Le prove di Gödel

Il lavoro di Gödel è difficile. È necessario assimilare bene quarantasei definizioni preliminari, insieme con molti teoremi preliminari assai importanti. Sceglieremo una via piú semplice che, tuttavia, dovrebbe egualmente permettere al lettore di gettare uno sguardo sull’argomentazione e sulla struttura finale.

La numerazione di Gödel
Gödel descrisse un calcolo formalizzato nel quale tutte le notazioni aritmetiche ordinarie possono essere espresse e nel quale è possibile stabilire le relazioni aritmetiche familiari [1]. Le formule del calcolo vengono costruite con una classe di segni elementari, che costituiscono il vocabolario fondamentale. Un insieme di formule primitive (o assiomi) ne sono il sostegno, e i teoremi del calcolo sono formule deducibili dagli assiomi con l’aiuto di un insieme di regole di trasformazione (o regole di inferenza) enumerato con cura. Per prima cosa, Gödel mostrò che è possibile assegnare un unico numero a ciascun segno elementare, a ciascuna formula (o sequenza di segni) e a ciascuna dimostrazione (o sequenza finita di formule). Questo numero, che serve da segno o etichetta distintiva, viene chiamato il “numero di Gödel” del segno, della formula, o della prova. Vi sono parecchie possibilità nell’assegnare il numero di Gödel, ed è irrilevante per la validità della dimostrazione quale di esse venga scelta. Daremo un esempio concreto di come possano venir assegnati questi numeri, per aiutare il lettore a seguire la discussione. Il metodo di numerazione usato da noi è quello impiegato da Gödel nel suo articolo del 1931.
I segni elementari appartenenti al vocabolario fondamentale sono di due tipi: i segni costanti e le variabili. Supporremo che vi siano esattamente dieci segni costanti [2], ai quali vengono attribuiti i numeri interi da 1 a 10, come numeri di Gödel. La maggior parte di tali segni sono già noti al lettore: ‘~’ (abbreviazione di ‘non’); ‘Ú’ (abbreviazione di ‘oppure’); ‘É’ (abbreviazione di ‘se ... allora...’; ‘=’ (abbreviazione di ‘eguale a’); ‘0’ (il numerale per il numero zero); e tre segni d’interpunzione, cioè la parentesi sinistra ‘(’, quella destra ‘)’ e la virgola ‘,’. Inoltre, saranno usati altri due segni: il segno ‘$’, che si può leggere come ‘vi è’ e che interviene nei “quantificatori esistenziali”; e la lettera minuscola ‘s’ che viene posta accanto a un’espressione numerica per designare l’immediato successore di un numero. Per esempio: la formula ‘((x)(x = s0)’ può leggersi ‘vi è un x tale che x è l’immediato successore di 0’. La tabella 4 mostra i dieci segni costanti, il numero di Gödel associato a ognuno di essi, e indica il significato usuale dei segni.
Oltre ai segni elementari costanti, compaiono tre tipi di variabili nel vocabolario fondamentale del calcolo: le variabili numeriche ‘x’, ‘y’, ‘z’, ecc., nelle quali possono essere sostituiti numerali ed espressioni numeriche; le variabili proposizionali ‘p’, ‘q’, ‘r’, ecc., nelle quali possono essere sostituite delle formule (proposizioni); e le variabili predicative ‘P’, ‘Q’, ‘R’, ecc., nelle quali possono essere sostituiti dei predicati, quali ‘primo’ o ‘maggiore di’. A queste variabili vengono assegnati dei numeri di Gödel secondo le seguenti regole:

1) a ogni variabile numerica assegniamo un numero primo diverso, maggiore di 10;

2) a ogni variabile proposizionale assegniamo il quadrato di un numero primo maggiore di 10;

3) a ogni variabile predicativa assegniamo il cubo di un numero primo maggiore di 10.
La tabella 5 illustra l’uso di queste regole, specificando i numeri di Gödel per alcune variabili.
Consideriamo, ora, una formula del sistema, per esempio ‘(($x)(x= sy)’. (Letteralmente tradotta, essa suona cosí: ‘vi è un x tale che x è il successore immediato di y’, e asserisce, in effetti, che ogni numero possiede un successore immediato.) I numeri associati ai suoi dieci costituenti elementari sono, rispettivamente, 8, 4, 11, 9, 8, 11, 5, 7, 13, 9. Lo indichiamo schematicamente in questa maniera:

(	$	x	)	(	x	=	s	y	)
¯	¯	¯	¯	¯	¯	¯	¯	¯	¯
8	4	11	9	8	11	5	7	13	9

È desiderabile, però, assegnare un singolo numero alla formula anziché un insieme di numeri ai suoi costituenti. Ciò si può fare facilmente. Conveniamo di associare alla formula il numero unico dato dal prodotto dei primi dieci numeri primi in ordine di grandezza, ciascun primo essendo elevato a una potenza eguale al numero di Gödel del corrispondente segno elementare. La formula suddetta viene dunque associata al numero 2⁸×3⁴×5¹¹×7⁹×11⁸×13¹¹×17⁵×19⁷×23¹³×29⁹; chiamiamo questo numero m. In maniera simile un numero unico, e cioè il prodotto di tanti fattori primi quanti sono i segni della formula (ciascuno elevato a una potenza eguale al numero di Gödel del segno corrispondente), può essere assegnato a ciascuna sequenza finita di segni elementari e, in particolare, a ogni formula.

Nel calcolo possono intervenire segni che non compaiono nel vocabolario fondamentale; essi vengono introdotti definendoli con l’aiuto dei segni del vocabolario. Per esempio, il segno ‘.’, il connettivo proposizionale usato come abbreviazione di ‘e’, può essere definito nel contesto come segue: ‘p.q’ sta per ‘~(~p Ú ~q)’. Quale numero di Gödel viene assegnato a un segno cosí definito? La risposta è ovvia se notiamo che espressioni contenenti segni definiti possono essere eliminati mediante i loro equivalenti che le definiscono; ed è chiaro che un numero di Gödel può essere determinato per le espressioni trasformate. Secondo ciò, il numero di Gödel della formula ‘p.q’ è il numero di Gödel della formula ‘~(~p Ú ~q)’. Similmente, i vari numerali possono essere introdotti con le definizioni seguenti: ‘1’ sta per ‘s0’, ‘2’ sta per ‘ss0’, ‘3’ sta per ‘sss0’, e cosí via. Per ottenere il numero di Gödel della formula ‘~ (2 = 3)’, noi eliminiamo i segni non elementari, ottenendo la formula ‘~ (ss0 = sss0)’, e determiniamo il numero di Gödel secondo le regole citate piú sopra.

Consideriamo, infine, una sequenza di formule, quale può intervenire in una dimostrazione; per esempio, la sequenza

($x) (x = sy)

($x)(x = s0).

La seconda formula, una volta tradotta, suona così: ‘0 ha un successore immediato’; essa è deducibile dalla prima sostituendo il numerale ‘0’ al posto della variabile numerica ‘y’[3]. Abbiamo già determinato il numero di Gödel della prima formula: è m; supponiamo che n sia il numero di Gödel della seconda formula. Come prima, è conveniente avere un singolo numero che caratterizzi la sequenza. Conveniamo, perciò, di associare ad essa il prodotto dei primi due numeri primi in ordine di grandezza (cioè 2 e 3), ciascuno elevato a una potenza eguale al numero di Gödel della formula corrispondente della sequenza. Se indichiamo questo numero con k, scriveremo 2^m´3ⁿ. Applicando questa procedura compatta, possiamo ottenere un numero per ogni sequenza di formule. In sostanza, ogni espressione del sistema, sia che si tratti di un segno elementare, di una sequenza di segni, o di una sequenza di sequenze, può ricevere un numero di Gödel.
Ciò che abbiamo fatto finora, è stato di stabilire un metodo per “aritmetizzare” completamente il calcolo formale. Il metodo consiste, essenzialmente, in un insieme di indicazioni per fissare una corrispondenza biunivoca tra le espressioni del calcolo e certi sottoinsiemi dei numeri interi.

Non ogni numero intero è un numero di Gödel. Consideriamo, per esempio, il numero 100. Tale numero è maggiore di 10, e perciò non può essere il numero di Gödel di un segno elementare costante; e, poiché non è neppure un numero primo maggiore di 10, né il quadrato o il cubo di un tale numero primo, non può essere il numero di Gödel di una variabile. Scomponendo 100 in fattori primi, troviamo che esso è uguale a 2² ´ 5²; e il numero primo 3 non compare come fattore della decomposizione, ma viene saltato. Secondo le regole enunciate, però, il numero di Gödel di una formula (o di una sequenza di formule) deve essere il prodotto di successivi numeri primi, ciascuno elevato a una certa potenza. Il numero 100 non soddisfa a questa definizione. In breve, 100 non può essere il numero di Gödel assegnato a un segno costante, a una variabile, a una formula. Quindi non è un numero di Gödel.

Una volta data un’espressione, si può calcolare il numero di Gödel che gli corrisponde, in maniera univoca. Ma questa è solo la prima metà della faccenda. Una volta dato un numero, possiamo determinare se è un numero di Gödel, e, se lo è, si può analizzare esattamente o “ritrovare” l’espressione che esso rappresenta. Se un certo numero è minore o eguale a 10, esso è il numero di Gödel di un segno costante elementare. Il segno può venir così identificato. Se il numero è maggiore di 10, esso può venire scomposto in fattori primi in modo unico (come sappiamo da un noto teorema dell’aritmetica)[4]. Se si tratta di un numero primo maggiore di 10, o la seconda o terza potenza di un tale numero primo, si tratta del numero di Gödel di una variabile identificabile. Se si tratta del prodotto di numeri primi successivi, ciascuno elevato a una certa potenza, può essere il numero di Gödel di una formula o di una sequenza di formule. In tal caso, l’espressione al quale corrisponde può, di nuovo, essere determinata. Seguendo questo programma, possiamo scomporre ciascun numero in pezzi, come se fosse una macchina, scoprire come è costruito e quali parti lo compongono; e, poiché ciascuno dei suoi elementi corrisponde a un elemento dell’espressione che rappresenta, possiamo ricostituire l’espressione, analizzare la sua struttura e le sue caratteristiche. La tabella 6 illustra come, dato un numero, possiamo stabilire se esso è un numero di Gödel e, se lo è, quale espressione esso rappresenti.

L’aritmetizzazione della metamatematica
Il passo successivo di Gödel è un’applicazione ingegnosa della rappresentazione. Egli dimostrò che tutte le proposizioni metamatematiche intorno alle proprietà strutturali delle espressioni del calcolo possono essere convenientemente rappresentate nel calcolo stesso. L’idea fondamentale che sta alla base del suo procedimento è la seguente: dato che ogni espressione del calcolo è associata a un numero (di Gödel), una proposizione metamatematica intorno alle espressioni e alle loro reciproche relazioni può essere costruita come una proposizione intorno al numeri (di Gödel) corrispondenti e alle loro reciproche relazioni aritmetiche. In tale maniera, la metamatematica diventa completamente “aritmetizzata”. Facciamo un paragone banale: i clienti di un supermercato affollato vengono spesso dotati, all’entrata, di uno scontrino sul quale è stampato un numero che determina l’ordine in cui i clienti devono essere serviti al banco. Osservando i numeri, è facile dire quante persone sono state servite, quante stanno attendendo il loro turno, a quante persone una data persona è avanti, e cosí via. Se, per esempio, il signor Smith ha il numero 37, e il signor Brown il numero 53, invece di spiegare al signor Brown che ha da aspettare il suo turno dopo il signor Smith, basta dire che 37 è minore di 53.
La situazione della metamatematica è simile a quella di un supermercato. Ciascuna proposizione metamatematica è rappresentata da una data formula aritmetica; e le relazioni di dipendenza logica fra le proposizioni metamatematiche sono perfettamente riflesse nelle relazioni numeriche di dipendenza fra le corrispondenti formule aritmetiche. Ancora una volta la rappresentazione facilita una ricerca di struttura. L’esplorazione dei problemi metamatematici può venir condotta studiando le proprietà e le relazioni di certi numeri interi.
Illustriamo queste osservazioni generali con un esempio elementare. Consideriamo il primo assioma del calcolo proposizionale, che e pure un assioma del sistema formale che stiamo analizzando: ‘(p Ú p) É p’. Il suo numero di Gödel è 2⁸´3¹¹´5²´7¹¹´11⁹´13³´17¹¹, che noi designeremo con la lettera ‘a’. Consideriamo anche la formula: ‘(p Ú p)’ il cui numero di Gödel è 2⁸´3¹¹´5²´7¹¹´11⁹; designeremo tale numero con la lettera ‘b’. Noi ora enunciamo la proposizione metamatematica secondo la quale la formula ‘(p Ú p)’ è la parte iniziale dell’assioma. A quale formula aritmetica del sistema formale corrisponde questa affermazione? È evidente che la formula piú piccola ‘(p Ú p)’ può essere la parte iniziale di una formula piú grande che è l’assioma se, e solo se, il numero di Gödel b, che rappresenta la prima, e un fattore del numero di Gödel a, che rappresenta la seconda. Supponendo che l’espressione ‘fattore di’ sia opportunamente definita nel sistema aritmetico formalizzato, la formula aritmetica che corrisponde univocamente alla proposizione metamatematica di cui sopra è: ‘b è un fattore di a’. Inoltre, se questa formula è vera, cioè se b è un fattore di a, allora è vero che ‘(p Ú p)’ è la parte iniziale di ‘(p Ú p) É p’.
Fissiamo la nostra attenzione sulla proposizione metamatematica: ‘la sequenza di formule con numero di Gödel x è una dimostrazione della formula con numero di Gödel z’. Questa proposizione è rappresentata (specchiata) da una formula ben definita del calcolo aritmetico, la quale esprime una relazione puramente aritmetica fra x e z. Possiamo, incidentalmente, avere un’idea della complessità di questa relazione, ricordando l’esempio fatto, in cui il numero di Gödel k=2^m´3ⁿ era assegnato alla dimostrazione (frammento di a) la cui conclusione possedeva il numero di Gödel n. Un poco di riflessione mostra che vi è qui una relazione aritmetica ben definita, per quanto non affatto semplice, fra il numero k, il numero di Gödel della dimostrazione, ed n, il numero di Gödel della conclusione. Comunque, noi scriveremo questa relazione fra x e z con la formula ‘Dim(x,z)’, per ricordarci della proposizione metamatematica a cui corrisponde (cioè, della proposizione metamatematica ‘la sequenza di formule con numero di Gödel x è una dimostrazione della formula con numero di Gödel z)[5]. Chiediamo, ora, al lettore di osservare che una proposizione metamatematica che afferma che una certa sequenza di formule è una dimostrazione di una certa formula, è vera se, e solo se, il numero di Gödel della dimostrazione citata sta, rispetto al numero di Gödel della conclusione, nella relazione aritmetica designata da ‘Dim’. In base a ciò, per stabilire la verità o la falsità della proposizione metamatematica in discussione, dobbiamo preoccuparci soltanto del fatto se la relazione Dim vale fra due numeri. Inversamente, possiamo stabilire che la relazione aritmetica vale per una coppia di numeri, mostrando che la proposizione metamatematica rappresentata da tale relazione tra numeri è vera. Similmente, la proposizione metamatematica ‘la sequenza di formule con il numero di Gödel x non è una dimostrazione della formula con il numero di Gödel z’ è rappresentata da una formula ben definita nel sistema aritmetico formalizzato. Tale formula è la negazione formale di ‘Dim(x,z)’, cioè ‘~Dim (x, z)’.
È ancora necessaria una semplice notazione speciale per presentare il punto cruciale del ragionamento di Gödel. Incominciamo con un esempio. La formula ‘($x)(x = sy)’ ha m per numero di Gödel (si veda a pagina 7 8), mentre la variabile ‘y’ ha come numero di Gödel 13. Sostituiamo, in questa formula, al posto della variabile con numero di Gödel 13 (cioè al posto di ‘y’) il numerale corrispondente a m. Come risultato abbiamo la formula ‘($x) (x = sm)’, la quale asserisce letteralmente che esiste un numero x tale che x è il successore immediato di m. Anche quest’ultima formula possiede un numero di Gödel, che può calcolarsi molto facilmente. Invece di calcolarlo, possiamo identificare il numero mediante una caratterizzazione metamatematica univoca: esso è il numero di Gödel della formula che si ottiene dalla formula con numero di Gödel m, sostituendo alla variabile con numero di Gödel 13, il numerale corrispondente a m. Questa caratterizzazione metamatematica determina in modo unico un certo numero che è una certa funzione aritmetica dei numeri m e 13, dove la funzione stessa può essere espressa nel sistema formalizzato.

Questa funzione è molto complessa, come possiamo vedere se cerchiamo di formularla in maggior dettaglio. Tentiamo una tale formulazione, senza condurla alla fine. È stato mostrato a pagina 78 che m, il numero di Gödel di ‘((x) (x = sy)’, vale

2⁸×3⁴×5¹¹×7⁹×11⁸×13¹¹×17⁵×19⁷×23¹³×29⁹. Per trovare il numero di Gödel di ‘($x)(x = sm’ (la formula ottenuta dalla precedente sostituendo alla variabile ‘y’ il numerale corrispondente a ‘m’), procediamo come segue. Questa formula contiene il numerale ‘m’, il quale è un segno non elementare; d’accordo con quanto detto a pagina 78, m deve essere sostituito dalla sua definizione equivalente. Quando si sia fatto questo, si ottiene la formula ($x) (x = ssss ... s0),dove la lettera ‘s’ compare m+ 1 volte. Questa formula contiene solo i segni elementari appartenenti al vocabolario fondamentale,. cosicché è possibile calcolare il suo numero di Gödel. Per fare ciò, otteniamo dapprima le serie dei numeri di Gödel associati ai segni elementari della formula: 8, 4, 11, 9, 8, 11, 5, 7, 7, 7, ...., 7, 6, 9, in cui il numero 7 compare m+ 1 volte. Prendiamo quindi il prodotto dei primi m+ 10 numeri primi in ordine di grandezza, ciascun primo essendo elevato a una potenza eguale al numero di Gödel del corrispondente segno elementare. Chiamiamo tale numero r, cosicché r=2⁸×3⁴×5¹¹×7⁹×11⁸×13¹¹×17⁵×19⁷×23⁷×29⁷×31⁷×...×p⁹_m+10 dove p_m+10 è 1’(m+10)-esimo primo in ordine di grandezza.
Paragoniamo ora i due numeri di Gödel m ed r. Il primo, cioè m, contiene un fattore primo elevato alla potenza 13; il secondo, cioè r, contiene tutti i fattori primi di m e molti altri ancora, ma nessuno di essi è elevato alla potenza 13. Il numero r può dunque ottenersi dal numero m, sostituendo il fattore primo in m che è elevato alla potenza 13 con altri numeri primi elevati a qualche potenza diversa da 13. Per poter dire con esattezza in pieno dettaglio come r è legato a m, non si può fare a meno di introdurre una grande quantità di apparato notazionale in piú, come è fatto nel lavoro originale di Gödel. Ma abbiamo già detto a sufficienza per indicare che il numero r è una funzione aritmetica definita di m e di 13.

Il numero cercato può perciò essere designato nell’ambito del calcolo. Tale designazione verrà scritta nella forma ‘sost (m, 13, m)’, lo scopo di tale forma essendo quello di ricordare la caratterizzazione metamatematica che essa rappresenta, cioè ‘il numero di Gödel della formula ottenuta dalla formula con numero di Gödel m, sostituendo la variabile con numero di Gödel 13 con il numerale corrispondente a m’. Possiamo ora lasciare da parte l’esempio e generalizzare. Il lettore vedrà facilmente che l’espressione ‘sost(y, 13, y)’ è l’immagine speculare, nell’ambito del calcolo aritmetico formalizzato, della caratterizzazione metamatematica: ‘il numero di Gödel della formula ottenuta dalla formula con numero di Gödel y, sostituendo alla variabile con numero di Gödel 13 il numerale corrispondente a y’. Egli noterà pure che, quando un numerale definito viene sostituito a ‘y’ in ‘sost(y, 13, y)’ - per esempio, il numerale corrispondente a m o quello corrispondente e duecentoquarantatré milioni - l’espressione risultante designa un intero ben definito, che è il numero di Gödel di una certa formula.

A questo punto molte obiezioni possono essere sollevate dal lettore, le quali richiedono una risposta. Ci si può domandare perché, nella caratterizzazione metamatematica ora menzionata, noi diciamo che è il “numerale corrispondente a y ” che deve essere sostituito al posto di una certa variabile, invece del “numero y”. La risposta dipende dalla distinzione, già discussa, tra la matematica e la metamatematica, e richiede una breve spiegazione della differenza fra numeri e numerali. Un numerale è un segno, un’espressione linguistica, qualche cosa che si può scrivere, cancellare, copiare, e cosí via. Un numero, invece, è un qualche cosa cui un numerale dà un nome o una designazione, e che non può essere, letteralmente, scritto, cancellato, copiato, ecc. Cosí, noi diciamo che 10 è il numero delle nostre dita e, nel fare questa affermazione, attribuiamo una certa “proprietà” alla classe delle nostre dita; ma sarebbe, evidentemente, assurdo dire che questa proprietà è un numerale. Ancora, il numero 10 ha tale nome dal numerale arabico ‘10’, e dalla lettera latina ‘X’; questi nomi sono differenti, sebbene indichino lo stesso numero. Brevemente, quando sostituiamo una variabile numerica (che è una lettera o segno), noi mettiamo un segno al posto di un altro segno. Non possiamo sostituire letteralmente un numero a un segno, perché un numero è una proprietà delle classi (e viene talvolta identificato con un concetto), non qualche cosa che si può mettere sulla carta. Ne segue che, sostituendo una variabile numerica, possiamo sostituirvi solo un numerale (o qualche altra espressione numerica, quale ‘s0’ o ‘7 + 5’), e non un numero. Questo spiega perché, nella caratterizzazione metamatematica suddetta, noi affermiamo che sostituiamo alla variabile il numerale corrispondente a (il numero) y, invece che il numero y stesso.
Il lettore può poi domandarsi quale numero sia designato da ‘sost(y, 13, y)’ se la formula il cui numero di Gödel è y non contiene la variabile con numero di Gödel 13, vale a dire se la formula non contiene la variabile ‘y’. Così, sost (243 000 000, 13, 243 000 000) è il numero di Gödel della formula ottenuta dalla formula con numero di Gödel 243 000 000 sostituendo alla variabile ‘y’ il numerale ‘243 000 000’. Ma se il lettore consulta la tabella 6, egli troverà che 243 000 000 è il numero di Gödel della formula ‘0 = 0’, che non contiene la variabile ‘y’. Qual è, allora, la formula ottenuta da ‘0 = 0’ sostituendo alla variabile ‘y’ il numerale corrispondente al numero 243 000 000? La risposta piú semplice è che, dato che ‘0 = 0’ non contiene questa variabile, non è possibile fare alcuna sostituzione, o, ciò che è lo stesso, che la formula ottenuta da ‘0= 0’ è proprio la stessa formula. Quindi, il numero designato da ‘sost (243 000 000, 13, 243 000 000)’ è 243 000 000.
Il lettore può anche domandarsi se ‘sost(y, 13, y)’ è una formula nell’ambito del sistema aritmetico nel senso in cui, per esempio, ‘($x)(x=sy)’, ‘0=0’ sono formule. La risposta è no, per la seguente ragione. L’espressione ‘0 = 0’ è chiamata una formula, perché asserisce una relazione fra due numeri e può quindi avere il significativo attributo di vero o falso. Similmente, quando numerali definiti vengono sostituiti alle variabili in ‘Dim (x, z)’, questa espressione formula una relazione fra due numeri, e diviene cosí una proposizione che è vera o falsa. Lo stesso vale per ‘($x)(x=sy)’. D’altra parte, anche quando al posto di ‘y’ viene sostituito un numerale definito, in ‘sost(y, 13, y)’, l’espressione risultante non afferma nulla e perciò non può essere né vera né falsa: semplicemente designa o dà un nome a un numero, descrivendolo come una certa funzione di altri numeri. La differenza fra una formula (che in effetti è una proposizione intorno a dei numeri, e quindi è vera o falsa) e una funzione-nome (che in effetti è un nome che identifica un numero, e quindi non è né vera né falsa) può essere chiarita da alcuni altri esempi. ‘5 = 3’ è una formula che, seppur falsa, dichiara che i due numeri 5 e 3 sono eguali; ‘5² = 4²+ 3²’ è anch’essa una formula che afferma che sussiste una certa relazione fra i tre numeri, 5, 4 e 3; e, in generale, ‘y = f (x)’ è una formula che afferma che vale una certa relazione fra i numeri non specificati x e y. Invece, ‘2 + 3’ esprime una funzione dei due numeri 2 e 3, e cosí dà un nome a un certo numero (cioè il numero 5); essa non è una formula, perché sarebbe privo di senso domandare se ‘2 + 3’ è vero o falso. ‘(7 × 5) + 8’ esprime un’altra funzione dei tre numeri 5, 7 e 8, e designa il numero 43. Piú generalmente, ‘f(x)’ esprime una funzione di x e identifica un certo numero ogni volta che al posto di ‘x’ viene sostituito un numerale definito, e ogni volta che alla funzione ‘f’ viene assegnato un significato definito. In breve, mentre ‘Dim(x,z)’ è una formula perché ha la forma di una proposizione concernente dei numeri, ‘sost (y, 13, y)’ non è una formula perché ha solo la forma di un nome per certi numeri.

Il nocciolo della dimostrazione di Gödel
Siamo finalmente in grado di affrontare, a grandi linee, la parte piú importante del ragionamento di Gödel. Incominceremo con l’enunciazione delle tappe principali in maniera generale, in modo che il lettore possa abbracciare a colpo d’occhio la sequenza dei ragionamenti.

1) Gödel mostrò in che modo sia possibile costruire una formula aritmetica G che rappresenti la proposizione metamatematica: ‘la formula G non è dimostrabile’. Questa formula, allora, evidentemente afferma la sua non dimostrabilità. In un certo senso, G viene costruita analogamente al paradosso di Richard. In tale paradosso, l’espressione ‘richardiano’ è associata a un certo numero n, e la proposizione ‘n è richardiano’ viene costruita. Nel ragionamento di Gödel, anche la formula G è associata a un certo numero b, ed è cosí costruita che corrisponde alla proposizione: ‘la formula con il numero b associato ad essa non è dimostrabile’.

2) Gödel, d’altra parte, dimostrò anche che G è dimostrabile se, e solo se, la sua negazione formale ~ G è dimostrabile. Questo aspetto della dimostrazione è di nuovo analogo al corrispondente aspetto del paradosso di Richard, in cui si dimostra che n è richardiano se, e solo se, n non è richardiano. Allora, se una formula e la sua negazione formale sono entrambe formalmente dimostrabili, il calcolo aritmetico è contraddittorio. In base a ciò, se il calcolo è autocompatibile, né G né la sua negazione formale ~ G sono formalmente deducibili dagli assiomi dell’aritmetica.

3) Gödel, quindi, dimostrò che, sebbene G non sia formalmente dimostrabile, tuttavia è una formula aritmetica vera. È vera nel senso che afferma che ogni intero possiede una certa proprietà aritmetica, che può essere esattamente definita ed è posseduta da qualsiasi intero assegnato.

4) Dato che G è vera e insieme formalmente indecidibile, gli assiomi dell’aritmetica non sono completi. In altre parole, non possiamo dedurre tutte le verità aritmetiche dagli assiomi. Inoltre, Gödel dimostrò che l’aritmetica è essenzialmente incompleta: anche se si supponessero altri assiomi aggiuntivi, tali da permettere la formale deduzione della formula vera G dall’insieme piú ampio, si potrebbe costruire un’altra formula vera ma formalmente indecidibile.

5) Gödel, infine, descrisse la maniera in cui costruire una formula aritmetica A che rappresenti la proposizione metamatematica: ‘l’aritmetica è autocompatibile’; e dimostrò che la formula ‘A É G’ è formalmente dimostrabile. Finalmente, egli mostrò che la formula A non è dimostrabile. Ne segue che l’autocompatibilità dell’aritmetica non può essere stabilita con argomenti rappresentabili nel calcolo aritmetico formale. Esaminiamo ora, in maggior dettaglio, i singoli elementi di questa sequenza.

La formula ‘~ Dim (x, z)’ è stata già identificata. Essa rappresenta, nell’ambito dell’aritmetica formalizzata, la proposizione metamatematica: ‘la sequenza di formule con numero di Gödel x non è una dimostrazione della formula con numero di Gödel z’. Il prefisso ‘(x)’venga ora introdotto nella formula Dim. Questo prefisso ha la stessa funzione, nel sistema formalizzato, della frase ‘per ogni x’. Aggiungendo tale prefisso, otteniamo una nuova formula: ‘(x) ~ Dim(x,z)’, che rappresenta, nell’ambito dell’aritmetica, la proposizione metamatematica: ‘per ogni x, la sequenza di formule con numero di Gödel x non è una dimostrazione della formula con numero di Gödel z’. La nuova formula è perciò la perifrasi formale (strettamente parlando, è l’unica rappresentazione), nel calcolo, della proposizione metamatematica: ‘la formula con numero di Gödel z non è dimostrabile’, o, in altre parole, ‘non si può dare alcuna prova della formula con numero di Gödel z’.
Ciò che Gödel mostrò è che un certo caso particolare di questa formula non è formalmente dimostrabile. Per costruire questo caso particolare, partiamo dalla formula

(1)	(x) ~ Dim [x, sost (y, 13, y)

Questa formula appartiene al calcolo aritmetico, ma rappresenta una proposizione metamatematica. Quale? Il lettore si ricordi innanzitutto che l’espressione ‘sost(y, 13, y)’ designa un numero. Questo numero è il numero di Gödel della formula ottenuta dalla formula con numero di Gödel y, sostituendo alla variabile con numero di Gödel 13 il numerale corrispondente a y. È allora evidente che la formula (1) rappresenta la proposizione metamatematica: ‘la formula con numero di Gödel sost (y, 13, y) non è dimostrabile’. Questa proposizione può essere sviluppata completamente nella seguente maniera: ‘la formula [il cui numero di Gödel è il numero della formula] ottenuta dalla formula con numero di Gödel y, sostituendo alla variabile con numero di Gödel 13 il numerale corrispondente a y, non è dimostrabile’.

È della massima importanza comprendere che ‘sost(y, 13, y)’, sebbene costituisca un’espressione nell’aritmetica formalizzata, non è una formula ma piuttosto una funzione-nome per identificare un numero (si ricordi quanto è stato detto a pagina 77). Il numero cosí identificato, però, è il numero di Gödel di una formula, e precisamente della formula ottenuta dalla formula con numero di Gödel y, sostituendo alla variabile ‘y’ il numerale corrispondente a y.
Ancora un’osservazione. Il lettore può essere imbarazzato dal fatto che, nella proposizione metamatematica ‘la formula con numero di Gödel sost(y, 13, y) non è dimostrabile’, l’espressione ‘sost(y, 13, y)’ non appare fra virgolette, sebbene sia stato piú volte da noi ripetuto che ‘sost(y, 13, y)’ è un’espressione. Questo punto è imperniato ancora una volta sulla distinzione fra l’uso di un’espressione per parlare intorno a ciò che l’espressione designa (nel qual caso l’espressione non viene posta fra virgolette) e il discorso sull’espressione stessa (nel qual caso dobbiamo usare un nome per l’espressione e, in conformità alle convenzioni per costruire tali nomi, dobbiamo porre l’espressione fra virgolette). Un esempio aiuterà a comprendere la cosa. ‘7 + 5’ è un’espressione che designa un numero; 7+5, invece, è un numero e non un’espressione. Similmente, ‘sost(243000000, 13, 243000000)’ è un’espressione che designa il numero di Gödel di una formula (si veda la tabella 6); ma sost (243 000 000, 13, 243 000 000) è il numero di Gödel di una formula, e non un’espressione.

La formula (1), dato che appartiene al calcolo aritmetico, possiede un numero di Gödel che può essere esattamente determinato. Supponiamo che il numero sia n. Sostituiamo ora alla variabile con numero di Gödel 13 (cioè alla variabile ‘y’) nella formula (1), il numerale corrispondente a n. Si ottiene cosí una nuova formula, che chiameremo ‘G’ (da Gödel) e che si scriverà

(G)	(x) ~ Dim [x, sost (n, 13, n)].

La formula G è quel caso particolare che ci eravamo ripromessi di costruire.
Ora, questa formula si trova nel calcolo aritmetico, e perciò deve possedere un numero di Gödel. Quale? Un poco di riflessione mostra che è sost(n, 13, n). Per afferrare ciò, dobbiamo ricordare che sost(n, 13, n) è il numero di Gödel della formula ottenuta dalla formula con numero di Gödel n sostituendo alla variabile con numero di Gödel 13 (cioè alla variabile ‘y’) il numerale corrispondente a n. Ma la formula G è stata ottenuta dalla formula con numero di Gödel n, cioè dalla formula (1), sostituendo alla variabile ‘y’, che in essa compare, con il numerale corrispondente a n. Quindi il numero di Gödel di G è proprio sost (n, 13, n).
Ma dobbiamo ricordare che la formula G è la rappresentazione, nell’ambito del calcolo aritmetico, della proposizione metamatematica: ‘la formula con numero di Gödel sost (n, 13, n) non è dimostrabile’. Ne segue che la formula aritmetica ‘(x)~Dim[x, sost(n, 13, n)]’, rappresenta nel calcolo la proposizione metamatematica: ‘la formula ‘(x)~ Dim [x, sost(n, 13, n)]’ non è dimostrabile’. In un certo senso, quindi, la formula aritmetica G può essere costruita in quanto afferma di se stessa che non è dimostrabile.

Passiamo ora al secondo punto: la dimostrazione che G non è formalmente dimostrabile. Il ragionamento di Gödel assomiglia allo sviluppo del paradosso di Richard, ma non cade nelle incongruenze che abbiamo riscontrato a proposito di quest’ultimo.

Può essere utile rendere esplicita questa somiglianza come pure la differenza del ragionamento di Gödel da quello usato nel paradosso di Richard. Il punto principale è osservare che la formula G non è identica alla proposizione metamatematica cui è associata, ma la rappresenta (o rispecchia) nel calcolo aritmetico. Nel paradosso di Richard (come è stato spiegato a pagina 69) il numero n è il numero associato a una certa espressione metamatematica. Nella costruzione di Gödel, il numero n è associato a una certa formula aritmetica appartenente al calcolo formale, sebbene questa formula aritmetica di fatto rappresenti una proposizione metamatematica. (La formula rappresenta questa proposizione, perché la metamatematica dell’aritmetica è stata proiettata sull’aritmetica stessa). Nello sviluppo del paradosso di Richard, ci si domanda se il numero n possegga la proprietà metamatematica di essere richardiano. Nella costruzione di Gödel, invece, ci si domanda se il numero sost (n, 13, n) possegga una certa proprietà aritmetica, cioè la proprietà aritmetica espressa dalla formula ‘(x)~Dim(x,z)’. Non vi è quindi alcuna confusione nella costruzione di Gödel fra proposizioni nell’ambito dell’aritmetica e proposizioni intorno all’aritmetica, come accade nel paradosso di Richard.

L’argomentazione è relativamente poco complicata. Si incomincia mostrando che se la formula G fosse dimostrabile, allora la sua negazione formale (cioè la formula ‘~(x) ~ Dim [ x, sost(n, 13,n)]’) sarebbe anch’essa dimostrabile; e, inversamente, che se la negazione formale di G fosse dimostrabile, allora G stessa sarebbe dimostrabile. Abbiamo cosí: G è dimostrabile se, e solo se, ~ G è dimostrabile. Ma, come abbiamo già notato, se una formula e la sua negazione formale sono entrambe deducibili da un insieme di assiomi, allora gli assiomi stessi sono contraddittori. Quindi, se gli assiomi del sistema formalizzato sono fra loro compatibili, né la formula G né la sua negazione formale sono dimostrabili. In breve, se gli assiomi sono fra loro compatibili, G è formalmente indecidibile, nel preciso senso tecnico che né G né la sua negazione possono essere dedotte formalmente dagli assiomi.

In realtà Gödel non dimostrò questo; e noi riportiamo, per semplicità di esposizione, un adattamento del teorema ottenuto da J. Barkley Rosser nel 1936. Ciò che Gödel dimostrò è che se G è dimostrabile, allora ~ G è dimostrabile (cosí che l’aritmetica è incoerente); e se ~ G è dimostrabile, allora l’aritmetica è w-contraddittoria. Che cosa significa w-contraddittorietà? Sia ‘P’ un predicato aritmetico. Allora, l’aritmetica sarebbe w-contraddittoria se fosse possibile dimostrare contemporaneamente la formula ‘($x)P(x)’ (cioè ‘vi è almeno un numero che ha la proprietà P)’ e ciascuna delle formule dell’insieme infinito ‘~P(0)’, ‘~P(1)’, ‘~P(2)’, ecc. (cioè ‘0 non ha la proprietà P’, 1 non ha la proprietà P’, ‘2 non ha la proprietà P’, e cosí via). Un poco di riflessione mostra che se un calcolo è contraddittorio, allora è anche (-contraddittorio; ma l’inverso non è necessariamente vero: un sistema può essere w-contraddittorio senza essere contraddittorio. Perché un sistema sia contraddittorio devono essere dimostrate sia ‘($x)P(x)’ che ‘(x) ~ P(x)’. Però, per quanto, se un sistema è w-contraddittorio, ‘($x)P(x)’ e ciascuna delle infinite formule ‘ ~ P(0)’, , ~ P(1)’, ‘ ~ P(2)’, ecc. siano dimostrabili, la formula ‘(x) ~ P(x)’ potrebbe non essere dimostrabile; per cui il sistema non sarebbe contraddittorio.
Accenniamo appena alla prima parte della dimostrazione di Gödel, secondo la quale se G è dimostrabile allora ~ G è dimostrabile. Supponiamo che la formula G sia dimostrabile. Deve esistere, in conseguenza, una sequenza di formule nell’ambito dell’aritmetica che costituisce la dimostrazione di G. Sia k il numero di Gödel di tale dimostrazione. Allora, la relazione aritmetica designata da ‘Dim(x,z)’ deve sussistere fra k, il numero di Gödel della dimostrazione, e sost(n, 13, n), il numero di Gödel di G, il che equivale a dire che ‘Dim[k, sost(n, 13, n)]’ deve essere una formula aritmetica vera. Ma si può dimostrare che questa relazione aritmetica è di un genere tale che, se essa sussiste fra una coppia definita di numeri, la formula che esprime questo fatto è dimostrabile. Conseguentemente, la formula ‘Dim[k, sost(n, 13, n)]’ è non solo vera, ma anche formalmente dimostrabile: vale a dire, la formula è un teorema. Ma con l’aiuto delle regole di trasformazione della logica elementare possiamo immediatamente dedurre da questo teorema la formula ‘~(x)~Dim[x,sost(n,13,n)]’. Abbiamo cosí mostrato che, se la formula G è dimostrabile, anche la sua negazione formale è dimostrabile. Ne segue che, se il sistema formale è autocompatibile, la formula G non è dimostrabile.
Un ragionamento in certo modo analogo ma piú complicato è necessario per mostrare che se ~G è dimostrabile allora anche G è dimostrabile. Non abbozzeremo neppure la traccia della dimostrazione.

La conclusione del punto 2) può non apparire, a prima vista, di un’importanza così capitale. Perché è così notevole, ci si può domandare, che sia possibile costruire nell’ambito dell’aritmetica una formula che sia indecidibile? Abbiamo in serbo una sorpresa la quale illumina le profonde implicazioni di questo risultato. Infatti, sebbene la formula G sia indecidibile se gli assiomi del sistema sono autocompatibili, si può tuttavia dimostrare con ragionamenti metamatematici che G è vera. In altre parole, si può dimostrare che G formula uni proprietà numerica complicata, ma ben definita, che sussiste per tutti gli interi, esattamente come la formula ‘(x) ~ (x + 3 = 2)’ (la quale, interpretata nella solita maniera, afferma che non esiste alcun numero cardinale che aggiunto a 3 dia per somma 2) esprime un’altra proprietà (parimenti necessaria) di tutti gli interi. Il ragionamento che convalida la verità della formula indecidibile G è lineare. Primo, nell’ipotesi che l’aritmetica sia autocompatibile, la proposizione metamatematica ‘la formula’,(x) ~ Dim [x, sost (n, 13, n)]’ non è dimostrabile’ è stata provata essere vera. Secondo, questa proposizione è rappresentata nell’ambito dell’aritmetica dalla stessa formula menzionata nella proposizione. Terzo, ricordiamo che le proposizioni metamatematiche sono state proiettate sul formalismo aritmetico in modo tale che proposizioni metamatematiche vere corrispondono a formule aritmetiche vere. (In realtà, l’istituzione di una tale corrispondenza è la raíson d’étre della rappresentazione, come per esempio nella geometria analitica, in cui, in virtù di questo processo, proposizioni geometriche vere corrispondono sempre a proposizioni algebriche vere). Ne segue che la formula G, che corrisponde a una proposizione metamatematica vera, deve essere vera. Si dovrebbe notare, però, che noi abbiamo stabilito una verità aritmetica non deducendola formalmente dagli assiomi dell’aritmetica ma mediante un ragionamento metamatematico.

Ricordiamo ora la nozione di “completezza” introdotta nella discussione del calcolo proposizionale. Abbiamo spiegato che gli assiomi di un sistema deduttivo sono “completi” se ogni proposizione vera esprimibile nel sistema è formalmente deducibile dagli assiomi. Se ciò non è, vale a dire, se non tutte le proposizioni vere esprimibili nel sistema sono deducibili, gli assiomi sono “incompleti”. Ma, dato che abbiamo appena dimostrato che G è una formula vera dell’aritmetica non deducibile formalmente nell’ambito di quest’ultima, ne segue che gli assiomi dell’aritmetica sono incompleti (nell’ipotesi, naturalmente, che essi siano coerenti). Di piú, essi sono essenzialmente incompleti: anche se G fosse aggiunta come un ulteriore assioma, l’insieme piú ampio non sarebbe ancora sufficiente a fornire tutte le verità aritmetiche. Infatti, se gli assiomi iniziali fossero completati nella maniera suggerita, sarebbe possibile costruire nel sistema piú ampio un’altra formula vera ma indecidibile; una tale formula potrebbe essere costruita ripetendo semplicemente, nel nuovo sistema, il procedimento usato originalmente per trovare una formula vera ma indecidibile nel sistema iniziale. Questa conclusione notevole è valida a prescindere da qualsiasi estensione possibile del sistema iniziale. Siamo dunque costretti ad ammettere una fondamentale limitazione nelle possibilità del metodo assiomatico. Contro le precedenti ipotesi, la vasta regione della verità aritmetica non può essere ridotta a un ordine sistematico enunciando, una volta per tutte, un insieme di assiomi da cui dedurre formalmente tutte le proposizioni aritmetiche vere.

Giungiamo finalmente alla coda della stupefacente sinfonia intellettuale di Gödel. Sono stati mostrati i passi con i quali egli ha stabilito la proposizione metamatematica: ‘se l’aritmetica è autocompatibile, essa è incompleta’. Ma è possibile anche dimostrare che questa proposizione condizionale, considerata come un tutto, è rappresentata da una proposizione dimostrabile nell’ambito dell’aritmetica formalizzata.
Questa formula cruciale è facilmente costruibile. Come è stato spiegato nel capitolo 5, la proposizione metamatematica ‘l’aritmetica è autocompatibile’ è equivalente alla proposizione ‘vi è almeno una formula dell’aritmetica che non è dimostrabile’. Quest’ultima è rappresentata nel calcolo formale dalla seguente formula, che chiameremo ‘A’:

(A)	($y) (x) ~ Dim (x, y).

Espressa in parole, essa afferma che ‘vi è almeno un numero y tale che, per ogni numero x, x non sta nella relazione Dim con y’. Interpretata in linguaggio metamatematico, la formula afferma che ‘vi è almeno una formula dell’aritmetica per la quale nessuna sequenza di formule costituisce una dimostrazione’. La formula A, perciò, rappresenta la clausola antecedente della proposizione metamatematica ‘se l’aritmetica è autocompatibile, essa è incompleta’. D’altra parte, la clausola conseguente in questa proposizione, cioè ‘essa [l’aritmetica] è incompleta’, segue direttamente da ‘vi è una proposizione aritmetica vera che non è formalmente dimostrabile nell’aritmetica’; e quest’ultima, come il lettore comprenderà, è rappresentata nel calcolo aritmetico da una vecchia conoscenza, dalla formula G. In base a ciò, la proposizione condizionale metamatematica ‘se l’aritmetica è autocompatibile, essa è incompleta’ è rappresentata dalla formula

($y) (x) ~ Dim (x, y) É (x) - Dim lx, sost (n, I 3, n)],.

che, per brevità, simbolizzeremo con ‘A É G’. (Questa formula si può dimostrare essere provabile, ma non affronteremo tale compito in questa sede.)
Mostreremo ora che la formula A non è dimostrabile. Supponiamo infatti che lo sia. Allora, dato che A É G è dimostrabile, usando la regola di separazione la formula G sarebbe dimostrabile. Ma, a meno che il calcolo non sia contraddittorio, G è formalmente indecidibile, cioè indimostrabile. Perciò, se l’aritmetica è autocompatibile, la formula A non è dimostrabile.
Che cosa significa tale fatto? La formula A rappresenta la proposizione metamatematica ‘l’aritmetica è autocompatibile’. Se quindi questa proposizione potesse essere provata mediante un ragionamento qualsiasi che potesse essere proiettato in una sequenza di formule costituenti una dimostrazione nel calcolo aritmetico, allora la formula A sarebbe dimostrabile. Ma ciò, come abbiamo appena visto, è impossibile, se l’aritmetica è autocompatibile.
Ecco il fondamentale risultato: dobbiamo concludere che, se l’aritmetica è autocompatibile, la sua autocompatibilità non può essere dimostrata da un ragionamento metamatematico dotato di una rappresentazione nell’ambito del formalismo dell’aritmetica!
L’imponente risultato dell’analisi di Gödel non deve essere frainteso: esso non esclude una dimostrazione metamatematica dell’autocompatibilità dell’aritmetica. Ciò che esclude è una dimostrazione di autocompatibilità che possa essere proiettata sulle deduzioni formali dell’aritmetica. Possiamo istituire un’analogia per aiutare il lettore a comprendere questo punto fondamentale. La dimostrazione che è impossibile dividere in tre parti eguali un angolo con soli riga e compasso, non significa che un angolo non possa essere diviso in tre parti eguali con qualche altro mezzo. Al contrario, un angolo arbitrario può essere diviso in tre parti eguali se, per esempio, oltre all’uso della riga e del compasso, si ammette di poter usare un regolo di lunghezza fissata.
Dimostrazioni metamatematiche dell’autocompatibilità dell’aritmetica sono state infatti costruite, specialmente per opera di Gerhard Gentzen, della scuola di Hilbert, nel 1936, e in seguito anche da altri.

La dimostrazione di Gentzen si basa sulla sistemazione di tutte le dimostrazioni dell’aritmetica in un ordinamento lineare, secondo il loro grado di “semplicità”. Tale sistemazione possiede un aspetto che è di un certo tipo “ordinale transfinito”. (La teoria dei numeri ordinari transfiniti fu creata dal matematico tedesco Georg Cantor nel secolo diciannovesimo.) La dimostrazione di autocompatibilità viene raggiunta applicando a quest’ordinamento lineare una regola di inferenza, chiamata “principio dell’induzione transfinita”. L’argomentazione di Gentzen non può essere proiettata sul formalismo aritmetico. Inoltre, sebbene molti studiosi non mettano in dubbio la forza della dimostrazione, questa non è finitistica nel senso delle convenzioni originali di Hilbert per una prova assoluta di autocompatibilità.

Queste dimostrazioni hanno un grande significato logico, tra l’altro, perché propongono nuove forme di costruzioni metamatematiche e perché aiutano a rendere piú chiaro il modo in cui la classe delle regole di inferenza deve essere allargata, se si vuole stabilire la coerenza dell’aritmetica. Queste dimostrazioni, però, non possono essere rappresentate nell’ambito del calcolo aritmetico; e, poiché esse non sono finitistiche, non raggiungono gli obiettivi enunciati nel programma originale di Hilbert.

Note al capitolo 7

Nota 1.Egli usò un adattamento del sistema sviluppato nei Principia mathematica. Un qualsiasi calcolo, però, nel quale il sistema dei numeri cardinali potesse essere costruito, sarebbe servito al suo scopo

Nota 2.Il numero di segni costanti dipende dal modo secondo cui il calcolo viene costruito. Gödel, nel suo articolo, usò soltanto sette segni costanti. Il nostro testo ne usa dieci per evitare certe complessità di esposizione.

Nota 3.Il lettore ricorderà che noi abbiamo definito una dimostrazione come una sequenza finita di formule, ciascuna delle quali è un assioma o può essere dedotta dalle formule precedenti della sequenza con l’aiuto delle regole di trasformazione. Secondo questa definizione, la sequenza riportata nel testo non è una dimostrazione, dal momento che la prima formula non è un assioma, e la sua deduzione degli assiomi non è mostrata: la sequenza è soltanto un frammento di dimostrazione. Sarebbe troppo lungo scrivere un esempio di prova completa, e, per scopi illustrativi, la sequenza citata sarà sufficiente.

Nota 4.Questo teorema è noto come il teorema fondamentale dell’aritmetica. Esso afferma che un intero, non primo, possiede una scomposizione in fattori primi che è unica.

Nota 5.5 - Il lettore deve avere ben presente in mente che, sebbene ‘Dim(x,z)’ rappresenti la proposizione metamatematica, la formula stessa appartiene al calcolo aritmetico. La formula avrebbe potuto essere scritta, con notazione piú familiare, ‘f (x,z) = 0’, in cui la lettera ‘f’ denota un insieme complesso di operazioni aritmetiche sui numeri. Ma questa notazione piú familiare non suggerisce immediatamente l’interpretazione metamatematica della formula.

Ernst Nagel e James R. Newman
La prova di Gödel
8- Riflessioni conclusive

Il significato delle conclusioni di Gödel è di grande portata, anche se non è stato ancora compreso completamente. Queste conclusioni mostrano che la prospettiva di trovare per ogni sistema deduttivo (e in particolare per un sistema nel quale l’intera aritmetica possa venir espressa) una dimostrazione assoluta di autocompatibilità che soddisfi alle richieste finitistiche delle proposte di Hilbert, per quanto non logicamente impossibile, è molto improbabile [1]. Esse mostrano anche che esiste un numero infinito di proposizioni aritmetiche vere che non possono essere formalmente dedotte da alcun insieme di assiomi mediante un insieme chiuso di regole di inferenza. Ne segue che un approccio assiomatico alla teoria dei numeri, per esempio, non può esaurire il dominio delle verità aritmetiche. Ne segue pure che ciò che noi intendiamo per processo di dimostrazione matematica non coincide con l’utilizzazione di un metodo assiomatico formalizzato. Un procedimento assiomatico formalizzato è basato su un insieme, inizialmente determinato e fissato, di assiomi e di regole di trasformazione. Come mostrano i ragionamenti di Gödel, non è possibile porre alcun limite aprioristico all’inventiva dei matematici nell’escogitare nuove regole di dimostrazione. Conseguentemente, non è possibile fare alcuna previsione sulla precisa forma logica delle dimostrazioni matematiche valide. Alla luce di queste considerazioni, l’eventualità di una definizione perfettamente inclusiva della verità matematica o logica, o la necessità - in cui Gödel stesso sembra credere - di un realismo filosofico generale del tipo dell’antico platonismo per definire adeguatamente tale verità, sono problemi ancora dibattuti e troppo difficili per essere ulteriormente analizzati in questa sede.

Il realismo platonico adotta la concezione che la matematica non crea o inventa i suoi “oggetti”, ma li scopre come Colombo scoprì l’America. Ora, se ciò è vero, gli oggetti devono esistere, in una certa maniera, indipendentemente dalla loro scoperta. Secondo la dottrina di Platone, gli oggetti dello studio matematico non si trovano nell’ordine spaziotemporale. Essi sono forme o archetipi disincarnati ed eterni che risiedono in un particolare mondo accessibile soltanto all’intelletto. Secondo questa visione, le forme triangolari o circolari dei corpi fisici, che possono essere percepite dai sensi, non sono gli oggetti propri della matematica. Queste forme sono delle incarnazioni imperfette del triangolo “perfetto” o del cerchio “perfetto”, i quali sono increati, mai compiutamente manifestati dalle cose materiali e comprensibili soltanto dalla mente esploratrice del matematico. Gödel sembra condividere una visione simile quando dice: “Le classi e i concetti possono... essere concepiti come oggetti reali ... esistenti indipendentemente dalle nostre definizioni e costruzioni. Mi sembra che l’ipotesi dell’esistenza di tali oggetti sia assai legittimata, come l’ipotesi dell’esistenza dei corpi fisici, e vi sono molte ragioni per credere nella loro esistenza.”[2]

Le conclusioni di Gödel fanno sorgere la questione se sia possibile costruire una macchina calcolatrice che faccia concorrenza al cervello umano in fatto di intelligenza matematica. Le macchine calcolatrici odierne posseggono un insieme fissato di direttive immagazzinare dentro di esse; queste direttive corrispondono alle regole di inferenza stabilite nella procedura assiomatica formalizzata. Le macchine, così, forniscono risposte a problemi operando in una maniera discontinua, ogni passaggio essendo controllato dalle direttive immagazzinate. Ma, come Gödel dimostrò nel suo teorema di incompletezza, vi sono innumerevoli problemi, nella teoria elementare dei numeri, che esulano dalle possibilità di un metodo assiomatico fissato, e che tali macchine non possono risolvere, comunque intricato e ingegnoso possa essere il loro meccanismo, e comunque rapide possano essere le loro operazioni. Assegnato un certo problema, una macchina di questo tipo potrebbe essere costruita per risolverlo; ma non è possibile costruire una macchina che risolva ogni problema. Il cervello umano, in realtà, possiede le sue intrinseche limitazioni, e vi possono essere dei problemi matematici che esso è incapace di risolvere. Ma, anche così, il cervello umano sembra possedere una struttura di regole di operazione la quale è di gran lunga piú potente della struttura delle macchine che al giorno d’oggi vengono correntemente concepite. Non vi è alcuna prospettiva immediata di rimpiazzare la mente umana con un robot.
La prova di Gödel non dovrebbe essere interpretata come un invito a disperare o come una scusante per coloro che vendono misteri. La scoperta che vi sono delle verità aritmetiche che non possono essere formalmente dimostrate non significa che vi siano delle verità che non riusciremo mai a conoscere, o che una sorta di intuizione “mistica” (radicalmente diversa, nel genere e nell’autorità, da quella generalmente presente nei progressi concettuali) debba sostituire le prove rigorose. Non significa, come un autore recentemente ha preteso, che vi siano dei “limiti ineluttabili alla ragione umana”. Significa invece che le risorse dell’intelletto umano non sono state, né possono essere, formalizzate completamente, e che sempre esistono dei nuovi principi di dimostrazione che attendono di essere inventati o scoperti. Abbiamo visto che è possibile dimostrare con un ragionamento metamatematico “non formale” delle proposizioni matematiche che non possono essere stabilite con una deduzione formale da un dato insieme di assiomi. Sarebbe privo di senso pretendere che queste verità formalmente indimostrabili provate da argomentazioni metamatematiche siano fondate su null’altro che un vuoto richiamo all’intuizione.
Né le inerenti limitazioni delle macchine calcolatrici implicano che non abbiamo il diritto di sperare di spiegare la materia vivente e la ragione umana in termini fisici e chimici. La possibilità di una tale spiegazione non è né preclusa né affermata dal teorema di incompletezza di Gödel. Il teorema in questione indica che la struttura e la potenza della mente umana sono di gran lunga piú complesse e sottili di qualunque macchina non vivente finora immaginata. L’opera di Gödel è un bellissimo esempio di una tale complessità e sottigliezza. È un motivo non per avvilire, ma per apprezzare ancora una volta la potenza della ragione creativa.

Note al capitolo 8
Nota 1.La possibilità di costruire una dimostrazione finitistica assoluta di autocompatibilità per l’aritmetica non è esclusa dai risultati di Gödel. Gödel mostrò che non è possibile alcuna prova che sia rappresentabile nell’ambito dell’aritmetica. Il suo ragionamento non elimina la possibilità di prove strettamente finitistiche non rappresentabili nell’ambito dell’aritmetica. Oggi, però, nessuno ha un’idea chiara del probabile aspetto di una prova finitistica non suscettibile di una rappresentazione o formulazione aritmetica.
Nota 2.K. GÖDEL, Russell's Mathematical Logic, in “The Philosophy of Bertrand Russell” a cura dì Paul A. Schilpp (Evaston, III., 1944) p. 137.

TABELLA 4

Segni costanti	Numero di Gödel	Significato
~	1	non
Ú	2	oppure
É	3	se ... allora...
$	4	vi è un...
(	5	eguale a
0	6	zero
s	7	l’immediato successore di
(	8	segno d’interpunzione
)	9	segno d’interpunzione
.	10	segno d’interpunzione

TABELLA 5
a)Le variabili numeriche sono associate a numeri primi maggiori di 10.

Variabile numerica Numero di Gödel Possibile esempio di sostituzione
x 11 0
y 13 s0
z 17 y

b)Le variabili proposizionali sono associate ai quadrati di numeri primi maggiori di 10.

Variabile proposizionale Numero di Gödel Possibile esempio di sostituzione
p 11² 0=0
q 13² ($x)(x= sy)
r 17² p É q

c)Le variabili predicative sono associate ai cubi di numeri primi maggiori di 10.

Variabile predicativa Numero di Gödel Possibile esempio di sostituzione
P 11³ primo
Q 13³ composto
R 17³ maggiore di

TABELLA 6
La formula aritmetica ‘zero eguale a zero’ ha come numero di Gödel il numero 243 000 000.
Leggendo da A a E, la tabella mostra come il numero venga tradotto nell’espressione che rappresenta; leggendo da E ad A, come si possa dedurre il numero di Gödel per la formula scritta.

A
243 000 000
B
64 ´ 243 ´ 15 625

C
2⁶ ´ 3⁵ ´ 5⁶

D

6 6 6
¯ ¯ ¯
0 = 0

E 0 = 0

Nota informativa sul testo e gli autori
Gli autori si ripromettono di rendere facilmente comprensibile la potenza argomentativa di Kurt Gödel, paragonabile almeno con quella di Euclide e che rappresenta uno degli apici del pensiero matematico, raggiunto paradossalmente proprio con una dichiarazione d’impotenza.
Si tratta del metodo assiomatico, di quel metodo cioè, che consiste nell’accettare senza dimostrazione certe proposizioni come assiomi , e quindi nel derivarne come teoremi tutte le altre proposizioni del sistema. Tale metodo sosteneva tutta la grande costruzione dell’aritmetica e, nelle fondamenta di David Hilbert, tendenti a dargli una compiutezza come sistema logico, raggiungeva la soddisfazione estetica.
Eppure proprio qui il metodo fallí: il ragionamento assolutamente lineare di Gödel, reso ancora piú semplice dalla prodigiosa capacità espositiva degli autori, pone in luce le limitazioni del metodo e di qualunque costruzione su di esso basata, e piú in generale l’incompiutezza di qualunque sistema.
Le idee di Gödel - di cui i lettori noteranno certe affinità con quelle esposte da Heisenberg in altri libri di questa stessa collana - sono presentate dagli autori premettendo una succinta ma completa esposizione della logica formale.