applicare ripetutamente la seguente operazione: trasformare le sotto-formule del tipo (QxA)(Q 0 yB) dove Q, Q 0 sono quantificator

e  è ∨ oppure ∧, in QzQ0w (A_{Jz/xK  BJw/yK) dove z è sostituibile}

in A e non occorre libera in B e w è sostituibile in B e non occorre libera in A.

La forma prenessa equivalente ad una data formula è ben lungi dall’essere unica — per esempio, poiché AB è equivalente a BA, nel Passo 3 possiamo trasformare (QxA)  (Q0yB) in Q0wQz (AJz/xK  BJw/yK). In particolare anche

∀w∀x∃y ((P (x, y) ∧ ¬Q(x)) ∨ R(w) ∨ S(z)) è una formula prenessa equivalente alla (3.2).

Se si trasforma in forma prenessa ∀xϕ ⇒ ψ oppure ∃xϕ ⇒ ψ dove x non occorre libera in ψ, si ottiene rispettivamente ∃x (ϕ ⇒ ψ) e ∀x (ϕ ⇒ ψ). In altre parole: se B non menziona x, un’affermazione del tipo

se per qualche x vale A di x, allora è vero che B è equivalente a

per ogni x, se vale A di x, allora è vero che B. Per esempio la frase

se y è un quadrato, allora è maggiore o uguale a zero si formalizza come

∃x (y = x · x) ⇒ y ≥ 0 o equivalentemente come

∀x (y = x · x ⇒ y ≥ 0) . L’altra equivalenza tra

se per ogni x vale A di x, allora è vero che B e

c’è un x per cui A di x implica che B

è più sorprendente (intuitivamente saremmo portati a pensare che ∀xϕ ⇒ ψ debba essere equivalente a ∀x (ϕ ⇒ ψ)) e mostra come l’uso disinvolto dei quantificatori nel linguaggio comune sia prono ad errori. Per esempio, consideriamo il seguente enunciato della teoria degli insiemi:8

due insiemi sono uguali se hanno gli stessi elementi.

Si formalizza così

∀x∀y (∀z (z ∈ x ⇔ z ∈ y) ⇒ x = y) , che in forma prenessa diventa

∀x∀y∃z ((z ∈ x ⇔ z ∈ y) ⇒ x = y) , e che si legge

dati due insiemi x e y c’è un elemento z tale che: se z appartiene ad x se e solo se z appartiene ad y, allora x e y coincidono.

Viene naturale chiedersi chi sia questo elemento z! Per scoprirlo basta prendere il contrappositivo di quanto scritto tra le parentesi, cioè

∀x∀y∃z (x 6= y ⇒ ((z ∈ x ∧ z /∈ y) ∨ (z ∈ y ∧ z /∈ x))) che si legge:

dati due insiemi x e y c’è un elemento z tale che: se x e y sono distinti, allora z appartiene ad uno dei due insiemi ma non all’altro.

Quindi, dati due insiemi x e y basta scegliere uno z che sta in uno dei due insiemi ma non nell’altro, nel caso in cui x 6= y, oppure z arbitrario nel caso in cui x = y.

È possibile dimostrare risultati sulle formule in forma prenessa procedendo per induzione sulla lunghezza del prefisso: si dimostra che una certa proprietà P vale per le formule prive di quantificatori, e che se P vale per una certa ϕ, allora vale anche per ∃xϕ e per ∀xϕ. Poiché ogni formula è equivalente ad una in forma prenessa, questo metodo può essere usato per dimostrare che una proprietà P vale per tutte le formule.

La lunghezza del prefisso è una nozione di complessità per le formule in forma prenessa, analoga alla nozione di lunghezza e altezza introdotte alla fine della Sezione 3.A. Tuttavia, in molte applicazioni, è più utile uti- lizzare un’altra misura di complessità, basata sull’alternanza di blocchi di quantificatori nel prefisso:

• se il prefisso è costituito da un unico blocco di quantificatori universali si ha una ∀-formula; se è costituito da un unico blocco di quantificatori esistenziali si ha una ∃-formula,

• se il prefisso è costituito da un blocco di quantificatori universali seguito da un blocco di quantificatori esistenziali si ha una ∀∃-formula; se è costituito da un blocco di quantificatori esistenziali seguito da un blocco di quantificatori universali si ha una ∃∀-formula,

