METODO ASSIOMATICO E TEORIA DEGLI INSIEMIa.a. 2013/14

TEORIE ASSIOMATICHEVersione provvisoria e incompleta∗

Alberto ZanardoDipartimento di Matematica - Universita di Padova

Maggio 2014

Indice

1 Prime nozioni sulle Teorie Assiomatiche 21.1 Deduzione Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Linguaggi del primo ordine - Interpretazioni e Modelli 5

3 Prime proprieta delle Teorie Assiomatiche 93.1 Coerenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.2 Indipendenza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Decidibilita degli assiomi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 Alcuni risultati di logica matematica 13

5 Categoricita e α-categoricita 165.1 Ordini lineari, densi, senza estremi . . . . . . . . . . . . . . . . . . . . . . 19

6 Completezza Semantica e Completezza Sintattica 20

7 Assiomi di Peano - I numeri naturali 227.1 Definizione per induzione. Categoricita degli assiomi di Peano . . . . . . . 257.2 Somma di naturali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277.3 Prodotto di naturali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307.4 Ordinamento dei naturali . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317.5 Altre formulazioni degli Assiomi di Peano . . . . . . . . . . . . . . . . . . . 34

8 Aritmetica al primo ordine. Modelli non-standard 348.1 Linguaggi ridotti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

∗Ringrazio fin d’ora chi vorra segnalarmi errori o inesattezze.

1

2

9 Teorema di Los e Teorema di Compattezza 469.1 Ultrafiltri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469.2 Prodotti diretti e ultraprodotti . . . . . . . . . . . . . . . . . . . . . . . . 48

10 Teorema di Ramsey 5410.1 Prodotti di ultrafiltri e dimostrazione del Teorema di Ramsey infinito . . . 57

A Tautologie 59

B Insiemi 59

1 Prime nozioni sulle Teorie Assiomatiche

Diciamo che una teoria (matematica, o in generale scientifica) viene sviluppata in modoassiomatico quando e costituita da tutte e solo le proposizioni che seguono logicamente(o sono conseguenza logica1) di alcune proposizioni fissate detti assiomi. Le conseguenzelogiche degli assiomi di una teoria vengono chiamate teoremi. Gli Elementi di Euclidecostituiscono l’esempio piu antico e piu noto di teoria assiomatica. Attualmente possiamodire che tutta la matematica viene studiata in modo assiomatico, anche se non vienesempre (anzi, quasi mai) precisato cosa si debba intendere con ‘conseguenza logica’ nequali siano gli assiomi logici (o anche della teoria degli insiemi) che vengono usati assiemeagli assiomi che caratterizzano la teoria stessa.

Consideriamo per esempio la Teoria dei Gruppi. Un gruppo e una terna G = 〈G, ∗, u〉dove G e un insieme non vuoto, ∗ e un’operazione binaria su G, u e un elemento di G, edinoltre sono verificate le seguenti proprieta:

G1. Associativita di ∗: ∀x, y, z [x ∗ (y ∗ z) = (x ∗ y) ∗ z]

G2. Proprieta dell’elemento neutro u: ∀x [x ∗ u = u ∗ x = x]

G3. Esistenza dell’inverso: ∀x∃y [x ∗ y = y ∗ x = u]

Questi sono gli assiomi per la Teoria dei Gruppi, e quindi i teoremi di questa teoria sonole proposizioni che seguono logicamente da questi assiomi. Dire per esempio che in ognigruppo l’elemento neutro e unico, significa dimostrare che, supposto che u e u′ abbianole proprieta espresse da G3, dagli assiomi G1-3 segue logicamente u = u′. Esercizio.

Nei corsi di Analisi ed in tanti altri usiamo i Numeri Reali. Anche in questo caso citroviamo di fronte ad una presentazione di tipo assiomatico. Il punto di partenza e laTeoria dei Campi Ordinati. Ricordiamo che un campo e una struttura K = 〈K,+, ·, 0, 1〉dove K e un insieme, + e · sono operazioni binarie su K, 0 e 1 sono elementi distinti diK, e in cui valgono le seguenti proprieta:

C1. Associativita di + e · : ∀x, y, z [ (x+(y+z) = (x+y)+z) e (x · (y ·z) = (x ·y) ·z) ];

1Qui ‘conseguenza logica’ va inteso in senso intuitivo, non in senso tecnico come per esempio in[Berarducci, 2006].

3

C2. Commutativita di + e · : ∀x, y [ (x+ y = y + x) e (x · y = y · x);

C3. Distributivita di · rispetto a + : ∀x, y, z [x · (y + z) = x · y + x · z];

C4. Proprieta degli elementi neutri : (i) ∀x(x+ 0 = x), (ii) ∀x(x · 1 = x);

C5. Esistenza dell’opposto e del reciproco: (i) ∀x∃y(x+y = 0), (ii) ∀x 6= 0, ∃y(x·y = 1).

I campi ordinati sono strutture K = 〈K,+, ·, 0, 1,≤〉 che verificano gli assiomi C1-5, e sucui e inoltre definita una relazione d’ordine totale ≤ avente quindi le seguenti proprieta:

C6. Riflessivita: ∀x(x ≤ x);

C7. Antisimmetria: ∀x, y (x ≤ y ∧ y ≤ x→ x = y);

C8. Transitivita: ∀x, y, z (x ≤ y ∧ y ≤ z → x ≤ z);

C9. Totalita, o Linearita: ∀x, y (x ≤ y ∨ y ≤ x).

Per la relazione d’ordine in un campo ordinato si richiede infine la compatibilita con leoperazioni di somma e prodotto:

C10. Compatibilita dell’ordine con l’addizione: ∀x, y, z (x ≤ y → x+ z ≤ y + z);

C11. Compatibilita dell’ordine con il prodotto: ∀x, y,∀z ≥ 0 (x ≤ y → x · z ≤ y · z).

Sono esempi di campi ordinati i numeri razionali ed i numeri reali. In quest’ultima strut-tura e pero anche verificato un ulteriore assioma: l’Assioma di Completezza. Un campoordinato K = 〈K,+, ·, 0, 1,≤〉 e completo se

C12. Completezza:

∀X, Y ⊆ K [∀x ∈ X, ∀y ∈ Y (x ≤ y)→ ∃z (∀x ∈ X, ∀y ∈ Y (x ≤ z ≤ y))]

Un risultato cruciale sui Campi Ordinati Completi e che sono tutti isomorfi. Una voltadimostrato quindi che esiste un Campo Ordinato Completo,2 possiamo definire l’insiemeR dei numeri reali come un’arbitraria struttura 〈K,+, ·, 0, 1,≤〉 in cui siano verificati C1-12. In cio e particolarmente evidente la natura assiomatica della teoria dei numeri reali:non interessano le entita che li costituiscono, ma solo il fatto che siano verificati quegliassiomi.

Il passo successivo alla definizione di una struttura algebrica astratta e quello di mostrarestrutture matematiche che rientrano in quella definizione. Tornando ai gruppi, si fa notareper esempio che gli interi, con la somma e lo 0, costituiscono un gruppo, che i razionali

2In genere tale struttura viene definita tramite le classi di equivalenza di successioni di Cau-chy, o tramite i tagli di Dedekind, su Q, v, [Fiori and Invernizzi, 2009], [Cohen and Ehrlich, 1963] o[Zanardo, 2014].

4

non nulli, con il prodotto e l’1, costituiscono un gruppo, e cosı via. Possiamo dire chein queste strutture i simboli ∗ e u che compaiono nella definizione di gruppo, cosı comel’insieme G, vengono interpretati in modo diverso. Questa distinzione tra simbolo esua interpretazione, che spesso non e rilevante nella pratica matematica, gioca inveceun ruolo fondamentale nello studio generale delle teorie assiomatiche. Il primo passo inquesta direzione e la definizione di linguaggio formale alla quale seguira la definizione diinterpretazione.

Osserviamo fin d’ora che, in relazione al linguaggio in cui una teoria assiomatica vieneespressa, c’e una profonda differenza tra la definizione di gruppo, o di campo ordinato, equella di campo ordinato completo. I quantificatori che compaiono in G1-3 o in C1-11possono essere tutti letti come “per ogni elemento di G” o “per ogni elemento di K”,mentre C12 inizia con “per ogni sottoinsieme X e ogni sottoinsieme Y di K”. Nel primocaso abbiamo una quantificazione su elementi, nel secondo una quantificazione su insiemi.I due tipi di quantificazione vengono detti rispettivamente del primo ordine e del secondoordine.3 Inizialmente considereremo solo teorie basate su linguaggi del primo ordine.

1.1 Deduzione Logica

Non e essenziale in queste note dare una definizione rigorosa di deduzione logica, per laquale rimandiamo ai primi capitoli di un qualsiasi manuale di logica matematica. Per gliscopi di questo corso basta sapere che i principi che usiamo abitualmente nelle dimostra-zioni possono essere formalizzati in una definizione rigorosa di dimostrazione. Ricordiamocomunque alcuni aspetti fondamentali delle deduzioni logiche.

DL1 Una deduzione logica (o dimostrazione) in una teoria assiomatica e una succes-sione finita ϕ0, . . . , ϕn di formule in cui ogni ϕi e un assioma della teoria, o seguelogicamente dalle formule precedenti.

DL2 Se le formule ϕ0, . . . , ϕn sono vere in una struttura matematica (in cui quelleformule sono interpretate) e ϕ segue logicamente da ϕ0, . . . , ϕn, allora anche ϕ evera in quella struttura matematica.

DL3 Tutte le tautologie (v. Appendice A) sono dimostrabili in ogni teoria assiomatica.

Le formule che seguono logicamente dagli assiomi di una teoria vengono chiamati teoremi(di quella teoria). Poiche in DL1 non escludiamo che n possa essere 0, gli assiomi risultanoessere particolari teoremi. Da DL1 segue anche in particolare che, anche se una teoriaha infiniti assiomi, ogni dimostrazione ne coinvolge solo un numero finito. Da DL2 segueche, se una struttura matematica verifica gli assiomi di una teoria, anche tutti i teoremirisultano verificati in quella struttura.

3Per rendersi conto della differenza tra quantificazione del primo e del secondo ordine basta pensarealla proprieta della densita che in qualche modo ‘assomiglia’ alla completezza, con la differenza che anzicheinsiemi abbiamo elementi. Sappiamo che tale proprieta deriva dagli assiomi per i campi ordinati, e chein particolare Q e denso. Cio non vale ovviamente per la completezza.

5

Scriveremo T ` ϕ (risp. T 6` ϕ) intendendo che ϕ e, (risp. non e) teorema della teoria T .Converra spesso inoltre identificare una teoria con l’insieme dei suoi assiomi. Scriveremoquindi {ϕ0, . . . , ϕn} ` ϕ intendendo che ϕ e teorema della teoria assiomatica aventeϕ0, . . . , ϕn come assiomi.

2 Linguaggi del primo ordine - Interpretazioni e Mo-

delli

Definizione 2.1 Un linguaggio L del primo ordine e una quaterna 〈C,F,R,V〉 in cuiC, F e R sono insiemi arbitrari, e V e un insieme numerabile (v. Appendice B). Glielementi di C, F e R sono chiamati rispettivamente (simboli per) costanti, funzioni erelazioni. Gli elementi di V sono chiamati variabili individuali, o brevemente variabili.La terna 〈C,F,R〉 viene chiamata segnatura del linguaggio L.

Le variabili di un linguaggio del primo ordine vengono generalmente indicate con x0, x1, . . . ,o con le lettere x, y, z, t, . . . . Gli elementi degli insiemi F e R sono generalmente indicaticon un apice che indica la loro arieta, cioe il numero di argomenti a cui si applicano. Nelseguito cercheremo di evitare il piu possibile questo tipo di notazione, facendo in modoche il contesto determini il numero di argomenti a cui le funzioni e le relazioni si applicano.In un linguaggio per la Teoria dei Gruppi avremo quindi

C = {u} , F = {∗} (= {f 2}) R = ∅

mentre, per la Teoria dei Campi Ordinati,

C = {1, 0} (= {c1, c2}) , F = {+ , ·} (= {f 21 , f

22}) R = {≤} (= {R2

1})

Per non appesantire la notazione e rendere piu comprensibili le formule, useremo spesso isimboli relativi alla struttura matematica che interpreta il linguaggio al posto dei simbolidel linguaggio stesso. Per questo motivo nell’esempio precedente abbiamo scritto C ={1, 0}, F = {+ , ·} e R = {≤}.Per dare una definizione rigorosa di formula (di un linguaggio del primo ordine) dob-biamo preliminarmente definire i termini. Essi sono le entita che, in una data strutturamatematica, vengono interpretati negli elementi di struttura. Abbiamo quindi, per ognilinguaggio L = 〈C,F,R,V〉, l’insieme TL dei suoi termini e il piu piccolo insieme tale che

C ∪ V ⊆ TL e t1, . . . , tn ∈ TL e fn ∈ F ⇒ fn(t1, . . . , tn) ∈ TL (2.1)

Esercizio 2.2 Sia N = 〈N, 0, σ〉 la struttura dei numeri naturali, dove σ e la funzionesuccessore. Descrivere l’insieme TL, dove L e un linguaggio adeguato per la struttura N .

L’insieme delle formule di L viene definito in modo analogo:

• se t e t′ sono termini, allora t = t′ e una formula;

6

• se t1, . . . , tn sono termini e Rn ∈ R, allora Rn(t1, . . . , tn) e una formula;

• se ϕ e ψ sono formule e x e una variabile, allora¬ϕ, ϕ ∨ ψ, ϕ ∧ ψ, ϕ→ ψ, ϕ↔ ψ, ∀xϕ, e ∃xϕ, sono formule.

Se ϕ e una formula e ∀xψ o ∃xψ e una sua sottoformula, allora diremo che ogni occorrenzadella variabile x in ψ e vincolata in ϕ. Le occorrenze di una variabile che non sonovincolate in una data formula sono dette libere. Osserviamo che in una formula la stessavariabile puo avere sia occorrenze libere sia occorrenze vincolate. Per esempio, nellaformula x ≤ 0 ∧ ∀x(y ≤ x) la prima occorrenza della x e libera e la seconda vincolata(mentre l’unica occorrenza della y, supposta diversa da x, e libera). Un enunciato euna formula che non ha variabili libere. Scriveremo spesso ϕ(x1, . . . , xn) per mettere inevidenza che nella formula ϕ le variabili x1, . . . , xn sono libere o, piu in generale, che levariabili libere di ϕ appartengono all’insieme {x1, . . . , xn}.Anche se non abbiamo ancora dato una definizione rigorosa di verita di una formula, none difficile rendersi conto che in generale una formula con variabili libere puo essere verao falsa a seconda del valore assegnato alle variabili che compaiono libere nella formulastessa: x > 0, interpretata nell’insieme dei numeri reali, e vera per alcuni valori di x efalsa per altri4. Cio non succede se una variabile e invece vincolata: ∃x(x > 0) e veranell’insieme dei numeri reali, indipendentemente dal valore di x, e infatti e equivalente a∃y(y > 0). Cio e perfettamente analogo al fatto che

∫ baf(x) dx dipende solo da a e b (e

coincide con∫ baf(t) dt), mentre

∫ zaf(x) dx dipende dal valore di z.

Prima di dare la definizione di interpretazione, ricordiamo che, dati gli insiemi A e B, conAB indichiamo l’insieme delle funzioni da A in B, e che una relazione n-aria su A e uninsieme di n-uple ad elementi in A, cioe un sottoinsieme del prodotto cartesiano An.

Definizione 2.3 Una interpretazione del linguaggio L = 〈C,F,R,V〉 e una coppia I =〈D, I〉, dove D e un insieme non vuoto, e I e una funzione definita su C∪F∪R tale che:

c ∈ C⇒ I(c) ∈ D fn ∈ F⇒ I(fn) ∈ (Dn)D Rn ∈ R⇒ I(Rn) ⊆ Dn (2.2)

Indicheremo talvolta I(c), I(fn) e I(Rn) rispettivamente con cI, fnI e Rn

I.

Un’interpretazione di L individua dunque un insieme D, il dominio5 dell’interpretazione,e: 1) ad ogni elemento di C associa un elemento di D, 2) ad ogni simbolo per funzionen-aria in F associa una funzione da Dn in D, e 3) ad ogni simbolo per relazione n-ariain R associa una relazione ad n argomenti in D. Osserviamo infine che la nozione diinterpretazione non coinvolge l’insieme V delle variabili in L, ma solo la segnatura.

4Abbiamo detto che questo discorso vale ‘in generale’ perche, per esempio, la verita della formulax = x non dipende dal valore della variabile libera x.

5In matematica si confonde spesso il dominio di un’interpretazione con l’interpretazione stessa. Siparla per esempio dell’insieme dei naturali intendendo la struttura che oltre all’insieme include le usualioperazioni e relazioni sui naturali. Non c’e niente di male in questo modo di fare che, anzi, rende ildiscorso piu snello. Se tuttavia vogliamo fare una teoria delle interpretazioni (Teoria dei Modelli) risultaspesso opportuno distinguere il dominio dall’interpretazione.

7

La cardinalita di un’interpretazione I = 〈D, I〉 viene definita come la cardinalita dell’in-sieme D. Diremo per esempio che I e numerabile se card(D) = card(N).

Nella sezione precedente abbiamo visto alcuni esempi di interpretazioni della segnaturaper la teoria dei gruppi: 〈{u}, {∗}, ∅〉. Con la notazione appena introdotta possiamodire per esempio che un’interpretazione di questa segnatura e la coppia Z = 〈Z, I〉, doveuZ = I(u) e ∗Z = I(∗) sono rispettivamente lo 0 e l’usuale somma negli interi.

Esercizio 2.4 Definire un linguaggio per gli anelli ordinati e l’interpretazione di quellinguaggio nella struttura degli interi.

Osservazione 2.5 Consideriamo ancora la segnatura 〈{u} , {∗} , ∅〉 per i gruppi e la cop-pia I = 〈M, I〉, dove M e l’insieme delle matrici 2×2, uI e la matrice identica in M , e ∗I eil prodotto righe per colonne in M . L’insieme delle matrici 2×2 con l’usuale prodotto none un gruppo, tuttavia la coppia 〈M, I〉 e una interpretazione del linguaggio per la teoriadei gruppi. Una struttura matematica e una interpretazione di un linguaggio quando leformule del linguaggio risultano vere o false in quella struttura. Non viene richiesto chei teoremi della teoria descritta da quel linguaggio risultino verificati. Per tale situazioneintroduciamo la nozione di modello, che richiede la nozione di ‘verita’ di una formula inuna interpretazione.

Abbiamo gia osservato che la verita di una formula con variabili libere dipende in generaledal valore assegnato a tali variabili. Per una definizione rigorosa di verita abbiamo dunquebisogno di un’ulteriore nozione.

Definizione 2.6 Data l’interpretazione I = 〈D, I〉 del linguaggio L = 〈C,F,R,V〉, unavalutazione (delle variabili di L in I) e una funzione V da V in D. Data una valutazioneV, una variabile v, ed un elemento a di D, indicheremo con V(v/a) la valutazione V ′ checoincide con V su tutte le variabili diverse da v e tale che V ′(v) = a.

Ogni valutazione V puo essere estesa induttivamente all’insieme di tutti i termini ponendo,per ogni costante c, termini t1, . . . , tn, e simbolo per funzione fn,

V(c) = cI e V(fn(t1, . . . , tn)) = fnI (V(t1), . . . ,V(tn)) (2.3)

Scriveremo spesso tV invece di V(t).

Useremo l’espressione I,V |= ϕ intendendo che la formula ϕ e vera nell’interpretazioneI = 〈D, I〉 con una data valutazione V . La relazione |= e definita dalle seguenti regole diverita, per induzione sulla costruzione di ϕ.

8

Regole di verita (per formule del primo ordine)

R0 I,V |= t1 = t2 sse tV1 = tV2

R1 I,V |= Rn(t1, . . . , tn) sse 〈tV1 , . . . , tVn〉 ∈ RnI

R2 I,V |= ¬ψ sse I,V 6|= ψ

R3 I,V |= ψ ∧ χ sse I,V |= ψ e I,V |= χ

R4 I,V |= ψ ∨ χ sse I,V |= ψ o I,V |= χ

R5 I,V |= ψ → χ sse I,V |= ¬ψ o I,V |= χ

R6 I,V |= ψ ↔ χ sse I,V |= ψ → χ e I,V |= χ→ ψ

R7 I,V |= ∀v ψ sse per ogni a ∈ D, I,V(v/a) |= ψ

R8 I,V |= ∃v ψ sse esiste a ∈ D : I,V(v/a) |= ψ

Da queste regole segue che, per ogni I e V , I,V |= ϕ ∨ ψ se e solo se I,V |= ¬(¬ϕ ∧ ¬ψ)

e dunque l’operatore ∨ puo essere definito per mezzo di ∧ e ¬ : ϕ∨ψ def≡ ¬(¬ϕ∧¬ψ). Inmodo analogo abbiamo

ϕ→ ψdef≡ ¬ϕ ∨ ψ ϕ↔ ψ

def≡ (ϕ→ ψ) ∧ (ψ → ϕ) ∃v ϕ def≡ ¬∀v¬ϕ

Quindi possiamo considerare un linguaggio con i soli operatori ¬, ∧, ∀ e considerare glialtri come operatori definiti6.

Questa riduzione del linguaggio torna in genere utile nelle dimostrazioni per induzionesulla complessita di una formula. Se vogliamo dimostrare che tutte le formule di un datolinguaggio hanno una data proprieta P , possiamo dimostrare come passo iniziale che Pvale per formule del tipo t1 = t2 o R(t1, . . . , tn) (formule atomiche), e poi (passo induttivo)dimostrare che, se ϕ e ψ hanno P allora lo stesso vale per ¬ϕ1, ϕ ∧ ψ, e ∃vϕ.

Usiamo questa tecnica di dimostrazione per formalizzare il discorso fatto sopra sulladipendenza della verita di una formula dall’interpretazione delle variabili.

Proposizione 2.7 Se la variabile x non compare libera in ϕ allora la verita di ϕ nell’in-terpretazione I con valutazione V non dipende da V(x).

Dimostrazione. Dimostriamo la proposizione per induzione della formula ϕ. Se ha laforma t1 = t2 o Rn(t1, . . . , tn), dire che x non compare libera equivale a dire che x noncompare, e dunque il risultato e banalmente vero. Supponiamo ora che l’enunciato siavero per ogni sottoformula (propria) di ϕ.

Se ϕ e della forma ¬ψ o ψ ∧ χ, abbiamo la proposizione applicando l’ipotesi induttiva.

Se ϕ e ∀vψ dobbiamo distinguere i casi in cui v e x oppure no. Nel primo caso la verita diϕ viene determinata dalle valutazioni della forma V(x/a) (a ∈ D) e quindi non dipendedal valore V(x). Nel secondo caso abbiamo che x non e libera in ψ, e quindi si arriva allaconclusione usando l’ipotesi induttiva.

6Sono possibili altre scelte degli operatori non definiti, per esempio ¬, ∨, ∃, o ¬, →, ∃, ecc.

9

Diciamo che la formula ϕ e vera (risp. falsa) in una interpretazione I se, se per ognivalutazione V , I,V |= ϕ (risp. I,V |= ¬ϕ), e in tal caso scriviamo I |= ϕ (risp. I |= ¬ϕ).Si osservi che una formula ϕ che non e vera in una interpretazione I, non e necessariamentefalsa in quella interpretazione: puo succedere che per qualche valutazione V , I,V |= ϕ eche per qualche altra valutazione V ′, I,V ′ |= ¬ϕ. Se pero ϕ e un enunciato, allora la suaverita in I non dipende dalla scelta della valutazione V (Proposizione 2.7), e quindi ϕrisulta vera oppure falsa in I. Se esiste una valutazione V tale che I,V |= ϕ, diciamo cheϕ e soddisfacibile in I. Diciamo che ϕ e soddisfacibile se lo e in qualche interpretazione.

Esercizio 2.8 Sia ϕ(x1, . . . , xn) una formula con le variabili libere nell’insieme {x1, . . . ,xn}. Dimostrare che ϕ(x1, . . . , xn) e vera in I se e solo se ∀x1, . . . , xn ϕ(x1, . . . , xn) e verain I.

Definizione 2.9 Diciamo che una interpretazione M e un modello della teoria assio-matica T se ogni assioma di T e vero in M.

Per la proprieta DL2 delle deduzioni logiche abbiamo quindi che tutti i teoremi di T sonoveri in ogni modello di T .

Esempio 2.10 L’interpretazione di 〈{u} , {∗} , ∅〉 considerata nell’Osservazione 2.5 none un modello della Teoria dei Gruppi. Essa diventa pero un modello se ∗I e la somma tramatrici 2× 2.

Osservazione 2.11 Abbiamo osservato che un enunciato risulta vero oppure falso in unadata interpretazione. Se invece la formula ϕ(x) contiene la variabile x libera, in generalela verita di questa formula dipende dalla particolare valutazione V(x) di x nel dominio del-l’interpretazione. Per esempio, se consideriamo l’interpretazione I dell’Osservazione 2.5,la formula ∀x∃y(x ∗ y = u), che e un enunciato, e falsa, mentre la formula ∃y(x ∗ y = u)risulta vera se V(x) e una matrice invertibile, falsa negli altri casi. Una formula ϕ(x) conx unica libera, identifica quindi un sottoinsieme Xϕ(x) del dominio D dell’interpretazione:Xϕ(x) = {a ∈ D : I,V(x/a) |= ϕ(x)} (si osservi che essendo x l’unica variabile libera inϕ, l’insieme Xϕ(x) non dipende da V). In questo caso si dice che Xϕ(x) e l’insieme definitodalla formula ϕ(x) (v. anche §8). In modo analogo, le formule del tipo ϕ(x1, . . . , xn)definiscono sottoinsiemi di Dn.

3 Prime proprieta delle Teorie Assiomatiche

3.1 Coerenza

Un requisito minimo che una teoria assiomatica T deve soddisfare perche abbia sensostudiarla, e quello della coerenza o non contraddittorieta. Vogliamo cioe che la teoria nonpermetta di dedurre una proposizione e al tempo stesso la sua negazione.

10

Definizione 3.1 La teoria T e coerente, o consistente, se non esiste nessuna formula ϕtale che T ` ϕ e T ` ¬ϕ.

Poiche una teoria dimostra due formule ϕ e ψ se e solo se ne dimostra la congiunzioneϕ ∧ ψ, e le formule del tipo ϕ ∧ ¬ϕ vengono chiamate contraddizioni, possiamo dire cheT e coerente se e solo se non dimostra contraddizioni. Verranno chiamate contraddittoriele teorie non coerenti.

Il motivo per cui si richiede che una teoria sia coerente e ovvio: se T dimostra unacontraddizione, allora T non ha modello. Dalle Regole di Verita segue infatti che, perogni interpretazione I e ogni valutazione V , I,V 6|= ϕ∧¬ϕ. Non esiste nessuna strutturamatematica della quale T descriva le proprieta. Oltre a questo, abbiamo che una teorianon coerente dimostra ogni proposizione. Infatti, l’implicazione (ϕ ∧ ¬ϕ) → ψ e unatautologia per ogni scelta delle formule ϕ e ψ, e quindi, se T ` ϕ∧¬ϕ, allora, per ModusPonens, T ` ψ. Non c’e alcun interesse nello studiare teorie in cui tutto e dimostrabile.

Avendo deciso di identificare una teoria con l’insieme dei suoi assiomi, possiamo ancheparlare di coerenza di un insieme {ϕ0, . . . , ϕn} di formule. Tale insieme sara dunquecoerente se e tale la teoria assiomatica che ha quelle formule come assiomi, ossia se esisteuna formula ϕ tale che {ϕ0, . . . , ϕn} 6` ϕ. La seguente proposizione permette di estendereinsiemi coerenti di formule e verra usata in seguito.

