l'eredità di Gödel: rivisitando la Logica

8/3/2019 l'eredit di Gdel: rivisitando la Logica

1/12

Leredit di Gdel: rivisitando la Logica

Giuseppe Ragun Universit UCAM di Murcia, Spagna ([email protected])

May 2, 2013

1. Introduzione

2. Il fardello di una frase

3. Licenze di Chaitin

4. Unavvizzita classificazione

5. Linterpretazione del Secondo Teorema dincompletezza

Abstract

Si evidenziano alcuni diffusi equivoci su argomenti fondamentali di

Logica: linterpretazione dei due Teoremi dincompletezza, diverse leg-

gerezze di Chaitin e lusuale classificazione dei Sistemi assiomatici in base

allordine espressivo.

Some common fallacies about fundamental themes of Logic are ex-

posed: the First and Second incompleteness Theorem interpretations,

Chaitins various superficialities and the usual classification of the ax-iomatic Theories in function of its language order.

PAROLE CHIAVE: Incompletezza, indecidibilit, coerenza, categoricit, com-pletezza semantica, casualit, complessit, linguaggi del primo or-dine, linguaggi del secondo ordine.

KEYWORDS: Incompleteness, undecidability, semantic completeness, categoric-ity, randomness, Chaitins constant, first and second order languages,consistency.

1 Introduzione

Da sempre, dopo aver goduto dei frutti del genio di alcuni uomini straordinari,dobbiamo subire lindiscutibilit di qualsiasi loro conclusione: tutto ci che essihanno asserito oro colato. In Fisica, un esperimento pu porre fine alle piostinate persuasioni, ma se la dottrina relazionata con la Filosofia pura, lecose sono molto pi complicate e quasi mai risolvibili in modo perentorio.

Tuttavia in alcuni settori applicati della Filosofia, come in Logica matem-atica, da qualche tempo possibile - e doveroso - esigere correttezza e rigore. Il

1


2/12

formalismo introdotto da Hilbert alla fine dell800 ha, infatti, dotato le Disci-

pline matematiche di una prescritta sistemazione simbolica, priva dellambiguitdi ricorsi allintuito e suscettibile di una rigorosa analisi epistemologica. Neseguirono i pregevoli - e sconvolgenti - risultati della Logica moderna, capeg-giati dalle dimostrazioni di Gdel.

Ci nonostante, a tuttoggi restano assai estesi non pochi gravi errori e ma-lintesi su argomenti anche dimportanza fondamentale. Tali equivoci, assiemealluso di una terminologia che gi da tempo si rivelata insidiosa e insuffi-ciente, ostacolano la diffusione - e non solo in ambito umanistico - di questoinestimabile ed affascinante sapere.

Illustreremo brevemente alcune di tali confusioni, coscienti di non poterpretendere, in questa sede, ladeguato grado di profondit che gli argomentimeriterebbero.

2 Il fardello di una frase

Il primo appunto riguarda lambito di applicabilit del Primo Teorema di In-completezza di Gdel. Ometteremo, qui, lenunciato e le importantissime impli-cazioni di tale famoso Teorema, che il lettore potr trovare in un qualsiasi buonlibro di Logica. Ci che si deve sottolineare che le ipotesi stesse del Teoremaimpongono la numerabilit dellinsieme dei teoremi e delle dimostrazioni dellaTeoria a cui pu applicarsi1. Come operazione previa alla dimostrazione, Gdelstabilisce un particolare codice numerico (chiamato brevemente gdeliano) siaper gli enunciati che per le dimostrazioni. Quando applicata alla Teoria formale2

dei numeri naturali (o Aritmetica di Peano, in seguito PA), tale codificazionefa s che ad ogni enunciato e ad ogni dimostrazione venga assegnato un codice

numerico, unico ed esclusivo. Ma che succede se si fa lo stesso con una Teoriaaritmetica che possiede una quantit pi che numerabile di teoremi? Tale Teoriaesiste e viene usualmente chiamata Aritmetica del secondo ordine (nel seguitoASO). Le sue premesse contengono uno schema assiomatico metamatematicoche, generalizzando il principio di induzione di PA, introduce un assioma perogni elemento di P(N), linsieme di tutti i sottoinsiemi di numeri naturali. Datoche tale insieme pi che numerabile, ne consegue che anche gli insiemi dei teo-remi e delle dimostrazioni sono pi che numerabili. Pertanto, in tale Teoria, nontutte le dimostrazioni possono possedere un distinto gdeliano : o sarebbero nu-merabili. La pi che numerabilit delle dimostrazioni rivela luso imprescindibiledi una strategia intrinsecamente semantica(cio con limpiego di significati noninteramente codificabili) per la deduzione dei teoremi. Anche volendo consid-

erare il principio di induzione completa come un singolo assioma simbolico, nerisulta un assioma semantico che non decidibile (n effettivamente numerabile),in quanto la sua semanticit ineliminabile. A tale conclusione si giunge, per es-

1Un insieme si dice numerabile se pu essere messo in corrispondenza biunivoca conlinsieme dei numeri naturali.