• se il prefisso è costituito da un blocco di quantificatori universali seguito da un blocco di quantificatori esistenziali seguito da un blocco di quanti- ficatori universali si ha una ∀∃∀-formula; se è costituito da un blocco di quantificatori esistenziali seguito da un blocco di quantificatori universali seguito da un blocco di quantificatori esistenziali si ha una ∃∀∃-formula, e così via. La negazione di una ∀-formula è equivalente ad una ∃-formula, e viceversa; la negazione di una ∀∃-formula è equivalente ad una ∃∀-formula, e viceversa; la negazione di una ∀∃∀-formula è equivalente ad una ∃∀∃-formula, e viceversa; ecc.

3.D. Soddisfazione di enunciati. Fissiamo un linguaggio del prim’ordine

L. Chiaramente L verrà scelto in funzione del tipo di struttura che si intende

studiare — per studiare i campi avremo bisogno di due simboli per le operazioni di somma + e prodotto ·, un simbolo di operazione unaria − per denotare l’opposto di un numero, più i simboli per lo zero 0 e per l’unità del campo 1; per studiare i gruppi abeliani ordinati dobbiamo usare un linguaggio con un simbolo + per l’operazione di somma gruppale e un simbolo _{C per} l’ordinamento, ecc. Una struttura per L o L-struttura consiste di:

• un insieme non vuoto M , detto universo o dominio della struttura, • degli elementi privilegiati cM _{di M , uno per ogni simbolo di costante c del}

linguaggio L,

• delle operazioni ∗M_{, +}M_{, . . ., una per ogni simbolo di operazione ∗, +, . . .}

del linguaggio L,

• dei sottoinsiemi PM _{⊆ M}n_{, uno per ogni simbolo P di predicato n-ario}

del linguaggio L.

Talvolta, al fine di uniformarci all’uso comune o se questo aiuta la leg- gibilità, useremo la lettera M come pedice invece che apice e scriveremo

cM, ∗M, +M, PM. . . per indicare gli elementi privilegiati, le operazioni, i

sottoinsiemi della struttura. Quando non c’è pericolo di confusione iden- tificheremo la struttura con il suo domino, come avviene negli altri campi della matematica — in algebra si dice “dato un gruppo G” e raramente si deve ricorrere ad espressioni del tipo “dato un gruppo (G, ∗)”. Se invece è necessario distinguere la struttura dal suo universo (per esempio quando abbiamo strutture distinte sullo stesso universo) utilizzeremo le lettere corsive M, N, . . . per le strutture.

Il linguaggio per i gruppi ha un simbolo di operazione binaria ·, un simbolo di operazione unaria f , e un simbolo di costante 1. Al fine di uniformarci con la notazione usuale in matematica, scriveremo x−1 invece di f (x). Le formule atomiche sono della forma t1 = t2, con t1 e t2 termini.

Una struttura per questo linguaggio consiste di un insieme M con un elemento privilegiato 1M, un’operazione binaria (x, y) 7→ x ·My, ed un’opera-

zione unaria x 7→ x−1M_{. Diremo che M è un gruppo se soddisfa gli enunciati}

∀x∀y∀z (x · (y · z) = (x · y) · z) (3.8a) ∀x (x · 1 = x ∧ 1 · x = x) (3.8b) ∀xx · x−1= 1 ∧ x−1· x = 1. (3.8c)

Volendo essere particolarmente stringati potremmo prendere come unico assioma per la teoria dei gruppi la congiunzione dei tre enunciati precedenti.9 Se L è il linguaggio per studiare i campi ordinati, allora una struttura per questo linguaggio è data da un insieme M con due elementi privilegiati 0M e 1M (non necessariamente distinti), due operazioni binarie +M e ·M, un’operazione unaria −M, e una relazione binaria <M. Naturalmente M in generale non sarà un campo ordinato — per assicurarci che ciò avvenga dobbiamo richiedere che la struttura M soddisfi gli assiomi per i gruppi abeliani ∀x∀y∀z ((x + y) + z = x + (y + z)) (3.9a) ∀x∀y (x + y = y + x) (3.9b) ∀x (x + 0 = x ∧ 0 + x = x) (3.9c) ∀x (x + (−x) = 0 ∧ (−x) + x = 0) , (3.9d)

più quelli che servono per gli anelli unitari

∀x∀y∀z ((x · y) · z = x · (y · z)) (3.10a) ∀x (x · 1 = x ∧ 1 · x = x) (3.10b) ∀x∀y∀z ((x + y) · z = (x · z) + (y · z)) , (3.10c)

più la commutatività del prodotto

(3.11) ∀x∀y (x · y = y · x) , più gli assiomi per i campi

0 6= 1 (3.12a)

∀x (x 6= 0 ⇒ ∃y (x · y = 1)) , (3.12b)

