Che cos’è la logica matematica?

Una sezione con un titolo come questo forse sarebbe stato più saggio collo- carla alla fine del libro, quando il lettore avrà acquisito le nozioni di base della materia. Ma anche dopo aver relegato questa sezione ad epilogo del libro, questo titolo risulterebbe sempre un po’ impegnativo, visto che que- sto testo non si propone di insegnare tutta la logica matematica (impresa palesemente impossibile), ma solo di insegnare le basi di quella parte della logica matematica che, a giudizio di che scrive, ha più stretta attinenza con altre parti della matematica. Forse questa sezione la si dovrebbe intitolare

Che cos’è quella parte della logica matematica trattata in questo libro? o

qualcosa del genere. . . Comunque il desiderio di dare una fugace panoramica di quanto verrà studiato in dettaglio nelle pagine successive è troppo forte.

La logica matematica nasce dal tentativo di dare delle risposte matema- ticamente precise a domande generali quali:

(1) Che cos’è una dimostrazione? (2) Che cos’è un procedimento effettivo?

(3) Che cosa vuol dire che una certa affermazione è vera? (4) Che cos’è un insieme?

(5) La logica è un’area della matematica, o è in qualche modo precedente

alla matematica?

I tentativi di rispondere a queste domande hanno generato una vasta mole di teorie matematiche.

4.A. Teoria della dimostrazione. La nozione informale di dimostrazione può essere formalizzata in modo adeguato per i linguaggi del prim’ordine: si parte da un insieme Γ di formule di L detti postulati o assiomi e mediante una catena di ragionamenti si giunge ad una formula che chiamiamo teorema. Per effettuare questi ragionamenti abbiamo bisogno di metodi per dedurre una formula dalle precedenti — le regole logiche — e di un insieme fissato di formule detti assiomi logici:

• le tautologie (definite a pagina 28), • le formule del tipo ϕ_{Jt/xK ⇒ ∃xϕ, e} • le formule del tipo

(x₁ = y₁∧ x₂= y₂∧ x₁ = x₂) ⇒ y₁ = y₂

(x1 = y1∧ · · · ∧ xn= yn) ⇒ f (x1, . . . , xn) = f (y1, . . . , yn)

(x₁= y₁∧ · · · ∧ x_n= y_n∧ P (x₁, . . . , xn)) ⇒ P (y1, . . . , yn)

Le regole logiche sono il modus ponens (pag. 8) e la regola di introduzione del quantificatore esistenziale: se x non occorre libera in ψ, allora da ϕ ⇒ ψ possiamo dedurre (∃xϕ) ⇒ ψ.

Fissato un insieme Γ di formule di un linguaggio del prim’ordine L, una derivazione da Γ è una stringa finita di formule

ϕ0, ϕ1, . . . , ϕn

tali che per ogni i ≤ n: • ϕ_i è in Γ, oppure

• ϕi è un assioma logico, oppure

• ϕi è ottenuta dalle ϕj con j < i mediante una delle due regole logiche.