2Con laggettivo formale intenderemo, ovunque in questo articolo, lassenza di significatoesplicito, ovvero lo stesso che sintattico, simbolico, codificato.

2


3/12

empio, se si rappresenta il Sistema nella Teoria formale degli insiemi3: lassioma

si traduce in uno schema assiomatico insiemistico che genera una quantit piche numerabile di assiomi induttivi4.La semplice conseguenza che il Primo teorema dincompletezza non pu

applicarsi allASO5. Eppure questo equivoco largamente e scandalosamentediffuso un p dovunque, anche in ambiti specificatamente tecnici6. Spesso sinota un tipico e inaspettato abbandono di rigore terminologico intorno allaquestione, probabilmente significativo di dubbi malcelati: una frase ricorrente,per esempio, che anche lAritmetica del secondo ordine, dato che contienegli assiomi di PA, soggetta al Teorema dincompletezza. Ma, naturalmente,si deve anche conservare leffettiva assiomatizzabilit. Emblematico il casodella Teoria che si ottiene da PA aggiungendo come assiomi tutti gli enunciatidi PA veri nel modello standard: anchessa contiene tutti gli assiomi di PA ma completa.

A rigore, anche possibile che lASO sia sintatticamente completa, malgradoil suo linguaggio sia semanticamente incompleto. Trattandosi di un Sistema nonformale, la risposta a questo interessante interrogativo non pu che venire dallaMetamatematica7.

Ci sono ben pochi dubbi sul fatto che questo stato di cose si debba, essenzial-mente, allintoccabilit della figura di Gdel. Nella presentazione del Teoremadincompletezza al convegno di Knigsberg del 1930, Gdel annunci il suo risul-tato come una prova dellincompletezza semantica dellAritmetica, dato cheessa categorica8. Ora, poich ci si riferisce a unAritmetica categorica9, nonpu che trattarsi dellASO. Gdel, pertanto, basa la sua affermazione applicando- erroneamente - il Primo Teorema dincompletezza allAritmetica pi che nu-merabile: dallincompletezza sintattica e dalla categoricit segue, infatti, anche

lincompletezza semantica. Nonostante lerrore, la conclusione corretta: come3Una qualsiasi tra NBG, ZF o MK.4G. Ragun, I Confini logici della Matematica, Aracne Roma (2010), p. 127-129. Sono

anche disponibili versioni on-line, pi aggiornate, su Amazon, Bubok, Lulu e Scribd. Versionein spagnolo: Confines lgicos de la Matemtica, rivista culturale La Torre del Virrey - Nexofa,nel Web: http://www.latorredelvirrey.es/nexofia/pdf/Confines-logicos-de-la-matematica.pdf(2011).

5Infatti in tale Teoria, lenunciato di Gdel, la cui interpretazione standard non esistecodice di una dimostrazione di questo stesso enunciato non equivale pi a io non sonodimostrabile in questa Teoria, come succede in PA.

6Due esempi: < >, E. Moriconi, I teoremi di Gdel, SWIF (2006), sulWEB: http://lgxserve.ciseca.uniba.it/lei/biblioteca/lr/public/moriconi-1.0.pdf, p. 32. C.Wright, On Quantifying into Predicate Position: Steps towards a New(tralist) Perspective(2007), p. 22 sul WEB: http://philpapers.org/autosense.pl?searchStr=Crispin%20Wright. In

questultimo lavoro forse indicativo che lautore commenti tale propriet con una serie didelicati quesiti epistemologici. In entrambi i casi, comunque, la propriet viene consideratacome ovvia, senza nessuna spiegazione.

7G. Ragun, op. cit.(nota n.4), p. 232-233.8K. Gdel, Collected Works I: publications 1929-1936, eds. S. Feferman et al., Oxford

University Press (1986), p. 26-29.9Una Teoria si dice categorica se ammette un unico modello a meno disomorfismi. In

termini pi semplici (ma anche piuttosto imprecisi), se ammette ununica interpretazionecorretta.

3


4/12

conseguenza del Teorema di Lwenheim-Skolem10, la categoricit e linfinit di

un modello sono sufficienti ad assicurare lincompletezza semantica del linguag-gio di una qualsiasi Teoria. Tuttavia, non tutte le sconcertanti conseguenze diquestultimo fondamentale Teorema, divennero chiare prima del 1936 (graziealla generalizzazione di Malcev) presso tutti i logici del tempo, inclusi Gdel eSkolem.

Ci si pu legittimamente domandare, nei riguardi del pi grande logico ditutti i tempi, non solo che cosa lo abbia indotto in errore, ma soprattutto per-ch non abbia mai corretto, successivamente, la sua affermazione. Risponderealla prima domanda non sembra facile. Qui osserviamo solo che, almeno finoal 1930, Gdel raramente distingue i due tipi di Aritmetica cos logicamentedifferenti. Daltra parte, in quel periodo, n lui n alcun altro logico evidenziamai lintrinseca semanticit delle Teorie con un numero pi che numerabile dienunciati. E le conseguenze di ci.

