6. Giovanni Salmeri, Piccola storia della Logica. Il Novecento (Parte II)

Giovanni Salmeri

Piccola

storia della logica

II. Il Novecento

4. La logica nel Novecento

4.1. Georg Cantor (1845-1918)

4.1.1. La teoria degli insiemi

L’opera di Georg Cantor si situa nel complesso di ricerche che vennero dedicate tra la fine dell’Ottocento e l’inizio del Novecento al problema della fon-dazione della matematica. Si trattava del tentativo di darle una base assoluta-mente solida, che non facesse ricorso né a considerazioni psicologiche, né a dati «intuitivi» come venivano presentati dai neokantiani. Questo nuovo punto di partenza è offerto secondo Cantor dalla teoria degli insiemi. Eccone i concetti fondamentali:

Con insieme (Menge) intendiamo ogni riunione I in un tutto di determinati e ben di-stinti oggetti i della nostra intuizione o del nostro pensiero (che vengono chiamati elementi di I). In simboli esprimiamo ciò così:

I = {i}. [...]

Ad ogni insieme I spetta una determinata potenza (Mächtigkeit), che chiamiamo an-che il suo numero cardinale (Kardinalzahl). Chiamiamo potenza o numero cardinale di I il con-cetto generale che con l’aiuto della nostra facoltà attiva di pensiero scaturisce dall’insieme I astraendo dalle fattezze dei suoi distinti elementi e dall’ordine nel quale essi sono dati. Il risul-tato di questo duplice atto di astrazione, il numero cardinale o la potenza di I, lo indichiamo con |I|.

Giacché da ogni singolo elemento i se si prescinde dalla sua fattezza, deriva un’unità, allora lo stesso numero cardinale |I| è un determinato insieme composto di semplici unità, che possiede esistenza nella nostra mente come immagine intellettuale o proiezione dell’in-sieme dato I.

Due insiemi I e J li chiamiamo equivalenti e indichiamo ciò con I ~ J oppure J ~ I

se è possibile porli secondo una legge in una relazione reciproca tale che ad ogni ele-mento di uno di essi corrisponda uno e solo un eleele-mento dell’altro.

[...]

È di significato fondamentale che due insiemi I e J hanno lo stesso numero cardinale se e solo se essi sono equivalenti:

da I ~ J segue |I| = |J|, e da |I| = |J| segue I ~ J.

L’equivalenza di insiemi costituisce dunque il necessario e infallibile criterio per l’ugua-glianza dei loro numeri cardinali (Contributi alla fondazione della teoria degli insiemi transfi-niti, 1897, § 1 [simbologia modificata]).

Così si è raggiunta secondo Cantor una soddisfacente caratterizzazione del numero: anzitutto del numero naturale, e tramite questo del numero relati-vo, razionale e infine reale (un passo quest’ultimo meno facile, che venne com-piuto da Cantor stesso). In questo modo l’aritmetica diventa una scienza edifica-ta sulla base della teoria degli insiemi, che pare rispondere a quelle doti di sem-plicità e solidità che dovrebbe richiedere una teoria di fondazione. La teoria de-gli insiemi mostra però un’ulteriore particolare duttilità: essa permette di considerare anche numeri che non avevano fino ad allora trovato spazio nella matematica: i numeri infiniti, o, come preferisce dire Cantor (per riservare la qualifica d’infinito a Dio solo) transfiniti:

Gli insiemi con numero cardinale finito si chiamano insiemi finiti; tutti gli altri li voglia-mo denominare insiemi transfiniti, e i numeri cardinali che spettano loro numeri cardinali transfiniti.

La totalità di tutti i numeri cardinali finiti n ci offre il più vicino esempio di insieme transfinito; il numero cardinale che gli spetta lo chiamiamo áleph zero, in simboli c₀; definia-mo dunque

c₀= |{n}|.

Che c₀sia un numero transfinito, che cioè non sia eguale a nessun numero finito m, deriva dal semplice dato di fatto che quando all’insieme {n} viene aggiunto un nuovo elemen-to e₀, l’insieme unione ({n}, e₀) è equivalente a quello originale {n}. Infatti è possibile pensare tra i due insiemi la relazione biunivoca secondo la quale all’elemento e₀del primo corrispon-de l’elemento 1 corrispon-del secondo, all’elemento n corrispon-del primo l’elemento n + 1 corrispon-dell’altro (Contributi alla fondazione della teoria degli insiemi transfiniti, § 6 [simbologia modificata]).

Dunque, la teoria degli insiemi rende inevitabile l’introduzione anche dell’infinito attuale, e non solo dell’infinito potenziale (considerato cioè come un limite irraggiungibile), cosa che Cantor discusse esplicitamente citando il pre-cedente di Leibniz. Si osservi anzi che come caratteristica definitoria viene scel-to proprio quell’aspetscel-to paradossale che fin da Arisscel-totele era stascel-to usascel-to come confutazione dell’esistenza dell’infinito attuale: l’infinito è ciò in cui una parte può essere equivalente al tutto. Questo è un chiaro indizio della portata che Cantor attribuiva all’idea secondo cui «l’essenza della matematica sta nella sua

libertà», libertà dunque anche di concepire e trattare oggetti apparentemente contraddittori.

4.1.2. La gerarchia dei transfiniti

È possibile, malgrado ciò che si è detto, parlare di differenti numeri tran-sfiniti? In un primo momento Cantor pensò di no: riuscì infatti a mostrare che l’insieme Ä dei numeri razionali ha anch’esso potenza c₀. Il risultato è molto si-gnificativo, perché Ä possiede una caratteristica peculiare, la densità, che lo di-stingue chiaramente daÁ (dati due numeri razionali q₁e q₃tali che q₁> q₃, esi-ste sempre un numero razionale q₂, per esempio la loro media aritmetica, tale che q₁> q₂> q₃). La dimostrazione dell’equivalenza diÁ e Ä è abbastanza sem-plice: si tratta solo di descrivere un metodo tramite cui ordinare tutti i numeri razionali, in modo che ad ognuno sia assegnato un posto univoco, e sia possibile così stabilire una corrispondenza con il numero naturale che indica quella deter-minata posizione. (Il nucleo del metodo trovato da Cantor consiste nell’elencare i numeri razionali, scritti sotto forma di frazione, ordinandoli per gruppi in cui sia uguale la somma del numeratore e del numeratore.)

Ma esistono insiemi con una potenza maggiore di c₀, in cui cioè gli infiniti elementi non possano essere messi in un qualsivoglia elenco ordinato che per-metta una relazione biunivoca con Á? Ciò è quanto Cantor alla fine dimostrò per l’insieme dei realiÅ. La dimostrazione più semplice e celebre è per assurdo: prima si ipotizza che i numeri reali (cioè costituiti da una sequenza di infinite ci-fre decimali a₁, a₂, ..., a_n, ...) possano essere messi in una sequenza ordinata (r1, r2, ..., rn, ...); poi si mostra come è possibile costruire un numero reale (r0) che non appartiene a tale sequenza:

Se r₁, r₂, ..., r_n, ... è una qualsiasi sequenza semplicemente infinita di elementi dell’in-siemeÅ, allora c’è sempre un elemento r₀diÅ che non coincide con alcun r_n.

Per dimostrarlo, sia r₁= (a_1,1, a_1,2, ..., a_1,n, ...), r₂= (a_2,1, a_2,2, ..., a_2,n, ...), ... r_m= (a_m,1, a_m,2, ..., a_m,n, ...), ... [...]

Siano r e s due caratteri mutuamente esclusivi [per esempio pari e dispari]. [...] Qui gli a_m,nsono in una determinata maniera r oppure s. Ci sia ora una sequenza b₁, b₂, ..., b_n, ..., definita cosicché il carattere r o s di b_nsia diverso da quello di a_n,n. Se dunque a_n,nè r, allora b_nè s, e se a_n,nè s, allora b_nè r.

r₀= (b₁, b₂, ..., b_n, ...)

si vede senz’altro che l’uguaglianza r₀= r_mnon può essere soddisfatta per nessun va-lore positivo di una riga m, perché altrimenti per il rispettivo m, per tutti i valori della riga, sa-rebbe

b_n= a_m,n

dunque anche in particolare b_m= a_m,m

il che è escluso per la definizione di b_n. Da questa conclusione segue imme-diatamente che la totalità di tutti gli elementi diÅ non può essere messa nella sequenza r₁, r₂, ..., r_n, .... altrimenti ci troveremmo di fronte alla contraddizione che r₀sarebbe e non sa-rebbe elemento diÅ (Su un problema elementare della teoria degli insiemi, 1890-1).

