LOGICA MATEMATICA - unipi.it

74
LOGICA MATEMATICA Mauro Di Nasso N.B. Questa ` e una prima versione, ancora incompleta e con diverse parti da rivedere. Ogni suggerimento su eventuali correzioni/integrazioni ` e il benvenuto.

Transcript of LOGICA MATEMATICA - unipi.it

Page 1: LOGICA MATEMATICA - unipi.it

LOGICA MATEMATICA

Mauro Di Nasso

N.B. Questa e una prima versione, ancora incompletae con diverse parti da rivedere. Ogni suggerimento sueventuali correzioni/integrazioni e il benvenuto.

Page 2: LOGICA MATEMATICA - unipi.it
Page 3: LOGICA MATEMATICA - unipi.it

CAPITOLO 1

Calcolo Proposizionale

1. Introduzione ai connettivi

In questa parte preliminare preciseremo il significato dell’avverbio“non”, delle congiunzioni “e” ed “o”, delle espressioni del tipo “se ...allora” e “se e solo se”.

Nel linguaggio comune di tutti i giorni – cioe nel cosiddetto lin-guaggio naturale – il loro significato non e univocamente stabilito. Adesempio, a seconda del contesto, la particella “o” puo assumere sia si-gnificato congiuntivo che disgiuntivo. Chiariamo un esempio. Quandochiediamo “un panino con prosciutto o con salame”, la “o” assumesignificato disgiuntivo. Infatti, la nostra richiesta sara soddisfatta sericeviamo un panino con prosciutto, sara soddisfatta se riceviamo unpanino con salame, ma certamente non sara soddisfatta nel caso in cuiricevessimo un panino con prosciutto e salame insieme. Invece, quandoun regolamento stabilisce che per partecipare ad un concorso occorre“essere laureati in matematica o in fisica”, certamente puo fare do-manda anche chi sia in possesso di una doppia laurea in matematica edin fisica (significato congiuntivo). Per riuscire a dare una trattazionematematica del ragionamento e della nozione di linguaggio, sara neces-sario fare una scelta precisa, definendo senza ambiguita ed una voltaper tutte il significato da attribuire alla congiunzione “o”, cosı comealle altre espressioni considerate. Lo faremo seguendo il comune usoche ne viene fatto nel linguaggio matematico.

Come primo passo verso una formalizzazione del concetto di lin-guaggio, introduciamo i seguenti simboli, chiamati connettivi logici :

• Simbolo di negazione ¬ “non” ;

• Simbolo di congiunzione ∧ “e” ;

• Simbolo di disgiunzione ∨ “o” ;

• Simbolo di implicazione → “se ... allora” ;

• Simbolo di doppia implicazione ↔ “se e solo se”.

I connettivi permettono di formare nuove proposizion a partire daproposizioni date. Ad esempio se P denota la proposizione “c’e il sole”

3

Page 4: LOGICA MATEMATICA - unipi.it

4 1. CALCOLO PROPOSIZIONALE

e Q la proposizione “vado al mare”, ¬P denotera la proposizione “nonc’e il sole”, P → Q la proposizione “se c’e il sole allora vado al mare”,e cosı via. Il simbolo di negazione ¬ e un connettivo unario perchesi applica ad una singola proposizione, mentre gli altri connettivi sidicono binari perche connettono coppie di proposizioni.

Qui per proposizione intendiamo un qualunque enunciato cui siaattribuito – in un fissato contesto – uno ed uno solo tra i due valoridi verita: vero oppure falso. Naturalmente, questa e una semplifica-zione rispetto al linguaggio naturale, in cui si hanno spesso enunciatiil cui valore di verita appare piu sfumato e non riducibile a due solepossibilita. Tuttavia, nel comune uso matematico, ogni proprieta “benformulata” viene effettivamente pensata come proposizione nel sensoindicato sopra, cioe come enunciato che e o vero o falso.

Il grande logico matematico (e filosofo) Bertrand Russell scrisseche in matematica non conosciamo mai cio di cui stiamo parlando.1 Ineffetti, piu che l’essenza degli oggetti presentati, cio che compete al ma-tematico e capire come funzionano (tipico esempio: i numeri). Anchequi faremo qualcosa di simile. Allo scopo di attribuire un significatopreciso ai vari connettivi, stabiliamo come si comportano rispetto aivalori di verita delle proposizioni coinvolte. Precisamente, per tutte leproposizioni P e Q, richiediamo quanto segue.

• ¬P e vera quando P e falsa, ed e falsa quando P e vera;

• P∧Q e vera quando sia P cheQ sono vere, ed e falsa altrimenti;

• P ∨ Q e falsa quando sia P che Q sono false, ed e vera altri-menti;

• P → Q e falsa quando l’ipotesi (o antecedente) P e vera e latesi (o conseguente) Q e falsa, ed e vera negli altri casi;

• P ↔ Q e vera quando P e Q hanno lo stesso valore di verita,ed e falsa altrimenti.

Tutte queste richieste sono schematizzate nella tabella qua sotto,dove e indicato il valore di verita V (vero) o F (falso) che intendiamoattribuire alle proposizioni formate usando i vari connettivi, in funzionedei possibili valori di verita delle proposizioni di partenza.

1 “Mathematics may be defined as the subject where we never know what weare talking about” (dal libro: Recent Work on the Principles of Mathematics).

Page 5: LOGICA MATEMATICA - unipi.it

1. INTRODUZIONE AI CONNETTIVI 5

P ¬PV FF V

P Q P ∧Q P ∨Q P → Q P ↔ QV V V V V VV F F V F FF V F V V FF F F F V V

Per giungere a definizioni precise abbiamo dovuto necessariamentecompiere delle scelte, non sempre corrispondenti al significato che i variconnettivi hanno nel linguaggio naturale. Ad esempio, la disgiunzione∨ corrisponde alla “o” nel suo significato inclusivo: richiediamo infattiche la proposizione P ∨ Q sia vera nel caso in cui P e Q siano en-trambe vere. E interessante il fatto che questa ambiguita di significatoche la disgiunzione ha in italiano, non sussisteva invece nel latino. Inquella lingua si usavano infatti due particelle diverse: “vel” per deno-tare la “o” inclusiva (quella corrispondente al nostro connettivo ∨), e“aut” per la disgiunzione esclusiva (come nell’esempio del “panino alprosciutto o al salame”).

Un caso particolarmente delicato e quello dell’implicazione P → Q.Pensare alla proposizione P → Q come vera quando P e Q sono vere,e come falsa quando P e vera ma Q e falsa, sembra in accordo conl’uso comune. Infatti, con un ragionamento corretto, da premesse veresi ottengono soltanto conseguenze vere.2 Un po’ strano sembra inveceaccettare come valida l’implicazione P → Q ogni volta che P e falsa.Questo e pero in accordo con la pratica matematica.

Un esempio tipico e dato dalla fondamentale nozione di sottoinsie-me. Per definizione, un insieme A e sottoinsieme di un insieme B se laseguente implicazione e vera per ogni x:

(x ∈ A) −→ (x ∈ B).

Nel caso in cui l’elemento scelto x appartenga ad A, cioe quando “x ∈A” e vera, richiediamo che anche “x ∈ B” sia vera. Se invece l’elementox non appartiene ad A, l’implicazione di sopra e considerata comunquevera, sia nel caso che “x ∈ B” sia vera, sia nel caso che “x /∈ B” siafalsa.

Un altro possibile argomento a favore della tavola di verita che ab-biamo dato per il connettivo →, e il seguente. Indipendentemente dal

2 In realta, nel linguaggio naturale, si considerano implicazioni P → Q solo nel-l’eventualita che possa esistere un preciso rapporto causale tra P e Q. Ad esempio,comunemente non si attribuisce alcun valore di verita ad implicazioni del tipo: “sei multipli di 12 sono pari allora Pisa e in Toscana”.

Page 6: LOGICA MATEMATICA - unipi.it

6 1. CALCOLO PROPOSIZIONALE

valore di verita di P e di Q, sembra ragionevole accettare come veral’implicazione (P ∧ Q) → P . Infatti, sembra corretta che la congiun-zione di due ipotesi implichi ognuna della due. Osserviamo che se P evera e Q e falsa, abbiamo la validita di “F→ V”; mentre se P e falso,abbiamo la validita di “F→ F”.

2. Le formule proposizionali

Dopo questa introduzione un po’ euristica sul significato dei con-nettivi logici, spostiamoci ora su un livello piu formale, introducendo ilcosiddetto calcolo proposizionale. Lo scopo e quello di matematizzarel’uso delle proposizioni e dei connettivi, cosı da poter trattare quellenozioni logiche mediante un vero e proprio calcolo. Naturalmente, ilpasso iniziale e quello di dare definizioni matematiche, cioe precise erigorose.

Definizione 1.1. Un linguaggio proposizionale e un insieme infi-nito di simboli L, chiamati L-variabili proposizionali.

Seguendo l’uso comune, denotiamo con lettere latine maiuscole levariabili proposizionali, eventualmente con indici.

A,B,C, . . . , X, Y, Z, . . . , A1, A2, A3, . . . , X1, X2, X3, . . .

Intuitivamente, possiamo pensare alle variabili proposizionali comea generiche proposizioni primitive, a partire dalle quali si ottengono –usando i connettivi – tutte le altre proposizioni che stiamo studiando.Naturalmente, devono essere stabilite regole precise per la formazionedi nuove proposizioni a partire da proposizioni date.

Definizione 1.2. L’insieme Form(L) delle L-formule proposizio-nali e il piu piccolo insieme che soddisfa le seguenti proprieta:

(1) Le L-variabili proposizionali sono L-formule proposizionali,dette L-formule atomiche ;

(2) Se A e B sono L-formule proposizionali, allora anche

(¬A), (A ∧ B), (A ∨ B), (A → B), (A ↔ B)

sono L-formule proposizionali.

Questa definizione ha bisogno di una giustificazione, perche dobbia-mo garantire che effettivamente esiste il piu piccolo tra gli insiemi chesoddisfano le proprieta (1) e (2) di sopra. A questo scopo, definiamola sequenza di insiemi 〈 Fn | n ∈ N 〉, ponendo induttivamente:

• F0 = L ;

Page 7: LOGICA MATEMATICA - unipi.it

2. LE FORMULE PROPOSIZIONALI 7

• Fn+1 = Fn⋃{(¬A) | A ∈ Fn}

⋃{(A ∧ B) | A,B ∈ Fn}⋃

{(A ∨ B) | A,B ∈ Fn}⋃{(A → B) | A,B ∈ Fn}⋃

{(A ↔ B) | A,B ∈ Fn(L)}.

Proposizione 1.3. L’insieme di tutte le L-formule proposizionalie dato dall’unione

Form(L) =⋃n∈N

Fn.

Dim. Vediamo intanto che l’unione⋃nFn soddisfa le proprieta (1)

e (2) della Definizione 1.2. Banalmente L = F0 ⊆⋃nFn. Supponiamo

ora che A,B ∈⋃nFn, cioe che A ∈ Fn1 e B ∈ Fn2 per opportuni

n1, n2. Visto che la successione degli Fn e crescente, cioe Fn ⊆ Fn′

per n ≤ n′, entrambe le formule A,B ∈ Fm, dove m = max{n1, n2}.Percio (¬A), (A ∧ B), (A ∨ B), (A → B), e (A ↔ B) appartengonotutte a Fm+1, e quindi a

⋃nFn. Resta da vedere che qualunque altro

insieme Λ che soddisfi le proprieta (1) e (2) della Definizione 1.2 includenecessariamente tutti gli insiemi Fn, cioe che

⋃nFn e il piu piccolo

insieme con quelle proprieta. Questo e immediato per induzione su n.Infatti, per la (1), F0 = L ⊆ Λ. Inoltre, per la (2), se Fn ⊆ Λ, ancheFn+1 ⊆ Λ. �

Le formule proposizionali sono dunque particolari stringhe finite divariabili proposizionali, connettivi, e parentesi. L’uso delle parentesi enecessario per evitare ambiguita. Ad esempio, la scrittura “¬A ∧ B”avrebbe due possibili interpretazioni: la prima consiste nel negare Ae poi nel congiungere con B, cioe “((¬A) ∧ B)”; la seconda consistenel negare la congiunzione di A e B, cioe “(¬(A ∧ B))”. Tuttavia, percomodita, alcune delle parentesi verranno omesse nella scrittura delleformule, quando cio non provochi confusione. Lo faremo attenendocialle seguenti convenzioni nella lettura di una stringa:

• Il connettivo ¬ ha la precedenza su ∧ e ∨, i quali, a loro volta,hanno la precedenza su → e ↔.

Ad esempio, scriviamo “¬A ∧ B → C” per intendere la formula“(((¬A) ∧ B)→ C)”.

Sull’insieme Form(L) vale una particolare forma di induzione, dettainduzione sulla costruzione delle formule che useremo ripetutamentedurante il corso.

Proposizione 1.4. Sia Φ una proprieta, e supponiamo che valga-no:

• Base di induzione: Φ vale per tutte le formule atomiche ;

Page 8: LOGICA MATEMATICA - unipi.it

8 1. CALCOLO PROPOSIZIONALE

• Passo induttivo: Se Φ vale per le formule A e B, allora Φvale anche per le formule (¬A), (A ∧ B), (A ∨ B), (A → B),e (A ↔ B).

Allora la proprieta Φ vale per tutte le L-formule.

Dim. Procedendo per induzione su n e usando le ipotesi di sopra,e immediato dimostrare che la proprieta Φ vale per tutte le formule inFn. La tesi segue allora dal fatto che Form(L) =

⋃nFn. �

Oltre a dimostrare proprieta per induzione sulle formule, si possonoanche dare definizioni per induzione sulle formule.3 Un primo esempioe la seguente nozione di sottoformula.

Definizione 1.5. Definiamo per induzione sulla costruzione delleformule l’insieme SF(A) delle sottoformule di una formula A in questomodo:

• Se A ∈ L e una formula atomica, allora SF(A) = {A}, cioe Ae l’unica sottoformula di se stessa.

• Se A = ¬B allora SF(A) = {A} ∪ SF(B) ;

• Se A = B∨C o se A = B∧C o se A = B → C o se A = B ↔ C,allora SF(A) = {A} ∪ SF(B) ∪ SF(C).

Definizione 1.6. Definiamo per induzione sulla costruzione delleformule il rango ρ(A) come segue:

ρ(A) =

0 se A e una variabile ;

ρ(B) + 1 se A = ¬B ;

max{ρ(B), ρ(C)}+ 1 se A = B ∨ C , o se A = B ∨ C ,o se A = B → C , o se A = B ↔ C .

Procedere per induzione sulla costruzione delle formule equivale aprocedere per induzione sul rango. Vale infatti la seguente proprieta,la cui facile dimostrazione e lasciata per esercizio.

Esercizio 1.7. Per ogni formula A, dimostrare che

ρ(A) = min{n | A ∈ Fn}.

Notiamo che il rango di una formula e diverso dal numero deiconnettivi che vi compaiono.

Esercizio 1.8. Sia A e una formula di rango n. Dimostrare che sek e il numero di connettivi che compaiono in A allora n ≤ k ≤ 2n − 1.

3 In realta in questo caso sarebbe piu corretto parlare di definizioni perricorsione.

Page 9: LOGICA MATEMATICA - unipi.it

3. LE INTERPRETAZIONI 9

E importante chiarire che le formule proposizionali sono oggettipuramente sintattici. Sono infatti semplici stringhe finite di simboli, equindi non hanno di per se alcun valore di verita.

Le formule possono essere pensate come strutture di proposizioni,nel senso che rimpiazzando le variabili con proposizioni arbitrarie, ne ri-sultano nuove proposizioni. Ad esempio, se nella formula “A→ B∨C”sostituiamo la variabile A con la proposizione “c’e il sole”, la variabileB con la proposizione “vado al mare” e infine C con “vado a fare shop-ping”, otteniamo la proposizione “se c’e il sole, allora vado al mare ovado a fare shopping”.

3. Le interpretazioni

Dopo i primi aspetti sintattici della logica proposizionale, occupia-moci ora della semantica, cioe del possibile significato delle formule.Da questo punto di vista, la forza espressiva della logica proposizionaleappare limitata, perche la semantica si riduce ad un’attribuzione deivalori di verita F o V.

Definizione 1.9. Si dice L-interpretazione l’attribuzione di unvalore di verita a ciascuna L-formula che sia coerente con le tavoledi verita dei connettivi; dunque una L-interpretazione e una funzioneI : Form(L)→ {F,V} tale che

I(¬A) =