Si pu ben comprendere, daltra parte, perch non ci sia giunto alcun tipodi correzione circa la citata affermazione. Il motivo che essa coinvolge unargomento - la completezza / incompletezza semantica e la sua relazione conla categoricit - che nel fondo, come si riconobbe successivamente, ha benpoco a che vedere con la completezza sintattica e quindi con il Primo Teo-rema dincompletezza. Nel corso degli anni 30, il suddetto tema era assaidattualit, soprattutto a causa delle preoccupazioni di Hilbert circa il prob-lema della categoricit. Gdel cominci col dimostrare che il linguaggio formaleclassico11 semanticamente completo: se coerente ha sempre almeno un mod-ello12. Ne seguiva che una Teoria formale sintatticamente incompleta, cio conalmeno un enunciato indecidibile I, non poteva essere categorica. Infatti, essaammette almeno due modelli non isomorfi: uno in cui I vero ed un altro

in cui falso. Oltre a ci, Gdel continu a congetturare, come tacitamentesupposto da Hilbert ed ogni altro logico del tempo, che la completezza sintat-tica di una Teoria formale (o, pi in generale, di una Teoria con un linguaggiosemanticamente completo) implicasse la sua categoricit. Di conseguenza, sivide nel Primo Teorema dincompletezza, subito dopo la sua accettazione, unostrumento capace di discriminare la categoricit e/o la completezza semantica.Ad esempio, si ritenne che la Teoria formale PA fosse non categorica perchsintatticamente incompleta.

Come abbiamo gi accennato, la piena comprensione del Teorema di Lwenheim-Skolem rese chiaro, dopo alcuni anni, che la categoricit impossibile per ogniSistema formale (o, pi in generale, con un linguaggio semanticamente completo)dotato di un modello infinito (che il caso delle Discipline di ordinario interesse);sia esso sintatticamente completo o no. In tal modo, il tema in questione veniva

finalmente decifrato grazie alle conseguenze del Teorema di completezza seman-tica (da cui, infatti, deriva lo stesso Teorema di Lwenheim-Skolem). N Gdel,n altri logici avveduti ebbero buoni motivi per ritornare su una frase che, in

10Si include, qui, sia la versione allins che allingi del Teorema.11Preferiamo chiamarlo cos piuttosto che Logica classica del primo ordine, per ragioni che

chiariremo presto.12Teorema di completezza semantica, 1929.

4


5/12

definitiva, si era rivelata quantomeno fuorviante circa le ripercussioni del Primo

Teorema dincompletezza. Le quali erano invero assai profonde, ma riguarda-vano aspetti di natura fondamentalmente diversa. I pi significativi legati alconcetto, nuovo e dirompente, di macchina, come fu chiarito principalmente daChurch, Turing e, successivamente, Chaitin.

Il triste epilogo che, ancora oggi, risulta facile imbattersi in frasi che, nellasostanza, ribadiscono senza alcun tipo di correzione la sfortunata frase di Gdel.Per esempio: lincompletezza sintattica dellAritmetica al primo ordine producelincompletezza semantica della Logica al secondo ordine!13. Sorvolando sullaterminologia dell"ordine espressivo" (che, come evidenzieremo pi avanti, cisembra ambigua), pare che si voglia in primo luogo suggerire la trasmissioneautomatica dellincompletezza sintattica al Sistema ampliato, cio a quello "delsecondo ordine" (prima scorrettezza); e, successivamente, dallincompletezzasintattica e dalla categoricit, concludere lincompletezza semantica del linguag-

gio (mentre basterebbe la categoricit pi linfinit di un modello). Del resto,laffermazione letteralmente smentita dalla semplice osservazione che ancheper il linguaggio della Teoria integrale dei reali "del secondo ordine", informalee categorica, non vale il Teorema di completezza semantica; e ci malgrado lasua versione formale del primo ordine sia sintatticamente completa (come di-mostrato da Tarski). Evidentemente, lincompletezza semantica del linguaggiodi tale Teoria prodotta soltanto dalla sua categoricit, unitamente allinfinitdel modello. Che ruolo dovrebbe giocare qui lincompletezza sintattica di PA?

Anche in un libro pi recente si pretende concludere lincompletezza se-mantica della "logica del secondo ordine" sia sfruttando il Primo Teoremadincompletezza, sia il Teorema di Church-Turing14. Nel primo caso il Teoremaviene illegalmente applicato allAritmetica del secondo ordine. Nel secondo caso,

lautore - allineandosi con tanti altri autori - fonda la dimostrazione sul fattoche se [per assurdo] la logica del secondo ordine fosse [semanticamente] com-pleta allora dovrebbe esistere un sistema di enumerazione delle formule valideal secondo ordine...15. Si intende uneffettiva numerabilit. Tuttavia tale con-seguenza suppone che tutte le formule del secondo ordine siano numerabili. Mase con lespressione "logica del secondo ordine" si vuole indicare un Sistemanumerabile, lAritmetica categorica non ne fa pi parte!