Esercizio 3.2 Siano Φ e Ψ insiemi coerenti di formule. Cosa possiamo dire riguardoalla coerenza di Φ ∩Ψ e Φ ∪Ψ?

Proposizione 3.3 Dato un insieme Φ di formule e la formula ϕ, l’insieme Φ ∪ {¬ϕ} ecoerente se e solo se Φ 6` ϕ.

Dimostrazione. Supponiamo Φ ` ϕ. Allora dalla proprieta DL1 (§1.1) segue Φ∪{¬ϕ} ` ϕe Φ ∪ {¬ϕ} ` ¬ϕ. Quindi Φ ∪ {¬ϕ} non e coerente.

Supponiamo inversamente che Φ ∪ {¬ϕ} non sia coerente e consideriamo una formula ψtale che Φ ∪ {¬ϕ} ` ψ ∧ ¬ψ. Per un risultato di logica (Teorema di Deduzione) abbiamoche Φ ` ¬ϕ→ (ψ ∧ ¬ψ), ma (¬ϕ→ (ψ ∧ ¬ψ))→ ϕ e una tautologia e quindi Φ ` ϕ.

Teorema 3.4 (T. di Compattezza Sintattica). Un insieme di formule e coerente see solo se ogni suo sottoinsieme finito e coerente.

Dimostrazione. Per DL1 ogni dimostrazione in una teoria assiomatica coinvolge un nu-mero finito di assiomi e quindi, se possiamo dedurre ϕ∧¬ϕ da un dato insieme di formule,possiamo dedurre la stessa contraddizione anche da un suo sottoinsieme finito.

L’affermazione che una data teoria T e coerente coinvolge implicitamente tutte le (infinite)possibili deduzioni logiche basate sugli assiomi di T , nel senso che si afferma che nessunadi queste deduzioni si conclude con una contraddizione. Considerare tutte le possibilideduzioni in una data teoria e nella maggioranza dei casi molto difficile, ma per dimostrareche una teoria assiomatica e coerente possiamo usare anche altre tecniche. La piu usata

11

e mostrare che la teoria in esame ha un modello. Abbiamo gia osservato infatti (DL2,§1.1) che se gli assiomi di una teoria T sono verificati in una interpretazione, allora in taleinterpretazione sono verificati anche tutti i teoremi di T . Basta dunque ricordare che perle Regole di Verita in una interpretazione non possono essere contemporaneamente vereuna formula e la sua negazione. Da questo segue che se gli assiomi di una teoria sonoverificati in una struttura, allora tale teoria non puo dimostrare una contraddizione, cioee coerente.

Osservazione 3.5 Per il Teorema 3.4, per dimostrare che una teoria assiomatica T coninfiniti assiomi e coerente e sufficiente dimostrare che ogni insieme finito dei suoi assiomie coerente. Puo succedere in particolare che vengano esibiti vari modelli per i vari insiemifiniti di assiomi, ma che ciascuno di questi modelli non sia modello di tutta la teoria. Nel§8 vedremo un esempio di questa situazione.

Osservazione 3.6 Abbiamo visto che per dimostrare la coerenza di una teoria possiamodimostrare che tale teoria ha un modello. La dimostrazione rigorosa dell’esistenza di talemodello deve avvenire internamente alla Teoria Assiomatica degli Insiemi e quindi sorgeinevitabilmente il problema della coerenza di questa teoria. Questo e un problema moltodelicato e per esporre quanto e attualmente noto al riguardo sarebbero necessarie nozionie risultati molto sofisticati di logica matematica e teoria degli insiemi. Ci limitiamo aricordare il risultato principale, cioe che non e possibile dare una dimostrazione dellacoerenza di questa teoria internamente alla teoria stessa. Per il Teorema di Incompletezzadi Godel, infatti, se la teoria degli insiemi fosse in grado di dimostrare la propria coerenza(per esempio dimostrando l’esistenza di un suo modello), allora sarebbe contraddittoria!Se poi teniamo presente che la teoria degli insiemi viene posta alla base della matematica,il Teorema di Incompletezza di Godel implica che la coerenza della teoria degli insieminon e dimostrabile.

Nella pratica matematica, la non contradditorieta della teoria degli insiemi viene presup-posta, basandosi essenzialmente sull’evidenza intuitiva dei suoi assiomi, anche se nonpossiamo escludere che prima o dopo venga trovata una contraddizione.

3.2 Indipendenza

Definizione 3.7 Sia Φ un insieme di formule. Diciamo che ϕ ∈ Φ e dipendente (risp.indipendente) in Φ se e (risp. non e) deducibile da Φ \ {ϕ}. Diciamo che Φ e dipendente(risp. indipendente) se esiste (risp. non esiste) una sua formula dipendente.

Gli assiomi di una teoria assiomatica sono indipendenti se nessuno di essi puo esserededotto dagli altri. Anche in questo caso, come per la coerenza, stiamo considerandouna proprieta che coinvolge tutte le possibili deduzioni in una data teoria: l’assioma ϕ

della teoria T e indipendente se, detta T ′ la teoria ottenuta togliendo l’assioma ϕ da T ,nessuna deduzione in T ′ si conclude con ϕ.

Analogamente a quanto si e visto per la coerenza, la proprieta DL2 delle deduzioni logichefornisce una tecnica piu semplice per dimostrare che ϕ e indipendente. Se ϕ fosse teorema

12

di T ′ (cioe dipendente) allora ϕ dovrebbe essere vero in ogni modello di T ′. Per dimostrarel’indipendenza di ϕ basta quindi trovare un’interpretazione in cui siano verificati tutti gliassiomi di T ad eccezione di ϕ. L’indipendenza del quinto postulato di Euclide e statadimostrata in questo modo. Per dimostrare che l’Assioma di Completezza C12 per i realinon e conseguenza degli altri, basta osservare che i razionali verificano gli assiomi deicampi ordinati, ma non l’Assioma di Completezza.

Supponiamo che gli assiomi di una teoria T siano ϕ0, . . . , ϕn e che ϕ0 sia dipendente.Cio significa che ϕ0 e dimostrabile nella teoria T ′ avente ϕ1, . . . , ϕn come assiomi. Non edifficile rendersi conto che, se trascuriamo l’indipendenza, le teorie T e T ′ hanno le stesseproprieta, hanno cioe gli stessi teoremi e gli stessi modelli. In effetti, le proprieta di unateoria dipendono da cio che e dimostrabile, cioe dai teoremi, piu che dalla scelta degliassiomi.

In base a questa osservazione sembra quindi che questioni legate all’indipendenza degliassiomi siano sostanzialmente questioni di eleganza formale. Come insegnano le Geometrienon Euclidee, pero, c’e qualcosa di piu. Supponiamo che gli assiomi ϕ0, . . . , ϕn dellateoria T siano indipendenti; da cio segue in particolare che {ϕ1, . . . , ϕn} 6` ϕ0. Per laProposizione 3.3 la teoria T ∗ avente per assiomi ϕ1, . . . , ϕn e ¬ϕ0 e coerente, per cuidiventa interessante vedere quali siano i teoremi di T ∗ e soprattutto vedere come sonofatti, se ce ne sono, i suoi modelli. Lo studio delle geometrie non Euclidee e appunto lostudio delle strutture in cui e verificata la negazione del quinto postulato.

3.3 Decidibilita degli assiomi

Un altro requisito elementare che le teorie assiomatiche devono soddisfare e che l’insiemedegli assiomi sia decidibile. Intuitivamente cio significa che deve esistere una proceduraeffettiva, un algoritmo, un programma di un computer7, che ci permetta di decidere seuna data formula sia un assioma della teoria oppure no. Il senso di questo requisito e cheuna teoria assiomatica non deve lasciare alcun dubbio sul fatto che una data successionedi passaggi sia una dimostrazione e, affinche questo succeda, deve essere ben determinatol’insieme degli assiomi che possono essere usati nelle dimostrazioni.

Le teorie assiomatiche che incontriamo in matematica sono generalmente presentate elen-candone gli assiomi, se questi sono in numero finito, oppure elencando degli ‘schemi d’as-siomi’, cioe dicendo che tutte le formule aventi una data struttura sono assiomi dellateoria. In questi casi la procedura effettiva per determinare se una data formula sia unassioma consiste semplicemente nel controllare se tale formula compaia in un dato elencoo abbia una data forma.

Ci sono molti modi tuttavia per definire un insieme (di formule, nel nostro caso) e nontutti gli insiemi possono essere descritti elencandone in qualche modo gli elementi. Diventaquindi sensato chiederci se un qualsiasi insieme coerente di formule, comunque definito,possa essere visto come l’insieme degli assiomi di una teoria assiomatica. Un esempio

7Possiamo trovare una definizione rigorosa di ‘procedura effettiva’ in Teoria della Ricorsivita nellanozione di funzione ricorsiva.

13

semplice di insieme di formule che non puo essere considerato l’insieme degli assiomi di unateoria assiomatica, e l’insieme di tutte le formule scritte con i simboli 0, 1, +, ×, = (oltreai simboli logici) vere nella struttura dei numeri naturali8 Il teorema di Incompletezza diGodel ci dice che non esiste una procedura effettiva per decidere se una data formula inquell’insieme sia vera oppure falsa nella struttura dei numeri naturali.

4 Alcuni risultati di logica matematica

In questa sezione enunceremo, senza darne sempre una dimostrazione dettagliata, al-cuni risultati fondamentali di logica matematica relativi alle teorie del primo ordine.Le dimostrazioni si trovano in qualsiasi manuale di logica matematica, per esempio:[Bell and Machover, 1977] o [Mendelson, 1981].

Gli assiomi e le regole della logica del primo ordine, comuni a tutte le teorie del primoordine, possono essere visti in ogni manuale di Logica Matematica. Essi includono gliassiomi e le regole del Calcolo Proposizionale visto in Appendice A, e quindi anche nelcaso delle teorie del primo ordine possiamo parlare di tautologie e contraddizioni.

Teorema 4.1 Ogni insieme coerente Φ di formule del primo ordine ha un modello.

Dimostrazione. (Cenni sulle linee essenziali) La costruzione di un modello 〈D, I〉 di Φsi sviluppa secondo le linee seguenti. Conviene tenere presente che abbiamo a disposi-zione solo un insieme di formule, e quindi sia D sia I verranno costruiti partendo daquell’insieme.

1. Bisogna innanzitutto estendere Φ ad un insieme coerente Φ∗ con le seguenti pro-prieta:

1) se ∃xϕ(x) ∈ Φ∗, allora esiste una costante c tale che ϕ(c) ∈ Φ∗, e

2) per ogni formula ϕ, ϕ ∈ Φ∗ oppure ¬ϕ ∈ Φ∗.

Teoremi di logica garantiscono che Φ∗ esiste (Lemma di Lindenbaum). In generaleil linguaggio L∗ di Φ∗ risulta esssere un’estensione (generalmente propria) di quellodi Φ, ottenuta aggiungendo nuove costanti.

2. Le entita del linguaggio che rappresentano gli elementi di D sono le costanti e quindi,per costruire D, si partira proprio dall’insieme delle costanti di L∗. Questo spiegala richiesta 1) al punto precedente: se abbiamo una formula esistenziale, dobbiamoavere anche una costante che rappresenta l’elemento di cui viene asserita l’esistenza.Sull’insieme delle costantti definiamo una relazione di equivalenza: c ≡ c′ se e solose c = c′ ∈ Φ∗. Il dominio D viene definito come l’insieme delle classi di equivalenza[c]≡, con c costante di L∗.

3. Osserviamo che la cardinalita di D e minore o uguale alla cardinalita dell’insiemedelle costanti di L∗.

8Si osservi che queste formule, essendo verificate in una data struttura matematica, costituiscono uninsieme coerente.

14

4. Per ogni costante c di L∗ poniamo I(c) = [c]≡.

5. Per ogni simbolo per funzione n-aria f di L∗ (che e anche in L) definiamo I(f)tramite I(f)([c1]≡ . . . [cn]≡) = [c]≡, dove f(c1, . . . , cn) = c ∈ Φ∗. Dalle proprieta diΦ∗ segue che un tale c esiste sempre, e dagli assiomi per l’uguaglianza segue cheI(f) e ben definita.

6. Per ogni simbolo per relazione n-aria R in Φ∗ poniamo I(R) = {〈[c1]≡ . . . [cn]≡)〉 ∈Dn : R(c1, . . . , cn) ∈ Φ∗}. Anche in questo caso gli assiomi per l’uguaglianzagarantiscono che I(R) e ben definita.

In questo modo si conclude la definizione dell’interpretazione. Il passo successivo e quellodi dimostrare che, ogni enunciato ϕ di L∗ e vero in 〈D, I〉 se e solo se ϕ ∈ Φ∗. Ladimostrazione e ovviamente per induzione sulla complessita di ϕ. Nel caso ϕ sia c = c′ oR(c1, . . . , cn) il risultato segue dalla definizione di I. Il discorso e semplice anche quandoϕ e ¬ϕ1 o ϕ1 ∧ ϕ2. In questi casi si usa il fatto che Φ∗ e massimale e coerente.

Piu insidioso e il caso in cui ϕ e ∃xϕ1 o ∀xϕ1 (a seconda di quale operatore riteniamoprimitivo e quale definito). Il problema e che in generale ϕ1 non e un enunciato. Bisognaquindi riprendere la dimostrazione dall’inizio, considerando anche le valutazioni delle va-riabili, e partendo da formule del tipo t = t′ o R(t1, . . . , tn) in cui i termini t, t′, t1, . . . , tnpossono contenere variabili.

Teorema 4.2 (T. di Compattezza Semantica) Un insieme di formule del primoordine ha modello se e solo se ogni suo sottoinsieme finito ha modello.

Dimostrazione. Segue immediatamente dai Teoremi 3.4 e 4.1.

Nel Teorema 9.22 verra data una dimostrazione puramente semantica di questo teorema,senza usare cioe il Teorema 4.1.

Corollario 4.3 Se un insieme Φ di enunciati del primo ordine ha modelli finiti di cardi-nalita9 arbitrariamente grande, allora ha anche un modello infinito.

Dimostrazione. Poniamo

En = ∃x1, . . . , xn

( ∧1≤i<j≤n

xi 6= xj

)e Φ∗ = Φ ∪ {En : n ∈ N e n ≥ 2} (4.4)

dove il simbolo∧

indica la congiunzione (∧) delle formule che lo seguono al variare degliindici i e j. L’espressione xi 6= xj e un’abbreviazione di ¬(xi = xj). La formula En e verain una interpretazione 〈D, I〉 se e solo D ha almeno n elementi.

Dato un qualsiasi sottoinsieme finito Φ0 di Φ∗, sia n0 il massimo indice tale che En0 ∈ Φ0.Dalle ipotesi sui modelli di Φ abbiamo che esiste un suo modello M0 con almeno n0

9La cardinalita verra definita nella seconda parte del corso. In questo caso, cioe per insiemi finiti,possiamo identificare la cardinalita di un insieme con il numero dei suoi elementi.

15

elementi e tale interpretazione e anche modello di Φ0. Ogni enunciato di Φ0 che appartienea Φ e banalmente vero inM0, cosı come tutte le formule della forma En, per la suppostamassimalita di n0.

Poiche Φ0 e un arbitrario sottoinsieme finito di Φ∗, per il Teorema di Compattezza Se-mantica possiamo concludere che Φ∗ ha modello M, che e anche modello di Φ percheΦ ⊆ Φ∗. Ma dalla definizione di Φ∗, segue che M deve essere infinito.

Corollario 4.4 Non esiste nessun insieme di enunciati del primo ordine che risultanoveri in tutte e solo le interpretazioni finite.

Dimostrazione. Se tutte le interpretazioni finite sono modelli di un insieme Φ di enunciatidel primo ordine, allora Φ ha modelli finiti di cardinalita arbitrariamente grande, e quindi,per il corollario precedente, ha anche un modello infinito.

Esercizio 4.5 Sia L un linguaggio del primo ordine senza (simboli per) costanti e fun-zioni con un’unica relazione binaria <. Si dimostri che non esistono enunciati ϕ di Lche risultano veri in un’interpretazione I se e solo se l’interpretazione <I di < e un buonordine (v. Definizione 7.25)

Suggerimento. Consideriamo una estensione L∗ di L ottenuta aggiungendo infinite co-stanti c0, c1, . . . indicizzate sull’insieme dei naturali. Sia Φ = {ϕ} ∪ {cn < cm : m < n}.Dimostriamo che ogni sottoinsieme finito di Φ ha modello, e quindi Φ ha modello.

Per enunciare il seguente teorema dobbiamo precisare che la cardinalita di un linguaggioL = 〈C,F,R,V〉 intendiamo la cardinalita dell’insieme C∪ F∪R∪V. Scrivendo card(L)intenderemo quindi card(C∪F∪R∪V). Si osservi che in ogni linguaggio l’insieme V dellevariabili e numerabile, in generale avremo quindi card(L) ≥ card(N). Se in particolare,come succede spesso in matematica, gli insiemi C, F, e R sono finiti o numerabili, alloraanche il linguaggio e numerabile.

Teorema 4.6 (T. di Lowenheim-Skolem). Se un insieme Φ di enunciati del primoordine ha un modello infinito, allora tale insieme ha modelli di qualsiasi cardinalita infinitaα maggiore o uguale alla cardinalita del linguaggio di Φ.10

Dimostrazione. Una possibile dimostrazione e un uso tipico del teorema di Compattez-za Semantica11. Dimostreremo il teorema nella forma della Nota 10, in modo di noncoinvolgere la nozione assoluta di cardinalita.

Sia X un insieme tale che card(L) ≤ card(X) e consideriamo il linguaggio L∗ ottenutoaggiungendo a L un insieme di nuove costanti indicizzate su X: {cx : x ∈ X}. Poichecard(L) ≤ card(X) per la Proposizione B.4, abbiamo card(L∗) = card(X). Sia Φ∗ = Φ∪C

10In assenza di una nozione assoluta di cardinalita (Card), possiamo riformulare l’enunciato di questoteorema nel modo seguente: Se un insieme Φ di enunciati del primo ordine ha un modello infinito, allora,per ogni insieme infinito X tale che card(L) ≤ card(X), Φ ha un modelloM tale che card(M) = card(X).

11Ci sono altre dimostrazioni che usano solo tecniche di Teoria dei Modelli, v. [Berarducci, 2006].

16

dove C = {cx 6= cy : x, y ∈ X e x 6= y}. Se M = 〈D, I〉 e un modello infinito di Φ, allora,M puo anche essere visto come modello di Φ ∪ C0 per ogni sottoinsieme finito C0 diC: basta interpretare le costanti che compaiono in C0 su elementi diversi di D. Cio esempre possibile perche D e infinito e le costanti che compaiono in C0 sono in numerofinito. Abbiamo dunque che ogni sottoinsieme finito di Φ∗ ha modello e quindi, per ilTeorema 4.2, anche Φ∗ ha un modello M∗ che sara anche modello di Φ.

Poiche in M∗ sono verificate anche tutte le disuguaglianze in C, vale la disuguaglianzacard(X) ≤ card(M∗). Ma, per il punto 3 della dimostrazione del Teorema 4.1, abbiamoche possiamo scegliere il modello di M∗ in modo che card(M∗) ≤ card(X).

Esercizio 4.7 Sia L il linguaggio per la teoria degli anelli. Si dimostri che non esistenessuna teoria assiomatica T del primo ordine nel linguaggio L avente tutti i modelliisomorfi a Z.

5 Categoricita e α-categoricita

Definizione 5.1 Date due interpretazioni I = 〈D, I〉 e I ′ = 〈D′, I ′〉 della segnatura〈C,F,R〉, diciamo che la funzione η : D → D′ e un isomorfismo tra I e I ′ se

a. η e una corrispondenza biunivoca tra D e D′;

b. per ogni c ∈ C, η(cI) = cI′;