{V se I(A) = F ;

F se I(A) = V.

I(A ∧ B) =

{V se I(A) = I(B) = V ;

F altrimenti.

I(A ∨ B) =

{F se I(A) = I(B) = F ;

V altrimenti.

I(A → B) =

{F se I(A) = V e I(B) = F ;

V altrimenti.

I(A ↔ B) =

{V se I(A) = I(B) ;

F altrimenti.

Le interpretazioni sono univocamente determinate dai valori di ve-rita che assegnano alle variabili.

Page 10: LOGICA MATEMATICA - unipi.it

10 1. CALCOLO PROPOSIZIONALE

Definizione 1.10. Si dice L-assegnamento l’attribuzione di un va-lore di verita a ciascuna variabile in L; dunque, un L-assegnamento euna funzione α : L → {F,V}.

E facile verificare che ogni assegnamento α : L → {F,V} si estendein modo unico ad un’interpretazione

α : Form(L)→ {F,V}.

Infatti, per definire α si procede per induzione sulla lunghezza ndelle formule. Quando n = 0, cioe per le variabili proposizionali A ∈ L,poniamo α(A) = α(A). Al passo induttivo, poniamo:

α(¬A) =

{V se α(A) = F ;

F se α(A) = V.

α(A ∧ B) =

{V se α(A) = α(B) = V ;

F altrimenti.

α(A ∨ B) =

{F se α(A) = α(B) = F ;

V altrimenti.

α(A → B) =

{F se α(A) = V e α(B) = F ;

V altrimenti.

α(A ↔ B) =

{V se α(A) = α(B) ;

F altrimenti.

Dunque, data un’interpretazione I : Form(L) → {F,V}, se deno-tiamo con α = I�L: L → {F,V} l’assegnamento ottenuto restringendoI ad L, deve essere α = I. Per questo, le due nozioni di assegnamentoe di interpretazione sono essenzialmente equivalenti.

Definizione 1.11. Una L-formula proposizionale A si dice veranell’interpretazione I se I(A) = V, e si dice falsa nell’interpretazioneI se I(A) = F.

Sia ora A una formula assegnata, e siano X1, . . . , Xn le variabiliproposizionali che vi occorrono. Dato un qualunque assegnamento I, efacile verificare che il valore di verita I(A) dipende soltanto dai valori diverita delle sue variabili: I(X1), . . . , I(Xn). Dunque, per determinarecompletamente la semantica di una formula assegnata al variare di tuttii possibili assegnamenti, e sufficiente considerare soltanto un numero

Page 11: LOGICA MATEMATICA - unipi.it

3. LE INTERPRETAZIONI 11

finito di casi, che possono essere visualizzati mediante le cosidette tavoledi verita.

In generale, se una formula contiene n variabili, la sua tavola diverita consistera di 2n righe, una per ognuno dei possibili assegnamentidi valori di verita alle sue variabili. Vediamo un esempio per illustrarecome si procede in pratica.

Consideriamo la formula “(X → Y ) ∧ ¬Z”. Ci sono 23 = 8 modipossibili di assegnare valori di verita alle 3 variabili X, Y e Z. Perciascuno di questi 8 casi, determiniamo il valore di verita delle sotto-formule “X → Y ” e “¬Z” e infine, a partire da questi, otteniamo ilvalore di verita della formula assegnata.

X Y Z X → Y ¬Z (X → Y ) ∧ (¬Z)V V V V F FV V F V V VV F V F F FV F F F V FF V V V F FF V F V V VF F V V F FF F F V V V

Piu formalmente, se A e una formula nella quale occorrono le va-riabili X1, . . . , Xn, allora la sua tavola di verita puo essere vista comeuna funzione

τA : Fun ({1, . . . , n}, {F,V}) −→ {F,V}.

Infatti, ogni assegnamento α dei valori di verita alle variabili di Apuo essere visto come una funzione χα : {1, . . . , n} → {F,V} do-ve intendiamo che χα(i) = α(Xi). Nella tavola di verita, ad ognunodi questi assegnamenti α ∈ Fun ({1, . . . , n}, {F,V}) viene associato ilcorrispondente valore di verita.

Esercizio 1.12. Dimostrare che per ogni funzione

f : Fun ({1, . . . , n}, {F,V}) −→ {F,V}

esiste una formula A nella quale compaiono le variabili X1, . . . , Xn taleche la corrispondente tavola di verita τA = f .

Page 12: LOGICA MATEMATICA - unipi.it

12 1. CALCOLO PROPOSIZIONALE

4. Formule soddisfacibili, tautologie, contraddizioni

Definizione 1.13. Sia A una L-formula proposizionale.

• A si dice soddisfacibile se e vera in almeno una interpretazione.

• A si dice tautologia se e vera in ogni interpretazione.

• A si dice contraddizione se e falsa in ogni interpretazione.

Dunque A e soddisfacibile se e solo se A non e una contraddizionese e solo se ¬A non e una tautologia. Notiamo che una formula esoddisfacibile se e solo se nella sua tabella di verita compare almenoun valore V. Analogamente, una formula e una tautologia (o unacontraddizione) se e solo se nella sua tabella di verita compaiono soloV (o solo F, rispettivamente).

Per quanto osservato sopra, verificare se una formula assegnata esoddisfacibile oppure no, e una tautologia oppure no, e una contraddi-zione oppure no, richiede una semplice procedura meccanica, e cioe lascrittura della corrispondente tavola di verita. Tuttavia tale proceduraha il difetto di richiedere molto “tempo” per essere eseguita. Ad esem-pio, supponiamo di voler stabilire se la formula seguente, che contienele 10 variabili proposizionali A,B, . . . , L, e una tautologia o meno.4[ (

A ∧B → C)→((D ∧ E → (F → G) )↔ (¬H → I ∧ L )

) ]↔[ (

(¬A ∨ (¬B ∨ C))→ (D ∧ F → (E → G)))↔((A→ (B → C))→ (H ∨ (I ∧ L))

) ]Nonostante si tratti di una formula che occupa lo spazio di due so-

le righe, non e consigliabile scriverne esplicitamente la tavola di verita.Questa consiste infatti di oltre 1.000 righe e vi compaiono piu di 36.000valori di verita! 5 Esistono altri metodi per controllare se una formulae una tautologia, che in molti casi pratici sono molto veloci. Tutta-via nei casi generali tutte le procedure note richiedono una quantitadi passaggi che cresce in modo esponenziale rispetto al numero dellevariabili. Il problema di stabilire se esistano metodi essenzialmente piuefficienti, cioe che permettano cioe di riconoscere le tautologie in tempopolinomiale anziche esponenziale, e tuttora irrisolto.6

Esercizio 1.14 (Modus Ponens). Se le formule A e A → B sonotautologie, allora anche B e una tautologia.

4 Per i curiosi: e una tautologia!5 Precisamente ci sono 210 = 1.024 righe, e un totale di 1.024·(10+26) = 36.864

valori di verita, in corrispondenza di ognuna delle 10 variabili e di ognuna delle 26sottoformule che si considerano.

6 Lo studio matematico di questo tipo di problemi rientra nell’ambito dellateoria della complessita, una delle intersezioni tra logica matematica e informaticateorica.

Page 13: LOGICA MATEMATICA - unipi.it

4. FORMULE SODDISFACIBILI, TAUTOLOGIE, CONTRADDIZIONI 13

Esercizio 1.15. Se la formula A e una tautologia, allora anche leformule A ∨ ¬A, A → A, A ↔ ¬¬A lo sono.

Esercizio 1.16 (Assiomi di Mendelson). Per ogni scelta delle for-mule A, B e C, verificare che le seguenti formule sono tautologie:

(1) A → (B → A) ;

(2) (A → (B → C))→ ((A → B)→ (A → C)) ;

(3) (¬A → ¬B)→ ((¬A → B)→ A).

Siano X1, . . . , Xn variabili che occorrono nella formula A, e sianoB1, . . . ,Bn formule arbitrarie. Denotiamo con

A(B1/X1, . . . ,Bn/Xn)

la formula ottenuta rimpiazzando in A tutte le occorrenze di Xi con Bi,per i = 1, . . . , n. Ad esempio, se A = (X → Y ) → ¬Z, B = Z → X,C = ¬W e D = Y → Z, allora

A(B/X, C/Y,D/Z) = ((Z → X)→ ¬W )→ ¬(Y → Z).

Piu in generale, se A e una formula e A1, . . . ,An sono sue sottofor-mule, allora denotiamo con

A(B1/A1, . . . ,Bn/An)

la formula ottenuta rimpiazzando in A tutte le occorrenze di A1 conB1, poi rimpiazzando nella formula cosı ottenuta tutte le occorrenze diA2 con B2, e cosı via.7

Esercizio 1.17. Siano X1, . . . , Xn variabili che occorrono nella for-mula A. Dimostrare che A e una tautologia se e solo se la formulaA(B1/X1, . . . ,Bn/Xn) e una tautologia per tutte le formule B1, . . .Bn.

Esercizio 1.18. Siano A1, . . . ,An sottoformule della formula Adove Ai non e sottoformula di Aj per ogni i 6= j. E vero che se A euna tautologia allora A(B1/A1, . . . ,Bn/An) e una tautologia per tut-

te le formule B1, . . .Bn? E vero che se A(B1/A1, . . . ,Bn/An) e unatautologia per tutte le formule B1, . . . ,Bn allora A e una tautologia?

7 Specificare l’ordine con cui si effettuano le sostituzioni e necessario affinchela definizione sia ben posta. Ad esempio, se A e la formula X ∨ (X → Y ), la sosti-tuzione A ((X → Y )/X, Y/(X → Y )) determina la formula Y ∨ (Y → Y ), mentrela sostituzione A (Y/(X → Y ), (X → Y )/X) produce (X → Y ) ∨ Y , come e facileverificare. Notiamo che questi problemi non si presentano quando si sostituisconoformule a variabili.

Page 14: LOGICA MATEMATICA - unipi.it

14 1. CALCOLO PROPOSIZIONALE

5. Equivalenze logiche

Due formule sono logicamente equivalenti se sono equivalenti dalpunto di vista semantico, cioe se non sono distinguibili da alcunainterpretazione. Precisamente:

Definizione 1.19. Diciamo che due formule A e B sono logicamen-te equivalenti, e scriviamo A ≡ B, se per ogni interpretazione I si hache I(A) = I(B).

Date due formule che contengono le stesse variabili, per vedere sesono logicamente equivalenti o no, si compilano le rispettive tavole diverita e si controlla se i corrispondenti valori di verita sono uguali omeno. Ad esempio, l’equivalenza logica (¬X ∨ Y ) ≡ (X → Y ) edimostrata dalla seguente tavola di verita:

X Y ¬X ¬X ∨ Y X → YV V F V VV F F F FF V V V VF F V V V

E immediato verificare la seguente

Osservazione 1.20. Due formule A e B sono logicamente equiva-lenti se e solo se la formula A ↔ B e una tautologia.

Qua sotto sono elencate alcune equivalenze logiche notevoli.

Esercizio 1.21. Verificare che le seguenti equivalenze logiche val-gono per ogni scelta delle formule A,B e C.

(1) Proprieta associative:

• A ∧ (B ∧ C) ≡ (A ∧ B) ∧ C ;

• A ∨ (B ∨ C) ≡ (A ∨ B) ∨ C ;

(2) Proprieta distributive:

• A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C) ;

• A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) ;

(3) Leggi di De Morgan:

• ¬(A ∧ B) ≡ ¬A ∨ ¬B ;

• ¬(A ∨ B) ≡ ¬A ∧ ¬B ;

(4) Contronominale: A → B ≡ ¬B → ¬A ;

(5) A → B ≡ ¬A ∨ B ;

(6) A ↔ B ≡ (A → B) ∧ (B → A) ≡ (A ∨ B) ∧ ¬(A ∧ B) ;

Page 15: LOGICA MATEMATICA - unipi.it

5. EQUIVALENZE LOGICHE 15

(7) A ∨ B ≡ ¬A → B ;

(8) A ∧ B ≡ ¬(A → ¬B).

Vista l’associativita (a meno di equivalenza logica) della congiun-zione e della disgiunzione, e consuetudine scrivere A1 ∧ . . . ∧ An oA1 ∨ . . . ∨ An senza uso di parentesi, perche tutte le possibili diversescritture sono comunque formule logicamente equivalenti.

Teorema 1.22 (di sostituzione). Siano A1, . . . ,An sottoformuledella formula A. Se Ai ≡ Bi per ogni i, allora A(B1/A1, . . . ,Bn/An) ≡A.

Dim. FARE �

Esercizio 1.23. Utilizzando le equivalenze logiche dell’Esercizio1.21 e il Teorema di sostituzione 1.22, dimostrare che la formula[ (

A ∧B → C)→((D ∧ E → (F → G) )↔ (¬H → I ∧ L )

) ]↔[ (

(¬A ∨ (¬B ∨ C))→ (D ∧ F → (E → G)))↔((A→ (B → C))→ (H ∨ (I ∧ L))

) ]menzionata a pagina 15 e una tautologia.

Nel nostro linguaggio abbiamo considerato 5 connettivi, cioe il con-nettivo unario ¬, e i connettivi binari ∨,∧,→,↔. Viste le equivalenze(5) e (6) dell’esercizio precedente, avremmo potuto restringerci a consi-derare i soli connettivi ¬,∨, e tutti gli altri sarebbero stati “definibili”a partire da quei due. Precisamente, vale la seguente proprieta, la cuiverifica e lasciata per esercizio.

Osservazione 1.24. Per ogni formula A esiste una formula B ≡ Anella quale compaiono i soli connettivi ¬,∨.

Dim. FARE �

Esercizio 1.25. Dimostrare che la proprieta di sopra vale se alposto dei due connettivi ¬,∨ consideriamo ¬,∧ oppure ¬,→ ; ma nonvale se consideriamo i due connettivi ∨,→ oppure ∧,∨ oppure →,↔,oppure ¬,↔.

In realta avremmo potuto ridurci a considerare addirittura un unicoconnettivo, ma a questo scopo avremmo dovuto definirne uno nuovo.

Definizione 1.26. Il connettivo binario “entrambe false” l e de-terminato dalla seguente tavola di verita:

P Q P l QV V FV F FF V FF F V

Page 16: LOGICA MATEMATICA - unipi.it

16 1. CALCOLO PROPOSIZIONALE

Esercizio 1.27. Per ogni formula A esiste una formula B ≡ Anella quale compare soltanto il connettivo l.

Definizione 1.28. Si dice letterale una variabile proposizionaleX o la sua negazione ¬X. Una formula si dice in forma normaledisgiuntiva (DNF) se e una disgiunzione di congiunzione di letterali;si dice in forma normale congiuntiva (CNF) se e una congiunzione didisgiunzioni di letterali.

Ad esempio, la formula A qua sotto e DNF, la formula B e CNF,ma la formula C non e ne DNF ne CNF:

A = (¬X1∧X2)∨X3 ; B = X1∧(¬X2∨X2) ; C = (X1∨¬X2)∨(X3∧X4) .

Esercizio 1.29. Dimostrare che ogni formula e logicamente equi-valente ad una formula DNF e ad una formula CNF.

Esercizio 1.30. Denotiamo con A∗ la formula che si ottiene da Asostituendo simultaneamente ogni simbolo ∧ con ∨, e ogni simbolo ∨con ∧. Dimostrare che A ≡ B se e solo se A∗ ≡ B∗.

6. Implicazione logica

Un altro fondamentale concetto semantico e quello di implicazionelogica. Una formula ne implica logicamente un’altra se ogni volta chee vera la prima e vera anche la seconda.

Definizione 1.31. Diciamo che la formula A implica logicamentela formula B, o che B e conseguenza logica di A, se per ogni interpre-tazione I dove I(A) = V, si ha anche I(B) = V. In questo caso si usala notazione A |= B.

Supponiamo di avere compilato la tavola di verita di due formuleA e B contenenti le stesse variabili. Avremo allora che A |= B se e solose in ogni riga dove compare V per la formula A compare V anche perla formula B. Ad esempio, consideriamo le formule A = ¬X ↔ Y eB = X∨Y . Nella seconda e terza riga, che sono le uniche dove compareil valore V per la formula A, c’e il valore V anche per la formula B.Dunque concludiamo che A |= B.

X Y ¬X ¬X ↔ Y X ∨ YV V F F VV F F V VF V V V VF F V F F

Page 17: LOGICA MATEMATICA - unipi.it

6. IMPLICAZIONE LOGICA 17

E immediato verificare che vale la:

Osservazione 1.32. A |= B se e solo se la formula A → B e unatautologia.

E importante osservare che l’implicazione → (chiamata anche im-plicazione materiale) e l’implicazione logica |= sono sostanzialmentediverse. La prima e un simbolo che fa parte del linguaggio formale, dun-que e un oggetto puramente sintattico. La seconda invece e di naturasemantica, ed e una relazione “metalinguistica” (cioe non appartenenteal linguaggio formale) che puo sussistere tra formule proposizionali.

Una considerazione puo aiutare a chiarire la differenza. Assegnatedue formule qualunque A e B, almeno una delle due implicazioni

A → B , B → Arisulta vera in una qualunque interpretazione. Infatti, A → B e falsasoltanto quando A e vera e B e falsa, ma in questo caso e l’altra im-plicazione B → A ad essere vera. Tuttavia, non necessariamente unadelle due formule implica logicamente l’altra. In altri termini, mentre(A → B) ∨ (B → A) e una tautologia, non si ha necessariamente cheuna tra le due formule A → B, B → A, lo sia. Ad esempio, se X e Ysono due variabili, ne la formula X → Y ne la formula Y → X e unatautologia, mentre la formula (X → Y ) ∨ (Y → X) lo e.

Esercizio 1.33. Verificare le seguenti implicazioni logiche, dove Ae B sono formule qualunque:

(1) (A ∧ B) |= A ;

(2) A |= (A ∨ B) ;

(3) Se A |= B e B |= C, allora A |= C ;

(4) A |= B se e solo se ¬B |= ¬A.

Esercizio 1.34. Stabilire se ciascuna delle seguenti proprieta e veraper ogni scelta delle formule A,B e C.

(1) Se A |= B e A |= C, allora A |= (B ∧ C) ;

(2) Se A |= (B ∧ C), allora A |= B e A |= C ;

(3) Se A |= C o B |= C, allora (A ∨ B) |= C ;

(4) Se (A ∨ B) |= C, allora A |= C o B |= C ;

(5) Se A |= B e A |= C, allora B |= C .

(6) Se A |= B e A |= (B → C), allora A |= C.

Page 18: LOGICA MATEMATICA - unipi.it
Page 19: LOGICA MATEMATICA - unipi.it

CAPITOLO 2

Teorie proposizionali e modelli

1. Teorie proposizionali

Definizione 2.1. Per teoria del calcolo proposizionale si intendeun qualunque insieme (eventualmente vuoto) di L-formule.

Introduciamo ora alcune importanti nozioni semantiche.

Definizione 2.2. Si dice che l’interpretazione I e un modello dellateoria T , e si scrive I |= T , se I rende vera T , cioe se I(A) = V pertutte le formule A ∈ T .

Diamo ora una generalizzazione della nozione di implicazione logicaA |= B vista nel paragrafo precedente.

Definizione 2.3. Diciamo che la teoria T implica logicamente laformula B, o che B e conseguenza logica di T , se B e vera in ognimodello di T . In questo caso scriviamo T |= B.

Esercizio 2.4. Dimostrare che:

(1) T |= A e T |= B se e solo se T |= A ∧ B ;

(2) Se T |= A o T |= B allora T |= A ∧ B ;

(3) Se T |= A e T |= A → B allora T |= B.

Dimostrare con un controesempio che non vale l’implicazione:

(4) Se T |= A ∨ B allora T |= A o T |= B.

Proposizione 2.5 (Procedimento per casi). Sia T una teoria eA,B formule. Se T ∪ {B} |= A e T ∪ {¬B} |= A allora T |= A.

Dim. Dimostriamo la contronominale, e supponiamo che T 6|= A,cioe che esista un modello I di T dove A e falsa. Si hanno due possibi-lita. Se B e vera in I, allora I e un modello di T ∪ {B}, e concludiamoche T ∪ {B} 6|= A; se B e falsa in I, allora I e un modello di T ∪ {¬B},e abbiamo che T ∪ {¬B} 6|= A. �

Vale la seguente proprieta.

19

Page 20: LOGICA MATEMATICA - unipi.it

20 2. TEORIE PROPOSIZIONALI E MODELLI

Teorema 2.6 (Deduzione semantica). Sia T una teoria e sianoA1, . . . ,An,B formule. Allora 1

T,A1, . . . ,An |= B ⇐⇒ T |= A1 ∧ . . . ∧ An → B .

Notiamo che quando T = ∅ e n = 1, ritroviamo la nozione diimplicazione logica A1 |= B introdotta nella Definizione 1.31.

Dim. ⇒ Fissato un modello I |= T , distinguiamo due casi. Seogni Ai e vera in I, allora A1 ∧ . . . ∧ An e vera in I, e dunque I e unmodello di T ∪{A1, . . . ,An}. Dall’ipotesi segue che B e vera in I. Vistoche A1 ∧ . . . ∧ An e B sono entrambe vere in I, anche l’implicazioneA1 ∧ . . . ∧ An → B e vera in I. Se invece c’e una formula Ai che efalsa in I, allora A1 ∧ . . . ∧ An e falsa in I e dunque l’implicazioneA1 ∧ . . . ∧An → B e vera in I a prescindere dalla verita o falsita di B.

⇐ Sia I e un modello di T ∪ {A1, . . . ,An}. Visto che A1, . . .Ansono tutte vere in I, anche A1 ∧ . . . ∧ An e vera in I. Visto che I e inparticolare un modello di T , per ipotesi l’implicazioneA1∧. . .∧An → Be vera in I. Ne segue che necessariamente B e vera in I. �

Definizione 2.7. Una teoria T si dice soddisfacibile se ammetteun modello; si dice insoddisfacibile in caso contrario.

Osservazione 2.8. Sia T una teoria. Le seguenti proprieta sonoequivalenti:

(1) T e soddisfacibile ;

(2) Per ogni formula A, se T |= A allora T 6|= ¬A ;

(3) Esiste almeno una formula B con T 6|= B.

Dim. (1)⇒ (2). Sia I un modello di T . Se T |= A, allora A e verain I e dunque ¬A e falsa in I. Concludiamo che T 6|= ¬A.

(2)⇒ (3). Se per assurdo la tesi non valesse, per ogni formula A siavrebbe sia T |= A che T |= ¬A, contro l’ipotesi.

(3) ⇒ (1). Per ipotesi deve esistere un’interpretazione I che emodello di T e dove B e falsa. In particolare T e soddisfacibile. �

Dunque T e contraddittoria se e solo se esiste una formula A taleche T |= A e T |= ¬A, se e solo se tutte le formule sono conseguenzalogica di T .

Proposizione 2.9 (Reductio ad absurdum). Sia T una teoria e Auna formula. Allora T |= A ⇔ T ∪ {¬A} e insoddisfacibile.

1 Con abuso di notazione, in accordo con la consuetudine, abbiamo scrittoT,A1, . . . ,An |= B per intendere T ∪ {A1, . . . ,An} |= B.

Page 21: LOGICA MATEMATICA - unipi.it

1. TEORIE PROPOSIZIONALI 21

Dim. ⇒. Se T ∪ {¬A} fosse soddisfacibile, esisterebbe un suo mo-dello I. Un tale I sarebbe un modello di T dove ¬A e falsa, e quindidove A e vera. Concludiamo che T 6|= A.

⇐. Sia I un modello di T . Per l’ipotesi, I non e un modello diT ∪ {¬A}, dunque ¬A e falsa in I, e quindi A e vera in I. Abbiamomostrato che ogni modello di T e anche modello di A, cioe la tesi.2 �

Esercizio 2.10. Supponiamo che T |= A → B.

(1) Dimostrare che se la teoria T ∪ {B} e insoddisfacibile, alloraanche T ∪ {A} e insoddisfacibile.

(2) E vera l’implicazione inversa della (1)?

Proposizione 2.11. Sia T una teoria soddisfacibile e A una for-mula. Allora T ∪ {A} e soddisfacibile o T ∪ {¬A} soddisfacibile.

Dim. Se T ∪ {¬A} e contraddittoria, allora abbiamo visto che ne-cessariamente T |= A. In questo caso, se I e un modello di T allora Ie anche un modello di T ∪ {A}. �

Definizione 2.12. Una teoria T si dice semanticamente completase per ogni formula A vale una ed una sola delle due proprieta: T |= A,T |= ¬A.

Esercizio 2.13. Sia T una teoria. Verificare che sono proprietaequivalenti:

(1) T e semanticamente completa ;

(2) Per ogni formula A, vale T |= A ⇔ T 6|= ¬A ;

(3) T e soddisfacibile e per ogni formula A, T 6|= A ⇒ T |= ¬A ;

(4) T ha un unico modello .

Esercizio 2.14. Sia T una teoria soddisfacibile. Dimostrare chesono proprieta equivalenti:

(1) T e completa ;

(2) Per tutte le formule A,B, vale T |= A∨B ⇔ T |= A o T |= B ;

(3) Per tutte le formule A,B, vale T 6|= A → B ⇔ T |= A eT |= ¬B .

L’insieme delle conseguenze logiche di una teoria T e denotato con

Con(T ) = {A | T |= A}.

2 Notiamo che non stiamo assumendo che T abbia modelli. Nel caso in cui Tfosse contraddittoria, avremmo che T |= A per ogni formula A.

Page 22: LOGICA MATEMATICA - unipi.it

22 2. TEORIE PROPOSIZIONALI E MODELLI

Con questa terminologia, Con(∅) e l’insieme delle tautologie. Infat-ti, banalmente, tutte le interpretazioni sono modelli della teoria vuotaT = ∅.

Definizione 2.15. Una teoria T si dice semanticamente chiusa seT = Con(T ), cioe se T |= A ⇒ A ∈ T .

Proposizione 2.16. Sia T una teoria. Allora:

(1) T e soddisfacibile se e solo se Con(T ) e soddisfacibile ;

(2) Con(T ) e una teoria semanticamente chiusa.

Dim. (1). Banalmente T ⊆ Con(T ), e dunque se Con(T ) e sod-disfacibile, anche T lo e. Viceversa, se I e modello di T allora I eanche modello di Con(T ), perche se B ∈ Con(T ), cioe se T |= B, perdefinizione di conseguenza logica abbiamo che B e vera in I.

(2). Una inclusione e immediata perche T ⊆ Con(T )⇒ Con(T ) ⊆Con(Con(T )). Per l’altra inclusione, supponiamo che B /∈ Con(T ), cioeche T 6|= B, e prendiamo un modello I |= T dove B e falsa. Abbiamonotato sopra che una tale interpretazione I e anche modello di Con(T ),e quindi Con(T ) 6|= B, cioe B /∈ Con(Con(T )). �

Proposizione 2.17. Sia T una teoria. Sono proprieta equivalenti:

(1) T e semanticamente chiusa e completa ;

(2) T e massimale rispetto all’inclusione tra le teorie soddisfacibili.

Dim. (1) ⇒ (2). Supponiamo per assurdo che esista un teoriasoddisfacibile T ′ che estende propriamente T , e prendiamo A ∈ T ′ \ T .Per ipotesi esiste un modello I di T ′; in particolare, I e un modello diT dove A e vera, e dunque dove ¬A e falsa. Di conseguenza, T 6|= ¬A.Abbiamo quindi che A /∈ T e ¬A /∈ Con(T ) = T , visto che T esemanticamente chiusa. Questo contraddice l’ipotesi di T completa.

(2)⇒ (1). Supponiamo che T |= A. Prendiamo un modello I di T .La formula A e vera in I, e dunque I e anche un modello di T ∪ {A},che e quindi una teoria consistente. Per la massimalita di T deve essereT ∪ {A} = T , cioe A ∈ T . Questo mostra che T e chiusa. Visto che Te soddisfacibile, per mostrare la completezza resta da vedere che valel’implicazione T 6|= A ⇒ T |= ¬A. Se T 6|= A, per la Proposizione 2.9,la teoria T∪{¬A} e soddisfacibile, e per la massimalita di T deve essereallora T ∪ {¬A} = T , quindi ¬A ∈ T , e banalmente T |= ¬A. �

Il prossimo esempio illustra come il concetto di modello di una teoriaproposizionale possa catturare le strutture matematiche.

Page 23: LOGICA MATEMATICA - unipi.it

2. IL TEOREMA DI COMPATTEZZA SEMANTICO 23

Esempio 2.18. Dato un insieme A, consideriamo il linguaggio pro-posizionale

L = {Xab | a, b ∈ A}contenente una variabile per ogni coppia ordinata di elementi di A. SiaT la teoria che consiste delle seguenti formule:

• ¬Xaa per ogni a ∈ A ;

• Xab → ¬Xba per ogni a, b ∈ A ;

• (Xab ∧Xbc)→ Xac per ogni a, b, c ∈ A ;

• Xab ∨Xba per ogni a, b ∈ A con a 6= b.

Per ogni L-interpretazione I, definiamo la corrispondente relazionebinaria ≺I su A ponendo a ≺I b ⇔ I(Xab) = V. Come si verificadirettamente, I |= T se e solo ≺I e un ordine totale stretto su A.

2. Il Teorema di compattezza semantico

Definizione 2.19. Una teoria T si dice finitamente soddisfacibile(FS) se ogni suo sottoinsieme finito T ′ ⊆ T e soddisfacibile.

Proposizione 2.20. Sia T una teoria finitamente soddisfacibile(FS). Allora per ogni formula A, T ∪ {A} e FS o T ∪ {¬A} e FS.

Dim. Supponiamo per assurdo che esistano insiemi finiti contrad-dittori

{B1, . . . ,Bn} ⊆ S ∪ {A} e {C1, . . . , Cm} ⊆ S ∪ {¬A}.Visto che T e FS, necessariamente {B1, . . . ,Bn} * T e {C1, . . . , Cm} *T , e quindi A ∈ {B1, . . . ,Bn} e ¬A ∈ {C1, . . . , Cm}. Senza perditadi generalita, supponiamo che Bn = A e Cm = ¬A. Prendiamo unmodello I dell’insieme finito {B1, . . . ,Bn−1, C1, . . . , Cm−1} ⊆ T . Se Ae vera in I, allora B1, . . . ,Bn = A sono tutte vere in I, contro l’as-sunzione di {B1, . . . ,Bn} contraddittorio; analogamente, se A e falsain I, allora C1, . . . , Cm = ¬A sono tutte vere in I, contro l’assunzio-ne di {C1, . . . , Cm} contraddittorio. Abbiamo cosı ottenuto l’assurdocercato. �

Un risultato fondamentale, che mette in evidenza la natura finiti-stica del concetto di conseguenza logica, e il seguente:

Teorema 2.21 (Compattezza semantica).Sia T una teoria proposizionale. Valgono le due seguenti proprietaequivalenti:

Page 24: LOGICA MATEMATICA - unipi.it

24 2. TEORIE PROPOSIZIONALI E MODELLI

(1) Per ogni formula A, T |= A se e solo se esiste una quantitafinita di formule B1, . . . ,Bn ∈ T tali che B1, . . . ,Bn |= A ;

(2) Se T e finitamente soddisfacibile allora T e soddisfacibile.

Dim. Dimostriamo anzitutto l’equivalenza delle due proprieta.

(1)⇒ (2). Se T non e soddisfacibile allora, per l’Osservazione 2.8,esiste una formula A tale che T |= A e T |= ¬A. Per l’ipotesi, esisteallora una quantita finita di formule B1, . . . ,Bn, C1, . . . , Cm in T taliche B1, . . . ,Bn |= A e C1, . . . , Cm |= ¬A. Di nuovo per l’Osservazione2.8, concludiamo che la teoria finita {B1, . . . ,Bn, C1, . . . , Cm} ⊆ T econtraddittoria, e quindi T non e finitamente soddisfacibile.

(2)⇒ (1). Se B1, . . . ,Bn ∈ T , banalmente B1, . . . ,Bn |= A ⇒ T |=A. Viceversa, supponiamo che per ogni scelta di B1, . . . ,Bn ∈ T siaB1, . . . ,Bn 6|= A, cioe esista un’interpretazione I dove B1, . . . ,Bn sonovere e A e falsa. Questo mostra che la teoria T ∪ {¬A} e finitamentesoddisfacibile e dunque, per l’ipotesi, esiste un modello I |= T ∪{¬A}.Concludiamo che T 6|= A.

Mostriamo ora che vale la proprieta (2). Consideriamo la seguentefamiglia, parzialmente ordinata per inclusione:

T = {S ⊇ T | S finitamente soddisfacibile (f.s.) }.Banalmente T 6= ∅ perche T ∈ T per ipotesi. Data 〈Si | i ∈ I〉una catena crescente in T , consideriamo l’unione S =

⋃i∈I Si. Se

S ′ = {A1, . . . ,An} ⊆ S e un suo sottoinsieme finito, per ogni t =1, . . . , n prendiamo it ∈ I tale che At ∈ Sit . Chiaramente S ′ ⊆ Sjdove j = max{i1, . . . , in}, e quindi S ′ ha un modello, visto che Sj ef.s. Questo mostra che S ∈ T e f.s., ed e un elemento maggiorantedella catena. Possiamo allora applicare il Lemma di Zorn, ed ottenerel’esistenza di un elemento massimale Smax ∈ T . Mostreremo che Smax(e quindi T ) ha un modello. Ci occorrono le seguenti proprieta:

(a) A ∈ Smax ⇔ ¬A /∈ Smax.(b) Se A ∈ Smax e A |= A′ allora A′ ∈ Smax.3 Di conseguenza, seA ≡ A′, allora A ∈ Smax ⇔ A′ ∈ Smax.

(a). Se per assurdo fosse A ∈ Smax e ¬A ∈ Smax, allora {A,¬A} ⊆Smax sarebbe un sottoinsieme finito di Smax insoddisfacibile. Inoltre,anche assumere ¬A /∈ Smax e A /∈ Smax porta ad un assurdo. Infatti,

3 Notiamo che questa proprieta e piu debole della proprieta di Smax semanti-camente chiusa. In realta, una volta dimostrato questa teorema di compattezza,si potra concludere che Smax e in effetti una teoria semanticamente chiusa perchesoddisfacibile massimale (cf. Proposizione 2.17). Per il momento pero, possiamosolo assumere che Smax e finitamente soddisfacibile.

Page 25: LOGICA MATEMATICA - unipi.it

2. IL TEOREMA DI COMPATTEZZA SEMANTICO 25

per la Proposizione 2.20, sappiamo che almeno una tra le teorie Smax∪{A} ! Smax e Smax ∪ {¬A} ! Smax e FS, contro la massimalita diSmax.

Per dimostrare (b), supponiamo per assurdo che A′ /∈ Smax. Allo-ra, per la (a), deve essere ¬A′ ∈ Smax. Notiamo che l’insieme finito{A,¬A′} ⊆ Smax e insoddisfacibile, perche per l’ipotesi, in ogni inter-pretazione dove A e vera, anche A′ e vera, e quindi ¬A′ e falsa. Questocontraddice l’ipotesi di finita soddisfacibilita di Smax.

Siamo finalmente pronti a costruire un modello di Smax, e quindi diT . Lo facciamo prendendo la seguente interpretazione:

I(A) =

{V se A ∈ Smax ;

F se A /∈ Smax.

Dobbiamo verificare verificare che I e effettivamente un’interpreta-zione, cioe che I soddisfa le seguenti proprieta.

(1) I(¬A) = V se I(A) = F, e I(¬A) = F se I(A) = V ;

(2) I(A∧B) = V se I(A) = I(B) = V, e I(A∧B) = F altrimenti ;

(3) I(A∨B) = F se I(A) = I(B) = F, e I(A∨B) = V altrimenti ;

(4) I(A → B) = F se I(A) = V e I(B) = F, e I(A → B) = Faltrimenti ;

(5) I(A ↔ B) = V se I(A) = I(B), e I(A ↔ B) = F altrimenti.

La (1) segue direttamente dalla proprieta (a) di sopra.

La proprieta (2) equivale a mostrare l’equivalenza A∧B ∈ Smax ⇔A ∈ Smax e B ∈ Smax. Visto che A∧B |= A e A∧B |= B, l’implicazione⇒ segue dalla proprieta (b) di sopra. Viceversa, se fosse A∧B /∈ Smax,allora ¬(A ∧ B) ∈ Smax, e si avrebbe l’insieme finito insoddisfacibile{A,B,¬(A ∧ B)} ⊆ Smax.

Gli altri casi (3), (4), e (5), seguono da (1) e (2) usando rispettiva-mente le equivalenze logiche:

• A ∨ B ≡ ¬(¬A ∧ ¬B) ;• A → B ≡ ¬(A ∧ ¬B) ;• A ↔ B ≡ ¬(A ∧ ¬B) ∧ ¬(¬A ∧ B).

A titolo di esempio vediamo la (3); per le altre si procede in mododel tutto simile. I(A ∨ B) = F ⇔ (per definizione) A ∨ B /∈ Smax ⇔(per la (b)) ¬(¬A∧¬B) /∈ Smax ⇔ (per la (1)) ¬A∧¬B ∈ Smax ⇔ (perla (2)) ¬A ∈ Smax e ¬B ∈ Smax ⇔ (per la (1)) A /∈ Smax e B /∈ Smax,cioe I(A) = I(B) = F. �

Page 26: LOGICA MATEMATICA - unipi.it

26 2. TEORIE PROPOSIZIONALI E MODELLI

In molte applicazioni, il Teorema di compattezza permette di dimo-strare proprieta generali a partire dai soli casi finiti. Vediamo subitoun esempio.

Teorema 2.22. Ogni ordinamento parziale si puo estendere ad unordinamento totale; cioe, per ogni insieme parzialmente ordinato (A,<)esiste un ordinamento totale (A,≺) tale che a < b⇒ a ≺ b.

Dim. Dimostriamo prima il caso finito:

• L’enunciato del teorema e vero se A e un insieme finito.

Procediamo per induzione sulla cardinalita n = |A|. La base n = 1e banale. Se |A| = n + 1, fissiamo un elemento a∗ ∈ A. Per ipotesiinduttiva su B = A\{a∗}, esiste un ordine totale (B,≺) dove ≺ estende<. Finalmente definiamo:

• a∗ ≺′ b se a∗ < b ;• b ≺′ a∗ se b < a∗ o se a e b non sono confrontabili in (A,<) ;• b ≺′ c se b, c ∈ B e b ≺ c.

E facile verificare che (A,≺′) e un ordine totale che estende (A,<).

Occupiamoci ora del caso generale usando gli strumenti del calcoloproposizionale. Sia L = {Xab | a, b ∈ A} il linguaggio proposizio-nale contenente una variabile per ogni coppia ordinata di elementi diA, e sia S la teoria ottenuta aggiungendo alla teoria T come definitanell’Esempio 2.18, le seguenti formule:

• Xab per ogni a, b ∈ A con a < b.

Notiamo che la tesi equivale a trovare un modello I della teoria S;infatti, in questo caso, basta porre a ≺ b⇔ I(Xab) = V.

Per il teorema di compattezza, trovare un modello di S equivale atrovare un modello per ogni sottoinsieme finito S ′ ⊂ S. Sia

A′ = {a, b | Xab occorre in una formula A ∈ S ′}.Denotiamo con (A′, <) la restrizione dell’ordine parziale (A,<) al sot-toinsieme A′. Visto che S ′ e finito, e visto che in ogni formula occorronosolo un numero finito di variabili Xab, anche A′ e finito. Per quantovisto sopra, esiste allora un ordine totale (A′,≺) che estende (A′, <).Prendiamo una qualunque interpretazione I tale che, per ogni a, b ∈ A′,

I(Xab) =

{V se a ≺ b

F altrimenti.

Si verifica direttamente che I e un modello di S ′. �

Sia (P,≤) un insieme parzialmente ordinato. Ricordiamo che dueelementi a, b ∈ P si dicono confrontabili se a ≤ b o b ≤ a; altrimenti,

Page 27: LOGICA MATEMATICA - unipi.it

2. IL TEOREMA DI COMPATTEZZA SEMANTICO 27

si dicono inconfrontabili. Una catena di P e un sottoinsieme C ⊆ Ple cui coppie sono tutte confrontabili. Un’anticatena e un sottoinsiemeC ⊆ P le cui coppie di elementi distinti sono tutte inconfrontabili.

Esercizio 2.23. Sia (P,≤) un insieme parzialmente ordinato ek ∈ N. Usando il Teorema di compattezza, dimostrare che se ognisottoinsieme finito di P e unione di k catene, allora anche P e unionedi k catene.

Ricordiamo il seguente risultato combinatorio:

• Teorema di Dilworth. Sia (P,≤) un insieme parzialmente or-dinato. P e l’unione di k catene se e solo se ogni anticatenaha cardinalita ≤ k.

Esercizio 2.24.∗ Usando il Teorema di compattezza, dimostrareche il Teorema di Dilworth segue dalla sua validita per i soli insiemiparzialmente ordinati finiti.

Ricordiamo che un grafo Γ su V e una coppia Γ = 〈V, L〉 doveV e un insieme di elementi detti vertici, e L e un insieme di coppiedi elementi distinti di V , detti lati. Un grafo Γ′ = 〈V ′, L′〉 si dicesottografo di Γ se V ′ ⊆ V e L′ ⊆ L.

Un grafo Γ = 〈V, L〉 si dice k-colorabile se si possono colorare ivertici con k colori, in modo che nessun lato abbia vertici dello stessocolore; piu formalmente, se esiste una funzione f : V → {1, . . . , k} taleche f(a) 6= f(b) per ogni {a, b} ∈ L.

Un grafo si dice connesso se ogni coppia di vertici distinti e collegatada un “percorso” sui lati, cioe se per ogni a, b ∈ V con a 6= b esisteuna sequenza finita 〈x1, . . . , xn〉 dove x1 = a e xn = b, e tale che{xi, xi+1} ∈ L per ogni 1 ≤ i < n.

Sia µ un cardinale, e sia Lµ il linguaggio proposizionale avente unavariabile Xa,b per ogni coppia ordinata (a, b) ∈ µ× µ. Denotiamo conT µG la seguente Lµ-teoria:

T µG = {¬Xa,a | a ∈ µ} ∪ {Xa,b ↔ Xb,a | (a, b) ∈ µ× µ}.

Esercizio 2.25. Verificare che se I e un modello di T µG, alloraΓI = 〈µ, LI〉 dove LI = {{a, b} | Xa,b e vera in I} e un grafo. Verificareinoltre che la corrispondenza I 7→ ΓI determina una funzione biunivocatra l’insieme dei modelli di T µG e l’insieme dei grafi su µ.

Esercizio 2.26. Per ogni cardinale µ e per ogni k ∈ N, trovare unateoria proposizionale con la proprieta che I e modello di T se e solo seΓI e un grafo k-colorabile.

Page 28: LOGICA MATEMATICA - unipi.it

28 2. TEORIE PROPOSIZIONALI E MODELLI

Esercizio 2.27. Usando il Teorema di compattezza, dimostrareche se ogni sottografo finito di un grafo Γ e k-colorabile, allora ancheΓ e k-colorabile.

Mentre il concetto di grafo k-colorabile e formalizzabile nel linguag-gio proposizionale, la nozione di grafo connesso non lo e, come mostrail seguente

Esercizio 2.28.∗ Per ogni µ infinito, dimostrare che non esistealcuna teoria proposizionale T con la proprieta che I e un modello diT se e solo se ΓI e un grafo connesso su µ.

Esercizio 2.29.∗ Senza usare alcuna forma dell’assioma di scelta,dimostrare l’equivalenza delle seguenti proprieta:

(1) Teorema semantico di compattezza (Teorema 2.21) ;

(2) Compattezza dei prodotti dello spazio topologico 2 = {0, 1}:“Tutti i prodotti topologici 2Y sono compatti”.4

3. Sistemi dimostrativi

Torniamo ora sul versante sintattico, e introduciamo la nozione for-male di dimostrazione. Si tratta di un concetto generale della logica cheuseremo – oltre che per il calcolo proposizionale – anche per il calcolodei predicati del primo ordine.

Definizione 2.30. Un sistema dimostrativo S consiste di:

(1) un insieme “effettivo” di formule AX, chiamate assiomi logici ;

(2) un numero finito di regole deduttive o regole di inferenza chesono relazioni “effettive” tra formule e formule (regole unarie)o fra coppie ordinate di formule e formule (regole binarie).5

Se R e una regola deduttiva unaria e vale R(A,B), diciamo che Adeduce B o che B si deduce da A applicando la regola R, e scriviamo:

A RBAnalogamente, se R e una regola binaria, diciamo che la coppia or-

dinata (A,A′) deduce B o che B si deduce dalla coppia ordinata (A,A′),applicando la regola R, quando vale R((A,A′),B). In questo casoscriviamo:

4 Quando Y = N, il prodotto infinito 2Y e noto come spazio di Cantor.5 Piu in generale, si potrebbero considerare anche regole n-arie con n ∈ N

qualunque, cioe relazioni tra n-uple ordinate di formule e formule. Tuttavia neisistemi formali che vedremo, ci basteranno le regole unarie e binarie.

Page 29: LOGICA MATEMATICA - unipi.it

3. SISTEMI DIMOSTRATIVI 29

A A′ RBPossiamo finalmente definire una nozione generale di dimostrazione.

Definizione 2.31. Sia S un sistema dimostrativo, T una teoria eA una formula. Diciamo che T dimostra A col sistema dimostrativoS, e scriviamo

T `S A ,se esiste una sequenza finita di formule 〈B0, . . . ,Bn〉 dove l’ultima for-mula Bn = A e dove per ogni k ≤ n:

• Bk appartiene a T o e un assioma logico (cioe Bk ∈ T ∪ AX);

oppure

• esiste una regola di inferenza unaria R del sistema S, ed esistei < k tale che

Bi RBkoppure

• esiste una regola di inferenza binaria R del sistema S, ed esi-stono formule Bi,Bj con i, j < k tali che

Bi BjRBk

In tal caso, A si dice teorema di T (col sistema dimostrativo S), ela sequenza 〈B0, . . . ,Bn = A〉 si dice dimostrazione di A nella teoria T(col sistema dimostrativo S).

E immediato dalle definizioni che valgono le seguenti proprietafondamentali:

Proposizione 2.32. Sia S un sistema dimostrativo. Allora:

(1) (Compattezza sintattica) T `S A se e solo se esiste una quan-tita finita di formule B1, . . . ,Bn ∈ T tali che B1, . . . ,Bn `SA.

(2) (Monotonicita) Se T `S A e T ′ ⊇ T allora anche T ′ `S A.

Notiamo che (1) afferma il carattere di finitista del concetto di di-mostrazione, mentre (2) afferma che se una certa proposizione si deduceda insieme di assunzioni, allora si continua a dedurla anche aggiungen-do ulteriori assunzioni.6 Supponiamo che la teoria T sia “effettiva”. E

6 Quest’ultima proprieta non e in accordo con la nozione di deduzione nellinguaggio naturale; infatti puo capitare che aggiungendo nuove conoscenze, sidebbano rivedere precedenti deduzioni.

Page 30: LOGICA MATEMATICA - unipi.it

30 2. TEORIE PROPOSIZIONALI E MODELLI

importante osservare che in questo caso anche la nozione di dimostra-zione nella teoria T e un concetto “effettivo”, cioe esiste una proceduracalcolabile per verificare se una data stringa finita di formule e una di-mostrazione nella teoria T oppure no. Tuttavia, in genere, la nozionedi teorema di T non e “effettiva”, cioe potrebbe non esistere una pro-cedura calcolabile che consenta di verificare se una formula assegnata eteorema di T oppure no (nel fissato sistema dimostrativo S). Come ve-dremo piu avanti, ci sono comunque alcuni importanti esempi di teorieper cui questo tipo di verifica e possibile (tali teorie si chiamano teoriedecidibili).

Denotiamo ora con

TeorS(T ) = {A | T `S A}l’insieme dei teoremi di T col sistema dimostrativo S.

Teorema 2.33. Per ogni sistema dimostrativo S e per ogni teoriaT si ha TeorS(TeorS(T )) = TeorS(T ).

Dim. FARE �

La seguente nozione di coerenza e il corrispettivo sintattico dellanozione semantica di soddisfacibilita.

Definizione 2.34. Una teoria T si dice coerente nel sistema S seesiste almeno una formula B con T 6`S B; si dice contraddittoria in casocontrario.

Segue immediatamente dal Teorema 2.33 che una teoria e coerentenel sistema S se e solo se TeorS(T ) e coerente.

4. Completezza del calcolo proposizionale

Definizione 2.35. Sia S0 il sistema dimostrativo del calcolo pro-posizionale dove:

• Gli assiomi logici AX sono tutte e sole le tautologie ;

• L’unica regola di inferenza (binaria) e il modus ponens MP :

A A → B MPBNotiamo che S0 ha le proprieta di “effettivita” richieste. Ricordiamo

infatti che, data una formula A, esiste una procedura “effettiva” perverificare se si tratta di una tautologia oppure no (si compila la suatavola di verita e si controlla se compaiono solo V nell’ultima colonnaoppure no).

Page 31: LOGICA MATEMATICA - unipi.it

4. COMPLETEZZA DEL CALCOLO PROPOSIZIONALE 31

Un’utile regola di inferenza che puo essere derivata dagli assiomilogici e dalle regola di modus ponens e la seguente.

Proposizione 2.36 (Regola di congiunzione C).A B CA ∧ B

Dim. Si applica due volte modus ponens a partire dalla seguentetautologia:

A → (B → (A ∧ B)) .

Il sistema S0 e “corretto”, cioe permette di dimostrare solo conse-guenze logiche.

Teorema 2.37 (Correttezza di S0). Se T `S0 A allora T |= A.

Dim. Sia 〈B0, . . . ,Bn = A〉 una dimostrazione di A nella teoria Tcon il sistema dimostrativo S0. Verifichiamo per induzione che T |= Bkper ogni k ≤ n. Se k = 0, allora B0 ∈ T o B0 e una tautologia. Inentrambi i casi, banalmente T |= B0. Al passo induttivo 0 < k ≤ n,distinguiamo due casi. Se Bk ∈ T o Bk e una tautologia, di nuovobanalmente T |= Bk. Se invece Bk segue dalla coppia (Bi,Bj) dovei, j < k applicando la regola di modus ponens, allora deve essere Bj =Bi → Bk. Per ipotesi induttiva, T |= Bi e T |= Bj = Bi → Bk, e quindianche T |= Bk. �

Il prossimo risultato va nella direzione opposta, e mostra che ogniformula conseguenza logica di T e dimostrabile col sistema S0.

Teorema 2.38 (Completezza di S0). Se T |= A allora T `S0 A.

Dim. Se T |= A, per il Teorema di compattezza semantica esisteuna quantita finita di formule B1, . . .Bn ∈ T tali che B1, . . . ,Bn |= A.Per il Teorema di deduzione semantica 2.6, quest’ultima proprieta valese e solo se l’implicazione (B1∧ . . .∧Bn)→ A e una tautologia. Adesso,banalmente T `S0 B1, . . . , T `S0 Bn e quindi, con ripetute applicazionidella regola derivata di congiunzione (vedi Proposizione 2.36), si deduceche T `S0 B1 ∧ . . . ∧ Bn. Infine, trattandosi di una tautologia, T `S0(B1 ∧ . . . ∧ Bn)→ A, e applicando la regola modus ponens si concludeche T `S0 A. �

Dunque la nozione semantica di conseguenza logica T |= A e equi-valente alla nozione sintattica di dimostrazione T `S0 A.

Vista l’equivalenza tra |= e `S0 , si ha che

Teor(T ) = {A | T `S0 A} = {A | T |= A} = Con(T ).

Page 32: LOGICA MATEMATICA - unipi.it

32 2. TEORIE PROPOSIZIONALI E MODELLI

Dunque le nozioni semantiche di soddisfacibilita e di insoddisfaci-bilita coincidono rispettivamente con le nozioni sintattiche di coerenzae di contraddittorieta.

Per semplicita, da qui in avanti ometteremo il sottoindice S0 escriveremo semplicemente `.

Grazie ai risultati gia visti per la conseguenza logica, abbiamo leseguenti proprieta:

• T e contraddittoria ⇔ T ` B per ogni formula B ;

• Deduzione sintattica:T,A ` B ⇔ T ` A → B ;

• Dimostrazione per casi:Se T ∪ {A} ` B e T ∪ {¬A} ` B allora T ` B ;

• Reductio ad absurdum:– T ` A ⇔ T ∪ {¬A} e contraddittoria;– T ` ¬A ⇔ T ∪ {A} e contraddittoria.

• Sia T coerente e sia A una formula. Allora T ∪{A} e coerenteo T ∪ {¬A} e coerente.

Esercizio 2.39.∗ Dimostrare le cinque proprieta di sopra usandosoltanto nozioni sintattiche.

Il sistema dimostrativo S0 e stato introdotto qui per motivi di sem-plicita, ma certamente non e l’unico equivalente alla deduzione logica,cioe che abbia le proprieta di correttezza e completezza. Ad esempio,il sistema dimostrativo per il calcolo proposizionale che piu frequente-mente appare in letteratura e quello che si trova nel classico libro di E.Mendelson “Introduction to Mathematical Logic”.7 Si tratta di una re-strizione del sistema S0 dove si considerano solo i due connettivi ¬,→,e gli altri sono introdotti come semplici abbreviazioni metalinguistiche.Precisamente:

• A ∧ B e una abbreviazione di ¬(A → ¬B) ;

• A ∨ B e una abbreviazione di ¬A → B ,

• A ↔ B e una abbreviazione di ¬(

(A → B)→ ¬(B → A)).

Inoltre, la lista di assiomi logici e limitata a tre soli schemi ditautologie, e l’unica regola di inferenza considerata e il modus ponens.

Definizione 2.40. Il sistema dimostrativo di Mendelson M e ilsistema dimostrativo dove:

7 E in realta una semplice modifica di un sistema precedentemente introdottoda Hilbert e Ackermann.

Page 33: LOGICA MATEMATICA - unipi.it

4. COMPLETEZZA DEL CALCOLO PROPOSIZIONALE 33

• Gli assiomi logici AX sono i seguenti tre schemi di tautologie:

(1) A → (B → A) ;

(2) (A → (B → C))→ ((A → B)→ (A → C)) ;

(3) (¬A → ¬B)→ ((¬A → B)→ A).

• L’unica regola di inferenza (binaria) e il modus ponens MP :

A A → B MPBRichiede un lungo e accurato lavoro dimostrare che il sistema M

ha le proprieta richieste di correttezza e completezza.8

Teorema 2.41 (Correttezza e completezza di M). T `M A se esolo se T |= A.

Gli appassionati di riduzionismo estremo saranno lieti di sapereche si puo ulteriormente restringere il sistema dimostrativo del calcoloproposizionale considerando un unico schema di tautologie.

Esercizio 2.42. Il sistema dimostrativo di Meredith M0 e unarestrizione del sistema di Mendelson, dove i tre schemi di assiomi logicisono sostituiti dall’unico schema seguente:[ ( (

(A → B)→ (¬C → ¬D))→ C

)→ E

]→[

(E → A)→ (D → A)]

Dimostrare che il sistemaM0 dimostra tutti gli assiomi logici diM, equindi anche M0 e corretto e completo.

8 Per la dimostrazione di questo fatto, si veda il primo capitolo del manuale diE. Mendelson citato sopra.

Page 34: LOGICA MATEMATICA - unipi.it
Page 35: LOGICA MATEMATICA - unipi.it

CAPITOLO 3

Il calcolo dei predicati

1. Sintassi: il linguaggio e le formule

Definizione 3.1. Il linguaggio puro della logica del primo ordineconsiste dei seguenti simboli:

• I connettivi logici:– Negazione: ¬ (“non”) ;– Congiunzione: ∧ (“e”) ;– Disgiunzione: ∨ (“o”) ;– Implicazione materiale: → (“se . . . allora”) ;– Doppia implicazione materiale: ⇔ (“se e solo se”).

• Un insieme numerabile di variabili : x, y, z, . . . , x1, x2, . . . , xn, . . .

• I quantificatori :– Quantificatore esistenziale: ∃ (“esiste”) ;– Quantificatore universale: ∀ (“per ogni”).

• Il simbolo di uguaglianza: =.

Definizione 3.2. Un linguaggio L della logica del primo ordineconsiste del linguaggio puro e di:

• Un insieme di simboli di costante {ci | i ∈ I} ;

• Un insieme di simboli di funzione {Fj | j ∈ J} ;

• Un insieme di simboli di relazione {Rk | k ∈ K}.Ad ogni simbolo di funzione e di relazione e associato un numero

naturale, detto arieta.

Piu avanti, quando passeremo al versante semantico e daremo unsignificato ai simboli del linguaggio, vedremo che i simboli di costantesaranno interpretati da singoli elementi (costanti); i simboli di funzionedi arieta n saranno interpretati come funzioni in n variabili; e i simbolidi relazione di arieta n saranno interpretati come relazioni n-arie.

Seguiremo l’uso comune, e nello specificare i simboli di un linguaggioL considereremo soltanto i simboli non puri:

L = {ci | i ∈ I} ∪ {Fj | j ∈ J} ∪ {Rk | k ∈ K} .35

Page 36: LOGICA MATEMATICA - unipi.it

36 3. IL CALCOLO DEI PREDICATI

Ad esempio:

• Il linguaggio puro e il linguaggio vuoto L = ∅ ;

• il linguaggio della teoria degli insiemi L = {∈ } consiste in ununico simbolo di relazione di arieta 2, che verra interpretatodalla relazione binaria di “appartenenza” ;

• il linguaggio della teoria dei gruppi L = { e , · } consiste in unsimbolo di costante e, che verra interpretato come l’elementoneutro, e di un simbolo di funzione · di arieta 2, che verrainterpretato dall’operazione di gruppo (che e una funzione in2 variabili); ecc.

Adesso che abbiamo introdotto i simboli del linguaggio, dobbiamospecificare le regole con cui devono essere disposti per formare le “for-mule” (le quali verranno interpretate come affermazioni relative a certielementi). A questo scopo, e necessario specificare prima la classe dei“termini” (la cui interpretazione saranno proprio quegli elementi cui leformule si riferiscono).

Definizione 3.3. L’insieme Term(L) dei termini nel linguaggioL o insieme degli L-termini, e il piu piccolo insieme che soddisfa leseguenti proprieta:

(1) Se x e una variabile, allora x e un termine la cui unica variabilelibera e se stessa, cioe VL(x) = {x} ;

(2) Se c e un simbolo di costante, allora c e un termine senzavariabili libere, cioe VL(c) = ∅ ;

(3) Se F e un simbolo di funzione di arieta n e t1, . . . , tn sonotermini, allora anche F(t1, . . . , tn) e un termine, il cui insiemedi variabili libere e VL(F(t1, . . . , tn)) =

⋃ni=1 VL(ti).

I termini t senza variabili libere si dicono termini chiusi.

Notiamo che esistono L-termini chiusi se e solo se il linguaggio Lcontiene simboli di costante.

Definizione 3.4. L’insieme Form(L) delle formule nel linguaggiodel primo ordine L o insieme delle L-formule e il piu piccolo insiemeche soddisfa le seguenti proprieta:

(1) Se t1, t2 sono termini, allora

(t1 = t2)

e una formula, il cui insieme di variabili libere e VL(t1) ∪VL(t2) ;

Page 37: LOGICA MATEMATICA - unipi.it

1. SINTASSI: IL LINGUAGGIO E LE FORMULE 37

(2) Se R e un simbolo di relazione di arieta n e se t1, . . . , tn sonotermini, allora

R(t1, . . . , tn)

e una formula, il cui insieme di variabili libere e⋃ni=1 VL(ti) ;

(3) Se ϕ e ψ sono formule, allora anche

(¬ϕ), (ϕ ∧ ψ), (ϕ ∨ ψ), (ϕ→ ψ), (ϕ↔ ψ)

sono formule, i cui insiemi di variabili libere sono

• VL(¬ϕ) = VL(ϕ),• VL(ϕ ∧ ψ) = VL(ϕ ∨ ψ) = VL(ϕ → ψ) = VL(ϕ ↔ ψ) =

VL(ϕ) ∪ VL(ψ) ;

(4) Se ϕ e una formula e x e una sua variabile libera, allora anche

(∃xϕ) e (∀xϕ)

sono formule, le cui variabili libere sono tutte e sole le variabililibere di ϕ tranne x, cioe VL(∃xϕ) = VL(∀xϕ) = VL(ϕ)\{x}.

Le formule del tipo (1) e (2) in cui non compaiono connettivi nequantificatori, si dicono formule atomiche.

Le formule senza variabili libere si dicono enunciati.Le variabili che compaiono in una formula ma che non sono variabili

libere, si dicono variabili legate.Le occorrenze di una variabile x nelle formule del tipo (∃xϕ) e

(∀xϕ) si dicono occorrenze legate.

Dunque, per definizione, se una variabile che compare in una for-mula e legata allora tutte le sue occorrenze sono occorrenze legate.Tuttavia non vale il viceversa, cioe possono esistere variabili libere diuna formula che hanno anche occorrenze legate, come mostrato dallaformula (5) nell’Esempio 3.5 qua sotto.

Per semplificare il formalismo ed arrivare ad una maggiore leggi-bilita delle formule, adottiamo le usuali semplificazioni per ridurre ilnumero di parentesi usate. Come nel calcolo proposizionale, convenia-mo che la negazione ¬ abbia la precedenza sulla congiunzione ∧ e sulladisgiunzione ∨, le quali a loro volta hanno la precedenza sull’impli-cazione → e la doppia implicazione ↔. Inoltre, seguendo un comuneabuso di notazione, scriveremo “t1 6= t2” per intendere “¬(t1 = t2)”.

Esempio 3.5. Sia L = {c1, c2,R} il linguaggio che contiene duesimboli di costante c1, c2 e un simbolo di relazione R di arieta 2.

(1) “c1 = x” e una formula atomica che ha x come unica variabilelibera ;

Page 38: LOGICA MATEMATICA - unipi.it

38 3. IL CALCOLO DEI PREDICATI

(2) “R(c1, c2)” e una formula atomica, ed e banalmente un enun-ciato perche non vi compare alcuna variabile ;

(3) “∃x (c1 = x)” e un enunciato perche le occorrenze dell’unicavariabile x che vi compare sono occorrenze legate ;

(4) “∀xR(x, y)” e una formula dove la variabile y e libera, e dovela variabile x non e libera, perche le sue occorrenze sono legate ;

(5) “∃x∀yR(x, y)” e un enunciato perche entrambe le variabilix, y che compaiono sono legate.

(6) “(x = c)∧∀xR(x, x)” e una formula dove x e l’unica variabilelibera. Notiamo pero che x occorre legata nella sotto-formula“∀xR(x, x)”, la quale e un enunciato.

Vedremo piu avanti quando introdurremo le nozioni semantiche, chela verita o falsita di una formula in una data interpretazione dipendeda quali elementi si fanno corrispondere alle variabili libere. Il valore diverita degli enunciati sara invece univocamente determinato, visto chenon contengono alcuna variabile libera. Per questo motivo, gli enun-ciati rivestiranno una particolare importanza; essi sono, in un sensopreciso, il corrispettivo nei linguaggi del primo ordine delle formuleproposizionali.

Definizione 3.6. Una teoria del primo ordine e un qualunqueinsieme di enunciati in un linguaggio del primo ordine.

Notazione 3.7. Se ϕ e una formula, scriviamo ϕ(x1, . . . , xn) perintendere che x1, . . . , xn sono variabili libere di ϕ, cioe {x1, . . . , xn} ⊆VL(ϕ). Adottiamo lo stesso tipo di notazione anche per i termini t,cioe scriviamo t(x1, . . . , xn) per intendere che {x1, . . . , xn} ⊆ VL(t).

Notazione 3.8. Se ϕ(x1, . . . , xn) e una formula, e t1, . . . , tn sonotermini, scriviamo ϕ(t1/x1, . . . , tn/xn) per intendere la formula che siottiene sostituendo in ϕ tutte le occorrenze non legate di xi con iltermine ti, per i = 1, . . . , n.

2. L-strutture e relazione di soddisfazione

Una struttura per un linguaggio del primo ordine e un insieme sulquale viene definito un significato ad ognuno dei simboli del lingauggio.Precisamente:

Definizione 3.9. Sia L un linguaggio della logica del primo ordine.Una L-struttura M consiste di:

• Un insieme non vuoto M , detto universo o dominio ;

Page 39: LOGICA MATEMATICA - unipi.it

2. L-STRUTTURE E RELAZIONE DI SODDISFAZIONE 39

• Un elemento cM ∈M per ogni c ∈ L simbolo di costante ;

• Una funzione in n variabili FM : Mn → M per ogni F ∈ Lsimbolo di funzione di arieta n ;

• Una relazione n-aria RM ⊆ Mn per ogni R ∈ L simbolo direlazione di arieta n.

cM,FM,RM si dicono interpretazioni rispettivamente dei simbolic,F,R nella struttura M.

Useremo lettere gotiche maiuscole M,N, . . . ,A,B,C, . . . per deno-tare L-strutture, e le corrispondenti lettere latine maiuscole M,N, . . . ,A,B,C, . . . per denotare i relativi universi.

Definizione 3.10. Siano M e N due L-strutture. Diciamo che M euna sottostruttura di N o che N e una sovrastruttura diM, e scriviamoM ⊆ N, se valgono le seguenti condizioni:

• cM = cN per ogni simbolo di costante c ∈ L ;

• FM = FN|Mn per ogni simbolo di funzione F ∈ L di arieta n ;

• RM = RN ∩Mn per ogni simbolo di relazione R ∈ L di arietan.

A partire dalle definizioni, e immediato verificare che vale la se-guente

Osservazione 3.11. Se N e una L-struttura, allora un sottoin-sieme M ⊆ N e universo di una sottostruttura M ⊆ N se e solose:

(1) cN ∈M per ogni simbolo di costante c ∈ L ;

(2) FN(m1, . . . ,mn) ∈M per ogni simbolo di funzione F di arietan, e per ogni m1, . . . ,mn ∈M .

Chiaramente in questo caso i simboli di relazione sono definiti suM per restrizione, cioe si pone RM = RN ∩Mn per ogni simbolo direlazione R di arieta n.

Esempio 3.12. FARE

Una volta attribuito un significato ai simboli del linguaggio in unafissata struttura, vogliamo dare un significato a tutte le formule. Aquesto scopo, occorrera pero prima specificare quale particolari valoridevo essere attribuiti alle variabili libere. Ad esempio, una volta in-terpretato il simbolo di costante c, per poter dare un significato allaformula “c = x” e necessario specificare a quale elemento dell’universofar corrispondere la variabile x.

Page 40: LOGICA MATEMATICA - unipi.it

40 3. IL CALCOLO DEI PREDICATI

Definizione 3.13. Un assegnamento sulla struttura M e una fun-zione ρ : Var → M che assegna un elemento dell’universo ad ognivariabile.

Fissato un assegnamento, possiamo intanto dare un significato atutti i termini.

Definizione 3.14. Sia M una L-struttura e ρ un assegnamentosu M. Per induzione sulla costruzione dell’L-termine t, definiamol’interpretazione tM,ρ ∈M di t in M per induzione in questo modo:

• Se x e una variabile x, allora xM,ρ = ρ(x) ;

• Se c ∈ L e un simbolo di costante, allora cM,ρ = cM ;

• Se F e un simbolo di funzione di arieta n e t1, . . . , tn sonotermini, allora F(t1, . . . , tn)M,ρ = FM(tM,ρ

1 , . . . , tM,ρn ).

L’interpretazione dei termini si preserva passando a sovrastrutture.

Osservazione 3.15. Siano M ⊆ N due L-strutture. Allora perogni assegnamento ρ su M e per ogni L-termine t, si ha tM,ρ = tN,ρ.

Dim. Procediamo per induzione sulla costruzione dei termini. Se t ela variabile x, allora banalmente tM,ρ = ρ(x) = tN,ρ. Se t e il simbolo dicostante c, allora per definizione di sottomodello si ha che tM,ρ = cM =cN = tN,ρ. Infine, se t e il termine F(t1, . . . , tn) dove F e un simbolodi funzione di arieta n e t1, . . . , tn sono termini allora, applicando laproprieta di sottomodello e l’ipotesi induttiva tM,ρ

i = tN,ρi ∈ M per

i = 1, . . . , n, si ottiene tN,ρ = FN(tN,ρ1 , . . . , tN,ρn ) = FN(tM,ρ1 , . . . , tM,ρ

n ) =

FM(tM,ρ1 , . . . , tM,ρ

n ) = tM,ρ. �

Il prossimo risultato mostra che l’interpretazione dei termini e coe-rente con le sostituzioni. Si tratta di una proprieta tecnica che cirisultera utile in seguito.

Notazione 3.16. Se ρ e un assegnamento su M, denotiamo conρ(m/x) l’assegnamento su M che coincide con ρ su tutte le variabilitranne x, cui assegna il valore m ∈M .

Proposizione 3.17. Siano t ed s due L-termini, x una variabile, et′ il termine t(s/x) che si ottiene rimpiazzando in t tutte le occorrenze dix con s. Per ogni L-struttura M e per ogni assegnamento ρ, dimostrareche (t′)M,ρ = tM,ρ′, dove ρ′ = ρ(m/x) con m = sM,ρ.

Dim. FARE �

Siamo finalmente pronti a dare la definizione fondamentale.

Page 41: LOGICA MATEMATICA - unipi.it

2. L-STRUTTURE E RELAZIONE DI SODDISFAZIONE 41

Definizione 3.18 (Relazione di soddisfazione alla Tarski). Sia Muna L-struttura e ρ un assegnamento su M. Per induzione sulla co-struzione dell’L-formula ϕ, definiamo la relazione di soddisfazione “Msoddisfa ϕ con l’assegnamento ρ”

M |= ϕ [ρ]

procedendo per induzione sulla costruzione di ϕ in questo modo:

• Formule atomiche:

– Se t1 e t2 sono L-termini, allora M |= (t1 = t2) [ρ] se e

solo se tM,ρ1 = tM,ρ

2 ;

– Se R ∈ L e un simbolo di relazione di arieta n e t1, . . . , tnsono L-termini, allora M |= R(t1, . . . , tn) [ρ] se e solo se

(tM,ρ1 , . . . , tM,ρ

n ) ∈ RM ;

• Connettivi:

– M |= ¬ψ [ρ] se e solo se M 6|= ψ [ρ] ;

– M |= (ψ ∧ ϑ) [ρ] se e solo se M |= ψ [ρ] e M |= ϑ [ρ] ;

– M |= (ψ ∨ ϑ) [ρ] se e solo se M |= ψ [ρ] o M |= ϑ [ρ] ;

– M |= (ψ → ϑ) [ρ] se e solo se vale l’implicazione:M |= ψ [ρ]⇒M |= ϑ [ρ] ;

– M |= (ψ ↔ ϑ) [ρ] se e solo se vale l’equivalenza:M |= ψ [ρ]⇔M |= ϑ [ρ] ;

• Quantificatori:

– M |= ∃xϕ [ρ] se e solo seesiste m ∈M tale che M |= ϕ [ρ(m/x)] ;

– M |= ∀xϕ [ρ] se e solo seper ogni m ∈M si ha M |= ϕ [ρ(m/x)] ;

Scriveremo M |= ϕ senza specificare l’assegnamento quando M |=ϕ [ρ] per ogni assegnamento ρ.

Segue direttamente dalla definizione di soddisfazione che la validitadegli enunciati non dipende dall’assegnamento; per questo motivo essirivestono un ruolo del tutto speciale, costituendo l’analogo delle formuleproposizionali.

Osservazione 3.19. Sia M una L-struttura e sia σ un L-enunciato.Allora vale una ed una sola delle seguenti due possibilita:

(1) M |= σ, cioe M |= σ [ρ] per ogni assegnamento ρ ;

(2) M |= ¬σ, cioe M |= ¬σ [ρ] per ogni assegnamento ρ.

Dim. FARE �

Page 42: LOGICA MATEMATICA - unipi.it

42 3. IL CALCOLO DEI PREDICATI

Definizione 3.20. Una L-formula ϕ si dice logicamente vera se perogni L-struttura M si ha M |= ϕ.

Esempio 3.21. Segue direttamente dalle definizioni che se x e unavariabile libera della formula ϕ(x), allora la formula “∀xϕ(x)→ ϕ(x)”e logicamente vera.

Un’ampia classe di formule logicamente vere e data dalle formuleche hanno la stessa struttura delle tautologie del calcolo proposizionale.

Definizione 3.22. Una L-formula ϕ si dice istanza di tautologiase esiste una tautologia A(X1, . . . , Xn) del calcolo proposizionale nellevariabili X1, . . . , Xn ed esistono L-formule ψ1, . . . , ψn tali che ϕ e laformula A(ψ1/X1, . . . , ψn/Xn) che si ottiene rimpiazzando simultanea-mente ogni occorrenza di Xi in A con la formula ψi, per i = 1, . . . , n.

Esercizio 3.23. Verificare che se ogni istanza di tautologia e unaformula logicamente vera.

Proposizione 3.24. Sia ϕ(x) una L-formula dove x e libera, e siat un L-termine. Se nessuna delle variabili che compaiono in t comparein ϕ, allora per ogni L-struttura M e per ogni assegnamento ρ su Msi ha M |= ϕ(t/x)[ρ]⇔ M |= ϕ(x)[ρ(m/x)], dove m = tM,ρ.

Dim. FARE �

Corollario 3.25. Se ϕ(x) una L-formula, e se t e un L-terminein cui non compare alcuna delle variabili che compaiono in ϕ, allora laformula “∀xϕ(x)→ ϕ(t/x)” e logicamente vera.

In realta quest’ultima proprieta vale per una classe piu ampia disostituzioni.

Esercizio 3.26. Dimostrare che il Corollario 3.25 vale anche sottol’ipotesi piu debole che tutte le variabili che appaiono in t rimangonolibere in ϕ(t/x).1

Definizione 3.27. Siano ϕ e ψ due L-formule. Diciamo che ϕimplica logicamente ψ, o che ψ e conseguenza logica di ϕ, se per ogniL-struttura M si ha che M |= ϕ⇒M |= ψ.

Diciamo che ϕ e ψ sono logicamente equivalenti se per ogni L-struttura M si ha che M |= ϕ⇔M |= ψ.

E immediato verificare che ϕ implica logicamente ψ se e solo se l’im-plicazione “ϕ → ψ” e logicamente vera; e che ϕ e ψ sono logicamenteequivalenti se e solo se la doppia implicazione “ϕ ↔ ψ” e logicamentevera.

1 Questo tipo di termini vengono chiamati termini sostituibili per x in ϕ.

Page 43: LOGICA MATEMATICA - unipi.it

4. L’ARITMETICA DI PEANO PA 43

3. Teorie del primo ordine

Definizione 3.28. Per teoria del primo ordine si intende un qua-lunque insieme (eventualmente vuoto) di enunciati in un linguaggio delprimo ordine.

Introduciamo ora alcune importanti nozioni semantiche.

Definizione 3.29. Sia T una teoria nel linguaggio L. Una L-struttura dice modello della teoria T se M |= τ per ogni τ ∈ T .

Introduciamo ora nozioni analoghe a quelle gia viste per il calcoloproposizionale.

Definizione 3.30. Diciamo che la teoria T implica logicamente laformula ϕ, o che ϕ e conseguenza logica di T , se ϕ e vera in ogni modellodi T . In questo caso scriviamo T |= ϕ.

Definizione 3.31. Una teoria T si dice soddisfacibile se ammetteun modello; si dice insoddisfacibile in caso contrario.

Gli stessi risultati gia dimostrati per le teorie proposizionale, valgo-no anche per le teorie del primo ordine. Ne elenchiamo i principali quasotto (le dimostrazioni sono le stesse del caso proposizionale e quindile omettiamo).

• Procedimento per casi: Sia T una teoria del primo ordine esiano ϕ, ψ formule. Se T ∪ {ψ} |= ϕ e T ∪ {¬ϕ} |= ψ alloraT |= ϕ.

• Deduzione semantica: Sia T una teoria e siano A1, . . . ,An,Bformule. Allora

T,A1, . . . ,An |= B ⇐⇒ T |= A1 ∧ . . . ∧ An → B .

• Reductio ad absurdum: Sia T una teoria e A una formula.Allora T |= A ⇔ T ∪ {¬A} e insoddisfacibile.

4. L’aritmetica di Peano PA

FARE

Page 44: LOGICA MATEMATICA - unipi.it

44 3. IL CALCOLO DEI PREDICATI

5. Il Teorema di Loweinheim-Skolem

In questa sezione vedremo importanti risultati nell’ambito dellateoria dei modelli, cioe quella parte della logica matematica che siconcentra sulla studio delle L-strutture.

Definizione 3.32. Siano M e N due L-strutture. Una funzionef : M → N tra i rispettivi universi si dice immersione elementare, e siscrive f : M � N, se per ogni L-formula ϕ e per ogni assegnamento ρsu M si ha l’equivalenza

M |= ϕ [ρ] ⇐⇒ N |= ϕ [f ◦ ρ].

M si dice sottostruttura elementare di N, e si scrive M � N, seM ⊆ N e l’inclusione ı : M → N e un’immersione elementare.

Visto che “x = y” e una formula di tutti i linguaggi del primoordine, segue subito che le immersioni elementari sono necessariamentefunzioni iniettive.

Esempio 3.33. FARE

Definizione 3.34. Due L-strutture M e N si dicono elementar-mente equivalenti, e si scrive M ≡ N, se per ogni L-enunciato σ si hal’equivalenza:

M |= σ ⇐⇒ N |= σ.

Esercizio 3.35. Dimostrare che se esiste un’immersione elementaref : M � N allora M ≡ N.

La proprieta dell’esercizio precedente non si puo invertire.

Esercizio 3.36. Trovare un esempio di due strutture elementar-mente equivalenti M ≡ N per le quali non esistono immersioni elemen-tari f : M � N o g : N �M.

Esercizio 3.37. Trovare due strutture M ⊆ N una sottostrutturadell’altra, tali che M ≡ N ma M 6� N.

Il seguente classico risultato ci fornisce un’utile criterio per deter-minare quando una sottostruttura e anche sottostruttura elementare.

Lemma 3.38 (Criterio di Tarski-Vaught). Siano M ⊆ N due L-strutture. M ≺ N se e solo se la seguente condizione e soddisfatta perogni L-formula ϕ(x) e per ogni assegnamento ρ : Var→M :

(?) N |= ∃xϕ(x) [ρ] =⇒ esiste m ∈M tale che N |= ϕ(x) [ρ(m/x)] .

Page 45: LOGICA MATEMATICA - unipi.it

5. IL TEOREMA DI LOWEINHEIM-SKOLEM 45

Dim. Se M ≺ N, allora la condizione (?) vale perche

N |= ∃xϕ(x) [ρ] ⇔ M |= ∃xϕ(x) [ρ]

e quindi esiste m ∈ M tale che M |= ϕ(x) [ρ(m/x)]. Viceversa, dob-biamo mostrare che per ogni L-formula ψ e per ogni assegnamento ρsu M, si ha l’equivalenza

M |= ψ [ρ] ⇐⇒ N |= ψ [ρ] .

Procediamo per induzione sulla costruzione di ψ, e supponiamoprima che ψ sia atomica, cioe sia R(t1, . . . , tn) dove R e un simbolo direlazione di arieta n, e t1, . . . , tn sono L-termini. Vista l’Osservazione3.15, le interpretazioni dei termini con l’assegnamento ρ in M e in Ncoincidono, cioe tM,ρ

i = tN,ρi ∈M per ogni i = 1, . . . , n. Allora abbiamo:

M |= ψ [ρ] ⇔(tM,ρ1 , . . . , tM,ρ

n

)=(tN,ρ1 , . . . , tN,ρn

)∈ RM ⇔

(per def. di sottomodello) ⇔(tN,ρ1 , . . . , tN,ρn

)∈ RN ⇔ N |= ψ [ρ] .

Se ψ e ¬ϕ, allora applicando l’ipotesi induttiva su ϕ si ha

M |= ψ [ρ] ⇔ M 6|= ϕ [ρ] ⇔ N 6|= ϕ [ρ] ⇔ M |= ψ [ρ] .

Se ψ e ϕ1 ∧ ϕ2, applicando l’ipotesi induttiva su ϕ1 e ϕ2 si hanno leequivalenze:

M |= ψ [ρ] ⇔ M |= ϕ1 [ρ] e M |= ϕ2 [ρ] ⇔N |= ϕ1 [ρ] e N |= ϕ2 [ρ] ⇔ N |= ψ [ρ] .

Gli altri connettivi ∨, → e ↔ seguono dai precedenti, utilizzando leseguenti istanze di tautologie: ϕ1 ∨ ϕ2 ↔ ¬(¬ϕ1 ∧ ¬ϕ2); ϕ → ϕ2 ↔¬ϕ1 ∨ ϕ2; e ϕ1 ↔ ϕ2 ↔ (ϕ1 → ϕ2) ∧ (ϕ2 → ϕ1).

Occupiamoci ora del quantificatore esistenziale, e supponiamo cheψ sia ∃xϕ(x). Una implicazione si dimostra notando che

M |= ψ [ρ] ⇔ esiste m ∈M t.c. M |= ϕ [ρ(m/x)] ⇒⇒ esiste m ∈ N t.c. M |= ϕ [ρ(m/x)] ⇔

⇔ esiste m ∈ N t.c. N |= ϕ [ρ(m/x)] ⇔ N |= ψ [ρ].

Abbiamo potuto usare l’ipotesi induttiva perchem ∈M , e quindi ancheρ(m/x) assume valori in M . L’altra implicazione segue direttamentedalla condizione (?), e dall’ipotesi induttiva su ϕ. Infine, la quantifi-cazione universale e conseguenza di quanto gia dimostrato, visto chel’equivalenza “∀xϕ(x)↔ ¬(∃x¬ϕ)” e logicamente vera. �

Teorema 3.39 (Lowenheim-Skolem). Per ogni L-struttura B e perogni X ⊆ B esiste una sottostruttura elementare A ≺ B dove X ⊆ Ae |A| ≤ max{|X|, |L|,ℵ0}.

Page 46: LOGICA MATEMATICA - unipi.it

46 3. IL CALCOLO DEI PREDICATI

Dim. Sia ϕ(x, y1, . . . , yn) una formula dove x, y1, . . . , yn sono tuttee sole le sue variabili libere. Chiamiamo funzione di Skolem per ϕrispetto alla variabile libera x (nella struttura B) una funzione f :Bn → B che “sceglie i testimoni”, cioe tale che per ogni b1, . . . , bk ∈ B:

M |= ∃xϕ(x, b1/y1, . . . , bk/yn) ⇒ M |= ϕ(b/x, b1/y1, . . . , bk/yk)

dove b = f(b1, . . . , bn). Nel caso in cui n = 0, cioe quando x e l’unicavariabile libera di ϕ, conveniamo che una funzione di Skolem sia unaqualunque funzione costante f : B → B. Segue direttamente dalladefinizione di “M |= ∃xϕ [ρ]” che per ogni formula ϕ e per ogni suavariabile libera x esiste una funzione di Skolem fϕ,x.

2 Possiamo quindiprendere una famiglia di Skolem per B:

F = {fϕ,x | x e una variabile libera della formula ϕ }

Senza perdita di generalita possiamo assumere X 6= ∅ (altrimenti ciaggiungiamo un qualunque elemento di B). Sia ora A =

⋃k∈NXk dove

X1 = X e dove, induttivamente, Xk+1 e la chiusura di Xk rispetto allefunzioni in F , cioe

Xk+1 = {f(a1, . . . , an) | f ∈ F funzione n-aria & a1, . . . , an ∈ Xk} .Per come e stato costruito, l’insieme A include X ed e chiuso per

funzioni di Skolem, cioe:

• Se f ∈ F e una funzione n-aria e a1, . . . , an ∈ A, allora anchef(a1, . . . , an) ∈ A.

Vogliamo mostrare che A e l’universo di una sottostruttura A ⊆ B;per farlo, verifichiamo che le due condizioni dell’Osservazione 3.11 sonosoddisfatte:

(1) cN ∈M per ogni simbolo di costante c ∈ L ;

(2) FN(m1, . . . ,mn) ∈M per ogni simbolo di funzione F di arietan, e per ogni m1, . . . ,mn ∈M .

Dato il simbolo di costante c, prendiamo una funzione f ∈ F diSkolem per la formula ϕ(x) data dall’uguaglianza “x = c”, rispettoalla variabile x. Dal momento che x e l’unica variabile libera di ϕ, lafunzione f : B → B assume un valore costante b. Notiamo che b ∈ A,perche se ξ e un qualunque elemento di X = X1, allora b = f(ξ) ∈

2 Notiamo che, in generale, e necessario usare l’assioma di scelta per dimostrarela sua esistenza; infatti, per ogni n-upla (b1, . . . , bn) ∈ Bn dobbiamo scegliere untestimone b ∈ B tale che B |= ϕ(b/x, b1/y1, . . . , bn/yn). Quando invece il dominioB e bene ordinabile (ad esempio, quando B e numerabile), l’assioma di scelta none necessario perche possiamo definire f(b1, . . . , bn) come il minimo elemento b ∈ Bche e un testimone.

Page 47: LOGICA MATEMATICA - unipi.it

5. IL TEOREMA DI LOWEINHEIM-SKOLEM 47

X2 ⊆ A. Adesso, banalmente N |= ∃xϕ(x), quindi N |= ϕ(b/x); maquesto vale se e solo se cN = b, e concludiamo che cN ∈ A. Se F eun simbolo di funzione di arieta n, e a1, . . . , an ∈ A, consideriamo laformula ψ(x, y1, . . . , yn): “∃x (F(y1, . . . , yn) = x)”, e prendiamo unafunzione di Skolem g ∈ F per ψ rispetto alla variabile x. Anche inquesto caso, banalmente N |= ∃xψ(x, a1/y1, . . . , an/yn), e quindi N |=ψ(b/x, a1/y1, . . . , an/bn), dove b = g(a1, . . . , an). Questo vale se e solose FN(a1, . . . , an) = b. Notiamo infine che un tale b ∈ A perche A echiuso per le funzioni di Skolem.

Per dimostrare che A ≺ B, usiamo il criterio di Tarski-Vaught, everifichiamo che per ogni ϕ(x) dove x e libera, e per ogni assegnamentoρ : Var→ A, vale la condizione:

(?) B |= ∃xϕ(x) [ρ] =⇒ esiste a ∈ A tale che B |= ϕ(x) [ρ(a/x)] .

Prendiamo f ∈ F funzione di Skolem per ϕ rispetto ad x. Sex, y1, . . . , yn sono tutte e sole le variabili libere di ϕ, e se ρ(yi) = ai ∈ Aper i = 1, . . . , n, allora, per definizione di funzione di Skolem, abbia-mo che B |= ϕ(b/x, a1/y1, . . . , an/yn) dove b = f(a1, . . . , an). Un taleb ∈ A perche l’insieme A e chiuso per funzioni di Skolem.

Occupiamoci infine della cardinalita del dominio A. Per semplicita,denotiamo con µ = max{|X|, |L|,ℵ0}. Vogliamo mostrare per indu-zione che |Xk| ≤ µ per ogni k. La base k = 1 e ovvia. Per il passoinduttivo, notiamo prima che la famiglia F delle funzioni di Skolemfϕ,x ha al piu la cardinalita del prodotto cartesiano Form(L) × Var,e quindi |F| ≤ max{|L|,ℵ0} ≤ µ. Quindi, per ogni funzione n-ariaf ∈ F , l’insieme immagine

Λf = {f(a1, . . . , an) | a1, . . . , an ∈ Xk}

ha cardinalita |Λf | = |f [Xnk ]| ≤ |Xk|n = |Xk|, visto che Xk e infinito.

Ma allora

|Xk+1| =

∣∣∣∣∣⋃f∈F

Λf

∣∣∣∣∣ ≤ ∑f∈F

|Λf | ≤ |Xk| · |F| ≤ µ · µ = µ.

Da qui segue subito la tesi, perche

|A| =

∣∣∣∣∣⋃k∈N

Xk

∣∣∣∣∣ ≤ µ · ℵ0 = µ .

Page 48: LOGICA MATEMATICA - unipi.it

48 3. IL CALCOLO DEI PREDICATI

6. Ultramisure e ultrafiltri

Come vedremo piu avanti, la costruzione di ultraprodotto permettedi ottenere nuove L-strutture a partire da sequenze arbitrarie 〈Mi | i ∈I〉 di L-strutture. In un certo senso, l’ultraprodotto M sara una sortadi “media” delle strutture di partenza. L’idea e quella di considerareuna speciale misura di probabilita µ su I, in modo che la validita omeno di un enunciato σ in M sia determinata dalla probabilita cheσ sia vera nelle strutture Mi. Per ottenere una simile proprieta, saranecessario imporre alcune condizioni sulla misura µ. Da qui in avantiassumeremo che l’insieme di indici I sia infinito (vedremo che se I efinito, la costruzione di ultraprodotto si banalizza).

Anzitutto, notiamo che per ogni A ⊆ I, e sempre possibile trovaresequenze di strutture 〈Mi | i ∈ I〉 ed enunciati σ in modo da avereA = {i ∈ I | Mi |= σ}. Dunque una prima naturale richiesta e laseguente:

(a) La misura di probabilita µ : P(I) → [0, 1] e definita su tutti isottoinsiemi di I.

Notiamo che se A = {i ∈ I | Mi |= σ}, allora il complementareAc = I \ A = {i ∈ I | Mi |= ¬σ}. Ovviamente, nella L-strutturaM dovra valere uno ed uno solo tra gli enunciati σ e ¬σ. La richiestanaturale e che in M valga l’enunciato piu probabile tra σ e ¬σ, e quindi:

• M |= σ se e solo se µ ({i ∈ I |Mi |= σ}) > 12.

In particolare, escluderemo la possibilita di insiemi con misura 1/2.Consideriamo ora la congiunzione logica σ ∧ τ di due enunciati. Perdefinizione, M |= σ ∧ τ se e solo se M |= σ e M |= τ . Chiaramente, seA = {i ∈ I | Mi |= σ} e B = {i ∈ I | Mi |= τ}, allora l’intersezioneA∩B = {i ∈ I |Mi |= σ∧τ}. Questo ci porta ad imporre la condizioneseguente:

(b) µ(A) > 12

e µ(B) > 12

se e solo se µ(A ∩B) > 12.

Quest’ultima richiesta sembra particolarmente difficile da soddisfa-re. Il problema pero puo essere risolto considerando delle speciali misu-re che assumono solo due valori: 0 e 1. Infatti, come si puo facilmenteverificare, ogni misura di probabilita µ : P(I) → {0, 1} soddisfa sia lacondizione (a) che la condizione (b). Supponiamo dunque che µ sia diquesto tipo, e continuiamo a riflettere su quali debbano essere le sueulteriori proprieta.

Quando Mi |= σ per tutti gli indici i tranne al piu un numero finito,e naturale richiedere che anche M |= σ. Questo equivale ad imporre laseguente condizione di non-atomicita:

Page 49: LOGICA MATEMATICA - unipi.it

6. ULTRAMISURE E ULTRAFILTRI 49

(c) Se A ⊆ I e cofinito, cioe se Ac e finito, allora µ(A) = 1.Equivalentemente, se A e finito allora µ(A) = 0.

Per la condizione (c), tutti i singoletti hanno misura 0. Se consi-deriamo il caso in cui I = {in | n ∈ N} e numerabile, ne deduciamoche la misura µ non puo essere σ-additiva, altrimenti avremmo cheµ(I) = µ (

⋃n{in}) =

∑∞n=1 µ({in}) = 0.

(d) µ e finitamente additiva.

Riassumiamo tutte le richieste (a), (b), (c), (d) viste sopra nellaseguente

Definizione 3.40. Chiamamo ultramisura sull’insieme I una mi-sura finitamente additiva µ : P(I) → {0, 1} e tale che µ(A) = 0 perogni A ⊂ I finito.

Un’utile caratterizzazione delle ultramisure e la seguente.

Teorema 3.41. Una funzione µ : P(I) → {0, 1} e un’ultramisurase e solo se la famiglia di insiemi U = {A ⊆ I | µ(A) = 1} soddisfa leseguenti proprieta:

(1) I ∈ U e ∅ /∈ U ;

(2) Se A ∈ U e B ⊇ A allora anche B ∈ U ;

(3) Se A ∈ U e B ∈ U allora anche A ∩B ∈ U ;

(4) Se A /∈ U allora il complementare Ac ∈ U ;

(5) Se A ⊆ I e finito, allora A /∈ U .

Dim. Riformuliamo le cinque proprieta di sopra come proprietadella funzione µ:

(1′) µ(I) = 1 e µ(∅) 6= 1 ;

(2′) Se µ(A) = 1 e B ⊇ A allora anche µ(B) = 1 ;

(3′) Se µ(A) = 1 e µ(B) = 1 allora anche µ(A ∩B) = 1 ;

(4′) Se µ(A) 6= 1 allora µ(Ac) = 1 ;

(5′) Se A ⊆ I e finito, allora µ(A) 6= 1.

Vediamo prima che se µ e un’ultramisura, allora tutte e cinque leproprieta (1′), . . . , (5′) sono soddisfatte. La (1′), la (4′) e la (5′) se-guono direttamente dall’equivalenza “µ(A) 6= 1 ⇔ µ(A) = 0”. La(2′) segue dalla proprieta di monotonia delle misure: “B ⊇ A ⇒µ(B) ≥ µ(A)”. Infine la (3′) si puo dimostrare per assurdo, notan-do che se fosse µ(A ∩ B) 6= 1, cioe se µ(A ∪ B) = 0, allora perle proprieta di misura finitamente additiva, si otterrebbe l’assurdo1 ≥ µ(A ∪B) = µ(A) + µ(B)− µ(A ∩B) = 2.

Page 50: LOGICA MATEMATICA - unipi.it

50 3. IL CALCOLO DEI PREDICATI

Viceversa, supponiamo che la funzione a due valori µ : P(I) →{0, 1} soddisfi le proprieta (1′), . . . , (5′), e mostriamo che µ e un’ultra-misura, cioe:

(I) µ(I) = 1 e µ(∅) = 0 ;

(II) Se A ∩B = ∅, allora µ(A ∪B) = µ(A) + µ(B).

(III) Se A e finito, allora µ(A) = 0.

La (I) e la (III) seguono in modo diretto rispettivamente dalla (1′)e dalla (5′). Prima di proseguire, notiamo che vale la proprieta:

• Per ogni X ⊆ I, si ha l’equivalenza µ(X) = 0⇔ µ(Xc) = 1.

L’implicazione ⇒ e data dalla (4′). Viceversa, se per assurdo fosseµ(Xc) = 1 ma µ(X) 6= 0, allora µ(X) = 1 e dalla (3′) seguirebbe che lamisura dell’intersezione µ(∅) = µ(X ∩Xc) = 1, contraddicendo la (1′).

Occupiamoci finalmente della (II). Supponiamo prima che almenouno dei due insiemi A e B abbia misura 1, ad esempio sia µ(A) = 1.Allora dalla (2′) segue che µ(A∪B) ≥ µ(A) e quindi anche µ(A∪B) = 1;inoltre, A ∩ B = ∅ ⇔ A ⊆ Bc ⇒ µ(Bc) = 1 ⇔ µ(B) = 0, e quindi inquesto caso la (II) vale. Supponiamo ora invece che µ(A) = µ(B) = 0.Allora µ(Ac) = µ(Bc) = 1 e quindi, per la (3′), µ ((A ∪B)c) = µ(Ac ∩Bc) = 1. Ma allora µ(A ∪ B) = 0, e anche in questo caso la (II)vale. �

La caratterizzazione di sopra ci risultera utile per risolvere il pro-blema dell’esistenza.

• Esistono ultramisure µ su ogni insieme infinito I?

Anticipiamo che la risposta sara positiva, ma richiedera un uso es-senziale dell’assioma di scelta, un tipico strumento matematico di na-tura non costruttiva. In altre parole, mostreremo che esistono ultrami-sure su ogni insieme infinito, ma non sara possibile costruirne nessunain modo “effettivo”.

Ricordiamo una nota nozione insiemistica.

Definizione 3.42. Si dice filtro su I una famiglia F ⊆ P(I) chesoddisfa le prime tre proprieta del Teorema 3.41:

(1) I ∈ U e ∅ /∈ U ;

(2) Se A ∈ U e B ⊇ A allora anche B ∈ U ;

(3) Se A ∈ U e B ∈ U allora anche A ∩B ∈ U ;

Esempi banali di filtri sono i filtri principali, cioe i filtri della forma

Fi = {A ⊆ I | i ∈ I}

Page 51: LOGICA MATEMATICA - unipi.it

6. ULTRAMISURE E ULTRAFILTRI 51

dove i ∈ I e un fissato elemento. Il prototipo di filtro non principale eil filtro di Frechet degli insiemi cofiniti:

Fr(I) = {A ⊆ I | Ac e finito }.

Definizione 3.43. Una famiglia di insiemi G ha la proprieta dell’inter-sezione finita (in breve FIP, cioe “finite intersection property”) se ogniintersezione finita di suoi elementi e non vuota:

∀ A1, . . . , An ∈ G A1 ∩ . . . ∩ An 6= ∅.

Dunque un filtro e una famiglia non vuota di insiemi che soddisfala FIP ed e chiusa per soprainsieme. E facile verificare che se G ⊂ P(I)e una famiglia (non vuota) con la FIP, allora

〈G〉 = {B ⊆ I | ∃G1, . . . , Gn ∈ G t.c. B ⊇ G1 ∩ . . . ∩Gn}

e un filtro su I, che si dice filtro generato da G.

Proposizione 3.44. Per ogni filtro F su I, sono proprieta equiva-lenti:

(i) F soddisfa anche la quarta condizione della proposizione pre-cedente: A /∈ F ⇒ Ac ∈ F ;

(ii) F e un filtro massimale rispetto all’inclusione.

Dim. (i) ⇒ (ii). Se per assurdo F non e massimale, allora esisteun filtro F ′ ⊃ F che lo estende propriamente, e possiamo prendere unelemento X ∈ F ′ \ F . Notiamo che X ∈ F ′ ⇒ Xc /∈ F ′ ⇒ Xc /∈ F .L’insieme X e quindi un controesempio alla proprieta (i).

(ii) ⇒ (i). Supponiamo per assurdo che esista A ⊆ I con A,Ac /∈F . Consideriamo la famiglia di insiemi:

G = {F ∩ A | F ∈ F}.

Dimostriamo che G ha la PIF. Se F1, . . . , Fn ∈ F , allora

(F1 ∩ A) ∩ . . . ∩ (Fn ∩ A) = F ∩ A

dove F = F1∩. . .∩Fn ∈ F . Chiaramente F ∩A 6= ∅, altrimenti F ⊆ Ac

implicherebbe che Ac ∈ F , contro la nostra assunzione. Consideriamoora il filtro F ′ = 〈G〉 generato da G. Notiamo che F ′ e un filtro cheestende propriamente F ; infatti F = F ∩ I ∈ G ⊆ F ′ per ogni F ∈ F ,e inoltre A = I ∩ A ∈ G ⊆ F ′ ⇒ A ∈ F ′ \ F . Questo contraddice lamassimalita di F . �

Definizione 3.45. Un filtro che soddisfi una (e quindi tutte) leproprieta precedenti e detto ultrafiltro.

Page 52: LOGICA MATEMATICA - unipi.it

52 3. IL CALCOLO DEI PREDICATI

Esercizio 3.46. Dimostrare che un filtro F e un ultrafiltro se esolo se soddisfa la seguente proprieta:

A ∪B ∈ F ⇒ A ∈ U o B ∈ U .

Esercizio 3.47. Dimostrare che due ultrafiltri U 6= V sono diversise e solo se esistono due insiemi disgiunti X e Y tali che X ∈ U eY ∈ V .

Notiamo che tutti i filtri principali sono banalmente ultrafiltri:

Ui = {A ⊆ I | i ∈ I} .

Invece, su ogni insieme infinito I, il filtro di Frechet Fr(I) non eun ultrafiltro. Infatti, basta prendere un insieme infinito A ⊂ I il cuicomplementare Ac sia infinito, ed abbiamo che A,Ac /∈ Fr(I).

Proposizione 3.48. Sia U un ultrafiltro su un insieme infinito I.Allora sono proprieta equivalenti:

(i) U soddisfa anche la quinta condizione del Teorema 3.41:A e finito ⇒ A /∈ U ;

(ii) U ⊃ Fr(I) include (propriamente) il filtro di Frechet ;

(iii) U non e principale.

Dim. (i) ⇒ (ii). Se per assurdo esistesse un insieme cofinito A ∈Fr(I) tale che A /∈ U allora, dalla proprieta di ultrafiltro, il comple-mentare finito Ac ∈ U , contro l’ipotesi.

(ii) ⇒ (iii). Se per assurdo U = Fi fosse principale, allora ilsingoletto {i} ∈ U , e quindi l’insieme cofinito {i}c = I \ {i} ∈ Fr(I)non apparterrebbe ad U .

(iii) ⇒ (i). Per assurdo supponiamo che esista un insieme finito

F = {i1, . . . , ik} ∈ U . Allora il complementare F c =⋂ks=1 I \ {is} /∈ U ,

e quindi deve esistere almeno un s tale che I \{is} /∈ U . Ma allora, perla proprieta di ultrafiltro, il complementare (I \ {is})c = {is} ∈ U , edunque U = Fis sarebbe un ultrafiltro principale, contro l’ipotesi. �

Grazie alle due ultime proposizioni, possiamo riformulare la Propo-sizione 3.41 in questo modo:

• µ : P(I) → {0, 1} e un’ultramisura se e solo se la corrispon-dente famiglia Uµ = {A ⊆ I | µ(A) = 1} e un ultrafiltro nonprincipale.

Page 53: LOGICA MATEMATICA - unipi.it

7. ULTRAPRODOTTI 53

L’esistenza di ultrafiltri non principali (e quindi di ultramisure) egarantita dal Lemma di Zorn, che e una delle forme equivalenti dell’as-sioma di scelta.3

Teorema 3.49 (UL - Ultrafilter Lemma). Ogni famiglia di insiemicon la FIP puo essere essere estesa ad un ultrafiltro. In particolare, perogni filtro F su un insieme I, esiste un ultrafiltro U su I con F ⊆ U .

Dim. Sia G ⊆ P(I) una famiglia di insiemi con la FIP, e sia F0 =〈G〉 il filtro su I generato da G. Allora F = {F filtro su I | F ⊇ F0}. Lafamiglia F e parzialmente ordinata per inclusione. Per poter applicareil Lemma di Zorn, occorre dimostrare l’esistenza di un maggioranteper ogni catena. Sia dunque 〈Fj | j ∈ J〉 una catena di elementi di F.Banalmente, l’unione H =

⋃j∈J Fj include tutti i Fj (e dunque anche

F). Perche sia un maggiorante, resta da dimostrare che H ∈ F, cioeche H e un filtro. Se A,B ∈ H, allora A ∈ Fj1 e B ∈ Fj2 per opportunij1, j2 ∈ J . Ma 〈Fj | j ∈ J〉 e una catena, dunque sara Fj1 ⊆ Fj2 (oviceversa). Quindi A,B ∈ Fj2 ⇒ A ∩ B ∈ Fj2 ⊆ H. La verifica cheH e anche chiuso per soprainsieme e immediata. Possiamo finalmenteapplicare il Lemma di Zorn, ed ottenere l’esistenza di un elemento Umassimale in F, che e l’ultrafiltro cercato. �

In un senso preciso, non si possono definire in modo esplicito ultra-filtri non principali. Piu precisamente, non esistono formule ϕ(x) dellateoria degli insiemi tali che la teoria ZFC dimostra entrambi gli enun-ciati: “Se vale ϕ(x) allora x e un ultrafiltro non principale” e “Esisteed unico x tale che ϕ(x)”. In altre parole, nonostante si possa dimo-strare che esistono (e lo abbiamo appena fatto!), nessuno di loro puoessere “descritto esplicitamente”. Per quanto possa apparire strano,un fenomeno simile si ritrova anche nella combinatoria elementare. Adesempio, per il cosiddetto principio dei cassetti, se abbiamo n+1 ogget-ti distribuiti in n cassetti, possiamo concludere che esiste un cassettocontenente almeno due oggetti, ma “descrivere esplicitamente” qualesia un tale cassetto non e possibile.

7. Ultraprodotti

In questa sezione mostreremo che gli ultrafiltri (o le le ultramisure)sono in effetti lo strumento che cercavamo per costruire nuove strutturea partire da sequenze di strutture assegnate.

3 Con questo intendiamo dire che, assumendo gli assiomi della teoria ZF diZermelo-Fraenkel, si dimostra l’equivalenza: “Assioma di scelta⇔ Lemma di Zorn”.

Page 54: LOGICA MATEMATICA - unipi.it

54 3. IL CALCOLO DEI PREDICATI

Definizione 3.50. Sia U un ultrafiltro su I. L’ultraprodotto diuna I-sequenza di L-strutture 〈Mi | i ∈ I〉 modulo U e la L-strutturaM =

∏i∈I Mi/U dove:

• L’universo e il quoziente M =(∏

i∈IMi

)/≡U del prodotto

cartesiano degli universi modulo la relazione di equivalenzadeterminata da U :

〈ai | i ∈ I〉 ≡U 〈bi | i ∈ I〉 ⇔ {i ∈ I | ai = bi} ∈ U ;

Denotiamo la U -classe di equivalenza di una I-upla f ∈∏

i∈IMi

scrivendo fU = 〈f(i) | i ∈ I〉U .

• Se c e un simbolo di costante, la sua interpretazione e il se-guente elemento di M :

cM =⟨cMi | i ∈ I

⟩U ;

• Se F e un simbolo di funzione di arieta n, la sua interpreta-zione FM e la funzione n-aria su M definita ponendo per ognif1, . . . , fn ∈

∏i∈IMi:

FM(fU1 , . . . , fUn ) =

⟨FMi(f1(i), . . . , fn(i)) | i ∈ I

⟩U ;

• Se R e un simbolo di relazione di arieta n, la sua interpreta-zione RM e la relazione n-aria su M definita ponendo per ognif1, . . . , fn ∈

∏i∈IMi:

(fU1 , . . . , fUn ) ∈ RM ⇔

{i ∈ I | (f1(i), . . . , fn(i)) ∈ RMi

}∈ U .

E necessario verificare che le definizioni date sopra sono ben poste.Le proprieta richieste si trovano nel seguente esercizio.

Esercizio 3.51. Supponiamo che fs ≡U gs per ogni s = 1, . . . , n.Dimostrare che per ogni n, anche le corrispondenti n-uple sono U -equi-valenti, cioe:{

i ∈ I∣∣∣ (f1(i), . . . , fn(i)) = (g1(i), . . . , gn(i))

}∈ U .

Dedurne che per ogni simbolo di funzione F di arieta n e per ognisimbolo di relazione R di arieta n si ha:

(1)⟨FMi(f1(i), . . . , fn(i)) | i ∈ I

⟩≡U

⟨FMi(g1(i), . . . , gn(i)) | i ∈ I

⟩;

(2){i ∈ I | (f1(i), . . . , fn(i)) ∈ RMi

}∈ U se e solo se{

i ∈ I | (g1(i), . . . , gn(i)) ∈ RMi}∈ U .

Page 55: LOGICA MATEMATICA - unipi.it

7. ULTRAPRODOTTI 55

Notiamo che la definizione di ultraprodotto sarebbe ben posta ancheprendendo un qualunque filtro F al posto dell’ultrafiltro U ; in lettera-tura, tali strutture si chiamano prodotti ridotti. Tuttavia per i prodottiridotti non vale il fondamentale Teorema di Los.4

Notazione 3.52. Se t e un L-termine avente x1, . . . , xn come varia-bili libere, allora per ogni L-struttura M e per ogni scelta m1, . . . ,mn ∈M di elementi nell’universo di M, denotiamo con

t [m1/x1, . . . ,mn/xn]

l’interpretazione di t in M con un qualsiasi assegnamento ρ tale cheρ(xs) = ms per s = 1, . . . , n. Analogamente, se ϕ e una formula nellevariabili libere x1, . . . , xn, scriviamo

M |= ϕ [m1/x1, . . . ,mn/xn] o semplicemente M |= ϕ [m1, . . . ,mn]

per intendere che M |= ϕ[ρ] dove ρ e un qualunque assegnamento taleche ρ(xs) = ms per s = 1, . . . , n.

Vediamo come caratterizzare l’interpretazione dei termini negli ul-traprodotti.

Osservazione 3.53. Sia M =∏

i∈I Mi/U un ultraprodotto. Alloraper ogni termine t avente x1, . . . , xn come variabili libere, e per ognif1, . . . , fn ∈

∏i∈IMi, si ha

tM [fU1 /x1, . . . , fUn /xn] =

⟨tMi [f1(i)/x1, . . . , fn(i)/xn] | i ∈ I

⟩U

Dim. FARE �

Teorema 3.54 ( Los). Sia M =∏

i∈I Mi/U un ultraprodotto. Allo-ra per ogni formula ϕ le cui variabili libere sono x1, . . . , xn, e per ognif1, . . . , fn ∈

∏i∈IMi, si ha∏

i∈I

Mi/U |= ϕ[fU1 , . . . , fUn ] ⇔ {i ∈ I |Mi |= ϕ[f1(i), . . . , fn(i)]} ∈ U .

Dim. Procediamo per induzione sulla costruzione della formula ϕ.Per semplicita, nel seguito denotiamo con M l’ultraprodotto

∏i∈I Mi/U .

4 In realta si puo dimostrare una versione piu debole del Teorema di Los perprodotti ridotti che garantisce, ad esempio, l’equivalenza∏

i∈I

Mi/U |= σ ⇔ {i ∈ I |Mi |= σ}

per gli enunciati σ costruiti usando solo i connettivi ∧ e →.

Page 56: LOGICA MATEMATICA - unipi.it

56 3. IL CALCOLO DEI PREDICATI

Cominciamo col caso di ϕ atomica. Se ϕ e “(t1 = t2)” dove t1, t2sono termini nei quali occorrono le variabili libere x1, . . . , xn allora,usando le definizioni e l’Osservazione 3.53, si hanno le equivalenze

M |= (t1 = t2) [fU1 /x1, . . . , fUn /xn] ⇔

tM1 [fU1 /x1, . . . , fUn /xn] = tM2 [fU1 /x1, . . . , f

Un /xn] ⇔{

i ∈ I | tMi1 [f1(i)/x1, . . . , fn(i)/xn] = tMi

2 [f1(i)/x1, . . . , fn(i)/xn]}∈ U ⇔

{i ∈ I |Mi |= (t1 = t2) [f1(i)/x1, . . . , fn(i)/xn]} ∈ U .Se ϕ e R(t1, . . . , tk) dove R e un simbolo di relazione di arieta k e

t1, . . . , tk sono termini nelle variabili libere x1, . . . , xn, allora:

M |= R(t1, . . . , tk) [fU1 /x1, . . . , fUn /xn] ⇔

(gU1 , . . . , gUk ) ∈ RM dove gUs = tMs [fU1 /x1, . . . , f

Un /xn] ⇔{

i ∈ I | (g1(i), . . . , gk(i)) ∈ RMi}∈ U

Per l’Osservazione 3.53, gs(i) = tMis [f1(i)/x1, . . . , fn(i)/xn], e quin-

di

(g1(i), . . . , gk(i)) ∈ RMi ⇔ Mi |= R(t1, . . . , tk) [f1(i)/x1, . . . , fn(i)/xn],

e possiamo concludere che le proprieta di sopra sono equivalenti a

{i ∈ I |Mi |= R(t1, . . . , tk) [f1(i)/x1, . . . , fn(i)/xn]} ∈ U .Se ϕ e ¬ψ ed ha x1, . . . , xn come variabili libere, allora dall’ipotesi

induttiva e dalla proprieta di ultrafiltro A /∈ U ⇔ Ac ∈ U , segue che

M |= ϕ [fU1 /x1, . . . , fUn /xn] ⇔ M 6|= ψ [fU1 /x1, . . . , f

Un /xn] ⇔

A = {i ∈ I |Mi |= ψ [f1(i)/x1, . . . , fn(i)/xn]} /∈ U ⇔Ac = {i ∈ I |Mi |= ϕ [f1(i)/x1, . . . , fn(i)/xn]} ∈ U .

Se ϕ e ψ1∧ψ2 ed ha x1, . . . , xn come variabili libere, di nuovo grazieall’ipotesi induttiva e alla proprieta di filtro A,B ∈ U ⇔ A ∩ B ∈ U ,si ottengono le equivalenze:

M |= ϕ [fU1 /x1, . . . , fUn /xn] ⇔

M |= ψ1 [fU1 /x1, . . . , fUn /xn] & M |= ψ2 [fU1 /x1, . . . , f

Un /xn] ⇔

A = {i ∈ I |Mi |= ψ1 [f1(i)/x1, . . . , fn(i)/xn]} ∈ U &

B = {i ∈ I |Mi |= ψ2 [f1(i)/x1, . . . , fn(i)/xn]} ∈ U ⇔A ∩B = {i ∈ I |Mi |= ϕ [f1(i)/x1, . . . , fn(i)/xn]} ∈ U .

Occupiamoci ora del quantificatore esistenziale, e supponiamo cheϕ sia ∃y ψ ed abbia x1, . . . , xn come variabili libere. Applicando ladefinizione e l’ipotesi induttiva, si ha

M |= ϕ [fU1 /x1, . . . , fUn /xn] ⇔

Page 57: LOGICA MATEMATICA - unipi.it

7. ULTRAPRODOTTI 57

esiste gU t.c. M |= ψ [gU/x, fU1 /x1, . . . , fUn /xn] ⇔

A = {i ∈ I |Mi |= ψ [g(i)/x, f1(i)/x1, . . . , fn(i)/xn]} ∈ U .Adesso, B = {i ∈ I | Mi |= ϕ [f1(i)/x1, . . . , fn(i)/xn]} ⊇ A, e quindianche B ∈ U . Viceversa, supponiamo che B ∈ U . Per ogni i ∈ B, pren-diamo un testimone bi ∈Mi tale che Mi |= ψ [bi, f1(i)/x1, . . . , fn(i)/xn].Se g ∈

∏i∈IMi e una qualunque I-upla tale che g(i) = bi per i ∈ B,

allora, per l’ipotesi induttiva su ψ,

{i ∈ I |Mi |= ψ [g(i)/x, f1(i)/x1, . . . , fn(i)/xn]} ∈ U ⇔

M |= ψ [gU/x, fU1 /x1, . . . , fUn /xn] ⇒ M |= ϕ [fU1 /x1, . . . , f

Un /xn].

I casi degli altri connettivi ψ1 ∨ ψ2, ψ1 → ψ2, ψ1 ↔ ψ2, e il caso delquantificatore universale, seguono dai precedenti. �

Corollario 3.55. Sia M =∏

i∈I Mi/U un ultraprodotto. Alloraper ogni enunciato σ, si ha∏

i∈I

Mi/U |= σ ⇔ {i ∈ I |Mi |= σ} ∈ U .

Particolarmente importante e il caso in cui si considerano I-sequenze〈Mi | i ∈ I〉 dove tutte le L-strutture sono uguali.

Definizione 3.56. Sia U un ultrafiltro sull’insieme I. L’ultrapotenzadi una L-struttura modulo U e l’ultraprodotto M I/U =

∏i∈I M/U della

I-sequenza costante 〈M | i ∈ I〉.L’immersione diagonale o immersione canonica d : M → M I/U

e la funzione dove d(m) e la classe di equivalenza 〈m | i ∈ I〉U dellacorrispondente I-upla costante.

Proposizione 3.57. L’immersione diagonale di una L-struttura inuna sua ultrapotenza e un’immersione elementare:

d : M �M I/U .

Dim. Segue direttamente dal Teorema di Los. �

Esercizio 3.58. Sia M una L-struttura. Dimostrare che l’immer-sione diagonale d : M �M I/U in una sua ultrapotenza e una immersio-ne elementare completa, cioe soddisfa la seguente proprieta: Per ogniespansione M′ della struttura M ad un linguaggio L′ ⊇ L, esiste unaespansione (M I/U)′ di M I/U ad L′ in modo che d : M′ → (M I/U)′ siaancora una immersione elementare.

Page 58: LOGICA MATEMATICA - unipi.it

58 3. IL CALCOLO DEI PREDICATI

8. Teorema di compattezza semantica

Vediamo ora un fondamentale risultato della logica matematica,la compattezza semantica, che fornisce un potente strumento per lacostruzione di strutture.

Teorema 3.59 (Compattezza semantica). Se una teoria del primoordine e finitamente soddisfacibile, allora e soddisfacibile.

Dim. Data la teoria T finitamente soddisfacibile, sia I = Fin(T )l’insieme dei suoi sottoinsiemi finiti. Per ipotesi, per ogni i ∈ I pos-siamo prendere un suo modello Mi. Vogliamo costruire un opportunoultraprodotto M =

∏i∈I Mi/U in modo che M |= T . A questo fine,

prenderemo un ultrafiltro U su I con particolari proprieta. Visto ilTeorema di Los, per ogni enunciato σ ∈ T , l’ultraprodotto M |= σ see solo se l’insieme

{i ∈ I | Mi |= σ} ⊇ {i ∈ I | σ ∈ i} ∈ U .Quindi, la tesi M |= T sarebbe garantita se trovassimo un ultrafiltroU che include tutti gli insiemi σ = {i ∈ I | σ ∈ i} al variare diσ ∈ T . Notiamo che la famiglia G = {σ | σ ∈ T} ha la FIP; infatti seσ1, . . . , σn ∈ T , banalmente i = {σ1, . . . , σn} ∈

⋂ns=1 σs. Ma allora un

qualunque ultrafiltro U che estende il filtro generato 〈G〉 ha le proprietacercate. �

Il Teorema logico di compattezza visto sopra corrisponde in effettialla proprieta di compattezza di una topologia naturale sullo spazioModL delle L-strutture. Precisamente, per ogni L-enunciato σ, con-sideriamo Oσ = {M ∈ ModL | M |= σ}. La famiglia di tutti gli Oσforma una base di aperti di una topologia τ . Notiamo che tale to-pologia e zero-dimensionale, perche ogni insieme Oσ e anche chiuso,visto che banalmente il complementare (Oσ)c = O¬σ. Secondo unadelle definizioni equivalenti, uno spazio topologico e compatto se ognifamiglia di chiusi con la FIP ha intersezione non vuota. E quindi facileverificare che il Teorema logico di compattezza afferma precisamente lacompattezza dello spazio topologico (ModL, τ).

Page 59: LOGICA MATEMATICA - unipi.it

CAPITOLO 4

Il Teorema di completezza

1. Un sistema formale per il calcolo dei predicati

Prima di presentare il nostro sistema formale per il calcolo dei predi-cati, facciamo alcune considerazioni riguardo la sostituzione di terminial posto di variabili libere.

Se ϕ(x) e una formula dove x occorre libera, sembra naturale ri-chiedere che valga l’implicazione ∀xϕ(x) → ϕ(t/x) per ogni terminet. Tuttavia, e necessario imporre alcune condizioni sulla scelta di t perevitare incongruenze. Ad esempio, se ϕ(x) e la formula ∃y (y 6= x),l’enunciato ∀xϕ(x) vale in tutte le strutture dove ci sono almeno dueelementi, mentre la formula ϕ(y/x), cioe ∃y (y 6= y) e falsa in tutte lestrutture. Il problema e superato se assumiamo che in t non campaianessuna delle variabili che compaiono in ϕ.

Definizione 4.1. S e il sistema dimostrativo del calcolo dei predi-cati dove:

• Gli assiomi logici AX sono:

– Le istanze di tautologie ;

– Gli assiomi dell’uguaglianza:

(E1) x = x ;

(E2) x = y → y = x ;

(E3) (x = y ∧ y = z)→ x = z ;

(E4) Per ogni simbolo di funzione F di arieta n:(x1 = y1 ∧ . . . ∧ xn = yn) → (F(x1, . . . , xn) =F(y1, . . . , yn)) ;

(E5) Per ogni simbolo di relazione R di arieta k:(x1 = y1 ∧ . . . ∧ xk = yk) → (R(x1, . . . , xk) ↔R(y1, . . . , yk)).

– Gli assiomi per la quantificazione:

(Q1) Se x e una variabile libera di ϕ, il seguente e unassioma:∀xϕ(x)→ ϕ(x) ;

59

Page 60: LOGICA MATEMATICA - unipi.it

60 4. IL TEOREMA DI COMPLETEZZA

(Q2) Se x e una variabile libera di ϕ e se nel termine tnon appare nessuna delle variabili che appaiono inϕ, il seguente e un assioma:∀xϕ(x)→ ϕ(t/x) ;

(Q3) Se x e una variabile libera di ϕ, il seguente e unassioma:∃xϕ(x)↔ ¬∀x¬ϕ(x).

• Le regole di inferenza sono

– Modus Ponens :ϕ ϕ→ ψ

MPψ

– Generalizzazione:ϕ(x)

G∀xϕ(x)

Notiamo che la regola di generalizzazione e una regola di inferenzaunaria.

Analogamente a quanto gia osservato riguardo il sistema dimostra-tivo S0 del calcolo proposizionale, anche nel caso del sistema S si puoderivare l’utile regola deduttiva di congiunzione.

Proposizione 4.2 (Regola di congiunzione C).ϕ ψ

Cϕ ∧ ψ

Dim. Si applica due volte modus ponens a partire dalla seguenteistanza di tautologia:

ϕ→ (ψ → (ϕ ∧ ψ)) .

Teorema 4.3. Tutti gli assiomi logici del sistema S sono logica-mente veri, cioe valgono in ogni L-struttura.

Dim. Come abbiamo gia osservato, e immediato verificare che leistanze di tautologie sono logicamente vere (cf. Esercizio 3.23). Ilsimbolo di uguaglianza e interpretato come la vera uguaglianza inogni struttura, e quindi e banale che tutti gli assiomi dell’uguaglian-za (E1), (E2), (E3), (E4), (E5) sono veri in ogni struttura con ogniassegnamento.

Occupiamoci ora degli assiomi per la quantificazione. La veritalogica degli assiomi (Q3), segue direttamente dalla definizione della

Page 61: LOGICA MATEMATICA - unipi.it

1. UN SISTEMA FORMALE PER IL CALCOLO DEI PREDICATI 61

relazione di soddisfazione. Occupiamoci ora di (Q1). Fissiamo una L-struttura M ed un assegnamento ρ su M. Se M |= ∀xϕ(x) [ρ] allora,per definizione, per ogni m ∈ M vale M |= ϕ(x)[ρ(m/x)]. In parti-colare, vale M |= ϕ(x) [ρ]. Questo dimostra la tesi M |= ∀xϕ(x) →ϕ(x) [ρ]. La validita degli assiomi (Q2) segue dalla seguente proprieta,gia dimostrata nel Corollario 3.25:

• Se nel termine t non appare nessuna delle variabili che appa-iono in ϕ(x), allora M |= ϕ(t/x) [ρ] ⇔ M |= ϕ(x) [ρ(m/x)],dove m = tM,ρ.

Infatti, come sopra, se M |= ∀xϕ(x) [ρ] allora per ogni m ∈M si haM |= ϕ(x)[ρ(m/x)]. In particolare, prendendo m′ = tM,ρ, abbiamo cheM |= ϕ(t/x)[ρ(m′/x)], e questo mostra che M |= ∀xϕ(x)→ ϕ(t/x) [ρ].

Teorema 4.4. Le regole di inferenza del sistema S preservano lavalidita delle formule, cioe per ogni L-struttura M, si ha:

(1) Modus ponens: Se M |= ϕ e M |= ϕ→ ψ allora M |= ψ ;

(2) Generalizzazione: Se x e una variabile libera di ϕ e M |= ϕ(x)allora M |= ∀xϕ(x).

Dim. (1). Per definizione, M |= ϑ significa M |= ϑ[ρ] per ogni asse-gnamento ρ. Dunque, fissato un assegnamento ρ, per ipotesi sappiamoche M |= ϕ[ρ] e M |= ϕ → ψ[ρ]. Quest’ultima proprieta equivale allavalidita dell’implicazione: “Se M |= ϕ[ρ] allora M |= ψ[ρ]”. Possiamodunque concludere che M |= ψ[ρ]. Vista l’arbitrarieta di ρ, otteniamola tesi M |= ψ.

(2). Sia ρ un assegnamento fissato. Per ogni m ∈ M , ancheρ(m/x) e un assegnamento, e quindi dall’ipotesi sappiamo che M |=ϕ(x)[ρ(m/x)]. Questo significa che M |= ∀xϕ[ρ]. Vista l’arbitrarietadi ρ, otteniamo la tesi M |= ∀xϕ(x). �

Definizione 4.5. Una teoria del primo ordine e un qualunqueinsieme di enunciati in un linguaggio del primo ordine.

Come conseguenza diretta dei due teoremi precedenti, si ricava ilfondamentale

Teorema 4.6 (di correttezza di S). Sia T una L-teoria e sia ϕuna L-formula. Se T ` ϕ allora T |= ϕ.

Dim. Sia 〈ψ1, . . . , ψn〉 una dimostrazione di T ` ϕ. Per induzionesu i ≤ n, mostriamo che se M e un qualunque modello di T , alloraM |= ψi. Se ψi e un assioma logico allora, per il Teorema 4.3, M |= ψi

Page 62: LOGICA MATEMATICA - unipi.it

62 4. IL TEOREMA DI COMPLETEZZA

per ogni struttura M. Se ψi ∈ T , la tesi e banale. Supponiamo orache ψi sia stata ottenuta per modus ponens dalle formule ψj e ψk dovej, k < i; ad esempio ψk sia la formula ψj → ψi. Per ipotesi induttiva,M |= ψj e M |= ψj → ψi e allora, per il Teorema 4.4 (1), M |= ψi.Infine, se ψi segue per generalizzazione da ψj con j < i, allora ψj euna formula ϕ(x) dove x e libera e ψi e la formula ∀xϕ(x). Per ipotesiinduttiva, M |= ϕ(x) e dunque, per il Teorema 4.4 (2), concludiamoche M |= ψi. �

Corollario 4.7. Sia T una L-teoria e sia ϕ una L-formula.

(1) Se M |= T e T ` ϕ allora M |= ϕ ;

(2) Se T e soddisfacibile allora T e coerente.

Dim. (1). Sia M |= T . Se T ` ϕ allora, per la (1), T |= ϕ, cioe ϕvale in ogni modello di T . In particolare M |= ϕ.

(2). Sia M |= T . Se per assurdo T fosse contraddittoria, alloraesisterebbe un enunciato τ tale che T ` τ e T ` ¬τ . Ma allora, per la(1), M |= τ e M |= ¬τ , e questo e impossibile. �

Gli enunciati hanno un ruolo fondamentale nel calcolo dei predicati.Come abbiamo gia visto, la loro validita in una fissata struttura nondipende dall’assegnamento sulle variabili. Anche nell’ambito sintatti-co del nostro sistema dimostrativo, non e restrittivo considerare soloformule senza variabili libere.

Definizione 4.8. Sia ϕ(x1, . . . , xn) una formula dove x1, . . . , xnsono tutte e sole le sue variabili libere. Si dice chiusura universaledella formula ϕ, e si denota con ϕ, l’enunciato “∀x1 . . . ∀xn ϕ”.

Proposizione 4.9. Sia T una L-teoria. Allora per ogni L-formulaϕ si ha l’equivalenza:

T ` ϕ ⇐⇒ T ` ϕ.

Dim. Se T ` ϕ allora applicando n volte la regola di generalizza-zione si ottiene che vale anche T ` ϕ. Viceversa, per ogni 1 ≤ i ≤ nsia ϕi la formula “∀xi ∀xi+1 . . . ∀xn ϕ”. Notiamo che ϕ1 coicide con lachiusura universale ϕ; notiamo inoltre che tutte le formule ϕi → ϕi+1

sono assiomi (Q1). Allora, partendo da T ` ϕ ed applicando n voltemodus ponens, si ottiene T ` ϕ. �

Il nostro sistema dimostrativo permette di dimostrare che il simbolodi uguaglianza si comporta in modo coerente rispetto al significato cheintendiamo attribuirgli.

Page 63: LOGICA MATEMATICA - unipi.it

1. UN SISTEMA FORMALE PER IL CALCOLO DEI PREDICATI 63

Definizione 4.10. Data una L-teoria T , definiamo la relazione ≈Tsull’insieme dei termini chiusi (cioe i termini senza variabili) ponendo:

t ≈ t′ ⇔ T ` t = t′ .

Notiamo che se il linguaggio L non contiene simboli di costante,allora non esistono termini chiusi.

Proposizione 4.11. Per ogni L-teoria T :

(1) La relazione ≈T e una relazione di equivalenza sull’insiemedegli L-termini chiusi ;

(2) Per ogni simbolo di funzione F di arieta n, se ti ≈T t′i per ognii = 1, . . . , n allora F(t1, . . . , tn) ≈T F(t′1, . . . , t

′n) ;

(3) Per ogni simbolo di relazione R di arieta k, se tj ≈T t′j per ognij = 1, . . . , k, allora T ` R(t1, . . . , tk)⇔ T ` R(t′1, . . . , t

′k).

Dim. (1). Dall’assioma dell’uguaglianza (E1) “x = x” segue pergeneralizzazione che ` ∀x(x = x). Allora per modus ponens dall’assio-ma (Q2) si ottiene che ` t = t, e quindi T ` t = t, per ogni terminechiuso t. Supponiamo ora che T ` t = t′. Applicando due volte lageneralizzazione all’assioma (E2) otteniamo ` ∀x∀y (x = y → y = x).Per l’assioma (Q2), ` ∀x∀y (x = y → y = x)→ (t = t′ → t′ = t). Allo-ra per modus ponens ` t = t′ → t′ = t e, di nuovo per modus ponens daT ` t = t′, si conclude che T ` t′ = t. La dimostrazione della proprietatransitiva e del tutto analoga, a partire dall’assioma dell’uguaglianza(E3).

(2). Per generalizzazione dall’assioma (E4), si ha che

` ∀x1 . . . ∀xn(x1 = y1∧. . .∧xn = yn)→ (F(x1, . . . , xn) = F(y1, . . . , yn))

e quindi, per modus ponens dall’assioma (Q2),

` (t1 = t′1 ∧ . . . ∧ tn = t′n)→ (F(t1, . . . , tn) = F(t′1, . . . , t′n)) .

Dall’ipotesi, segue per congiunzione che T ` (t1 = t′1 ∧ . . . ∧ tn = t′n) einfine, per modus ponens, si ottiene la tesi.

(3). Si procede in modo simile a sopra. Per generalizzazione dall’as-sioma (E5), si ottiene

` ∀x1 . . . ∀xn(x1 = y1∧. . .∧xk = yk)→ (R(x1, . . . , xk)↔ R(y1, . . . , yk))

e quindi, per modus ponens dall’assioma (Q2),

` (t1 = t′1 ∧ . . . ∧ tn = t′n)→ (R(t1, . . . , tk)↔ R(t′1, . . . , t′k)) .

Dall’ipotesi, segue per ripetute applicazioni della regola di congiunzioneche T ` (t1 = t′1 ∧ . . . ∧ tk = t′k) e quindi, per modus ponens, si ha

Page 64: LOGICA MATEMATICA - unipi.it

64 4. IL TEOREMA DI COMPLETEZZA

T ` R(t1, . . . , tk)↔ R(t′1, . . . , t′k). La tesi si ottiene ancora applicando

modus ponens a partire dalle istanze di tautologie

(R(t1, . . . , tk)↔ R(t′1, . . . , t′k))→ (R(t1, . . . , tk)→ R(t′1, . . . , t

′k)) ,

(R(t1, . . . , tk)↔ R(t1, . . . , tk))→ (R(t′1, . . . , t′k)→ R(t1, . . . , tk)) .

Nel sistema formale che abbiamo introdotto, l’implicazione si com-porta in modo coerente rispetto alle dimostrazioni.

Teorema 4.12 (di deduzione). Sia T una teoria, σ un enunciatoe ϕ una formula. Allora T, σ ` ϕ se e solo se T ` σ → ϕ.

Dim. Una implicazione e immediata. Infatti, banalmente T, σ ` σ.Inoltre, dall’ipotesi T ` σ → ϕ segue che anche T, σ ` σ → ϕ, permonotonia (cf. Proposizione 2.32 (2)). La tesi T, σ ` ϕ si ottieneinfine per modus ponens.

Viceversa, sia 〈ϕ1, . . . , ϕn = ϕ〉 una dimostrazione di ϕ dalla teoriaT∪{σ} nel sistema S. Per raggiungere la tesi, mostriamo per induzionesu k ≤ n che T ` σ → ϕk. Notiamo che ϕ1 ∈ T ∪ {σ} ∪ Ax. Se ϕ1 ∈T ∪Ax, banalmente T ` ϕ1; inoltre ϕ1 → (ϕ1 → σ) ∈ Ax e un assiomalogico perche e un’istanza di tautologia, e quindi T ` ϕ1 → (σ → ϕ1).Applicando la regola modus ponens si ottiene allora T ` σ → ϕ1.Se invece ϕ1 e σ, allora T ` σ → σ perche σ → σ e un’istanza ditautologia.

Occupiamoci ora del passo induttivo ϕk con k > 1. Se ϕk ∈ T ∪{σ} ∪Ax, procedendo esattamente come sopra si mostra che T ` σ →ϕk. Supponiamo ora che ϕk sia stata ottenuta dalle formule precedentiper modus ponens ; dunque esistono i, j < k tali che ϕj e la formulaϕi → ϕk. Per ipotesi induttiva, T ` σ → ϕi e T ` σ → (ϕi → ϕk).Adesso notiamo che la formula

(σ → ϕi)→ [ (σ → (ϕi → ϕk))→ (σ → ϕk) ]

e un’istanza di tautologia, e dunque e dimostrata da T . Applicandodue volte il modus ponens, si ottiene T ` σ → ϕk. Resta da conside-rare il caso in cui ϕk e ottenuta per generalizzazione da una formulaprecedente, cioe quando ϕk e la formula ∀xϕi(x) per qualche i < k.Per ipotesi induttiva, T ` σ → ϕi(x). Applicando la regola di genera-lizzazione, si ottiene T ` ∀x(σ → ϕ(x)). Visto che x non e libera in σ,che e un enunciato, per l’assioma di quantificazione (Q2) abbiamo cheT ` ∀x(σ → ϕ(x)) → (σ → ∀xϕ(x)). Finalmente, per modus ponensotteniamo la tesi T ` σ → ∀xϕ(x). �

Page 65: LOGICA MATEMATICA - unipi.it

2. PRELIMINARI PER IL TEOREMA DI COMPLETEZZA 65

Teorema 4.13 (Dimostrazione per assurdo). Sia T una teoria esia σ un enunciato. Allora:

(1) T ∪ {¬σ} e contraddittoria se e solo se T ` σ ;

(2) T ∪ {σ} e contraddittoria se e solo se T ` ¬σ.

Dim. (1). Se T ` σ, allora la teoria T ∪ {¬σ} dimostra sia σ che¬σ, ed e dunque una teoria contraddittoria. Viceversa, se T ∪ {¬σ}e contraddittoria, in particolare avremo che T,¬σ ` σ e quindi, peril Teorema di deduzione, T ` ¬σ → σ. Adesso, (¬σ → σ) → σ eun’istanza di tautologia e allora, applicando la regola di modus ponens,possiamo concludere che T ` σ. (2) si dimostra in modo del tuttosimile. �

Corollario 4.14. Sia T una teoria coerente. Allora per ognienunciato σ, almeno una tra le due teorie T∪{σ} e T∪{¬σ} e coerente.

Dim. Se T∪{σ} e T∪{¬σ} fossero entrambe contraddittorie, alloraallora T ` ¬σ e T ` σ, e quindi T sarebbe contraddittoria. �

Esercizio 4.15 (Procedimento per casi). Siano T una teoria e σ, τenunciati. Dimostrare che se T ∪ {σ} ` τ e T ∪ {¬σ} ` τ allora T ` τ .

2. Preliminari per il teorema di completezza

Un passo cruciale verso la dimostrazione del teorema di completezzadi Godel e il seguente risultato, che ci garantisce la possibilita di poterestendere ogni teoria coerente fino ad ottenere una teoria completa.

Teorema 4.16 (Lemma di Lindenbaum numerabile). AssumiamoZF (senza assioma di scelta). Se L e un linguaggio finito o numera-bile, allora ogni L-teoria coerente puo essere estesa ad una L-teoriacompleta.

Dim. Poiche il linguaggio e finito o numerabile, l’insieme di tuttigli L-enunciati e numerabile, diciamo {σn | n ∈ N}. Data una L-teoriacoerente T , definiamo per ricorsione una sequenza non-decrescente diteorie coerenti 〈Sn | n ∈ N0〉, a partire dalla base S0 = T . Al passoinduttivo n ≥ 1, poniamo Sn = Sn−1∪{σn} se quella teoria e coerente;altrimenti, poniamo Sn = Sn−1. Per induzione, segue subito che ogniSn e coerente. La teoria S =

⋃n∈N0

Sn e la teoria completa cercata.Infatti, intanto T = S0 ⊆ S. Inoltre, ogni sottoinsieme finito F ⊂ Se incluso in un livello Sn, ed e dunque coerente. Per compattezzasintattica, si ha allora che l’intera teoria S e coerente. Resta da vedereche S e coerente massimale, cioe che se τ e un enunciato e S ∪ {τ} e

Page 66: LOGICA MATEMATICA - unipi.it

66 4. IL TEOREMA DI COMPLETEZZA

coerente, allora τ ∈ S. Sia k tale che τ e l’enunciato σk; la coerenzadi S ∪ {σk} implica banalmente la coerenza di Sk−1 ∪ {σk}, e quindiσk ∈ Sk−1 ∪ {σk} = Sk ⊆ S. �

Ricordiamo la seguente proprieta:

• Lemma dell’ultrafiltro (UL): Ogni famiglia con la FIP puoessere estesa ad un ultrafiltro.

Teorema 4.17 (Lemma di Lindenbaum). Assumiamo ZF + UL.Ogni teoria coerente puo essere estesa ad una teoria completa.

Dim. Data una L-teoria coerente T , sia

T = {S ⊇ T | S e una L-teoria coerente},e per ogni L-enunciato τ , sia

Xτ = {S ∈ T | τ ∈ S o ¬τ ∈ S}.La famiglia {Xτ}τ ha la PIF. Infatti, siano τ1, . . . , τn enunciati. Indut-tivamente, poniamo S0 = T ; e per 0 ≤ i < n, poniamo Si+1 = Si∪{τi}se e una teoria coerente, altrimenti Si+1 = S ∪ {¬τi}. Applicandoil Corollario 4.14, e facile verificare per induzione che ogni Si ⊇ T ecoerente. Inoltre, per costruzione, Sn ∈

⋂ni=1Xτi . Dunque la fami-

glia {Xτ | τ L-enunciato} ha la FIP, e per UL, possiamo prendere unultrafiltro U su T che contiene tutti gli insiemi Xτ . Definiamo ora

X ′τ = {S ∈ T | τ ∈ S} e X ′′τ = {S ∈ T | ¬τ ∈ S}.Finalmente poniamo T ∗ = {τ | X ′τ ∈ U}. Se τ ∈ T , banalmenteX ′′τ = ∅ e quindi X ′τ = Xτ ∈ U e τ ∈ T ∗. Resta da verificare che T ∗

e completa. A questo scopo, basta notare che per ogni enunciato τ , siha Xτ = X ′τ ∪X ′′τ ∈ U , e quindi valgono le equivalenze:

τ /∈ T ∗ ⇔ X ′τ /∈ U ⇔ X ′′τ = X ′¬τ ∈ U ⇔ ¬τ ∈ T ∗.�

Un tipico modo di procedere quando si cerca di dimostrare cheuna certa proprieta vale per tutti gli oggetti in esame (ad esempio pertutti i numeri reali), e quello di considerare un oggetto “generico” (adesempio un numero reale non meglio specificato), e verificare che essosoddisfa quella proprieta. Il seguente risultato puo essere visto comeuna formalizzazione di questo tipo di procedura.

Proposizione 4.18. Sia T una L-teoria e sia c /∈ L un nuovosimbolo di costante. Se 〈ψ1, . . . , ψn〉 e una dimostrazione di T ` ϕnel linguaggio L ∪ {c} e y e una variabile che non compare in alcuna

Page 67: LOGICA MATEMATICA - unipi.it

2. PRELIMINARI PER IL TEOREMA DI COMPLETEZZA 67

delle formule ψi, allora 〈ψ1(y/c), . . . , ψn(y/c)〉 e una dimostrazione diT ` ϕ(y/c) nel linguaggio L.

Dim. Vediamo intanto che se ψ e un assioma logico nel linguaggioL∪{c} dove non compare y, allora ψi(y/c) e un assioma logico nel lin-guaggio L. Se ψ e un’istanza di tautologia A(ϑ1/X1, . . . , ϑk/Xk), doveA(X1, . . . , Xk) e una tautologia del calcolo proposizionale e ϑ1, . . . , ϑksono (L ∪ {c})-formule, allora ϕ(y/x) e un’istanza di tautologia nellinguaggio L, perche coincide con la formula A(ϑ′1/X1, . . . , ϑ

′k/Xk) do-

ve ϑ′i = ϑi(y/c) sono L-formule. Se ψ e un assioma dell’uguaglianza,allora il simbolo c non compare in ψ, e banalmente ψ(y/c) coincide conψ. Se ψ e un assioma (Q1) della forma ∀xϑ(x)→ ϑ(x) allora ψ(y/c) ela formula ∀xϑ′(x)→ ϑ′(x) dove ϑ′ e la L-formula ϑ(y/c), ed e quindiun assioma (Q2) nel linguaggio L. Analogamente, si verifica che se ψe un assioma (Q3), allora ψ(y/c) e un assioma (Q3) nel linguaggio L.Se ψ e un’assioma (Q2), la dimostrazione richiede maggiore attenzione.Supponiamo dunque che ψ sia della forma ∀xϑ(x) → ϑ(t/x) dove t eun (L ∪ {c})-termine le cui variabili non compaiono in ϑ. Sia adessoϑ′ la formula ϑ(y/c). Visto che y non appare in ψ, e facile controllareche ψ(y/c) coincide con la L-formula ∀xϑ′(x) → ϑ′(t′/x), dove t′ el’L-termine t(y/c); dunque ψ(y/c) e un assioma (Q2) nel linguaggio L.

Adesso mostriamo per induzione su i ≤ n che 〈ψ1(y/c), . . . , ψi(y/c)〉e una dimostrazione di T ` ψi(y/c) nel linguaggio L. Se ψ1 ∈ T allorac non appare in ψ1, quindi ψ1(y/c) coincide con ψ1 e la tesi segue ba-nalmente. Se ψ1 e un assioma logico nel linguaggio L ∪ {c} allora, perquanto visto sopra, ψ1(y/c) e un assioma logico nel linguaggio L, edanche in questo caso la tesi segue. Consideriamo ora il passo induttivoψj. Se ψj ∈ T o e un assioma logico, si procede come sopra. Suppo-niamo ora che ψj sia stata ottenuta per modus ponens dalle formuleψk e ψh dove k, h < j; ad esempio ψh sia la formula ψk → ψj. Notia-mo che ψh(y/c) coincide con la formula ψk(y/c)→ ψj(y/c), e dunqueψj(y/c) segue per modus ponens dalle formule ψk(y/c) e ψh(y/c). In-fine, supponiamo che ψj segua per generalizzazione da ψk con k < i.Allora ψk e una formula ϕ(x) dove x e libera e ψj e la formula ∀xϕ(x).Notiamo che ψk(y/c) e la formula ϕ(y/c) in cui x appare libera, eψj(y/c) e la formula ∀xϕ(y/c); concludiamo quindi che ψj(y/c) segueper generalizzazione da ψk(y/c). �

Come corollario otteniamo il seguente risultato, che sara di crucialeimportanza per la dimostrazione del Teorema di completezza.

Teorema 4.19 (della costante generica). Sia S una L-teoria, ϕuna L-formula dove x e l’unica variabile libera, e c /∈ L un nuovo

Page 68: LOGICA MATEMATICA - unipi.it

68 4. IL TEOREMA DI COMPLETEZZA

simbolo di costante. Allora S ` ϕ(c/x) nel linguaggio L∪{c} se e solose S ` ∀xϕ(x) nel linguaggio L.

Dim. Supponiamo prima S ` ∀xϕ(x) nel linguaggio L. La formula∀xϕ(x)→ ϕ(c/x) e un assioma logico (Q2) nel linguaggio L∪{c}. Permodus ponens, otteniamo allora che S ` ϕ(c/x) nel linguaggio L∪{c}.

Viceversa, prendiamo una dimostrazione 〈ψ1, . . . , ψn〉 di S ` ϕ(c/x)nel linguaggio L ∪ {c}, e prendiamo una variabile y che non compa-re in alcuna delle formule ψi. Allora, per la proposizione preceden-te, 〈ψ1(y/c), . . . , ψn(y/c)〉 e una dimostrazione di S ` ϕ(c/x)(y/c)nel linguaggio L. Visto che c non appare in ϕ, la doppia sostituzio-ne ϕ(c/x)(y/c) coincide con ϕ(y/x). Per generalizzazione segue cheS ` ∀y ϕ(y/x). Chiaramente la variabile x non appare in ϕ(y/x), eallora per (Q2) e modus ponens, si ottiene che S ` ϕ(y/x)(x/y). Maϕ(y/x)(x/y) coincide con ϕ e allora, di nuovo per generalizzazione, siconclude che S ` ∀xϕ(x). �

Particolare importanza avranno le teorie dove questo procedimentodella “costante generica” e – in un certo senso – incorporato al propriointerno.

Definizione 4.20. Sia ϕ(x) una formula con un’unica variabilelibera. Un simbolo di costante c si dice costante generica per ϕ nellateoria T se l’enunciato ϕ(c/x)→ ∀xϕ(x) appartiene a T .

Definizione 4.21. Una teoria H e una teoria di Henkin se ogniformula ϕ(x) con un’unica variabile libera ha una costante generica inH.

Notiamo che se H e di Henkin e H ⊆ H ′, allora anche H ′ e diHenkin.

Teorema 4.22. Assumiamo ZF (senza assioma di scelta). Ogniteoria coerente e inclusa in una teoria coerente di Henkin.

Dim. Sia T una L-teoria coerente. Definiamo per ricorsione unasequenza crescente di linguaggi Ln e di Ln-teorie Hn. Come base,poniamo H1 = T nel linguaggio L1 = L. Al passo induttivo, definiamoLn+1 come il linguaggio ottenuto aggiungendo ad Ln un nuovo simbolodi costante cψ per ogni Ln-formula ψ; e poniamo

Hn+1 = Hn ∪{ϕ(cϕ/x)→ ∀xϕ(x) | ϕ Ln-formula con VL(ϕ) = {x}} .Per costruzione, Hn+1 e una Ln+1-teoria dove ogni Ln-formula con un’u-nica variabile libera ha una costante generica. Sia L′ =

⋃n∈N Ln il

linguaggio contenente, oltre ai simboli di L, tutti i nuovi simboli di

Page 69: LOGICA MATEMATICA - unipi.it

3. IL TEOREMA DI COMPLETEZZA DI GODEL 69

costante introdotti. Vogliamo mostrare che la L′-teoria H =⋃n∈NHn

ha le proprieta richieste. Intanto H ⊃ T e una teoria di Henkin; infattiogni L′-formula con un’unica variabile libera e in realta una Ln-formulaper qualche n, e quindi ha una costante generica in Hn+1 ⊆ H.

Resta da verificare che la teoria H e coerente. Visto che ogni sotto-teoria finita di H e inclusa in un Hn, per il teorema di compattezza sin-tattico bastera verificare che tutti i livelliHn sono coerenti. Procediamoper induzione. La base e ovvia, perche H1 = T e coerente per ipotesi.Per il passo induttivo, di nuovo per il teorema di compattezza sintatti-co, bastera mostrare che ogni sottoinsieme finito Γ ⊂ Hn+1 e coerente.Notiamo che esistono un numero finito di Ln-formule ϕ1(x), . . . , ϕk(x)aventi x come unica variabile libera, tali che

Γ ⊆ Hn ∪ {ϕi(cϕi/x)→ ∀xϕi(x) | i = 1, . . . , k} .

Senza perdita di generalita possiamo supporre che le formule ϕi /∈ Hm

per m < n, e quindi che i simboli di costante cϕi/∈ Ln. Visto che

Hn e coerente per ipotesi induttiva, la tesi segue applicando k volte laseguente proprieta:

• Se S e una L-teoria coerente, ϕ(x) e una L-formula aventex come unica variabile libera, e c /∈ L e un nuovo simbolo dicostante, allora anche S ∪ {ϕ(c/x) → ∀xϕ(x)} e una teoriacoerente.

Supponiamo per assurdo che la teoria S ∪ {ϕ(c/x) → ∀xϕ(x)} siacontraddittoria. Allora, per il Teorema di deduzione, S ` ¬(ϕ(c/x)→∀xϕ(x)). Visto che ¬(P → Q) → P e ¬(P → Q) → ¬Q sono tau-tologie, per modus ponens si ottiene che S ` ϕ(c/x) e S ` ¬∀xϕ(x).Adesso, per il Lemma della costante generica, da S ` ϕ(c/x) segue cheS ` ∀xϕ(x), e quindi si ottiene l’assurdo che S e contraddittoria. �

3. Il Teorema di completezza di Godel

Il fondamentale risultato della completezza del calcolo dei predicatidel primo ordine, seguira dall’esistenza di modelli per ogni teoria dihenkin.

Teorema 4.23. Assumiamo ZF (senza assioma di scelta). OgniL-teoria completa di Henkin H ha un modello canonico M |= H dove|M | ≤ max{|L|,ℵ0}.

Dim. Consideriamo l’insieme CT(L) degli L-termini chiusi, cioe deitermini t senza variabili. Visto che H e una teoria di Henkin, devono

Page 70: LOGICA MATEMATICA - unipi.it

70 4. IL TEOREMA DI COMPLETEZZA

esistere simboli di costante in L, e quindi CT(L) 6= ∅. Consideriamoora la seguente relazione su CT(L):

• t ≈ t′ ⇔ (t = t′) ∈ H (o, equivalentemente, H ` t = t′).

Usando gli assiomi logici dell’uguaglianza (E1), (E2), (E3), si dimo-stra che ≈ e una relazione di equivalenza (vedi Esercizio 4.11). Comeuniverso della L-struttura M prendiamo l’insieme quoziente:

M = CT(L)/ ≈ .

Denotiamo con t = {s | s ≈ t} la classe di ≈-equivalenza del terminechiuso t. Notiamo che M , in quanto quoziente di un insieme di stringhefinite di simboli in L, ha cardinalita |M | ≤ max{|L|,ℵ0}.

Per interpretare i simboli del linguaggio, procediamo nel modo piuovvio, facendo in modo che tutti i termini chiusi siano interpretati inM dalla loro classe di equivalenza. Precisamente:

• Ogni simbolo di costante c ∈ L e interpretato dalla corrispon-dente classe di equivalenza c.• Ogni simbolo di funzione F ∈ L di arieta n e interpretato

come la funzione FM : Mn → M dove, per tutti i terminichiusi t1, . . . , tn,

FM(t1, . . . , tn) = F(t1, . . . , tn).

• Ogni simbolo di relazione R ∈ L di arieta k e interpretatoponendo per tutti i termini chiusi t1, . . . , tk:

(t1, . . . , tk) ∈ RM ⇔ R(t1, . . . , tk) ∈ H.

Le definizioni date di FM e RM sono ben poste, perche non dipen-dono dai rappresentanti scelti nelle classi di equivalenza. Infatti, dagliassiomi dell’uguaglianza segue che se ti ≈T t′i per i = 1, . . . , n, alloraf(t1, . . . , tn) ≈T f(t′1, . . . , f

′n). Inoltre, se tj ≈T t′j per i = 1, . . . , k,

allora H ` R(t1, . . . , tk)⇔ H ` R(t′1, . . . , t′k) (vedi Proposizione 4.11).

Infine, ricordiamo che la completezza di H garantisce H ` σ ⇔ σ ∈ Hper ogni enunciato σ.

Se ρ : Var → CT(L), denotiamo con ρ : Var → M l’assegnamentodelle variabili su M che si ottiene passando alle classi di equivalenza,cioe ρ(x) = ρ(x). Introduciamo una notazione che semplifichera unpo’ la scrittura. Per ogni termine s = s(x1, . . . , xk) le cui variabililibere sono x1, . . . , xk, e per ogni ρ : Var → CT(L), denotiamo con sρil seguente termine chiuso:

sρ : s(t1/x1, . . . , tk/xk) dove ti = ρ(xi).

Page 71: LOGICA MATEMATICA - unipi.it

3. IL TEOREMA DI COMPLETEZZA DI GODEL 71

Analogamente, se ψ(x1, . . . , xk) e una formula le cui variabili liberesono x1, . . . , xk, se t1, . . . , tk sono termini chiusi, e se ρ : Var→ CT(L),denotiamo con ψρ il seguente enunciato:

ψρ : ψ(t1/x1, . . . , tk/xk) dove ti = ρ(xi).

La tesi segue dalle due seguenti proprieta:

(a) Per ogni termine s, si ha sM,ρ = sρ ;

(b) Per ogni formula ψ, si ha M |= ψ [ ρ ] ⇐⇒ ψρ ∈ H.

Infatti, ogni assegnamento su M e della forma ρ per qualche funzio-ne ρ : Var→ CT(L). Inoltre, se σ e un enunciato, banalmente σρ = σ,e quindi da (b) si conclude che M |= τ per ogni τ ∈ H.

(a). Procediamo per induzione sulla costruzione del termine s. Ses e una variabile x, e ρ(x) = t, allora sρ e il termine t, e quindi sM,ρ =ρ(x) = t = sρ. Se s e un simbolo di costante c, allora sρ coincide con c,e cM,ρ = cM = c = sρ. Infine, se s e un termine del tipo F(u1, . . . , un)dove F e un simbolo di funzione di arieta n e gli ui sono termini, allora:

F(u1, . . . , un)M,ρ = FM(u1M,ρ, . . . , un

M,ρ) = (per ipotesi induttiva)

= FM(

(u1)ρ, . . . , (un)ρ

)= F((u1)ρ, . . . , (un)ρ) = F(u1, . . . , un)ρ.

(b). Procediamo per induzione sulla costruzione di ψ, a partiredalle formule atomiche. Supponiamo prima che ψ sia una identita tradue termini “s = u”. In questo caso:

M |= s = u [ ρ ] ⇔ sM,ρ = uM,ρ ⇔ (per la (a))

sρ = uρ ⇔ H ` sρ = tρ ⇔ (s = t)ρ ∈ H.Sia ora ψ = R(s1, . . . , sk), dove R e un simbolo di relazione di arietak e gli sj sono termini. Allora:

M |= R(s1, . . . , sn)[ ρ ] ⇔ (s1M,ρ, . . . , sn

M,ρ) ∈ RM ⇔ (per la (a))((s1)ρ, . . . , (sn)ρ

)∈ RM ⇔ R((s1)ρ, . . . , (sn)ρ) ∈ H ,

cioe, R(s1, . . . , sn)ρ ∈ H. Se ψ e della forma ¬ϕ allora, usando l’ipotesiinduttiva e la completezza di H,

M |= ¬ϕ [ ρ ] ⇔ M 6|= ϕ [ ρ ] ⇔ ϕρ /∈ H ⇔ ¬ (ϕρ) ∈ H ,

cioe (¬ϕ)ρ ∈ H. Riguardo la congiunzione, se ψ e della forma ϕ ∧ ϑallora, usando l’ipotesi induttiva e la completezza di H,

M 6|= (ϕ ∧ ϑ) [ ρ ] ⇔ M |= ϕ [ ρ ] e M |= ϑ [ ρ ] ⇔

ϕρ ∈ H e ϑρ ∈ H ⇔ (ϕρ ∧ ϑρ) ∈ H , cioe (ϕ ∧ ϑ)ρ ∈ H.

Page 72: LOGICA MATEMATICA - unipi.it

72 4. IL TEOREMA DI COMPLETEZZA

Resta da verificare il caso della quantificazione, dove sara crucialel’ipotesi che H e una teoria di Henkin. Sia ψ della forma ∀xϕ doveVL(ϕ) = {x, x1, . . . , xn}. Notiamo che (∀xϕ)ρ = ∀xϑ(x), dove ϑ(x) ela formula ϕ(x, ρ(x1)/x1, . . . , ρ(xn)/xn) che ha x come unica variabilelibera. Notiamo inoltre che per ogni termine chiuso t, la formula ϑ(t/x)coincide con ϕρ(t/y), dove ρ(t/x) : Var → CT(L) e la funzione checoincide con ρ tranne che sulla variabile x, cui assegna il valore t. Vistoche H e di Henkin, esiste un simbolo di costante generica cϑ per ϑ(x)in H, cioe la formula ϑ(cϑ/x) → ∀xϑ(x) appartiene a H. Applicandomodus ponens e l’assioma (Q2), per la proprieta di completezza di Habbiamo allora che

ϑ(cϑ/x) ∈ H ⇒ ∀xϑ(x) ∈ H, cioe (∀xϕ)ρ ∈ H ⇒

ϑ(t/x) ∈ H per ogni t ∈ CT(L), cioe ϕρ(t/x) ∈ H per ogni t ∈ CL(L).

La seguente serie di implicazioni conclude la dimostrazione:

M |= ∀xϕ [ ρ ] ⇔ M |= ϕ [ ρ(t/x)] per ogni t ∈ CT(L) ⇒

M |= ϕ [ ρ(cϑ/x)] ⇔ (per ip. ind.) ϕρ(cϑ/x) ∈ H, cioe ϑ(cϑ/x) ∈ H ⇒

(∀xϕ)ρ ∈ H ⇒ ϕρ(t/x) ∈ H per ogni t ∈ CL(L) ⇔ (per ip. ind.)

M |= ϕ [ ρ(t/x) ] per ogni t ∈ CT(L) ⇔ M |= ∀xϕ [ ρ ].

Possiamo finalmente formulare il teorema fondamentale del calcolodei predicati del primo ordine.

Teorema 4.24 (Completezza di Godel – caso numerabile). Assu-miamo ZF (senza assioma di scelta). Sia L un linguaggio del primoordine finito o numerabile. Allora:

(1) Ogni L-teoria coerente ha un modello ;

(2) Per ogni L-teoria T e per ogni L-formula ϕ si ha l’equivalenzaT ` ϕ⇔ T |= σ.

Dim. (1). Data una L-teoria coerente T , grazie al Teorema 4.22possiamo estenderla ad una L′-teoria di Henkin H ′ ⊇ T , per un op-portuno linguaggio L′ ⊇ L. Per il teorema di Lindenbaum numerabile(Teorema 4.16), possiamo estendere poi H ′ ad una L′-teoria completaH ⊇ H ′. Notiamo che anche H ′ e una L′-teoria di Henkin. Infine,grazie al Teorema 4.23, possiamo trovare un modello N |= H. Se M ela L-struttura ottenuta restringendo la L′-struttura N al linguaggio L,chiaramente M |= T .

Page 73: LOGICA MATEMATICA - unipi.it

3. IL TEOREMA DI COMPLETEZZA DI GODEL 73

(2) segue direttamente da (1) e dal Teorema 4.13. Valgono infattile seguenti equivalenze: T 6` σ se e solo se T ∪ {¬σ} e coerente, se esolo se esiste un modello M |= T ∪ {¬σ}, se e solo se T 6|= σ. �

Il caso generale per linguaggi di cardinalita arbitraria richiede UL(Ultrafilter Lemma).

Teorema 4.25 (Completezza – Godel). Assumiamo ZF+UL. Al-lora:

(1) Ogni teoria coerente ha un modello ;

(2) Per ogni L-teoria T e per ogni L-formula ϕ si ha l’equivalenzaT ` ϕ⇔ T |= σ.

Dim. Si dimostra esattamente come il teorema precedente, usandopero la forma generale del Teorema di Lindenbaum (Teorema 4.17),che richiede UL. �

I teoremi fondamentali del calcolo dei predicati, cioe completezza ecompattezza semantica per linguaggi arbitrari, possono essere visti co-me forme deboli dell’assioma di scelta; hanno infatti hanno esattamentela stessa forza dell’Ultrafilter Lemma.

Teorema 4.26. Assumiamo ZF (senza assioma di scelta). Sonoproprieta equivalenti:

(1) Teorema di complezza: Ogni teoria coerente della logica delprimo ordine ha un modello ;

(2) Teorema di compattezza semantico: Ogni teoria della logicadel primo ordine finitamente soddisfacibile e soddisfacibile ;

(3) UL (Ultrafilter Lemma): Ogni filtro si estende ad un ultrafiltro.

Dim. (1) ⇒ (2). Sia T una teoria finitamente soddisfacibile. Ognisuo sottoinsieme finito e coerente perche ha un modello. Ma allora, perla compattezza sintattica, l’intera teoria T e coerente, e dunque l’ipotesigarantisce l’esistenza di un suo modello M |= T .

(2) ⇒ (3). Data una famiglia G di sottoinsiemi di I con la FIP,consideriamo il linguaggio L = {A(x) | A ⊆ I} che contiene un simbolodi relazione di arieta 1 per ogni sottoinsieme di I. Sia M la L-strutturaavente I come universo, e dove i simboli A sono interpretati nel modonaturale, cioe i ∈ AM ⇔ i ∈ A. Introduciamo ora un nuovo simbolo dicostante c e consideriamo la (L∪{c})-teoria T che consiste dei seguentienunciati:

(I) “¬Ø(c)” ;

Page 74: LOGICA MATEMATICA - unipi.it

74 4. IL TEOREMA DI COMPLETEZZA

(II) “A(c)→ B(c)” ogni volta che A ⊆ B ;

(III) “(A(c) ∧B(c))→ C(c)” ogni volta che A ∩B = C ;

(IV) “¬A(c)↔ Ac(c)” per ogni A ⊆ I ;

(V) “A(c)” per ogni A ∈ G.

Se T0 ⊂ T e finito, allora soltanto un numero finito di simboliA1, . . . ,An appaiono negli enunciati di T . Espandiamo la L-strutturaM al linguaggio L ∪ {c}, interpretando il nuovo simbolo di costante ccome un elemento che appartiene a tutti quegli Aj che appartengonoa G (nel caso in cui nessun Aj appartenesse a G, prendiamo i ∈ I

qualunque). Notiamo che questo e possibile perche G ha la FIP. Efacile verificare che questa L ∪ {c}-struttura e un modello di T0. Percompattezza semantica, esiste allora un modello N |= T dell’interateoria T . Verifichiamo che la famiglia

U = {A ⊆ I | N |= A(c)}e l’ultrafiltro cercato. L’insieme vuoto ∅ /∈ U perche N soddisfa (I).La validita degli enunciati (II) e (III) in N garantisce che la famigliaU e chiusa rispettivamente per soprainsieme e per intersezione. Dallavalidita degli assiomi (IV) in N si ottiene che A /∈ U ⇔ Ac ∈ U .Dunque U e un ultrafiltro. Infine G ⊆ U perche N soddisfa gli enunciati(V).

(3) ⇒ (1). Come abbiamo visto sopra, il Teorema di completezzasi dimostra nella teoria ZF+UL. �

Notiamo che la dimostrazione (1) ⇒ (2) di sopra fornisce una di-mostrazione alternativa al Teorema di compattezza semantico, diversada quella gia vista con l’uso di ultraprodotti (vedi Teorema 3.59).

UL e in effetti una forma debole dell’assioma di scelta AC, comemostrato dai seguenti risultati:

• ZF + AC ` UL (vedi Teorema 3.49).

• Esistono modelli M |= ZF dove non esistono ultrafiltri non-principali su N (Feferman 1965). Dunque, ZF 6` UL.

• Esistono modelli M |= ZF + UL dove non vale l’assioma discelta (Halpern-Levy 1971). Dunque, ZF + UL 6` AC.