In verit, fino a quando lincompletezza (o la completezza) sintattica dellASOresta indimostrata, non si scorgono alternative alluso del Teorema di Lwenheim-Skolem per dimostrare lincompletezza semantica del suo linguaggio.

Infine, si ripete spesso persino il vecchio abbaglio che la non categoricitdellAritmetica formale, PA, si deve alla sua incompletezza sintattica. Un pcome dire che linfinit dei poligoni si deve al fatto che i triangoli isosceli sono

infiniti.13E. Moriconi, ibidem (nota n. 5). Una frase del tutto simile si ripete nellabstract di F.

Berto, Gdels first theorem, ed. Tilgher Genova, fasc. Epistemologia 27, n.1 (2004). Maanche presso tanti altri autori.

14C. L. De Florio, Categoricit e modelli intesi, ed. Franco Angeli (2007).15C. L. De Florio, op. cit., p. 54.

5


6/12

3 Licenze di Chaitin

Nel 1970, Gregory Chaitin formul uninteressante versione informatica delPrimo Teorema dincompletezza. Nella sua presentazione pi semplice essa pre-scrive che una qualsiasi macchina che rispetti la Tesi di Church-Turing16 pustabilire la casualit di un numero necessariamente finito di stringhe di sim-boli. La casualit di una stringa simbolica, viene definita come limpossibilit,per la macchina stessa, di comprimerla per pi di un certo grado (che dovrprefissarsi). Per ogni macchina, esiste un numero infinito e preponderante distringhe casuali: infatti, si pu facilmente concludere che, data ad arbitrio unastringa finita di simboli, la probabilit che una prestabilita macchina possacomprimerla sempre molto bassa (a meno di non considerare un grado di com-pressione davvero irrisorio). Tuttavia ci non toglie che le stringhe comprimibilisiano infinite; inoltre bisogna evidenziare che gli ordinari prodotti umani, anche

codificati in simboli, sono quasi sempre non casuali17

. Grazie allinterpretazionedi Chaitin, sappiamo che ogni macchina pu indicarci soltanto un numero finitodelle stringhe che non pu comprimere. Come conseguenza, nessun programmadi compressione, che termini sempre, pu essere stabilito con certezza come ide-ale, cio immigliorabile: per assurdo, sarebbe in grado di stabilire la casualitdi qualsiasi stringa, per il fatto che non riesce a comprimerla; in violazione dellacitata versione dellincompletezza18.

Purtroppo Chaitin ha rilasciato affermazioni superficiali, spesso scorrette,che causano pericolose confusioni sulla questione dellincompletezza, gi di pers non cos facile. Il fatto che le suddette conclusioni valgano anche per le mac-chine universali19, lo ha indotto, in primo luogo, a trascurare che la definizionedi casualit si riferisce sempre e comunque ad una concreta macchina partico-

lare. Inoltre, per il fatto ovvio che in ogni ordinario calcolatore i numeri naturalisi rappresentano mediante stringhe, egli ha precipitosamente assegnato la pro-priet della casualit ai numeri naturali. Come risultato di tale approssimativitegli ha pi volte proclamato di aver scoperto la casualit in Aritmetica20. Rib-

16Tale famosa Tesi, non che la supposizione che tutte le macchine siano riproducibililogicamente tramite funzioni ricorsive e viceversa. Le funzioni ricorsive rappresentano tuttoil possibile campo di calcolabilit dambito aritmetico. Dettagli pi esatti ed ampi possonotrovarsi in un qualsiasi buon libro di Logica.

17Da cui la diffusione delle tecniche di compressione dei files del tipo loss-less, cio senzaperdita o alterazione di dati, come zip, tar, etc.. Comunque, per i prodotti con maggiorecasualit, come video e musica, si pu comprimere efficacemente solo con perdita o deteriorodi dati, come nei formati jpeg, mp3, etc.

18G. Ragun, op. cit., p. 217.19Una macchina si dice universale se in grado di riprodurre logicamente il comporta-

mento di una qualsiasi altra macchina. La sua esistenza deriva dalla Tesi di Church-Turing edallesistenza di funzioni ricorsive universali. Un esempio di macchina universale un qualsi-asi, anche modesto, PC ma con una memoria ampliabile senza limiti.

20Due esempi: recentemente ho dimostrato che esiste una casualit nella teoria dei numeri.Il mio lavoro dimostra che - per usare una metafora di Einstein - Dio talvolta gioca a dadi coni numeri interi!, La casualit in Aritmetica, rivista Le Scienze n. 241, settembre (1988); inpoche parole, Gdel ha scoperto lincompletezza, Turing lincomputabilit e io la casualit,prefazione del libro The unknowable, ed. Springer-Verlag, Singapore (1999). Frasi di questotipo, comunque, si ripetono in quasi tutte le sue pubblicazioni, anche pi recenti.

6


7/12

adiamo che la definita casualit una propriet che riguarda soltanto le stringhe