c. per ogni fn ∈ F e ogni 〈d1, . . . , dn〉 ∈ Dn, η(fnI (d1, . . . , dn) = fnI′(η(d1), . . . , η(dn));

d. per ogni Rn ∈ R e ogni 〈d1, . . . , dn〉 ∈ Dn, 〈d1, . . . , dn〉 ∈ RnI ⇔ 〈η(d1), . . . , η(dn)〉 ∈

RnI′.

Le interpretazioni I e I ′ sono dette isomorfe (in simboli I ∼= I ′) se esiste un isomorfismotra I e I ′.

Questa e l’usuale definizione di isomorfismo tra strutture matematiche: una funzionebiunivoca che conserva le costanti, le operazioni e le relazioni. Il motivo per cui vengonocoinvolte le segnature e che una data funzione puo essere o non essere un isomorfismoa seconda dalle relazioni e funzioni che vengono considerate, cioe, nella terminologia diqueste dispense, a seconda della segnatura. Per esempio, i naturali e i naturali pari sonoisomorfi se vengono considerate strutture dotate con le usuali somma e relazione d’ordine;non lo sono se consideriamo anche la moltiplicazione (Esercizio).

Proposizione 5.2 Siano I = 〈D, I〉 e I ′ = 〈D′, I ′〉 sono due interpretazioni isomorfe conisomorfismo η. Data una qualsiasi valutazione V su I indichiamo con V ′ la valutazionedefinita da V ′(v) = η(V(v)) per ogni variabile v. Allora, per ogni formula ϕ della segnaturaper I e I ′, (∗) I,V |= ϕ ⇔ I ′,V ′ |= ϕ.

17

Dimostrazione. La dimostrazione e ovviamente per induzione sulla complessita di ϕ,osservando preliminarmente che, per ogni termine t, dalla clausola c. nella Definizione 5.1segue che η(V(t)) = V ′(t). Da cio segue l’equivalenza (∗) quando ϕ e t1 = t2. Se ϕ eR(t1, . . . , tn) allora usiamo la clausola d. nella definizione di isomorfismo.

Supponiamo induttivamente che (∗) valga per ψ e χ, e per ogni valutazione V . I casi incui ϕ e ¬ψ o ψ ∧χ seguono immediatamente dall’ipotesi induttiva e dalle regole di veritaper ¬ e ∧.

Se ϕ e ∀v ψ, abbiamo: I,V |= ϕ ⇔ per ogni d ∈ D, I,V(v/d) |= ψ ⇔ per l’ipotesiinduttiva, per ogni d ∈ D, I ′,V ′(v/η(d)) |= ψ. Ma η e una corrispondenza biunivocatra D e D′ e quindi abbiamo che, per ogni d′ ∈ D′, I ′,V ′(v/d′) |= ψ che equivale aI ′,V ′ |= ∀v ψ.

Definizione 5.3 Una teoria assiomatica e categorica se tutti i suoi modelli sono isomorfi(cioe se ha un solo modello, a meno di isomorfismi).

La categoricita e molto importante quando, come nel caso dei numeri reali, una teoriaassiomatica ha lo scopo di precisare formalmente proprieta di una particolare struttura,come la retta reale, della quale abbiamo un’intuizione abbastanza precisa. In questo casopossiamo dire che gli assiomi catturano tutte le proprieta essenziali di quella struttura,nel senso che non esistono strutture diverse (non isomorfe) in cui tali assiomi sono veri-ficati. Come abbiamo gia osservato, la teoria assiomatica dei numeri reali e categorica.Mostreremo piu avanti che anche la teoria dei numeri naturali basata sugli Assiomi diPeano e categorica. Inversamente, non e difficile rendersi conto che la teoria dei gruppinon e categorica, cosı come molte altre teorie che studiamo in algebra.

Si potrebbe pensare che questa differenza tra teoria dei gruppi e teoria dei reali sia dovutasemplicemente al fatto che la prima ha meno assiomi della seconda. E effettivamente veroche aumentando gli assiomi in generale diminuiscono i modelli di una teoria perche talimodelli devono verificare piu enunciati. Tuttavia, la differenza tra teoria dei gruppi eteoria dei campi ordinati completi e molto piu sostanziale: come abbiamo gia osservato,la prima e una teoria del primo ordine mentre la seconda e una teoria del secondo ordine.

Proposizione 5.4 Ogni teoria del primo ordine con modelli infiniti non e categorica.

Dimostrazione. Per il Teorema di Lowenheim-Skolem (T. 4.6), se T ha modelli infini-ti, allora ha modelli infiniti di cardinalita arbitrariamente grande, ma due modelli dicardinalita diversa non possono essere isomorfi.

La Proposizione 5.4 (che risolve l’Esercizio 4.7) chiude definitivamente la questione dellacategoricita per le teorie del primo ordine con modelli infiniti. Possiamo pero chiedercise, fissato un cardinale, tutti i modelli equipotenti a quel cardinale siano isomorfi.

18

Definizione 5.5 Sia α un insieme cardinale. Una teoria assiomatica e α-categorica setutti i suoi modelli di cardinalita α sono isomorfi.12

Ogni numero naturale e un insieme cardinale. Una teoria n-categorica e dunque una teoriai cui modelli con n elementi sono tutti isomorfi. Dal corso di algebra sappiamo che ognigruppo con un numero primo di elementi e ciclico e che gruppi ciclici con lo stesso ordinesono isomorfi ([Piacentini Cattaneo, 1996, Cap.5]). Possiamo quindi concludere che, perogni numero primo p, tutti i gruppi di ordine p sono isomorfi. Abbiamo quindi il seguenterisultato.

Proposizione 5.6 Per ogni numero primo p, la teoria dei gruppi e p-categorica.

Consideriamo ora la formula En definita in (4.4) e la formula

An = ∃x1, . . . , xn∀x(x = x1 ∨ · · · ∨ x = xn) (5.5)

Abbiamo gia osservato che l’enunciato En in (4.4) risulta vero in una interpretazione〈D, I〉 se D ha almeno n elementi. La formula An invece e vera quando il dominio haal piu n elementi. Abbiamo quindi che la congiunzione En ∧ An e vera quando D haesattamente n elementi. Indichiamo con TGn la teoria assiomatica avente come assiomi gliassiomi della teoria dei gruppi e l’enunciato En ∧An. Per la Proposizione 5.6, abbiamo ilseguente risultato.

Proposizione 5.7 Per ogni numero primo p, la teoria TGp dei gruppi di ordine p ecategorica.

Esercizio 5.8 Dimostrare che la teoria dei gruppi non e ℵ0-categorica.

Suggerimento. Si considerino i gruppi numerabili 〈Z,+, 0〉 e 〈Q+, ·, 1〉. Si supponga perassurdo che f sia un isomorfismo tra le due strutture e si dimostri che, per ogni k ∈ Z,f(k) = (f(1))k. Si concluda che f non puo essere suriettiva.

Esercizio 5.9 Sia L un linguaggio senza simboli per costanti o per funzioni, e con unsolo simbolo R per relazione n-aria. Dimostrare che se due interpretazioni I e I ′ di Lverificano gli stessi enunciati e una delle due e finita, allora esse sono isomorfe.

Svolgimento. Osserviamo innanzitutto che, se l’interpretazione I ha k elementi: D ={a1 . . . ak}. Allora anche I ′ ha k elementi perche l’esistenza di esattamente k oggetti eesprimibile da una formula del primo ordine.

12Anche in questo caso possiamo riformulare la definizione senza ricorrere alla nozione di insiemecardinale: sia X un insieme. Una teoria assiomatica e X-categorica se tutti i suoi modelli M tali checard(M) = card(X) sono isomorfi. In particolare, anticipando una notazione della seconda parte delcorso, diciamo che una teoria e ℵ0-categorica se tutti i suoi modelli numerabili sono isomorfi.

19

Fissiamo un insieme {x1 . . . xk} di variabili distinte (tante quante gli elementi di D).Per ogni n-upla (xi1 , . . . , xin) di elementi (non necessariamente distinti) in {x1 . . . xk},consideriamo la formula

A(xi1 , . . . , xin) =

{R(xi1 , . . . , xin) se (ai1 , . . . , ain) ∈ RI

¬R(xi1 , . . . , xin) se (ai1 , . . . , ain) 6∈ RI

Sia ϕ(x1, . . . , xk) la congiunzione di tutte le (kn) formule A(xi1 , . . . , xin). La formu-la ϕ(x1, . . . , xk) risulta vera in I quando le variabili x1, . . . , xk vengono interpretaterispettivamente in a1, . . . , ak. Risulta quindi vera in I anche la formula

ψ = ∃x1, . . . , xk

[( ∧1≤i<j≤k

xi 6= xj

)∧ ϕ(x1, . . . , xk)

]

Per le ipotesi ψ e vera anche in I ′. Esistono quindi k elementi b1, . . . , bk di D′, tuttidistinti (da cui segue {b1, . . . , bk} = D′) e tali che ϕ(x1, . . . , xk) risulta vera in I ′ quandox1, . . . , xk vengono interpretati rispettivamente in b1, . . . , bk. Per come e stata definitaϕ(x1, . . . , xk), poiche R e l’unico simbolo per relazioni in L, abbiamo che da funzionef : D → D′ definita da f(ai) = bi e un isomorfismo.

5.1 Ordini lineari, densi, senza estremi

Consideriamo la teoria assiomatica TOLDS espressa in un linguaggio senza costanti efunzioni, e con un solo simbolo, ≤, per relazione binaria. Gli assiomi di tale teoria sono:

O1− 4 Assiomi per gli ordini lineari

O5 ∀x, y[x < y → ∃z(x < z < y)] (densita)

O6 ∀x∃y(x < y) (assenza di massimo)

O7 ∀x∃y(y < x) (assenza di minimo)

I modelli di TOLDS sono gli ordini lineari, densi, senza estremi. Tale teoria non e categorica.Possiamo infatti osservare che i reali e i razionali con l’usuale relazione d’ordine sono suoimodelli, ma non possono essere isomorfi perche hanno cardinalita diversa. Vedremo cheTOLDS e ℵ0-categorica.

Ricordiamo preliminarmente che in Teoria degli Insiemi una funzione f : X → Y vienevista come un insieme di coppie 〈a, b〉 ∈ X × Y tale che: 1) per ogni a ∈ D, esiste b ∈ Ytale che 〈a, b〉 ∈ f , e 2) se 〈a, b〉 ∈ f e 〈a, b′〉 ∈ f , allora b = b′. Nella notazione usuale〈a, b〉 ∈ f viene espresso da f(a) = b. Quindi, in teoria degli insiemi, le funzioni vengonoidentificate con l’insieme che spesso viene chiamato grafico della data funzione.

Definizione 5.10 Siano X = 〈X,≤〉 e Y = 〈Y,≤′〉 ordini lineari. Un isomorfismo(finito) parziale da X in Y e una funzione f = {〈xi, yi〉 ∈ X × Y : i ≤ n, x0 < · · · <xn e y0 <

′ · · · <′ yn}. Gli insiemi {x0, . . . , xn} e {y0, . . . , yn} sono rispettivamente ildominio e l’ immagine di f .

20

Lemma 5.11 Siano X = 〈X,≤〉 e Y = 〈Y,≤′〉 ordini lineari densi senza estremi, e siaf = {〈xi, yi〉 ∈ X × Y : i ≤ n} un isomorfismo parziale da X in Y. Allora, per ognix ∈ X (risp. y ∈ Y ) esiste un isomorfismo parziale f ′ ⊇ f da X in Y avente comedominio (risp. immagine) l’insieme {x0, . . . , xn, x} (risp. {y0, . . . , yn, y}).

Dimostrazione. Esercizio. Si osservi che, se x ∈ {x0, . . . , xn} (risp. y ∈ {y0, . . . , yn}),allora f ′ = f .

Teorema 5.12 Se le interpretazioni X = 〈X,≤〉 e Y = 〈Y,≤′〉 sono modelli numerabilidi TOLDS, allora X e isomorfo a Y.

Dimostrazione. La dimostrazione di questo teorema e un esempio della tecnica del back-and-forth, nel senso che definiamo un isomorfismo f da 〈X,≤〉 su tutto 〈Y,≤′〉 andandoavanti e indietro tra le due strutture.

Dalla numerabilita di X e Y segue che possiamo scrivere questi insiemi come:

X = {x0, x1, . . . , xn, . . . } Y = {y0, y1, . . . , yn, . . . }

Per ogni naturale n definiamo induttivamente un isomorfismo parziale fn da X in Y conla proprieta che, per n < m, fn ⊆ fm. Poniamo f0 = {〈x0, y0〉}. Per ogni n > 0 definiamofn usando il Lemma 5.11. Se n = 2k − 1 e dispari allora fn si ottiene aggiungendo ykall’immagine di fn−1. Se n = 2k e pari, allora otteniamo fn aggiungendo xk al dominiodi fn−1.

Poniamo f = ∪n∈Nfn e mostriamo che f e un isomorfismo sa X su Y . Se 〈a, b〉 e 〈a, b′〉sono elementi di f , possiamo considerare il minimo n tale che 〈a, b〉 ∈ fn e 〈a, b′〉 ∈ fn,da cui segue b = b′ perche ogni fn e una funzione. In modo analogo si dimostra che fconserva l’ordine. Poiche infine nella costruzione vengono considerati tutti gli elementixk ∈ X e tutti i yk ∈ Y , abbiamo che f (che contiene ogni fn) e una funzione da X sututto Y .

Corollario 5.13 Tutti gli ordini lineari densi, senza estremi, e numerabili sono isomorfi,come insiemi ordinati, ai numeri razionali.

Anche in questo caso si vede come la nozione di isomorfismo dipenda dalle funzioni e rela-zioni che consideriamo. Per esempio, il campo ordinato dei reali algebrici13 e numerabile,ed e quindi isomorfo a Q come insieme ordinato, Ma non e isomorfo a Q come campo.

6 Completezza Semantica e Completezza Sintattica

Definizione 6.1 La teoria T e semanticamente completa se per ogni enunciato del lin-guaggio di T vero in ogni modello di T e anche dimostrabile in T .

13Sono algebrici i reali che sono radici di polinomi a coefficienti in Z. I reali non algebrici vengonochiamati trascendenti.

21

Teorema 6.2 (T. di Adeguatezze e di Completezza Semantica per Teorie delPrimo Ordine) Ogni enunciato del linguaggio della teoria del primo ordine T e vero inogni modello di T se e solo se e dimostrabile in T .

Dimostrazione. Sia T una teoria del primo ordine e sia ϕ un enunciato del linguaggio diT . Se ϕ e teorema di T allora, per DL2, ϕ e vera in ogni modello di T .14

Supponiamo inversamente che ϕ non sia teorema di T . Per la Proposizione 3.3 la teoriaT ∪ {¬ϕ} e coerente e, per il Teorema 4.1, ha modelloM. QuindiM e un modello di Tin cui ϕ non e vero.

Definizione 6.3 La teoria T e sintatticamente completa se per ogni enunciato ϕ dellinguaggio di T , T ` ϕ oppure T ` ¬ϕ.15

Osservazione 6.4 Nelle definizioni di completezza semantica e sintattica parliamo didimostrabilita di un enunciato. Bisogna pero distinguere la dimostrabilita di un enunciato,dal fatto che siamo in grado (anche solo teoricamente) di trovarne una dimostrazione. Cisono esempi di teorie semanticamente o sintatticamente complete, per le quali non esisteun algoritmo in grado di determinare la dimostrazione di ogni formula dimostrabile.

E chiaro che la completezza sintattica e una proprieta e molto forte: si richiede che la teoriasia in grado di dimostrare o confutare ogni enunciato. All’inizio del ’900, tuttavia, essa eraconsiderata piu forte di quanto effettivamente sia. Si pensava infatti che i modelli di unateoria sintatticamente completa dovessero essere isomorfi perche verificano esattamentele stesse formule. In altri termini, si pensava che la completezza sintattica implicassela categoricita. Il teorema di Lowenheim-Skolem ed altri risultati ci dicono che cio none vero: possono esserci strutture non isomorfe che rendono vere le stesse formule. Perquanto riguarda le teorie del primo ordine e vero invece il seguente risultato opposto.

Proposizione 6.5 Ogni teoria categorica del primo ordine e sintatticamente completa.

Dimostrazione. Sia T sia una teoria categorica del primo ordine e supponiamo per assurdoche T non sia sintatticamente completa. Esiste quindi un enunciato ϕ tale che T 6` ϕe T 6` ¬ϕ. Per la Proposizione 3.3 abbiamo che entrambe le teorie T ′ e T ′′ ottenuteaggiungendo rispettivamente ¬ϕ e ϕ agli assiomi di T sono coerenti e quindi, per ilTeorema 4.1, queste teorie hanno modello. Siano M′ e M′′ i rispettivi modelli delledue teorie. Questi modelli devono essere isomorfi in quanto modelli anche di T (che ecategorica), ma per la Proposizione 5.2 cio e assurdo perche il primo modello verifica ¬ϕmentre il secondo verifica ϕ.

Un’applicazione di questo risultato viene dalla Proposizione 5.7: la teoria TGp e sintatti-camente completa.

14Questa parte del teorema va sotto il nome di Teorema di Adeguatezza, o di Validita.15Si osservi che questa definizione e significativa solo se parliamo di enunciati, e non di formule con

variabili libere. Non ha senso infatti richiedere, per esempio, che la formula x ≤ 0 o la sua negazione sianodimostrabili. I teoremi di una teoria sono veri in tutti i modelli della teoria stessa, e non possiamo quindirichiedere che siano dimostrabili formule la cui verita dipende da come vengono valutate le variabili.

22

Aggiungendo un’ulteriore ipotesi la Proposizione 6.5 puo essere estesa al caso di teorieα-categoriche per qualche α infinito.

Proposizione 6.6 Se la teoria del primo ordine T non ha modelli finiti ed e α-categoricaper qualche α infinito e maggiore o uguale alla cardinalita del linguaggio di T , allora T esintatticamente completa.

Dimostrazione. La dimostrazione e simile a quella precedente. Supponendo che la teoriaT non sia sintatticamente completa concludiamo che esistono due modelliM′ eM′′ di Tche non verificano le stesse formule. Dalle ipotesi su T segue che questi due modelli sonoinfiniti e quindi, per il Teorema di Lowenheim-Skolem, possiamo supporre che M′ e M′′

abbiano cardinalita α. A questo punto si arriva ad un assurdo come nella dimostrazioneprecedente usando il fatto che T e α-categorica.

Come conseguenza di questa proposizione abbiamo che la teoria degli ordini densi senzaestremi considerata nel §5.1 (che non ha modelli finiti) e sintatticamente completa.

Il seguente risultato mette in relazione la completezza semantica con la completezzasintattica. Non dovrebbe sorprendere il fatto che il legame tra le due nozioni sia lacategoricita.

Proposizione 6.7 Ogni teoria T semanticamente completa e categorica e sintatticamen-te completa.

Dimostrazione. Sia M l’unico modello di T . Dalla completezza semantica di T segueche ogni formula vera inM e dimostrabile in T . A questo punto possiamo osservare che,dato un qualsiasi enunciato ϕ, tale enunciato oppure la sua negazione sono veri in M equindi dimostrabili in T .

Esercizio 6.8 Se la teoria T e sintatticamente completa e ha un modello, allora T esemanticamente completa.