Una formula ϕ è un teorema di Γ, in simboli Γ ` ϕ

se c’è una derivazione da Γ tale che l’ultima formula della derivazione ϕn è

proprio ϕ.

La nozione di derivazione ha un carattere sintattico, mentre nell’usuale argomentazione matematica si basa sul concetto di conseguenza logica (vedi pagina 41) che è una nozione semantica, cioè che tratta di modelli. Per esempio, se si vuole dimostrare l’affermazione

ogni gruppo con 49 elementi è abeliano

si considera un gruppo di ordine 49 (o più in generale di ordine p2con p primo) e si argomenta che il gruppo è isomorfo a Z/49Z oppure a Z/7Z × Z/7Z, che sono entrambi abeliani. La derivazione della sua versione formalizzata

ε49⇒ ∀x∀y (x · y = y · x)

a partire dagli assiomi per i gruppi (gli enunciati (3.8) a pagina 38), è invece assai laboriosa.13 Tuttavia la nozione formale, sintattica di dimostrazione (codificata dalle definizione di derivazione) e quella semantica (in uso nella pratica matematica) sono strettamente collegate. Supponiamo, per semplicità, che tanto ϕ quanto le formule di Γ siano degli enunciati: se Γ ` ϕ allora ogni modello di Γ è un modello di ϕ (Teorema di Correttezza 34.2) e, viceversa, se ogni modello che soddisfa Γ soddisfa anche ϕ allora Γ ` ϕ (Teorema di Completezza 35.2). Quindi le derivazioni sono la controparte formale della nozione intuitiva di dimostrazione — ϕ è dimostrabile (nell’accezione comune del termine) a partire da Γ, se e solo se ϕ è derivabile da Γ, in simboli Γ ` ϕ. Attenzione. La parola “completezza” ha due significati distinti in logica, e questa spiacevole situazione può causare confusione. La “Completezza” nel Teorema 35.2 si riferisce al fatto che le regole logiche sono complete, cioè sono sufficientemente potenti per derivare ogni risultato dimostrato semanticamente, per mezzo di modelli. Questo non significa che l’insieme degli enunciati veri in ogni struttura sia una teoria completa, come l’Esempio 3.28 mostra.

Un sistema di assiomi Σ si dice coerente se non è contraddittorio, cioè se non è in grado di derivare una formula e la sua negazione. Chiaramente se Σ ha un modello allora è coerente, dato che una struttura non può soddisfare tanto un enunciato quanto la sua negazione. Ma vale anche il viceversa (Teorema di Esistenza di Modelli 35.3): se Σ è coerente, allora ha un modello.

Il calcolo logico che abbiamo descritto qui sopra (essenzialmente dovuto ad Hilbert e Ackermann) è molto utile per dimostrare i Teoremi di Cor- rettezza e Completezza, ma è piuttosto distante dal modo informale con cui si argomenta in matematica. La deduzione naturale, inventata da Gentzen proprio per ovviare a questo inconveniente, permette un’analisi più

incisiva della struttura delle dimostrazioni. L’idea di base del calcolo della deduzione naturale consiste nel privilegiare la nozione di regola: per ogni connettivo e quantificatore vengono introdotte delle regole simili a quelle della Sezione 2.A mediante le quali si definisce un’adeguata nozione di deri- vazione. Si dimostra che la deduzione naturale è equivalente al calcolo logico alla Hilbert-Ackermann nel senso che i teoremi derivabili da un insieme Σ di formule è lo stesso per i due calcoli logici. Questi argomenti verranno affrontati nel Capitolo ??.

4.B. Calcolabilità. Ogni funzione calcolabile risulta appartenere ad un insieme di funzioni note come funzioni ricorsive. Poiché ogni funzione ricorsiva è calcolabile, useremo il termine “ricorsivo” come sinonimo di “calcolabile”. Un insieme A ⊆ N è ricorsivo se la sua funzione caratteristica lo è. Per verificare se un certo numero n appartiene a ran(f ), dove f : N → N è ricorsiva, è sufficiente calcolare i valori f (0), f (1), . . .: se n compare in questa lista, allora in un numero finito di passi saremo in grado di asserire che

n ∈ ran(f ), se invece n non compare, dovremo effettuare un numero infinito

di computi per essere sicuri che n /∈ ran(f ). Un insieme della forma ran(f ) con f calcolabile si dice semiricorsivo o ricorsivamente enumerabile. Ogni insieme ricorsivo è ricorsivamente enumerabile, ma non viceversa. I sottoinsiemi ricorsivamente enumerabili di N sono esattamente gli insiemi diofantei cioè quelli della forma

(4.1) N ∩ {f (n1, . . . , nk) | n1, . . . , nk∈ Z}

dove f è un polinomio in k variabili a coefficienti in Z.

Se consideriamo un linguaggio che ha un numero finito di simboli non logici — e tutti i linguaggi del prim’ordine sin qui considerati rientrano in questa tipologia — è possibile associare ad ogni formula e, più in generale, ad ogni stringa di formule un numero naturale. Se Σ è un insieme ricorsivo di assiomi, allora