di caratteri e si ripercuote sui numeri naturali solo attraverso la codificazioneche per essi si scelta. Questultima, dal punto di vista logico, del tutto ar-bitraria. Di fatto, possibile che una determinata macchina faccia uso di unacodificazione (sia pure assolutamente scomoda e dispendiosa di bits) che rendefinito il numero di numeri naturali casuali (o meglio delle stringhe che li rappre-sentano)21. Inoltre, come dicevamo, anche la casualit delle stringhe relativaal funzionamento e al codice della macchina prefissata. Data unarbitraria esufficientemente lunga stringa casuale per una determinata macchina, non cnulla che vieti lesistenza di unaltra macchina, magari concepita ad hoc, cheriesca a comprimerla. Per essa, possibilmente, saranno invece casuali talunestringhe considerate comprimibili nelle macchine che usano gli ordinari codici.

Nello stesso articolo de Le Scienze gi citato, Chaitin scrive:

La maggior parte dei matematici non ha dato molto peso [allincompletezza]....forse bisognerebbe [invece] cercare nuovi assiomi validi per i nu-meri interi. La quantit di problemi matematici rimasti irrisoltiper centinaia o migliaia di anni tende a rafforzare la mia tesi. Nonpotrebbe darsi che qualcuno di tali enunciati sia indimostrabile? Secos fosse, forse i matematici farebbero meglio ad accettarlo comeassioma. Questa proposta potrebbe sembrare ridicola a molti matem-atici... ma non agli scienziati empirici... In realt, in alcuni casii matematici hanno gi assunto a fondamento congetture non di-mostrate ma utili.

Queste parole sembrano proporre la rivoluzione gdeliana di una nuovaMatematica empirica che, in verit, esiste da sempre: quella che fa anche uso

di congetture. Considerare come assiomi queste ultime senza alcuna giustifi-cazione metamatematica sarebbe, naturalmente, inutile oltrech imprudente. Enon suona a progresso ma a presunzione rinunciataria: si desiste, a priori, dalricercare metadimostrazioni di indecidibilit che si sono spesso rivelate prezioseminiere per la Logica e la Matematica. Tanto pi se si considera che il Teoremadincompletezza non preclude, per nessun enunciato indecidibile, la possibilitdi un riconoscimento puramente metamatematico. Questo scorretto punto divista si ripete, entusiasticamente, in quasi tutti i suoi lavori pi recenti: di fattoegli giunge a questionare, sulla base (epidermica, non certo logica) del Teoremadincompletezza, lopportunit stessa dei Sistemi assiomatici22!

Il logico svedese Torkel Franzn, scomparso recentemente, ha evidenziato nel2005 altre errate leggerezze di Chaitin23. Lunica che qui riferiamo quella rela-

tiva allabstract di un articolo dove si afferma: Il teorema di Gdel pu essere di-mostrato mediante argomenti la cui natura appartiene alla teoria dellinformazione.In tale approccio possibile evincere che se un teorema contiene pi informazioni

21Due esempi in: G. Ragun, op. cit., p. 218-219.22G. Chaitin, The halting probability: irreducible complexity in pure mathematics, Milan

Journal of Mathematics n. 75 (2007), p. 2 e seguenti.23T. Franzn, Gdels Theorem: an incomplete guide to its use and abuse, A.K. Peters

(2005).

7


8/12

rispetto a un dato insieme di assiomi, allora impossibile per il teorema essere

derivato da quegli assiomi

24

. La frase mescola scorrettamente la proprietche per ogni macchina esistono sempre infinite stringhe casuali, con la capac-it dimostrativa della macchina stessa (soggetta al Teorema dincompletezza).Franzn confuta in modo semplice ed ineccepibile: dal solo assioma x(x=x),di complessit costante, si pu ottenere un teorema, n=n, di complessit arbi-trariamente grande al crescere del numero naturale n. Questultima propriet,infatti, garantita qualora si rappresentino i naturali con un ordinario codiceesponenziale in base qualsiasi.

La costante , introdotta da Chaitin in riferimento a una prefissata macchinauniversale, rappresenta la probabilit che un programma della macchina, sceltoa caso, si fermi. Il suo indiscutibile interesse si deve al fatto che rappre-senta una sorta di massima compressione della conoscenza matematica: dallaconoscenza dei primi n bits di si pu risolvere il problema dellarresto per

tutti i programmi di lunghezza minore o uguale a n. Tuttavia, Chaitin ne esaltaoltremisura limportanza, giungendo perfino a descrivere come il mezzo perottenere la conoscenza25. Naturalmente, le cifre di non sono, invece, chelimmigliorabile modo di riassumere tale conoscenza matematica, per il cui rag-giungimento non restano che i tradizionali teoremi e metateoremi.

Queste critiche non hanno lo scopo di scalfire la figura di questo grandelogico-informatico, ma pretendono solo aiutare a far chiarezza su un panoramache, non soltanto ai non esperti, appare piuttosto confuso.

4 Unavvizzita classificazione

Si vuole adesso criticare lusuale classificazione delle Teorie assiomatiche clas-