Suggerimento. Usare il fatto che T 6` ϕ implica che ¬ϕ e vera in tutti i modelli di T .

7 Assiomi di Peano - I numeri naturali

La presentazione assiomatica dei numeri naturali e basata sugli Assiomi di Peano (o diPeano-Dedekind). In base a questa presentazione, i numeri naturali sono una struttura〈N, 0, σ〉 dove N e un insieme, 0 e un elemento di N e σ e una funzione da N in N , taliche:

(N1) ∀n (σn 6= 0)

(N2) ∀n,m (σn = σm→ n = m)

23

(PI) ∀X ⊆ N [(0 ∈ X ∧ ∀k (k ∈ X → σk ∈ X))→ X = N ] 16

Indicheremo con TN la teoria basata sui tre assiomi di Peano. Si osservi che in PI, ilPrincipio di Induzione, ∀X e un quantificatore del secondo ordine perche quantifica su℘(N), l’insieme di tutti i sottoinsiemi di N .17 La teoria TN e dunque una teoria delsecondo ordine.

Una variante, piu informale, ma molto usata, del Principio di Induzione e la seguente:

(PIP ) Se il numero naturale 0 ha una certa proprieta P , e dal fatto che k ha la proprietaP segue che σk ha tale proprieta, allora ogni numero naturale n ha la proprieta P .

Gli enunciati PI e PIP risultano equivalenti in base alla seguente corrispondenza trainsiemi e proprieta. Ad ogni proprieta P possiamo associare l’insieme KP dei naturaliaventi tale proprieta e ad ogni insieme K di naturali possiamo associare la proprieta PKdi appartenere a K. Si verifica facilmente che P = PKP e K = KPK da cui segue che lacorrispondenza tra proprieta dei naturali e sottoinsiemi di N e biunivoca.

Internamente alla teoria degli insiemi si dimostra che la teoria dei naturali e coerente.L’ordinale ω infatti e costituito dagli insiemi

∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, . . .

dove il successore di ogni elemento α e α ∪ {α}. Posto σn = n ∪ {n}, la terna 〈ω, ∅, σ〉risulta essere un modello di N1, N2, PI.18

Questo e un ulteriore esempio di situazione in cui e evidente la natura assiomatica del-l’aritmetica di Peano. La struttura 〈ω, ∅, σ〉 e un modello di N1, N2 e PI, ma e anchedotato di una struttura insiemistica e in particolare la relazione ∈ su ω e una relazioned’ordine stretto. Per potere parlare di relazione d’ordine sui naturali, tuttavia, abbiamobisogno di una costruzione piu complessa che vedremo in seguito, e che deve essere basatasolo sugli assiomi di Peano.

Dimostriamo ora che gli Assiomi di Peano sono indipendenti costruendo tre opportunimodelli della forma 〈N, 0, σ〉, dove tuttavia N, 0, e σ sono scelti in modo da rendere veridue degli assiomi e falsificare il rimanente.

(1) Sia N = {0}, dove 0 e un arbitrario oggetto, e poniamo σ0 = 0. Si verifica facilmenteche gli assiomi N2 e PI sono veri in questa struttura (esercizio), mentre N1 ebanalmente falso.

16Spesso questi assiomi sono preceduti da “0 e un numero naturale” e “il successore di un numeronaturale e un numero naturale”. Ma queste due assunzioni sono implicite nel considerare strutture〈N, 0, σ〉, con 0 costante e σ funzione.

17A rigore, N non e un simbolo del linguaggio per l’Aritmetica di Peano. Una formulazione piu correttadel Principio di Induzione sarebbe stata questa: ∀X [(0 ∈ X ∧∀k (k ∈ X → σk ∈ X))→ ∀n(n ∈ X)], con∀X quantificazione del II ordine. Una volta chiarito questo, conviene continuare con la solita notazione.

18In particolare, nella struttura ω abbiamo che ogni naturale risulta l’insieme dei naturali che loprecedono.

24

(2) Sia N = {0, a, b}, dove 0, a e b sono oggetti distinti, e poniamo σ0 = a, σa = b eσb = a. In questa struttura N1 e PI sono verificati (esercizio), ma σ non e iniettivaperche σ0 = σb, e quindi N2 non e verificato.

(3) Siano 0 e a due oggetti distinti e siaN l’insieme di tutte le successioni finite 0, , 00, 000, . . .e a, aa, aaa, . . . . Data una successione s ∈ N , σs e la piu piccola successione in Nche contiene propriamente s. Questa struttura verifica N1 e N2 (esercizio). Sia Xin sottoinsieme di N costituito da tutte le successioni in cui compare solo 0. Abbia-mo che l’antecedente del Principio di Induzione e verificato da X, ma ovviamenteX 6= N .

D’ora in avanti, in questo paragrafo, parlando dei numeri naturali intenderemo sempreun arbitrario modello 〈N, 0, σ〉 degli assiomi N1, N2 e PI. Come abbiamo visto sopra,esiste almeno una struttura con queste proprieta. In ognuna di queste strutture, diremoche σn e il successore del numero naturale n.

Osservazione 7.1 Abbiamo usati gli stessi simboli (0, σ, ∀n, ecc.) sia per esprimeregli assiomi di Peano, sia in riferimento al modello 〈N, 0, σ〉 di tali assiomi. A rigore, gliassiomi sono formule di un linguaggio formale (v. anche Nota 17) e si sarebbero dovuteesprimere in un linguaggio con una costante, c, ed un simbolo per funzione 1-aria f 1.Abbiamo volutamente evitato questa distinzione per non appesantire la notazione.

La dimostrazione dell’indipendenza del Principio di Induzione mette in luce il significatodi questo principio, cioe che ogni numero naturale puo essere raggiunto dallo 0 mediantesuccessive applicazioni della funzione σ, cioe che l’insieme dei naturali puo essere descrittocome {0, σ0, σσ0, . . . }. Piu formalmente, se un insieme X contiene 0 ed e chiuso perl’operazione σ allora X esaurisce tutto N . Vale inoltre la seguente proposizione, la cuidimostrazione e un primo esempio di dimostrazione per induzione.

Proposizione 7.2 Se 〈N, 0, σ〉 e un modello di N1, N2 e PI, allora, per ogni n 6= 0 inN , esiste un unico m ∈ N tale che n = σm.

Dimostrazione. Sia X l’insieme {n ∈ N : n = 0 oppure ∃m : n = σm}. L’insieme Xcontiene ovviamente 0. Se k ∈ X, allora σk appartiene a X perche X contiene tutti glielementi di N del tipo σn. Per l’assioma PI, possiamo concludere che X = N . Per quantoriguarda l’unicita, per N2 abbiamo che da σm = σm′ segue m = m′.

Da questa proposizione segue che l’immagine della funzione σ e N \ {0} e quindi, perogni n 6= 0, possiamo parlare del predecessore di n come dell’unico m tale che σm = n; ilpredecessore di n verra indicato con σ−1n.

Esercizio 7.3 Dimostrare che, per ogni n ∈ N , n 6= σn.

25

7.1 Definizione per induzione. Categoricita degli assiomi diPeano

Abbiamo visto nel paragrafo precedente che ogni naturale puo essere raggiunto dallo 0tramite successive applicazioni della funzione σ. Questa proprieta sta alla base della co-struzione di molte funzioni definite sui naturali, incluse le usuali operazioni di sommae prodotto. Intuitivamente, possiamo definire una funzione f fornendo il valore f(0) efornendo una regola che permetta di calcolare f(σn) una volta calcolato f(n). Per esem-pio, supponendo di aver gia definito la moltiplicazione, il fattoriale puo essere definito da0! = 1 e (σn)! = σn·n!. Per accettare questo tipo di definizioni, dobbiamo pero dimostrareche questa procedura definisce effettivamente una funzione. La seguente dimostrazione ealtre in questa sezione sono tratte da [Feferman, 1964]

Teorema 7.4 [Definizione per Induzione 1] Sia X un insieme, sia a un elemento di X, esia F una funzione da X in X. Allora, per ogni modello 〈N, 0, σ〉 degli Assiomi di Peano,esiste un’unica funzione f da N in X con le seguenti proprieta: (1) f(0) = a, (2) per ognin ∈ N , f(σn) = F (f(n)).

Dimostrazione. Dimostriamo prima l’esistenza di f e poi l’unicita.

Insiemisticamente, una funzione da N in X e un insieme di coppie 〈n, x〉 ∈ N × X.Consideriamo l’insieme F costituito da tutti i sottoinsiemi W di N ×X tali che

(1′) 〈0, a〉 ∈ W(2′) 〈n, x〉 ∈ W ⇒ 〈σn, F (x)〉 ∈ W

L’insieme F non e vuoto perche l’intero insieme N ×X ha le proprieta (1′) e (2′) e quindiappartiene a F . Si osservi che queste proprieta corrispondono proprio alle proprieta (1) e(2) dell’enunciato del teorema. L’insieme F e chiuso per intersezioni arbitrarie. Se Wi ∈ Fper ogni i ∈ I e W =

⋂i∈IWi, allora 〈0, a〉 ∈ W perche questa coppia appartiene a ogni

Wi. Se 〈n, x〉 ∈ W allora, per ogni i, 〈n, x〉 ∈ Wi e, per la proprieta (2’) 〈σn, F (x)〉 ∈ Wi.Ma da cio segue 〈σn, F (x)〉 ∈ W che quindi appartiene a F .

Appartiene dunque a F anche l’insieme f definito da

f =⋂W∈F

W (7.6)

Dimostriamo ora che l’insieme f e effettivamente una funzione da N in X, cioe che

(3) ∀n ∈ N, ∃x ∈ X : 〈n, x〉 ∈ f(4) ∀n ∈ N, ∀x1, x2 ∈ X, 〈n, x1〉 ∈ f e 〈n, x2〉 ∈ f ⇒ x1 = x2

E facile dimostrare (3) per induzione. Sia K l’insieme {n ∈ N : ∃x ∈ X : 〈n, x〉 ∈ f}.Per (1′), abbiamo 0 ∈ K e, per (2′), se k ∈ K, allora σk ∈ K. Abbiamo quindi K = N ,cioe (3).

26

Anche (4) si dimostra per induzione. Poniamo

K = {n ∈ N : ∀x1, x2 ∈ X, 〈n, x1〉 ∈ f e 〈n, x2〉 ∈ f ⇒ x1 = x2} (7.7)

K e dunque l’insieme dei naturali sui quali f ‘si comporta’ come una funzione. Dimostre-remo per induzione che K = N .

Supponiamo per assurdo 0 6∈ K, cioe 〈0, x0〉 ∈ f per qualche x0 6= a. Consideriamo ilsottoinsieme V di N ×X definito da V = f \ {〈0, x0〉}. L’insieme V verifica la proprieta(1′) perche f ha tale proprieta e x0 6= a. Se 〈n, x〉 ∈ V , allora 〈n, x〉 ∈ f e, per (2′),〈σn, F (x)〉 ∈ f ; ma cio implica 〈σn, F (x)〉 ∈ V perche, per N1, 0 6= σn per ogni n.Abbiamo quindi che V ha le proprieta (1′) e (2′) e quindi V ∈ F , ma cio contraddice (7.6)perche V e contenuto propriamente in f .

Dimostriamo ora preliminarmente che, per ogni naturale n,

〈σn, y〉 ∈ f ⇒ ∃x : 〈n, x〉 ∈ f e y = F (x) (7.8)

Cio significa che ogni coppia del tipo 〈σn, y〉 puo essere vista come risultato della proprieta(2′). Supponiamo per assurdo che l’implicazione (7.8) non valga, cioe che esista una coppia〈σn0, y〉 in f tale che, per ogni x ∈ X, se 〈n0, x〉 ∈ f , allora y 6= F (x). Consideriamol’insieme V = f \ {〈σn0, y〉}; vogliamo dimostrare che V ∈ F , cioe che verifica (1′) e (2′),in modo da contraddire (7.6) come nel caso precedente. La coppia 〈0, a〉 appartiene a fe quindi anche a V perche 0 6= σn0. Supponiamo 〈k, z〉 ∈ V , cosicche 〈k, z〉 e 〈σk, F (z)〉appartengono a f , ma per le ipotesi su n0 abbiamo che 〈σk, F (z)〉 6= 〈σn0, y〉, e quindi〈σk, F (z)〉 ∈ V . Abbiamo dunque V ∈ F che contraddice (7.6).

Possiamo tornare all’insieme K definito in (7.7) e dimostrare che k ∈ K implica σk ∈ K.Supponiamo 〈σk, y1〉 ∈ f e 〈σk, y2〉 ∈ f . Da (7.8) segue che esistono x1 e x2 tali che〈k, x1〉 ∈ f , 〈k, x2〉 ∈ f , y1 = F (x1) e y2 = F (x2). Ma dall’ipotesi k ∈ K segue x1 = x2 equindi y1 = y2, cioe σk ∈ K. Cio conclude la dimostrazione che K = N e quindi che f euna funzione.

Supponiamo ora che due funzioni f1 ed f2 da N in X verifichino le condizioni (1) e (2)dell’enunciato di questo teorema. Vogliamo dimostrare che f1 = f2, cosicche la funzionef definita sopra risultera unica.

Sia K l’insieme {n ∈ N : f1(n) = f2(n)}; dimostriamo per induzione che K = N . Dallacondizione (1) segue banalmente che 0 ∈ K. Supponiamo k ∈ K, cioe f1(k) = f2(k).Dalla condizione (2) abbiamo f1(σk) = F (f1(k)) = F (f2(k)) = f2(σk), e quindi σk ∈ K.

Questo risultato ci permette di dimostrare il teorema dell’unicita del modello degli assiomidi Peano.

Teorema 7.5 Siano 〈N, 0, σ〉 e 〈N ′, 0′, σ′〉 strutture in cui sono verificati gli assiomi diPeano N1, N2 e PI. Allora le due strutture sono isomorfe.

Dimostrazione. Per il Teorema 7.4, ponendo X = N ′, a = 0′ e F = σ′, esiste un’unicafunzione f da N in N ′ tale che f(0) = 0′ e, per ogni n ∈ N , f(σn) = σ′f(n). Abbiamo

27

quindi che f verifica le clausole b. e c. della Definizione 5.1 (si noti che la condizione d. ebanalmente verificata). Per concludere che f e un isomorfismo, dobbiamo dimostrare chee suriettiva e iniettiva.

Consideriamo l’insieme Im(f) = {n′ ∈ N ′ : ∃n ∈ N : f(n) = n′}. Im(f) contiene 0′

perche f(0) = 0′. Se k′ ∈ Im(f) e f(k) = k′, allora f(σk) = σ′f(k) = σ′k′ e quindi ancheσ′k′ ∈ Im(f). Poiche 〈N ′, 0′, σ′〉 verifica PI, abbiamo Im(f) = N ′ e quindi f e suriettiva.

Consideriamo ora l’insieme

K = {n ∈ N : ∀m ∈ N, f(n) = f(m)⇒ n = m}

Anche in questo caso dimostriamo per induzione che K = N , da cui segue che f e iniettiva.Poiche f(0) = 0′, dobbiamo dimostrare che, per ogni m, f(m) = 0′ ⇒ m = 0. Se, perassurdo, f(m) = 0′ e m 6= 0, allora, per il Teorema 7.2, esiste k tale che m = σk e quindi0′ = f(m) = σ′f(k), ma queste uguaglianze contraddicono N1 per σ′.

Sia ora k ∈ K e supponiamo f(σk) = f(m). Poiche f(σk) = σ′f(k) 6= 0′, abbiamo chem non puo essere 0. Esiste quindi un n tale che m = σn e quindi f(m) = σ′f(n), e, perl’assioma N2 applicato a σ′ abbiamo che σ′f(n) = σ′f(k) implica f(n) = f(k). Poichek ∈ K, abbiamo infine n = k e m = σk. Questo conclude la dimostrazione che f einiettiva

Quest’ultimo teorema puo essere enunciato in modo equivalente dicento che la teoriacostituita dagli assiomi di Peano e categorica.

Il Teorema 7.4 ha spesso la seguente forma un po’ piu complessa.

Teorema 7.6 [Definizione per Induzione 2] Sia 〈N, 0, σ〉 un modello di N1, N2 e PI,X un insieme, a un elemento di X, e ϕ una funzione da N × X in X. Allora esisteun’unica funzione f da N in X con le seguenti proprieta: (1) f(0) = a, (2) per ognin ∈ N , f(σn) = ϕ(n, f(n)).

Omettiamo la dimostrazione che puo essere svolta in modo analogo a quella del Teo-rema 7.4: la funzione f viene definita come l’intersezione di tutti gli insiemi W checontengono 〈0, a〉 e chiusi per l’operazione 〈n, x〉 ∈ W ⇒ 〈σn, ϕ(n, x)〉 ∈ W .

7.2 Somma di naturali

Una volta dimostrato che gli assiomi N1, N2 e PI determinano un’unica struttura ma-tematica (Teorema 7.5) resta il problema di definire le usuali operazioni sui naturali. Ciaspettiamo ovviamente di dover usare una definizione per induzione e quindi il Teore-ma 7.4. In base a questo teorema, per esempio, possiamo definire una funzione +m cheapplicata ad ogni naturale gli somma m: (i) +m(0) = m, (ii) +m(σn) = σ(+m(n)). Inquesto caso, l’insieme X, l’elemento a, e la funzione ϕ del Teorema 7.4 sono rispettiva-mente N , m, e la funzione σ. La funzione somma puo dunque essere definita consideriamol’insieme di tutte le +n. Questo passaggio viene formalizzato dal seguente teorema.

28

Teorema 7.7 Date due funzioni g : N ×N → N e h : N → N , esiste un’unica funzionef da N ×N in N con le seguenti proprieta

(1) f(n, 0) = h(n)

(2) f(n, σm) = g(n, f(n,m))

Dimostrazione. Per ogni naturale k, indichiamo con ak il valore di h(k) e con ϕk : N → N

la funzione definita da ϕk(n) = g(k, n). Per il Teorema 7.4, esiste un’unica funzionefk : N → N tale che fk(0) = ak e fk(σn) = ϕk(fk(n)).

Possiamo ora definire f : N2 → N tramite:

f(n,m)def= fn(m)

Per tale funzione valgono le uguaglianze f(n, 0) = fn(0) = an = h(n) e f(n, σm) =fn(σm) = ϕn(fn(m)) = g(n, fn(m)) = g(n, f(n,m)). Le condizioni (1) e (2) sono dunqueverificate dalla funzione f .

Se f ′ : N×N → N e un’altra funzione che verifica (1) e (2), per ogni naturale n possiamoconsiderare la funzione f ′n definita da f ′n(m) = f ′(n,m). Per l’unicita delle funzioni fndeve essere f ′n = fn per ogni naturale n, da cui segue f ′ = f .

Siamo ora in grado di definire l’operazione di somma ponendo, nel Teorema 7.7, g(n,m) =σ(m) e h(n) = n. In questo modo, la funzione f , che indicheremo con f+, risulta definitada:

(1) f+(n, 0) = n

(2) f+(n, σ(m)) = σf+(n,m)(7.9)

Dobbiamo ora dimostrare che f+ gode effettivamente delle proprieta della funzione somma.Si osservi per esempio che la definizione di f+(n,m) non e simmetrica nelle variabili m en, per cui non e immediato concludere la commutativita di f+.

Proposizione 7.8 [Associativita di +] Per ogni n, m, k, f+(n, f+(m, k)) = f+(f+(n,m), k).

Dimostrazione. Procediamo per induzione su k, facendo svolgere a n e m il ruolo diparametri. Poniamo

K = {k ∈ N : f+(n, f+(m, k)) = f+(f+(n,m), k)}

Per (1) in (7.9), f+(n, f+(m, 0)) = f+(n,m) = f+(f+(n,m), 0). Dunque 0 ∈ K. Sup-posto k ∈ K, usando (2) in (7.9) e l’ipotesi induttiva, abbiamo f+(n, f+(m,σk)) =

f+(n, σf+(m, k)) = σf+(n, f+(m, k))i.i.= σf+(f+(n,m), k) = f+(f+(n,m), σk); per cui

anche σk ∈ K.

Lemma 7.9 Per ogni naturale n, f+(n, 0) = f+(0, n).

Dimostrazione. Per induzione su n. Poniamo K = {k ∈ N : f+(k, 0) = f+(0, k)}. Ba-

nalmente 0 ∈ K. Supponiamo k ∈ K. Allora f+(σk, 0) = σk = σf+(k, 0)i.i.= σf+(0, k) =

f+(0, σk).

29

Lemma 7.10 Per ogni coppia m,n di naturali, f+(σn,m) = f+(n, σn).

Dimostrazione. Per induzione su m. Poniamo K = {k ∈ N : f+(σn, k) = f+(n, σk)}.Dalle uguaglianze f+(σn, 0) = σn = σf+(n, 0) = f+(n, σ0) segue 0 ∈ K. Supposto k ∈ K,

abbiamo f+(σn, σk) = σf+(σn, k)i.i.= σf+(n, σk) = f+(n, σσk).

Proposizione 7.11 [Commutativita di +] Per ogni n, m, f+(n,m) = f+(m,n).

Dimostrazione. Per induzione su m. Fissato n ∈ N , poniamo K = {k ∈ N : f+(n, k) =

f+(k, n)}. Per il Lemma 7.9, 0 ∈ K. Posto k ∈ K, abbiamo f+(n, σk) = σf+(n, k)i.i.=

σf+(k, n) = f+(k, σn) = f+(σk, n) per il Lemma 7.10.

Proposizione 7.12 [Cancellazione per +] Per ogni n, m, k, se f+(n, k) = f+(m, k),allora n = m.

Dimostrazione. Poniamo K = {k ∈ N : f+(n, k) = f+(m, k) ⇒ n = m}. Banalmente,0 ∈ K. Posto k ∈ K, supponiamo f+(n, σk) = f+(m,σk) che equivale a σf+(n, k) =σf+(m, k) da cui segue f+(n, k) = f+(m, k) per l’iniettivita di σ. Ma per l’ipotesi induttivadall’ultima uguaglianza segue n = m e quindi anche σk ∈ K.

Esercizio 7.13 (i) Dimostrare che n = f+(n,m) se e solo se m = 0. (ii) Dimostrare chef+(n,m) = 0 se e solo se n = m = 0.

Proposizione 7.14 [Tricotomia per +] Dati i numeri naturali n e m, vale una ed unasolo delle seguenti alternative:

(i) n = m;

(ii) esiste un unico x 6= 0 tale che n = f+(m,x);

(iii) esiste un unico x 6= 0 tale che m = f+(n, x).

Dimostrazione. Dimostriamo prima le asserzioni di unicita. Se (i) e (ii) fossero con-temporaneamente verificate, allora verrebbe contraddetto l’enunciato dell’Esercizio 7.13.Analogamente per (i) e (iii). Se (ii) e (iii) valessero contemporaneamente, allora avremmon = f+(m,x) = f+(f+(n, x′), x) = f+(n, f+(x′, x)) che ancora contraddice l’Esercizio 7.13.L’unicita di x in (ii) e in (iii) segue dalla Legge di Cancellazione.

Fissato ora n ∈ N , dimostriamo l’enunciato principale per induzione su m. Consideriamol’insieme

K = {k ∈ N : (i), o (ii), o (iii) vale per m = k}

0 ∈ K perche, se n 6= 0 (e quindi (i) non vale), allora e verificata la (ii) con x = n.Supposto k ∈ K, possiamo distinguere tre casi.

1) n = k. Allora σk = σn = σf+(n, 0) = f+(n, σ0) e (iii) vale per σk.

30

2) ∃x 6= 0 : n = f+(k, x). Poiche x 6= 0, possiamo considerare σ−1x. Abbiamo quindin = f+(k, σσ−1x) = f+(σk, σ−1x) (Proposizione 7.10). Se σ−1x = 0, allora n = σk e (i) everificata da σk. Altrimenti e verificata (ii).

3) ∃x 6= 0 : k = f+(n, x). In questo caso abbiamo σk = f+(n, σx) e quindi (iii) e verificataanche da σk.

D’ora in avanti scriveremo n+m anziche f+(n,m).

7.3 Prodotto di naturali

Anche per il prodotto si usera il Teorema 7.7, tenendo presente che possiamo usare lafunzione somma che abbiamo gia definito. Con riferimento alla notazione di quel teorema,poniamo h(n) = 0 per ogni n, e g(n,m) = n+m. Ottenendo in questo modo la definizionedi f×:

(1) f×(n, 0) = 0

(2) f×(n, σ(m)) = n+ f×(n,m)(7.10)

Proposizione 7.15 [Distributivita di ×] La funzione f× e distributiva rispetto a +.

Dimostrazione. Dimostriamo prima la distributivita a sinistra: per ogni n, m, k, f×(n,m+k) = f×(n,m) + f×(n, k). Per k = 0 abbiamo f×(n,m + 0) = f×(n,m) = f×(n,m) +f×(n, 0). Supposta la precedente uguaglianza vera per k, abbiamo f×(n,m + σk) =

f×(n, σ(m+ k)) = f×(n,m+ k) + ni.i= f×(n,m) + f×(n, k) + n = f×(n,m) + f×(n, σk).

Per la distributivita a destra dobbiamo dimostrare f×(n+m, k) = f×(n, k)+f×(m, k). Perk = 0 abbiamo: f×(n+m, 0) = 0 = f×(n, 0)+f×(m, 0). Per σk abbiamo: f×(n+m,σk) =

f×(n+m, k) + n+mi.i= f×(n, k) + f×(m, k) + n+m = f×(n, σk) + f×(m,σk).

Lemma 7.16 Per ogni n ∈ N , f×(n, 0) = f×(0, n) = 0 e f×(n, σ0) = f×(σ0, n) = n.

Dimostrazione. Dalla definizione di f× abbiamo f×(n, 0) = 0. L’uguaglianza f×(0, n) vale

banalmente per n = 0, supposta vera per n, abbiamo: f×(0, σn) = f×(0, n) + 0i.i= 0.

Dalla definizione di f× abbiamo f×(n, σ0) = f×(n, 0)+n = n. L’uguaglianza f×(σ0, n) = n

vale banalmente per n = 0. Supposta vera per n, abbiamo: f×(σ0, σn) = f×(σ0, n)+σ0i.i=

n+ σ0 = σn.

Proposizione 7.17 [Commutativita di ×] Per ogni n, m, f×(n,m) = f×(m,n).

Dimostrazione. Per induzione su m. Il caso m = 0 e stato dimostrato nel lemma preceden-

te. Supposta la commutativita verificata per m, abbiamo: f×(n, σm) = f×(n,m) + ni.i=

f×(m,n) + n = (per il lemma precedente) f×(m,n) + f×(σ0, n) = (per associativita)f×(m+ σ0, n) = f×(σm, n).

Esercizio 7.18 [Associativita di ×] Per ogni n, m, k, f×(n, f×(m, k)) = f×(f×(n,m), k).

31

Esercizio 7.19 Dimostrare che f×(n,m) = 0 se e solo se n = 0 oppure m = 0.

Proposizione 7.20 [Cancellazione per ×] Se k 6= 0 e f×(n, k) = f×(m, k) allora n = m.

Dimostrazione. Supponiamo n 6= m. Per la Proposizione 7.14, esiste x 6= 0 tale chen = m + x oppure m = n + x. Nel primo caso (l’altro e identico) abbiamo: f×(n, k) =f×(m+ x, k) = f×(m, k) + f×(x, k) 6= f×(m, k) essendo x 6= 0 e k 6= 0.

D’ora in avanti scriveremo n ·m o nm al posto di f×(n,m).

7.4 Ordinamento dei naturali

Una volta definita la somma di naturali e dimostrate le sue proprieta, la relazione d’ordinesu N puo essere semplicemente definita da

n ≤ mdef≡ ∃k : n+ k = m (7.11)

Come al solito si scrivera n < m per n ≤ m e n 6= m.

Esercizio 7.21 Dimostrare che n < m se e solo se ∃k 6= 0 : n+ k = m.

Proposizione 7.22 La relazione ≤ e riflessiva, totale, antisimmetrica e transitiva. Inol-tre, per ogni coppia di naturali n e m di naturali, vale una ed una sola delle seguentirelazioni: n < m, m < n, n = m (tricotomia di <).

Dimostrazione. Le prime proprieta seguono immediatamente dalla definizione di ≤, dallaProposizione 7.14 e dall’associativita della somma. La tricotomia segue dalla Proposizio-ne 7.14 assieme all’Esercizio 7.21.

Proposizione 7.23 Per ogni coppia di naturali n, m,

(i) 0 ≤ n e n 6< 0

(ii) n < σm se e solo se n ≤ m

(iii) σn ≤ m se e solo se n < m

(iv) n < σn e σn 6≤ n

(v) non esiste nessun k tale che n < k < σn

(7.12)

Dimostrazione. (i) segue dalla definizione di ≤ e dalla tricotomia di <.

(ii). Se n + k = σm e k 6= 0, allora σ−1k esiste e abbiamo: n + σσ−1k = σm ⇒σ(n+σ−1k) = σm ⇒ n+σ−1k = m ⇒ n ≤ m. Inversamente, n+k = m ⇒ n+σk =σm ⇒ n < σm perche σk 6= 0.

(iii). Da σn + k = m segue n + σk = m e n < m. Inversamente, se n + k = m e k 6= 0,allora n+ σσ−1k = m e σn+ σ−1k = m, cioe σn ≤ m.

(iv). La prima disuguaglianza segue da: n + σ0 = σn + 0 = σn. La seconda segue dallaprima per tricotomia.

(v). Se k < σn, per (ii) abbiamo k ≤ n e quindi non puo essere n < k.

32

Esercizio 7.24 Dimostrare che la relazione d’ordine sui naturali e compatibile con som-ma e prodotto.

Definizione 7.25 Sia ≺ una relazione binaria sull’insieme S. Diciamo che 〈S,≺〉 e unbuon ordinamento (o che ≺ bene ordina S) se ≺ e un ordine stretto e ogni sottoinsiemenon vuoto di S ha minimo.

Osserviamo che un buon ordinamento e anche un ordine lineare. Dati infatti due elementidistinti x1 e x2 di X, l’insieme {x1, x2} ha minimo, e quindi x1 ≺ x2, oppure x2 ≺ x1.

Esercizio 7.26 Dimostrare che se 〈S,≺〉 e un buon ordinamento e S ′ ⊆ S allora anche〈S ′,≺〉 e un buon ordinamento.

Esercizio 7.27 Dimostrare che l’ordine totale stretto 〈S,≺〉 e un buon ordinamento se esolo se non esistono catene discendenti infinite, cioe successioni s0 � s1 � · · · � sn � . . . .

Esercizio 7.28 Siano 〈S1,≺1〉 e 〈S2,≺2〉 buoni ordinamenti e sia S1∩S2 = ∅. Sia 〈S,≺〉la struttura in cui S = S1 ∪ S2 e

s ≺ s′ se e solo se s, s′ ∈ S1 e s ≺1 s′

oppure s, s′ ∈ S2 e s ≺2 s′

oppure s ∈ S1 e s′ ∈ S2

Dimostrare che 〈S,≺〉 e un buon ordinamento.

Teorema 7.29 La coppia 〈N,<〉 e un buon ordinamento.

Dimostrazione. Supponiamo per assurdo che il sottoinsieme non vuoto A di N non abbiaminimo. Poniamo

K = {n ∈ N : n < m per ogni m ∈ A}

0 ∈ K. Infatti 0 ≤ m per ogni naturale m e 0 6∈ A, altrimenti 0 sarebbe il minimo di A.

Supponiamo ora n ∈ K, cioe n < m per ogni m in A. Per il punto (iii) della Proposizio-ne 7.23, abbiamo σn ≤ m per ogni m in A, da cui segue σn < m per ogni m in A perchealtrimenti σn sarebbe il minimo di A. Dunque σn ∈ K e K = N . Per concludere bastaora osservare che K ∩ A = ∅ (altrimenti avremmo m < m per qualche m in A) e quindiA = ∅.

Il fatto che N sia bene ordinato da < e di fatto equivalente al Principio di Induzione (v.Teorema 7.32). Un’ulteriore formulazione dello stesso principio viene fornita dal seguenteteorema.

Teorema 7.30 Nella struttura dei numeri naturali vale

PI′ ∀X ⊆ N [∀n (∀m < n (m ∈ X)→ n ∈ X)→ X = N ]

33

Dimostrazione. Sia X un sottoinsieme di N tale che n ∈ X ogniqualvolta m ∈ X per ognim < n. Se X 6= N , allora N \X e non vuoto e quindi possiamo considerarne il minimon0. A questo punto possiamo arrivare ad una contraddizione osservando che ogni m < n0

appartiene ad X e che quindi per le ipotesi su X anche n0 vi appartiene.

In PI′ sembra mancare il passo iniziale 0 ∈ X che compare invece in PI. Tale mancanzae tuttavia solo apparente. Per n = 0 infatti la formula ∀m < 0(m ∈ X) e banalmenteverificata (perche non esistono m < 0) e quindi 0 ∈ X.

Dato un ordine stretto ≺ sull’insieme S e due elementi s e s′ di S, diciamo che s′ e unimmediato successore di s, o che s e un immediato predecessore di s′ se s ≺ s′ e non esistes′′, tale che s ≺ s′′ ≺ s′.

Lemma 7.31 Sia 〈S,≺〉 un buon ordinamento e sia s ∈ S. (1) Se esiste x tale che s ≺ x,allora s ha un unico immediato successore; (2) s ha al piu un immediato predecessore.

Dimostrazione. (1) Consideriamo l’insieme {x ∈ S : s ≺ x}. Per le ipotesi su s questoinsieme non e vuoto e quindi ha minimo s0. Dalla linearita di ≺ segue che s0 e l’unicoimmediato successore di s. (2) Siano s1 e s2 immediati predecessori di s. Dall’ipotesis1 6= s2 possiamo arrivare ad un assurdo usando ancora la linearita di ≺.

In base a questo lemma, in ogni buon ordinamento 〈S,≺〉 possiamo definire la funzioneσ≺ che ad ogni s ∈ S associa il suo immediato successore, se questo esiste. Il seguenteteorema mostra che la funzione σ≺ si comporta come la funzione σ nei modelli degliassiomi di Peano.

Teorema 7.32 Sia 〈S,≺〉 un buon ordinamento e sia s0 il minimo di S. Supponiamoinoltre che ogni elemento di S abbia immediato successore e che s0 sia l’unico elementodi S che non ha immediato predecessore. Allora 〈S, s0, σ≺〉 e un modello degli Assiomi diPeano.

Dimostrazione. Dalla minimalita di s0 segue che l’assioma N1 e verificato. L’assioma N2segue dall’unicita dell’immediato predecessore (Lemma 7.31).

Sia ora K un sottoinsieme di S tale che s0 ∈ K e σ≺s ∈ K ogniqualvolta s ∈ K.Supponiamo per assurdo K 6= S, da cui segue che X = S \ K non e vuoto, e quindipossiamo considerarne il minimo s∗. s∗ e diverso da s0 perche s0 ∈ K e quindi s∗ ha unimmediato predecessore s′ che appartiene a K per la minimalita di s0. Ma dalle proprietadi K segue s∗ = σ≺s

′ ∈ K che contraddice s∗ ∈ X. Quindi anche PI e verificato.

Questo teorema mostra come i numeri naturali possano anche essere descritti come uninsieme bene ordinato 〈S,≺〉 in cui ogni elemento ha immediato successore e il minimodi S e l’unico elemento senza immediato predecessore. Il seguente teorema mostra diconseguenza come si possa caratterizzare i naturali partendo da un ordine lineare strettoin cui valga la versione PI′ del Principio di Induzione.

Teorema 7.33 Sia 〈S,≺〉 un ordine lineare stretto che verifica PI′. Allora 〈S,≺〉 e unbuon ordinamento.

34

Dimostrazione. Supponiamo per assurdo che il sottoinsieme non vuoto A di S non abbiaminimo. Sia X = S \ A. Mostriamo che X verifica l’antecedente di PI′. Dato s ∈ S,supponiamo s′ ∈ X per ogni s′ ≺ s. Dalla linearita di ≺ segue s � s′′ per ogni s′′ ∈ A.Poiche A non ha minimo, abbiamo s 6∈ A, e quindi s ∈ X. Per PI′ possiamo concludereX = S che contraddice le ipotesi A 6= ∅.

7.5 Altre formulazioni degli Assiomi di Peano

Gli Assiomi di Peano che abbiamo visto precedentemente soddisfano ad un principio di‘economia’ di nozioni primitive nel senso che sono formulati in un linguaggio minimo cheusa esclusivamente le nozioni di numero 0 e di successore. Una volta dimostrato che conquelle nozioni, e i tre assiomi, possiamo definire le usuali operazioni e relazione d’ordi-ne, possiamo considerare nuove assiomatizzazioni. Possiamo cioe considerare strutture〈N, 0, σ,+, ·,≤〉 in cui valgano i seguenti assiomi.

(N1) ∀n (σn 6= 0)

(N2) ∀n,m (σn = σm→ n = m)

(N3) ∀n (n+ 0 = n)

(N4) ∀n,m ((n+ σm) = σ(n+m))

(N5) ∀n (n · 0 = 0)

(N6) ∀n,m (n · σm = n+ n ·m)

(N7) ∀n,m (n ≤ m↔ ∃k(n+ k = m))

(PI) ∀X ⊆ N [(0 ∈ X ∧ ∀k (k ∈ X → σk ∈ X))→ X = N ]

Ovviamente questa assiomatizzazione e ridondante, nel senso che abbiamo visto preceden-temente come somma, prodotto e relazione d’ordine possano essere definite usando esclu-sivamente la funzione successore. Nella pratica matematica conviene comunque spessotrascurare questioni di economia di principi in favore di una maggiore chiarezza espositi-va. E anche importante osservare che N3-N7 sono le stesse formule che abbiamo usatocome definizioni della somma, del prodotto, e della relazione d’ordine. E naturale chesia cosı: avendo nuove nozioni primitive (+, ·, ≤) abbiamo bisogno di nuovi assiomi chestabiliscano come queste nozioni siano collegate alle precedenti (0, σ), ed il collegamen-to e proprio quello precedentemente espresso dalle definizioni. Infine, i risultati del §7.4mostrano come avremmo potuto usare anche altre formulazioni del Principio di Induzione.

8 Aritmetica al primo ordine. Modelli non-standard

Il Principio di Induzione e una formula del secondo ordine perche in essa si quantifica suinsiemi. In questa sezione considereremo la possibilita di sostituire questo principio con

35

formule del primo ordine. In questo modo si ottiene una teoria del primo ordine perchetutti gli altri assiomi, diversi da Principio di Induzione, sono formule le primo ordine.Conviene chiarire immediatamente che la teoria ottenuta in questo modo non puo averele stesse proprieta dalla precedente. La differenza piu evidente e che la prima e categorica(Teorema 7.5), mentre, in base al Teorema di Lowenheim-Skolem, ogni teoria del primoordine con un modello infinito non puo essere categorica. La nozione di α-categoricita,tuttavia, porta a chiedersi se non possano essere isomorfi i modelli di una fissata cardinalitadi una teoria del primo ordine dei numeri naturali. In particolare risulteranno interessantii modelli numerabili, per cui il problema riguarda l’eventuale ℵ0-categoricita di quellateoria. Anche in questo caso la risposta e negativa, e la dimostrazione (che non puobasarsi sul Teorema di Lowenheim-Skolem) usa una costruzione ad hoc ed il Teorema diCompattezza Semantica.

Abbiamo gia osservato (Osservazione 2.11) che, in una data interpretazione, una formulain cui tutte le variabili sono vincolate (enunciato) puo essere vera oppure falsa, mentrela verita di formule con qualche variabile libera in generale dipende dal valore assegnatoa tale variabile. Data quindi un’interpretazione 〈D, I〉 per un dato linguaggio L ed unaformula ϕ(x) di L in cui x sia l’unica variabile libera, possiamo considerare l’insiemeXϕ(x) costituito da tutti gli elementi d di D che rendono vera ϕ(x) quando ad x vengaassegnato il valore d. Come casi limite abbiamo Xx=x = D e Xx 6=x = ∅. Applicandole precedenti considerazioni alla struttura 〈N, 0, σ,+, ·,≤〉, abbiamo per esempio che, seϕ(x) e ∃n(n+n = x) allora Xϕ(x) e l’insieme dei numeri pari, mentre, per ϕ(x) = ∃n(x =n · σσσ0), Xϕ(x) e l’insieme dei multipli di 3. D’ora in avanti ci riferiremo esclusivamentea strutture 〈N, 0, σ,+, ·,≤〉, e quindi le formule ϕ saranno formule del linguaggio, cheindicheremo con L1

N, per queste strutture.

La singola istanza del Principio di Induzione relativa all’insieme Xϕ(x) puo essere espressadalla formula

PIϕ(x) (ϕ(0) ∧ ∀k(ϕ(k)→ ϕ(σk))) → ∀nϕ(n)

che puo essere letta come: se la formula ϕ(x) e verificata da x = 019 ed e verificata perx = σk ogniqualvolta e verificata per x = k, allora ϕ(x) e verificata da ogni numeronaturale.

Un’assiomatizzazione al primo ordine dell’aritmetica puo dunque consistere degli assiomi(del primo ordine) N1-7 del §7.5 e di tutte le formule del tipo PIϕ(x), dove ϕ(x) e unaformula del primo ordine del linguaggio per 〈N, 0, σ,+, ·,≤〉 in cui x e l’unica variabilelibera. Si osservi che con queste ipotesi ogni istanza di PIϕ(x) e un enunciato.20 In questocaso quindi la teoria assiomatica include uno schema d’assiomi, cioe un insieme infinito dienunciati aventi tutti la stessa forma. Possiamo dunque dire che gli assiomi dell’aritmeticaal primo ordine sono N1-7 e

SI (Schema d’Induzione) {PIϕ(x) : ϕ(x) e una formula di L1N}

19Questo e un modo semplice per dire che ϕ(x) e verificata quando a x viene assegnato il valore 0.20Talvolta incontriamo anche formulazioni di PIϕ(x) in cui ϕ contiene altre variabili libere ol-

tre ad x, in cui cioe scriviamo questa formula come ϕ(x, y1, . . . , yn). In tal caso PIϕ(x) diventa∀y1, . . . , yn[(ϕ(0, y1, . . . , yn) ∧ ∀k(ϕ(k, y1, . . . , yn)→ ϕ(σk, y1, . . . , yn))) → ∀nϕ(n, y1, . . . , yn)].

36

Indicheremo con T 1N la teoria avente come assiomi N1-7 e tutte le istanze di SI.

Gli insiemi del tipo Xϕ(x) vengono chiamati insiemi definibili. Lo schema SI esprime

quindi tutte le istanze dl Principio di Induzione relative ad insiemi definibili. E abbastanzafacile convincersi, in base alla seguente proposizione, che il Principio di Induzione alsecondo ordine e piu espressivo di questo schema di assiomi.

Proposizione 8.1 Per ogni modello 〈N, 0, σ,+, ·,≤〉 di T 1N , l’insieme {X : X ⊆ N} e

piu che numerabile, mentre l’insieme {X : X = Xϕ(x) per qualche formula ϕ(x) di L1N }

e numerabile.

Dimostrazione. Per dimostrare la prima parte dell’enunciato, mostriamo che N ha unsottoinsieme infinito e che quindi N stesso e infinito. Sia N0 l’insieme {0, σ0, σσ0 . . . },cioe l’intersezione di tutti i sottoinsiemi di N che contengono 0 e sono chiusi per la funzioneσ. L’immagine σ[N0] di N0 tramite σ e ovviamente contenuta in N0 e, per N2, σ e unabiiezione tra N0 e σ[N0]. Per N1, σ[N0] e un sottoinsieme proprio di N0 perche 0 6∈ σ[N0].Abbiamo quindi che N0 e equipotente ad un suo sottoinsieme proprio e quindi e infinito.21

Da cio segue che card(N) ≥ card(N) e quindi card({X : X ⊆ N}) ≥ card(℘N).

Per la seconda parte dell’enunciato basta osservare che l’insieme delle formule ϕ(x) enumerabile. Infatti, ogni formula di questo tipo e una successione finita di elementi dellinguaggio L1

N che e numerabile, e l’insieme di tutte le successioni finite ad elementi inun insieme numerabile e pure numerabile (v. App. B). Risulta quindi numerabile anchel’insieme di tutti i sottoinsiemi definibili di N .22

Il fatto che SI sia piu debole di PI ha effettivamente conseguenze sull’insieme delle fun-zioni che risultano definibili nei modelli di T 1

N . A differenza di quanto abbiamo fatto nellesezioni precedenti, avendo solo SI non possiamo usare il Principio di Induzione con insiemiarbitrai di naturali, ma solo con quelli definibili da formule del primo ordine. Per approfon-dire questo argomento si puo vedere per esempio [Boolos and Jeffrey, 1980]. Nel seguitoconsidereremo il problema da un altro punto di vista, concentrandoci prevalentementesulla relazione d’ordine, e considerando i possibili modelli di T 1

N .

D’ora in avanti, N0 = 〈N0, 0, σ,+, ·,≤〉 indichera un (o meglio, il) modello di TN. Chia-meremo questa struttura il modello standard degli Assiomi di Peano. Poiche ogni assiomadi T 1

N puo essere dedotto dagli assiomi di TN, N0 sara anche modello dell’aritmetica alprimo ordine. Sia Φ0 l’insieme definito da

Φ0 = {ϕ : ϕ e un enunciato di L1N vero in N0} (8.13)

Notazione. Fino a questo punto abbiamo usato gli stessi simboli (0, σ, n, m . . . ) perindicare sia i simboli del linguaggio sia gli elementi dell’interpretazione (v. Osservazio-ne 7.1). Ora invece conviene sottolineare anche formalmente la differenza tra i due aspetti.

21E importante osservare che abbiamo dimostrato solo che N0 e contenuto in N . Come vedremo piuavanti la dimostrazione dell’uguaglianza N0 = N richiede il principio di induzione nella forma forte PI.Esistono infatti modelli di T 1

N in cui N0 e contenuto propriamente in N .22Questo insieme e ovviamente infinito. Ogni insieme costituito dal singolo numero naturale k, per

esempio, viene definito da x = σ . . . σ0, dove σ viene applicato k volte.

37

Manterremo quindi gli stessi simboli per l’interpretazione, ma per il linguaggio useremosimboli diversi (piu vicini al formalismo logico). Il linguaggio L1

N avra quindi il simboloper costante c0 (che verra interpretato in 0), il simbolo per funzione unaria hσ (che verrainterpretato in σ). Avranno pure le ovvie interpretazioni i simboli per funzioni binarieh+ e h×, e il simbolo per relazioni binaria R≤ . Per non confondere gli elementi delleinterpretazioni di L1

N con le variabili di questo linguaggio, indicheremo queste ultime conv, w, v1, . . . , anziche con n, m . . . come abbiamo fatto finora.

Consideriamo ora il linguaggio L∗N ottenuto aggiungendo una nuova costante, c, ad L1N;

nelle formule di L∗N abbiamo quindi che, oltre a c0 ed alle varibili, puo comparire anche ccome termine elementare. Per ogni naturale n ∈ N0, scriveremo n per indicare il terminehσ . . . hσc0 dove hσ e ripetuto n volte. L’espressione n, che viene chiamata numerale, edunque un termine del linguaggio, la cui interpretazione in N0 e σ . . . σ0, cioe il numeron.

Sia Φ∗0 l’insieme di formule di L∗N definito da

Φ∗0 = Φ0 ∪ {m 6= c : m ∈ N0} (8.14)

Ogni sottoinsieme finito Φ di Φ∗0 e costituito da formule di Φ0, che sono vere in N0, e daun insieme finito di formule del tipo m 6= c : {m1 6= c, . . . ,mk 6= c}. Il modello standardN0 diventa quindi anche modello di Φ: basta interpretare c in un numero naturale chenon compare in {m1, . . . ,mk}. Per il Teorema di Compattezza, possiamo concludere cheanche Φ∗0 ha modello. Tenendo presente che il linguaggio L∗N e numerabile, per il Teoremadi Lowenheim-Skolem possiamo anche concludere che Φ∗0 ha modello numerabile. SiaN ∗ = 〈N∗, c∗, 0∗, σ∗,+∗, ·∗,≤∗〉 un tale modello che rimarra fissato fino alla fine di questasezione. Si osservi che in tale modello deve anche comparire l’interpretazione c∗ dellacostante c.

Osservazione 8.2 N ∗ e un modello di T 1N perche Φ0 contiene tutti i teoremi di questa

teoria. Ci possiamo chiedere se in N ∗ siano vere anche tutte le istanze di PIϕ(v,c), doveϕ(v, c) e una formula, con v variabile libera, che contiene la costante c, e dunque nonappartiene a Φ0. La risposta e positiva.

Sia w una variabile che non compare in ϕ(v, c), e consideriamo la formula ϕ(v, w) ottenutasostituendo c con w in ϕ(v, c). La formula

ψ = ∀w[ (ϕ(c0, w) ∧ ∀v(ϕ(v, w)→ ϕ(hσv, w)))→ ∀vϕ(v, w) ]

e vera in N0. Infatti ψ asserisce che, per ogni naturale n0, vale il Principio di Induzioneper l’insieme dei k ∈ N0 tali che ϕ(v, w) e verificata assegnando rispettivamente k e n0 av e w. Quindi ψ appartiene a Φ0 ed e vera anche in N ∗. Per una elementare legge logicarisulta vera in N ∗ anche la formula

(ϕ(c0, c) ∧ ∀v(ϕ(v, c)→ ϕ(hσv, c)))→ ∀vϕ(v, c)

che e proprio PIϕ(v,c).

38

Sia ora f : N0 → N∗ la funzione definita da:

f(0) = 0∗ , f(σn) = σ∗f(n) (8.15)

Lemma 8.3 La funzione f definita in (8.15) e iniettiva.

Dimostrazione. Consideriamo la seconda parte della dimostrazione del Teorema 7.5. Inquella parte viene usato PI in N e la validita dell’Assioma N2 in N ′. Basta quindiosservare che le strutture N0 e N ∗ verificano rispettivamente PI e N2.

L’immagine Im(f) di f e costituita dagli elementi di N∗ della forma σ∗ . . . σ∗0∗ che sonole interpretazioni dei termini della forma m. L’elemento c∗ di N∗ non puo appartenerea Im(f) perche in N ∗ sono verificate tutte le disuguaglianze del tipo m 6= c, e dunquel’immersione f e propria.

Corollario 8.4 Il sottoinsieme Im(f) di N∗ non e definibile.

Dimostrazione. Se Im(f) fosse definibile dalla formula ϕ(v), allora, per PIϕ(v), avremmoIm(f) = N∗.

Basta ora tenere presente che ogni eventuale isomorfismo tra N0 e N ∗ deve avere le pro-prieta di f per concludere che questi due modelli di T 1

N non sono isomorfi. I modelli di T 1N

che, come N ∗, non sono isomorfi a N0 sono chiamati modelli non-standard dell’aritmetica.Poiche N ∗ e numerabile abbiamo che esistono modelli non standard numerabili e quindivale il seguente teorema.

Teorema 8.5 La teoria T 1N non e ℵ0-categorica.

Possiamo ora studiare alcune proprieta del modello non standard N ∗. La tecnica usatasara sostanzialmente sempre la stessa: poiche N ∗ e modello anche di Φ0, per (8.13)ogni formula del primo ordine vera nel modello standard dovra essere vera anche in N ∗.Questo permettera di ricavare altre proprieta di questa struttura. Conviene chiamarenaturali standard gli elementi di Im(f) e naturali non standard gli elementi di N∗ \ Im(f).Useremo le lettere m,n, k, . . . per indicare i naturali standard, le lettere a, b, c, . . . per inaturali non standard, e le lettere x, y, z, . . . per arbitrari elementi di N∗. L’elemento c∗

di N∗ e un naturale non standard.

Proposizione 8.6 Siano n,m, a ∈ N∗, dove n e m sono standard, e a e non standard.Allora

(a) n+∗ m e un naturale standard;

(b) esiste un naturale standard k tale che n+∗ k = m oppure m+∗ k = n;

(c) se x ≤∗ n, allora x e un naturale standard;

(d) n <∗ a;

39

(e) a+∗ x e non standard per ogni x ∈ N∗;(f) se x+∗ n = a, allora x e non standard;

(g) per ogni x ∈ N∗ e ogni naturale k, (σ∗)k(x) 6= x.

Dimostrazione. (a) Se n e m sono naturali standard, allora essi sono l’interpretazione inN ∗ dei numerali n e m. La formula h+(n,m) = n+m appartiene a Φ0, quindi e verain N ∗, ma l’interpretazione di h+(n,m) in N ∗ e proprio n +∗ m che quindi coincide conl’interpretazione di n+m che e un naturale standard.

(b) Supponiamo n ≤∗ m. Quindi, nel modello standard, n ≤ m ed esiste un naturale ktale che n + k = m. La formula h+(n, k) = m appartiene dunque a Φ0 ed e vera in N ∗.Possiamo ora ragionare come nel caso precedente.

(c) Consideriamo la formula del primo ordine ∀v(R≤(v, n)→ (v = 0∨v = 1∨· · ·∨v = n))che e vera in N0 e quindi anche in N ∗. Poiche stiamo supponendo che in N ∗ sia verox ≤∗ n, cioe la formula R≤(v, n) quando v viene interpretata in x, abbiamo che in N ∗deve essere vera anche una delle formule v = k (con k ≤ n) quando v viene interpretatain x. Ma cio significa che x e standard.

(d) segue da (c) tenendo presente per la tricotomia della relazione <∗ (che viene espressada una formula del primo ordine che appartiene a Φ0).

(e) Osserviamo che, se a +∗ x fosse standard allora a sarebbe minore o uguale a qualchenaturale standard, contro (d).

(f) segue da (a).

Per (g), basta osservare che la formula ∀v(hσhσ . . . hσv 6= v) appartiene a Φ0 per ogniiterazione finita hσhσ . . . hσ di hσ.

In base alle proprieta appena considerate possiamo abbozzare una prima rappresentazioneparziale di N ∗ nella Figura 1.

Figura 1

q q q q q . . . . . .0∗

Im(f)

qc∗

Il fatto che ogni naturale abbia un unico successore e che ogni elemento di N∗ diverso da0∗ abbia un unico predecessore viene espresso da formule del primo ordine (Esercizio).La struttura N ∗ conterra quindi σ∗c∗ e σ∗−1c∗. Ovviamente σ∗ puo essere applicataanche a σ∗c∗ per cui possiamo iterare l’applicazione di σ∗ un arbitrario numero finito divolte. Anche l’applicazione di σ∗−1 puo essere iterata perche, per la proprieta (f) nellaProposizione 8.6, il predecessore di ogni naturale non standard e ancora un naturale nonstandard e quindi in particolare e diverso da 0∗. Infine, per (g) nella Proposizione 8.6, nonesistono σ∗-cicli. Possiamo dunque associare a c∗ un insieme Zc∗ di naturali non standardche, come insieme ordinato, e isomorfo all’insieme Z degli interi. Dalle considerazioniprecedenti segue anche Im(f) ∩ Zc = ∅. La Figura 2 e una rappresentazione di N ∗ piuprecisa della Figura 1, seppure ancora parziale.

40

Figura 2

q q q q q . . . . . .0∗

Im(f)

q q q . . .qq. . .

Zc∗

Ogni naturale puo essere raddoppiato: cio corrisponde alla formula ∀v ∃w (w = h+(v, v)).Possiamo quindi considerare il naturale (non standard, perche maggiore di c∗) uguale ac∗ +∗ c∗ e che possiamo chiamare 2c∗. In base a successive applicazioni di σ∗ e σ∗−1 a 2c∗

possiamo considerare anche la copia Z2c∗ di Z in N∗.

Lemma 8.7 Zc∗ ∩ Z2c∗ = ∅.

Dimostrazione. Ogni elemento x di Zc∗ puo essere scritto nella forma (σ∗)kc∗ o nellaforma (σ∗−1)kc∗, per un opportuno k, e analogamente per gli elementi di Z2c∗ . Se, perassurdo, x ∈ Zc∗ ∩ Z2c∗ , combinando opportunamente le espressioni di x del tipo vistosopra, ricaviamo che, essendo c∗ <∗ 2c∗, esiste un naturale standard m tale che c∗+∗ c∗ =(σ∗)mc∗. Ogni formula della forma ∀v, w(w = (hσ)m(v) → h+(v,m) = w) e vera in N0 equindi in N ∗. Se v e w vengono interpretati rispettivamente in c∗ e (σ∗)mc∗, otteniamoc∗ +∗ c∗ = (σ∗)mc∗ = c∗ +∗ (σ∗)m0∗, da cui segue c∗ = (σ∗)m0∗ (osservando che la Leggedi Cancellazione viene espressa da una formula del primo ordine). Ma cio contraddice ilfatto che c∗ sia non standard.

E chiaro a questo punto che N ∗ contiene infinite copie di Z a due a due disgiunte. Dalladimostrazione del lemma precedente abbiamo inoltre il seguente risultato.

Corollario 8.8 Dati due naturali non standard a e b in N∗, essi appartengono ad unastessa copia di Z se e solo se esiste un naturale standard n tale che a = n +∗ b oppureb = n+∗ a.

Detta Za la copia di Z che contiene a, possiamo definire in modo naturale una relazioned’ordine stretto sull’insieme degli Za ponendo

Za ≺ Zb se solo se Za 6= Zb e a <∗ b

Per quanto visto finora, l’insieme degli Za non ha massimo. Per verificare che non haneanche minimo basta considerare la formula

∀v ∃w (h+(w,w) = v ∨ h+(w,w) = hσ(v))

che asserisce che ogni numero naturale o il suo successore puo essere diviso per due. Questaformula e ovviamente vera nel modello standard, e quindi anche in N ∗. Esiste quindi unelemento di N∗, che possiamo indicare con c∗

2, tale che c∗

2+ c∗

2= c∗ oppure c∗

2+ c∗

2= σ∗c∗.

Con una dimostrazione simile a quella del Lemma 8.7, possiamo concludere che c∗

2e un

numero naturale non standard e che la corrispondente copia di Z non interseca Zc∗ (v.Figura 3).

41

Figura 3

q q q q q . . . . . .0

Im(f)

q q q . . .qq. . .

Z c∗2

q q q . . .qq. . .

Zc∗

q q q . . .qq. . .

Z2c∗

Infine, possiamo considerare la formula che esprime l’esistenza della ‘media’ di due numeriinteri:

∀v1, v2,∃w(h+(w,w) = h+(v1, v2) ∨ h+(w,w) = hσ(h+(v1, v2)))

dove, come nel caso della divisione per due, abbiamo dovuto tener presente che la sommadei due numeri potrebbe essere dispari. Questa formula e vera in N0 e dunque anche inN ∗. Dati quindi i naturali non standard a e b, possiamo considerare l’elemento di N∗

la cui esistenza viene stabilita dalla precedente formula quando v1 e v2 vengono interpre-tate rispettivamente in a e b. Possiamo indicare tale elemento con a+b

2e considerare la

corrispondente copia di Z.

Esercizio 8.9 Dimostrare che, per ogni coppia a e b di naturali non standard, se Za = Zballora Za+b

2= Za, mentre, se Za ≺ Zb allora Za ≺ Za+b

2≺ Zb

Questo risultato conclude lo studio della struttura di N ∗ come insieme ordinato. Oltread una parte iniziale (Im(f)) isomorfa a N0, N ∗ contiene infinite copie Za di Z sullequali e possibile definire una relazione d’ordine stretto. Questo ordine e senza massimo,senza minimo e denso e quindi, essendo la struttura numerabile, e isomorfo all’ordine deirazionali.

8.1 Linguaggi ridotti

Possiamo ora tornare ad usare gli stessi simboli 0, σ,+, . . . sia nel linguaggio, sia nell’in-terpretazione. Nella prima parte di questa sezione abbiamo considerato un linguaggiodel primo ordine con tutti i simboli dell’aritmetica. Puo essere interessante esaminarelinguaggi ridotti. In particolare considereremo un linguaggio del primo ordine L1

N,σ, conla costante 0 e il solo simbolo di successore.23 Questi simboli erano sufficienti per definiresomma, prodotto e relazione d’ordine nella teoria al secondo ordine. Si dimostrera che cionon e possibile con la capacita espressiva molto ridotta dei linguaggi del primo ordine.

Cominciamo col considerare un sistema di assiomi per un’opportuna teoria basata su L1N,σ.

Dopo i primi tre, abbiamo una successione infinita di assiomi, uno schema di assiomi.

A1 ∀n(0 6= σn)

A2 ∀m,n(σm = σn→ m = n)

A3 ∀n(n 6= 0→ ∃m(n = σm))

23Altre sottoteorie del linguaggio per l’aritmetica, assieme a quella considerata in questa sezione, sonoconsiderate nelle sezioni 3.1 e 3.2 di [Enderton, 1972].

42

A4.k ∀n(n 6= σkn) (k ∈ N+0 )

Indichiamo con T 1N,σ la teoria basata su questi assiomi. Ogni assioma (e quindi ogni

teorema) di questa teoria e vero nella struttura N0 che tuttavia non e l’unico suo modello.Come nella parte precedente di questa sezione possiamo considerare modelli in cui esistonoelementi a 6∈ N0. Chiamiamo ancora numeri non-standard questi nuovi elementi.

Proposizione 8.10 I modelli della teoria T 1N,σ sono tutte e solo le strutture N ∗ = 〈N∗, 0, σ〉

in cui: (1) N∗ = N ∪⋃i∈I Zi; (2) 〈N, σ〉 e isomorfo alla struttura 〈N0, σ〉 dei naturali

standard; (3) I e un insieme arbitrario di indici e ogni 〈Zi, σ〉 e isomorfo alla strutturadei numeri interi; (4) se i 6= j, Zi e Zj sono disgiunti.

Dimostrazione. Si verifica facilmente che ogni struttura descritta nell’enunciato e modellodi T 1

N,σ. In tali strutture infatti: (i) 0 non appartiene all’immagine di σ; (ii) σ e iniettiva;(iii) ogni elemento diverso da 0 appartiene all’immagine di σ; (iv) non esistono σ-cicli.

Supponiamo inversamente che 〈N∗, 0, σ〉 sia modello di T 1N,σ. Sia f la funzione da N0 in

N∗ definita da f(0) = 0 e f(σn) = σf(n). Per il Lemma 8.3, osservando che N2 e ancheassioma di T 1

N,σ, la funzione f e iniettiva. La funzione f conserva banalmente la funzioneσ e quindi, posto N = Im(f), 〈N, σ〉 e una sottostruttura di N ∗ isomorfa a 〈N0, σ〉.Se N = N∗, poniamo I = ∅. Altrimenti, sia a un elemento di N∗ \N . Per l’iniettivita diσ, anche σ−1 e una funzione (iniettiva), e possiamo considerare la chiusura Za di {a} perle operazioni σ e σ−1. Poiche N = {σk0 : k ∈ N} e Za = {σk(a) : k ∈ Z}, abbiamo cheZa∩N = ∅. Per lo stesso motivo, se anche b ∈ N∗ \N , allora Za = Zb oppure Za∩Zb = ∅.Osserviamo infine che, per A4, σka 6= σk

′a ogniqualvolta k 6= k′; non si sono cioe σ-cicli.

Ogni Za dunque e isomorfo a Z (come struttura dotata dell’operazione di successore).

In base a questo risultato c’e una stretta analogia tra i modelli di T 1N,σ e i modelli di

T 1N considerati nella sezione precedente. Osserviamo pero che il linguaggio che stiamo

considerando non contiene la relazione d’ordine ne la somma. Non viene quindi definitanessuna struttura d’ordine nell’insieme delle strutture Za. L’insieme di queste Z-catene earbitrario.

Per quanto riguarda l’indipendenza, gli assiomi A4.k meritano una discussione a parte.Osserviamo per esempio che A4.k e conseguenza di A4.2k. Se infatti per qualche n,n = σkn, allora vale anche n = σ2kn. In generale A4.k e conseguenza di A4.h per ognimultiplo h di k. La formulazione dell’indipendenza nella seguente proposizione assumequindi una forma particolare.

Proposizione 8.11 Gli assiomi A1-3 di T 1N,σ sono indipendenti, e per nessun valore di

k A4k e deducibile da A1-3, A4.1, . . . ,A4.k−1.

Dimostrazione. Per l’indipendenza di A1 basta considerare la struttura Z dei numeriinteri ed interpretare σ nell’usuale operazione di successore. In questo modo otteniamoun modello di A2, A3, e ogni A4.k in cui A1 non e verificata.

43

Per l’indipendenza di A2 consideriamo una struttura Z′ isomorfa a Z, unita allo 0. Indi-chiamo con k′ gli elementi di Z′, dove k ∈ Z. La funzione σ e l’usuale funzione successoresugli elementi di Z′, mentre σ(0) = 1′. In questo modo σ(0) = 1′ = σ(0′), e dunque σ none iniettiva. Gli assiomi diversi da A2 sono invece verificati.

Per A3 possiamo considerare la struttura costituita da N0 e da una sua copia N ′0. Lafunzione σ e l’usuale successore. In questo modo 0′ e un elemento diverso da 0 che nonha predecessore.

Per seconda parte dell’enunciato infine, dato k > 0, consideriamo una struttura costituitada N0 e da k nuovi elementi a1, . . . , ak. La funzione σ e l’usuale successore su N0, perh < k poniamo σah = ah+1, mentre σak = a1. Abbiamo cioe aggiunto a N0 un ‘ciclo’ dik elementi. In questa struttura sono verificati gli assiomi A1-3 e ogni A4h con h < k.Vale invece l’uguaglianza ai = σkai.

Corollario 8.12 L’insieme dei teoremi di T 1N,σ non e finitamente assiomatizzabile, non

esiste cioe nessun insieme finito di assiomi da cui siano deducibili tutti i teoremi di T 1N,σ.

Dimostrazione. Supponiamo per assurdo che esista una teoria T , con un insieme finito{B1, . . . , Bn} di assiomi (non necessariamente assiomi di T 1

N,σ), in grado di dimostraretutti i teoremi di T 1

N,σ.

Le due teorie sono cioe equivalenti, e quindi in particolare ogni assioma Bi sara teorema diT 1

N,σ. Poiche ogni dimostrazione coinvolge un numero finito di formule, possiamo indicarecon Ai,1, . . . , Ai,ki gli assiomi di T 1

N,σ coinvolti nella dimostrazione di Bi in questa teoria.Consideriamo la teoria T 1∗

N,σ avente come assiomi tutti gli Ai,j (1 ≤ i ≤ n, 1 ≤ j ≤ ki).

Tutti i teoremi di T (e quindi di T 1N,σ) sono anche teoremi di T 1∗

N,σ che ha un numero finitodi assiomi. Ma cio contraddice la Proposizione 8.11.

Sia N ∗ un modello di T 1N,σ. Per la Proposizione 8.10 possiamo porre N∗ = N ∪

⋃i∈I Zi,

dove ogni Zi e una Z-catena. Si α il cardinale dell’insieme I. Poiche ogni Zi e numerabile,possiamo concludere

|N ∗| =

{ℵ0 se α ≤ ℵ0

α altrimenti(8.16)

Proposizione 8.13 Se N1 e N2 sono modelli non numerabili di T 1N,σ ed hanno la stessa

cardinalita, allora N1 e N2 sono isomorfi.

Dimostrazione. Sia α > ℵ0 la cardinalita di N1 e N2. Per (8.16), abbiamo che α e anchela cardinalita degli insiemi C1 e C2 delle Z-catene nei due modelli. Esiste quindi unacorrispondenza biunivoca tra C1 e C2. Componendo tale corrispondenza con l’identita suZ otteniamo quindi una biiezione (che conserva σ) tra le parti non-standard di N1 e N2.Le parti standard sono ovviamente isomorfe.

In base a questa proposizione abbiamo immediatamente:

Teorema 8.14 La teoria T 1N,σ e α-categorica per ogni α non numerabile.

44

Corollario 8.15 La teoria T 1N,σ e sintatticamente completa.

Dimostrazione. Per il teorema precedente e la Proposizione 6.6, tenendo presente che T 1N,σ

non ha modelli finiti.

Corollario 8.16 Per ogni enunciato ϕ di L1N,σ, ϕ e vero nella struttura standard N0 se

e solo se e dimostrabile in T 1N,σ.

Dimostrazione. La struttura N0 e modello di T 1N,σ, e dunque ogni teorema di T 1

N,σ e veroin N0. Inversamente, se T 1

N,σ 6` ϕ, allora T 1N,σ ` ¬ϕ per la completezza sintattica di T 1

N,σ,e quindi ϕ non e vero in N0.

Definizione 8.17 Una teoria assiomatica T ammette eliminazione dei quantificatori se,per ogni formula ϕ, esiste una formula ψ, in cui non compaiono quantificatori, tale cheT ` ϕ↔ ψ.

