Che cos’è la logica matematica

Che cosa studia la logica

Ogni conoscenza che non si ottiene per osservazione diretta si ottiene ragionando: da certe affermazioni che si accettano si passa a un’altra che ne segue. In geometria, chi sa che gli angoli di un triangolo sommano due retti conclude che nessun triangolo ha due angoli ottusi; in medicina, chi sa che una certa malattia produce febbre, e che la persona visitata non ne ha, esclude quella malattia. La logica è la disciplina che studia quando quel passaggio è legittimo, e la logica matematica è quella che lo studia con i metodi della matematica: definendo con esattezza i suoi oggetti, che sono linguaggi, formule e deduzioni, e dimostrando teoremi su di essi.

Per enunciare con precisione che cosa studia, conviene fissare prima il vocabolario. Una proposizione è una frase dichiarativa di cui ha senso dire che è vera o che è falsa: «$7$ è un numero primo» è una proposizione vera; «ogni numero pari è maggiore di $5$», una proposizione falsa. Non sono invece proposizioni le domande («che ore sono?»), gli ordini («chiudi la porta») né le espressioni con variabili libere, come «$x$ è pari», il cui valore dipende da ciò che $x$ designa.

Un argomento è una lista di proposizioni, le premesse, insieme a un’altra proposizione, la conclusione, che si presenta come loro conseguenza. Le premesse possono essere proposizioni qualsiasi: vere, false, note o semplici supposizioni; l’unica cosa che le distingue è il posto che occupano nell’argomento. Scriveremo gli argomenti con le premesse su righe successive e la conclusione preceduta da «dunque»:

La logica non è una teoria della verità

Se è così, la logica non ha il compito di accertare se le premesse di un argomento siano vere. Che $28$ sia multiplo di $4$ lo decide l’aritmetica; che una persona abbia la febbre, il termometro; che una battaglia sia avvenuta in un certo anno, la storia. Né le spetta definire che cosa sia la verità, questione che appartiene alla filosofia. La logica ammette che le proposizioni abbiano un valore di verità, quale che sia, e studia come quei valori si rapportino tra loro: in particolare, quando la verità di alcune proposizioni obbliga alla verità di un’altra. In altre parole, la logica non è una teoria della verità, ma una teoria della trasmissione della verità.

Ora, ciò che trasmette la verità non dipende dall’argomento trattato, ma dalla struttura. Si confronti l’argomento precedente con quest’altro: «se un animale è un mammifero, respira aria; la balena è un mammifero; dunque la balena respira aria». Entrambi hanno la stessa forma: «se qualcosa è $A$, è $B$; $c$ è $A$; dunque $c$ è $B$». La forma di un argomento è ciò che resta sostituendo i suoi termini non logici (numeri, animali, proprietà) con lettere e conservando le parole logiche: «non», «e», «o», «se… allora», «ogni», «qualche». Ogni argomento che si ottiene da una forma dando un contenuto alle sue lettere è una sua istanza.

Una forma è valida quando nessuna delle sue istanze ha tutte le premesse vere e la conclusione falsa; un argomento è valido quando lo è la sua forma. Un’istanza con premesse vere e conclusione falsa si chiama controesempio della forma: donde una forma non è valida esattamente quando ha un controesempio.

Nelle dimostrazioni di questa lezione useremo una stenografia dell’italiano: $V(A)$ abbrevia «$A$ è vera» e $F(A)$, «$A$ è falsa»; $\neg$ abbrevia «non», $\wedge$ abbrevia «e», $\vee$ abbrevia «o», $\Rightarrow$ abbrevia «se… allora» e $\Leftrightarrow$ abbrevia «se e solo se»; $\forall$ si legge «per ogni» ed $\exists$, «esiste». Questi segni sono qui semplici abbreviazioni di parole del metalinguaggio, e le frecce doppie sono riservate in tutto il corso a quest’uso. Nella lezione successiva compariranno i segni a un solo tratto, $\rightarrow$ e $\leftrightarrow$, insieme a $\neg$, $\wedge$ e $\vee$, come abbreviazioni di un linguaggio formale, con un senso che il corso fisserà con esattezza; la differenza di tratto tra le frecce ricorderà a quale livello si parla.