siche in base allordine espressivo: primo ordine, secondo ordine, etc.26. Purtropposi consolidato negli anni il ritenere che la formalit del linguaggio (o, pi ingenerale, la sua completezza semantica) sia una prerogativa del primo ordineespressivo e daltra parte che i linguaggi di ordine superiore siano tutti nec-essariamente semantici (tipicamente, pi che numerabili). Lerrore dovutoprincipalmente a due malintesi.

Il primo legato al significato dellespressione Logica classica del primo or-dine. Con tale locuzione si intende normalmente la collezione di tutti i Calcolipredicativi classici. Ogni Calcolo predicativo classico una Teoria formale del

24G. Chaitin, Gdels Theorem and Information, International Journal of TheoreticalPhysics, n. 22 (1982). Traduzione dellautore.

25Per esempio, nellarticolo: Meta-mathematics and the foundations of Mathematics,

EATCS Bulletin, vol. 77, pp. 167-179 (2002), espone un criterio che dovrebbe esser valido inprincipio per risolvere lipotesi di Riemann a partire dalla conoscenza di un numero sufficientedi bits di . Ma il ragionamento un palese circolo vizioso!

26Un linguaggio si dice del primo ordine se i quantificatori e possono riferirsi soltantoa variabili (come avviene in ogni retta parallela a r anche parallela a t). Al secondo ordine,si pu quantificare anche sui predicati (e tradurre frasi come: ogni relazione che c tra lerette r e t, c anche tra le rette r e s). Al terzo ordine si pu quantificare anche su relazioniancora pi generali (super-relazioni) e cos via allinfinito.

8


9/12

primo ordine che consiste: a) di alcuni assiomi di base, del primo ordine, indi-

viduati per la prima volta da Russell e Whitehead, che formalizzano i concettinon, o ed esiste27; b) di altri eventuali assiomi propri, sempre numerabili edel primo ordine, che formalizzano alcuni concetti particolari che si vogliono us-are nella Teoria (per esempio: uguale, maggiore di, perpendicolare, etc.); c)delle quattro regole deduttive classiche di particolarizzazione, generalizzazione,sostituzione e modus ponens. Dato che tali regole si compongono di operazionimeramente sintattiche sugli assiomi e/o sui teoremi via via dedotti (cio si appli-cano, macchinalmente, solo al codice simbolico degli assiomi), in ogni particolareCalcolo - e quindi nellintera Logica classica del primo ordine - risulta semprerispettata la formalit. Ma, ovviamente, ci non significa che ogni Teoria delprimo ordine, fondata su un particolare Calcolo predicativo classico e che deducasolo con le quattro regole classiche, debba essere formale. Nulla vieta, ad esem-pio, che la Teoria aggiunga una quantit pi che numerabile di assiomi propri a

tale Calcolo, bench tutti espressi al primo ordine: ne risulterebbe un linguaggiointrinsecamente semantico e dunque non formale. La Logica classica del primoordine, in altri termini, non ingloba tutti i Sistemi classici del primo ordine.Infiniti di essi usano un linguaggio informale e/o semanticamente incompleto28.

Il secondo equivoco legato al Teorema di Lindstrm. Esso afferma che ogniTeoria classica espressa in un linguaggio semanticamente completo pu essereespressa con un linguaggio del primo ordine. La confusione deriva dal con-fondere il pu con un deve. Il Teorema non vieta la completezza semantica, nla formalit, dei linguaggi di ordine superiore al primo. Afferma soltanto che,quando si ha questo caso, la Teoria pu essere ri-espressa in un - pi semplice- linguaggio del primo ordine. Certamente, questa propriet distingue la parti-colare importanza del primo ordine espressivo. Una propriet che, daltronde,

pu gi evidenziarsi grazie alle capacit espressive della Teoria formale degliinsiemi: ogni Sistema formale, infatti, in quanto totalmente rappresentabile intale Teoria - che del primo ordine - esprimibile al primo ordine. Ma taleimportanza non va radicalizzata.

Sicuramente, il fatto innegabile che i linguaggi del secondo ordine siano, nelcaso tipico, pi che numerabili e dunque intrinsecamente semantici, aggrava lasituazione. Ci di deve al fatto che, se il modello infinito, i predicati vari-ano, nel caso pi generale, su un insieme senzaltro pi che numerabile. Ma,certamente, nulla impedisce lesistenza di un assioma che limiti tale variabil-it a un sottoinsieme numerabile; e, in particolare, che sia rispettata anchela formalit29. Un esempio concreto il Sistema ottenuto da PA esprimendoil suo principio di induzione parziale, cio limitato agli enunciati con almeno

27

Gli altri usuali concetti classici, come e, implica e qualunque sia, vengono definiti me-diante questi. Inoltre, ricordiamo che anche non e o possono ottenersi dallunico connettivoNAND (o NOR), come dimostrato da H. Sheffer nel 1913.

28A sostegno: M. Rossberg, First-Order Logic, Second-Order Logic, and Completeness,Hendricks et al. (eds.) Logos Verlag Berlin (2004), sul WEB:

http://www.st-andrews.ac.uk/~mr30/papers/RossbergCompleteness.pdf29Si legga ad esempio: H. B. Enderton, Second order and Higher order Logic, Standford En-