Dimostreremo che T 1N,σ ammette eliminazione dei quantificatori. In base al Corollario 8.16

sara sufficiente mostrare che, per ogni formula ϕ, esiste una formula ψ, in cui non com-paiono quantificatori, tale che N0 |= ϕ↔ ψ. D’ora in avanti quindi, parleremo di formuleϕ e ψ equivalenti intendendo sia T 1

N,σ ` ϕ↔ ψ, sia N0 |= ϕ↔ ψ.24

Enunciamo preliminarmente un risultato sulle logiche del primo ordine. Chiamiamo let-terale ogni formula atomica, o negazione di formula atomica. Nel caso di L1

N,σ, dove nonabbiamo simboli per relazioni, i letterali saranno quindi le formule del tipo t1 = t2 ot1 6= t2, dove t1 e t2 sono termini. Essendo poi 0 l’unica costante e σ l’unica funzione, itermini saranno solo del tipo σn0 o σnx, con x variabile e n ≥ 0.

Definizione 8.18 La formula ϕ e in forma normale prenessa congiuntiva se ϕ e Q1x1,. . . , Qnxnψ dove (1) ogni Qi e ∀ o ∃, e (2) ψ e una congiunzione ψ1∧· · ·∧ψk dove ciascunϕi e una disgiunzione ψi1 ∨ · · · ∨ψimi di letterali. La forma normale prenessa disgiuntivae definita in modo analogo, scambiando ∧ e ∨.

Non daremo una dimostrazione della seguente proposizione. Ci limitiamo ad osservareche la dimostrazione si basa su equivalenze del tipo ¬(ϕ∧ψ)↔ ¬ϕ∨¬ψ, ¬∀xϕ↔ ∃x¬ϕecc., e sulla distributivita di ∨ rispetto a ∧ e viceversa.

Proposizione 8.19 Ogni formula del primo ordine e equivalente ad una formula in formanormale prenessa congiuntiva e ad una formula in forma normale prenessa disgiuntiva.

24Spesso problemi relativi all’eliminazione dei quantificatori sono riferiti a ‘teorie’ intese come insiemidi formule chiusi per deducibilita, e quindi non necessariamente teorie ‘assiomatiche’. L’esempio piufrequente e “l’insieme degli enunciati veri in una data interpretazione I”, per cui la definizione dell’elimi-nazibilita dei quantificatori e che, per ogni formula ϕ esiste una formula ψ senza quantificatori tale cheI |= ϕ↔ ψ.

45

Lemma 8.20 Se una teoria del primo ordine T ammette eliminazione dei quantificatoriper formule del tipo ∃x(ψ1 ∧ · · · ∧ψn) con ψi letterali, allora T ammette eliminazione deiquantificatori.

Dimostrazione. Consideriamo una formula ϕ e supponiamo inizialmente che, in formanormale prenessa disgiuntiva, abbia un solo quantificatore. Quindi ϕ e equivalente allaformula Qx(ϕ1 ∨ · · · ∨ ϕn) dove Q e ∃ o ∀, e ogni ϕi e una congiunzione di letterali.

Caso 1: Q e ∃. Dall’equivalenza ∃x(χ1∨χ2)↔ (∃xχ1∨∃xχ2) abbiamo che ϕ e equivalentea ∃xϕ1∨· · ·∨∃xϕn. Essendo ogni ϕi una congiunzione di letterali, per le ipotesi del lemmaogni formula ∃xϕi e equivalente ad una formula senza quantificatori, quindi il risultatovale anche per ϕ.

Caso 2: Q e ∀. Questo caso si riporta facilmente al precedente osservando che ∀xψ eequivalente a ¬∃x¬ψ. La formula ¬ψ risulta a sua volta equivalente alla disgiunzione dicongiunzioni di letterali, e dunque, come abbiamo visto sopra, ∃x¬ψ e equivalente ad unaformula senza quantificatori.

Nel caso in cui la forma normale prenessa disgiuntiva di ϕ abbia piu di un quantificatore,possiamo iterare il processo precedente e determinare una formula equivalente a ϕ e senzaquantificatori.

Teorema 8.21 La teoria T 1N,σ ammette eliminazione dei quantificatori.

Dimostrazione. Per il lemma precedente possiamo limitarci a dimostrare il teorema performule del tipo ∃x(ϕ1 ∧ · · · ∧ ϕn) dove le ϕi sono letterali che, in L1

N,σ, sono formule deltipo σkt1 = σmt2 o σkt1 6= σmt2, dove t1 e t2 sono la costante 0 o una variabile, e k,m ≥ 0.

Mostreremo che ogni formula ϕi puo essere sostituita con una formula in cui x non com-pare. Il teorema seguira quindi dal fatto che ∃xψ e equivalente a ψ se questa formula noncontiene x. Ogni formula ϕi che contiene x ha la forma σkx = σmt o σkx 6= σmt, dove t e0 o una variabile. Possiamo anche supporre che t non sia la variabile x perche σkx = σmxpuo essere sostituito da 0 = 0 se k = m, e da 0 6= 0 se k 6= m. Possiamo ora distingueredue casi.

Caso 1: ogni ϕi e e del tipo σkx 6= σmt, con t 6= x. Dunque ∃x(ϕ1 ∧ . . . ϕn) esprimel’esistenza di un x che verifica un numero finito di disuguaglianze di quel tipo. Per ogniscelta di valori per le variabili diverse da x che compaiono in ϕ, esiste sempre un valoredi x che verifica le disuguaglianze perche queste sono in numero finito. La formula ϕ edunque equivalente alla formula 0 = 0.

Caso 2: esiste almeno una ϕi della forma σkx = t, dove t non contiene x. Questaequazione ha soluzioni quando il numero naturale corrispondente a t e maggiore o ugualea k. L’esistenza di un x tale che σkx = t corrisponde alla verita della formula t 6= 0∧ t 6=σ0∧· · ·∧t 6= σk−10 in cui x non compare. Possiamo quindi sostituire quest’ultima formulaa ϕi. Se σmx = u e un’altra ϕj nella forma di uguaglianza, possiamo prima sostituire ϕjcon σm+kx = σku e quindi con σmt = σku in cui x non compare.

Possiamo ora vedere alcune conseguenze dell’eliminabilita dei quantificatori per L1N,σ. La

prima e la decidibilita dell’insieme degli enunciati di L1N,σ veri in N0. Non enunciamo

46

esplicitamente questo risultato perche non abbiamo dato una definizione rigorosa di de-cidibilita. Alcune osservazioni intuitive possono tuttavia presentare adeguatamente ilrisultato. Osserviamo preliminarmente che la costruzione della formula senza quantifica-tori nella dimostrazione del Teorema 8.21 e basata su una procedura effettiva che permettedi costruire quella formula con un numero finito di passaggi. Sempre per quella dimostra-zione, inoltre, la formula ottenuta non ha piu variabili libere della formula ϕ di partenza.Un enunciato risulta quindi equivalente ad un enunciato ψ senza quantificatori, in cuicioe non compaiono variabili. Tenendo presente ora i simboli di L1

N,σ, ψ non e altro chela combinazione di formule del tipo σm0 = σk0 con gli operatori ∧, ∨ e ¬. La verita delleformule costruite in questo modo e determinabile in un numero finito di passaggi (con letavole di verita). Abbiamo quindi che la verita in N0 per le formule di L1

N,σ (che equivalealle dimostrabilita in T 1

N,σ) risulta decidibile.25

Diciamo che A ⊆ X e cofinito se A, il complementare X \ A di A in X, e finito.

Lemma 8.22 I sottoinsiemi di N0 definibili nel linguaggio L1N,σ sono i sottoinsiemi finiti

e cofiniti.

Dimostrazione. Consideriamo una formula ϕ(x) con l’unica variabile libera x. Per ilTeorema 8.21 possiamo supporre che ϕ(x) non contenga quantificatori, e quindi sia com-binazione, per mezzo degli operatori ∧, ∨ e ¬, di formule atomiche σkt1 = σmt2 in cuicompare al piu la variabile x. Ogni formula di questo tipo definisce un insieme con alpiu un elemento, quindi un insieme finito, oppure l’intero N0. Le operazioni insiemistichecorrispondenti agli operatori ∧, ∨ e ¬ sono intersezione, unione, e complementazione. Ba-sta quindi osservare che applicando queste operazioni a insiemi finiti o cofiniti, otteniamoancora insiemi finiti o cofiniti.

Proposizione 8.23 L’operazione di somma non e definibile in L1N,σ.

Dimostrazione. Con l’operazione di somma possiamo definire l’insieme dei numeri pari:∃y(y + y = x). Ma questo insieme non e finito ne cofinito. Quindi il risultato segue dallemma precedente.

9 Teorema di Los e Teorema di Compattezza

9.1 Ultrafiltri

La nozione generale di filtro riguarda i reticoli, o in particolare le Algebre di Boole. Per gliscopi di queste note possiamo limitarci all’Algebra di Boole ℘X, dove X e un arbitrarioinsieme infinito.

25In effetti questo risultato poteva essere dedotto anche dal Corollario 8.15. E un risultato classicodi Teoria della Ricorsivita infatti che l’insieme dei teoremi di una teoria assiomatica sintatticamentecompleta e decidibile.

47

Definizione 9.1 Un filtro sull’insieme X e un sottoinsieme F di ℘X tale che (1) ∅ 6∈ F ,(2) se Y ∈ F e Y ⊆ Z, allora Z ∈ F , e (3) se Y ∈ F e Z ∈ F , allora Y ∩ Z ∈ F .

Esercizio 9.2 Sia F un filtro su X e siano A e B sottoinsiemi di X. Dimostrare cheA ∩B ∈ F se e solo se A ∈ F e B ∈ F .

Esercizio 9.3 Sia A e un sottoinsieme non vuoto di X. Dimostrare che {B ⊆ X : A ⊆B} e un filtro (che viene chiamato filtro principale generato da A)

Esercizio 9.4 Dimostrare che i sottoinsiemi cofiniti di un insieme infinito X costitui-scono un filtro (filtro di Frechet su X).

Definizione 9.5 Un sottoinsieme H di ℘X ha la proprieta dell’intersezione finita (PIF)se A0 ∩ · · · ∩ An 6= ∅ per ogni sottoinsieme finito {A0, . . . , An} di H.

Esercizio 9.6 Dimostrare che, se H ∈ ℘X ha la PIF, allora l’insieme F = {A ⊆ X :∃A0, . . . , An ∈ H : A0 ∩ · · · ∩ An ⊆ A} e un filtro su X

Proposizione 9.7 Sia U un filtro sull’insieme X. Sono equivalenti le seguenti afferma-zioni: (i) U e massimale per inclusione, cioe, se F e un filtro su X e U ⊆ F , alloraU = F ; (ii) per ogni A ⊆ X, A ∈ U oppure A ∈ U ; (iii) se A0 ∪ · · · ∪ An ∈ U , alloraesiste un i ≤ n tale che Ai ∈ U .

Dimostrazione. (i) ⇒ (ii). Supponiamo A 6∈ U . Allora, per la proprieta (2) dei filtri,B 6⊆ A e dunque B ∩A 6= ∅ per ogni B ∈ U . Quindi U ∪ {A} ha la PIF26 ed e contenutoin un filtro F , ma per (i) F = U e A ∈ U .

(ii)⇒ (iii). Supponiamo Ai 6∈ U per ogni i ≤ n. La proprieta (ii) implica Ai ∈ U per ognii e quindi A0∩ · · ·∩An ∈ U , ma A0∩ · · ·∩An = A0 ∪ · · · ∪ An e quindi A0∪ · · ·∪An 6∈ U .

(iii) ⇒ (i). Sia U un filtro che verifica (iii) e supponiamo U ⊆ F . Mostriamo che ognielemento di F e anche elemento di U . Dato A ∈ F , A ∪ A ∈ U e quindi A ∈ U oppureA ∈ U . Ma la seconda alternativa non puo verificarsi perche U ⊆ F .

Definizione 9.8 Un ultrafiltro su X e un filtro che verifica le tre condizioni equivalentidella Proposizione 9.7.

Dato un insieme X e un suo elemento x0, l’insieme U = {A ⊆ X : x0 ∈ A} e un ultrafiltro(esercizio). In questo caso diciamo che U e l’ultrafiltro principale generato da x0. Esistonoanche ultrafiltri non principali; in particolare ogni filtro puo essere esteso ad un ultrafiltro.Per dimostrare questo risultato e necessario il Lemma di Zorn (Appendice B).

Teorema 9.9 Ogni filtro F sull’insieme X e contenuto in un ultrafiltro.

26Si osservi che possiamo sostituire B con qualsiasi intersezione finita B1 ∩ · · · ∩Bn di elementi di U .

48

Dimostrazione. Sia F = {G : G e un filtro su X e F ⊆ G}. La relazione ⊆ e una relazioned’ordine su F. Sia H un sottoinsieme di F totalmente ordinato da ⊆. Mostriamo cheH =

⋃G∈H G e un filtro. L’insieme vuoto non appartiene a nessun elemento di H e quindi

neanche a H. Se A ∈ H e A ⊆ B, basta osservare che A appartiene a qualche G ∈ H equindi B ∈ G, da cui segue B ∈ H. Supponiamo A,B ∈ H. Esistono quindi G,G ′ ∈ Htali che A ∈ G e B ∈ G ′. Poiche H e totalmente ordinato da ⊆, abbiamo G ⊆ G ′ oppureG ′ ⊆ G. Supponiamo G ⊆ G ′. Allora A,B ∈ G ′ e A ∩B ∈ G ′ ⊆ H.

Dunque H e un filtro che contiene tutti i filtri in H; e cioe un maggiorante per H. Sonoquindi verificate le ipotesi del Lemma di Zorn e possiamo concludere che F ha elementimassimali per l’inclusione. Tali elementi sono ultrafiltri.

Corollario 9.10 Dato l’insieme X, ogni sottoinsieme di ℘X con la PIF e contenuto inun ultrafiltro.

L’insieme dei sottoinsieme cofiniti di X per esempio puo essere esteso ad un ultrafiltroche non e principale.

Esercizio 9.11 Dimostrare che un ultrafiltro non e principale se e solo se contiene tuttigli insiemi cofiniti.

9.2 Prodotti diretti e ultraprodotti

In questa sezione (tratta da [Bell and Machover, 1977, Cap. 5]) verra considerata la co-struzione di interpretazioni di un dato linguaggio basata su altre interpretazioni dello stes-so linguaggio. Vogliamo determinare delle condizioni affinche nella nuova interpretazionerisultino vere le formule che erano vere nelle interpretazioni di partenza.

Per non appesantire il discorso considereremo un linguaggio L con un’unico simbolo perrelazione binaria R (oltre all’identita) e senza simboli per costanti e per funzioni. Gli unicitermini di L sono dunque le variabili. In tutta la sezione, J e un fissato insieme non vuotodi indici e, per ogni j ∈ J , Ij = 〈Dj, Ij〉 e una fissata interpretazione di L. Indichiamocon D il prodotto cartesiano

∏j∈J Dj. Gli elementi di D sono dunque funzioni f da J in⋃

j∈J Dj tali che, per ogni j, f(j) ∈ Dj.

Il prodotto diretto∏

j∈J Ij e una interpretazione I = 〈D, I〉 per L in cui l’interpretazioneRI di R viene definita dalla seguente condizione

〈f, g〉 ∈ RI ⇔ per ogni j ∈ J, 〈f(j), g(j)〉 ∈ RIj (9.17)

I prodotti diretti di strutture non funzionano bene per conservare la verita delle formule.Non e difficile infatti costruire esempi di enunciati che risultano veri in ogni Ij, ma falsinel prodotto diretto I.

Supponiamo per esempio che ogni RIj sia una relazione di ordine totale che indichiamocon ≤j. Indicando con ≤ la relazione RI , in base a (9.17) abbiamo che f ≤ g se esolo se, per ogni j ∈ J , f(j) ≤j g(j). Per la totalita degli ordini ≤j, l’enunciato ϕ =

49

∀x, y (R(x, y)∨R(y, x)) e vero in ogni Ij. Supponiamo ora che gli insiemi J e Dj abbianoalmeno due elementi. Esistono quindi f, g ∈ D tali che: per qualche j, f(j) 6≤j g(j) e,per altri k, f(k) 6≤k g(k). Da cio segue f 6≤ g e g 6≤ f , e dunque I 6|= ϕ. Per conservare laverita degli enunciati abbiamo bisogno di costruzioni piu complesse del prodotto diretto.

Sia ϕ(v1, . . . , vn) una formula le cui variabili libere appartengono all’insieme {v1, . . . , vn}e consideriamo gli elementi f1, . . . , fn di D. Siamo interessati all’

insieme degli indici j tali che la formula ϕ(v1, . . . , vn) risulta vera in Ij quando levariabili v1, . . . , vn vengono valutate rispettivamente in f1(j), . . . , fn(j).

Estendendo la notazione vista nella Definizione 2.6, scriveremo V(v1, . . . , vn/a1, . . . , an)per indicare la valutazione V ′ tale che V ′(vi) = ai per i = 1, . . . , n, e V ′(v) = V(v) perogni altra variabile. Conviene infine usare la notazione vettoriale scrivendo v al posto div1, . . . , vn, f al posto di f1, . . . , fn, e f(j) al posto di f1(j), . . . , fn(j). Poniamo:

||ϕ(v)[f ] || def= {j ∈ J : Ij,Vj(v/f(j)) |= ϕ(v)} (9.18)

dove Vj e una arbitraria valutazione su Ij. Poiche tutte le variabili libere di ϕ(v) sononell’insieme {v1, . . . , vn}, la definizione precedente non dipende dalla scelta delle Vj.

Lemma 9.12 Per ogni f, g, f1, . . . , fn in D, abbiamo

||v1 = v2 [f, g] || = {j ∈ J : f(j) = g(j)}||R(v1, v2) [f, g] || = {j ∈ J : 〈f(j), g(j)〉 ∈ RIj}

||¬ϕ(v)[f ] || = J \ ||ϕ(v)[f ] ||||(ϕ ∧ ψ)(v)[f ] || = ||ϕ(v)[f ] || ∩ ||ψ(v)[f ] ||||∃v ϕ(v,v)[f ] || =

⋃f∈D ||ϕ(v,v)[f, f ] ||

Dimostrazione. Le prime due uguaglianze seguono immediatamente dalla regola di veritaR0 e R1. Dalle regole R2 e R3 segue facilmente l’enunciato per formule del tipo ¬ϕ eϕ ∧ ψ.

Per l’ultima uguaglianza dobbiamo usare la regola R8. Supponiamo j ∈ ||∃v ϕ(v,v)[f ] ||,cioe, per (9.18),

Ij,Vj(v/f(j)) |= ∃v ϕ(v,v)

e quindi esiste a ∈ Dj tale che

Ij,Vj(v,v/a, f(j)) |= ϕ(v,v)

Se dunque g e un qualsiasi elemento di D tale che g(j) = a, abbiamo

j ∈ ||ϕ(v,v)[g, f ] || ⊆⋃f∈D

||ϕ(v,v)[f, f ] ||

Supponiamo inversamente j ∈⋃f∈D ||ϕ(v,v)[f, f ] ||. Esiste quindi g ∈ D tale che j ∈

||ϕ(v,v)[g, f ] ||, cioeIj,Vj(v,v/g(j), f(j)) |= ϕ(v,v)

ma per R8 da cio segue Ij,Vj(v/f(j)) |= ∃v ϕ(v,v), cioe j ∈ ||∃v ϕ(v,v)[f ] ||.

50

Osservazione 9.13 Nel precedente lemma abbiamo considerato solo formule costruitesolo usando ¬, ∧ e ∃. Non e una scelta restrittiva perche (come abbiamo osservato nellanota 6) gli altri operatori possono essere definiti usando questi. In tutto il capitolo quindiconsidereremo formule costruite in questo modo.

Esercizio 9.14 Sia ϕ(v) una formula con l’unica variabile libera v e siano f e g elementidi D. Mostrare che

||v1 = v2[f, g] || ∩ ||ϕ(v)[f ] || ⊆ ||ϕ(v)[g] ||

Suggerimento. Per (9.18), il fatto che j appartenga o meno a ||ϕ(v)[f ] || dipende solo dalvalore di f in j.

Lemma 9.15 Sia ϕ(v,v) una formula con variabili libere in {v, v1, . . . , vn} e siano f1, . . . , fnelementi di D. Allora esiste g ∈ D tale che

||∃v, ϕ(v,v)[f ] || = ||ϕ(v,v)[g, f ] ||

Dimostrazione. Per semplicita di scrittura supponiamo che v sia l’unica variabile liberain ϕ, per cui le n-uple v e f sono vuote. La dimostrazione nel caso generale e identica.

Consideriamo un buon ordinamento di D.27 Abbiamo dunque D = {fβ : β < α}, dove αe un opportuno ordinale. Per ogni β < α poniamo

Xβ = ||ϕ(v)[fβ] || \⋃η<β

||ϕ(v)[fη] ||

Per il Lemma 9.12 abbiamo quindi

||∃v ϕ(v)|| =⋃f∈D

||ϕ(v)[f ] || =⋃β<α

||ϕ(v)[fβ] || =⋃β<α

Xβ

Gli insiemi Xβ sono per costruzione sottoinsiemi di J a due a due disgiunti. Poiche unionidi funzioni con domini disgiunti sono ancora funzioni, l’unione

⋃β<α fβ |Xβ delle restrizioni

delle fβ a Xβ e una funzione con dominio⋃β<αXβ. Sia g un qualsiasi elemento di D

che estende questa funzione. Per ogni β < α abbiamo quindi g|Xβ = fβ |Xβ . QuindiXβ ⊆ ||v1 = v2[g, fβ] || e, per l’Esercizio 9.14,

||ϕ(v)[g] || ⊇ ||v1 = v2[g, fβ] || ∩ ||ϕ(v)[fβ] || ⊇ Xβ

da cui segue||∃v ϕ(v)|| =

⋃β<α

Xβ ⊆ ||ϕ(v)[g] ||

L’inclusione inversa segue dal Lemma 9.12.

Sia ora U un ultrafiltro sull’insieme J degli indici. Per ogni f, g ∈ D poniamo

f ∼U g ⇔ {j : f(j) = g(j)} ∈ U (9.19)

27In questa dimostrazione viene usata la nozione di ordinale che verra precisata solo nella seconda partedel corso.

51

Esercizio 9.16 Dimostrare che la relazione ∼U e una relazione di equivalenza. (Si osserviche e sufficiente supporre che U sia un filtro).

Possiamo quindi considerare l’insieme delle classi di equivalenza modulo ∼U in D. Indi-cheremo questo insieme con D/U , e con [f ]U la classe di equivalenza dell’elemento f diD. Vogliamo usare l’insieme D/U come dominio di una nuova interpretazione di L, percui dobbiamo definire l’interpretazione di R che indicheremo con RU . Poniamo

〈[f ]U , [g]U〉 ∈ RU ⇔ {j ∈ J : 〈f(j), g(j)〉 ∈ RIj} ∈ U (9.20)

Lemma 9.17 La relazione RU in (9.20) e ben definita.

Dimostrazione. Poniamo F = {j ∈ J : f(j) = f ′(j)}, G = {j ∈ J : g(j) = g′(j)} eX = {j ∈ J : 〈f(j), g(j)〉 ∈ RIj}, e supponiamo F ∈ U , G ∈ U , e X ∈ U . Le primedue relazioni dicono rispettivamente che f ∼U f ′ e g ∼U g′. Per verificare che RU eben definita dobbiamo mostrare che anche l’insieme X ′ = {j ∈ J : 〈f ′(j), g′(j)〉 ∈ RIj}appartiene a U . Ma F ∩G ∩X ⊆ X ′ e quindi, per le proprieta dei filtri, X ′ ∈ U .

L’interpretazione di L, basata su D/U e con l’interpretazione RU del simbolo per relazioni

R, viene indicata con∏j∈J

Ij/U (o I/U) e viene chiamata ultraprodotto delle interpretazioni

Ij (con ultrafiltro U). Se tutte queste interpretazioni coincidono con l’interpretazione K,allora l’interpretazione I/U , indicata con KJ/U , viene chiamata ultrapotenza di K.

Si vedra in seguito gli ultraprodotti sono interessanti solo quando sono basati su ultrafiltrinon principali, quindi ultrafiltri che non hanno insiemi finiti come elementi (v. Eserci-zio 9.11). Per questo motivo si dice spesso che le classi di equivalenza [ · ]U identificanoelementi di D che coincidono su un ‘sottoinsieme grande’ di J . Un discorso analogo sipuo fare per la relazione RU .

Teorema 9.18 (Teorema di Los) Sia ϕ una formula di L con variabili libere nell’in-sieme {v1, . . . , vn} (= {v}). Per ogni n-upla f1, . . . , fn (= f) di elementi di D,

I/U ,V(v/[f ]U) |= ϕ ⇔ ||ϕ(v)[f ] || ∈ U

dove [f ]U e l’n-upla [f1]U , . . . , [fn]U . In particolare, se ϕ e un enunciato,

I/U |= ϕ ⇔ {j ∈ J : Ij |= ϕ} ∈ U

Dimostrazione. La seconda equivalenza e conseguenza immediata della prima che dimo-striamo per induzione sulla complessita di ϕ. Se ϕ e della forma v1 = v2 o R(v1, v2), allorail risultato e conseguenza immediata della definizione di ∼U e di RU . Possiamo quindiconsiderare i casi in cui ϕ e ¬ψ, o ψ∧χ, o ∃v ψ, e supporre induttivamente che il teoremavalga per ψ e χ.

Caso 1: ϕ e ¬ψ. Allora

I/U ,V(v/[f ]U) |= ϕ ⇔ I/U ,V(v/[f ]U) 6|= ψ

52

⇔ ||ψ(v)[f ] || 6∈ U ⇔ ||ϕ(v)[f ] || ∈ U

dove nella penultima equivalenza abbiamo usato l’ipotesi induttiva e, nell’ultima, abbiamousato l’uguaglianza ||ψ(v)[f ] || = J \ ||ϕ(v)[f ] || (Lemma 9.12) e il fatto che U sia unultrafiltro.

Caso 2: ϕ e ψ ∧ χ. Allora

I/U ,V(v/[f ]U) |= ϕ ⇔ I/U ,V(v/[f ]U) |= ψ e I/U ,V(v/[f ]U) |= χ

⇔ ||ψ(v)[f ] || ∈ U e ||χ(v)[f ] || ∈ U ⇔ ||ψ(v)[f ] || ∩ ||χ(v)[f ] || ∈ U

⇔ ||(ψ ∧ χ)(v)[f ] || ∈ U

dove abbiamo usato il (Lemma 9.12) e l’Esercizio 9.2.

Caso 3: ϕ e ∃v ψ. Allora I/U ,V(v/[f ]U) |= ϕ se e solo se esiste f ∈ D tale cheI/U ,V(v,v/[f ]U , [f ]U) |= ψ. Per l’ipotesi induttiva cio equivale a ||ψ(v,v)[f, f ] || ∈ U .Per il Lemma 9.12, ||ψ(v,v)[f, f ] || ⊆ ||∃v ψ(v,v)[f ] || e dunque, per le proprieta dei filtri,||∃v ψ(v,v)[f ] || ∈ U .

Supponiamo inversamente ||∃v ψ(v,v)[f ] || ∈ U . Per il Lemma 9.15 esiste g ∈ D taleche ||ψ(v,v)[g, f ] || ∈ U . Per l’ipotesi induttiva abbiamo I/U ,V(v,v/[g]U , [f ]U) |= ψ cheimplica I/U ,V(v/[f ]U) |= ∃v ψ.

La seguente proposizione dimostra che un ultraprodotto e effettivamente interessante soloquando l’ultrafiltro su cui e basato non e principale. Altrimenti non costruiamo niente dinuovo.

Proposizione 9.19 Se l’ultrafiltro U e l’ultrafiltro principale generato da j0, allora l’ul-traprodotto I/U e isomorfo a Ij0.

Dimostrazione. Dobbiamo definire una opportuna funzione biiettiva h da D/U su Dj0 .Poniamo h([f ]U) = f(j0). Tale funzione e ben definita perche [f ]U = [g]U ⇔ {j : f(j) =g(j)} ∈ U ⇔ j0 ∈ {j : f(j) = g(j)} ⇔ f(j0) = g(j0) ⇔ h([f ]U) = h([g]U). Questeequivalenze mostrano anche che h e iniettiva.

La funzione h e banalmente suriettiva perche, per ogni a ∈ Dj0 esiste f in D tale chef(j0) = a. Resta quindi da dimostrare che h conserva le interpretazioni RU e RIj0 delsimbolo per funzioni R. Da (9.20) segue: 〈[f ]U , [g]U〉 ∈ RU ⇔ {j : 〈f(j) = g(j)〉 ∈ RIj} ∈U ⇔ 〈f(j0), g(j0)〉 ∈ RIj0 .

Esercizio 9.20 Si supponga Ij = K per ogni j ∈ J , e che l’insieme J sia finito.Dimostrare che l’ultrapotenza KJ/U e isomorfa a K.

Proposizione 9.21 Sia J = N , l’insieme dei naturali e sia K l’interpretazione di Lbasata sul dominio N , in cui RK e l’usuale ordine sui naturali. Sia infine U in ultrafiltronon principale su N . Allora KJ/U non e un buon ordinamento.

53

Dimostrazione. Indichiamo con 〈a0, a1, . . . 〉 le successioni di naturali. Il dominio D diKJ/U e quindi costituito dalle classi di equivalenza [〈a0, a1, . . . 〉]U dove [〈a0, a1, . . . 〉]U =[〈b0, b1, . . . 〉]U ⇔ {n : an = bn} ∈ U . La relazione RU in KJ/U e definita da

〈[〈a0, a1, . . . 〉]U , [〈b0, b1, . . . 〉]U〉 ∈ RU ⇔ {n : an ≤ bn} ∈ U

Siano f0, f1, . . . , fn, . . . le successioni di naturali dove f0 = 〈0, 1, 2, 3 . . . 〉 e, per ognin, se fn = 〈a0, a1, . . . 〉 allora fn+1 = 〈b0, b1, . . . 〉 e definita da: bk = 0 se ak = 0, ebk = ak−1 se ak 6= 0. Le successioni f0, f1, . . . sono quindi 〈0, 1, 2, 3 . . . 〉, 〈0, 0, 1, 2, 3 . . . 〉,〈0, 0, 0, 1, 2, 3, . . . 〉, ecc. In particolare, per ogni naturale k, bk ≤ ak che implica 〈[fn+1]U ,[fn]U〉 ∈ RU per ogni n. La successione [f0]U , [f1]U , . . . , [fn]U , . . . e dunque una successioneRU -decrescente.

Per concludere la dimostrazione dobbiamo mostrare che la successione [f0]U , [f1]U , . . . ,[fn]U , . . . e infinita. Per ogni n 6= m, fn e fm coincidono solo su un insieme finito dinaturali (un segmento iniziale) che quindi non appartiene a U (essendo questo ultrafiltronon principale). Dunque [fn]U 6= [fm]U .

Questo risultato puo essere generalizzato all’ultraprodotto di arbitrari insiemi infiniti beneordinati. Una conseguenza e un risultato gia visto nell’Esercizio 4.5: la proprieta diessere un buon ordinamento non e esprimibile da formule del primo ordine (altrimentitale proprieta dovrebbe essere conservata dagli ultraprodotti).

Siamo ora in grado di dimostrare il Teorema di Compattezza Semantica (Teorema 4.2)con mezzi puramente semantici, cioe senza usare il Teorema 4.1.

Teorema 9.22 (Teorema di Compattezza Semantica) Un insieme Φ di enunciatidel primo ordine ha modello se e solo se ogni suo sottoinsieme finito ha modello.

Dimostrazione. Sia J l’insieme di tutti i sottoinsiemi finiti di Φ e, per ogni ∆ ∈ J , fissiamoun modello I∆ di ∆. Poniamo

∆ = {∆′ ∈ J : ∆ ⊆ ∆′}

Dati gli elementi ∆1, . . . ,∆n di J , abbiamo ∆i ⊆ ∆1∪· · ·∪∆n per ogni i e quindi ∆1∪· · ·∪∆n ∈ ∆1∩· · ·∩ ∆n. L’insieme {∆ : ∆ ∈ J} ha dunque la proprieta dell’intersezione finitae possiamo considerare un ultrafiltro U che lo contiene. Dimostriamo che l’ultraprodotto∏∆∈J

I∆/U e un modello di Φ.

Sia ϕ un enunciato in Φ. Allora il singoletto {ϕ} appartiene a J e possiamo considerare

{ϕ} che appartiene a U . Per ogni ∆ ⊇ {ϕ} (cioe ∆ ∈ {ϕ}) abbiamo I∆ |= ϕ e quindi

{ϕ} ⊆ {∆ ∈ J : I∆ |= ϕ}

da cui segue {∆ ∈ J : I∆ |= ϕ} ∈ U e∏∆∈J

I∆/U |= ϕ per il Teorema 9.18.

54

10 Teorema di Ramsey

La prima parte di questa sezione e tratta da [Boolos and Jeffrey, 1980]. Il Teorema diRamsey riguarda un problema di combinatoria. Consideriamo un insieme finito X eindichiamo con [X]r l’insieme dei sottoinsiemi di X con esattamente r elementi. Sia{C1, . . . , Cs} una arbitraria partizione di [X]r; abbiamo cioe

⋃Ci = [X]r e Ci ∩ Cj = ∅

per ogni i 6= j. Dato un numero naturale n, ci poniamo il seguente problema:

esiste Y ⊆ X : Y ha n elementi e [Y ]r e contenuto in qualche Ci ? (10.21)

Esempio 10.1 Sia r = 2. Allora possiamo pensare gli elementi di X come i vertici diun poligono e [X]2 come l’insieme dei lati e delle diagonali di quel poligono. Sia s = 2.Cio vuol dire che dividiamo [X]2 in due insiemi disgiunti C1 e C2. Se n = 3, il problemadiventa: esiste sottoinsieme Y di X con 3 elementi tale che i segmenti aventi estremi inY sono tutti in C1 oppure oppure tutti in C2?

Mostriamo che se X ha 6 elementi, allora la risposta e positiva. Sia A un elemento diX. Da A partono 5 tra lati e diagonali, e quindi almeno tre di questi sono in C1 o inC2. Supponiamo che AB, AC, AD, siano in C1. Se BC ∈ C1 allora Y = {A,B,C}. SeBD ∈ C1 allora Y = {A,B,D}. Se CD ∈ C1 allora Y = {A,C,D}. Se nessuna delleprecedenti alternative vale, allora abbiamo BC ∈ C2, BD ∈ C2, e CD ∈ C2, e in questocaso Y = {B,C,D}.

Una volta fissati i valori r, s, e n, l’esistenza dell’insieme Y in (10.21) dipende dal numerodi elementi di X.

Definizione 10.2 Il Numero di Ramsey R(r, s, n) e il minimo numero naturale tale che,per ogni X con R(r, s, n) elementi, e per ogni partizione {C1, . . . , Cs} di [X]r, esiste unY ⊆ X che verifica (10.21).

Teorema 10.3 Teorema di Ramsey Per ogni r, s, n, R(r, s, n) esiste.

Dimostreremo questo teorema usando i Teoremi di Compattezza e di Lowenheim-Skolem,passando attraverso la seguente versione infinitaria dello stesso teorema.

Teorema 10.4 Teorema di Ramsey infinito Siano r e s naturali positivi arbitrari.Per ogni partizione {C1, . . . , Cs} di [N]r, esiste un sottoinsieme infinito Y di N ed unindice i tali che [Y ]r ⊆ Ci.

Dimostrazione. V. §10.1.

Nel seguito converra identificare una partizione {C1, . . . , Cs} di [X]r con una funzionef : [X]r → {1, . . . , s}: Ci = f−1{i}. In questo modo la proprieta dell’insieme Y in (10.21)puo essere espressa da f [[Y ]r] = {i}.

55

Mostreremo, nel caso particolare r = 4, s = 3, n = 5, che il Teorema 10.3 segue dalTeorema 10.4. Sara evidente dalla dimostrazione che il caso particolare puo essere gene-ralizzato ad arbitrarie terne (r, s, n). Useremo una dimostrazione per assurdo, per cui ilprimo passo sara esprimere la negazione del Teorema di Ramsey in quel caso particolare.Tale negazione e equivalente a: per ogni naturale m,

NRm esiste un insieme X con m elementi ed una funzione f : [X]4 → {1, 2, 3} taleche, per ogni sottoinsieme Y di X con 5 elementi, esistono Z1, Z2, Z3 ∈ [Y ]4 tali chef(Z1) 6= 1, f(Z2) 6= 2, f(Z3) 6= 3.

Si osservi che l’ultima parte di NRm dice proprio che f [[Y ]4] non e un singoletto {i} comevorrebbe il Teorema di Ramsey.

Il prossimo passaggio e quello di esprimere NRm per mezzo di una formula di un op-portuno linguaggio L del primo ordine. Oltre ai simboli logici e all’uguaglianza, questolinguaggio ha tre simboli per relazioni a 4 argomenti: R1, R2, R3. Il significato che verraattribuito alla formula Ri(x, y, z, t) e “l’elemento {x, y, z, t} di [X]4 appartiene all’i-esimacomponente della partizione”, o, nella notazione introdotta sopra, f({x, y, z, t}) = i.Sulla base di queste considerazioni possiamo dare un senso alle seguenti formule doveDist(x1, . . . , xk) e la formula

∧1≤i<j≤k xi 6= xj, e quindi e vera quando x1, . . . , xk vengono

interpretati su k oggetti distinti.

Le seguenti formule ϕ1 e ϕ2 esprimono il fatto che R1, R2, R3 determinano una partizionedi [X]4.

ϕ1def= ∀x, y, z, t (Dist(x, y, z, t)↔ R1(x, y, z, t) ∨R2(x, y, z, t) ∨R3(x, y, z, t))

ϕ2def= ∀x, y, z, t [(R1(x, y, z, t)→ (¬R2(x, y, z, t) ∧ ¬R3(x, y, z, t)) ∧

(R2(x, y, z, t)→ (¬R1(x, y, z, t) ∧ ¬R3(x, y, z, t)) ∧(R3(x, y, z, t)→ (¬R1(x, y, z, t) ∧ ¬R1(x, y, z, t))]

L’insieme [X]4 e costituito da quaterne non ordinate e quindi l’appartenenza di una qua-terna (a, b, c, d) ad un insieme Ci non dipende dall’ordine in cui i quattro elementi sonopresentati. Anche questo fatto puo essere espresso da una formula di L. Per la relazioneRi abbiamo:

ϕ3,idef= ∀x, y, z, t [(Ri(x, y, z, t)→ (Ri(x, y, t, z) ∧ · · · ∧Ri(z, t, y, x)]

dove nella congiunzione a destra di → compaiono tutte le permutazioni di x, y, z, t.Indichiamo con ϕ3 la formula ϕ3,1 ∧ ϕ3,2 ∧ ϕ3,3.

Ora dobbiamo esprimere il fatto che in NRm viene negato il Teorema di Ramsey nel cason = 5. Cio significa che, considerato un arbitrario insieme Y con 5 elementi, non puosuccedere che tutti i sottoinsiemi di Y con 4 elementi appartengano allo stesso elementodella partizione. Equivalentemente, possiamo dire che, per ogni elemento della partizione,esiste una quaterna ad elementi in Y che non appartiene a quell’elemento. Tenendo pre-sente che gli elementi della partizione vengono rappresentati nel linguaggio dalle relazioniRi, poniamo:

ϕ4,idef= ∀x, y, z, t, w [Dist(x, y, z, t, w)→ ¬(Ri(x, y, z, t) ∨ ¬Ri(x, y, z, w) ∨ . . . ]

56

dove a destra di→ abbiamo la disgiunzione di tutte le formule del tipo ¬Ri(x1, x2, x3, x4)con x1, x2, x3, x4 elementi distinti dell’insieme {x, y, z, t, w}. Si osservi inoltre che laquantificazione “per ogni Y con 5 elementi” viene rappresentata dalla quantificazione∀x, y, z, t, w (con la successiva clausola Dist(x, y, z, t, w)). Indichiamo con ϕ4 la formulaϕ4,1 ∧ ϕ4,2 ∧ ϕ4,3.

Infine, consideriamo la formula che esprime l’esistenza di almeno k oggetti:

ψkdef= ∃x1, . . . , xkDist(x1, . . . , xk)

Poniamo:

Ψk = {ϕ1, . . . , ϕ4, ψk} e Ψ = {ϕ1, . . . , ϕ4} ∪ {ψk : k ∈ N}

Proposizione 10.5 L’insieme Ψk ha modello se e solo se NRk e verificato.

Dimostrazione. Supponiamo che NRk sia verificato e siano X e f l’insieme e la funzioneche lo verificano. Il modello di Ψk avra la forma I = 〈X, I〉, dove dobbiamo definirele interpretazioni RIi delle relazioni Ri. Poniamo RIi = {〈x1, . . . , x4〉 : {x1, . . . , x4} ∈f−1[{i}]}. Per come sono state costruite le formule ϕi abbiamo che esse sono verificateda quell’interpretazione delle Ri. Consideriamo in particolare ϕ4. Dati cinque elementidistinti y1, . . . , y5, possiamo considerare l’insieme Y = {y1, . . . , y5} e gli elementi Zi di[Y ]4, la cui esistenza e stabilita da NRk. Per ogni i abbiamo che la quaterna ordinatacostituita dagli elementi di Zi non appartiene a f−1[{i}] e quindi non appartiene a RIi .Cio significa che anche ϕ4,i e verificata. La formula ψk e verificata in tutte le strutturecon almeno k elementi, quindi anche in quella considerata.

Sia ora I = 〈D, I〉 un’interpretazione in cui le formule in Ψk sono verificate. Allora D haalmeno k elementi e quindi possiamo considerare un suo sottoinsieme X con esattamentek elementi. Siano RIi le interpretazioni in I dei simboli Ri; quindi ogni RIi e un sottoin-sieme di D4. Definiamo la funzione f : [X]4 → {1, 2, 3} tramite: f({a, b, c, d}) = i ⇔〈a, b, c, d〉 ∈ RIi . Poiche in I e verificate ϕ3, f e ben definita (come funzione definita suquaterne non ordinate). Per ϕ1 e ϕ2, f determina in effetti una partizione di [X]4. Infine,per ϕ4 non esistono sottoinsiemi Y di X con 5 elementi tali che f risulti costante su [Y ]4.

Corollario 10.6 Se NRm e verificata per ogni m, allora Ψ ha modello numerabile.

Dimostrazione. Osserviamo che, se un’interpretazione verifica ψk, allora quell’interpre-tazione verifica anche ψk

′per ogni k′ ≤ k. Dalla Proposizione 10.5 e dalle ipotesi segue

quindi che ogni sottoinsieme finito di Ψ ha modello. Per il Teorema di Compattezza, Ψstesso ha modello e, per il Teorema di Lovenheim-Skolem, ha modello numerabile.

Proposizione 10.7 Esiste un naturale m tale che NRm non e verificata.

Dimostrazione. Per il Corollario 10.6, se non vale la tesi possiamo considerare un modellonumerabile I = 〈D, I〉 di Ψ. Non e restrittivo supporre D = N. Come nella dimostrazione

57

della Proposizione 10.5 la funzione f : [N]4 → {1, 2, 3} definita da f({a, b, c, d}) = i ⇔〈a, b, c, d〉 ∈ RIi determina una partizione di [N]4. Il fatto poi che I verifichi ϕ4 implica chenon esiste un insieme Y di naturali con 5 elementi tale che f risulti costante su [Y ]4. Macio contraddice il Teorema 10.4, in base al quale esiste un insieme infinito Y ′ di naturalitale che f e costante su [Y ′]4. Se Y ha 5 elementi ed e contenuto in Y ′, allora f deveessere costante anche su [Y ]4.

Tenendo presente che l’enunciato del Teorema di Ramsey nel caso r = 4, s = 3, n = 5,esprime proprio l’esistenza di unm tale che NRm non e verificata, la proposizione concludela dimostrazione del teorema in quel casa particolare. Il minimo tra questi naturali eR(4, 3, 5). E infine evidente che la dimostrazione puo essere ripetuta per ogni valore dir, s e n. Cio conclude la derivazione del Teorema di Ramsey dalla sua versione infinitaria.

10.1 Prodotti di ultrafiltri e dimostrazione del Teorema di Ram-sey infinito

I risultati di questa sezione sono tratti da [Di Nasso, 2009] dove vengono presentate anchealtre interessanti applicazioni della teoria degli ultrafiltri.

Dati gli ultrafiltri U e V , rispettivamente sugli insiemi X e Y , possiamo definire l’ultrafiltroprodotto U ⊗ V su X × Y . Posto, per A ⊆ X × Y e x ∈ X, Ax = {y ∈ Y : (x, y) ∈ A},definiamo

U ⊗ V = {A ⊆ X × Y : {x : Ax ∈ V} ∈ U} (10.22)

Proposizione 10.8 L’insieme U ⊗ V e un ultrafiltro.

Dimostrazione. Per ogni x ∈ X, ∅x = ∅ 6∈ V e quindi {x : ∅x ∈ V} = ∅ 6∈ U . Da cio segue∅ 6∈ U ⊗ V .

Supponiamo A ∈ U ⊗V e A ⊆ B. Per ogni x ∈ X, Ax ⊆ Bx. Quindi {x : Ax ∈ V} ⊆ {x :Bx ∈ V} e da {x : Ax ∈ V} ∈ U segue {x : Bx ∈ V} ∈ U .

Supponiamo A,B ∈ U⊗V . Osserviamo che {x : Ax ∈ V}∩{x : Bx ∈ V} ⊆ {x : Ax∩Bx ∈V} e (A ∩ B)x = Ax ∩ Bx. Se quindi {x : Ax ∈ V} ∈ U e {x : Bx ∈ V} ∈ U , allora anche{x : (A ∩B)x ∈ V} ∈ U .

Resta da dimostrare che U ⊗ V e massimale. Osserviamo preliminarmente che, per ogniA ⊆ X×Y , (A)x = Ax. Supponiamo A 6∈ U ⊗V . Allora {x : (A)x ∈ V} = {x : Ax ∈ V} ={x : Ax 6∈ V} 6∈ U . Quindi, poiche U e un ultrafiltro, {x : Ax 6∈ V} = {x : Ax ∈ V} ∈ U ,da cui segue A ∈ U ⊗ V .

Esercizio 10.9 Dimostrare che, se U e V sono ultrafiltri non principali, allora ancheU ⊗ V non e principale.

Suggerimento. Se U ⊗ V fosse principale, allora conterrebbe un insieme della forma{〈x, y〉}.

58

Il prodotto di k ultrafiltri sugli insiemi X1 . . . Xk viene definito induttivamente da U1 ⊗· · · ⊗ Uk

def= U1 ⊗ (U2 ⊗ · · · ⊗ Uk). Se X1 = · · · = Xk e U1 = · · · = Uk, tale prodotto viene

indicato con U⊗k.Nel caso in cui X e totalmente ordinato gli elementi di [X]r corrispondono biunivocamenteagli elementi 〈x1, . . . , xr〉 di Xr con x1 < · · · < xr. Poiche gli insiemi che verrannoconsiderati in seguito sono sottoinsiemi di N, useremo quindi la seguente definizione di[X]r (che e equivalente alla precedente).

[X]r = {〈x1, . . . , xr〉 ∈ Xr : x1 < · · · < xr}

Lemma 10.10 Se U e un ultrafiltro non principale su N e X ∈ U , allora [X]r ∈ U⊗r.

Dimostrazione. Per r = 1 poniamo, per ogni A ⊆ X, As = {〈a〉 : a ∈ A}. L’insiemeU⊗1 = {As : A ∈ U} e dunque un ultrafiltro su [X]1 e [X]1 ∈ U⊗1. Supposto il lemmavero per k − 1 abbiamo(

[X]k)n

= {〈n2, . . . , nk〉 : 〈n, n2, . . . , nk〉 ∈ [X]k} = [X ∩ [n+ 1,∞)]k−1

dove [n+ 1,∞) indica l’insieme dei naturali maggiore di n. In particolare, [n+ 1,∞) e uncofinito e quindi appartiene ad U che non e principale. Dunque anche X ∩ [n+1,∞) ∈ U .Per l’ipotesi induttiva [X ∩ [n+ 1,∞)]k−1 ∈ U⊗(k−1) e quindi {n :

([X]k

)n∈ U⊗(k−1)} =

N ∈ U . Per la definizione di prodotto di ultrafiltri abbiamo quindi [X]k ∈ U⊗k.

Lemma 10.11 Se U e un ultrafiltro non principale su N, allora, per ogni r > 0 e ogniA ∈ U⊗r, esiste un sottoinsieme infinito X di N tale che [X]r ⊆ A.

Dimostrazione. (Bozza) Il caso r = 1 e banale. Ci limitiamo a dimostrare il lemmaper r = 2. Negli altri casi la dimostrazione usa sostanzialmente la stessa idea. Dalladefinizione di prodotto di ultrafiltri abbiamo che

A ∈ U⊗2 ⇔ A = {n : An ∈ U} ∈ U (10.23)

Dato h1 ∈ A, Ah1 appartiene ad U e quindi possiamo considerare un h2 > h1 in A ∩ Ah1 ;questa intersezione e infatti infinita come tutti gli elementi di un ultrafiltro non principale.In modo analogo, Ah2 ∈ U e quindi esiste un h3 > h2 appartenente a A ∩ Ah1 ∩ Ah2 . Da(10.23) segue inoltre che le coppie 〈h1, h2〉, 〈h2, h3〉, 〈h1, h3〉 sono tutte in A. Iterandoil procedimento otteniamo una successione infinita h1 < h2 < . . . , < hk < . . . tale cheogni coppia 〈hi, hj〉 con i < j appartiene ad A. Se X e l’insieme degli hi allora abbiamo[X]2 ⊆ A.

Dimostrazione del Teorema di Ramsey infinito (T. 10.4). Sia {C1, . . . , Cs} una partizionedi [N]r. Consideriamo un ultrafiltro non principale U su N. Per il Lemma 10.10, tenendopresente che N ∈ U , [N]r ∈ U⊗r. Dall’uguaglianza [N]r = C1 ∪ · · · ∪ Cs, per le proprietadegli ultrafiltri, segue che esiste i tale che Ci ∈ U , e quindi, per il Lemma 10.23, esiste unX infinito tale che [X]r ⊆ Ci.

APPENDICI

59

A Tautologie

Le tautologie sono le formule che risultano vere per la loro struttura logica (proposizionale).Supponiamo che una formula ϕ sia costruita per mezzo delle formule ϕ1, . . . , ϕn per mezzodegli operatori logici proposizionali ¬, ∧,∨, →, e ↔ (cioe senza usare ∀ o ∃), e che sianoto il valore di verita (V o F) di ϕ1, . . . , ϕn. In tal caso il valore di verita di ϕ puo esseredeterminato induttivamente per mezzo delle cosiddette Tavole di Verita:

ϕ ¬ϕF V

V F

ϕ ψ ϕ ∧ ψ ϕ ∨ ψ ϕ→ ψ ϕ↔ ψF F F F V VF V F V V FV F F V F FV V V V V V

Diciamo che la formula ϕ e una tautologia se risulta avere sempre il valore di verita Vindipendentemente dai valori di verita delle sue componenti ϕ1, . . . , ϕn. Nel caso in cuiil valore di verita di ϕ risulti costantemente F diremo che ϕ e una contraddizione. Dallaprima tabella di verita risulta immediatamente che A e una tautologia se e solo se ¬A euna contraddizione, e viceversa.

Risultano in particola tautologie le formule

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

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

che mostrano come l’operatore di negazione assieme ad un operatore tra ∧,∨,→ sianosufficienti per definire gli altri.

Affermare DL3 (§1.1) equivale a dire che ogni teoria assiomatica T (basata sulla LogicaClassica) viene ritenuta sufficiente ricca da poter dimostrare tutte le tautologie. Affinchequesto avvenga e sufficiente che T abbia tra i suoi assiomi tutte le formule della formaϕ → (ψ → ϕ), (ϕ → (ψ → χ)) → ((ϕ → ψ) → (ϕ → χ)) e (¬ψ → ¬ϕ) → ((¬ψ →ϕ) → ψ), e che tra le Regole di Deduzione di T compaia il Modus Ponens che permettedi dedurre ψ da ϕ → ψ e ϕ.28 Questo risultato e noto come Completezza del CalcoloProposizionale.

Nella pratica matematica usuale gli assiomi che permettono di dimostrare tutte le tautolo-gie non vengono specificati. Vengono solo usate delle tautologie come verita ‘autoevidenti’.

B Insiemi

In questa appendice vedremo, senza dimostrazioni, alcuni risultati e definizioni basilaridi teoria degli insiemi. Per le dimostrazioni, che verranno svolte nella seconda parte delcorso, si puo vedere [Lolli, 1994].

28Oltre a questi assiomi e regole dobbiamo ovviamente assumere che gli operatori ∧,∨ e↔ siano definititramite ¬ e → nel modo indicato sopra.

60

Diciamo che l’insiemeX ha cardinalita minore o uguale all’insieme Y (in simboli card(X) ≤card(Y )) quando esiste una funzione iniettiva da X in Y . Diciamo che X e Y hanno lastessa cardinalita (card(X) = card(Y )) quando esiste una funzione biiettiva da X suY . Con card(X) < card(Y ) intendiamo valgono simultaneamente card(X) ≤ card(Y ) ecard(X) 6= card(Y ).

Le precedenti definizioni forniscono una nozione di cardinalita relativa, nel senso che per-mettono di confrontare la ‘grandezza’ di due insiemi dati. Non viene pero introdotta unanozione assoluta di cardinalita: l’espressione card(X), da sola, non ha nessun significato.Nella seconda parte del corso verra definita una nozione assoluta di cardinalita (Card)associando ad ogni insieme un opportuno insieme cardinale.

Teorema B.1 T. di Cantor-Schroder-Bernstein. Se card(X) ≤ card(Y ) e card(Y ) ≤card(X), allora card(X) = card(Y ).

Diciamo che un insieme X e numerabile se card(X) = card(N). Un insieme e dunquenumerabile se puo essere messo in corrispondenza biunivoca con l’insieme dei numeri na-turali. Cio significa che possiamo scrivere X come {x0, x1, . . . }, possiamo cioe enumerarnegli elementi.

Il numerabile e la piu piccola cardinalita infinita, nel senso che per ogni insieme infinito X,esiste una funzione iniettiva da N in X, cioe card(N) ≤ card(X). Questa disuguaglianzaviene in effetti spesso usata come definizione di insieme infinito.29

Sugli insiemi numerabili possiamo fare molte delle usuali operazioni insiemistiche, otte-nendo ancora insiemi numerabili. Abbiamo per esempio che se X e Y sono numerabili,allora sono numerabili anche gli insiemi X ∪ Y e il prodotto cartesiano X × Y di X e Y .Da cio segue che anche il prodotto cartesiano Xn = X × · · · ×X e numerabile per ogninaturale n > 0. In particolare Z e Q sono insiemi numerabili. Un risultato piu generalesulla numerabilita e il seguente

Proposizione B.2 Se gli insiemi Xi sono finiti o numerabili per ogni i appartenente adun insieme finito o numerabile I di indici, allora anche

⋃i∈I

Xi e finito o numerale.

Esistono insiemi X piu che numerabili, cioe tali che card(N) < card(X). Uno di questiinsieme e ℘(N), l’insieme potenza di N, cioe l’insieme di tutti i sottoinsiemi di N. Ingenerale abbiamo che per ogni insieme X, card(X) < card(℘(X)) (Teorema di Cantor).Un insieme piu che numerabile che incontriamo quotidianamente in matematica e R. Sidimostra infatti che card(℘(N)) = card(R). La seguente proposizione dice sostanzialmenteche operazioni insiemistiche tra insiemi di cardinalita infinita diversa lasciano inalteratala cardinalita maggiore. In particolare il numerabile e trascurabile rispetto al piu chenumerabile.

29Un’altra definizione, piu elegante perche non usa l’insieme dei numeri naturali, e quella dovuta aDedekind: un insieme X e infinito se esiste una corrispondenza biunivoca tra X e un suo sottoinsiemeproprio. Le due definizioni risultano equivalenti.

61

Proposizione B.3 Supponiamo card(X) < card(Y ). Allora

card(X ∪ Y ) = card(X × Y ) = card(Y \X) = card(Y )

Unioni e prodotti cartesiani di insiemi con la stessa cardinalita non variano la cardinalita.Dalla proposizione precedente ricaviamo quindi:

Proposizione B.4 Supponiamo card(X) ≤ card(Y ). Allora

card(X ∪ Y ) = card(X × Y ) = card(Y )

Il Lemma di Zorn, e un principio in Teoria degli Insiemi che non e deducibile dagli usualiassiomi perche equivalente all’Assioma di Scelta. Per enunciare questo principio abbiamobisogno di una definizione.

Definizione B.5 Sia 〈S,�〉 un insieme ordinato. Dato S ′ ⊆ S, diciamo che s ∈ S eun maggiorante per S ′ se s′ � s per ogni s′ ∈ S ′. Diciamo che un elemento s0 di S emassimale se non esiste s ∈ S tale che s0 ≺ s.

Lemma di Zorn Sia 〈S,�〉 un insieme ordinato tale che ogni S ′ ⊆ S totalmente ordinatoda � abbia maggiorante in S. Allora, per ogni s ∈ S esiste un s0 massimale tale ches � s0.

Riferimenti bibliografici

[Bell and Machover, 1977] Bell, J. and Machover, M. (1977). A Course in MathematicalLogic. North-Holland.

[Berarducci, 2006] Berarducci, A. (2006). Corso di teoria dei modelli. Dispensa,http://www.dm.unipi.it/~berardu/Didattica/Appunti/modelli.pdf.

[Boolos and Jeffrey, 1980] Boolos, G. and Jeffrey, R. (1980). Computability and Logic.Cambridge University Press.

[Cohen and Ehrlich, 1963] Cohen, L. and Ehrlich, G. (1963). The Structure of the RealNumber System. van Nostrand.

[Di Nasso, 2009] Di Nasso, M. (2009). Logica matematica 1. Dispensa,http://www.dm.unipi.it/~dinasso/LOMA/loma09a.pdf.

[Enderton, 1972] Enderton, H. (1972). A Mathematical Introduction to Logic. HarcourtAc. Press.

[Feferman, 1964] Feferman, S. (1964). The Number Systems - Foundations of Algebra andAnalysis. Addison-Wesley.

62

[Fiori and Invernizzi, 2009] Fiori, C. and Invernizzi, S. (2009). Numeri Reali. Pitagora.

[Lolli, 1994] Lolli, G. (1994). Dagli insiemi ai numeri. Boringhieri.

[Mendelson, 1981] Mendelson, E. (1981). Introduzione alla Logica Matematica.Boringhieri.

[Piacentini Cattaneo, 1996] Piacentini Cattaneo, G. M. (1996). Algebra - Un approccioalgoritmico. Decibel.

[Zanardo, 2014] Zanardo, A. (2014). Costruzione della struttura dei numeri reali.Dispensa, http://www.math.unipd.it/~azanardo/Fond_Mat/Reali_2013_14.pdf.

Indice analitico

[x]r, 54ℵ0, 18α-categoricita, 18L, 5TN, 23I, 6|=, 7A, 46`, 5AB, 6cI , f