(4.2) l’insieme delle derivazioni a partire da Σ è ricorsivo,

in altre parole: dimostrare che una stringa di formule costituisca o meno una derivazione è una verifica meccanica, mentre

se Σ è sufficientemente potente, allora l’insieme dei teoremi di Σ è ricorsivamente enumerabile, ma non ricorsivo.

L’espressione “sufficientemente potente” significa che gli assiomi di Σ dimo- strano certi fatti elementari sui numeri naturali — per esempio, l’aritmetica di Peano (Sezione 7.E del Capitolo II) rientra tra questi sistemi assiomatici.

Un ulteriore sviluppo di queste idee porta al celebre Primo Teorema di Incompletezza14di Gödel:

Ogni sistema Σ di assiomi sufficientemente potente, ricorsi- vo e coerente è incompleto, cioè c’è un enunciato σ tale che Σ 6` σ e Σ 6` ¬σ.

L’ipotesi di coerenza di Σ è necessaria, dato che un sistema di assiomi incoerente deriva qualsiasi formula.

4.C. Modelli. Per la logica matematica, i termini e le formule di un lin- guaggio L sono oggetti matematici a tutti gli effetti (al pari dei numeri naturali, dei grafi, degli spazi vettoriali, . . . ). Invece nell’uso corrente le (pseudo-)formule non hanno un vero status in matematica, la loro funzione è quella di descrivere proprietà delle strutture, che sono il vero oggetto di interesse per i matematici che non si occupano di logica. Quindi uno dei primi e principali ostacoli che si incontra all’inizio dello studio della logica è accettare che le formule e le strutture siano entrambi oggetti di studio. Questo cambiamento di punto di vista consente non solo di studiare tutte le formule che valgono in una data struttura, o in una classe di strutture, come già avviene nell’algebra, ma anche di seguire il percorso opposto: partire da un insieme di formule e andare a studiare le strutture che soddisfano questo insieme. La teoria dei modelli, cioè lo studio delle interazioni tra formule e strutture dello stesso linguaggio, già intrapreso nelle Sezioni 3 e 5 sarà sviluppato in modo sistematico nel Capitolo VI. Vedremo come lo studio dei modelli delle teorie del prim’ordine sia in grado di risolvere problemi provenienti da altre parti della matematica, e di gettare nuova luce su oggetti ben noti. Per esempio, vedremo come sia possibile costruire delle strutture (M, +, ·, <) che sono elementarmente equivalenti, ma non isomorfe, a (N, +, ·, <). Queste strutture si dicono modelli non-standard dell’aritmetica e sono essenziali per poter comprendere appieno i teoremi di Incompletezza di Gödel.

Infine osserviamo che nelle pagine precedenti abbiamo detto che cosa significa che un enunciato di L è vero in una struttura M , cioè abbiamo dato una funzione

(Enunciati di L) × (Strutture di L) → {0, 1}

che associa ad una coppia (σ, M ) il valore 1 se e solo se M _{ σ. Ad} una osservazione più attenta si vede però che la definizione data, benché rassicurante per via della sua naturalezza, non è molto soddisfacente dal punto di vista del rigore in quanto si passa con troppa disinvoltura dal linguaggio

14I teoremi di incompletezza sono tra i risultati più profondi della logica e verranno dimostrati nel Capitolo ??.

formale L al linguaggio informale con cui solitamente si descrivono le verità matematiche. Per convincersi della necessità di un’adeguata formalizzazione della nozione di verità e conseguentemente di definibilità, basta considerare il seguente ragionamento, noto come paradosso di Berry:

Sia n il più piccolo numero naturale che non è definibile con meno di 1000 simboli.

Ma la frase qui sopra ha meno di 1000 simboli ed è quindi una definizione di n. Nel Capitolo VI formalizzeremo in modo rigoroso la nozione di soddisfazione e il paradosso di Berry si scioglierà come neve al sole.