La tecnica usata in questa dimostrazione è il primo esempio del «metodo dia-gonale» che sarà ripetutamente usato nel campo della logica e della matematica. Il numero decisivo viene infatti ottenuto invertendo l’attributo r o s delle cifre che sono individuate da una linea «diagonale» tracciata dall’alto a sinistra nella sequenza dei numeri razionali. In termini più astratti, il nocciolo consiste nell’attribuire ad uno stes-so numero m una doppia funzione: individuare l’m-esimo elemento della sequenza e l’m-esima cifra di tale elemento.

L’insieme Å è particolarmente importante perché esso è un insieme «continuo»: intuitivamente, i punti di una retta possono essere messi in corri-spondenza biunivoca con l’insieme dei numeri reali. Si è dunque dimostrato che l’infinito della continuità non è l’infinito «numerabile», ovvero c₀, ma è di en-tità maggiore. Più precisamente, Cantor dimostrò che il cardinale dell’insieme Å può essere espresso come 2c0.

Ma esiste un numero transfinito maggiore della potenza di Á e minore della potenza di Å? oppure il secondo è l’immediato successore del primo? (Il concetto di «immediato successore di un numero transfinito» venne esattamen-te definito da Cantor, che mostrò in qual modo esso fosse concretamenesattamen-te co-struibile). Indicando la successione dei numeri transfiniti con indici, si tratta in-somma di appurare la giustezza dell’equivalenza c₁ = 2c0 (ipotesi del continuo)

o, in termini più ampi, c_n= 2cn-1 (ipotesi generalizzata del continuo). Cantor non

riuscì a dare risposta, e il problema rimase a lungo aperto. Esso venne risolto so-lo nel 1963 dall’americano Paul Cohen, che dimostrò che l’ipotesi del continuo è «indecidibile» nell’ambito delle normali teorie degli insiemi: essa non può es-sere cioè né dimostrata né confutata.

Tra gli ulteriori e sorprendenti risultati di Cantor è da citare la dimostrazione — semplicissima — che l’insieme Ån _{(con n naturale qualsiasi) è equivalente ad} Å. Ad esempio infatti la coppia di numeri reali a = (a₁, a₂, ..., a_n, ...) e b = (b₁, b₂, ..., b_n, ...) può essere posta in corrispondenza biunivoca con il numero reale c = (a1, b1, a2, b2, ...,

a_n, b_n, ...). In termini geometrici, ciò significa che una retta ha tanti punti quanti ne hanno un piano o lo spazio!

4.2. Gottlob Frege (1848-1925)

4.2.1. La fondazione della matematica

Attorno all’inizio del Novecento sono diversi gli studiosi che presentano contributi importanti alla fondazione della logica formale. Tra i più importanti, vanno citati almeno George Boole (1815-1864), Charles S. Peirce (1839-1914), Giuseppe Peano (1858-1932). Su tutti spicca però la personalità di Gottlob Fre-ge, che più degli altri elabora un sistema logico formalmente perfetto, espri-mendo con estrema chiarezza idee che altrove si possono trovare in modo anco-ra solo approssimativo. La sua opeanco-ra logica si inscrive — come in buona parte quella di Cantor — nella ricerca di una fondazione rigorosa della matematica. Ecco l’opinione di Frege al riguardo:

Nei miei Fondamenti dell’aritmetica ho tentato di rendere plausibile la tesi che l’arit-metica sia una branca della logica e che non abbia bisogno di prendere i fondamenti delle sue dimostrazioni né dall’esperienza né dall’intuizione. Nel presente volume questa tesi sarà confermata dal fatto che le leggi più semplici dei numeri possono essere dedotte con mezzi esclusivamente logici. Ciò dimostra, tuttavia, che si debbono porre sui procedimenti di dimo-strazione condizioni notevolmente più forti di quanto si sia soliti fare in aritmetica. Si deve delimitare preventivamente un insieme di pochi modi di inferenza e deduzione e non fare al-cun passo che non sia in accordo con uno di questi. Nel passaggio ad un nuovo giudizio, quin-di, non ci si deve accontentare, come hanno quasi sempre fatto finora i matematici, della cir-costanza che esso sia evidentemente corretto, ma lo si deve analizzare nei suoi passaggi logi-ci più semplilogi-ci, che spesso non sono affatto pochi (FL 38.23).

Tale punto di vista, che verrà chiamato «logicista», tende quindi a subor-dinare la matematica alla logica, cercando in quest’ultima la precisazione dei concetti e dei procedimenti fondamentali della prima. Dal punto di vista pratico

vale però per Frege in un certo senso un rapporto inverso: e cioè la logica deve ispirarsi, per perseguire un ideale di assoluto rigore e trasparenza, alla matema-tica, e più in particolare al metodo «assiomatico» della geometria di Euclide:

L’ideale di un metodo rigorosamente scientifico in matematica, quale io ho qui tenta-to di realizzare e che potrebbe giustamente essere intitenta-tolatenta-to ad Euclide, potrebbe venire se-condo me così delineato.

Che tutto venga dimostrato non si può certo pretendere, perché ciò è impossibile. Si può però esigere che tutte le proposizioni che si usano senza dimostrazione vengano espres-samente enunciate come tali, affinché si riconosca con chiarezza ove si fonda l’intero edificio. Bisogna quindi cercare di restringere il loro numero al minimo possibile, dimostrando tutto ciò che risulta possibile.

Si può esigere in secondo luogo — e in ciò io compio un passo ulteriore rispetto ad Euclide — che vengano espressamente elencati, prima di costruire l’edificio matematico, i metodi di deduzione e di dimostrazione che si applicheranno. In caso contrario, è impossibile garantire che la stessa esigenza precedente sia davvero soddisfatta. Io ritengo di avere so-stanzialmente raggiunto questo ideale (FL 38.24).

Il «passo ulteriore» che Frege cita va effettivamente ascritto tra i suoi maggiori contributi: la prima consapevole distinzione tra regole di deduzione e assiomi. Tale distinzione è parallela ad un’altra importantissima, che Frege ha ben chiara: quella tra il linguaggio simbolico che viene costruito (in questo caso il linguaggio matematico, del quale fanno parte gli assiomi), e il linguaggio che descrive il funzionamento del primo (successivamente chiamato metalinguag-gio, del quale fanno parte le regole).

Tali distinzioni (così come in generale un efficace modello di sistema logico) possono essere embrionalmente già trovate nella sillogistica aristotelica. Che in que-sto conteque-sto essa non venga citata è dovuto esclusivamente alla dimenticanza e all’in-comprensione in cui essa era caduta da secoli. Ciò tuttavia aumenta ancora il merito di Frege, che quasi partendo da zero riesce ad elaborare una logica che risulterà in ef-fetti molto più rigorosa e completa di quella di Aristotele.

Bisogna inoltre porre attenzione ad un altro requisito che Frege esige pur senza dichiararlo con tanta chiarezza: la preventiva ed esatta definizione dei simboli che compongono il linguaggio e delle regole che conducono ad espres-sioni sensate. È infatti impossibile contentarsi del linguaggio naturale, data la sua imperfezione ed ambiguità, ma bisogna elaborare un linguaggio completa-mente univoco e artificiale, in modo che i procedimenti dimostrativi si riducano di fatto ad un’elaborazione meccanica di simboli. Solo in questo modo il linguag-gio logico potrà ritenersi perfettamente «formalizzato». Frege crea perciò quel-la che denomina «ideografia» (Begriffsschrift: questo anche il titolo delquel-la sua opera fondamentale del 1879), un linguaggio cioè di tipo grafico che rappre-senta senza ambiguità i nessi concettuali. Nel seguito però tradurremo per

sem-plicità la logica di Frege nella notazione contemporanea, che deriva con piccole varianti da quella elaborata da Giuseppe Peano.

Per curiosità ecco un teorema nella notazione originaria di Frege, seguito dalla sua traduzione nella notazione di Peano:

([a(f(x,a)  F(a))  (f(x,y)  F(y)))  ([b(F(b) [a(f(b,a)  F(a)))  (F(x)  (f(x,y)  F(y))))

4.2.2. Funzione, senso, significato

La costruzione della logica da parte di Frege ha come presupposto l’ela-borazione di alcuni concetti di base, che vengono discussi con una precisione mai prima raggiunta. Il primo è il concetto di funzione, per il quale la spiegazio-ne di Frege è sostanzialmente rimasta immutata fino ad oggi:

L’essenza della funzione si esprime [...] nella corrispondenza che essa stabilisce fra i numeri i cui segni vengono sostituiti a x e i numeri che si ottengono di conseguenza come si-gnificati della nostra espressione. [...] L’essenza della funzione sta quindi in quella parte dell’espressione che rimane quando si prescinde da x. L’espressione di una funzione è biso-gnosa di completamento, o non saturata. La lettera x serve soltanto a tenere liberi i posti in cui si può sostituire un segno numerico che completi l’espressione, e permette quindi di rico-noscere lo speciale tipo di bisogno di completamento che costituisce il carattere peculiare della funzione descritto più sopra. Nel seguito, invece della lettera x sarà usata a questo sco-po la lettera ξ.

Questo tener liberi deve essere inteso nel senso che in tutti i posti in cui compare ξ si deve sostituire sempre lo stesso segno e mai segni diversi. Questi posti li chiamo posti di ar-gomento e ciò il cui segno (nome) occupa questi posti in un dato caso lo chiamo arar-gomento della funzione per questo caso. La funzione è completata dall’argomento; ciò che essa divie-ne dopo essere stata completata lo chiamo valore della funziodivie-ne corrispondente a quell’mento. Otteniamo quindi un nome del valore di una funzione corrispondente ad un argo-mento sostituendo nei posti di argoargo-mento del nome della funzione il nome dell’argoargo-mento.

Così, ad esempio, (2 + 3 · 12) · 1 è un nome del numero 5 composto mediante il nome di fun-zione (2 + 3 · ξ2) · ξ e 1 (FL 42.03).

Si noti in tale discussione il livello di astrazione che viene raggiunto nel ca-ratterizzare la funzione come una «corrispondenza»: essa non è un’espressione numerica, ma un rapporto tra due serie numeriche, rappresentanti rispettiva-mente l’argomento e il valore. Questo concetto di funzione può essere eviden-temente esteso considerando più argomenti («x + 2y» è per esempio una fun-zione a due argomenti). Più importante però e anzi fondamentale per la costru-zione della logica una seconda estensione, riguardante il tipo di valori della fun-zione:

Il dominio dei valori delle funzioni non può rimanere limitato ai numeri; se prendo in-fatti come successivi argomenti della funzione ξ2= 4 i numeri 0, 1, 2, 3, non ottengo come va-lori dei numeri. 02= 4, 12 = 4, 22= 4, 32= 4 sono espressioni di pensieri ora veri, ora falsi. Esprimo ciò dicendo che il valore della funzione ξ2= 4 è il valore di verità di ciò che è vero op-pure di ciò che è falso. Da ciò si vede che, scrivendo semplicemente un’equazione, io non tendo asserire nulla, ma soltanto designare un valore di verità, allo stesso modo che non in-tendo asserire nulla scrivendo 22, ma soltanto designare un numero. Dico: i nomi 22= 4 e 3 > 2 denotano lo stesso valore di verità, che chiamo per brevità il vero. Allo stesso modo, 32= 4 e 1 > 2 denotano lo stesso valore di verità, che chiamo per brevità il falso, così come il nome 22denota il numero 4. Dico perciò che il numero 4 è il significato di 4 e di 22, e che il vero è il significato di 3 > 2 (FL 42.13).

La «funzione» diventa così un concetto molto ampio e flessibile in grado di comprendere sotto di sé tutte le possibili corrispondenze univoche tra insie-mi di qualsiasi tipo. Particolare importanza rivestono le funzioni (dette «logi-che») che hanno sia il loro valore sia il loro argomento nei valori di verità. Consi-deriamo per esempio la proposizione complessa «3 > 2 e Roma si trova in Ita-lia»: essa significa il vero perché entrambe le sue componenti significano il vero. La funzione è quindi rappresentabile come «p e q», dove l’operatore (o «funto-re», o «connettivo») è la congiunzione «e». Per definire il comportamento di ta-li funzioni, il modo più sempta-lice consiste nel compilare le cosiddette «tavole di verità», cioè indicare quale valore esse assumono in corrispondenza di ognuna delle possibili combinazioni dei valori di verità degli argomenti. Ecco le tavole di verità delle funzioni logiche più usate, cioè la congiunzione («p e q»), la disgiun-zione («p o q»), l’implicadisgiun-zione («p implica q»), l’equivalenza («p equivale a q»), la negazione («non p»):

congiunzione disgiunzione implicazione equivalenza negaz. p ‚ q p ƒ q p  q p  q ¬ p v v v v v v v v v v v v f v v v f v f f v f f v f f v f f v v f f v f v v f f v f f f f f f f v f f v f

La teoria secondo cui le funzioni «saturate» non sono altro che «nomi» del valore assunto dalla funzione stessa può parere paradossale. Tale apparenza svanisce quando si introduca un’ulteriore distinzione:

Distinguo tuttavia il senso di un nome dal suo significato. 22e 2 + 2 non hanno lo stes-so senstes-so, così come non hanno lo stesstes-so senstes-so 22= 4 e 2 + 2 = 4. Il senso del nome di un valo-re di verità lo chiamo pensiero. Dico inoltvalo-re che un nome esprime il suo senso e denota il suo significato (FL 42.13).

Le nozioni di senso e significato (o, nella terminologia più comune, di in-tensione e esin-tensione) furono oggetto di ampia riflessione da parte di Frege (Sul senso e il significato, 1892), che pose così le basi di una dottrina importante non solo per la logica ma anche per l’analisi del linguaggio comune. In maniera pa-rallela agli esempi matematici, si deve per esempio dire che le due espressioni «la stella del mattino» e «la stella della sera» hanno lo stesso significato, perché denotano entrambi il pianeta Venere, ma esprimono sensi differenti, perché contengono in sé differenti caratterizzazioni concettuali. In generale, per Frege hanno significato eguale tutti i termini (semplici o complessi) che sostituiti l’un con l’altro non mutano il valore di verità di una proposizione.

Deviazioni da questa norma si trovano però nei casi di riferimento indiretto: le due proposizioni «Paolo sa che la stella del mattino è Venere» e «Paolo sa che la stella della sera è Venere» potrebbero essere infatti l’una vera e l’altra falsa. Ciò si spiega se-condo Frege ammettendo che in un contesto indiretto il significato di un termine è il senso che esso assume in un contesto diretto.

4.2.3. La logica proposizionale

Il primo livello della logica è individuato dalle espressioni che hanno per significato il vero o il falso, chiamate «proposizioni». Non sono però esse a costi-tuire oggetto diretto di studio: ciò significherebbe infatti per Frege ritenere che la logica si occupa solo di combinazioni meccaniche di simboli (i «nomi» del ve-ro e del falso, come visto). Bisogna invece ritenere oggetto della logica il senso di tali espressioni:

Ciò che viene dimostrato non è la proposizione (Satz), ma il pensiero (Gedanke). [...] Il pensiero non è percepibile dai sensi, ma ne diamo una rappresentazione udibile o visibile

nella proposizione. [...] Ciò implica, inoltre, che i pensieri non siano qualche cosa di soggetti-vo prodotto dalla nostra attività mentale. Infatti, il pensiero che troviamo nel teorema di Pita-gora è lo stessa per tutti e la sua verità è del tutto indipendente dal fatto che esso sia pensa-to o non pensapensa-to da quespensa-to o quell’uomo. Pensare non significa produrre pensieri, ma com-prenderli (FL 39.01).

Con tali precisazioni, Frege si avvicina ad una dottrina stoica: quella che distin-gueva l’ἀξίωμα (la proposizione) dal suo senso oggettivo e immateriale, il λεκτόν (il pensiero). E parimenti allineata con la posizione stoica è la concezione della logica co-me scienza dei «pensieri» e non delle «proposizioni». La terminologia contemporanea è però differente, e oggi s’intende con «enunciato» ciò che Frege diceva «proposizio-ne», e con «proposizione» ciò che Frege diceva «pensiero». Nel seguito parleremo quindi di «proposizione» dove Frege parlava di «pensiero».

In generale, lo scopo della logica è dimostrare «teoremi» logici, vale a di-re proposizioni che sono vedi-re in virtù della loro sola forma, o più esattamente funzioni logiche che hanno come valore il vero qualsiasi siano i loro argomenti. Per esempio, la proposizione «p ƒ ¬ p» è sempre vera (essa esprima l’antico principio logico del «terzo escluso»). Per dimostrare tali teoremi — come visto — Frege stabilisce un insieme di assiomi, che servano da punto di partenza indi-mostrato, e un gruppo di regole che specifichi in qual modo è possibile procede-re da un passaggio all’altro della dimostrazione. Assiomi e procede-regole possono esse-re scelti in modo diffeesse-rente in maniera da portaesse-re agli stessi risultati, a esse-rendeesse-re dimostrabili cioè tutte e sole le proposizioni che risultano sempre vere. Questi sono gli assiomi stabiliti originariamente da Frege:

1. p  (q  p) 2. (p  (q  r))  (q  (p  r)) 3. (p  (q  r))  ((p  q)  (p  r)) 4. (p  q)  (¬ q  ¬ p) 5. p  ¬ ¬ p 6. ¬ ¬ p  p

Come si nota, questi assiomi riguardano solo due funzioni logiche: l’implicazio-ne e la l’implicazio-negaziol’implicazio-ne. Le altre vengono infatti introdotte da Frege per definiziol’implicazio-ne a partire da queste, e non hanno bisogno quindi di assiomi propri. In particolare:

p ‚ q = ¬ (p  ¬ q)

p ƒ q = ¬ p  q

p  q = (p  q) ‚ (q  p)

Le regole necessarie sono soltanto due. La prima è la regola di separazio-ne: se si è affermata sia la proposizione α  β sia la proposizione α, si può affer-mare anche la proposizione β. Questa regola corrisponde all’antico «modus po-nendo ponens» degli Stoici. La seconda è la regola di sostituzione: se si è

affer-mata la proposizione α, si può affermare anche la proposizione che risulta dalla sostituzione in α di tutte le occorrenze di una variabile proposizionale p con una stessa espressione β (tale regola assicura per esempio che dall’assioma 5 si può banalmente ricavare «r  ¬ ¬ r»). In termini sintetici le due regole possono es-sere così espresse:

1. α  β, α L β 2. α L sost [α, p/β]

Diamo ora un semplice esempio di dimostrazione, indicando a destra la giustifi-cazione di ciascun passaggio:

1. (p  q)  (¬ q  ¬ p) ass 4 2. (p  ¬ q)  (¬¬ q  ¬ p) sost [1, q /¬ q] 3. (p  (q  r))  (q  (p  r)) ass 2 4. ((p ¬ q)  (¬¬ q  ¬ p))  (¬¬ q  ((p ¬ q)  ¬ p)) sost [3, p / (p ¬ q); q / ¬ ¬ q; r / ¬ p] 5. ¬¬ q  ((p ¬ q)  ¬ p) sep 2,4

Esiste anche un altro modo per provare la verità del teorema: sostituire alle va-riabili proposizionali tutte le possibili combinazioni di valori di verità, e controllare che la proposizione complessiva risulti sempre vera: questo sarà il sistema che proporrà tra gli altri Ludwig Wittgenstein (1889-1951). Tale sistema è indubbiamente più sem-plice e inoltre puramente meccanico; esso però diventa inutilizzabile appena la logica proposizionale è estesa in logica dei predicati, nella quale dunque un approccio assio-matico è indispensabile. Ecco comunque come la proposizione precedente verrebbe dimostrata con il sistema della tavola di verità:

3a 2a 1a 5 1b 3b 2b 1c 4 2c 1d ¬ ¬ q  ((p  ¬ q)  ¬ p) v f v v v f f v v f v f v f v v v v f f f v v f v v f v f v v v f f v f v f v v f v v f

Le colonne vengono compilate nell’ordine numerico indicato in alto: nelle co-lonne 1 si scrivono le possibili combinazioni di valori di verità (che in questo caso sono quattro, essendo due le variabili proposizionali coinvolte: a variabili uguali devono ov-viamente corrispondere valori uguali, donde l’identità delle colonne 1a e 1c, e di 1b e 1d); le colonne con i numeri successivi indicano il valore delle rispettive funzioni appli-cate ai loro argomenti nel corretto ordine di precedenza (2a è applicato a 1a; 2b a 1c; 2c a 1d; 3a a 2a; 3b a 1b e 2b; 4 a 3b e 2c); la colonna 5 il valore finale dell’espressio-ne (che è l’implicaziodell’espressio-ne applicata alle colondell’espressio-ne 3a e 4). Che in quest’ultima colonna sia presente solo il valore v mostra che la proposizione è un teorema, cioè che è vera indi-pendentemente dal valore di p e q.

4.2.4. La logica dei predicati

Un fondamentale ampliamento del calcolo proposizionale viene effettua-to quando le proposizioni vengono considerate nella loro struttura interna, cioè distinte in soggetto e predicato. In questo modo una proposizione come «il libro è bianco» non sarà più semplicemente simboleggiata da p, ma da B(l), in cui l è il soggetto e B il predicato. Ciò è particolarmente utile perché permette l’uso di variabili che riguardano individui (e non più, come prima, solo proposizioni). Si potrà dunque scrivere B(x): essa non è propriamente una proposizione (è im-possibile infatti dire se sia vera o falsa), ma una funzione o forma proposiziona-le, che diventa una proposizione appena il posto della variabile venga preso da un nome individuale. C’è però anche un altro modo per trasformare una forma proposizionale in proposizione, che è poi quello più interessante: quantificare la variabile, cioè asserire che la proprietà in questione vale per tutti i possibili sog-getti o almeno per uno. Così, la scrittura[x P(x) significa che qualsiasi soggetto gode della proprietà P (o in altre parole che una proposizione di forma P(x) è sempre vera), mentre la scrittura x P(x) significa che almeno un soggetto gode della stessa proprietà. La variabile x che cade sotto l’influenza di un quantifi-catore viene detta «vincolata», in contrapposizione alle altre (eventuali) variabi-li «variabi-libere».

La sillogistica aristotelica può essere considerata un sottoinsieme della logica dei predicati. Il sillogismo barbara per esempio risulta così formalizzato: ([x (P(x) 

Q(x)) ‚ [x (Q(x)  R(x)))  ([x (P(x)  R(x)), che letto dettagliatamente è: «se per

qualsiasi cosa l’essere P implica l’essere Q e per qualsiasi cosa l’essere Q implica l’es-sere R, allora per qualsiasi cosa l’esl’es-sere P implica l’esl’es-sere R». D’altra parte va detto che lo sviluppo della logica dei predicati, piuttosto che «riscoprire» la sillogistica di Ari-stotele, ha mostrato proprio che essa riguardava solo alcuni casi particolari, e che dun-que era ingiustificato il posto di assoluta supremazia che le era stato riconosciuto per quasi due millenni.

L’ampliamento viene effettuato da Frege aggiungendo tre regole alle due già stabilite. La prima è la regola di degeneralizzazione: essa stabilisce che se si è affermata la proposizione [x α(x) si può ovviamente affermare anche α(a), in-tendendosi con «a» un termine individuale qualsiasi. La seconda è la regola di generalizzazione: se si è affermato α  β(a), è possibile affermare anche α  [x β(x), a condizione che il termine individuale «a» non compaia in α (o se vi compaia sia vincolato da un quantificatore). Il senso di questa regola e il motivo della restrizione possono essere così spiegati: se si è dimostrato qualcosa per un termine individuale «a caso», la dimostrazione vale in universale; il passaggio all’universale non vale però se su tale termine individuale vengono fatte parti-colari assunzioni. La terza regola è una regola di sostituzione analoga a quella prima vista, questa volta valida però per i termini individuali: se si è affermata la

proposizione α, si può affermare anche la proposizione che si ottiene sostituen-do in α tutte le occorrenze di un termine individuale x con un altro termine y, purché y non occorra «vincolato» in α (ciò porterebbe infatti alla confusione de-gli ambiti di differenti quantificazioni). In sintesi:

3. [x α(x) L α(a)

4. α  β(a) L α  [x β(a/x)purché a non occorra libera in α

5. α(x) L sost [α(x), x/y] purché y non occorra vincolata in α

Queste regole riguardano soltanto il quantificatore universale. Il quantificatore esistenziale viene introdotto da Frege per definizione, analogamente a ciò che avveni-va per le funzioni logiche diverse dall’implicazione:

x P(x) ¬ [x ¬ P(x)

Per quanto riguarda il compito di fondazione della matematica, la logica dei predicati è importante soprattutto perché permette una definizione del con-cetto di numero. Il primo passo consiste nell’applicare anche al predicato la di-stinzione tra senso e significato. Il senso (o intensione) è ovviamente costituito dal concetto che viene pensato in ciascun predicato. Il significato (o estensione) coincide invece con la classe degli oggetti che godono della proprietà espressa dal predicato. Il significato del predicato «essere pari» sarà per esempio la clas-se dei numeri pari {0, 2, 3, 4...}. In questo modo la logica dei predicati diventa una traduzione «intensionale» della logica delle classi. Per ammettere questa equivalenza basta ammettere il cosiddetto «assioma di comprensione»: che cioè ogni proprietà individui effettivamente la classe di tutti e soli gli elementi che godono di quella certa proprietà. Il numero naturale potrà a questo punto essere definito — in maniera analoga alla «potenza» in Cantor — come il con-cetto che può essere attribuito a tutti i predicati che denotano una classe «equi-numerosa». Con ciò, anche al concetto fondamentale della matematica viene assicurata una base puramente logica.

L’illusione però di aver sostanzialmente terminato il compito di fondazio-ne della matematica durò poco. Nel 1902 il giovafondazio-ne logico Bertrand Russel co-municò infatti a Frege di aver scoperto nel suo sistema un’«antinomia» (nota appunto come «antinomia di Russel»), cioè una contraddizione dedotta dalle premesse, che mostrava come la logica di Frege era in realtà difettosa. Eccola nelle parole di Russel:

Sia w la classe di tutte le classi che non sono membri di sé stesse. Allora, qualunque sia la classe x, «x è un w» è equivalente a «x non è un x». Quindi, dando a x il valore w, «w è un w» è quivalente a «w non è un w» (FL 48.11).

In termini più semplici: la classe di tutte le classi che non hanno sé stesse come elemento, ha o no sé stessa come elemento? È chiaro che qualsiasi rispo-sta porta ad una contraddizione. Ciò mostrava che l’«assioma di comprensio-ne», che svolgeva un ruolo essenziale di collegamento tra logica e matematica, non poteva in realtà essere accettato. Frege riconobbe che ciò significava il falli-mento del suo programma di fondazione, e in generale di tutti quelli che faceva-no uso di una qualche teoria degli insiemi («Ad ufaceva-no scrittore di scienza — scris-se — ben poco può giungere più sgradito del fatto che, dopo aver completato un lavoro, venga scosso uno dei fondamenti della sua costruzione»). Ciò non to-glieva però evidentemente nulla al valore della logica di Frege in sé, che è rima-sta per il Novecento un punto di riferimento fondamentale.

La scoperta dell’antinomia di Russel non significava neanche che la teoria degli insiemi fosse da abbandonare in quanto irrimediabilmente contraddittoria. Era possi-bile infatti aggiungere condizioni aggiuntive che evitassero l’antinomia. Una prima so-luzione venne elaborata dallo stesso Russel con la cosiddetta «teoria dei tipi»: secon-do essa l’espressione «appartenere a sé stessi» è scorretta, in quanto ogni classe dev’essere di «tipo» differente dai suoi elementi. Tale correzione venne integrata nei

Principia Mathematica (1910-13), l’opera di Russel (in collaborazione con Alfred North

Whitehead) che, ispirata da vicino a Frege, più di ogni altra si avvicinò all’ideale di un’esposizione globale dei fondamenti della matematica dal punto di vista logicista. Altre soluzioni si diressero invece verso l’«indebolimento» dell’assioma di comprensio-ne (in questa direziocomprensio-ne andò la successiva più importante sistemaziocomprensio-ne della teoria degli insiemi, effettuata da Ernst Zermelo nel 1908). In questo modo però le pretese «fondamenta» della matematica parevano diventare meno semplici e intuitive della matematica stessa, e dunque quasi vanificate nel loro ruolo. Ma il seguito degli svilup-pi del problema dei fondamenti porterà alla luce difficoltà ancora svilup-più gravi, come si vedrà.

4.3. David Hilbert (1862-1943)

4.3.1. L’assiomatica

David Hilbert rappresenta, assieme a Frege, l’altro maggiore protagonista della rifondazione della matematica e della logica all’inizio del Novecento. La prima fondamentale opera di Hilbert è costituita dai Fondamenti della geome-tria (1900). In essa egli intraprende il compito di riesporre la geomegeome-tria euclidea dandole perfetto rigore. Tale compito era urgente per almeno due fatti nuovi: anzitutto l’elaborazione, avvenuta verso la fine dell’Ottocento, delle «geometrie non euclidee», che pur non accettando il quinto postulato («Per un punto passa una ed una sola parallela ad una retta data») risultavano cionondimeno perfettamente coerenti; poi la nascita della logica matematica. Entrambe que-ste circostanze attiravano l’attenzione sulla necessità di precisare nel modo mi-gliore gli assiomi di una certa costruzione logica. In particolare, Hilbert mise in evidenza tre caratteristiche cui questi dovevano soddisfare. La prima e più im-portante è la coerenza o non contraddittorietà: dagli assiomi dev’essere impos-sibile dedurre due teoremi contraddittori. La seconda era la completezza: gli as-siomi devono permettere di dimostrare tutte le proposizioni vere e respingere tutte quelle false (in altre parole, non devono esistere proposizioni «indecidibi-li»). La terza era l’indipendenza: gli assiomi devono essere ciascuno indipenden-te da tutti gli altri, o altrimenti detto nessun assioma deve poindipenden-ter essere dimo-strato tramite gli altri. Obbedendo a questi criteri, Hilbert introdusse venti assio-mi (contro i cinque originari di Euclide), formulando anche quelle proprietà che parrebbero «evidenti» (per esempio: «Di tre punti qualsiasi di una retta ce n’è al massimo uno che giace fra gli altri due»). In realtà, per Hilbert l’«evidenza» non deve giocare alcun ruolo nella definizione degli assiomi: essi vanno conside-rati il punto di partenza per una costruzione puramente formale, indipendente-mente dal fatto che essa abbia poi un qualche rapporto con la «realtà». Il che si-gnifica anche che è privo di senso richiedere che gli assiomi siano «veri» in

sen-so realistico: la loro verità consiste nella capacità di individuare oggetti ideali, e ciò è assicurato dalla coerenza.

Tali stesse idee vengono applicate da Hilbert anche alla matematica e al problema della sua fondazione, venendo a definire quella posizione chiamata «formalismo»:

Tutto ciò che costituisce la matematica nel senso comunemente accettato del termi-ne vietermi-ne formalizzato rigorosamente, cosicché la matematica propriamente detta, o matema-tica nel senso più ristretto, diventa un insieme di formule. [...]

Oltre alla matematica propriamente detta, formalizzata in questo modo, c’è, per così dire, una nuova matematica, una meta-matematica, che serve a fondare la prima su basi si-cure. [...] Nella meta-matematica si opera con le dimostrazioni della matematica propriamen-te detta, che costituiscono esse spropriamen-tesse l’oggetto delle inferenze che propriamen-tengono conto dell’argo-mento su cui vertono. In questo modo, lo sviluppo della scienza complessiva della matemati-ca viene ottenuto mediante un continuo smatemati-cambio, che è di due tipi: da una parte, l’ac-quisizione di nuove formule derivabili dagli assiomi mediante l’inferenza formale, dall’altra l’aggiunta di nuovi assiomi parallelamente alla dimostrazione della loro non-contradditto-rietà [...].

Gli assiomi e le proposizioni derivabili, cioè le formule, che nascono in questo proces-so di scambio proces-sono rappresentazioni dei pensieri che costituiscono i procedimenti usuali del-la matematica quali sono stati finora concepiti, ma non esono essi stessi verità in senso asso-luto. Sono piuttosto le informazioni fornite dalla mia teoria della dimostrazione riguardo alla derivabilità e alla non contraddittorietà che devono essere considerate verità assolute (FL 38.28).

Anche Hilbert, così come Frege, vede quindi uno stretto rapporto tra logi-ca e matematilogi-ca; esso viene individuato però nel fatto che entrambe deducono o derivano, a partire da un insieme di assiomi, delle «formule», cioè sequenze di simboli, indipendentemente dall’interpretazione che se ne possa dare. Spetta poi ad una «meta-matematica» giustificare la coerenza del sistema.

4.3.2. Gli assiomi di Peano

L’approccio assiomatico al problema della fondazione si mostrò par-ticolarmente promettente dopo la scoperta dell’antinomia di Russel, che aveva mostrato i gravi pericoli di un approccio «intuitivo» alla fondazione della mate-matica. Fu allora che Hilbert sostenne la necessità di ricorrere ad un vero e pro-prio sistema di assiomi da cui dedurre tutte le proposizioni matematiche. In ciò egli trovò un fondamentale lavoro preparatorio nel lavoro di Giuseppe Peano, il quale aveva costruito un sistema di questo tipo. La definizione di numero (natu-rale) che viene presupposta è la seguente: «zero è un numero; se x è un nume-ro, è un numero anche il successore di x». Si tratta di una definizione puramen-te formalistica, che indica quale successioni di simboli vadano considerapuramen-te nu-meri senza proporre alcuna loro identificazione intuitiva. Gli assiomi di Peano possono essere così formalizzati (indicando con «´» la funzione di «successo-re»):

1. [x (¬ x´ = 0)

2. [x[y (x´ = y´  x = y)

3. α(0) ‚ [x (α(x)  α(x´))  [x α(x) 4. [x[y (x + 0 = x ‚ x + y´ = (x + y)´) 5. [x[y (x × 0 = 0 ‚ x × y´ = (x × y) + x)

In termini discorsivi gli assiomi affermano: 1. non esiste alcun numero na-turale il cui successore sia 0; 2. due numeri naturali il cui successore è eguale sono uguali; 3. se 0 gode di una certa proprietà e si può dimostrare che se un numero naturale gode di quella proprietà ne gode anche il successore, allora tutti i numeri naturali godono di quella proprietà (questo è l’importantissimo «principio di induzione matematica»); 4. la somma di x con y è eguale a x se y è 0, altrimenti è eguale al successore della somma di x e del predecessore di y; 5. il prodotto di x per y è eguale a 0 se y è 0, altrimenti è eguale alla somma di x con il prodotto di x per il predecessore di y. Benché paiano estremamente

pove-ri, tali assiomi consentono effettivamente di derivare tutti i teoremi dell’aritme-tica, e dunque di assicurare un sostegno all’intera matematica.

Si notino negli assiomi di Peano le definizioni della somma e del prodotto; esse possono sembrare scorrette, in quanto citano al loro interno proprio l’operazione che definiscono. Ma in realtà la circolarità è evitata dal fatto che esse «convergono» verso il caso più elementare (in cui un argomento è 0) il cui valore viene direttamente indi-cato. Si tratta quindi di definizioni «ricorsive», o anche «induttive» in quanto sfruttano un principio analogo a quello del principio d’induzione. Proprio tale tipo di definizione avrà un’importanza centrale, come si vedrà, nello sviluppo della teoria della computa-bilità. Peraltro, definizioni ricorsive di funzioni sono lecite in quasi tutti i moderni lin-guaggi di programmazione per calcolatori (per esempio Pascal, C, Lisp). Ecco come come possono essere rappresentati i due assiomi di Peano in Pascal, sotto forma di funzioni:

function sum (x, y: integer): integer; begin

if y = 0 then sum := x

else sum := succ (sum (x, pred (y))) end;

function prod (x, y: integer): integer; begin

if y = 0 then prod := 0

else prod := sum (prod (x, pred (y)), x) end;

Il sistema assiomatico della matematica sarà in conclusione costituito dal-la logica dei predicati «arricchita» con gli assiomi di Peano. Ma — come visto — per Hilbert è un compito fondamentale dimostrare (in ambito meta-matemati-co) la coerenza e la completezza di tale sistema di assiomi: solo in questo modo sarà scongiurato il pericolo di incontrare in futuro un’antinomia simile a quella che ha fatto franare il programma di Frege, e solo in questo modo agli assiomi poteva essere riconosciuta una loro «verità». L’antinomia di Russel, inoltre, avendo messo in questione anche la teoria degli insiemi di Cantor, esigeva se-condo Hilbert che tale dimostrazione non facesse alcun ricorso ai numeri «tran-sfiniti» che di lì provenivano; nella terminologia di Hilbert, la dimostrazione do-veva essere effettuata con mezzi esclusivamente «finitisti». In un certo senso, bisognava effettuare la dimostrazione restando all’interno dell’aritmetica. Que-sto costituisce il nocciolo del celebre «programma di Hilbert».

Si noti che la coerenza e la completezza sono facili da dimostrare quando è in questione la sola logica proposizionale, meno facili ma comunque appurate quando è in questione la logica dei predicati. Il programma di Hilbert si presentava dunque co-me estremaco-mente ragionevole.

4.4. Kurt Gödel (1906-1978)

4.4.1. Gödelizzazione e diagonalizzazione

È verso il programma di Hilbert che si dirige il rivoluzionario lavoro di Kurt Gödel, «Sulle proposizioni formalmente indecidibili dei Principia mathematica e di sistemi affini, I» (1931). I teoremi dimostrati da Gödel si basano su due sco-perte preliminari, estremamente importanti quanto al loro significato logico. La prima scoperta è questa: ogni proposizione matematica può essere rappresen-tata da un numero, e quindi ogni affermazione meta-matematica su proposizio-ni può essere tradotta in un’affermazione matematica su numeri:

Le formule di un sistema formale [...] sono successioni materiali finite di simboli pri-mitivi (variabili, costanti logiche e parentesi o segni di interpunzione), ed è facile specificare esattamente quali successioni di simboli primitivi sono formule dotate di significato e quali non lo sono. Analogamente, dal punto di vista formale le dimostrazioni sono soltanto succes-sioni finite di formule (con proprietà definite che si possono enunciare). Dal punto di vista della meta-matematica è naturalmente indifferente quali oggetti siano scelti come simboli primitivi, e noi optiamo per l’uso di numeri naturali [Cioè, associamo a ogni simbolo primiti-vo un numero naturale in modo biuniprimiti-voco]. Di conseguenza, una formula diventa una sione finita di numeri naturali e una dimostrazione diventa una successione finita di succes-sioni finite di numeri naturali. I concetti (teoremi) meta-matematici diventano così concetti (teoremi) sui numeri naturali o su loro successioni, e sono quindi esprimibili (almeno in par-te) coi simboli dello stesso sistema dei Principia Mathematica [In altre parole, la procedura descritta fornisce un modello isomorfo del sistema PM nel dominio dell’aritmetica e tutte le considerazioni meta-matematiche possono essere trattate altrettanto bene in questo model-lo isomorfo] (Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I).

Ciò equivale a dire che la matematica, una volta che siano state stabilite le opportune convenzioni, è in grado di «parlare di sé stessa». Ciò non vìola af-fatto la distinzione di principio tra linguaggio e meta-linguaggio, in quanto il pro-cedimento individuato da Gödel crea all’interno del linguaggio oggetto un

mo-dello del metalinguaggio. In questo modo sarà per esempio possibile definire una proprietà matematica con argomento numerico che indichi se il suo argo-mento è un numero che rappresenta o no una formula dotata di significato per la matematica stessa. Il procedimento tramite cui le proposizioni vengono tra-dotte in numeri venne successivamente chiamata, in ricordo del suo ideatore, «gödelizzazione», e i numeri associati vengono detti «gödeliani».

Non c’è bisogno di dare esempi concreti della gödelizzazione, un procedimento che può essere condotto in innumerevoli modi differenti e che oltretutto è con-cettualmente analogo ai familiari procedimenti di codifica degli attuali calcolatori (si pensi per esempio ai codici ASCII o Unicode). È opportuno piuttosto attirare l’attenzio-ne su una caratteristica particolare della gödelizzaziol’attenzio-ne: in essa gli elementi di un cer-to sotcer-toinsieme dei simboli matematici (i numeri, e probabilmente — secondo la par-ticolare codifica scelta — neanche tutti) vengono posti in relazione biunivoca con gli elementi dell’intero insieme delle espressioni matematiche, compresi i numeri stessi. Questa — come già visto — è la caratteristica propria degli insiemi infiniti.

La seconda scoperta è costituita dalla dimostrazione di quello che è chia-mato «teorema di diagonalizzazione» (in quanto sfrutta un metodo simile al procedimento diagonale di Cantor). Esso afferma che, per ogni proprietà defini-bile nel linguaggio, è possidefini-bile costruire una proposizione che afferma che il suo proprio gödeliano gode di quella proprietà. Insomma, non soltanto la matemati-ca è in grado di parlare di sé stessa in generale, ma esistono anche proposizioni che parlano proprio di sé stesse.

Vediamo come ciò è possibile, con un procedimento lievemente differente da quello originario di Gödel. È anzitutto necessario definire una funzione numerica sost. Essa ha come argomenti tre numeri e come valore il gödeliano della proposizione ot-tenuta sostituendo, nella proposizione rappresentata dal primo argomento, la variabi-le rappresentata dal secondo numero con il terzo numero (indichiamo con {φ} il gödeliano della formula φ). Ad esempio: sost ({x > y}, {x}, 15) = {15 > y}.

Ora, data una qualsiasi proprietà propr, consideriamo anzitutto la seguente for-mula α: propr (sost (x, {x}, x)). Poi sostituiamovi la variabile x con il gödeliano {α}. Otte-niamo così la proposizione β: propr (sost ({α}, {x}, {α})). (Si osservi che {x} non è una variabile, ma un numero, e quindi non va sostituito.) Ora, qual è il gödeliano {β}? Ba-sta controllare la definizione della funzione sost per comprendere che esso è uguale a

sost ({α}, {x}, {α}). La proposizione β è stata infatti ottenuta proprio sostituendo in α le

occorrenze di x con {α}. Dunque, la proposizione β afferma propr ({β}).

4.4.2. I due teoremi di limitazione

Poste le due premesse, possiamo ora comprendere il meccanismo dei due teoremi di Gödel. Anzitutto si può mostrare facilmente che è possibile

defi-nire una proprietà dim ({α}) che indica se α è dimostrabile. Ma se è definibile dim lo è ovviamente anche ¬ dim, e per il teorema di diagonalizzazione sarà possibile costruire una proposizione γ che afferma ¬ dim ({γ}) (detto in termini semplici, una proposizione che afferma: «io sono indimostrabile»). Ecco dunque il punto cruciale:

Dimostriamo ora che l’enunciato γ è indecidibile in PM. Infatti, supponendo che l’enunciato γ sia dimostrabile, esso sarebbe anche vero, cioè, per quel che è stato detto [...] varrebbe ¬ dim ({γ}), contro l’ipotesi. Se però, al contrario, la negazione di γ fosse dimostrabi-le, allora [...] si avrebbe dim ({γ}). Quindi, sia γ sia la sua negazione sarebbero dimostrabili, il che è di nuovo impossibile. [...]

Dall’osservazione che γ afferma la propria indimostrabilità segue immediatamente che γ è vera, perché γ è effettivamente indimostrabile (in quanto indecidibile). L’enunciato che afferma che essa è indecidibile nel sistema PM è stato così deciso mediante considerazio-ni meta-matematiche (Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I [simbologia modificata]).

In questo modo si è mostrato che esiste almeno una proposizione vera che tuttavia è indimostrabile: dunque il sistema della matematica è incompleto (tutto ciò, ovviamente, sotto l’ipotesi che la matematica sia non-contradditto-ria). Con il suo primo teorema Gödel dimostrò così che la nozione di verità an-dava distinta da quella di dimostrabilità nel caso della matematica e di tutti i si-stemi formali di una simile «ricchezza»:

Il metodo di dimostrazione ora esposto può essere applicato ad ogni sistema formale che, in primo luogo, disponga, una volta interpretato, di mezzi espressivi sufficienti a definire i concetti che compaiono nelle precedenti considerazioni (in particolare, quello di «formula dimostrabile») e in cui, in secondo luogo, ogni formula dimostrabile, una volta interpretata, sia vera.

Ciò significa anche che la matematica è essenzialmente incompleta: l’in-completezza non deriva infatti da una «povertà» dei suoi assiomi, ma al con-trario dalla sua «ricchezza» espressiva: un sistema è necessariamente incomple-to appena esso (come abbiamo visincomple-to nei due passi preliminari) diventa in grado di parlare di sé stesso. Per questo motivo, Gödel stesso riconobbe che il suo teo-rema poteva essere considerato una versione raffinata dell’antica «antinomia del mentitore».

Il secondo teorema di Gödel riguarda la coerenza della matematica. Il pri-mo passo consiste nel definire una proposizione coer che afferma la coerenza (ovvero non contraddittorietà) della matematica. Ora, il ragionamento che pri-ma abbiamo condotto per dimostrare l’indimostrabilità di γ può essere «tradot-to» all’interno della matematica con questa implicazione: coer  γ. Si era infatti concluso che se la matematica è coerente allora γ è indimostrabile, e γ afferma appunto la propria indimostrabilità. Ma la verità di questa implicazione ci

as-sicura che, se coer fosse dimostrabile, allora lo sarebbe anche γ. Ma ciò è contro l’ipotesi dell’indimostrabilità di γ e, in ultima analisi, della coerenza della mate-matica. Bisogna quindi concludere che, se la matematica è coerente, allora la sua coerenza è indimostrabile all’interno della matematica stessa. Il programma di Hilbert si mostrava quindi definitivamente illusorio.

Bisogna fare attenzione all’ultima precisazione: all’interno della matematica

stessa. Nulla infatti vieta che tale coerenza venga dimostrata al suo esterno, cioè

fa-cendo uso di ipotesi aggiuntive che non fanno parte della matematica così com’è fino a quel momento definita. Questo è in effetti proprio ciò che venne fatto nel 1936 da Gerhardt Gentzen (1909-1945) usando ipotesi aggiuntive tratte dalla teoria degli insie-mi di Zermelo e Fraenkel, e dunque non più con i soli metodi «finitisti» che auspicava Hilbert. Si noti però che, in maniera analoga a quanto abbiamo detto riguardo al pri-mo teorema, non si può credere di aggirare del tutto il problema aggiungendo ulterio-ri ipotesi agli assiomi della matematica: la stessa difficoltà si ulterio-ripresenta infatti ad un li-vello più alto, perché è impossibile dimostrare la coerenza di questo insieme «arricchi-to» di assiomi senza ammetterne ancora altri, e così all’infinito. I teoremi di Gödel so-no stati per questo spesso invocati per sostenere la superiorità del pensiero umaso-no sui procedimenti di calcolo formale. Questa interpretazione pare in realtà arbitraria. I teoremi di Gödel pongono infatti un limite di natura oggettiva: essi cioè dimostrano che — raggiunto un certo livello di ricchezza espressiva — è oggettivamente impossi-bile costruire un sistema deduttivo in grado di giustificare sé stesso, ovvero tale che in esso non esistano funzioni non computabili; e ciò non per limiti connessi a colui (o a ciò) che calcola, ma per la contraddizione che altrimenti ne nascerebbe. Purtroppo (o fortunatamente) le domande sull’uomo non possono ricevere risposta da un teorema logico, neppure se il suo risultato è negativo come nel caso di quelli di Gödel.

4.5. Alan M. Turing (1912-1954)

4.5.1. Computabilità e tesi di Church

La dimostrazione del teorema di incompletezza di Gödel, tutt’altro che frenare la ricerca logico-matematica, le diede un nuovo impulso. Una volta in-fatti accertato che la nozione di verità andava distinta da quella di deducibilità — o che in altre parole esistevano funzioni non calcolabili — si apriva il proble-ma di definire in proble-maniera esatta il campo delle funzioni calcolabili o computabi-li, il cui valore cioè per ogni argomento o n-upla di argomenti fosse univocamen-te deunivocamen-terminabile con una sequenza di passi finita. Gli studi si concentrarono in-torno ad un’idea di base già intuìta negli anni ’20: definire la computabilità sulla base della ricorsività, cioè del criterio che già negli assiomi di Peano era stato usato per definire le operazioni di somma e prodotto. In poche parole, si dichia-ravano cioè computabili tutte (e sole) le funzioni che fossero definibili stabilen-do una condizione di partenza e una condizione induttiva. Tale definizione attra-versò differenti tappe. In un primo momento si giunse alla definizione della co-siddetta ricorsività primitiva; quando però nel 1928 il matematico Wilhelm Ac-kermann scoprì una funzione evidentemente calcolabile ma non ricorsiva primi-tiva, il concetto di ricorsività venne esteso, ad opera di diversi matematici tra i quali Kurt Gödel e Alonzo Church, con la formulazione della cosiddetta ri-corsività generale (formulata in tempi successivi in alcune varianti tra loro equi-valenti, note come ε-ricorsività, λ-ricorsività, μ-ricorsività, σ-ricorsività).

I particolari delle definizioni di ricorsività sono notevolmente complessi; intuiti-vamente e in termini informatici moderni, le funzioni ricorsive primitive sono quelle calcolabili da un programma per calcolatore che dispone solo di cicli finiti (del tipo «for i := 1 to n do ...», con n predeterminato all’esterno del ciclo); le funzioni ricorsive generali sono quelle calcolabili con l’ausilio di cicli indefiniti (del tipo «while ... do ...», con condizione di uscita determinata all’interno del ciclo). Questa caratterizzazione della ricorsività generale si avvicina particolarmente alla nozione di μ-ricorsività, in cui μ è appunto l’operatore che indica la ricerca indefinita di un valore minimo. Si noti che

un ciclo «indefinito» è cosa ben diversa da un ciclo «infinito»: affermare l’esigenza di quest’ultimo equivarrebbe infatti a dichiarare una funzione non computabile.

Diversamente da quanto era avvenuto con la ricorsività primitiva, nei con-fronti della ricorsività generale non si riuscì malgrado gli sforzi a scoprire alcun controesempio: nessuna funzione cioè che rispondesse ai criteri intuitivi di com-putabilità senza però poter essere definita in maniera ricorsiva generale. Nel 1936 Alonzo Church formulò quindi la congettura nota appunto come «tesi di Church»: la classe delle funzioni intuitivamente computabili coincide con la clas-se delle funzioni ricorsive generali. È chiaro che tale congettura è per principio non passibile di dimostrazione giacché uno dei suoi concetti, quello di «compu-tabilità», rimane formulato ad un livello solo intuitivo.

4.5.2. Il modello di Turing e Post

Nello stesso anno avvenne però un ulteriore passo decisivo: Alan Turing ed Emil Post, indipendentemente l’uno dall’altro ma in termini pressoché identi-ci, effettuarono un approccio del tutto differente al problema della computabi-lità. Piuttosto che cercare modelli matematici, essi elaborarono un modello meccanico che rispondesse al concetto intuitivo di procedimento di calcolo. In-tuitivamente, colui che calcola (per esempio una comune somma) ha a sua di-sposizione della carta, in quantità indefinita; usa un certo alfabeto di simboli (le dieci cifre e qualche segno aggiuntivo); può spostare il suo occhio in un punto qualsiasi, leggere e scrivere i simboli; segue nelle sue operazioni un insieme uni-voco e finito di istruzioni (che dicono appunto «come si fa» a sommare due numeri); termina l’operazione quando ha scritto sulla carta il risultato. Turing e Post cercarono dunque di semplificare il più possibile queste condizioni, crean-do un modello puramente meccanico di calcolo, tramite il quale sarebbe stato più semplice studiare il concetto di computabilità. Tale modello è da allora noto per lo più come «macchina di Turing». Seguiamo però la più semplice de-scrizione di Post:

Lo spazio dei simboli deve essere costituito da una sequenza di celle infinita da ambo le parti, ordinalmente simile alla serie degli interi ..., -3, -2, -1, 0, 1, 2, 3, ... . Il risolutore del problema o esecutore deve muoversi e lavorare in questo spazio dei simboli, avendo la capa-cità di trovarsi ed operare in una sola cella per volta. Inoltre, a prescindere dalla presenza dell’esecutore, una cella deve potersi trovare solo in una di due possibili condizioni, cioè es-sere vuota o non contrassegnata oppure avere un singolo contrassegno, per esempio un trat-to verticale. Una cella deve essere individuata e chiamata puntrat-to di partenza.

Assumiamo, inoltre, che un problema specifico debba essere assegnato in forma sim-bolica mediante un numero finito di celle contrassegnate da un tratto. Similmente, la rispo-sta deve essere fornita mediante un’opportuna configurazione di celle contrassegnate. Per essere precisi, la risposta deve essere la configurazione di celle contrassegnate lasciata alla

Si assuma che l’esecutore sia in grado di effettuare le seguenti azioni primitive: (a) contrassegnare la cella in cui si trova (supposta vuota),

(b) cancellare il contrassegno nella cella in cui si trova (supposta contrassegnata), (c) spostarsi nella cella alla sua destra,

(d) spostarsi nella cella alla sua sinistra,

(e) determinare se la cella in cui trova è o no contrassegnata.

L’insieme di istruzioni che, va notato, è lo stesso per tutti i problemi specifici e perciò corrisponde al problema generale, deve essere della seguente forma. Deve essere intestato:

Parti dal punto di partenza ed esegui l’istruzione 1. Deve quindi essere costituito da un numero finito di istruzioni che debbono essere numerate 1, 2, 3, ..., n. L’i-esima istruzione deve avere una delle seguenti forme:

(α) esegui l’operazione Oi [ = (a), (b), (c) o (d)] e passa all’istruzione j,

(β) esegui l’operazione (e) e, a seconda che la risposta sia sì o no passa all’istruzione j' o j",

(γ) fèrmati.

Chiaramente occorre solo un’istruzione di tipo (γ). Notiamo anche che lo stato dello spazio dei simboli influenza direttamente il processo solo tramite istruzioni di tipo (β) (Finite combinatory processes. Formulation 1).

Si noti che in tale modello viene supposto un alfabeto composto di soli due simboli (casella vuota o contrassegnata). È evidente infatti che qualsiasi al-tro insieme di simboli più ricco può sempre essere «tradotto» in questo alfabe-to minimo; tutti i numeri naturali per esempio possono essere scritti in sistema binario anziché decimale. Si osservi inoltre l’importante distinzione tra proble-ma generale e probleproble-ma specifico: probleproble-ma generale è per esempio «somproble-mare due numeri», problema specifico è «sommare 5 e 7»: il problema generale è in-dividuato da un certo insieme di istruzioni (il procedimento è uguale per tutte le somme), il problema specifico è contraddistinto da un diverso stato di partenza dello spazio dei simboli (come sarebbe un foglio di carta su cui fosse scritto «5 + 7 =»). Ma a quale scopo elaborare tale modello meccanico? La spiegazione di Post è molto chiara:

Lo scrivente si aspetta che la presente formulazione si riveli equivalente alla ricorsi-vità nel senso dello sviluppo di Gödel e Church. La sua intenzione, comunque, è non solo di presentare un sistema di una certa potenza logica, ma anche, nel suo campo ristretto, di fe-deltà psicologica. In quest’ultimo senso sono contemplate formulazioni sempre più estese.

D’altra parte, sarebbe nostra intenzione mostrare che tutte queste sono logicamente ricon-ducibili alla formulazione 1.

Noi offriamo questa conclusione, al momento attuale, come un’ipotesi di lavoro. E per noi questo è il significato dell’identificazione di Church tra la calcolabilità effettiva e la ri-corsività. [...]

Il successo del precedente programma dovrebbe, per noi, cambiare questa ipotesi non tanto in una definizione o in un assioma, quanto in una legge naturale. Solo così, sembra a chi scrive, il teorema di Gödel sull’incompletezza della logica simbolica di un certo tipo ge-nerale e i risultati di Church sull’irresolubilità ricorsiva di certi problemi possono essere tra-sformati in conclusioni riguardanti tutta la logica simbolica e tutti i metodi di risolubilità (Fini-te combinatory processes. Formulation 1).

L’anno successivo lo stesso Turing dimostrò appunto ciò che anche Post si aspettava: la computabilità nel senso del loro modello meccanico (detta anche τ-ricorsività) equivale alle definizioni di ricorsività generale. Ciò in effetti non si-gnifica ancora aver dimostrato la tesi di Church, ma perlomeno averla resa alta-mente plausibile: per contestarla bisognerebbe infatti anzitutto immaginare una «maniera» di calcolo effettivo che sia essenzialmente differente e più am-pio di quello schematicamente rappresentato dalla macchina di Post-Turing: il che — come osserva Post — è almeno «psicologicamente» difficile (e di fatto non è a tutt’oggi né avvenuto né ritenuto probabile). D’altra parte, la dimostra-zione dell’equivalenza tra τ-ricorsività e ricorsività generale ha qualcosa di sor-prendente: essa infatti significa che qualsiasi problema risolubile (sotto l’ipotesi di Church) è risolubile da una macchina tanto semplice, purché ovviamente provvista di un insieme di istruzioni adeguato, che potrà essere anche estrema-mente complesso (anzi, in generale è intuitivo che la complessità delle istruzioni cresce contemporaneamente alla semplicità di una macchina). Ciò si può espri-mere anche dicendo che la macchina di Post-Turing è in grado di «simulare» qualsiasi altra macchina calcolatrice in senso lato.

4.5.3. Informatica e pensiero artificiale

Con gli studi di Church, Turing e Post furono in effetti inconsapevolmente gettate le basi dell’informatica (o computer science). Con le loro macchine infat-ti Post e Turing prepararono il modello al quale negli anni ’40 ci si ispirò per co-struire i primi calcolatori numerici (o «digitali», dall’inglese digit, «cifra»). Non si trattava delle prime macchine calcolatrici in assoluto: già in secoli precedenti erano stati progettati strumenti di questo tipo, a volte anche notevolmente raf-finati e complessi (da ricordare le calcolatrici di Pascal [1642], Leibniz [1673] e soprattutto la «macchina analitica» di Charles Babbage [1822], quest’ultima co-sì complessa che solo nel 1991 potè essere costruita in base ai progetti originali, con una spesa di 300 000 sterline, e trovata perfettamente funzionante). Si trat-tava però sempre di calcolatori destinati a risolvere un’unica classe di problemi

(tipicamente, certe operazioni matematiche). Fu solo con il modello teorico di Turing e Post che si comprese la possibilità di costruire un calcolatore «universa-le», estremamente semplice nella sua architettura ma versatile al punto da po-ter effettuare qualsiasi calcolo (o più genericamente qualsiasi elaborazione di dati) il cui algoritmo sia stato correttamente individuato e codificato. L’essen-ziale infatti sta nel distinguere la macchina in sé dalle istruzioni che essa esegue e dai dati sui quali opera.

È evidente che il modello di Post e Turing lascia la più ampia libertà nelle moda-lità di realizzazione fisica di una macchina calcolatrice: qualsiasi risultato che sia «iso-morfo» al modello originario è infatti accettabile. In effetti, molto differenti sono le tecnologie finora usate: il primo calcolatore (Mark I, terminato nel 1943) era di tipo elettromeccanico; successivamente si passò a circuiti elettronici a valvole («prima ge-nerazione», 1946-54); quindi le valvole furono sostituite da transistor («seconda generazione», 1955-64); i transistor furono quindi riuniti nei circuiti integrati («terza generazione», 1965-74, «quarta generazione», 1975-1980, «quinta generazione», dal 1981). Tutte queste differenti realizzazioni hanno incrementato la velocità di calcolo, l’ampiezza della memoria, la facilità di programmazione e dunque la capacità pratica di calcolo: ma dal punto di vista teorico sono equivalenti all’originario modello di Post e Turing.

In comune tra le diverse generazioni di calcolatori è inoltre la scelta del sistema binario (suggerito già da Post), di per sé per nulla obbligata, ma che rende molto più semplice non solo la costruzione delle macchine, ma anche il loro progetto: in questo modo infatti i circuiti di base della macchina (a prescindere dalle particolarità dei cir-cuiti sequenziali, ovvero contenenti elementi di memoria) sono isomorfi alle operazio-ni della logica proposizionale, che opera anch’essa su due soli valori (vero e falso). Nel-la moderna «elettronica digitale» (in cui cioè sono previsti due soli possibili segnali, «alto» e «basso») il funzionamento dei componenti di base («porte logiche») è in ef-fetti descritto da tavole di verità e portano gli stessi nomi (in inglese) delle funzioni lo-giche corrispondenti. Una porta AND è per esempio un circuito che ha un’uscita «al-ta» solo se entrambi i suoi ingressi sono «alti». Ecco le porte praticamente usate con i loro simboli (i tratti a sinistra equivalgono agli argomenti della funzione, il tratto a de-stra al suo valore, in modo che lo schema di circuiti complessi ricorda un po’ la