più gli assiomi per gli ordini totali

¬∃x (x < x) (3.13a) ∀x∀y∀z(x < y ∧ y < z ⇒ x < z) (3.13b) ∀x∀y (x < y ∨ x = y ∨ y < x) . (3.13c)

Infine dobbiamo avere degli assiomi che garantiscono la compatibilità dell’or- dinamento con le operazioni algebriche

∀x∀y∀z (x < y ⇒ x + z < y + z) (3.14a)

∀x∀y (0 < x ∧ 0 < y ⇒ 0 < x · y) . (3.14b)

Dire che M soddisfa un enunciato σ di L significa che se sostituiamo i simboli 0, 1, +, ·, −, < con le costanti, le operazioni e la relazione binaria di M , e se restringiamo i quantificatori agli elementi di M , otteniamo un’affermazione vera in M . Per esempio, dire che la struttura

(M, +M, ·M, −M, <M, 0M, 1M) soddisfa l’enunciato (3.12b) equivale ad asserire che

∀x ∈ Mx 6= 0M ⇒ ∃y ∈ Mx ·M y = 1M

mentre dire che M soddisfa l’enunciato (3.14b) significa che ∀x, y ∈ M (0 <M x ∧ 0 <M y ⇒ 0 <M x ·M y).

Come si vede da questi esempi, gli apici per le operazioni, costanti e relazioni di M appesantiscono eccessivamente la scrittura, per cui verranno soppressi, quando questo non causa confusione.

Se M è una L-struttura e σ un enunciato di L, scriveremo

M  σ

per dire che la struttura M soddisfa l’enunciato σ; equivalentemente diremo che σ è vero in M . Quando ciò non accade scriveremo M 6_{ σ. Osserviamo} che

la scrittura. . . equivale a dire. . .

M  ¬σ M 6 σ,

M  σ ∧ τ M  σ e M  τ,

M  σ ∨ τ M  σ oppure M  τ,

M  σ ⇒ τ se M _{ σ allora M  τ,}

M  σ ⇔ τ M  σ se e solo se M  τ.

Se M rende vero ogni σ appartenente ad un insieme Σ di enunciati, diremo che M è un modello di Σ, in simboli

M  Σ.

Poiché una struttura soddisfa una congiunzione se e solo se soddisfa tutte le formule di cui la congiunzione è costituita, dire che M è un modello di un insieme finito di enunciati {σ1, . . . , σn} equivale a dire che M V1≤i≤nσi.

Ricapitolando, abbiamo visto alcuni linguaggi del prim’ordine utili per studiare alcune classi di strutture matematiche:

• L_gruppi ha un simbolo di operazione binaria ·, un simbolo di operazione unaria −1 e un simbolo di costante 1. Una L_gruppi-struttura è un gruppo se e solo se soddisfa l’insieme Σ_gruppi formato dagli enunciati (3.8). • L_{gruppi a.}è ottenuto da L_gruppi rimpiazzando i simboli ·,−1 e 1 con +, −

e 0. Una L_{gruppi a.}-struttura è un gruppo abeliano se e solo se soddisfa l’insieme Σ_{gruppi a.}formato dagli enunciati (3.9).

• L_anelli è ottenuto aggiungendo ad L_{gruppi a.} il simbolo · di operazione binaria. Una L_anelli-struttura è un anello se soddisfa l’insieme Σ_anelli ottenuto aggiungendo a Σ_{gruppi a.} gli enunciati (3.10a) e (3.10c), ed è un anello commutativo se soddisfa Σ_{anelli c.}, l’insieme di enunciati ottenuto aggiungendo a Σ_anelli la (3.11).

• L_anelli-1 è ottenuto da L_anelli aggiungendo il simbolo di costante 1 e una sua struttura è un anello unitario se soddisfa l’insieme di enunciati Σ_anelli-1 dato da Σ_anelli con l’aggiunta di (3.10b). Se aggiungiamo anche la (3.11) otteniamo l’insieme di enunciati Σ_{anelli c.}, i cui modelli sono gli anelli commutativi unitari; aggiungendo anche gli enunciati (3.12) si ottiene Σ_campi i cui modelli sono i campi.

• Aggiungendo a L_anelli-1 un simbolo di relazione binaria < si ottiene il linguaggio L_{anelli o.}. Un campo ordinato è una L_{anelli o.}-struttura che soddisfa l’insieme di enunciati Σ_{campi o.}, ottenuto aggiungendo a Σ_campi gli enunciati (3.13) e (3.14).