cyclopedia of Philosophy (2007), sul WEB: http://plato.standford.edu/entries/logic-higher-order/.

9


10/12

una variabile libera, come un singolo enunciato simbolico (anzich come uno

schema assiomatico metamatematico). Ne risulta un assioma del secondo or-dine che bisogna ancora interpretare semanticamente, dato che le premesse delSistema non specificano alcuna deduzione sintattica con formule del secondoordine. Tuttavia tale semantica non intrinseca, cio ineliminabile: rappre-sentando il Sistema nella Teoria formale degli insiemi, tale assioma si traducein uno schema assiomatico insiemistico che genera una quantit numerabile diassiomi induttivi formali. Di conseguenza, nella stessa Teoria originaria la for-malit potrebbe ripristinarsi aggiungendo le opportune premesse con cui operaresintatticamente sullassioma induttivo del secondo ordine in modo da produrre irichiesti teoremi sulle propriet enunciabili simbolicamente. Ma, naturalmente,esistono strategie pi semplici per ricostituire tale formalit30.

Come risultato della confusione, spesso si critica il carattere non formaledelle Teorie del secondo (o pi) ordine sulla base dellintrinseca semanticit di

alcune di esse. E altri, anzich evidenziare che il problema non risiede nel tipo diordine espressivo, bens nella particolare fisionomia delle premesse della Teoria,ribattono che anche alcuni Sistemi del secondo ordine possiedono una vesteformale come quelli del primo. Semmai, come alcuni del primo!

In conclusione, il raggruppamento delle Teorie assiomatiche classiche in baseallordine espressivo fuorviante, in generale, delle loro propriet logiche fonda-mentali. Queste sono conseguenza della struttura delle premesse, in cui lordineespressivo non gioca sempre un ruolo decisivo. Il principale strumento di clas-sificazione resta il rispetto della formalit hilbertiana o, pi in generale, dellacompletezza semantica del linguaggio.

5 Linterpretazione del Secondo Teorema dincompletezza

Finalmente, bisogna far chiarezza sullabituale, erronea, interpretazione del Sec-ondo Teorema dincompletezza. In riferimento a una Teoria che soddisfa le stesseipotesi del Primo, il Secondo Teorema dincompletezza generalizza lindecidibilitad una classe di enunciati che, interpretati nel modello standard significanoquesto Sistema coerente. La sua (non semplice) dimostrazione, solo accen-nata da Gdel, fu rilasciata da Hilbert e Bernays nel 1939.

Lusuale interpretazione di questo Teorema, soggetta alle nostre critiche, che ogni Teoria che soddisfa le ipotesi del Primo Teorema dincompletezza nonpu dimostrare la propria coerenza. Ci sembra evidente, infatti, che la conclu-sione che una Teoria non possa dimostrare la propria coerenza sia valida perun qualunque Sistema classico, anche non formale! Inoltre, che tale conclusione

non spetti al Secondo Teorema dincompletezza, ma ad un nuovo Metateorema.Consideriamo un arbitrario Sistema classico. Se esso incoerente, privo di

modelli e, quindi, di ogni sensata interpretazione di qualsiasi sua proposizione31.Pertanto, il semplice ammettere che un enunciato del Sistema significhi qual-

30G. Ragun, op. cit., p. 160-161.31Pi in profondit: di qualsiasi interpretazione che rispetti i principi di non contraddizione

e del terzo escluso.

10


11/12

cosa, implica supporre la sua coerenza. E ci vale, in particolare, anche se

linterpretazione dellenunciato questo Sistema coerente. Dunque, se nonsi pu essere certi della coerenza della Teoria (cosa che, a voler sviscerare i fon-damenti, vale per ogni Disciplina), neppure si pu esserlo di nessuna interpre-tazione del suo linguaggio. Nel caso dellusuale Geometria, per esempio, quandodimostriamo il teorema di Pitagora, in realt quello concludiamo : se il Sistemaammette il modello euclideo (e quindi coerente), allora in ogni triangolo ret-tangolo c1

2+c22=I2. Certo, una deduzione di innegabile valore epistemologico,

anche nel caso di clamoroso sfacelo qualora il Sistema si rivelasse incoerente.Supponiamo, per, che a un certo teorema T di una determinata Teoria vengaattribuito il significato questo Sistema coerente in un certa interpretazioneM. Analogamente, quello che in realt concludiamo tramite detto teorema seil Sistema ammette il modello M (e quindi coerente), allora il Sistema co-erente. Qualcosa che sapevamo gi e, soprattutto, che non dimostra affatto la

coerenza del Sistema. In definitiva, per un siffatto enunciato si ha una situazionepeculiare che lo differenzia da qualsiasi altro enunciato significativo in M: preoc-cuparsi di dimostrarlo allinterno del Sistema ininfluente ai fini epistemologicirelativi allinterpretazione M. In termini pi semplici, lenunciato in questionepu essere indecidibile oppure un teorema senza nessuna differenza dal puntodi vista epistemologico. Soltanto, non pu essere il negato di un teorema, seM davvero un modello. In ogni caso, il problema di concludere la coerenzadella Teoria non alla portata della Teoria stessa. Proponiamo di chiamareMetateorema dellindimostrabilit interna della coerenza tale conclusione meta-matematica del tutto generale.