La proposizione dice che cosa la validità garantisce; conviene vedere con uguale chiarezza che cosa non garantisce. Delle otto combinazioni possibili tra la validità dell’argomento, la verità di tutte le sue premesse e la verità della sua conclusione, una sola è esclusa, quella dell’argomento valido con premesse vere e conclusione falsa; le altre si presentano tutte.

Ne segue la regola pratica che la lezione eserciterà: per mostrare che un argomento non è valido non basta segnalare che qualche premessa o la conclusione è falsa, e per mostrare che è valido non basta che tutto in esso sia vero; la prima cosa richiede di esibire un controesempio della sua forma, e la seconda, un ragionamento che valga per tutte le istanze.

Linguaggio naturale e linguaggio formale

La definizione di validità poggia su due operazioni: riconoscere la forma di un argomento e decidere se una proposizione è vera o falsa. Entrambe presuppongono che ogni frase abbia una sola lettura. Il linguaggio naturale, l’italiano, il cinese o l’arabo, che gli esseri umani apprendono senza istruzione formale e usano per comunicare, non soddisfa questa condizione: la sua flessibilità, che lo rende adatto alla poesia, alla conversazione e alla sfumatura, lo rende anche ambiguo.

• Ambiguità lessicale: una parola ha più significati. «La pesca era ottima» può riferirsi a un frutto o a un’attività all’aria aperta.
• Ambiguità sintattica: una frase ammette più strutture. «Il doppio di tre più quattro» può essere $2 \cdot 3 + 4 = 10$ o $2 \cdot (3 + 4) = 14$.
• Ambiguità di portata: non si sa su quale parte della frase agisca una parola logica. «Tutti gli studenti non hanno superato l’esame» può significare che nessuno l’ha superato o che non tutti l’hanno superato.
• Connettivi imprecisi: la «o» a volte ammette che entrambe le alternative si verifichino («si richiede laurea o esperienza») e altre volte lo esclude («caffè o tè»); il «se… allora» a volte esprime una causa, altre una regola, altre una semplice successione.

All’ambiguità si aggiunge un tratto più profondo: il linguaggio naturale può parlare di sé. Contiene le parole «frase», «vero» e «definire», e con esse può formare frasi che si riferiscono a sé stesse, come «questa frase ha cinque parole». Questa autoreferenzialità è, in generale, innocua; ma, come si vedrà, combinata con la nozione di verità produce frasi che non possono essere né vere né false.

Un linguaggio formale è progettato per eliminare entrambe le fonti di difficoltà. Si fissano un alfabeto, una collezione di simboli, e alcune regole di formazione che dicono, senza lasciare spazio all’interpretazione, quali successioni di simboli sono espressioni ben formate; il significato di ciascuna espressione si fissa poi mediante definizioni altrettanto precise. Così, chiedersi se una successione di simboli appartenga al linguaggio è una questione che si risolve meccanicamente, controllando regole, e ogni espressione si legge in un solo modo. Il linguaggio di questo corso, che la lezione su il linguaggio della logica proposizionale costruisce, ha un alfabeto di soli due simboli, il cerchio $\sigO$ e il disco $\sigI$, e una sola regola di formazione.

Il prezzo è la flessibilità: un linguaggio formale non serve a conversare, e ciascun linguaggio formale esprime solo ciò che le sue regole permettono. Non è vero, però, che si sacrifichi tutto il potere espressivo: i linguaggi formali della logica del primo ordine bastano per scrivere quasi tutta la matematica. Ciò che si sacrifica è l’ambiguità e l’autoreferenzialità incontrollata; ciò che si guadagna è la possibilità di dimostrare teoremi sul linguaggio stesso.

Linguaggio oggetto e metalinguaggio