L’aritmetica di Peano e la teoria degli insiemi sono teorie in cui è possibile trovare enunciati che non sono né dimostrabili né refutabili a partire da tale teoria. Tuttavia ci sono molti esempi di teorie del prim’ordine, matemati- camente interessanti, che non sono soggette al fenomeno dell’incompletezza. Per esempio, la teoria dei campi algebricamente chiusi di caratteristica zero (Sezione 5.D.4) è una teoria completa, quindi è la teoria di (C, +, ·), per la Proposizione 3.15. Ogni teoria completa T in un linguaggio ricorsivo è decidibile, nel senso che esiste un algoritmo in grado di determinare se un enunciato è dimostrabile o meno a partire da T , e lo studio delle teorie com- plete e decidibili è uno degli argomenti centrali nella teoria dei modelli. La teoria di (N, +, ·) è completa, ma indecidibile, e quindi non è ricorsivamente assiomatizzabile. Quindi ogni qual volta si interpreta definibilmente (N, +, ·) in una struttura, si ottiene che questa struttura è indecidibile.

4.D. Insiemi. La teoria degli insiemi è onnipresente in matematica — i vari oggetti studiati in algebra, analisi, geometria, sono definiti come insiemi dotati di qualche struttura addizionale. Nella Sezione 10 del Capitolo III e più diffusamente nel Capitolo V mostreremo come ricostruire in termini insiemistici gli enti fondamentali della matematica — l’aritmetica, i numeri reali, la teoria della misura, ecc. Per via di questa propedeuticità, studieremo la teoria degli insiemi nel Capitolo IV.

Oltre a fornire un linguaggio comodo ed elastico per la matematica, la teoria degli insiemi ha una vita sua propria, incentrata sull’analisi della nozione di infinito, con problemi, tecniche, metodologie specifiche, che la rendono una delle parti più affascinanti della logica matematica. Prima di addentrarci in questi argomenti osserviamo che la teoria degli insiemi può essere formalizzata come una teoria del prim’ordine — anzi la formalizzazione è una scelta necessaria, visto che Russell nel 1901 mostrò che la teoria ingenua degli insiemi è contraddittoria. Nei primi anni del XX secolo sono state introdotte alcune assiomatizzazioni (essenzialmente equivalenti) della nozione di insieme che evitano queste antinomie, e in questo libro svilupperemo la teoria degli insiemi come una teoria del prim’ordine. Torniamo al concetto di

infinito. L’idea rivoluzionaria di Cantor, l’inventore della teoria degli insiemi, è che è possibile confrontare la taglia degli insiemi infiniti mediante biezioni. In particolare, il tipo di infinito della retta reale è maggiore del tipo di infinito dei numeri naturali (Teorema 10.23 a pagina 231). Cantor congetturò che non ci fosse nessun tipo di infinità intermedia, cioè che ogni sottoinsieme infinito della retta fosse in biezione con i naturali o con la retta stessa e questa congettura prese il nome di Ipotesi del Continuo. Nel 1938 Gödel dimostrò che l’Ipotesi del Continuo non è refutabile a partire dal sistema di assiomi della teoria degli insiemi, e nel 1963 Cohen dimostrò che non è neppure dimostrabile. Quindi la teoria degli insiemi è incompleta e l’Ipotesi del Continuo è un esempio di tale incompletezza. Negli ultimi decenni sono stati individuati moltissimi altri esempi di enunciati indipendenti, alcuni dei quali provenienti da altre aree della matematica. Ma questi sono argomenti troppo avanzati per questo libro.

4.E. Metamatematica. In questo libro la teoria degli insiemi è presa come base fondante per la costruzione degli altri oggetti matematici. In particolare, le nozioni logiche quali linguaggio, derivazione, struttura, verità, . . . , sono formalizzate all’interno della teoria assiomatica degli insiemi, che per brevità indicheremo con TI.15 D’altra parte, come abbiamo osservato, anche la teoria degli insiemi è una teoria del prim’ordine e quindi il suo studio andrebbe posposto dopo il Capitolo VI dove si danno i risultati sulle teorie del prim’ordine. Ci troviamo davanti a una situazione paradossale: da un lato abbiamo bisogno della teoria degli insiemi per definire il concetto di struttura di un linguaggio del prim’ordine (e quindi per poter parlare di validità di una formula), dall’altro dobbiamo usare un linguaggio del prim’ordine per sviluppare in modo rigoroso la nozione di insieme, cioè la teoria TI. Più in generale: se la logica è una parte della matematica, come può essere fondamento di tutta la matematica (e quindi di sé stessa)? Questo circolo vizioso, che ricorda il problema della primogenitura tra galline e uova, è in realtà solo apparente. Vediamo come uscirne.

