• Precedente • Successivo • Indice •
Capitolo 2
COMPLETEZZA1. UN DIBATTITO A TRE VOCI: GÖDEL, HILBERT, BROUWER
Il risultato di completezza semantica per il calcolo proposizionale dei Principia era stato ottenuto da Paul Bernays nel 1926 (Axiomatische Untersuchung des Aussagen-Kalkuls der "Principia Mathematica"). Ma con le parole di David Hilbert e Wilhelm Ackermann: "se il sistema di assiomi sia completo, nel senso che da esso possano essere derivate tutte le formule logiche che sono corrette in ogni dominio di individui è un problema ancora non risolto"1. In questo senso intesa, la completezza del calcolo dei predicati del primo ordine è al centro della tesi di dottorato di Kurt Gödel (1929) e del successivo articolo Die Vollständigkeit der Axiome des logischen Funktionenkalküls (1930). Ma la definizione di completezza, che ogni formula universalmente valida, esprimibile nel calcolo dei predicati del primo ordine sia dimostrabile in esso, viene reimpostata in modo equivalente: ogni sistema coerente di formule del calcolo dei predicati del primo ordine ha un modello. Questa impostazione del problema rappresenta, come scrive Gödel nella dissertazione del 1929, "un completamento teoretico del metodo usuale di dimostrare la coerenza"2, vale a dire si deve o esibire un modello o produrre una contraddizione. L'alternativa esclusiva che così si genera sembrerebbe legittimare l'equiparazione tra coerenza e esistenza da Hilbert indicata. Perciò nell'introduzione alla tesi, Gödel presenta le difficoltà che questa concezione provocherebbe. Gödel inizia con il ricordare come per Brouwer la coerenza di un sistema di assiomi non implichi di necessità la costruibilità di un modello. L'ordine genetico andrebbe per Brouwer semmai invertito; la costruzione sta prima, è ragione della coerenza, poiché con le parole di Arend Heyting: "la matematica intuizionista tratta di costruzioni mentali. Ogni proposizione matematica ha la forma 'una costruzione A con tali e tali proprietà può venire eseguita'"3, esistere matematicamente significa essere intuitivamente costruito. In questo contesto il principio logico del terzo escluso non viene accolto. La sua accettazione comporterebbe infatti che, per un qualunque enunciato matematico sia sempre possibile o costruire la sua dimostrazione o costruire la dimostrazione della sua negazione4. Il principio del terzo escluso si identifica quindi per Brouwer con l'assioma della risolubilità di ogni problema matematico. Ma la decidibilità, in tal modo pre-assunta all'effettiva costruzione, comporta che l'oggetto matematico raggiunga una qualche autonomia dal pensiero, se la sua legge intrinseca, obiettiva è quella della coerenza. Analogamente Gödel sottolinea che se l'esistenza dei concetti introdotti da un sistema di assiomi può essere definita solo per la via della coerenza del sistema stesso: "si presuppone l'assioma della risolubilità di ogni problema matematico". O, più esattamente, anticipando il risultato del 1931, si presuppone "che non si possa dimostrare la non risolubilità di alcun problema matematico"5. Nell'introduzione Gödel considera, a titolo esemplificativo, un sistema di assiomi per i numeri reali. Se, rispetto a tale sistema, si dimostrasse la indecidibilità di un qualunque problema, data la definizione di esistenza mediante coerenza, seguirebbero due modelli non isomorfi per quel sistema. Così, posta quale proposizione indecidibile A, potremmo assumere quale nuovo assioma tanto A che non A, ottenendo M modello del sistema più A e M* modello del sistema più non A. Dove A esisterebbe come vera nel primo caso, e come falsa nel secondo.
Ma, Gödel prosegue, è dimostrabile l'isomorfismo di due modelli qualunque per i numeri reali. Come osservano Burton Dreben e Jean van Heijenoort, nel commento agli scritti di Gödel sulla completezza, si sottace qui la distinzione tra logica del primo e del secondo ordine, che modificherebbe i termini della discussione, fondandosi l'argomento dell'isomorfismo di due modelli qualunque per i numeri reali sull'interpretazione standard della logica del secondo ordine. Ma tolto l'esempio specifico, è chiaro che la stessa costruibilità dei modelli non isomorfi incrina l'equiparazione tra esistenza e coerenza. Mentre l'effettiva costruzione di una proposizione aritmetica indecidibile, quale sarà prodotta nella relazione del 1931, la rende insostenibile.2. DIMOSTRAZIONE
Intanto Gödel prende le distanze anche da Brouwer: "Non possiamo escludere una dimostrazione della non risolubilità di un problema, se si osserva che qui si tratta soltanto della non risolubilità mediante certi metodi di inferenza formali precisamente specificati"6. La precisazione sui metodi di inferenza si applica proprio al risultato di completezza: "mentre in quel che segue viene appunto dimostrato che ogni espressione universalmente valida si può dedurre con regole di inferenza del tutto determinate, concretamente enumerate"7. Il chiarimento è doveroso, perché la formulazione del problema della completezza: "si deve poter dimostrare la coerenza tramite un modello, o si deve produrre una contraddizione"8 sembra in sintonia con il dettame intuizionista all'alternativa dimostrabile-refutabile con un controesempio. Ma "l'esistenza di tale alternativa non viene dimostrata in senso intuizionista"9. In particolare accogliere l'interpretazione intuizionista del principio del terzo escluso, porterebbe a intendere il risultato di completezza come attestazione della decidibilità del calcolo dei predicati(la cui indecidibilità sarà stabilita da Alonzo Church in A note on the Entscheidungsproblem del 1936).
Ora non c'è motivo di attenersi ai vincoli intuizionisti: l'impiego essenziale del principio del terzo escluso varrà per totalità infinite, dove il concetto di totalità infinita sfugge per primo al costruibile. Di questo dibattito nella stesura del 1930 resta appena una traccia. Quando si opera in modo puramente formale "sorge immediatamente il problema se il sistema di assiomi e dei principi di inferenza inizialmente postulati è completo, vale a dire, se esso è effettivamente sufficiente per la derivazione di ogni proposizione logico-matematica o se, forse, è concepibile che esistano proposizioni vere (che addirittura possono essere dimostrabili mediante altri principi) che non possono essere derivate nel sistema considerato"10.
Nel veloce accenno, la non escludibile indecidibilità di un problema si concreta come indecidibilità di una proposizione che si sa vera. Come riferirà Hao Wang, Gödel non credeva che esistessero problemi di teoria dei numeri realmente indecidibili per la mente umana, o la ragione sarebbe irrazionale nel porre a se stessa interrogazioni di cui non sapesse trovare risposta11. Che quest'ultima affermazione non possa venire accolta, lo attesterebbero per prime quelle parti di matematica a fondo sviluppate; qui leggi, procedimenti e strategie di risoluzione manifestano un'elevata bellezza, e con la perfetta eleganza della loro efficacia sembrano giustificare la fiducia di Hilbert nel potere del puro pensiero di fronte alle questioni ancora insolute. Ma il nodo è quello della formalizzazione. L'incompletezza intrinseca a tutti i sistemi formali per la matematica segnerebbe un'insufficienza degli assunti finitari; sembrerebbe quindi necessario, stando a quanto emergerà dalla più celebre memoria del 1931, l'uso di assunti che sostanzialmente trascendano l'aritmetica.
Ma per il calcolo dei predicati del primo ordine si può provare il seguente risultato di completezza semantica: ogni formula universalmente valida del calcolo funzionale ristretto è dimostrabile (teorema I dello scritto del 1930). Gödel lo esplicita nella forma equivalente: ogni formula del calcolo funzionale ristretto o è refutabile o è soddisfacibile (e precisamente nel dominio numerabile di individui) (teorema II, dove "A è refutabile" significa " ~A è dimostrabile"). In questo modo si può includere, come caso particolare, il teorema di Löwenheim-Skolem. Nel 1915 Leopold Löwenheim (Über Möglichkeiten im Relativkalkül) aveva provato che se una formula chiusa del primo ordine è soddisfacibile, è soddisfacibile in un dominio infinito numerabile. Perfezionando il metodo già introdotto da Löwenheim, nel 1920 Thoralf Skolem mostrava come associare, in modo effettivo, a ogni formula quantificazionale Q una formula Q* in forma normale prenessa, tale che Q è soddisfacibile se e solo se Q* lo è (Q* si dice in forma prenessa se è del tipo PSM, con P stringa di r (r ³ 1) quantificatori universali, S stringa di s (s ³ 0) quantificatori esistenziali, M matrice priva di quantificatori; Q* si dice inoltre in forma normale prenessa se, per P e/o S, con r e/o s > 0, le x1,...,xn variabili quantificate risultano tra di loro distinte e tutte occorrono nella matrice; con r e/o s = 0, nella matrice non occorrono variabili). Calcando sulla nozione insiemistica di soddisfacibilità, Skolem dà una generalizzazione del teorema di Löwenheim: se un insieme numerabile di formule quantificazionali è soddisfacibile, è soddisfacibile in un dominio infinito numerabile. Ma l'alternativa di Skolem si configura tra soddisfacibile o non soddisfacibile; non ancora tra soddisfacibile o refutabile. Nemmeno Jacques Herbrand (Recherches sur la théorie de la démonstration 1930), introducendo con la versione finitista del teorema di Skolem lo sviluppo congiuntivo di una formula, compie il passo che lo porterebbe alla completezza. Da un lato egli si astiene dal trarre la conclusione di Skolem, in favore della soddisfacibilità in un dominio numerabile, in quanto ciò coinvolgerebbe una nozione non finitistica. D'altro lato fa il suo ingresso la refutabilità: se la formula in questione non è dimostrabile (soddisfacibile), è espressamente refutabile.
Anche Gödel lavora con procedura affine a quella di Skolem. Ma, definita (P)A una formula del tipo PSM e (Pn)An come chiusura esistenziale di An, aggiunge il nesso: per ogni n è dimostrabile (P)A ® (Pn)An. Quindi se per qualche n An non è soddisfacibile, allora (P)A è refutabile.
L'esito raggiunto si estende alla logica dei predicati con identità (teorema VIII) e a insiemi numerabili di formule del primo ordine: ogni insieme infinito numerabile di formule del calcolo funzionale ristretto o è soddisfacibile (cioè tutte le formule del sistema sono contemporaneamente soddisfacibili) oppure esso possiede un sottoinsieme finito il cui prodotto logico è refutabile (teorema IX).3. CONSEGUENZE
La completezza comporta l'equivalenza tra validità e dimostrabilità per la logica del primo ordine. Questo sembrerebbe convalidare che la correttezza di una teoria sia rimpiazzabile dalla condizione di coerenza formale, sostenendosi quindi la tesi hilbertiana della non contraddittorietà quale prova di esistenza. Sarebbe perciò perseguibile l'eliminazione delle nozioni infinitarie. Poiché "'universalmente valido' si riferisce alla totalità più che numerabile delle funzioni, mentre 'dimostrabile' presuppone soltanto la totalità numerabile delle figure di dimostrazione" la completezza comporta "per il problema della decisione, una riduzione del più che numerabile al numerabile"12. Tuttavia la sostituibilità piena del requisito di correttezza con quello puramente formale del dimostrabile smentirebbe quanto dichiarato nello scritto del 1929, che non si possa presupporre l'assioma della risolubilità di ogni problema matematico. Ogni teorema coerente attesterebbe della veridicità dell'esistenza di ciò che definisce, e in sé conterrebbe assicurazione della propria categoricità.
Anche tralasciando queste considerazioni, già dal teorema di Löwenheim-Skolem discende la non categoricità delle teorie del primo ordine con modelli infiniti. Rispetto alla teoria degli insiemi, nasce il paradosso di Skolem (1922). Si può provare, nel sistema di assiomi Zermelo-Fraenkel (ZF), l'esistenza di un insieme più che numerabile, cioè non equipotente all'insieme dei numeri naturali. Ma se ZF, formulata nell'ambito del calcolo dei predicati del primo ordine, è coerente, per il teorema di Löwenheim-Skolem gli assiomi devono risultare tutti veri rispetto a un universo di insiemi numerabile13 . Skolem ne concluse l'impossibilità di caratterizzare al primo ordine per via assiomatica strutture insiemistiche. Quindi o si sale a linguaggi di ordine superiore al primo, o proprietà insiemistiche, quale quella della cardinalità, restano inassolute14 , così che un insieme appaia ora numerabile in un modello, ora non numerabile in un altro.
Affini considerazioni si traggono dal teorema di compattezza, che nello scritto del 1930 Gödel immette a seguito di IX: affinché un insieme numerabile di formule sia soddisfacibile è necessario e sufficiente che ogni sottoinsieme finito sia soddisfacibile (teorema X). L'applicazione del risultato di compattezza al più che numerabile, a opera di Anatolii Ivanovich Maltsev (1936), garantisce alla base l'esistenza di modelli non standard. Ma con Leon Henkin (1949) si osserva che per l'aritmetica essa deriva già dal teorema X di Gödel. Sia infatti D un insieme di assiomi per i numeri naturali, e i una costante che non occorra in D, diversa da ogni numerale di n, con n numero naturale. Dato il nuovo insieme D + i, ogni suo sottoinsieme finito è soddisfacibile, se si interpreti i su un qualunque numero naturale che non compaia nel sottoinsieme considerato. Per la compattezza tutto l'insieme avrà un modello. Poiché tale modello contiene almeno un elemento, i, che non coincide con alcun numero naturale, esso è non standard15.NOTE
1. La citazione, tratta da Hilbert, D., Ackermann, W., Grundzüge der theoretischen Logik, Springer, Berlin, 1928, 2° ed. 1938, è riprodotta da Burton Dreben e Jean van Heijenoort, nella "Nota introduttiva a 1929, 1930, 1930a" (le date indicano i tre scritti pubblicati in vita da Gödel sulla completezza), in Gödel, K. Collected Works; Vol. I, Publications 1929-1936, a cura di S. Feferman, J. W. Dawson Jr., S. C. Kleene, G. H. Moore, R. M. Solovay, J. van Heijenoort, Oxford University Press, New York - Clarendon Press, Oxford, 1986; trad. it. Gödel, K., Opere; Volume I: 1929-1936, a cura di E. Ballo, S. Bozzi, G. Lolli, C. Mangione, Boringhieri, Torino, 1999, pp. 47-62, cit. da p. 51.
2. Gödel, K., "Über die Vollständigkeit des Logikkalküls", (dissertazione di dottorato, Università di Vienna, 1929); trad. it. di C. Mangione, "Sulla completezza del calcolo della logica", in Gödel, K., Opere; Vol. I, op. cit., pp. 63-82, cit. da p. 63.
3. Heyting, A., voce "Intuizionismo", in Enciclopedia del Novecento, Roma, Istituto dell'Enciclopedia Italiana Treccani, 1984, vol. III, pp. 846-855.
4. Così Brouwer: "Se ad ogni applicazione linguistica del principio del terzo escluso ad un'argomentazione matematica dovesse corrispondere una costruzione della matematica intuizionista, ciò significherebbe che ogni assunzione della matematica intuizionista (...) può essere giudicata, cioè dimostrata o ridotta all'assurdo". Brouwer, L.E.I., "Historical Background, Principles and Methods of Intuitionism", in South African Journal of Science, vol. 49 (1952), pp. 139-143; trad. it. "Fondamenti storici, principi e metodi dell'intuizionismo", in Cellucci, C.(a cura di), La filosofia della matematica, op. cit., pp. 223-231, citazione da p.227. Nello stesso volume, si legga anche, alle pp. 249-267, il saggio di Heyting, A.,"L'intuizionismo in matematica", trad. it. di "Intuitionism in Mathematics", in Philosophy in the Mid-Century, a cura di R. Klibansky, La Nuova Italia, Firenze, 1958, pp. 101-115. "Si può affermare A Ú ~A solo dopo che si è dimostrata A o si è dedotta una contraddizione dall'ipotesi che si sia dimostrata A. Ciò significa che il principio del terzo escluso non è valido. (Potrebbe darsi infatti che non si sia dimostrata A né si sia dedotta una contraddizione dall'ipotesi che si sia dimostrata A.)" Cit. da p. 257-258. La fiducia nella validità universale del principio del terzo escluso contrasta con l'esistenza delle 'proprietà sfuggenti', caratterizzate, secondo Brouwer, dalle seguenti condizioni: a) per ogni dato n, si può decidere se n possiede o meno la proprietà; b) non si conosce alcun metodo per calcolare un numero n che goda della proprietà; c) non si può respingere l'asserzione che almeno un numero naturale n abbia la proprietà. Le proprietà sfuggenti sono quindi indecidibili.
5.Gödel, K., "Sulla completezza del calcolo della logica", op. cit., p.64
6. Gödel, K., ibidem, p.64.
7. Gödel, K., ibidem, p. 65.
8. Gödel, K., ibidem, p. 63.
9.Gödel, K., ibidem, p. 63.
10.Gödel, K., "Die Vollständigkeit der Axiome des logischen Funktionenkalküls", Monatshefte für Mathematik und Physik, 37 (1930), pp. 349-360; trad. it. di C. Mangione, "La completezza degli assiomi del calcolo funzionale logico", in Gödel, K., Opere; Vol. I, op. cit., pp. 83-93, cit. da p. 83.
11.Wang, H., From mathematics to philosophy, Routledge & Kegan, London, 1974; trad. it. di A. Giacomelli, Dalla matematica alla filosofia, Boringhieri, Torino, 1984, pp. 341 e seg. L'opinione di Gödel è pronunciata nel contesto del rapporto tra procedimenti meccanici e mentali, rispetto al quale, nel bilancio di una discussione sull'eventuale superiorità delle menti umane sulle macchine, Gödel conclude con una alternativa aperta: o i procedimenti mentali sorpassano infinitamente il potere di ogni macchina finita, o esistono problemi matematici del tutto indecidibili per la mente umana. Gödel respinge quindi questo secondo ramo dell'alternativa, e ciò appare in singolare sintonia con le dichiarazioni di Hilbert: "il nostro intelletto è capace di dare una risposta a tutte le questioni da esso stesso poste" ("Problemi matematici", op. cit., p. 155). Tuttavia l'affermazione di Hilbert resta agganciata all'assioma della risolubilità di ogni problema matematico nel quadro del programma formalista strictu sensu inteso.
12. Gödel, K., "La completezza degli assiomi del calcolo funzionale logico", op. cit., p. 90.
13. Il paradosso è enunciato da Thoralf Skolem in "Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre", Wissenschaftliche Vorträge gehalten auf dem Fünften Kongress der Skandinavischen Mathematiker in Helsingfors vom 4. bis 7. Juli 1922, Helsingfors 1923, pp. 217-232; trad. it. "Osservazioni sulla fondazione assiomatica della teoria degli insiemi", in Cellucci, C. (a cura di), Il paradiso di Cantor, op. cit., pp. 159-174. Dagli assiomi di ZF, si desume l'esistenza di un insieme infinito x e del suo insieme potenza y, che cioè contiene come elementi tutti i sottoinsiemi di x. Per il teorema di Cantor, y ha cardinalità maggiore di x; quindi y non è numerabile. Ma l'applicazione a ZF della versione generalizzata del teorema di Löwenheim comporta che ZF abbia un modello numerabile, che contiene tanto x quanto y come suoi elementi.
14."L'assiomatizzazione della teoria degli insiemi conduce alla relatività della nozione di insieme, e tale relatività è inseparabilmente legata ad ogni assiomatizzazione totale." Se "gli insiemi non sono altro che oggetti connessi tra loro mediante certe relazioni espresse dagli assiomi", non è più contraddittorio che "un insieme M del dominio B sia non numerabile nel senso dell'assiomatizzazione; ciò significa semplicemente che in B non esiste un'applicazione biunivoca di F M su Z0 (la successione numerica di Zermelo). Esiste tuttavia la possibilità di enumerare tutti gli oggetti di B, e quindi anche gli elementi di M, mediante gli interi positivi". Cioè y (qui M) è, in quanto elemento del modello (B), numerabile, mentre la corrispondenza biunivoca tra x e y non è, a sua volta, membro del modello. (Skolem, T., idib., pp. 166-167.) Dunque non avrebbe senso parlare di diversi gradi di infinità in modo assoluto: potremmo ottenere un insieme assolutamente non numerabile, solo se disponessimo di un numero infinito, assolutamente non numerabile, di assiomi, o di un unico assioma atto a fornirci un numero infinito assolutamente non numerabile di enunciati numerici. Questo però renderebbe circolare il processo di introduzione delle infinitą superiori.
15 Il primo modello non standard per l'aritmetica fu costruito da Skolem nel 1933, senza ricorrere al teorema di compattezza. Per N insieme dei numeri naturali e R struttura data da (N,+,×, <), esiste una struttura R* non isomorfa a R, con gli stessi enunciati veri (del primo ordine) di R. Né Skolem né Gödel si avvidero della diretta discendenza di questo risultato dalla compattezza. In "Besprechung von Thoralf Skolem, 'Über die Unmöglichkeit einer vollständigen Charakterisierung der Zahlenreihe mittels eines endlichen Axiomensystems'" (1934), Gödel sottolinea piuttosto il nesso tra le proprie ricerche del 1931 e l'esistenza di un modello non standard R* per l'aritmetica, in cui sia falso qualche enunciato vero in R. (Si veda la trad. it. di G. Lolli, "Recensione di Skolem 1933a", in Gödel, K., Opere; Vol. I, op. cit., p. 283.)
• Precedente • Successivo • Indice •
©2002 Optima