Per studiare un linguaggio bisogna parlarne, e per parlarne occorre un altro linguaggio. Il linguaggio oggetto è il linguaggio che si studia; il metalinguaggio è il linguaggio in cui lo si studia. In una grammatica latina scritta in italiano, il latino è il linguaggio oggetto e l’italiano il metalinguaggio. In questo corso il linguaggio oggetto sarà il linguaggio formale dei cerchi e dei dischi, e il metalinguaggio sarà l’italiano, arricchito di segni matematici e di lettere greche, $\varphi$, $\psi$, che designeranno formule qualsiasi del linguaggio oggetto senza appartenervi.

La distinzione è centrale per una ragione precisa: le affermazioni che il corso dimostrerà sul linguaggio formale (che ogni formula si legge in un solo modo, che tutto ciò che è deducibile è vero) non sono formule del linguaggio formale, ma frasi del metalinguaggio. Per questo si chiameranno metateoremi, per distinguerle dai teoremi che il sistema deduttivo produce all’interno del linguaggio oggetto.

Una forma elementare della distinzione è quella che separa l’uso di un’espressione dalla sua menzione. In «Roma è una città» si usa la parola per parlare della città; in «“Roma” ha quattro lettere» si menziona la parola, e le virgolette lo indicano: la frase parla della parola, non della città. Confondere le due cose produce enunciati assurdi, come «Roma ha quattro lettere», o argomenti fallaci, come «Roma è una città; “Roma” è una parola di quattro lettere; dunque una città è una parola di quattro lettere».

I paradossi del linguaggio

Una contraddizione è un’affermazione insieme alla sua negazione, come $V(A) \wedge \neg V(A)$. Un paradosso è un ragionamento che, partendo da ipotesi che sembrano accettabili e procedendo per passi che sembrano validi, giunge a una contraddizione. Per la proposizione su che cosa garantisce la validità, se i passi sono davvero validi, qualche ipotesi è falsa: risolvere un paradosso consiste nel trovare quale. Conviene non confondere il paradosso con l’ambiguità, che è soltanto la molteplicità delle letture, né con ciò che è semplicemente sorprendente.

Il mentitore

Il paradosso più antico di questo genere è attribuito a Eubulide di Mileto, nel IV secolo prima della nostra era. Nella sua forma precisa non parla di mentire, che presuppone l’intenzione di ingannare, ma di falsità: sia $m$ la frase «la frase $m$ è falsa». Per ottenere la contraddizione bastano due ipotesi, che conviene scrivere esplicitamente.

• Bivalenza (B): ogni proposizione è vera o falsa, e non entrambe le cose; essere falsa equivale a non essere vera.
• Schema di verità (T): una frase è vera se e solo se ciò che dice è il caso. Per esempio, «la neve è bianca» è vera se e solo se la neve è bianca.

Il teorema non dice che la logica sia contraddittoria, ma che le due ipotesi non possono sostenersi insieme per un linguaggio che contiene la frase $m$. Ci sono, dunque, tre vie d’uscita: abbandonare la bivalenza e ammettere frasi prive di valore di verità; restringere lo schema di verità; oppure impedire che il linguaggio formi la frase $m$. La terza è quella di Alfred Tarski, nel 1933: il predicato «è vera» di un linguaggio non appartiene a quel linguaggio, ma al suo metalinguaggio. In un linguaggio siffatto, $m$ non è una frase ben formata, e il paradosso non può essere enunciato.

Il paradosso di Berry

Pubblicato da Bertrand Russell nel 1906, che lo attribuì a George Berry, bibliotecario di Oxford, questo paradosso non usa la parola «vero», ma la parola «definire». Si dice che un’espressione dell’italiano definisce un numero naturale quando lo descrive in modo che lo si possa identificare senza ambiguità: «il più piccolo numero primo maggiore di dieci» definisce l’$11$. Consideriamo l’espressione «il più piccolo naturale che non sia definibile con meno di venti parole», che va letta così come è scritta, e chiamiamo $b$ il numero che essa pretende di definire. I numeri naturali, in questo corso, sono $1, 2, 3, \ldots$