4.E.1. Sintassi. Consideriamo un linguaggio del prim’ordine L contenente una quantità finita di simboli non logici (cioè simboli di funzione, di relazione e di costante) — tutti gli esempi delle Sezioni 3 e 5 sono di questo tipo, così come è LST, il linguaggio della teoria degli insiemi che ha un unico simbolo di relazione binaria ∈. I termini e le formule di L sono oggetti concreti, segni che scriviamo sulla lavagna o sul foglio di carta. Quindi è possibile determinare in modo meccanico se una certa stringa di simboli è un termine o una formula di L. Supponiamo Σ sia un insieme effettivo di enunciati di L, cioè tale che si possa stabilire in modo algoritmico se un

15TI è soltanto un simbolo per denotare una delle possibili assiomatizzazioni della teoria degli insiemi: ZF, GB, MK, . . .

enunciato σ di L appartiene a Σ. Per brevità chiameremo gli L e Σ come sopra finitistici. Tutti gli esempi di sistemi di assiomi visti nelle Sezioni 3 e 5, così come i sistemi di assiomi per la teoria degli insiemi che vedremo nel Capitolo IV, sono esempi di teorie finitistiche. Come spiegato nella Sezione 4.A una derivazione di σ a partire da Σ è una stringa finita di formule di L, ciascuna delle quali è un assioma logico, oppure è in Σ, oppure è ottenuto dalle formule precedenti mediante una regola di inferenza, e come già osservato a pagina 65 la nozione “essere una dimostrazione in Σ” è effettiva. In altre parole: data una stringa ϕ₀, . . . , ϕn di formule di L

possiamo stabilire in modo meccanico se questa è una derivazione in Σ.16 Le formule di LST e le derivazioni in questo linguaggio sono enti pre-

insiemistici, oggetti concreti che ci servono per parlare di insiemi arbitrari.

L’ambiente matematico in cui si effettuano questi ragionamenti costruttivi e finitistici sulle formule si dice metateoria o metamatematica. Tentando un’analogia un po’ azzardata con il mondo dell’informatica, potremmo dire che la metamatematica sta alla matematica come i linguaggi-macchina stanno ai programmi in generale.

Diremo che Σ è coerente se da esso non è possibile derivare ogni formula o, equivalentemente, se da esso non si deriva una formula logicamente falsa, per esempio ∃x(x 6= x). Quindi l’asserzione della coerenza di Σ è un enunciato universale e può essere visto come una previsione ottimistica: non riusciremo mai a derivare una contraddizione da Σ. Viceversa, per affermare che Σ è incoerente (cioè non è coerente) dobbiamo esplicitamente esibire una derivazione di una contraddizione da Σ.

4.E.2. Semantica. Le nozioni di struttura, verità di una formula in una struttura, ecc., sono tutte nozioni essenzialmente insiemistiche e che quindi sono formulabili all’interno di TI, ma non sono formalizzabili a livello di metateoria. Invece, tutti i ragionamenti della metateoria possono essere codificati all’interno di una teoria sufficientemente potente, quale, per esempio, la teoria TI. In particolare, le nozioni di derivazione e coerenza possono essere codificate nella teoria degli insiemi, quindi TI è in grado di formulare (e dimostrare) il Teorema di Completezza 35.2