Poi, il fatto che un enunciato di tal tipo sia indecidibile o sia un teoremadipende, naturalmente, dal Sistema dalla forma dellenunciato. Per le Teorie che

soddisfano le ipotesi del Primo, il Secondo Teorema dincompletezza assicura chedi norma tali enunciati sono indecidibili. Abbiamo scritto di norma perchpare che esistano tuttavia altri enunciati, formulanti anchessi la coerenza delSistema in altri peculiari modelli, che, invece, risultano essere teoremi dellaTeoria32. Come afferma lo stesso Lolli, sembra che neanche una dimostrazionechiude le discussioni33. Ma in ogni caso tale dibattito, come abbiamo concluso,non tange la validit del proposto Metateorema dellindimostrabilit internadella coerenza.

In conclusione, il Secondo Teorema dincompletezza individua altre speciedi enunciati essenzialmente indecidibili in ogni Teoria che soddisfa le ipotesi delPrimo. Mentre il Primo teorema dincompletezza determina solo lenunciato diGdel, il Secondo estende lindecidibilit ad una categoria assai pi ampia diproposizioni. Tuttavia, a parte questa radicale generalizzazione, non introduce

alcun concetto cardinale circa la coerenza del Sistema, come normalmente siritiene. Non lo farebbe neanche se fosse valido per ogni enunciato interpretabilecome questo Sistema coerente (cosa che, ribadiamo, sembra risultare falsa).

32G. Lolli, Da Euclide a Gdel, Il Mulino (2004), p. 140 e 142. A. Martini, Notazioni ordi-nali e progressioni transfinite di teorie, Tesi di Laurea, Universit di Pisa (2006), p. 11-15, sulWEB: http://etd.adm.unipi.it/theses/available/etd-11082006-161824/unrestricted/tesi.pdf.

33G. Lolli, op. cit., p. 142.

11


12/12

Infatti, in ogni caso, da esso non pu concludersi che il Sistema non pu di-

mostrare la propria coerenza: ci compete, invece, a un metateorema del tuttogenerale che non mai stato messo in evidenza, malgrado la sua immediatezzae indiscutibilit34.

Lerrore aggravato dalle frequentissime dimostrazioni intuitive, scorrette,del Secondo Teorema dincompletezza, del seguente tipo: Sia S un Sistema chesoddisfa le ipotesi del Primo Teorema dincompletezza e C un suo enunciato cheafferma la coerenza dello stesso S. Il Primo Teorema di incompletezza dimostrache se S coerente, lenunciato di Gdel, G, indecidibile. Perci, se C fossedimostrabile, potrebbe dedursi che G indecidibile e quindi indimostrabile. Mapoich G afferma di essere indimostrabile, ci significherebbe dimostrare G, ilche assurdo35. Il difetto manifesto: nel ragionamento si d a C e G unvalore semantico che giustificato solo supponendo che il Sistema ammetta unmodello con tali interpretazioni e quindi che sia gi coerente. In tale modello

fuori discussione che la verit di C implica la verit di G, ma limplicazionesintattica CG una questione affatto diversa. In generale, non c alcunassurdo conseguente alla possibilit che C sia un teorema perch ci, comeabbiamo gi osservato, non dimostrerebbe affatto che il Sistema coerente. Delresto, in caso di incoerenza, non si ha forse che ogni enunciato un teorema?In realt, dimostrare limplicazione sintattica CG tuttaltro che banale e,come segnalato, non vale in tutti i casi ma dipende dalla struttura sintatticadellenunciato C.

Lunico risultato di rilevante importanza circa la coerenza, dato dal Meta-teorema della sua indimostrabilit interna. E risaltiamo che la sua metadi-mostrazione, per il riferirsi a un Sistema classico qualsiasi, non pu che con-sistere in un ragionamento puramente metamatematico, cio informalizzabile;

come quello che si proposto.

-

Nel libro, gi citato, I Confini logici della Matematica, esponiamo altre revi-sioni e alcune proposte di rinnovamento della terminologia di questi argomenti,che immutata dai tempi di Hilbert.

34La coerenza di un Sistema pu essere dimostrata soltanto da un altro Sistema, esterno adesso. Per il quale, tuttavia, il problema della coerenza si riproporrebbe. Lultima conclusionedi coerenza, per uscire da tale circolo, devessere puramente metamatematica (ma, nella prat-ica, pu consistere semplicemente in un sensato convincimento, come in effetti succede conla Teoria assiomatica degli insiemi).

35Cos, per esempio, in: P. Odifreddi, Metamorfosi di un Teorema (1994), sul WEB:http://www.vialattea.net/odifreddi/godel.htm.

12

l'eredità di Gödel: rivisitando la Logica

Documents

Transcript of l'eredità di Gödel: rivisitando la Logica