L’esposizione corrente, che si limita a osservare che l’espressione ha meno di venti parole, omette metà dell’argomento: che il numero $b$ esiste, il che richiede la finitezza del vocabolario e la scelta del primo numero che manca. L’ipotesi che cade è la seconda: «definire» non è una relazione precisa dell’italiano, perché l’espressione che definisce $b$ usa la parola stessa «definire», e il suo senso dipende da quali espressioni contino come definizioni. In un linguaggio formale $L$ si può precisare che cosa significhi «definibile in $L$», ma questa nozione si esprime solo nel metalinguaggio; l’espressione che definisce $b$ non appartiene a $L$, e la contraddizione scompare: $b$ non è definibile in $L$ con pochi simboli, benché lo sia nel metalinguaggio.

Il barbiere e l’insieme di Russell

Il paradosso del barbiere si racconta di solito così: in un villaggio c’è un barbiere, uomo del villaggio, che rade tutti gli uomini del villaggio che non si radono da sé, e soltanto loro. Il barbiere rade sé stesso? Le parole «e soltanto loro» sono essenziali: un barbiere che radesse tutti quelli che non si radono da sé, senza la restrizione, potrebbe radere anche sé stesso senza alcuna contraddizione. Il paradosso è un caso particolare di un lemma generale, di forma diagonale, che conviene dimostrare una volta per tutte.

La conclusione del barbiere è innocua: nessuno aveva affermato che un tale barbiere esistesse. Non accade lo stesso con la sua versione nella teoria degli insiemi. Nel 1902 Russell scrisse a Gottlob Frege che il suo sistema, che pretendeva di fondare l’aritmetica sulla logica, ammetteva il seguente principio di comprensione: per ogni proprietà c’è un insieme i cui elementi sono esattamente gli oggetti che la possiedono. Applicato alla proprietà di non appartenere a sé stesso, il principio afferma che esiste l’insieme

A differenza del barbiere, qui l’esistenza di $Z$ non era una supposizione di un racconto, ma un principio della teoria. Il paradosso di Russell non si risolve dichiarando che $Z$ non esiste, ma riformando la teoria: la teoria assiomatica degli insiemi di Zermelo, del 1908, permette di formare, con una proprietà, soltanto sottoinsiemi di un insieme già dato, e con questa restrizione la contraddizione non si deduce.

Ciò che non è un paradosso

Si è chiamata talvolta «paradosso dell’insieme vuoto» l’osservazione che l’insieme vuoto esiste benché non abbia elementi, come se un oggetto esistente dovesse essere fatto di oggetti esistenti. Non c’è in ciò alcuna contraddizione: un insieme non è fatto dei suoi elementi come un muro dei suoi mattoni, ma è determinato da essi, e la collezione degli elementi di un insieme può non averne nessuno, come una scatola vuota resta una scatola. Che un fatto sorprenda non lo rende paradossale; il paradosso esige di dedurre una contraddizione, e qui non se ne deduce nessuna.

Come li tratta un linguaggio formale

Da quanto precede segue che un linguaggio formale non evita i paradossi per magia, ma in due modi precisi. Il primo è che può essere privo delle risorse che li producono. Il linguaggio della logica proposizionale, che questo corso costruisce, non ha frasi che si riferiscano a sé stesse né un predicato di verità: in esso non si può scrivere la frase del mentitore, e la sua semantica assegna a ogni formula, in ogni assegnazione di valori alle variabili, un unico valore di verità. Il secondo è che, in linguaggi più ricchi, il paradosso si trasforma in teorema: il ragionamento del mentitore, condotto con rigore, dimostra che la verità di un linguaggio sufficientemente espressivo non è definibile in quello stesso linguaggio (Tarski); quello del barbiere e di Russell dimostra che certe collezioni non sono insiemi; e argomenti imparentati con quello di Berry stanno al cuore dei teoremi di incompletezza di Kurt Gödel, del 1931. Così, ciò che nel linguaggio naturale è una perplessità, in un linguaggio formale è informazione.

I quattro pilastri della logica matematica

La logica matematica nacque alla fine del XIX secolo e all’inizio del XX, con Frege, Peano, Russell e David Hilbert, come risposta a una domanda precisa: su quali fondamenti poggi la matematica e se quei fondamenti siano privi di contraddizione. Oggi la si divide in quattro grandi rami, che si intrecciano di continuo.