nI , R

nI , 6

adeguatezza, 21algebrici, reali, 20antisimmetria, 3arieta, 5assioma, 2Assioma di Scelta, 61Assiomi di Peano, 22associativita, 2

back-and-forth, 20buon ordinamento, 32

campi ordinati, 3Campi Ordinati Completi, 3campo, 2cardinalita, 60categoricita, 17coerenza, 9cofinito, 46commutativita, 3compatibilita dell’ordine con il prodotto, 3compatibilita dell’ordine con l’addizione, 3compatibilita di ≤ con le operazioni, 3Compattezza Semantica, 14Compattezza Sintattica, 10completezza, 3completezza semantica, 20completezza sintattica, 21consistente, 10contraddittorieta, 9

contraddizione, 10, 59

decidibilita, 12densita, 4dipendenza, 11distributivita, 3dominio, 6

eliminazione dei quantificatori, 44enunciato, 6

filtro, 47filtro di Frechet, 47filtro principale, 47finitamente assiomatizzabile, 43forma normale prenessa, 44

gruppi, 2

immediato predecessore, 33immediato successore, 33indipendenza, 11Induzione, Definizione per, 25, 27insieme potenza, 60insiemi definibili, 36interpretazione, 6isomorfismo, 16

Lowenheim-Skolem, 15Lemma di Zorn, 61letterale, 44libera, variabile, 6linearita, 3linguaggi del primo ordine, 5linguaggio formale, 4

maggiorante, 61massimale, 61modelli non-standard, 38modello, 9modello standard, 36

naturali (non) standard, 38numerabile, insieme, 60

63

64

numerale, 37Numero di Ramsey, 54

ordine totale, 3

piu che numerabile, insieme, 60predecessore, 24primo ordine, quantificazione, 4Principio d’Induzione, 23Principio di Induzione, seconda forma, 32prodotto di naturali, 30prodotto diretto, 48proprieta dell’intersezione finita, 47

Ramsey, Teorema, 54regole di verita, 7riflessivita, 3

secondo ordine, quantificazione, 4segnatura, 5soddisfacibile, 9somma di naturali, 28successore, 24

tautologia, 59tavole di verita, 59teorema, 2Teorema di Los, 51termini, 5totalita, 3transitivita, 3trascendenti, reali, 20

ultrafiltro, 47ultrafiltro principale, 47ultrafiltro prodotto, 57ultrapotenza, 51ultraprodotto, 51

valutazione, 7vincolata, variabile, 6