Osservazioni 3.7. (a) Se M _{ Σ e Σ è un insieme infinito di enunciati} infinito, per esempio Σ = {σ_{n| n ∈ N}, siamo tentati di dire che M} soddisfa la congiunzione infinita V

n∈Nσn. Tuttavia dobbiamo resistere

stoicamente a questa tentazione, dato che V

n∈Nσn non è una formula

di un linguaggio del prim’ordine. Ci sono sistemi formali, le logiche infinitarie, in cui è consentito formare congiunzioni e disgiunzioni di infinite formule, ma queste fanno parte di argomenti più avanzati e non verranno trattate in questo libro.

(b) Quando valutiamo se un enunciato σ è vero in una struttura M , la quantificazione avviene sugli elementi di M e non sui sottoinsiemi di

M . Questo vincolo è ciò che caratterizza i linguaggi e la logica del

prim’ordine. Per quantificare anche sui sottoinsiemi della struttura si deve introdurre una nuova lista di variabili per denotare i sottoinsiemi ed un simbolo ∈ per specificare quando un elemento della struttura appartiene ad un sottoinsieme, e la relazione di soddisfazione deve essere modificata in modo da distinguere tra i due livelli di quantificazione (su elementi o su insiemi). Il sistema che si ottiene va sotto il nome di logica del second’ordine. Se si è più ambiziosi è possibile definire la logica del terz’ordine, in cui ci sono tre livelli di quantificazione (su

elementi, su sottoinsiemi, su famiglie di sottoinsiemi) o, più in generale, è possibile definire la logica di ordine n. Le logiche di ordine n > 1 si dicono logiche di ordine superiore è hanno un potere espressivo molto superiore rispetto alla logica del prim’ordine. Tuttavia, come spesso capita in matematica, la ricerca dell’eccessiva generalità va a scapito della profondità dei risultati, per cui in questo libro, come nella maggior parte dei manuali, ci concentreremo principalmente sulla logica del prim’ordine.

Diremo che un enunciato τ è conseguenza logica di un insieme Σ di enunciati (del medesimo linguaggio del prim’ordine), o che τ discende logicamente da Σ, in simboli

Σ |= τ se

M  Σ implica che M  τ, per ogni L-struttura M .

Quando Σ = {σ} è costituito da un unico enunciato identificheremo Σ con σ e diremo che τ è conseguenza logica di σ, in simboli σ |= τ. Equivalen- temente: τ è conseguenza logica di σ se σ ⇒ τ è un enunciato valido. Due enunciati σ e τ si dicono logicamente equivalenti se uno è conseguenza logica dell’altro, cioè se

σ|= τ e τ|= σ; equivalentemente, se σ ⇔ τ è un enunciato valido.

Attenzione. Non si deve confondere_{ la relazione di soddisfazione, con |=} la relazione di conseguenza logica — sono nozioni distinte anche se usano simboli simili! La relazione di soddisfazione (M _{ σ) è una relazione tra}

L-strutture ed enunciati (o insiemi di enunciati), mentre la relazione di

conseguenza logica (Σ |= σ) è una relazione tra insiemi di enunciati e singoli enunciati. Nella maggioranza dei testi, le due nozioni sono denotate con il medesimo simbolo, ma noi abbiamo preferito, almeno per questo capitolo, adottare questa variante notazionale per aiutare il lettore a non confondere le due nozioni.

Definizione 3.8. (i) Una teoria del prim’ordine o semplicemente teo- ria è un insieme T di enunciati di un linguaggio del prim’ordine L, che si dice linguaggio di T .

(ii) Un sistema di assiomi per una teoria T è un insieme Σ di enunciati del linguaggio di T tale che per ogni enunciato σ

Σ |= σ se e solo se T |= σ.

(iii) Una teoria si dice finitamente assiomatizzabile se ammette un sistema finito di assiomi.

Le due espressioni “teoria” e “insieme di enunciati” denotano lo stesso concetto, ma la prima è particolarmente comoda per indicare delle assio- matizzazioni al prim’ordine di settori della matematica. Quindi parleremo di teoria del prim’ordine dei gruppi abeliani, teoria del prim’ordine degli

anelli, teoria del prim’ordine dei campi, . . . per indicare le teorie che hanno

per sistemi di assiomi rispettivamente Σ_{gruppi a.}, Σ_anelli, Σ_campi . . . . Invece riserveremo le locuzioni teoria dei gruppi abeliani, teoria degli anelli, teoria

dei campi, . . . , per indicare genericamente certe parti della matematica.

Osservazione 3.9. Ogni teoria T , in quanto insieme di enunciati, è un