Sia T una teoria del prim’ordine in un linguaggio L e sia σ un L-enunciato. Allora T |= σ se e solo se T ` σ. e il Teorema di Esistenza di Modelli 35.3

Una teoria del prim’ordine coerente è soddisfacibile.

16Osserviamo che quando in matematica asseriamo di aver dimostrato un certo teorema, stiamo essenzialmente affermando (modulo un’operazione di traduzione dell’enunciato nel linguaggio insiemistico LST) che un certo enunciato σ è derivabile a partire dagli assiomi della teoria degli insiemi.

Osserviamo che i risultati qui sopra si applicano a tutte le teorie del prim’or- dine, e non solo quelle finitistiche.

4.E.3. Codifica della sintassi. Se L e Σ sono finitistici, allora sono rappresen- tabili all’interno della teoria degli insiemi mediante numeri naturali. Ogni formula ϕ è codificata mediante un numero naturale _{pϕq, mentre Σ è codifi-} cato mediante un insieme calcolabile di numeri naturali _{pΣq. Quindi una} derivazione a partire da Σ può essere codificata come una successione finita di naturali, e questa a sua volta può essere vista come un numero naturale.

Se nella metateoria abbiamo dimostrato che

(4.3) Σ ` σ

allora il fatto che tale derivazione esiste è dimostrabile all’interno di TI, e scriveremo

(4.4) TI `pΣ ` σq.

Quindi (4.4) segue da (4.3). L’implicazione inversa, in generale, non vale: per dimostrare la formula (4.3) bisogna esibire esplicitamente una derivazione ϕ0, . . . , ϕn di σ, mentre per dimostrare la (4.4) è sufficiente dimostrare che

c’è una qualche derivazione di σ a partire da Σ, per esempio dimostrando

per assurdo che la non-esistenza di una dimostrazione siffatta porta ad una contraddizione in TI. La situazione è analoga a quanto avviene in teoria dei numeri quando si dimostrano affermazioni del tipo ∃n ϕ(n) con ϕ una proprietà calcolabile: se gli argomenti usati per la dimostrazione sono costruttivi, allora possiamo (sperare di) esibire esplicitamente un numero n per cui vale la proprietà ϕ, ma se si sono usati metodi astratti, in generale non si ha idea di quanto valga n.

L’affermazione “Σ è coerente” è formalizzabile in TI e indicheremo la sua formalizzazione con ConΣ. Asserire che

TI ` ¬ ConΣ

significa che abbiamo dimostrato (in teoria degli insiemi) l’esistenza di una dimostrazione di una contraddizione in Σ, ma non è detto che abbiamo idea di come sia fatta tale dimostrazione. Per (4.2) e (4.1), asserire ¬ ConΣè equi-

valente ad affermare che certo polinomio a coefficienti interi (esplicitamente calcolabile a partire da Σ) ha una soluzione negli interi.

Il Secondo Teorema di Incompletezza di Gödel asserisce che nessuna teoria sintattica Σ coerente e sufficientemente potente è in grado di dimostrare la propria coerenza. Sufficientemente potente significa che la teoria in questione è in grado di codificare la sintassi di un linguaggio finitistico, quindi TI è sufficientemente potente. Inoltre la vasta mole di risultati di matematica dimostrati nella teoria degli insiemi ci inducono a ritenere che

TI sia scevra da contraddizioni. Quindi, per il Teorema di Gödel, TI 6` ConTI.

La coerenza è ovviamente un requisito essenziale per una teoria sintattica Σ, ma non è l’unico requisito importante. Consideriamo, per esempio la teoria Σ ottenuta aggiungendo a TI l’enunciato ¬ Con_TI. Poiché TI è coerente e non dimostra Con_TI, ne segue che Σ è coerente. Inoltre una dimostrazione a partire da TI è anche una dimostrazione a partire da Σ, quindi ¬ Con_TI⇒ ¬ Con_Σ, da cui

Σ ` ¬ ConΣ.

Cioè Σ dimostra l’esistenza di (un numero naturale che codifica) una deri- vazione di una contraddizione a partire da Σ, anche se noi non saremo mai in grado di esibire una dimostrazione siffatta. In altre parole: la teoria Σ è coerente, ma asserisce la propria incoerenza!

Lo studio della dialettica tra teoria e metateoria è uno degli aspetti più affascinanti della logica e verrà studiato nel Capitolo ??.

Definibilità in algebra