• Teoria della dimostrazione: studia le dimostrazioni formali come oggetti matematici, cioè come successioni finite di formule che seguono regole esplicite; si chiede che cosa si possa dimostrare in un sistema, se un sistema sia coerente e come alcune dimostrazioni si trasformino in altre. L’unità di deduzione di questo corso ne è un primo contatto.
• Teoria dei modelli: studia la relazione tra un linguaggio formale e le strutture che lo interpretano, i suoi modelli; si chiede quali strutture soddisfino un insieme di formule e quali proprietà delle strutture si possano esprimere in un linguaggio dato. L’unità di semantica, con le sue assegnazioni di valori di verità, ne è la versione più elementare.
• Teoria degli insiemi: studia gli insiemi con assiomi precisi, come quella di Zermelo e Fraenkel, nella quale si può scrivere quasi tutta la matematica; è nata, in buona parte, dalla necessità di evitare il paradosso di Russell.
• Teoria della computabilità: studia quali problemi si possano risolvere mediante una procedura meccanica e quali no. La logica proposizionale è decidibile, come vedrà il corso: esiste una procedura che decide in un numero finito di passi se una formula è valida; la logica dei predicati, invece, non lo è.

Nessun pilastro si studia a fondo senza toccare gli altri: la completezza, risultato centrale di questo corso, è insieme un teorema della teoria della dimostrazione e della teoria dei modelli, e la decidibilità che se ne ricava appartiene alla computabilità.

La mappa del corso

Il corso percorre, per il linguaggio più semplice della logica, quello proposizionale, il cammino completo di una teoria logica, in quattro unità.

1. Linguaggio: la sintassi. Si costruisce il linguaggio oggetto con il suo alfabeto di due simboli e la sua regola di formazione, si dimostra che ogni formula si legge in un solo modo, si impara a dimostrare per induzione e si traducono nel linguaggio formale enunciati e argomenti del linguaggio naturale, segnalando ciò che la traduzione conserva e ciò che perde.
2. Deduzione: si fissa un sistema di assiomi e di regole d’inferenza, e si definisce che cosa significhi che una formula $\varphi$ si deduca da un insieme di formule $\Gamma$, il che si scrive $\Gamma \vdash \varphi$. È la faccia sintattica della validità: manipolare simboli secondo regole, senza badare al loro significato.
3. Semantica: si assegna a ogni formula un valore di verità in ogni assegnazione, e si definisce che cosa significhi che $\varphi$ sia conseguenza di $\Gamma$, il che si scrive $\Gamma \models \varphi$: ogni assegnazione che rende vere le formule di $\Gamma$ rende vera $\varphi$. È la faccia semantica della validità, la definizione di questa lezione resa precisa.
4. Metateoria: si dimostra che le due facce coincidono. La correttezza dice che tutto ciò che è deducibile è conseguenza, e la completezza, che ogni conseguenza è deducibile. Si studiano poi la compattezza e un metodo meccanico, la risoluzione, per decidere se un insieme di formule possa essere soddisfatto.

Se è così, il corso è il primo esempio completo di una teoria matematica il cui oggetto è il ragionamento stesso; e tutte le sue affermazioni sul linguaggio formale saranno, come si è visto in questa lezione, frasi del metalinguaggio dimostrate con il rigore della matematica.

Problemi risolti

I problemi seguenti esercitano, in difficoltà crescente, le distinzioni della lezione: confutare un argomento le cui frasi sono tutte vere, separare le letture di un enunciato ambiguo, classificare espressioni del linguaggio oggetto e del metalinguaggio, e analizzare due ragionamenti di apparenza paradossale per decidere se lo siano.

Problemi proposti

I primi due problemi esercitano la validità e l’ambiguità; il terzo, l’uso e la menzione; gli ultimi due chiedono di analizzare un paradosso nuovo e di applicare il lemma diagonale fuori della linguistica. Ciascuno ha un suggerimento, che conviene aprire solo dopo averlo tentato.