Logica Classica, Teoria degli insiemi, Teoria deiModelli e Algebra

Simone Camosso∗

∗Address: Via Carlo Alberto 10, Torino, e-mail: r.camosso@alice.it

“La Matematica e la scienza che traccia le conclusioni necessarie.”B.Peirce

“La matematica, nel suo significato piu ampio, e lo sviluppo di tutti i tipi diragionamenti, formali e deduttivi.”

A.N.Whitehead

“La matematica e un metodo logico. Le proposizioni matematiche non esprimonopensieri. Nella vita non avremo mai bisogno di una proposizione matematica; usiamole proposizioni matematiche solo per dedurre da proposizioni che non appartengonoalla matematica altre che ugualmente non vi appartengono.”

L. Wittgenstein, in “Tractatus Logico Philosophicus”

“La matematica pura e la classe di tutte le proposizioni della forma “p implicaq”, dove p e q sono proposizioni contenenti una o piu variabili, le stesse nelle dueproposizioni, e ne p ne q contengono alcuna costante eccetto costanti logiche. [...]Oltre a queste, la matematica adopera poi una nozione che non entra come costituentenelle proposizioni da essa considerate, e precisamente la nozione di verita.”

B.Russell, “I principi della Matematica”

“Il motore dell’invenzione matematica non e la ragione ma l’immaginazione.”A.De Morgan

“L’algebra e generosa, spesso ti da molto di piu di quello che le hai chiesto.”D’Alembert

Introduzione

Alcune note tratte dal Corso di Istituzioni di Logica (Prof. Andretta Alessandro), An-no accademico 2010-2011. Vengono trattati argomenti come Logica Classica, Teoriadei Modelli, Strutture Matematiche e Teoria degli insiemi.

Indice

1 Linguaggi e strutture 11.1 Sistema assiomatico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Linguaggi del primo ordine . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Strutture di un linguaggio . . . . . . . . . . . . . . . . . . . . . . . . 61.4 Teorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5 Assiomatizzabilita e definibilita . . . . . . . . . . . . . . . . . . . . . 121.6 Formalizzazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.7 Tautologie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.8 Forma prenessa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2 Teoria degli insiemi 222.1 Antinomia di Russel . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2 Classi,insiemi e classi proprie . . . . . . . . . . . . . . . . . . . . . . . 232.3 Assiomi e linguaggio della teoria degli insiemi . . . . . . . . . . . . . 232.4 Successioni e assioma della scelta . . . . . . . . . . . . . . . . . . . . 282.5 Insiemi ordinati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.6 Ordinali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342.7 Cardinali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3 Funzioni ricorsive 413.1 Ricorsione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.2 Funzioni continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.3 Aritmetica ordinale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.4 Aritmetica cardinale . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4 Gli interi, i razionali ed i reali 574.1 Gli assiomi di Peano . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.2 Gli interi e i razionali . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.3 I numeri reali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.4 L’insieme di Cantor e il prodotto di spazi di Cantor . . . . . . . . . . 60

5 Algebre di Boole 615.1 Anelli Booleani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

3

6 Forme deboli dell’assioma della scelta 646.1 Assioma delle scelte numerabili . . . . . . . . . . . . . . . . . . . . . 646.2 La misura di Lebesgue . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7 Teorema di completezza 677.1 Problema della riduzione . . . . . . . . . . . . . . . . . . . . . . . . . 677.2 Teorema di completezza . . . . . . . . . . . . . . . . . . . . . . . . . 687.3 Dimostrazione del teorema di completezza . . . . . . . . . . . . . . . 69

8 Teoria dei modelli 738.1 Teorema della compattezza . . . . . . . . . . . . . . . . . . . . . . . . 738.2 Teorema di Skolem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

9 Gruppi, Anelli, Sottoanelli e Campi 789.1 Teorema di isomorfismo per i gruppi . . . . . . . . . . . . . . . . . . 789.2 Teorema di isomorfismo per gli anelli . . . . . . . . . . . . . . . . . . 799.3 Estensioni di campi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

Bibliografia 83

Capitolo 1

Linguaggi e strutture

1.1 Sistema assiomatico

Per stabilire nuovi risultati la matematica utilizza il metodo assiomatico. In que-sto metodo bisogna esibire una dimostrazione, cioe una successione di ragionamentipartendo da affermazioni di partenza detti assiomi. Questi assiomi o postulati sonoaffermazioni vere poiche evidenti. I teoremi sono affermazioni che dimostro partendodagli assiomi. Bisogna tenere presente che i teoremi, le congetture e le affermazioniin matematica sono formulate partendo da un linguaggio che viene fissato in modoesplicito o implicito. In generale un linguaggio formale e stabilito dai simboli e dalleespressioni. Una espressione e una sequenza finita di simboli. Le formule sono inve-ce espressioni dotate di significato. Un linguaggio formale e determinato quando siconoscono i simboli e le formule. Indichiamo un linguaggio formale con la notazioneL(F ). Un sistema formale F e costituito da un linguaggio formale L(F ), un elencodi formule del linguaggio L(F ) detti postulati e delle regole di inferenza. La regolae una meccanismo che mi permette di inferire formule (conclusioni) da altre formule(ipotesi di una regola). I teoremi all’interno di un sistema formale F vengono definitiin modo induttivo, ovvero un assioma e un teorema di F , se le ipotesi di una regoladi F sono teoremi di F allora la conclusione e un teorema di F . Quindi parto daun insieme di assiomi che indico con S0. In S1 ho le conclusioni di ipotesi in S0.In S2 ho conclusioni di ipotesi in S0 ∪ S1, cosı via, in Sn+1 ho conclusioni di ipotesiin Sn ∪ · · · ∪ S0. In Sω conclusioni con ipotesi in qualche Sn. Cosı via fino a chenon ottengo piu nuovi teoremi. Se le ipotesi sono in numero finito mi arresto a Sω.Per dimostrare che ogni teorema di F gode di una certa proprieta P , e sufficientedimostrare che ogni assioma gode della proprieta P e che se le ipotesi di una regolagodono della proprieta P allora anche le conclusioni godono della proprieta P .

Esempio 1.1.1. Il sistema MIU (Godel,Escher,Bach) 1979, in cui ho tre simboliM, I, U , quattro regole:R1 da vI inferisco vIUR2 da Mv inferisco MvvR3 da vIIIw inferisco vUw

1

R4 da vUUw inferisco vwe un assioma MI.

Esempio 1.1.2. Il sistema preso dal Kaye The Logic of Mathematics 2007, in cuiho due simboli 0, 1, tre regole:R1 da v inferisco v0R2 da v inferisco v1R3 da v0 e v1 inferisco ve un insieme di assiomi Σ (eventualmente infinito).

Se in una espressione compare un’altra espressione diremo che la seconda occorrenella prima.

1.2 Linguaggi del primo ordine

Un linguaggio del primo ordine e costituito da:

1)x, y, z, t, u, w, · · · variabili2)un simbolo di uguaglianza =3)¬,∨,∃4)per ogni n ≥ 0 dei simboli di funzione n-ario o predicato n-ario.

Un simbolo di funzione o predicato diverso da = e detto simbolo non logico. Ri-sulta opportuno definire nuovi simboli che abbreviano certe espressioni:

A ∨B abbrevia ∨AB.A⇒ B abbrevia ¬A ∨B.A ∧B abbrevia ¬(A⇒ ¬B).∀xA abbrevia ¬∃¬xA.A⇔ B abbrevia (A⇒ B) ∧ (B ⇒ A).aub con u binario abbrevia uab.a 6 ub con u binario abbrevia ¬(aub).

Questi simboli potevano essere introdotti gia all’inizio ma invece viene fatto oraperche si vuole utilizzare un linguaggio “ minimale, ovvero solo lo stretto necessario.Questi simboli:

¬,∨,∧,⇒,⇔si chiamano connettivi logici. Sono utili per formalizzare in modo non ambiguo iragionamenti matematici. Mentre i simboli:

∃, ∀si chiamano quantificatori. I connettivi e i quantificatori vengono detti costantilogiche.

Osservazione 1. Nel dare i simboli del linguaggio si tenga presente che ci sono anchedei simboli di costante che corrispondo alle funzioni 0-arie.

Per dimostrare A∧B e sufficiente dimostrare A e dimostrare B. Questo si esprimegraficamente:

A B

A ∧BViceversa, da A ∧B posso dedurre tanto A quanto B, cioe:

A ∧BA

A ∧BB

. (1.2.1)

Se si possiede una dimostrazione di A si puo indebolire il risultato asserendo A∨B,per qualsiasi affermazione B. Analogamente da B si deduce A ∨B:

A

A ∨BB

A ∨B.

Viceversa a partire da A ∨B non e possibile ne concludere A che B. Se abbiamoA∨B e sappiamo negare una delle due affermazioni A e B, allora concludiamo l’altra:

A ∨B ¬AB

A ∨B ¬BA

. (1.2.2)

Supponendo che valga A, allora non possiamo asserire ¬A, altrimenti ho unacontraddizione, quindi concludo ¬¬A. Viceversa supponiamo ¬¬A, se per assurdo Anon valesse concluderemmo ¬A da cui una contraddizione. Questa e la regola delladoppia negazione:

A

¬¬A¬¬AA

. (1.2.3)

Questo e un esempio di dimostrazione per assurdo: se si vuole dedurre A da certeipotesi e sufficiente aggiungere ¬A alle ipotesi e dimostrare una contraddizione, cioeuna affermazione del tipo B ∧ ¬B. Possiamo dimostrare le leggi di De Morgan, valea dire:

A ∧B¬(¬A ∨ ¬B)

A ∨B¬(¬A ∧ ¬B)

. (1.2.4)

Dimostrazione. Suppongo A ∧ B e, per assurdo assumiamo ¬A ∨ ¬B. Per (1.2.1)otteniamo A da A∧B e applicando la regola della doppia negazione (1.2.3) otteniamo¬¬A. Quindi applicando la (1.2.2) a ¬A ∨ ¬B otteniamo ¬B. Poiche B segue daA ∧ B per (1.2.1), otteniamo una contraddizione e concludiamo ¬(¬A ∧ ¬B) comerichiesto. L’altra legge si dimostra in modo analogo.

Inoltre scrivere ¬(A ⇒ B) significa dire che A vale ma B non vale. Cioe questoe equivalente a dire A ∧ ¬B che, per De Morgan, e equivalente a (¬(¬A ∨ B)). La

regola (1.2.2) puo essere riformulata per l’implicazione cosı da A⇒ B e A deduco B.Questa regola prende il nome di Modus Ponens e la si descrive cosı:

A⇒ B A

B. (1.2.5)

Quando si scrive ∃xA o ∀xA implicitamente intendiamo che A stia affermandoqualche proprieta di x. Negare ∀xA significa dire che non tutti gli x godono dellaproprieta descritta da A cioe esiste almeno un x per cui vale ¬A. Viceversa, seneghiamo ∃xA allora vuol dire che non si da il caso che ci sia un x per cui vale A,cioe ∀x vale ¬A. Quindi:

¬∀xA∃x¬A

¬∃xA∀x¬A

.

E’ possibile considerare piu quantificatori. Ad esempio se i quantificatori sonotutti dello stesso tipo e indifferente l’ordine in cui compaiono, cioe:

∃x∃yA∃y∃xA

∀x∀yA∀y∀xA

.

Un’altra regola e la seguente:

∃x∀yA∀y∃xA

infatti se troviamo un x tale che per ogni y vale A allora se scelgo un y arbitrarioposso sempre trovare un x tale che A: basta prende x. Questa regola non puo essereinvertita. Il quantificatore esistenziale si distribuisce rispetto alla disgiunzione nelseguente modo:

(∃xA) ∨ (∃xB)

∃x(A ∨B)

∃x(A ∨B)

(∃xA) ∨ (∃xB).

Per il quantificatore esistenziale con la congiunzione vi e solo una regola:

∃x(A ∧B)

(∃xA) ∧ (∃xB).

Il viceversa non vale, infatti dal fatto che c’e un numero pari e c’e un numerodispari non possiamo concludere che esista un numero che e tanto pari quanto dispari.Analoghe distribuzioni per il quantificatore universale vengono pero invertite:

(∀xA) ∧ (∀xB)

∀x(A ∧B)

∀x(A ∧B)

(∀xA) ∧ (∀xB).

Parzialmente rispetto alla disgiunzione:

(∀xA) ∨ (∀xB)

∀x(A ∨B).

Osservazione 2. Se A non afferma nessuna proprieta di x allora il significato di∀xA e ∃xA sono come quello di A.

I termini vengono definiti in modo induttivo come segue.

1)Una variabile e un termine.2)Se u1, · · · , un sono termini e f e n-aria allora fu1 · · ·un e un termine.

Definizione 1.2.1. Se t1, · · · , tn sono termini e P e un simbolo di predicato n-aria,allora Pt1 · · · tn e detta formula atomica.

Possiamo definire le formule in modo induttivo.

1)La formula atomica e una formula.2)Se A e una formula allora ¬A e una formula.3)Se A e B sono formule, allora ∨AB e una formula.4)Se A e una formula e x variabile allora ∃xA e una formula.

Definizione 1.2.2. Un’occorrenza di una variabile x in una formula A si dice:

1)vincolata se occorre in una parte di A della forma ∃xB,2)libera altrimenti.

Esempio 1.2.1. In

∃y(x = y)

y e vincolata, x libera.

Esempio 1.2.2. In

∃x(x = x) ∧ (x = y)

la x in ∃x(x = x) non e libera mentre in (x = y) sono entrambe libere.

Se y e distinta da x, allora le occorrenze libere di x in ¬A,∨AB, ∃yB sono occor-renze di x in A. Se a, b sono termini, A una formula e x una variabile si ha che bx[a] el’espressione ottenuta sostituendo le occorrenze di x in b con a. Analogamente Ax[a]e l’espressione ottenuta sostituendo le occorrenze di x in A con a.

Osservazione 3. La sostituzione avviene sempre tra un termine a una variabile.

Definizione 1.2.3. a e sostituibile ad x in A se e solo se per ogni variabile y di anessuna parte della forma ∃yB di A contiene un’occorrenza di x che risulta libera inA.

Scrivendo Ax[a] si intende che la a e sostituibile.

Esempio 1.2.3. x e sempre sostituibile a se stesso Ax[x] e A.

Esempio 1.2.4. Se a non contiene variabili e sempre sostituibile.

Esempio 1.2.5. Una y che non occorre in A e sostituibile ad x in A.

Esempio 1.2.6. Sia A la formula

∃y(x = 2y)

dice che x e pari. Ax[z] dice che z e pari ma, Ax[y+ 1] cioe ∃y(y+ 1 = 2y) non diceche y + 1 e pari!. Il termine y + 1 non e sostituibile.

Osservazione 4. Se a1, · · · , an e b sono termini, A una formula e x1, · · · , xn so-no variabili: bx1···xn [a1, · · · , an] e l’espressione ottenuta sostituendo le occorrenze dix1, · · · , xn in b con a1, · · · , an. Analogamente Ax1···xn [a1, · · · , an] e l’espressione otte-nuta sostituendo le occorrenze libere di x1, · · · , xn in A con a1, · · · , an, con a1, · · · , ansostituibili in A.

La sostituzione deve essere simultanea.

1.3 Strutture di un linguaggio

Fissiamo un linguaggio del primo ordine L. Una L-struttura A o semplicementestruttura consiste di:

1)un insieme non vuoto |A| detto universo o dominio di A, in cui sono presentigli individui2)degli elementi privilegiati di |A|, uno per ogni simbolo di costante3)per ogni simbolo di funzione f n-aria del linguaggio una funzione n-aria fA : |A|n →|A|4)per ogni simbolo di predicato P n-ario del linguaggio un predicato n-ario PA ⊆ |A|n.

Definizione 1.3.1. Una formula che non contiene variabili libere si dice enunciato.

Una formula che contiene variabili libere non e necessariamente vera o falsa inuna struttura A. Per esempio x = 0 non e ne vera ne falsa, dipende da cosa denotala x. Viceversa un enunciato o e vero o e falso in una struttura A. Scrivo:

A |= A.

Per dire che A soddisfa A, cioe A e modello di A, cioe A e vero in A. Fissatauna struttura cioe, una L-struttura A, ad ogni elemento a ∈ |A| associo una nuovacostante,detta nome di a. Oggetti, individui distinti hanno nomi distinti. Aggiungo

ad L tutti questi nomi ed ottengo il linguaggio L(A). Se a e un termine chiuso diL(A), definisco A(a) ∈ |A| per induzione sulla complessita di a:

1)se a e il nome di a ∈ |A|, allora A(a) = a altrimenti se a e fa1 · · · an con a1, · · · , antermini chiusi. Allora:

A(a) = fA(A(a1), · · · ,A(an)).

In particolare se n = 0 cioe a e simbolo di costante f del linguaggio L, allora A(a)e l’elemento fA di A.

Definizione 1.3.2. Un valore A(A) ∈ 0, 1 per ogni enunciato A, per induzionesulla complessita di A:1)Se A e a = b, allora A(A) = 1⇔ A(a) = A(b).2)Se A e Pa1 · · · an con P simbolo di predicato n-ario, allora A(A) = 1 se e solo se(A(a1), · · · ,A(an)) ∈ PA.3)Se A e ¬B allora A(A) = 1 ( o equivalentemente A |= A) se e solo se A(B) = 0.4)Se A e ∃xB, allora A(A) = 1 se e solo se A(Bx[c]) = 1 per qualche nome c.5)Se A e B ∨ C allora A(A) = H∨(A(B),A(C)).

Osservazione 5. H e una funzione di verita H : 0, 1n → 0, 1.

In modo analogo si definiscono i valori di A1 ∨ · · · ∨ An, A ∧ B,A ⇒ B, ∀xA · · · ,ad esempio A(A1 ∨ · · · ∨ An) = 1 se e solo se A(Ai) = 1 per qualche i = 1, · · · , n.

Lemma 1.3.1. Sia A una L-struttura, a un termine chiuso di L(A), c un nomedell’individuo A(a) (cioe A(a) = A(c)).1)Se b e un termine che non ha variabili libere, se non eventualmente x, alloraA(bx[a]) = A(bx[c]).2)Se A e una formula di L(A) che non ha variabili libere, se non eventualmente x,allora A(Ax[a]) = A(Ax[c]).

Dimostrazione. Prima si procede per induzione sulla lunghezza di b e poi per indu-zione sulla lunghezza di A.

Osservazione 6. Se x1, x2 sono distinte, b, a1, a2 sono termini sostituibili per x1 ex2 nella formula A tale che x2 non occorre in a1, allora

1)bx1x2 [a1, a2] e (bx1 [a1])x2 [a2].2)Ax1x2 [a1, a2] e (Ax1 [a1])x2 [a2].

Da ora in avanti i nomi verranno indicati normalmente come gli individui per nonappesantire il formalismo. Se A e una formula con variabili libere x1, · · · , xn e se

c1, · · · , cn sono nomi di individui in A, dico che A e vera in A tramite l’assegnazionec1, · · · , cn se e solo se:

A(Ax1···xn [c1, · · · , cn]) = 1.

Per abbreviare A |= A[c1, · · · , cn], l’enunciato A[c1, · · · , cn] e detto A-esempio diA. Una formula A e valida in A se ogni suo A-esempio e vero in A. Ci sono for-mule di L che sono valide in ogni L-struttura A, ad esempio x = x. Una formulae conseguenza logica di un insieme di formule se e solo se la formula e vera in ogniL-struttura in cui sono vere tutte le formule dell’insieme considerato. Quello che sidesidera e che prendendo un insieme di postulati, cioe delle formule e se A soddisfatutte queste formule allora deve soddisfare tutti i teoremi che si ottengono partendoda questi assiomi. Abbiamo quindi:1)Un assioma proposizionale della forma ¬A ∨ A.2)Un assioma di sostituzione della forma Ax[a]⇒ ∃xA.3)Un assioma di identita della forma x = x.4)Un assioma di uguaglianza e della forma:

x1 = y1 ⇒ · · · ⇒ xn = yn ⇒ fx1 · · ·xn = fy1 · · · ynoppure

x1 = y1 ⇒ · · · ⇒ xn = yn ⇒ Px1 · · ·xn ⇒ Py1 · · · yn.

Ogni assioma logico deve essere tra queste tipologie. Si verifica che sono validi inogni A. Ad esempio per gli assiomi di sostituzione, considero un A-esempio dell’as-sioma di sostituzione Ax[a] ⇒ ∃xA e supponiamo che A(Ax[a] ⇒ ∃xA) = 0. AlloraA(Ax[a]) = 1 e A(∃xA) = 0. Se c e il nome di A(a), allora A(Ax[c]) = 0 contro illemma precedente. Vediamo adesso le regole di inferenza o regole logiche.

1)Regola di espansione, inferire B ∨ A da A.2)Regola di contrazione, inferire A da A ∨ A.3)Regola associativa, inferire (A ∨B) ∨ C da A ∨ (B ∨ C).4)Regola di taglio, inferire B ∨ C da A ∨B e ¬A ∨ C.5)Regola di ∃ introduzione: se x non e libera in B, inferire ∃xA⇒ B da A⇒ B.Sono finitarie.

Osservazione 7. La regola di taglio viene giustificata osservando che ¬A∨C risultauguale a A⇒ C mentre A∨B risulta la stessa di B ∨A poiche ipotizzo di sapere chevale la commutativita quindi ¬B ⇒ A quindi per transitivita ¬B ⇒ C ovvero B ∨C.

Le regole preservano la validita logica ovvero le conclusioni discendo logicamentedalle ipotesi. Verifico solo per ∃ introduzione, suppongo A ⇒ B sia vera in A e xnon occorre libera in B. Per assurdo sia ∃xA′ ⇒ B′ un A-esempio di ∃xA⇒ B taleche

A(∃xA′ ⇒ B′) = 0.

Quindi A(∃xA′) = 1 e A(B′) = 0. Sia c un nome per cui A(A′x[c]) = 1 quindiA(A′x[c]⇒ B′) = 0. Dato x non libera in B e quindi neppure in B′ segue A′x[c]⇒ B′

e un A-esempio di A⇒ B. Assurdo (ho trovato un esempio falso di A⇒ B suppostovero).

1.4 Teorie

Definizione 1.4.1. Una teoria del primo ordine e un sistema formale T tale che:1)Il linguaggio di T e del primo ordine L(T ).2)Gli assiomi di T sono assiomi logici L(T ), piu certi assiomi detti non logici.3)Le regole di T sono le solite (espansione, taglio, associativita, contrazione, ∃-introduzione).

Osservazione 8. Una teoria e nota quando si conoscono tutti i simboli non logici egli assiomi non logici.

Facciamo ora degli esempi di teorie.

Esempio 1.4.1 (Teoria dei gruppi (in notazione moltiplicativa)). Il linguaggio dellateoria dei gruppi ha come simboli non logici: 1 (o e) funzione 0-aria, ()−1 (o i) fun-zione 1-aria, · funzione 2-aria. Gli assiomi non logici sono:

∀x∀y∀z(((x · y) · z) = (x · (y · z)))∀x(x · 1 = x ∧ 1 · x = x)∀x(x · x−1 = 1 ∧ x−1 · x = 1)

che possono essere scritti anche come formule aperte, senza quantificatori:

(((x · y) · z) = (x · (y · z)))(x · 1 = x ∧ 1 · x = x)(x · x−1 = 1 ∧ x−1 · x = 1)

Esempio 1.4.2 (Teoria dei gruppi abeliani (in notazione additiva)). Il linguaggiodella teoria dei gruppi abeliani ha come simboli non logici: 0 (o e) funzione 0-aria,− (o i) funzione 1-aria, + funzione 2-aria. Gli assiomi non logici sono:

∀x∀y∀z(((x+ y) + z) = (x+ (y + z)))∀x(x+ 0 = x ∧ 0 + x = x)∀x(x+ (−x) = 0 ∧ (−x) + x = 0)∀x∀y((x+ y) = (y + x))

Esempio 1.4.3 (Teoria degli anelli). Il linguaggio della teoria degli anelli ha comesimboli non logici: 1, 0 funzioni 0-arie, − funzione 1-aria, ·,+ funzioni 2-arie. Gliassiomi non logici sono:

∀x∀y∀z(((x+ y) + z) = (x+ (y + z)))∀x(x+ 0 = x ∧ 0 + x = x)∀x(x+ (−x) = 0 ∧ (−x) + x = 0)∀x∀y((x+ y) = (y + x))∀x∀y∀z(((x · y) · z) = (x · (y · z)))∀x(x · 1 = x ∧ 1 · x = x)∀x∀y∀z((x+ y) · z = (x · z) + (y · z))∀x∀y((x · y) = (y · x))

Esempio 1.4.4 (Teoria dei campi). Il linguaggio della teoria dei campi ha comesimboli non logici: 1, 0 funzioni 0-arie, − funzione 1-aria, ·,+ funzioni 2-arie. Gliassiomi non logici sono:

∀x∀y∀z(((x+ y) + z) = (x+ (y + z)))∀x(x+ 0 = x ∧ 0 + x = x)∀x(x+ (−x) = 0 ∧ (−x) + x = 0)∀x∀y((x+ y) = (y + x))∀x∀y∀z(((x · y) · z) = (x · (y · z)))∀x(x · 1 = x ∧ 1 · x = x)∀x∀y∀z((x+ y) · z = (x · z) + (y · z))∀x∀y((x · y) = (y · x))0 6= 1∀x(x 6= 0⇒ ∃y(x · y = 1))

Esempio 1.4.5 (Teoria dei campi ordinati). Il linguaggio della teoria dei campi or-dinati ha come simboli non logici: 1, 0 funzioni 0-arie, − funzione 1-aria, ·,+, <funzioni 2-arie. Gli assiomi non logici sono:

∀x∀y∀z(((x+ y) + z) = (x+ (y + z)))∀x(x+ 0 = x ∧ 0 + x = x)∀x(x+ (−x) = 0 ∧ (−x) + x = 0)∀x∀y((x+ y) = (y + x))∀x∀y∀z(((x · y) · z) = (x · (y · z)))∀x(x · 1 = x ∧ 1 · x = x)∀x∀y∀z((x+ y) · z = (x · z) + (y · z))∀x∀y((x · y) = (y · x))0 6= 1∀x(x 6= 0⇒ ∃y(x · y = 1))¬∃x(x < x)

∀x∀y∀z(x < y ∧ y < z ⇒ x < z)∀x∀y(x < y ∨ x = y ∨ y < x)

inoltre ci sono assiomi che garantiscono la compatibilita dell’ordinamento con leoperazioni algebriche

∀x∀y∀z(x < y ⇒ x+ z < y + z)∀x∀y∀z(x < y ∧ 0 < z ⇒ x · z < y · z)

Esempio 1.4.6. Se abbiamo la teoria dei campi ordinati e una struttura A, dire chela struttura A soddisfa un enunciato σ di L significa che se sostituiamo i simboli0, 1,+, ·,−, < con delle costanti, le operazioni e la relazione di A e se restringiamoi quantificatori ad A, otteniamo una affermazione vera in A. Per esempio dire che(|A|,+A, ·A,−A, <A, 0A, 1A) soddisfa

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

equivale

∀x ∈ |A|(x 6= 0A ⇒ ∃y ∈ |A|(x ·A y = 1A))

(attenzione! la formula scritta sopra non e una formula del linguaggio a causa delsimbolo ∈ e denominata pertanto pseudo-formula.)

Esempio 1.4.7 (Teoria dei numeri di Robinson Q). Il linguaggio della teoria dei nu-meri ha come simboli non logici: 0 funzione 0-aria, S funzione 1-aria, ·,+ funzioni2-arie.Gli assiomi non logici sono:

S(x) 6= xS(x) = S(y)⇒ x = yx+ 0 = xx+ S(y) = S(x+ y)x · 0 = 0x · S(y) = x · y + x¬(x < 0)x < S(y)⇔ x < y ∨ x = yx < y ∨ x = y ∨ y < x

(non sono scritti come enunciati ma come formule aperte).

Definizione 1.4.2. Un modello di una teoria T e una struttura che soddisfa tutti gliassiomi di T .

Una formula e valida in T teoria se e vera in tutti i modelli di T . I gruppi sonomodelli della teoria dei gruppi. La formula (xy)−1 = y−1x−1 e valida nella teoria dei

gruppi mentre x · y = y · x non in generale. Un modello della teoria dei numeri e Ncon S : N→ N e S(n) = n+ 1 e con simboli 0,+, · e <.

Teorema 1.4.1 (Validita). Sia T una teoria, allora ogni teorema di T e valido in T .

Dimostrazione. Per induzione si dimostra che ogni teorema di T e valido in Amodellodi T . Fisso A modello di T .1)Se A e assioma logico e valido in ogni L-struttura in particolare in A.2)Se A e assioma di T , A vale in A.3)Se A e conclusione di una regola le cui premesse sono valide in A allora e vera inA.

Esempio 1.4.8. Modelli per gruppi abeliani sono (Z,+), (Q,+), (R,+), (C,+) in no-tazione additiva. Altri modelli sono (Q\0, ·), (R\0, ·), (C\0, ·), (R>0, ·), (µn, ·), (Zn,+)dove µn e l’insieme delle radici ennesime dell’unita.

Esempio 1.4.9 (Sottogruppi). E’ possibile parlare di sottogruppi aggiungendo unsimbolo di predicato unario P (x) al linguaggio dei gruppi ottenendo un linguaggioLH . Le LH-strutture hanno la forma (G, ·,−1 , 1, H) e se queste soddisfano gli assiomiper i gruppi e

∀x, y(H(x) ∧H(y)⇒ H(x · y−1))

allora stiamo considerando dei gruppi dotati di un sottogruppo privilegiato. Sevogliamo dire che questo sottogruppo e normale e non banale utilizziamo l’enunciato:

∀x, y(H(x)⇒ H(y · x · y−1)) ∧ ∃x(x 6= 1 ∧H(x)) ∧ ∃x¬H(x)

Esempio 1.4.10. Modelli per gli anelli commutativi sono (Z,+, ·), (Zn,+, ·).

Esempio 1.4.11. Modelli per i campi sono (Q,+, ·), (R,+, ·), (C,+, ·), (Zp,+, ·) dovep e un numero primo.

Esempio 1.4.12. Gli insiemi Z[X],Q[X],R[X],C[X],Zn[X] dei polinomi a coeffi-cienti nei rispettivi anelli, risultano modelli di anelli commutativi con unita rispettole usuali operazioni di somma e prodotto. L’unita e il polinomio costante 1.

1.5 Assiomatizzabilita e definibilita

Una collezione di L-strutture si dice assiomatizzabile (al primo ordine) se e la colle-zione dei modelli di un qualche insieme Σ di L-enunciati. Se Σ puo essere preso finitodiremo che e finitamente assiomatizzabile (al primo ordine). In maniera equivalente:una collezione di L-strutture e finitamente assiomatizzabile se e solo se e la collezionedi tutti i modelli di un enunciato σ.

Definizione 1.5.1. Un sottoinsieme X di |A|n con A struttura e definibile se esisteuna qualche formula che lo definisce.

Esempi di sottoinsiemi definibili sono i seguenti.

Esempio 1.5.1. Il centro Z(G) di un gruppo G, e definito dalla formula ∀y(y · x =x · y)

Esempio 1.5.2. Il sottogruppo banale 1 e definito da ∀y(y = x · y ∧ y = y · x) oanche da x = x · x.

Vediamo un esempio di insieme non definibile.

Esempio 1.5.3. La torsione

∃n ∈ N(xn = 1)

e una pseudo-formula, ma non e una formula del nostro linguaggio, per via dellaquantificazione sui naturali, se tentassimo di sostituire ∃n ∈ N con una disgiunzionedel tipo

(x2 = 1) ∨ (x3 = 1) ∨ · · ·

otterremmo una stringa infinita di simboli di nuovo non una formula. Quindi nonpossiamo concludere che:

Tor(G) = x ∈ G|∃n ∈ N(xn = 1)

l’insieme degli elementi di torsione di G, sia definibile nel nostro linguaggio.

1.6 Formalizzazioni

Vediamo come formalizzare in un linguaggio L delle affermazioni di matematica.

Esempio 1.6.1. Formalizza: “ Un elemento non nullo ha un inverso” . L ha comesimboli 0, 1, ·.

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

“ Un” significa “ per ogni” e x 6= 0 sta per ¬(x = 0). “ Un x tale che P (x) e · · · ”si formalizza ∀x(P (x) ⇒ (· · · )) e non ∀x(P (x) ∧ (· · · ))! ∀x(x 6= 0 ∧ ∃y(x · y = 1))significa: “ ogni numero e non nullo e ha un inverso.” La negazione di “ Un x taleche P (x) e (· · · )” e “ C’e un x tale che P (x) e non (· · · )” ∃x(P (x) ∧ ¬(· · · )).

Esempio 1.6.2. “ C’e un unico x tale che P (x)” si formalizza ∃x(P (x)∧∀y(P (y)⇒x = y)) oppure ∃xP (x) ∧ ∀x∀y(P (x) ∧ P (y)⇒ x = y) oppure ∃x∀y(P (y)⇔ x = y).

∀x∀y(P (x) ∧ P (y)⇒ x = y) non e sufficiente!

Esempio 1.6.3. “ f g ha un punto fisso” si formalizza ∃x∃y(f(x) = y ∧ g(y) = x).

Esempio 1.6.4. “ Ci sono almeno tre elementi per cui vale P” si formalizza come:

∃x1∃x2∃x3(P (x1) ∧ P (x2) ∧ P (x3) ∧ x1 6= x2 ∧ x2 6= x3 ∧ x1 6= x3)

Esempio 1.6.5. “ Ci sono al piu tre elementi per cui vale P” e equivalente allanegazione di “ Ci sono almeno quattro elementi per cui vale P” cioe

∀x1∀x2∀x3∀x4(¬P (x1) ∨ ¬P (x2) ∨ ¬P (x3) ∨ ¬P (x4)∨

∨x1 = x2 ∨ x1 = x3 ∨ x1 = x4 ∨ x2 = x3 ∨ x2 = x4 ∨ x3 = x4)

Utilizzando De Morgan:

∀x1∀x2∀x3∀x4(P (x1) ∧ P (x2) ∧ P (x3) ∧ P (x4)⇒

x1 = x2 ∨ x1 = x3 ∨ x1 = x4 ∨ x2 = x3 ∨ x2 = x4 ∨ x3 = x4)

Le espressioni: ∧1≤i≤n

ϕi

∨1≤i≤n

ϕi

abbreviano:

ϕ1 ∧ · · · ∧ ϕn

ϕ1 ∨ · · · ∨ ϕn.

I blocchi di quantificatori ∀x1 · · · ∀xn e ∃x1 · · · ∃xn li si abbreviano ∀x1 · · ·xn e∃x1 · · ·xn.

Esempio 1.6.6. “ Ci sono almeno n elementi ” (ε≥n)

∃x1 · · ·xn

( ∧1≤i≤j≤n

xi 6= xj

)

Esempio 1.6.7. “ Ci sono al piu n elementi ” (ε≤n)

∀x1 · · ·xn+1

( ∨1≤i≤j≤n+1

xi = xj

)

Esempio 1.6.8. “ Ci sono esattamente n elementi ” e

ε≥n ∧ ε≤n

Esempio 1.6.9. “ Tra due elementi che godono della proprieta P c’e un elementoche gode della proprieta Q, e viceversa”

∀x∀y((x < y ∧ P (x) ∧ P (y))⇒ ∃z(x < z ∧ z < y ∧Q(z)))∧

∧∀x∀y((x < y ∧Q(x) ∧Q(y))⇒ ∃z(x < z ∧ z < y ∧ P (z)))

1.7 Tautologie

Si utilizzera la notazione:

Σ ` A

per dire che A e deducibile da Σ, esiste cioe una dimostrazione di A partendo daaffermazioni in Σ.

Definizione 1.7.1. Una formula e elementare se e atomica oppure e della forma∃xA.

Una valutazione di verita e una funzione dalle formule elementari in 0, 1.Ognivalutazione si estende in modo ovvio alle formule ponendo:

V (A ∨B) = sup(V (A), V (B))

V (¬A) = 1− V (A)

· · ·

Definizione 1.7.2. B e conseguenza tautologica di A1, · · · , An se per ogni valutazioneV che renda vere V (A1) = · · · = V (An) = 1 ho V (B) = 1.

Definizione 1.7.3. A e una tautologia se e solo se V (A) = 1 per ogni valutazioneV .

Definizione 1.7.4. B e conseguenza tautologica di A1, · · · , An se e solo se A1 ⇒· · · ⇒ An ⇒ B e tautologia.

Teorema 1.7.1 (tautologia E.Post). Se B e conseguenza tautologica di A1, · · · , Ane Σ ` A1, · · · ,Σ ` An, allora Σ ` B.

Corollario 1.7.2. Ogni tautologia e un teorema.

Enunciamo le conseguenze piu importanti del teorema della tautologia. Suppo-niamo di avere una mappa che manda A in A∗ dall’insieme delle formule in se stessotale che (¬A)∗ e ¬A∗ mentre (A ∨B)∗ e A∗ ∨B∗. Vale il risultato:

Lemma 1.7.3. Se B e conseguenza tautologica di A1, · · · , An allora B∗ e conseguenzatautologica di A∗1, · · · , A∗n.

Dimostrazione. Sia V valutazione, definisco V ′(A) = V (A∗) per ogni A elementa-re.Per induzione lo definisco per tutte le formule A. Per induzione sulla complessita.Se V (A∗1) = · · · = V (A∗n) = 1 allora V ′(A1) = · · · = V ′(An) = 1 quindi V ′(B) = 1cioe V (B∗) = 1.

Altre conseguenze:

1)` A⇔ B se (` A se e solo se ` B).2)Se ` A⇒ B e ` B ⇒ C allora ` A⇒ C.3)Se ` A⇔ B e ` B ⇔ C allora ` A⇔ C.4)` A ∧B se e solo se ` A e ` B.5)` A⇔ B se e solo se ` A⇒ B e ` B ⇒ A.6)` A⇒ B se e solo se ` ¬B ⇒ ¬A.

Sia T una teoria.Ogni assioma di sostituzione,identita,uguaglianza e assioma nonlogico e teorema di T .Se A1, · · · , An sono teoremi di T e B e conseguenza tautologicadi A1, · · · , An allora B e un teorema di T . Se A e teorema di T e B e ottenuta da Amediante regola di ∃-introduzione,allora B e un teorema di T .

Segue ora un elenco di regole che possono essere facilmente dimostrate con l’uti-lizzo di risultati precedenti.

Regola di ∀-introduzione

Se ` A⇒ B e x non e libera in A,allora ` A⇒ ∀xB.

Dimostrazione. Da ` A⇒ B ho ` ¬B ⇒ ¬A, x non libera in ¬A uso ∃-introduzionee ho che ` ∃x¬B ⇒ ¬A da cui ` A⇒ ¬∃x¬B.

Regola di generalizzazione

Se ` A allora ` ∀xA.

Dimostrazione. Da ` A e per il teorema della tautologia ho ` ¬∀xA ⇒ A. Uso laregola di ∀-introduzione,` ¬∀xA⇒ ∀xA,da cui ` ∀xA per il teorema della tautologia.

Regola di sostituzione (o particolarizzazione)

Se A′ e esempio di A e ` A allora ` A′.

Dimostrazione. Supponiamo che A′ sia Ax[a] (un esempio):per generalizzazione `∀xA cioe ` ¬∃x¬A. Per gli assiomi di sostituzione ` ¬Ax[a] ⇒ ∃x¬A, quindi Ax[a]per il teorema della tautologia, cioe ` ∀xA⇒ Ax[a] poi per modus pones ` Ax[a] cioe` A′. Ora supponiamo che A′ sia Ax1···xn [a1, · · · , an]. Siano y1, · · · , yn delle nuovevariabili. Per quanto fatto in precedenza ` Ax1 [y1], · · · ,` Ax1,··· ,xn [y1, · · · , yn]. Orasostituisco gli yi con gli ai:` Ax1,··· ,xn [a1, y2, · · · , yn], · · · ,` Ax1,··· ,xn [a1, · · · , an].

Teorema 1.7.4 (Sostituzione). a)` Ax1···xn [a1, · · · , an]⇒ ∃x1 · · · ∃xnAb)` ∀x1 · · · ∀xnA⇒ Ax1···xn [a1, · · · , an].

Dimostrazione. a)Dall’assioma di sostituzione ` C ⇒ ∃xC applicato ripetutamentee poi la regola di sostituzione.b)Dall’assioma di sostituzione ` ¬C ⇒ ∃x¬C e dal teorema della tautologia ottengo` ∀xC ⇒ C, lo si applica ripetutamente e poi con la regola di sostituzione ottengo ilrisultato.

Regola di distribuzioneSe ` A⇒ B, allora ` ∃xA⇒ ∃xB e ` ∀xA⇒ ∀xB.

Dimostrazione. Per la prima parte:` B ⇒ ∃xB, per il teorema di sostituzione.` A⇒ B, per ipotesi.` A⇒ ∃xB, per il teorema della tautologia.` ∃xA⇒ ∃xB, per la regola di ∃-introduzione.Per la seconda parte:` ∀xA⇒ A, per il teorema di sostituzione.` A⇒ B, per ipotesi.` ∀xA⇒ B, per il teorema della tautologia.` ∀xA⇒ ∀xB, per la regola di ∀-introduzione.

Definizione 1.7.5. Data una formula A, le cui variabili libere sono x1, · · · , xn, sidefinisce chiusura universale di A la formula A′ data da ∀x1 · · · ∀xnA.

Teorema 1.7.5 (Teorema della chiusura). Se A′ e la chiusura di A, allora ` A′ se esolo se ` A.

Dimostrazione. Da ` A ricavo ` A′ per regola di generalizzazione. Per il teorema disostituzione ` A′ ⇒ A quindi se ` A′ allora ` A per modus ponens.

Corollario 1.7.6. Se A′ e la chiusura universale di A, allora A e valida in unastruttura A se e solo se A′ e valida in A.

Teorema 1.7.7 (Teorema della deduzione). Sia A un enunciato (una formula chiusa)di T . Per ogni formula B di T ho T ` A⇒ B se e solo se T [A] ` B, cioe B e teoremadi T [A].

Dimostrazione. Supponiamo che T ` A⇒ B allora A⇒ B e A sono teoremi di T [A]quindi per modus pones T [A] ` B. Dimostriamo ora per induzione che se T [A] ` Ballora T ` A⇒ B.1)Se B e assioma di T [A]. Se B e A, A ⇒ B e tautologia quindi derivabile in T ,T ` A ⇒ B. Se B e assioma di T allora T ` B dunque T ` A ⇒ B per il teoremadella tautologia.2)Se B e conseguenza tautologia di C1, · · · , Cn allora A⇒ B e conseguenza tautologi-ca di A⇒ C1, · · · , A RightarrowCn. Per ipotesi induttiva ` A⇒ C1, · · · ,` A⇒ Cnquindi ` A⇒ B per il teorema della tautologia.3)Se B e ∃xC ⇒ D, con x non libera in D e ottenuta da C ⇒ D mediante la regola di∃-introduzione. Per ipotesi induttiva ` A⇒ C ⇒ D, per il teorema della tautologiaho che C ⇒ A⇒ D, per la regola di ∃-introduzione ` ∃xC ⇒ A⇒ D, per il teoremadella tautologia ` A⇒ ∃xC ⇒ D.

Osservazione 9. Il teorema della deduzione vale solo se richiedo A enunciato. Adesempio se aggiungo x = 0 come assioma nella teoria dei naturali, posso dimostrarey = 0 con la regola di sostituzione. Ma x = 0⇒ y = 0 non e un teorema della teoriadei numeri naturali perche non e valido nel modello N.

Teorema 1.7.8 (Teorema delle costanti). Sia T ′ ottenuta da T aggiungendo nuovecostanti. Per ogni formula A del linguaggio di T e nuove costanti e1, · · · , en, T ` Ase e solo se T ′ ` A[e1, · · · , en].

Dimostrazione. Se T ` A allora T ′ ` A e T ′ ` A[e1, · · · , en] per la regola diparticolarizzazione. Supponiamo T ′ ` A[e1, · · · , en], supponiamo inoltre che

B1, · · · , Bm

sia la derivazione. Siano B∗i le formule ottenute da Bi sostituendo y1, · · · , yn alposto di e1, · · · , en. Le y1, · · · , yn non compaiono in Bi.1)Se Bi e assioma logico, allora B∗i e assioma logico dello stesso tipo.2)Se Bi e assioma non logico di T ′, allora B∗i e Bi ed e a ssioma non logico di T .3)Se Bi e ottenuta mediante una regola da Bj e Bk con j, k < i, allora B∗i e ottenutamediante la stessa regola da B∗j e B∗k. Quindi B∗1 , · · · , B∗m testimonia T ` A.

Teorema 1.7.9 (Teorema di equivalenza). Sia A′ ottenuta da A sostituendo alcuneoccorrenze di B1, · · · , Bn con B′1, · · · , B′n.Se ` Bi ⇔ B′i per i = 1, · · · , n allora` A⇔ A′.

Dimostrazione. Nel caso particolare A e Bi per qualche i. Allora A′ e B′i quindi

` A⇔ A′. Il caso generale si dimostra per induzione sulla complessita di A.

Definizione 1.7.6. Una variante A′ di A e ottenuta mediante una sequenza di rim-piazzamenti del tipo: sostituisco ∃xB con ∃yBx[y] dove y e variabile non libera inB.

Teorema 1.7.10 (Teorema della variante). Se A′ e una variante di A, allora ` A⇔A′.

Dimostrazione. Per i teoremi di equivalenza e di tautologia e sufficiente dimostrareche ` ∃xB ⇔ ∃yB′, dove B′ e Bx[y]. Per il teorema di sostituzione ` B′ ⇒ ∃xB,quindi per ∃-introduzione, ` ∃yB′ ⇒ ∃xB. Dato che B′y[x] e B, ripeto l’argomentosopra scambiando B e x con B′ e y ottenendo ` ∃xB ⇒ ∃yB′.

Teorema 1.7.11 (Teorema di simmetria).

` a = b⇔ b = a

Dimostrazione. 1)x = y ⇒ x = x⇒ x = x⇒ y = x per l’assioma di uguaglianza peri predicati.2)x = x⇒ x = x⇒ x = y ⇒ y = x per il teorema della tautologia.3)x = x assioma di identita.4)x = x⇒ x = y ⇒ y = x per modus pones di 2),3).5)x = y ⇒ y = x per modus pones 3),4).Quindi ` x = y ⇒ y = x per la regola di sostituzione che avviene in due modi (primax con a e y con b, poi x con b e y con a) dimostro il se e solo se, cioe

` a = b⇔ b = a.

Teorema 1.7.12 (Teorema di uguaglianza). 1)Sia b′ ottenuto da b sostituendo qual-che occorrenza di a1, · · · , an con a′1, · · · , a′n. Se ` a1 = a′1, · · · ,`, an = a′n allora` b = b′.2)Sia A′ ottenuta da A sostituendo qualche occorrenza di a1, · · · , an con a′1, · · · , a′n,con implicita assunzione che:se una ai e una variabile x, nessuna occorrenza del tipo∃x puo essere sostituita. Se ` a1 = a′1, · · · ,` an = a′n, allora ` A⇔ A′.

Dimostrazione. 1)Nel caso particolare ai e b. Quindi a′i e b′ e b′ = b. Nel caso generaleprocedo per induzione sulla lunghezza di b.2)Procedo per induzione sulla lunghezza di A.

Corollario 1.7.13. ` a1 = a′1 ⇒ · · · ⇒ an = a′n ⇒ b[a1, · · · , an] = b[a′1, · · · , a′n].

Corollario 1.7.14. ` a1 = a′1 ⇒ · · · ⇒ an = a′n ⇒ (A[a1, · · · , an]⇔ A[a′1, · · · , a′n]).

Corollario 1.7.15. Se x non occorre libera in a, allora ` Ax[a]⇔ ∃x(x = a ∧ A).

1.8 Forma prenessa

Definizione 1.8.1. Una formula e aperta se non contiene quantificatori.

Definizione 1.8.2. Una formula e in forma prenessa se e della forma Q1x1, · · · , QnxnBdove B e aperta, x1, · · · , xn sono variabili distinte e Q1, · · · , Qn sono quantificatori.B e la matrice di A e Q1x1 · · ·Qnxn e il prefisso.

Se Q e un quantificatore il suo duale Q e ∀ se Q e ∃ ed e ∃ se Q e ∀.

Le operazioni prenesse sono le seguenti:1)Rimpiazzo A con una variante.2)Rimpiazzo una parte ¬QxB con Qx¬B.3)Rimpiazzo QxB ∨ C se e solo se Qx(B ∨ C), se x non e libera in C.4)Rimpiazzo B ∨QxC se e solo se Qx(B ∨ C), se x non e libera in B.

Dimostrazione. Dimostriamo che se A′ e ottenuta da A mediante operazioni prenesse,allora ` A⇔ A′. Per 1) basta usare il Teorema della variante. Per 2) basta osservareche ` ¬∃xB ⇔ ∀¬B e ` ¬∀xB ⇔ ∃x¬B ed usare il teorema di equivalenza. La4) discende dalla 3) per commutativita e il teorema di equivalenza. Per 3) bastadimostrare che` QxB ⇒ Qx(B ∨ C),` C ⇒ Qx(B ∨ C) e ` Qx(B ∨ C)⇒ QxB ∨ C.

Per la prima:B ⇒ B ∨ C per il teorema della tautologia.QxB ⇒ Qx(B ∨ C) per la regola di distribuzione.

Per la seconda:C ⇒ B ∨ C per il teorema della tautologia.B ∨ C ⇒ ∃x(B ∨ C) per l’assioma di sostituzione.C ⇒ ∃x(B ∨ C) per il teorema della tautologia applicato alle due precedenti.C ⇒ ∀x(B ∨ C) per la regola di ∀-introduzione applicata alla prima.

Per la terza, quando Q e ∃:B ⇒ ∃xB per l’assioma di sostituzione.B ∨ C ⇒ ∃xB ∨ C per il teorema della tautologia.∃x(B ∨ C)⇒ ∃B ∨ C per ∃-introduzione.

Quando Q e ∀:∀x(B ∨ C)⇒ B ∨ C per il teorema di sostituzione.∀x(B ∨ C) ∧ ¬C ⇒ B per il teorema della tautologia.∀x(B ∨ C) ∧ ¬C ⇒ ∀xB per ∀-introduzione.∀x(B ∨ C)⇒ ∀xB ∨ C per il teorema della tautologia.

Teorema 1.8.1. Ogni formula A puo essere trasformata mediante operazioni pre-nesse in una formula prenessa A′.

Dimostrazione. Se A e atomica allora e in forma prenessa. Se A e ¬B,allora peripotesi induttiva B e equivalente ad Q1x1 · · ·QnxnB

′ con B′ aperta, quindi A e equi-valente a Q1x1 · · · Qnxn¬B′, dove Q e il duale di Q. Se A e QxB, per ipotesi in-duttiva trasformo B in Q1x1 · · ·QnxnB

′ e possiamo supporre che x1, · · · , xn sianodistinte da x. Allora A e equivalente a QxQ1x1 · · ·QnxnB

′. Se A e B ∨ C alloraper ipotesi induttiva B e C sono equivalenti ad Q1x1 · · ·QnxnB

′ e Q′1y1 · · ·Q′mymC ′con C ′ e B′ aperte, e posso supporre che le variabili x1, · · · , xn non occorrano libe-re in C ′ e che le y1, · · · , ym non occorrano libere in B′. Allora A e equivalente aQ1x1 · · ·QnxnQ

′1y1 · · ·Q′mym(B′ ∨ C ′).

Osservazione 10. L’algoritmo richiede che ∧ e ⇒ siano rimpiazzate dalle lorodefinizioni.

Ulteriori operazioni prenesse sono:5)Rimpiazzo QxB ⇒ C con Qx(B ⇒ C) se x non e libera in C.6)Rimpiazzo B ⇒ QxC con Qx(B ⇒ C) se x non e libera in B.7)Rimpiazzo QxB ∧ C con Qx(B ∧ C) se x non e libera in C.8)Rimpiazzo B ∧QxC con Qx(B ∧ C) se x non e libera in B.

Esempio 1.8.1. Nei numeri naturali scrivi in forma prenessa la formula ∃x(x =y)⇒ ∃x(x = 0 ∨ ¬∃y(y < 0)).

∃x(x = y)⇒ ∃z(z = 0 ∨ ¬∃w(w < 0))

∃x(x = y)⇒ ∃z(z = 0 ∨ ∀w¬(w < 0))

∃x(x = y)⇒ ∃z∀w(z = 0 ∨ ¬(w < 0))

∀x∃z∀w(x = y ⇒ z = 0 ∨ ¬(w < 0))

Capitolo 2

Teoria degli insiemi

2.1 Antinomia di Russel

Nella teoria ingenua degli insiemi si parla di elementi ed insiemi dove gli elementiappartengono a degli insiemi cioe x ∈ A con A insieme e x elemento. Questo fa si cheun insieme A sia completamente determinato dai suoi elementi. In altri termini dueinsiemi coincidono se hanno gli stessi elementi. Questo principio viene preso comeassioma e denominato assioma di estensionalita. Questo assioma afferma che se Ae B sono due insiemi e per ogni x, x ∈ A se e soltanto se x ∈ B allora A = B.Un’altra caratteristica di questa nozione intuitiva di insieme e che data una proprietaφ, possiamo considerare l’insieme di tutti gli x che soddisfano la φ,

x|φ(x).

Questo insieme e determinato totalmente grazie all’assioma di estensionalita. Po-niamolo come secondo assioma ovvero, se φ e una proprieta, allora esiste l’insiemex|φ(x). Tuttavia come osservo Bertrand Russel nel 1901 questo secondo assio-ma contraddice quello di estensionalita. Consideriamo infatti la proprieta φ(x) cheasserisce x e un insieme e x 6∈ x: considero l’insieme di Russel

R = x|x 6∈ x,

dove R e un insieme per il secondo assioma e ci chiediamo se soddisfi o meno laproprieta φ, cioe se R 6∈ R oppure R ∈ R. Ma

R ∈ R⇒ R 6∈ R (2.1.1)

R 6∈ R⇒ R ∈ R (2.1.2)

una contraddizione. Per risolvere questa contraddizione sono state introdotte varieteorie assiomatiche qui riportiamo quella introdotta da A.P.Morse e J.Kelly e prendeil nome di MK.

22

2.2 Classi,insiemi e classi proprie

Assumiamo come concetto primitivo quello di classe e consideriamo come simbolo direlazione tra loro il simbolo di appartenenza ∈ tra classi.Una classe A e un insiemese e solo se esiste una classe B a cui A appartiene, cioe

∃B(A ∈ B).

Una classe che non e un insieme e detta classe propria.Si assumera che gli elementidi una classe siano a loro volta delle classi anzi, degli insiemi. In un certo senso gliinsiemi sono come delle classi piccole mentre le classi grosse sono classi proprie.

2.3 Assiomi e linguaggio della teoria degli insiemi

Il linguaggio della teoria degli insiemi e un linguaggio del primo ordine che possiedesolo un simbolo non logico 2-ario, quello di appartenenza ∈. Le formule atomicherisultano della forma:

x ∈ y x = y.

Diamo ora l’elenco degli assiomi della teoria degli insiemi.Assioma di estensionalita.

∀x∀y(∀z(z ∈ x⇔ z ∈ y)⇒ x = y).

Assioma di comprensione (o esistenza delle classi):

Sia ϕ(x, y1, · · · , yn) una formula in cui la variabile x compare libera e sia A unavariabile differente da x, y1, · · · , yn. Allora:

∀y1, · · · ∀yn∃A∀x (x ∈ A⇔ (∃z(x ∈ z) ∧ ϕ(x, y1, · · · , yn))) .

Osservazione 11. Per l’assioma di estensionalita la classe A e unica e la si denotaanche:

x|ϕ(x, y1, · · · , yn)

Assioma di esistenza degli insiemi.

∃x∃y(x ∈ y).

Assioma dell’insieme potenza.Per ogni insieme x c’e un insieme z tale che:

∀x(∃y(x ∈ y)⇒ ∃z∃w(z ∈ w ∧ ∀t(t ∈ z ⇔ t ⊆ x))).

Osservazione 12. Se x e insieme allora l’insieme delle parti di x lo indichiamo con℘(x).

Assioma della coppia.Se x e y sono insiemi, allora x, y e un insieme. Cioe:

∀x∀y(∃a(x ∈ a) ∧ ∃b(y ∈ b)⇒ ∀z∃c((z ∈ c⇒ z = x ∨ z = y) ∧ ∃d(c ∈ d)).

Osservazione 13. Se x = y allora x, y = x singoletto di x che e ugualmente uninsieme.

Osservazione 14. Se B e un insieme e A ⊆ B allora A e un insieme. Equivalente-mente: se A e una classe propria e A ⊂ B allora B e una classe propria.

Sia A un insieme allora x ∈ A|x 6= x e un insieme. Viene detto insieme vuoto∅.

Assioma di fondazione.

∀A(A 6= ∅ ⇒ ∃x(x ∈ A ∧ x ∩ A = ∅)).

Osservazione 15. Se per qualche classe si avesse A ∈ A, allora A e un insieme edesisterebbe A per l’assioma della coppia. Per l’assioma di fondazione deve esistereun B ∈ A tale che B ∩ A = ∅; ma B deve essere A e per ipotesi A ∈ A = B equindi A ∈ B ∩ A:contraddizione.

Poiche nessun insieme appartiene a se stesso la classe di tutti gli insiemi R e in-dicata con V e la si definisce cosı:

V = x|x = x,

detto universo degli insiemi o classe totale.

Definizione 2.3.1 (Unione e intersezione generalizzata). Su una classe A di insiemisono definite: ⋃

A =⋃x∈A

x = y|∃x ∈ A(y ∈ x)

⋂A =

⋂x∈A

x = y|∀x ∈ A(y ∈ x)

per convenzione se A = ∅ allora⋂A = ∅.

Assioma dell’unione.

Se A e un insieme allora anche⋃A e un insieme.

∀A(∃B(A ∈ B)⇒ ∃C∃D

(C ∈ D ∧ C =

⋃A))

Definizione 2.3.2. Se x e un insieme si definisce:

S(x) = x ∪ x.

Osservazione 16.⋃x, y =

⋃w∈x,y

w = k|∃w ∈ x, y(k ∈ w) = x ∪ y

Definizione 2.3.3. Una classe I si dice induttiva se:

∅ ∈ I ∧ ∀x(x ∈ I ⇒ S(x) ∈ I).

Assioma dell’infinito.Esiste un insieme induttivo.

∃I∃J(I ∈ J ∧ ∅ ∈ I ∧ ∀x(x ∈ I ⇒ ∃y(y = S(x) ∧ y ∈ I))).

Sia I la classe di tutti gli insiemi induttivi. Poniamo:

N =⋂I.

Quindi N e il piu piccolo insieme contenente ∅ e chiuso per successori. Definiamoanche:

0 = ∅ 1 = S(0) 2 = S(1) 3 = S(2) · · ·

Proposizione 1. N ∈ I e se n ∈ N, allora n = 0 oppure n = S(m) per qualchem ∈ N.

Dimostrazione. Sia I un elemento di I. Per l’assioma dell’infinito un insieme siffattoesiste. Poiche 0 ∈ I e poiche I e arbitrario, possiamo concludere che 0 ∈

⋂I = N.

Sia n un elemento di N. Per ogni I ∈ I si ha che n ∈ I e quindi S(n) ∈ I:essendo I ∈ I arbitrario, otteniamo che S(n) ∈

⋂I = N. Quindi N ∈ I. Sia

n ∈ N \ 0 e supponiamo che per assurdo n 6= S(m) per ogni m ∈ N. Alloral’insieme J = N \ n soddisferebbe la formula che definisce I e quindi J ∈ I. Daquesto segue che

⋂I = N ⊆ J , ma per costruzione J ⊂ N:contraddizione.

Proposizione 2. Sia I ⊆ N tale che 0 ∈ I e tale che ∀n(n ∈ I ⇒ S(n) ∈ I). AlloraI = N.

Dimostrazione. I ∈ I, quindi N ⊆ I.

Definizione 2.3.4 (coppia ordinata). La definizione di coppia ordinata che si adot-ta in teoria degli insiemi e dovuta a Kazimirez Kuratowski, se x e y sono insiemiponiamo:

(x, y) = x, x, y.

Osservazione 17. Un’altra definizione di coppia ordinata e quella di Norbert Wienernel 1914:

(x, y)W = ∅, x, y

Un’altra e una variante di quella di Kuratowski:

(x, y)K′ = x, x, y.

Quest’ultima richiede l’assioma di fondazione. Si puo vedere quindi che la definizionedi coppia ordinata non e unica.

Definizione 2.3.5. Date due classi A e B, il prodotto cartesiano A×B e la classe:

A×B = (x, y)|x ∈ A, y ∈ B = c|∃a∃b(a ∈ A ∧ b ∈ B ∧ c = (a, b).

Osservazione 18. La classe A×B esiste per l’assioma di comprensione.

Proposizione 3. Se A e B sono insiemi, anche A×B e un insieme.

Dimostrazione. Bisogna trovare un insieme che lo contenga. Se x ∈ A e y ∈ B,allorax,x, y ⊆ A ∪ B e quindi (x, y) = x, x, y ⊆ ℘(A ∪ B). Ne segue cheA×B ⊆ ℘(℘(A ∪B)) poiche questo e un insieme la dimostrazione e completa.

Definizione 2.3.6. Una relazione binaria e una classe tale che tutti i suoi elementisono coppie ordinate. Una relazione F si dice funzionale se (x, y), (x, y′) ∈ F implicay = y′. Spesso di scrive anche xRy invece di (x, y) ∈ R e, nel caso in cui R siarelazione funzionale, R(x) indica l’unico y se esiste tale che (x, y) ∈ R. Si definisceanche dominio, immagine e campo di una classe R come:

dom(R) = x|(x, y) ∈ R, per qualche y.ran(R) = y|(x, y) ∈ R, per qualche x.fld(R) = dom(R) ∪ ran(R).

Per verificare che dom(R) e una classe si applica l’assioma di costruzione di classialla formula φ(x,R):

∃y∃z(z = (x, y) ∧ z ∈ R).

Proposizione 4. Se R e un insieme, allora dom(R),ran(R) e fld(R) sono insiemi.

Dimostrazione. Se x ∈ dom(R) allora x ∈ x ∈ (x, y) ∈ R, per qualche y, quindix ∈

⋃(⋃R), quindi dom(R) ⊆

⋃(⋃R). Ho trovato un insieme che lo contiene. Gli

altri casi sono analoghi.

Se F e una relazione funzionale e A una classe poniamo:

F [A] = F (x)|x ∈ A ∩ dom(F )

F A = (x, y) ∈ F |x ∈ A

Osservazione 19. Non si richiede che A ⊆ dom(F ).

Osservazione 20. Se F ed A sono classi proprie puo succedere che F [A] e classepropria. Si verifica pero facilmente che se F e un insieme allora F [A] e un insieme.

Se pero F e classe propria e A un insieme? In questo caso abbiamo l’assioma dirimpiazzamento.

Se F e una relazione funzionale e A un insieme, allora F [A] e un insieme.

∀F∀A((∀x∃!y(x, y) ∈ F ∧ ∃B(A ∈ B))⇒ ∃C(F [A] ∈ C)).

Con questo risulta completata la lista degli assiomi MK.

2.4 Successioni e assioma della scelta

Molto spesso in Analisi matematica si scrivono delle espressioni del tipo ai con i ∈ I.Quello che facciamo scrivendo queste espressioni e di affermare che esiste una funzionea di dominio I che ad i ∈ I associa ai. Per scrivere questo si utilizza la notazione〈ai|i ∈ I〉.

Esempio 2.4.1. La funzione s = 〈a0, a1, · · · , an−1〉 e la funzione di dominio dom(s) =n = 0, 1, · · · , n − 1 che si dice lunghezza di s e si indica con lh(s). Se X e unaclasse:

X<N = s|s stringa finita e ran(s) ⊆ X.

Questa nozione con “insiemi indicizzati” e molto comoda in matematica e spessouna famiglia F di insiemi viene descritta come Ai|i ∈ I. Questo si puo sempre fareponendo I = F e prendere i 7→ Ai la funzione identica. La scrittura ai sottintendel’esistenza di una funzione f che ad i ∈ I associa f(i) = ai ∈ Ai. In altre parole,siamo passati dall’ipotesi originale ∀i ∈ I∃x ∈ Ai a ∃f∀i ∈ I(f(i) ∈ Ai) scambiandol’ordine dei quantificatori. L’assioma della scelta asserisce che questo e sempre lecito.

Assioma della scelta.Se F e un insieme non vuoto e se ∀A ∈ F(A 6= ∅), allora esiste f : F →

⋃F tale che

∀A ∈ F(f(A) ∈ A).

L’assioma della scelta si indica anche con AC. La teoria MK +AC si indica conMKC o MK + AC.

Se F e una classe funzione di dominio A e immagine contenuta in B diremo cheF e una (classe-) funzione da A a B e lo indicheremo con F : A→ B. La collezionedi tutte queste F e denotata

BA =AB = F |F : A→ B

Proposizione 5. Se A e B sono insiemi allora BA e un insieme.

Dimostrazione. BA ⊆ ℘(A×B)

Definizione 2.4.1 (Prodotto cartesiano generalizzato). Se I e un insieme e 〈Ai|i ∈I〉 e una successione di insiemi, si definisce:

Xi∈IAi = f |f e una funzione, dom(f) = I e ∀i ∈ I(f(i) ∈ Ai)

Quindi se Ai = A per ogni i, allora Xi∈IAi = AI .

Osservazione 21. Se Ai0 = ∅ per qualche i0 ∈ I, allora Xi∈IAi = ∅. Per dimostrareil converso si deve ricorrere all’assioma della scelta.

Teorema 2.4.1. Non esiste nessuna funzione f tale che dom(f) = N e

∀n ∈ N(f(S(n)) ∈ f(n))

Dimostrazione. Per assurdo, supponiamo esista una f siffatta. Poiche ∅ 6= ran(f),per l’assioma di fondazione c’e un y ∈ ran(f) tale che y∩ ran(f) = ∅. Sia n ∈ N taleche y = f(n). Ma f(S(n)) ∈ f(n) ∩ ran(f):contraddizione.

Esempio 2.4.2. Data 〈Xi|i ∈ N〉 una sequenza di insiemi. Prova che lim infi∈NXi ⊂lim supi∈NXi.

Dimostrazione. Si ricorda che

lim infi∈N

Xi =⋃j∈N

⋂i∈N,i>j

Xi

e

lim supi∈N

Xi =⋂j∈N

⋃i∈N,i>j

Xi.

Se x ∈ lim infi∈NXi allora x ∈⋂i>kXi per qualche k. Esiste un k ∈ N tale

che x ∈ Xi per ogni i > k. x ∈⋃i∈N,i>j Xi per ogni j in N perche altrimenti

x 6∈ Xi ∀i > j, quindi

x ∈⋂j∈N

⋃i∈N,i>j

Xi

Esempio 2.4.3. Se lim inf(Xi) = lim sup(Xi) = lim(Xi) trovare i limiti nei seguenticasi:

1)Xi = [0, i] ⊂ R2)Xi =

[0, 1

i

]3)Xi = [0, 1] per i pari e [0,−1] per i dispari.

Per 1) ho [0,∞),per 2) ho 0 e per 3) ho lim sup(Xi) = [−1, 1], lim inf(Xi) = 0

Definizione 2.4.2. Una funzione finitaria o operazione su X e una f : Xn → Xper qualche n ∈ N detto arieta della funzione n = ar(f). Se n = 0 ho f : ∅ → Xquindi le funzioni 0-arie su X possono essere identificate con gli elementi di X.

Esempio 2.4.4. Costruire gli insiemi 23, 32, 20, 02, 00, 10, 11, 01, 21, 12.

23 = (0, 0), (1, 0), (2, 0), (0, 0), (1, 0), (2, 1), (0, 0), (1, 1), (2, 0), (0, 1), (1, 0), (2, 0),, (0, 1), (1, 1), (2, 0), (0, 1), (1, 1), (2, 1), (0, 0), (1, 1), (2, 1), (0, 1), (1, 0), (2, 1)

32 = (0, 0), (1, 0), (0, 0), (1, 1), (0, 1), (1, 1), (0, 1), (1, 0), (0, 0), (1, 2), (0, 2), (1, 2),, (0, 2), (1, 0), (0, 1), (1, 2), (0, 2), (1, 1)

20 = ∅ = 102 = ∅ = 000 = ∅ = 110 = 111 = (0, 0)01 = 021 = (0, 0), (0, 1)12 = (0, 0), (1, 0)

Esempio 2.4.5. Provare che AB = 0 se e solo se A = 0, B 6= 0. Se A = 0, B 6=0 ⇒ f |f : B → A = 0 ⇒ AB = 0. Viceversa suppongo A 6= 0 allora AB = f |f :B → A 6= ∅ = 0 poiche (x, a)|x ∈ B e funzione con a ∈ A, quindi ho che AB = 0implica A = 0.

Osservazione 22. Un insieme di numeri reali E si dice inferiormente limitato seesiste un numero K tale per cui:

K ≤ x ∀x ∈ E.

Il maggiore tra i numeri K con tale proprieta e detto estremo inferiore di E e siindica inf E.Piu precisamente λ = inf E se λ ≤ x per ogni x ∈ E e se, per ogni ε > 0,possiamo trovare x ∈ E tale che x < λ + ε.Se infE ∈ E, allora inf E e il minimodi E, che si indica con minE. Un insieme di numeri reali E si dice superiormentelimitato se esiste un numero K tale per cui:

K ≥ x ∀x ∈ E.

Il minore tra i numeri K con tale proprieta e detto estremo superiore di E e siindica supE. Piu precisamente Λ = supE se Λ ≥ x per ogni x ∈ E e se, per ogniε > 0, possiamo trovare x ∈ E tale che x > Λ − ε. Se supE ∈ E, allora supE e ilmassimo di E, che si indica con maxE.

2.5 Insiemi ordinati

Sia X una classe, un ordine parziale su X o semplicemente un ordine su X e unarelazione R ⊆ X × X riflessiva, antisimmetrica e transitiva su X, se R e ancheconnessa (∀x∀y(x = y ∨ xRy ∨ yRx)) su X diremo che e un ordine lineare o totalesu X. Un pre-ordine su X e una relazione binaria riflessiva e transitiva su X. Siindicano con:

≤,, · · ·

Un ordine stretto su X e una relazione che e la parte irriflessiva di un ordine(parziale o totale) su X, dove la parte irriflessiva di una relazione R ⊆ X × X edefinita come:

R \ (x, y)|(x, y) ∈ R ∧ (y, x) ∈ R.

Un pre-ordine stretto e la parte irriflessiva di un pre-ordine. Si indicano con

<,≺, · · ·

Osservazione 23. La proprieta di connesione per ordini stretti si dice anche trico-tomia.

Definizione 2.5.1 (segmento iniziale). Un segmento iniziale di un pre-ordine ≤ suX e un Y ⊆ X tale che

∀y ∈ Y ∀x ∈ X(x ≤ y ⇒ x ∈ Y ).

Definizione 2.5.2. Una catena in un ordine ≤ su X e un C ⊂ X tale che C elinearmente ordinato da ≤, vale a dire

∀x, y ∈ C(x ≤ y ∨ y ≤ x).

Definizione 2.5.3. Se A ⊆ X, l’insieme:

pred(x,A;<) = y ∈ A|y < x

denota l’insieme di tutti i predecessori di x che giacciono in A.In particolare pred(x) =pred(x,X;<). Osserviamo che pred(x) e segmento iniziale di 〈X,≤〉. Ma non tuttii segmenti iniziali sono di questa forma.

Se R ⊆ X × X e S ⊆ Y × Y , un morfismo f : 〈X,R〉 → 〈Y, S〉 e una funzionef : X → Y tale che:

∀x1, x2 ∈ X(x1Rx2 ⇒ f(x1)Sf(x2)).

Se inoltre f e una biezione tra X e Y e f−1 e morfismo, diremo che f e isomorfismo.Un pre-ordine ≤ su X e detto diretto superiormente se ∀x, y ∈ X∃z(x ≤ z ∧ y ≤ z),

diretto inferiormente se ∀x, y ∈ X∃z ∈ X(z ≤ x ∧ z ≤ y). Se richiedo che ≤ siaun ordine e che sup x, y (oppure inf x, y) esista, per ogni x, y ∈ X otteniamola nozione di semi-reticolo superiore (rispettivamente semi-reticolo inferiore). Unreticolo e un semi-reticolo superiore ed inferiore. Ogni ordine lineare e un reticolo.

Proposizione 6. Sia F una classe di funzioni e supponiamo ⊆ sia diretto superior-mente su F . Allora

⋃F e una relazione funzionale.

Dimostrazione.⋃F e una classe di coppie ordinate. Supponiamo che (x, y) ∈

⋃F

e (x, z) ∈⋃F e quindi (x, y) ∈ f e (x, z) ∈ g, per qualche f, g ∈ F . Sia h ∈ F tale

che f, g ⊆ h:allora (x, y), (x, z) ∈ h e quindi y = z.

Teorema 2.5.1 (Punto Fisso). Sia X un insieme con un ordine ≤ e per ogni Y ⊆ X,ammette estremo superiore, sia f : X → X una funzione crescente. Allora esiste unpunto fisso, cioe ∃a ∈ X(f(a) = a).

Dimostrazione. Considero A = x ∈ X|f(x) ≥ x e considero a = supA. Allora ognix ∈ A e tale che x ≤ a inoltre f(x) ≤ f(a) quindi x ≤ f(a) quindi f(a) e maggiorantee si ha a ≤ f(a). Per la crescenza f(f(a)) ≥ f(a) cioe f(a) ∈ A quindi f(a) ≤ apoiche a e estremo superiore.

Osservazione 24. Funziona anche se A e l’insieme vuoto.

Per indicare piu brevemente che una funzione e iniettiva si utilizzera il simbolo, mentre per le funzioni suriettive .

Teorema 2.5.2 (Teorema di S.Bernstein). Siano A,B due insiemi ordinati e f :A B e g : B A iniettive, allora esiste H : A→ B biettiva.

Dimostrazione. Considero 〈℘(A),⊆〉 come insieme ordinato e definisco la funzioneΦ : ℘(A)→ ℘(A) crescente Φ[C] = A \G[B \ F [C]]. Per il teorema del punto fisso siha che esiste C tale che Φ[C] = C ovvero A \ C = G[B \ F [C]]. Quindi le funzioniF C : C → F [C] e G−1 A\C : A \C → B \F [C] sono biezioni e H = F C ∪G−1 A\Ce la biezione cercata.

Introduciamo il concetto di classe.

Definizione 2.5.4. Sia X una classe e R ⊆ X × X.R e ben fondata se e solo se∀Y ⊆ X(Y 6= ∅ ⇒ ∃y ∈ Y ∀z ∈ Y (z 6= y ⇒ (z, y) 6∈ R)). R e regolare se e solo sey ∈ X|yRx e un insieme, per ogni x ∈ X.

Osservazione 25. Dire che una relazione e regolare vuol dire che gli y che sono inrelazione con x sono “pochi” ovvero formano un insieme. Dire ben fondata vuole direche ogni sua sottoclasse non vuota contiene un elemento R-minimale.

Definizione 2.5.5. Un buon ordine e un ordine lineare stretto, ben fondato e regolare.Con abuso di linguaggio diremo che un ordine ≤ e un buon ordine se lo e il suo ordinestretto associato <.

Proposizione 7. Se 〈A,<〉 e un buon ordine e f : A→ A e strettamente crescente,allora ∃a ∈ A(f(a) ≥ a).

Dimostrazione. Considero X = x ∈ A|f(x) < x suppongo sia non vuoto e consi-dero il minimo di X ovvero, sia a = minX allora si ha che f(a) < a e poiche a e ilminimo si ha che f(a) non sta in X dunque f(f(a)) ≥ f(a) ovvero per la crescenzaf(a) ≥ a:contraddizione.

Osservazione 26. L’ordinamento su N e un buon ordine perche ha il minimo. None cosı su R o Z.

Proposizione 8. Se 〈A,<〉 e un buon ordine e f : A→ A e una biezione strettamentecrescente, allora f = id A.

Dimostrazione. Supponiamo che f non sia l’identita allora considero il piu piccoloelemento a tale che f(a) 6= a ma allora per proposizione precedente f(a) > a quindif non puo essere suriettiva:contraddizione.

Corollario 2.5.3. Se 〈A,<〉 e 〈B,〉 sono buoni ordini isomorfi, allora tale isomor-fismo e unico.

Dimostrazione. Sia f : A → B una biezione tra A,B e g : B → A un’altra biezioneallora f g−1 : A → A ed e una biezione strettamente crescente dunque per laproprieta precedente f g−1 = id A quindi f = g.

Corollario 2.5.4. Se 〈A,<〉 e un buon ordine e a ∈ A allora 〈pred(a,A;<), <〉 e〈A,<〉 non sono isomorfi.

Dimostrazione. Sia f : A → pred(a,A;<) l’isomorfismo se considero f(a) ho chef(a) < a:assurdo.

Osservazione 27. L’assioma di fondazione implica che la relazione di appartenenza

(x, y) ∈ V |x ∈ y

e irriflessiva, ben fondata e poiche y|y ∈ x = x e un insieme per ogni x ∈ V eanche regolare.

Proposizione 9. Siano 〈A,<〉 e 〈B,≺〉 due classi bene ordinate allora vale una eduna sola delle tre proprieta:

1)∃a ∈ A(〈pred(a), <〉 ∼= 〈B,≺〉).2)∃b ∈ B(〈pred(b),≺〉 ∼= 〈A,<〉).3)〈A,<〉 ∼= 〈B,≺〉.

Dimostrazione. Si osserva che le tre proprieta sono mutualmente esclusive quindibasta dimostrare che almeno una vale. Sia

f = (a, b) ∈ A×B|〈pred(a), <〉 ∼= 〈pred(b),≺〉

un insieme. Se (a, b1), (a, b2) ∈ f allora si ha che 〈pred(a), <〉 ∼= 〈pred(b1),≺〉 ∼=〈pred(b2),≺〉 dunque per corollario precedente b1 = b2, quindi f e relazione funzio-nale. Se (a1, b), (a2, b) ∈ f allora si ha a1 = a2 ovvero f e iniettiva. Sia a ∈ dom(f)allora 〈pred(a), <〉 ∼= 〈pred(f(a)),≺〉.Sia g l’isomorfismo che testimonia questo al-lora se a′ < a ho che a′ ∈ dom(g) e 〈pred(a′), <〉 ∼= 〈pred(g(a′)),≺〉 quindi indom(f) e un segmento iniziale di A. Analogamente posso dimostrare che ran(f)e segmento iniziale di B nell’altro ordinamento. Siano a2 < a1 con a2, a1 ∈ dom(f)allora 〈pred(a1), <〉 ∼= 〈pred(f(a1)),≺〉 sia g la funzione che testimonia l’isomorfi-smo allora g pred(a2) e isomorfismo 〈pred(a2), <〉 ∼= 〈pred(g(a2)),≺ rangle quindig(a2) = f(a2) ≺ f(a1) ovvero f e isomorfismo tra i segmenti iniziali di 〈A,<〉 e〈B,≺〉.Mi rimane da dimostrare che

dom(f) = A ∨ ran(f) = B.

Sia a = min (A \ dom(f)) e b = min (B \ ran(f)) allora per quanto detto f :〈pred(a), <〉 → 〈pred(b),≺〉 e isomorfismo dunque (a, b) ∈ f per definizione dif :contraddizione.

2.6 Ordinali

Gli ordinali sono esempi canonici di buoni ordini.

Definizione 2.6.1. Una classe A si dice transitiva se⋃A ⊆ A cioe ∀a∀x(a ∈ A∧x ∈

a⇒ x ∈ A). Un ordinale e un insieme transitivo i cui elementi sono transitivi.

Esempio 2.6.1. x e transitivo se e solo se x = ∅. Nessun (x, y) e transitivo. V etransitiva. x|x ∈ V non e transitivo. Se x e transitivo, anche S(x) e transitivo.Se α e ordinale, anche S(α) e ordinale. Se x e transitivo anche

⋃x e transitivo. Se

α e un ordinale e β ∈ α allora anche β e ordinale. Se x e un insieme di ordinaliallora

⋃x e un ordinale.

Osservazione 28. ∅ e transitivo poiche ∀a∀x(a ∈ ∅ ∧ x ∈ a⇒ x ∈ ∅) e vero.

Indichiamo con Ord la collezione di tutti gli ordinali.

Proposizione 10. Ord e una classe propria.

Dimostrazione. Sia α ∈ Ord allora se β ∈ α allora β e ordinale cioe β ∈ Ordquindi Ord e una classe transitiva. Se fosse un insieme, sarebbe un ordinale e avreiOrd ∈ Ord assurdo dunque Ord e una classe propria.

Osservazione 29. E’ stato Cantor ad introdurre la classe Ord.

Teorema 2.6.1. ∀α, β ∈ Ord(α ∈ β ∨ α = β ∨ β ∈ α)

Dimostrazione. Considero A = α ∈ Ord|α 6∈ β ∧ α 6= β ∧ β 6∈ α suppongo siadiverso dall’insieme vuoto, allora ∃α tale per cui α ∩ A = ∅. Considero quindiB = β ∈ Ord|α 6∈ β ∧ α 6= β ∧ β 6∈ α e sia diverso dall’insieme vuoto allora ∃βtale che β ∩ B = ∅. Sia γ ∈ α allora γ 6∈ A e γ ∈ β o γ = β o β ∈ γ,le ultime dueportano ad β ∈ α ma β ∈ B, un assurdo. Dunque deve essere α ⊆ β. Posso ripeterel’argomentazione ed ottenere β ⊆ α dunque α = β:contraddizione.

Osservazione 30. Anche in questo caso α e β sono gli elementi minimali.

Corollario 2.6.2. ∈ e un buon ordine stretto su Ord e quindi su ogni ordinale α.

Si scrivera α < β e α ≤ β al posto di α ∈ β e (α ∈ β ∨ α = β).

Osservazione 31. Ogni α definisce un buon ordine 〈α,∈〉 dunque se β ∈ α si ha cheβ = pred(β, α,∈), quindi 〈α,<〉 ∼= 〈β,<〉 se e solo se α = β.

Teorema 2.6.3. Ogni insieme bene ordinato e isomorfo ad un ordinale. Inoltreordinale ed isomorfismo sono unici.

Dimostrazione. Sia〈X,<〉 un insieme bene ordinato e sia A = α ∈ Ord|∃x ∈ X〈α,∈〉 ∼= 〈pred(x), <〉. Sia α ∈ A allora f : 〈α,∈〉 → 〈pred(x), <〉 l’isomorfismo allorase β ∈ α posso considerare f β : 〈pred(β),∈〉 → 〈pred(f(β)), <〉 quindi β ∈ Adunque A e un insieme transitivo dunque e un ordinale. Sia f : A→ X l’isomorfismoche ad ogni ordinale α mi fa corrispondere un unico x tale per cui il suo segmentoiniziale e isomorfo con α.ran(f) e segmento iniziale di X. Sia ran(f) 6= X alloraran(f) = pred(x) per qualche x ∈ X e avrei un isomorfismo f : 〈A,∈〉 → 〈pred(x), <〉quindi A ∈ A assurdo, dunque ran(f) = X e X e isomorfo ad un ordinale, taleisomorfismo risulta anche unico.

Proposizione 11.α ∈ β ⇔ S(α) ∈ S(β)

Dimostrazione. Per ipotesi α ∈ β inoltre α ∈ S(α) e, per la tricotomia si ha β ∈S(α) ∨ β = S(α) ∨ S(α) ∈ β. Se β ∈ S(α) allora si avrebbe che β ∈ α oppure β = αche sono contraddizioni, dunque S(α) ∈ β ∨ S(α) = β. Inoltre β ∈ S(β) quindiS(α) ∈ S(β). Viceversa se S(α) ∈ S(β) allora α ∈ S(α) ∈ S(β) cioe α ∈ S(β).Poiche β ∈ S(β) l’unica possibilita e che α ∈ β ∈ S(β), infatti se β ∈ α ∈ S(α)avremo β ∈ α ∈ S(α) ∈ S(β) e perveniamo ad un assurdo. Dunque α ∈ β.

Proposizione 12. Sia A una classe non vuota di ordinali, allora⋂A = minA.

Dimostrazione. Poiche A 6= ∅ si ha che ∃α ∈ A tale che α∩A = ∅ quindi α e elementominimale ovvero ∀α(α ⊆ α) quindi

⋂A = minA = α.

Osservazione 32. Si fa largo uso dell’assioma di fondazione che garantisce in uncerto senso l’esistenza di un elemento minimale.

Corollario 2.6.4. Non esiste nessuna catena discendente di ordinali, vale a dire¬∃f(f : N→ Ord ∧ ∀n(f(S(n)) < f(n))).

Lemma 2.6.5. Ogni numero naturale e un ordinale.

Dimostrazione. Supponiamo che X = N \ Ord sia diversa dall’insieme vuoto alloraesiste n ∈ X tale che n ∩X = ∅. Se n = 0 e un ordinale, suppongo n 6= 0 allora ∃mtale che n = S(m) dunque ho che m ∈ N ed e un ordinale ma allora anche n deveessere ordinale cioe n ∈ N ∩Ord:assurdo.

Lemma 2.6.6. Se n ∈ N e x ∈ n allora x ∈ N.

Dimostrazione. SiaX = n ∈ N|∃x ∈ n(x 6∈ N), per assurdo suppongo sia non vuotoallora ∃n ∈ X tale che n ∩X = ∅. Fisso x tale che x ∈ n \ N, quindi esiste m ∈ Ntale che S(m) = n allora x = m oppure x ∈ m. Nel primo caso x = m ∈ N:assurdo,mentre nel secondo caso si ha x ∈ m ∈ N:assurdo.

Un ordinale α e successore se α = S(β) per qualche β. Chiaramente α < S(α) enon esiste nessun β tale che α < β < S(α). Infatti se cosı fosse avrei β = α oppureβ ∈ α ed in entrambi i casi avrei un assurdo.

Definizione 2.6.2. Un ordinale che non e successore e non e zero si dice limite.

Teorema 2.6.7. N e il piu piccolo ordinale limite.

Dimostrazione. N e un ordinale inoltre ogni n ∈ N e 0 oppure ammette un successorequindi non ci sono ordinali limite minori di N, allora mi basta dimostrare che N none successore. Per assurdo sia N = S(α) per qualche α ∈ N allora avrei che S(α) ∈ Ndunque N ∈ N:una contraddizione.

Come notazione da ora in avanti denoteremo N = ω.

Proposizione 13. Valgono le seguenti proprieta:1)α < β ⇔ α ⊂ β2)α ≤ β ⇔ α ⊆ β3)α < β ⇔ S(α) ≤ β4)x ⊆ α⇒ (

⋃x = α ∨

⋃x < α)

5)⋃S(α) = α

6)α = S (⋃α) ∨ α =

⋃α

7)⋃α = α⇔ (α = 0 ∨ α limite)⇔ 〈α,<〉 non ha massimo.

Dimostrazione. In ordine abbiamo che:1)Se α ∈ β allora per la transitivita ho che α ⊆ β. Per l’assioma di fondazione α 6= βquindi α ⊂ β. Se α ⊂ β allora per l’assioma di fondazione β 6∈ α e poiche α 6= β siha che α ∈ β.2)Analoga ad 1).3)Sia α < β, si ha α < S(α) dunque poiche β ∈ S(α) e impossibile, segue per trico-tomia che S(α) < β oppure S(α) = β. Il viceversa e banale.

4)⋃x e un ordinale perche unione di un insieme di ordinali, dunque e confrontabile

con α ma se α <⋃x allora α ∈ γ ∈ x ⊆ α, per qualche γ, che e assurdo dunque si

ha α =⋃x ∨

⋃x < α.

5)β ∈⋃S(α) solo se β ∈ γ ∈ α per qualche γ oppure β ∈ α.β ∈

⋃S(α)⇔ β ∈ α.

6)Da 4) si ha che⋃α ≤ α se

⋃α < α allora per la 3) si ha S (

⋃α) ≤ α, dimostriamo

che non vale la disuguaglianza stretta:se S (⋃α) ∈ α allora

⋃α ∈ S (

⋃α) quindi⋃

α ∈⋃α (per definizione di unione): contraddizione.

7)Segue da 5) e 6).

Osservazione 33. Si osserva che⋃ω = ω e

⋃0 = 0. Fare

⋃idealmente e come

“sottrarre”.

Proposizione 14. Se A e un insieme di ordinali allora⋃A = supA.

Dimostrazione.⋃A e il piu piccolo insieme contenente tutti gli ordinali di di A.

Inoltre dato che⋃A e un ordinale e ⊆ coincide con ≤ allora si ha

⋃A = supA.

Proposizione 15. Sia A ∈ Ord o A = Ord.Se I ⊆ A e tale che (∀β ∈ A(β < α ⇒β ∈ I))⇒ α ∈ I per ogni α ∈ A allora I = A. In particolare discende il principio diinduzione sui naturali. Se I ⊆ N e tale che ∀n ∈ N, (∀m ∈ N(m < n ⇒ m ∈ I) ⇒n ∈ I allora I = N.

Proposizione 16. Sia A un ordinale o A = Ord. Supponiamo che I ⊆ A sia taleper cui:1)0 ∈ I.2)∀α ∈ A(∃β(α = S(β) ∧ β ∈ I)⇒ α ∈ I).3))∀α ∈ A(α limite ∀β(β < α ∧ β ∈ I)⇒ α ∈ I).Allora I = A.

Proposizione 17. Sia f : α→ β strettamente crescente allora:

∀γ ∈ α(γ ≤ f(γ))

e α ≤ β. Se f : α→ β e un isomorfismo, α = β ed f e l’identita.

Dimostrazione. Per assurdo sia A = γ ∈ α|γ > f(γ) considero γ = minA siha che f(γ) < γ quindi f(γ) non appartiene ad A quindi f(γ) ≤ f(f(γ)) ovveroper la crescenza γ ≤ f(γ):contraddizione. Se per assurdo fosse β ∈ α allora avreif(β) ∈ β cioe f(β) < β:contraddizione. Per la seconda parte del teorema osservoche f e un isomorfismo dunque per la prima parte ho che α ≤ β mentre se considerof−1 : β → α quindi sempre applicando la prima parte ho anche β ≤ α. Infine applicoancora la prima parte del teorema per f e f−1 ottenendo γ ≤ f(γ) e γ ≤ f−1(γ), cioel’identita.

Definizione 2.6.3. x e finito se e in biezione con un numero naturale,altrimenti einfinito.

Teorema 2.6.8 (Dirichlet). Se n,m ∈ N ed esiste f : n m iniettiva, allora n ≤ m.Se n,m sono in biezione allora n = m.

Dimostrazione. Applico l’induzione sui naturali ovvero faccio vedere chen|∀m ∈ N f : n m iniettiva ⇒ n ≤ m = N. Se n = 0 e banale, se n

non e zero allora esiste un n′ ∈ N tale per cui n = S(n′), analogamente se m none zero esiste m′ ∈ N tale che m = S(m′). Considero una funzione g : m → mbiezione che scambia f(n′) con m′ e lascia invariato il resto. Allora la composizionef g n′ : n′ → m′ e quindi, per ipotesi induttiva n′ ≤ m′. Quindi n ≤ m.

Proposizione 18. N e infinito.

Dimostrazione. Se N fosse in biezione con un naturale n ∈ N allora N n iniettiva-mente (e una inclusione) ma anche S(n) N iniettivamente (e una inclusione) alloraanche S(n) n iniettivamente (e una inclusione):contraddizione della proposizioneprecedente.

2.7 Cardinali

Definizione 2.7.1. Un cardinale e un ordinale κ che non e in biezione con nessunordinale α < κ. La cardinalita di un ordinale α ∈ Ord,|α|, e il piu piccolo β inbiezione con α.Card e la classe dei cardinali.

|α| ≤ α. Il teorema di Dirichlet implica che ogni numero naturale e un cardinalee che ω e il primo cardinale infinito. Invece S(ω), S(S(ω)), · · · non sono cardinali.

Proposizione 19. Se λ, κ ∈ Card allora:1)κ = λ se e solo se κ e λ sono in biezione.2)κ ≤ λ se e solo se c’e una funzione iniettiva f : κ→ λ.

Dimostrazione. Per la 1) supponiamo che λ e κ siano in biezione e che λ 6= κ, peresempio κ < λ allora λ sarebbe in biezione con un ordinale piu piccolo:contraddizione.Per la 2) sia f : κ→ λ iniettiva e supponiamo che κ 6= λ allora suppongo che λ < κallora considero l’iniezione di λ in κ data dalla funzione identica j : λ → κ. Per ilteorema di S.Bernstein κ e λ sono in biezione pertanto κ = λ per 1):contraddizione.

Proposizione 20. Valgono:1)Se α ≥ ω allora |α| = |S(α)|.2)|α| ≤ β ≤ α⇒ |α| = |β|.3)|α| = |β| se e solo se α e β sono in biezione.4)|α| ≤ |β| se e solo se esiste f : α→ β iniettiva.

Dimostrazione. Per 1) considero la funzione:

f : S(α)→ α f(β) =

S(β) se β < ωβ se α > β ≥ ω

0 se β = αe una biezione. Per 2) sia f : α→ |α| una biezione. Poiche f : α→ β e iniettiva

e β si inietta in α, |α| = |β| per il teorema di S.Bernstein e dalla proposizioneprecedente. 3) e 4) discendono dalla proposizione precedente.

Sia X un insieme infinito. A = (α, f)|α ∈ Ord e f : α → X e iniezione. Adogni (α, f) ∈ A associo il buon ordine W(α,f) su ran(f) ⊆ X indotto da f :

xW(α,f)y ⇔ f−1(x) < f−1(y).

f : 〈α,<〉 → 〈ran(f),W(α,f)〉 e un isomorfismo. Se (α, f), (β, g) ∈ A e W(α,f) =W(β,g) allora g−1 f : 〈α,<〉 → 〈β,<〉 e un isomorfismo e quindi β = α e f = g.Quindi A → ℘(X × X),(α, f) 7→ W(α,f) e iniettiva ed e un insieme per l’assiomadi rimpiazzamento e potenza. Allora B = β ∈ Ord|β X e un insieme. Ilnumero di Hartogs di X e Hrtg(X) = supS(α)|∃f : α X.B e chiuso sotto S enon ha massimo, cioe Hrtg(X) 6∈ B. Se, per assurdo |Hrtg(X)| < Hrtg(X), allora|Hrtg(X)| ≤ β < Hrtg(X) per qualche β ∈ B. Dato che β X iniettivamente,allora anche |Hrtg(X)| X, e quindi Hrtg(X) X:una contraddizione. Quindi

Teorema 2.7.1. Hrtg(X) e il piu piccolo ordinale che non si inietta in X, ed e uncardinale.

Osservazione 34. Il numero di Hartogs di X si indica anche con ℵ(X).

Definizione 2.7.2. Un insieme finito o in biezione con ω si dice numerabile; altri-menti si dice non-numerabile o piu che numerabile.

Teorema 2.7.2. Un insieme non vuoto X e numerabile se e solo se e immaginesuriettiva di ω.

Dimostrazione. Se X e numerabile allora, o e in biezione con ω oppure e finito. See in biezione con ω allora e immagine suriettiva di ω. Se e finito allora e in biezionetramite con un naturale m. Sia f : X → m tale biezione, esibisco g : ω → msuriettiva data da g(i) = i se i < m e g(j) = m−1 per m ≤ j. La funzione compostagf e la suriezione cercata. Viceversa se esiste h : ω → X suriettiva allora esisteuna h′ : X ω iniettiva definita nel seguente modo. Per la suriettivita ho che perogni x ∈ X esiste n ∈ ω tale che h(n) = x, definisco h′(x) = min n ∈ ω|h(n) = x.Questa funzione e iniettiva e segue che X deve essere numerabile o finito.

Il primo cardinale piu che numerabile ω+ si indica con ω1.

Teorema 2.7.3. Se X ⊆ Card, allora supX ∈ Card ed e il piu piccolo cardinale≥ κ per ogni κ ∈ X.

Dimostrazione. Se, per assurdo λ =⋃X = supX 6∈ Card allora sarebbe in biezione

con un ordinale piu piccolo cioe |λ| < λ ed esiste κ ∈ X tale per cui |λ| ≤ κ < λ cioeκ non sarebbe un cardinale:contraddizione.

Corollario 2.7.4. Card e una classe propria.

Dimostrazione. Se Card fosse un insieme non avrebbe il massimo ma, il supCarde un cardinale per il teorema precedente ma non puo stare in Card poiche non hamassimo: assurdo.

Osservazione 35. Se Card fosse un insieme non avrebbe il massimo perche per ogniκ cardinale troverei κ+ che e piu grande di κ.

Capitolo 3

Funzioni ricorsive

3.1 Ricorsione

Sia A un insieme e f : A→ A possiamo definire le iterate della funzione f :

f (0) = id A f (1) = f f (2) = f f f (3) = f f (2) · · ·

E’ chiaro che ciascuna f (n) esiste per esempio usando l’assioma di comprensione ho:

f (2) = (x, y) ∈ A× A|∃z((x, z) ∈ f ∧ (z, y) ∈ f).

Ma riguardo la successione G = 〈f (n)|n ∈ N〉?. La definizione di G suggerisceuna espressione del tipo G = (n, g)|ϕ(n, g,G), questa non e una applicazione lecitadell’assioma di comprensione (la ϕ contiene la G!).

Teorema 3.1.1. A,B insiemi,h : A → B e F : A × ω × F → B, dove F = p ⊆(A× ω)× B|p e una funzione . Allora ∃!G : A× ω → B tale che per ogni a ∈ A eogni n ∈ ω G(a, 0) = h(a) e G(a, S(n)) = F (a, n,G (a,m)|m ≤ n).

Corollario 3.1.2. Se B e un insieme, b ∈ B e F : ω×F → B, dove F = p ⊆ ω×B|pe una funzione , allora ∃!G : ω → B tale che G(0) = b e G(S(n)) = F (n,G m|m ≤ n).

Esempio 3.1.1. Se f : A → A, sia A = B, h = id A e F : A × ω × F →A,(a, n, p) 7→ f(p(a, n)). Per il teorema c’e un’unica G : A × ω → A tale cheG(a, n) = f (n)(a). Infatti:

G(a, 0) = f (0)(a) = h(a) = id A

G(a, 1) = F (a, 0, G (a,m)|m ≤ 0) = F (a, 0, G(a, 0)) = f(G(a, 0)) = f(h(a)) = f (1)(a) = f(a)

41

G(a, 2) = F (a, 1, G (a,m)|m ≤ 1) = F (a, 0, G(a, 1)) = f(G(a, 1)) = f(f(a)) = f (2)(a)

e cosı via · · · .

Esempio 3.1.2. La funzione somma e definita ricorsivamente nella seconda variabilemediante le equazioni:

n+ 0 = n

n+ S(m) = S(n+m).

Se A = ω × ω,B = ω,h = id ω e:

F ((n, k),m, p) =

S(p(n, k)) se S(k) = m e (n, k) ∈ dom(p)

0 altrimenti

ottengo la funzione + = G : (ω × ω) × ω → ω che e definita da G((n, 0), 0) = n eG((n, k), S(m)) = F ((n, k),m,G ((n, k), t)|t ≤ m) = S(G((n, k),m)) = S(n +k) = n+m ovvero proprio la definizione di somma.

Esempio 3.1.3. A partire dall’addizione possiamo definire il prodotto mediante leequazioni:

n · 0 = 0

n · S(m) = (n ·m) + n.

In questo caso la funzione h e identicamente 0 mentre:

F ((n, k),m, p) =

S(p(n, k)) + n se S(k) = m e (n, k) ∈ dom(p)

0 altrimenti

Esempio 3.1.4. Mediante il corollario definisco la funzione fattoriale ! = G : ω → ωche viene ottenuta dal corollario ponendo B = ω,b = 1 e

F (n, p) =

p(k) · n se S(k) = n

0 se n = 0

quindi 0! = G(0) = 1 e S(k)! = G(S(k)) = F (k,G m|m ≤ k)) = G(k) · S(k) =k! · n.

Proposizione 21. Ogni ordine stretto ≺ su un insieme finito non vuoto X ha ele-menti massimali e elementi minimali, in particolare ≺ e relazione ben fondata suX.

Dimostrazione. Dimostriamo che esistono elementi massimali poiche per quelli mini-mali bastera considerare l’ordinamento x ≺−1 y ⇔ y ≺ x. Per assurdo supponiamoche X non abbia elementi massimali ovvero ∀x ∈ X∃y ∈ X(x ≺ y). Fissiamo unaenumerazione xi|i ≤ n di X e consideriamo la g : ω → S(n) definita come segue:

g(0) = 0 g(S(i)) = min j ≤ n|xg(i) ≺ xj

(per ipotesi l’insieme j ≤ n|xg(i) ≺ xj non e vuoto, quindi g(i) e definito per tuttigli i ∈ ω). Verifico per induzione su j ∈ ω che:

∀i < j(xg(i) ≺ xg(j)).

Se j = 0 e banale. Se j non e zero allora esiste m tale che j = S(m) con i ≤ mquindi per ipotesi induttiva xg(i) ≺ xg(m), ma si ha anche che xg(m) ≺ xg(S(m)) = xg(j)per costruzione, quindi xg(i) ≺ xg(j). Se i = m, allora xg(i) ≺ xg(j) per costruzione.Quindi g e iniettiva ed ho una mappa che mappa ω in un insieme finito:assurdo.

Osservazione 36. La funzione g e definita per il teorema di ricorsione precedente.

Teorema 3.1.3. Siano X, Z classi, sia R ⊆ X × X irriflessiva, regolare e benfondata e sia F : Z × X × V → V . Allora ∃!G : Z × X → V tale che ∀(z, x) ∈Z ×X(G(z, x) = F (z, x,G (z, y)|yRx)).

Osservazione 37. Con la notazione Ω ≤ Ord si intende Ω = Ord ∨ Ω ∈ Ord.

Teorema 3.1.4. Ω ≤ Ord, Z una classe. Allora ∃!G : Z × Ω→ V tale che

G(z, α) =

H(z) se α = 0

K(z, α,G z × α) con α successoreL(z, α,G z × α) con α limite

,

dove dom(H) = Z,dom(K) = Z × α ∈ Ω|α successore × V e dom(L) = Z × α ∈Ω|α e limite × V .

Teorema 3.1.5. Ω ≤ Ord, Y un insieme. Allora ∃!G : Ω→ V tale che

G(α) =

Y se α = 0

K(α,G α) con α successoreL(α,G α) con α limite

,

dove dom(K) = α ∈ Ω|α successore × V e dom(L) = α ∈ Ω|α e limite × V .

3.2 Funzioni continue

Sia A ≤ Ord.Una funzione f : A → Ord si dice continua se ∀λ ∈ A(λ limite⇒ f(λ) = supα<λ f(α)).

Osservazione 38. E’ noto che se possiedo un insieme linearmente ordinato possodefinire una topologia tramite l’ordine. Ogni ordinale successore e un punto isolatomentre questo non e vero per i punti limite, che non sono mai isolati.

Proposizione 22. Se f : Ord → Ord e crescente e continua, allora per ogni limiteλ e per ogni X ⊆ λ tale che supX = λ,

f(λ) = supν∈X

f(ν).

Se f e anche strettamente crescente, allora f(λ) e ordinale limite.

Dimostrazione. Sia ν < λ allora f(ν) ≤ f(λ) cioe supν∈X f(ν) ≤ f(λ). Per il vice-versa osservo che

⋃X = λ e un ordinale quindi per qualche γ:

f(λ) = supν<λ

f(ν) = supν<γ<X

f(ν) ≤ supν<γ<X

f(γ) = supγ∈X

f(γ).

Per la seconda parte se f e strettamente crescente faccio vedere che⋃f(λ) =

f(λ). Se ν ∈⋃f(λ) allora ν ∈ α ∈ f(λ) per qualche α quindi ν ∈ f(λ), cioe⋃

f(λ) ⊆ f(λ). Se ν ∈ f(λ) allora ν ∈ supγ<λ f(γ) ∈ f(λ) ovvero ν ∈⋃f(λ) quindi

f(λ) ⊆⋃f(λ)

Lemma 3.2.1. Se f : Ord → Ord e strettamente crescente e continua allora∀α∃α(f(α) = α).

Dimostrazione. Definisco una successione 〈αn|n ∈ ω〉 nel seguente modo α0 = S(α)e αS(n) = f(αn). Sia α = supn αn. Se α0 = f(α0) allora ho un punto fisso eα = α0. Se α0 < f(α0) = α1, allora αn < αS(n) e α = supn αn e limite. Alloraf(α) = supν<α f(ν) = supn f(αn) = supn αS(n) = α.In qualunque caso α e il piupiccolo punto fisso per f maggiore di α.

Definizione 3.2.1. ℵ0 = ω, ℵS(α) = (ℵα)+ , ℵλ = supα<λ ℵαℵ : Ord→ Ord e strettamente crescente e continua, quindi esistono cardinali tali

che κ = ℵκ, il piu piccolo dei quali e l’estremo superiore di

ℵ0, ℵℵ0 , ℵℵℵ0 , · · ·

Osservazione 39. Altre importanti notazioni utilizzate sono le seguenti:

ℵ1 = ω1, ℵ2 = ω2, · · · , ℵω = ωω, · · · , ℵα = ωα.

Osservazione 40. La funzione ℵ : Ord→ Card \ ω enumera la classe dei cardinaliinfiniti.

3.3 Aritmetica ordinale

Tramite la ricorsione (Teorema 3.1.4) e possibile definire operazioni di somma, pro-dotto ed esponenziazione sugli ordinali come le uniche funzioni da Ord×Ord→ Ordche soddisfano certe proprieta.

Definizione 3.3.1. La somma tra due ordinali α, β si definisce:

α+β =

α se β = 0

S(α+γ) se β = S(γ)supγ<β α+γ se β risulta limite

Proposizione 23. Per la somma valgono le seguenti proprieta:1)β < β′ ⇒ α+β < α+β′.2)Se λ e limite e λ = supi∈I λi,allora α+λ = supi∈I α+λi.3)(α+β)+γ = α+(β+γ).4)α < α′ ⇒ α+β ≤ α′+β.5)0+β = β.6)β ≤ α+β.7)α ≤ β ⇔ ∃!γ(α+γ = β).

Dimostrazione. 1)Per induzione su β′. Se β′ = 0 allora vale per motivi bana-li, possiamo supporre che β′ = S(β′′) allora β′′ ≥ β quindi α+β′′ ≥ α+β maα+β′′ < S(α+β′′) = α+β′, da cui le conclusioni. Se β′ e limite e β′ > β allora:

α+β′ = supγ<β′

α+γ ≥ α+S(β) > α+β.

2)La funzione ν 7→ α+ν e crescente e continua, quindi α+λ e limite (per un esempioprecedente). Se λ = supi∈I λi allora α+λi ≤ α+λ quindi supi∈I α+λi ≤ α+λ. Vi-ceversa, se β < α+λ allora posso trovare un γ < λ tale che β < α+γ inoltre possofissare j in I tale che γ < λj. Dunque α+γ < α+λj. 3)Per induzione su γ. Se γ = 0e banale. Supponiamo la proprieta valga per un γ:

(α+β)+S(γ) = S((α+β)+γ)(per definizione della somma)= S(α+(β+γ))(per ipotesi induttiva)= α+S(β+γ)(per definizione di somma)= α+(β+S(γ))(per definizione di somma).Supponiamo che γ sia limite (allora anche α+γ e limite) e che γ′ < γ allora:(α+β)+γ = supγ′<γ(α+β)+γ′( per definizione della somma)

= supγ′<γ α+(β+γ′)(per ipotesi induttiva)= α+(β+γ)(per 2) e β+γ limite).4),5),6) seguono per semplice induzione su β. 7)L’unicita di γ segue dal punto1) poiche supponiamo che siano due γ 6= γ′ allora supponiamo che γ < γ′,per 1)α+γ < α+γ′ = β:assurdo. Dimostriamo l’esistenza. Per 4) l’insieme

ξ|α+ξ < β

e contenuto in β e dunque e ordinale (poiche e transitivo ed i suoi elementi sonotransitivi) che chiamiamo γ. Poiche γ 6∈ γ si ha α+γ ≥ β. Dimostriamo ora cheα+γ ≤ β. Se γ = 0 allora α ≤ β. Se γ = S(δ) allora δ < β quindi α+γ ≤ β. Seinvece γ e limite allora α+γ = supξ∈γ α+ξ ≤ β.

Osservazione 41. La somma non e commutativa.

Definizione 3.3.2. La moltiplicazione tra due ordinali α, β si definisce:

α·β =

0 se β = 0

(α·γ)+γ se β = S(γ)supγ<β α·γ se β risulta limite

Definizione 3.3.3. L’esponenziazione tra due ordinali α, β si definisce:

α.β =

1 se β = 0α.γ·α se β = S(γ)

supγ<β α.γ se β risulta limite

Proposizione 24. Per il prodotto valgono le seguenti proprieta:1)Supponiamo α 6= 0. Allora β < β′ ⇒ α·β < α·β′.2)Se λ e limite e α 6= 0 allora α·λ e limite e se λ = supi∈I λi,allora α·λ = supi∈I α·λi.3)α·(β+γ) = α·β+(α·γ).4)(α·β)·γ = α·(β·γ).5)α < α′ ⇒ α·β ≤ α′·β.6)0·β = 0 e 1·β = β.7)Se α 6= 0 allora β ≤ α·β.8)Se α > 0 allora ∀β > 0∃!γ ≤ β∃!δ < α(α·γ+δ = β).

Dimostrazione. Le proprieta dalla 1) alla 7) si dimostrano in modo analogo alla pro-posizione precedente. Dimostriamo la proprieta 8). Cominciamo con il verificarel’unicita di γ e δ. Se α·γ+δ = α·γ′+δ′ e γ 6= γ′, per esempio, γ < γ′, allora per 1):

β = α·γ+δ < α·(γ+1) ≤ α·γ′ ≤ α·γ′+δ′ = β

contraddizione! Quindi γ = γ′.Se, per esempio δ < δ′ allora:

β = α·γ+δ < α·γ+δ′ = β

contraddizione! Dimostriamo l’esistenza di γ e δ.Se α > β allora prendo γ = 0 eδ = β. Se cosı non fosse ho che α ≤ β, per 1) esiste un γ tale che β < α·γ alloraconsidero il piu piccolo γ per cui vale chiamandolo γ. Poiche γ = 0 e γ limite eimpossibile allora deve essere un successore cioe γ = S(γ). Quindi α·γ ≤ β e γ ≤ βper 1) e 7). Se vale l’uguaglianza, allora poniamo δ = 0. Se invece α·γ < β per laparte 7) della proposizione precedente si ha che esiste un δ tale per cui α·γ+δ = β.Poiche α·γ+α > β segue δ < α.

Esempio 3.3.1.

ω+3+ω+5+ω = ω+(3+ω)+(5+ω) = ω+ω+ω

ω+1 = S(ω+0) = ω+1

1+ω = supν∈ω

1+ν = ω.

La somma e il prodotto ordinale possono essere definiti in modo alternativo:

Definizione 3.3.4. La somma di due insiemi ordinati 〈A,≺〉 e 〈B,〉 e 〈A× 0 ∪B × 1, <〉 dove:(a1, 0) < (a2, 0)⇔ a1 ≺ a2

(b1, 0) < (b2, 0)⇔ b1 b2

(a, 0) < (b, 1) per ogni a ∈ A e b ∈ B.

Osservazione 42. La somma di due buoni ordini A, B e un buon ordine di tipoot(A)+ot(B).

Definizione 3.3.5. Il prodotto di due insiemi ordinati 〈A,≺〉 e 〈B,〉 e 〈A×B,<〉dove:(a1, b1) < (a2, b2)⇔ [(a1 ≺ a2) ∨ (a1 = a2 ∧ (b1 b2))].

Osservazione 43. Il prodotto di due buoni ordini A, B e un buon ordine di tipoot(B)·ot(A).

Definizione 3.3.6. Se X e bene ordinabile la cardinalita di X e il piu piccolo ordinale|X| in biezione con X. Quindi la cardinalita di un insieme e un cardinale.

Vediamo qualche altro esempio di insieme bene ordinato in matematica.

Esempio 3.3.2. I sottoinsiemi di R.

ot

(n

n+ 1|n ∈ ω

)= ot

(−1 ∪

n

n+ 1|n ∈ ω

)= ω

ot

(n

n+ 1|n ∈ ω

∪ 1

)= ω+1

ot

(n

n+ 1|n ∈ ω

∪

2n+ 1

n+ 1|n ∈ ω

)= ω+ω

ot

(n

n+ 1|n ∈ ω

∪

2n+ 1

n+ 1|n ∈ ω

∪ 2

)= ω+ω+1

ot

(nm− 1

n|n,m ∈ ω \ 0

)= ω·ω

Esempio 3.3.3. I polinomi. Se f e g sono funzioni reali di variabile reale, definiamol’ordinamento

f ≺ g ⇔ ∃M∀x > M(f(x) < g(x)).

L’ordine ≺ sull’insieme N[X] dei polinomi in una variabile X con coefficienti inN e un buon ordine del tipo ω.ω. Infatti f ≺ g se e solo se deg(f) < deg(g),dove ildeg(f) denota il grado di f , oppure deg(f) = deg(g) = n, f = anX

n + · · · + a0, g =bnX

n + · · · + b0 e se k ≤ n e il piu piccolo indice tale che ak 6= bk, allora ak < bk.Possiamo definire un isomorfismo F : 〈N[X],≺〉 → 〈ω.ω, <〉

F (anXn + · · ·+ a0) = ω.n·an+ · · · +a0.

Proposizione 25. Per l’esponenziale valgono le seguenti proprieta:1)0.α = 1 se α = 0 o se α e ordinale limite.2)0.α = 0 se α e ordinale successore.3)1.α = 1.4)α.0 = 1.5)α.1 = α.6)α.2 = α·α.7)α > 1 e β > 1⇒ α < α.β.8)α > 1⇒ β ≤ α.β.9)α > 1 e β < γ ⇒ α.β < α.γ.10)α < β ⇒ α.γ ≤ β.γ.11)α.(β+γ) = α.β·α.γ se α 6= 0.12)(α.β).γ

= α.(β·γ) se α 6= 0.13)1 < α, β ⇒ 1 < α.β.14)1 < α, β ⇒ α·β ≤ α.β.

Dimostrazione. Dimostriamo ad esempio la 11). Se γ = 0 allora:

α.(β+0) = α.β·1 = α.β·α.0.

Se γ = S(δ) allora:

α.(β+S(δ)) = α.S(β+δ) = α.(β+δ)·α =

=(α.β·α.δ

)·α = α.β·

(α.δ·α

)=

α.β·(α.S(δ)

).

Se γ e limite allora:

α.(β+γ) = α.(β+ supν<γ ν) = α. supν<γ β+ν =

= supν<γ

α.(β+ν) = supν<γ

α.β·α.ν = α.β· supν<γ

α.ν =

= α.β·α.γ

Lemma 3.3.1. Supponiamo che α = γ.δ0·ε0+ζ0,con δ0 ≤ α,0 < ε0 < γ,ζ0 < γ.δ0

e, che β = γ.δ1·ε1+ζ1,con δ1 ≤ β,0 < ε1 < γ,ζ1 < γ.δ1 allora si ha che α < β se esoltanto se vale una delle tre condizioni:1)δ0 < δ1.2)δ0 = δ1 e ε0 < ε1.3)δ0 = δ1,ε0 = ε1 e ζ0 < ζ1.

Dimostrazione. Se δ0 < δ1 allora:α = γ.δ0·ε0+ζ0 < γ.δ0·(ε0+1) ≤ γ.δ0·γ ≤ γ.(δ0+1) ≤ γ.δ1 ≤ γ.δ1·ε1 ≤ β.Se δ0 = δ1 e ε0 < ε1 allora:α = γ.δ0·ε0+ζ0 < γ.δ0·(ε0+1) ≤ γ.δ1·ε1 ≤ β.Se δ0 = δ1,ε0 = ε1 e ζ0 < ζ1 allora e banale.Viceversa se non vale 1), 2), 3) allora hodue casi: nel primo caso δ0 = δ1, ε0 = ε1 e ζ0 = ζ1, allora α 6< β. Nel secondo casovale una delle tre condizioni e, scambiando gli 0 con gli 1 ottengo α 6< β.

Teorema 3.3.2. Se α > 0,β > 1 allora ∃!γ, ∃!δ∃!ε tale che α = β.γ·δ+ε,γ ≤ α,0 <δ < β e ε < β.γ.

Dimostrazione. Se γ = 0 allora β.0 = 1 ≤ α, e β.S(α) ≥ S(α) > α, prendo γ taleche β.γ ≤ α < βS(γ), scelgo δ e ε tali che α = β.γ·δ+ε con δ ≤ α e ε < β.γ per ladivisione, e chiaro che γ ≤ α. Se δ = 0, allora α = ε < β.γ, il che e contraddittorio.Infine β ≤ δ ⇒ α ≥ β.γ·δ ≥ β.γ·β = β.S(γ): contraddizione!, allora δ < β. Con cio edimostrata l’esistenza. L’unicita discende dal lemma precedente.

Teorema 3.3.3. Se α < ω.β allora α+ω.β = ω.β.

Dimostrazione. Iniziamo con il dimostrare che se γ < β ⇒ ω.γ+ω.β = ω.β. Infattiprendo un δ tale che β = γ+δ; allora:

ω.γ + ω.β = ω.γ+ω.γ·ω.δ = ω.γ·(1+ω.δ) = ω.γ·ω.δ = ω.β.

Qui noi sappiamo che ω.δ ≥ ω, perche δ ≥ 1 e ω.1 = ω. Con una semplice indu-zione su m, otteniamo che:

se γ < β, allora ω.γ·m+ω.β = ω.β, per ogni m. Supponiamo ora che α < ωβ. Il casoβ = 0 e banale, come lo e il caso ω > α. Assumo che α ≥ ω e pongo α = ω.γ·m+δ,con m 6= 0,δ < ω.γ; allora chiaramente γ < β, e quindi:

ω.β ≤ α+ω.β = (ω.γ·m+δ)+ω.β ≤ ω.γ·(m+1)+ω.β = ω.β

Definizione 3.3.7. α e un γ-numero se e solo se β+α = α per ogni β < α.

Osservazione 44. Per il teorema visto sopra ωγ e sempre un γ-numero, ed e ovvioche tali lo sono anche 0 e 1; questi sono inoltre i soli γ-numeri.

Teorema 3.3.4. Le seguenti tre condizioni sono equivalenti:a)α e un γ-numero.b)∀β, γ < α,β+γ < α.c)α = 0,oppure α = ω.β per un qualche β.

Dimostrazione. a)⇒b):Abbiamo β+γ < β+α = α.b)⇒ c):Assumiamo che α 6= 0, 1per la b) ω ≤ α in base ad un teorema precedente prendo β,m, γ tali che α =ω.β·m+γ, con m 6= 0 e γ < ω.β. Se γ 6= 0, allora ω.β·m < α,γ < ω.β ≤ ω.β·m < α, eω.β·m+γ = α, in contraddizione con b); dunque γ = 0.Se m > 1, allora m = n+1 perun qualche n, e ω.β·n+ω.β = α,per ω.β·n < α e ω.β < α, di nuovo in contraddizionecon la b);quindi α = ω.β.c)⇒a) per il teorema precedente.

Definizione 3.3.8. α e un δ-numero se e solo se per ogni β tale che 0 < β < α,β·α = α.

Teorema 3.3.5. Le seguenti tre condizioni sono equivalenti:a)α e un δ-numero.b)∀β, γ < α, β·γ < α.c)α ∈ 0, 1, 2, oppure α = ω.ω

.βper un qualche β.

Dimostrazione. a)⇒b):Se assumiamo che β, γ < α,abbiamo β 6= 0 e β·γ < β·α = αoppure β = 0 e β·γ = 0 < α.b)⇒c):assumiamo α 6∈ 0, 1, 2; allora α 6∈ ω, perchealtrimenti α = m+1 per qualche m ≥ 2, e dunque m·m ≥ α; il fatto che m·m ≥ m+1per ogni m ≥ 2 si dimostra facilmente. Quindi ω ≤ α. Inoltre α e un γ-numero.Infatti suppongo che β, γ < α, vogliamo fare vedere che β+γ < α. Possiamo assumereche 1 < β, γ; allora β+γ ≤ β·γ < α cosı α e un γ-numero. Quindi α = ω.γ perqualche γ. Se δ, ε < γ, allora ω.δ, ω.ε < ω.γ, cosicche ω.δ·ω.ε < ω.γ;vale a dire,ω.( delta+ε) < ω.γ. Cio implica che δ+ε < γ, e che γ e un γ-numero. Poniamo γ = ω.β,allora α = ω.ω

.β.c)⇒a) basta mostrare che ω.ω

.βe un δ-numero. Assumiamo che

0 < γ < ω.ω.γ

; se γ < ω, allora γ·ω.ω.β = ω.ω.β

. Assumiamo ω ≤ γ; poiche γ < ω.ω.β

,deve essere β 6= 0, e quindi ω.β e un ordinale limite. Per un teorema precedenteprendo un δ, un m e un ε tali che m 6= 0,ε < ω.δ e γ = ω.δ·m+ε; allora δ < ω.β,quindi δ+1 < ω.β, e

ω.ω.β ≤ γ·ω.ω.β = (ω.δ·m+ε)·ω.ω.β

≤ (ω.δ·m+ω.δ)·ω.ω.β = ω.δ·(m+1)·ω.ω.β

≤ ω.(δ+1)·ω.ω.β = ω.((δ+1)+ω.β) = ω.ω.β

Definizione 3.3.9. α e un ε-numero se e solo se β.α = α per ogni β tale che 1 <β < α.

Teorema 3.3.6. Ogni ε-numero e un δ-numero.

Dimostrazione. Assumiamo che α sia un ε-numero, e che 0 < β < α; se β = 1, alloraβ·α = α; se 1 < β, allora α ≤ β·α ≤ βα = α.

Teorema 3.3.7. La seguenti condizioni sono equivalenti:a)α e un ε-numero.b)α = 1,oppure per ogni β, γ < α, βγ < α.

Dimostrazione. a)⇒b):E’ chiaro che possiamo assumere che α 6= 0, 1, 2. Se β = 0,allora β.γ ≤ 1 < α; se β = 1, allora β.γ = 1 < α; e se 1 < β, allora β.γ < β.α = αcosı b).b)⇒a):possiamo assumere che α 6= 0, 1, 2. In base a b) e per le proprietadell’esponenziale α e un δ-numero. Supponiamo che 1 < β < α; se α = S(γ) perqualche γ, allora α ≤ β.α = β.S(γ) = β.γ·β < α, per la b) e poiche α e δ-numero, e cioe impossibile. Cosı α deve essere un ordinale limite, e α ≤ β.α =

⋃γ<α β

.γ ≤ α,per lab); dunque α = β.α.

Teorema 3.3.8. 0, 1, 2, ω sono ε-numeri, e sono i soli ε-numeri ≤ ω.

Teorema 3.3.9. Per ogni α > 1, il minimo ε-numero maggiore di α e l’ordinale νω,dove ν e definito per ricorsione come segue: ν0 = α, ν(m+1) = νm.νm per m ∈ ω, eνω =

⋃m∈ω νm.

Dimostrazione. In primo luogo sia β un qualunque ε-numero > α; si dimostra facil-mente, per induzione su m, che νm < β per ogni m ∈ ω, facendo appello alla parteb) del teorema precedente; quindi νω ≤ β. In secondo luogo facciamo vedere νω eesso stesso un ε-numero:supponiamo che γ, δ < νω; allora esistono un m e un n ∈ ωtali che γ < νm e δ < νn; poniamo m ≤ n; dunque:

γ.δ ≤ νm.νn = ν(n+1) < ν(n+2) ≤ νω.

Questo conclude la dimostrazione.

Se applico il teorema a α = ω ottengo il primo ε-numero > ω; in tal caso ν0 =ω,ν1 = ω.ω, · · · . Il primo ε-numero maggiore di ω si scrive in modo naturale come

ω.ω.ω · ·

·

, ed e uso chiamarlo ε0. In molti casi si fa appello all’induzione fino a ε0.

Osservazione 45. Se 〈I,〉 e 〈Xi,≤i〉 sono insiemi bene ordinati, allora ≤lex e unbuon ordine su

⋃i∈Ii ×Xi. Dove:

(i, x) ≤lex (j, y)⇔ (i ≺ j ∨ (i = j ∧ x ≤i y))

Definizione 3.3.10. Sia 〈αi|i < ν〉 una successione di ordinali, e possibile definirela somma ordinale:

∑i<ναi = ot

⟨⋃i<ν

i × αi,≤lex

⟩

Osservazione 46. Si dimostra che se ν = ξ+1, allora∑

i<ναi =∑

i<ξαi+αξ,in

particolare se ν = 2,∑

i<ναi = α0+α1.Se ξ < ν, allora∑

i<ξαi <∑

i<ναi e ladisuguaglianza e stretta se e solo se αj 6= 0 per qualche ξ ≤ j < ν. Se ν e limite,

allora∑

i<ναi = supξ<ν∑

i<ξαi.

Teorema 3.3.10. Per ogni α esiste un m ∈ ω e esistono ordinali γ0, · · · , γm−1 eδ0, · · · , δm−1 con α ≥ γ0 > γ1 > · · · > γm−1 e 0 < δi < β per ogni i < m, tali che:

α = β.γ0·δ0+ · · · +β.γm−1 ·δm−1.

Inoltre m, i γi e i δi sono unici.

Osservazione 47. Nel teorema precedente l’espressione rappresenta lo sviluppo di αin base β. Nel caso β = ω e gli ordinali δi sono numeri naturali si parla di formanormale di Cantor.

Esempio 3.3.4. Scrivere in forma normale di Cantor:[(ω·3+ω.7

)·ω.3]·ω.2.

Si ha che [(ω·3+ω.7

)·ω.3]·ω.2 =

=[ω.7·ω.3

]·ω.2 = ω.12.

Esempio 3.3.5. Scrivere in forma normale di Cantor:[ω.8+ω.ω·3

]·(ω+1).

Si ha che [ω.8+ω.ω·3

]·(ω+1) =

=[ω.8+ω.ω·3

]·ω+

[ω.8+ω.ω·3

]·1 =

= ω.ω·3+1+ω.ω·3.

3.4 Aritmetica cardinale

La somma e prodotto cardinale sono le operazioni binarie Card × Card → Carddefinite da:

κ+ λ = |κ× 0 ∪ λ× 1|

κ · λ = |κ× λ|.

Teorema 3.4.1. ω + ω = ω · ω

Dimostrazione. Considero le biezioni:ω × 0 ∪ ω × 1 → ω, (n,m) 7→ 2n+mω × ω → ω, (n,m) 7→ 2n(2m+ 1)− 1.

Si dimostra facilmente che somma e prodotto cardinale sono operazioni associativee vale la proprieta distributiva del prodotto rispetto la somma.

Proposizione 26. Se κ, λ ≥ 2, allora max (κ, λ) ≤ κ + λ ≤ κ · λ ≤ max (κ, λ) ·max (κ, λ).

Lemma 3.4.2. ∀n,m ∈ ω(m+ n = m+n ∈ ω), ∀n,m ∈ ω(m · n = m·n ∈ ω).

Dimostrazione. Induzione su n.

Definiamo un buon ordine <G su Ord × Ord : (α, β) <G (γ, δ) ⇔ [max (α, β) <max (γ, δ) ∨ (max (α, β) = max (γ, δ) ∧ (α, β) <lex (γ, δ))] dove (α, β) <lex (γ, δ) ⇔α < γ ∨ (α = γ ∧ β < δ).

Teorema 3.4.3. Sia κ un cardinale infinito. Allora ot(κ× κ,<G) = κ e |κ× κ| = κ.

Dimostrazione. Per induzione su κ ≥ ω. Osserviamo che ∀α < κ(|α × α| < κ).Dimostriamolo. Se α < ω e banale, se ω ≤ α < κ allora ω ≤ |α| < κ quindi peripotesi induttiva, ||α| × |α|| = α < κ ma |α| × |α| e in biezione con α × α, quindi|α × α| < κ. Inoltre ∀α, β < κ(ot(pred(α, β), <G) < κ) e quindi ot(κ × κ,<G) ≤ κ.Dimostriamolo.pred(α, β) ⊆ ν × ν con ν = max α, β + 1, quindi |pred(α, β)| ≤|ν × ν| < κ. Allora ot(pred(α, β), <G) < |pred(α, β)|+ ≤ κ.Infine la funzione 〈κ,<〉 → 〈κ× κ,<G〉, α 7→ (α, 0) e strettamente crescente, quindi κ ≤ ot(κ× κ,<G).

Corollario 3.4.4. Se κ e λ sono cardinali e max (κ, λ) ≥ ω,

max (κ, λ) = κ+ λ = κ · λ.

Esempio 3.4.1.ℵ5 + ℵ3 = ℵ5 = ℵ5 · ℵ3.

Osservazione 48. ℘(X) e in biezione con X2 (e l’insieme delle funzioni caratteri-stiche).

Teorema 3.4.5 (Cantor). Non esiste nessuna suriezione da X in ℘(X).

Dimostrazione. Siano π : X → ℘(X) una suriezione, considero Y = x ∈ X|x 6∈π(x). Fisso un x ∈ X tale per cui π(x) = Y allora x ∈ Y ⇔ x 6∈ π(x) = Y :contraddizione.

Proposizione 27. Se 2 ≤ κ ≤ λ e λ ≥ ω allora λ2,λ κ,λ λ sono in biezione.

Dimostrazione. Si ha che λ2 ⊆λ κ ⊆λ λ quindi esiste una iniezione λ2 λ λ inoltreho che ℘(λ× λ) e in biezione con ℘(λ) quindi, λλ ⊆ ℘(λ× λ) λ 2. Si conclude peril teorema di S.Bernstein.

Sia κ ≥ ω e f : 〈κ × κ,<G〉 → 〈κ,<〉 l’isomorfismo. Definiamo per ricorsione sun ≥ 1 delle biezioni jn :n κ→ κ. Poniamo j1(〈α〉) = α e poiche n+1κ→n κ× κ, s 7→(s n), s(n)), e biezione, possiamo definire jn+1 con il diagramma:

n+1κ→n κ× κ→ κ× κ→ κ

s 7→ (s n, s(n)) 7→ (jn(s n), s(n)) 7→ f(jn(s n), s(n)).

Quindi |nκ| = κ per ogni n.|<ωκ| = κ dato che jω :<ω κ→ ω × κ e iniettiva:

jω(s) =

(0, 0) se s = ∅

(n, jn(s)) se lh(s) = n > 0

Teorema 3.4.6. Se X e bene ordinabile e infinito, allora |<ωX| = |X|.

Un linguaggio del primo ordine L che ha κ simboli non logici (simboli di predicatoe funzione) si dice che ha cardinalita κ.

Corollario 3.4.7. Se L e un linguaggio del primo ordine che ha una quantita finitadi simboli non logici allora L ha ℵ0 formule. Se L e un linguaggio del primo ordineche ha κ simboli non logici allora L ha κ formule.

Dimostrazione. L’insieme X dei simboli logici e non logici ha cardinalita rispet-tivamente ℵ0 e κ, quindi X<ω l’insieme delle stringhe su X ha cardinalita ℵ0 eκ.

Definizione 3.4.1. L’esponenziale cardinale κλ e definita come |λκ|, la cardinalitadell’insieme delle f : λ → κ. Se λ ≥ ω, per garantire che λκ sia bene ordinabileoccorre utilizzare l’assioma della scelta.

Teorema 3.4.8. AC implica che ogni insieme e in biezione con un ordinale.

Dimostrazione. Sia X 6= ∅ considero C : ℘(X)\∅ → X funzione di scelta. Definiscox0 = C(X) e xα = C(X \ xβ|β < α) se xβ|β < α 6= ∅ altrimenti non e definita.Se xα e definita e β < α allora xα 6= xβ quindi la funzione ν 7→ xν e iniettiva. Se xνfosse definita per ogni ν < Hrtg(X) avrei che Hrtg(X) X:assurdo. Dunque esisteα tale che X = xβ|β < α.

Teorema 3.4.9. Sono equivalenti:1)AC.2)Principio di massimilita di Hausdorff: Oqni insieme parzialmente ordinato contie-ne una catena massimale.3)Lemma di Zorn: Ogni insieme parzialmente ordinato in cui ogni catena ha unestremo superiore, contiene un elemento massimale.

Dimostrazione. 1 ⇒ 2. Sia X un insieme parzialmente ordinato dal ≤,suppongonon ci siano catene massimali. Sia C una catena di X non massimale, consideroK(C) = x ∈ X \ C|C ∪ x e una catena di X. Questo e un insieme non vuoto eposso considerare una funzione di scelta F : ℘(X) \ ∅ → X. Allora g : Hrtg(X) X,g(α) = F (K(g(β)|β < α)),un assurdo. 2 ⇒ 3. Sia X un insieme parzialmenteordinato di X in cui ogni catena C massimale ha un maggiorante. Per Hausdorffesiste una catena massimale e il suo maggiorante deve appartenere alla catena Cquindi esiste l’elemento massimale. 3 ⇒ 1. Sia Ai|i ∈ I una famiglia di insiemi

non vuoti. L’insieme X = p|p funzione, dom(p) ⊆ I e ∀i ∈ I(p(i) ∈ Ai) ordinatoper inclusione soddisfa le ipotesi del lemma di Zorn, quindi c’e un elemento massimalef ∈ X. Se esistesse un i0 ∈ I\dom(f) allora f∪(i0, a) ∈ X, per un qualsiasi a ∈ Ai0 ,contro la massimalita della f . Quindi f e una funzione di scelta per Ai|i ∈ I.

Osservazione 49. Il dominio della funzione massimale e proprio I.

Teorema 3.4.10 (Cantor). Se 〈X,〉 e un ordine lineare, denso, senza primo edultimo elemento allora e isomorfo a Q.

Dimostrazione. X = xn|n ∈ ω e Q = qn|n ∈ ω siano enumerazioni senza ripeti-zioni. Costruiremo delle funzioni pn che godono delle seguenti proprieta:1)p0 ⊆ p1 ⊆ · · · .2)xn ∈ dom(p2n) ⊂ X e qn ∈ ran(p2n+1) ⊂ Q.3)dom(pn) e finito e pn : dom(pn)→ ran(pn) e biezione ed ∀x, y ∈ dom(pn)(x y ⇔pn(x) ≤ pn(y)).Quindi F :

⋃n∈ω pn : X → Q e un isomorfismo. p0 = (x0, q0). Se n + 1 = 2m e

xm ∈ dom(pn) oppure n+1 = 2m+1 e qm ∈ ran(pn) allora pn = pn+1. Se n+1 = 2me xm 6∈ dom(pn) allora distinguo in tre casi:1)xm min (dom(pn)) allora q = min (ran(pn))− 1 e pn+1 = pn ∪ (xm, q).2)xm max (dom(pn)) allora q = max (ran(pn)) + 1 e pn+1 = pn ∪ (xm, q).3)x xm x′ con x, x′ ∈ dom(pn) elementi consecutivi allora,q = pn(x)+pn(x′)

2e

pn+1 = pn ∪ (xm, q).Infine se n+ 1 = 2m+ 1 e qm 6∈ ran(pn) allora distinguo in tre casi:1)qm < min (ran(pn)).2)qm > max (ran(pn)).3)q < qm < q′ con q, q′ ∈ ran(pn).Si procede come prima sfruttando il fatto che X non ha massimo, non ha minimo ede denso.

Capitolo 4

Gli interi, i razionali ed i reali

4.1 Gli assiomi di Peano

Dopo avere costruito l’insieme dei numeri naturali N = ω e le sue operazioni arit-metiche abbiamo ottenuto la seguente struttura 〈N, S,+, ·, <, 0〉 che puo essere vistacome modello di una opportuna collezione di enunciati del primo ordine.

Definizione 4.1.1. Considero il linguaggio del prim’ordine LPA che ha:1)Un simbolo di funzione unario s.2)Due simboli di funzione binari + e ·.3)Un simbolo di relazione binaria <.4)Un simbolo di costante 0.

I postulati o assiomi di Peano sono:

1)∀x(s(x) 6= 0)2)∀x∀y(x 6= y ⇒ s(x) 6= s(y))3)∀x(x+ 0 = x)4)∀x∀y(x+ s(y) = s(x+ y))5)∀x(x · 0 = 0)6)∀x∀y(x · s(y) = (x · y) + x)7)∀x¬(x < 0)8)∀x∀y(x < s(y)⇔ (x < y ∨ x = y)9)∀y1, · · · , yn[(ϕ(0, ~y)∧∀x(ϕ(x, ~y)⇒ ϕ(s(x), ~y)))⇒ ∀xϕ(x, ~y)] per ogni LPA-formulaϕ(x, y1, · · · , yn)

Il sistema assiomatico ottenuto si chiama aritmetica di Peano.

57

4.2 Gli interi e i razionali

L’insieme Z degli interi relativi e definito come N × N/EZ dove EZ e la relazione diequivalenza definita da

(n,m)EZ(h, k)⇔ n+ k = h+m

L’ordinamento <Z e le operazioni di somma +Z e prodotto ·Z su Z sono definite da:

[(n,m)]EZ <Z [(n′,m′)]EZ ⇔ n+m′ < n′ +m

[(n,m)]EZ +Z [(h, k)]EZ = [(n+ h,m+ k)]EZ

[(n,m)]EZ ·Z [(h, k)]EZ = [(n · h+m · k, n · k +m · h)]EZ .

La funzione:

N→ Z, n 7→ [(n, 0)]EZ

e un morfismo iniettivo rispetto all’ordinamento e alle operazioni di somma e pro-dotto, quindi a tutti gli effetti, N puo essere identificato con un sottoinsieme di Z(e possibile dimenticarsi del pedice nella definizione di ordine, somma e prodotto).Gli interi della forma [(n, 0)]EZ si denotano con n e quelli della forma [(0, n)]EZ con−n. Chiaramente ogni z ∈ Z e della forma n o −n con n ∈ N, quindi la funzionef : N→ Z:

f(n) =

m se n = 2m

−m se n = 2m− 1

e una biezione.L’insieme Q dei razionali e definito come Z × (Z \ 0)/EQ doveEQ e la relazione di equivalenza definita da

(x, u)EQ(z, w)⇔ x · w = y · z

L’ordinamento <Q e le operazioni di somma +Q e prodotto ·Q su Q sono definiteda:

[(x, y)]EQ <Q [(z, w)]EQ ⇔ x · w < y · z

[(x, y)]EQ +Q [(z, w)]EQ = [(x · w + z · y, y · w)]EQ

[(x, y)]EQ ·Q [(z, w)]EQ = [(x · z, y · w)]EQ .

La funzione

Z→ Q, z 7→ [(z, 1)]EQ

e un morfismo iniettivo di anelli rispetto all’ordinamento, quindi a tutti gli effetti,Z puo essere identificato con un sottoinsieme di Q (e possibile dimenticarsi anchequi del pedice nella definizione di ordine, somma e prodotto). I razionali della forma[(z, w)]EZ si denotano con z

we ogni razionale puo essere scritto nella forma z

wcon z e

w relativamente primi. Quindi Q e in biezione con un sottoinsieme di Z× Z che e asua volta in biezione con N×N. Ricordando che |N×N| = N si ha che Q e in biezionecon un sottoinsieme di N e poiche N Z Q, per il teorema di Schroder-Bernsteingli insiemi N e Q sono in biezione.

4.3 I numeri reali

Definizione 4.3.1. Un sottoinsieme x ⊆ Q e una sezione di Dedekind se e un seg-mento iniziale proprio, privo di massimo, non vuoto di Q, cioe:

1)x 6= Q, ∅.2)∀q ∈ x∀p ∈ Q(p < q ⇒ p ∈ x).3)∀q ∈ x∃p ∈ x(q < p).

Le sezioni di Dedekind si dicono numeri reali e

R = x ∈ ℘(Q)|x e una sezione di Dedekind .

L’ordinamento e somma su R sono definiti da:

x <R y ⇔ x ⊂ y

x+R y = p+ q|p ∈ x ∧ q ∈ y

La definizione del ·R e leggermente piu laboriosa.

Definizione 4.3.2. Un insieme 〈L,≤〉 linearmente ordinato si dice completo seogni sottoinsieme non vuoto che ha un maggiorante, ha estremo superiore e ognisottoinsieme non vuoto che ha un minorante, ha estremo inferiore.

Teorema 4.3.1. 〈R,≤〉 e completo.

Per ogni x ∈ 2N sia:

Φ(x) =∞∑n=0

2x(n)

3n+1

si dimostra facilmente che la serie converge ad un reale in [0, 1] inoltre, se x n = y n, x(n) = 0 e y(n) = 1, allora Φ(x) < φ(y) ≤ Φ(x) + 3−n. La funzioneΦ : 2N [0, 1] e iniettiva e quindi ℘(N) R. Poiche R ⊆ ℘(Q) e ℘(Q) e inbiezione con ℘(N), ne segue che R ℘(N). Per il teorema di Schroder-Bernstein ela proposizione 26 segue:

Proposizione 28. Gli insiemi R, 2N e NNv sono equipotenti (cioe in biezione).

4.4 L’insieme di Cantor e il prodotto di spazi di

Cantor

Consideriamo la seguente costruzione.Fissiamo un intervallo chiuso I = [a, b] non de-genere (cioe a < b) di R e fissiamo un r ∈ (0, 1). Rimuoviamo da I l’intervallo apertocentrato nel punto medio di I di ampiezza r(b − a). Otteniamo cosı due intervallichiusi non degeneri:

I(0;r) =

[a, a+

1 + 2r

2(b− a)

],

I(1;r) =

[b− 1 + 2r

2(b− a), b

].

Definizione 4.4.1. Definiamo l’insieme ternario di Cantor come:

E1/3 =⋂n

E(n)1/3,

dove E(0)1/3 e l’intervallo [0, 1],E

(n)1/3 ⊆ E

(n−1)1/3 e unione di 2n intervalli chiusi di lunghez-

za 3−n ottenuti applicando la costruzione precedente a ciascuno dei 2n−1 intervalli diE

(n−1)1/3 . L’insieme E1/3 e un sottoinsieme compatto, non numerabile di R con interno

vuoto.

Si puo dimostrare che 2N e in biezione con E1/3 e che ran(Φ) e proprio E1/3.

Proposizione 29. Φ : 2N → E1/3 e omeomorfismo.

Poiche |ω×ω| = ω, 2N e omeomorfo a 2N×N ∼ (2N)N e a (2N)k, per ogni k > 0. Peril teorema di Schroder-Bernstein 2N×N, (2N)N e (2N)k sono in biezione con R. Quindiper il teorema di Schroder-Bernstein e quanto detto in precedenza R,Rk,RN sono inbiezione.

Osservazione 50. Il cubo [0, 1]k e il cubo di Hilbert [0, 1]N sono equipotenti,cioe inbiezione con R.

Esempio 4.4.1. Si consideri l’insieme delle funzioni continue C(R,R) = f : R →R|f continua .C(R,R) RQ.f 7→ f Q e iniettiva, e poiche RQ ∼ (2N)N ∼ R,allora C(R,R) R. Ovviamente R C(R,R) quindi C(R,R) e R sono in biezione.

Capitolo 5

Algebre di Boole

Definizione 5.0.2. Un reticolo 〈L,≤〉 e un insieme ordinato dove ogni coppia dielementi x e y ammette un estremo superiore ed inferiore. Indicati con:

sup x, y con x t y o x ∨ yinf x, y con x t y o x ∧ y.

Un reticolo 〈L,≤〉 si dice:1)distributivo se:

x t (y u z) = (x t y) u (x t z),

x u (y t z) = (x u y) t (x u z),

per ogni x, y, z ∈ L.2)complementato se esistono il massimo > = >L e il minimo ⊥=⊥L e se per ogni xc’e un y, detto complemento di x, tale che:

x u y =⊥ x t y = >

3)completo se supX e inf X esistono per ogni X ⊆ L.

Si verifica facilmente che t e u sono commutative ed associative.

Lemma 5.0.1. In un reticolo distributivo 〈L,≤〉 il complemento di un elemento x eunico e si denota con x∗.

Dimostrazione. Suppongo che y e z siano complementi di x allora:y = > u y = (x t z) u y = (x u y) t (z u y) =⊥ t(y u z) = y u z

da cui y ≤ z. Analogamente scambiando y con z, otteniamo che z ≤ y.

Quindi se 〈B,≤〉 e un reticolo complementato e distributivo:1)x t y = y t x x u y = y u x.

61

2)x t (y t z) = (x t y) t z x u (y u z) = (x u y) u z.3)(x t y) u y = y (x u y) t y = y.4)(x t y) u z = (x u z) t (y u z) (x u y) t z = (x t z) u (y t z).5)x t x∗ = > x u x∗ =⊥.

per ogni x, y, z ∈ B. Quindi:

〈B,≤〉 → 〈B,t,u,∗ ,⊥,>〉

e una corrispondenza tra reticoli distributivi complementati e strutture algebrichedotate di due elementi privilegiati ⊥,>, operazioni binarie u e t ed un’operazioneunaria ∗ che soddisfano le 1)-5). Viceversa, se B e una struttura come sopra, possia-mo definire un ordine ≤ su B:

x ≤ y ⇔ x u y = x.

Allora 〈B,≤〉 e un reticolo distributivo complementato tale che ∈ x, y = x u ye sup x, y = xt y,minB =⊥ e max(B) = >. Inoltre la corrispondenza che trasfor-ma strutture algebriche che soddisfano 1)-5) in reticoli distributivi complementati el’inversa della mappa 〈B,≤〉 → 〈B,t,u,∗ ,⊥,>〉.

Definizione 5.0.3. Un’algebra di Boole e un reticolo 〈B,≤〉 complementato e di-stributivo con almeno due elementi o, equivalentemente, e una struttura algebrica〈B,u,t,∗ ,⊥,>〉, dove >,⊥ sono distinti, u,t sono operazioni binarie su B e ∗ euna operazione unaria su B che soddisfano 1)-5).

Esempio 5.0.2. L’esempio piu importante di algebra di Boole e 〈℘(X),⊆〉 con X 6=∅, ovvero la struttura algebrica

〈℘(X),∩,∪,′ , ∅, X〉

dove Y ′ = X \ Y e il complementare di Y in X.

Un’algebra di Boole si dice completa se e completa come reticolo.

Definizione 5.0.4. Un omomorfismo di algebre di Boole f : 〈B,≤〉 → 〈C,〉 e unafunzione f : B → C tale che f(⊥B) =⊥C, f(>B) = >C e per ogni b1, b2 ∈ B

f(b1 u b2) = f(b1) ∧ f(b2) e f(b1 t b2) = f(b1) ∨ f(b2).

dove ∧ e ∨ sono gli operatori di inf e sup di C. Se f : B → C e una biezione,allora anche f−1 e un omomorfismo. Due algebre di Boole si dicono isomorfe se c’eun isomorfismo tra esse.

Definizione 5.0.5. Una sub-algebra di B e un C ⊆ B non vuoto e chiuso per t, ue ∗, equivalentemente, se la funzione identica C → B e un omomorfismo di algebre.

5.1 Anelli Booleani

Definiamo la somma in un’algebra di Boole:

x+ y = (x u y∗) t (y u x∗).

Osservo che se f : B → C e un omomorfismo di algebre di Boole, allora f(x+y) =f(x) + f(y). Definiamo il prodotto in un’algebra di Boole:

x · y = x u y.

Quindi ad ogni algebra di Boole possiamo associare un anello:

〈B,t,u,∗ ,⊥,>〉 7→ 〈B,+, ·,⊥,>〉.

In un anello siffatto vale x2 = x, per ogni x, e un anello che gode di questaproprieta si dice anello Booleano. Ogni anello Booleano e l’anello costruito a partireda una qualche algebra di Boole e ogni omomorfismo f : B → C di algebre di Boolee un omomorfismo di anelli con unita. In altre parole la corrispondenza:

〈B,t,u,∗ ,⊥,>〉 7→ 〈B,+, ·,⊥,>〉

e un funtore covariante dalla categoria delle algebre di Boole nella categoria deglianelli Booleani ed e un isomorfismo di categorie. Il nucleo di un morfismo di algebredi Boole f : B → C e:

ker(f) = b ∈ B|f(b) =⊥C.

Quindi f e iniettivo se e solo se il suo nucleo e ⊥B.

Definizione 5.1.1. Un atomo di un’algebra di Boole B e un elemento minimale diB \ ⊥ cioe un a ∈ B \ ⊥ per cui non esistono ⊥< b < a. L’insieme degli atomidi B si indica con At(B). Un’algebra si dice atomica se per ogni b ∈ B \ ⊥ c’e unatomo a ≤ b.

Esempio 5.1.1. 〈℘(X),⊆〉 e un’algebra di Boole (se X 6= ∅) ed e atomica e completa.Le operazioni di reticolo sono ∪,∩, il complemento di A e X \A. Una sub-algebra di℘(X) e un ∅ 6= F ⊆ ℘(X) chiuso per unioni, intersezioni e complementi. La somma+ in ℘(X) e la differenza simmetrica 4.

Capitolo 6

Forme deboli dell’assioma dellascelta

6.1 Assioma delle scelte numerabili

Per ogni X insieme vale l’assioma delle scelte numerabili se per ogni successione〈An|n ∈ ω〉 di sottoinsiemi non vuoti di X, esiste una f tale che f(n) ∈ An per ognin ∈ ω. Cioe:

∀A ∈ (℘(X) \ ∅)ω∃f ∈ Xω∀n ∈ ω(f(n) ∈ An).

Se X e bene ordinabile allora ACω(X), l’assioma delle scelte numerabili e veroin quanto possiamo scegliere l’elemento minimo di An. Ma se X non e numerabileallora non e dimostrabile in MK o ZF .

Teorema 6.1.1. ACω implica che l’unione numerabile di insiemi numerabili e nu-merabile.

Dimostrazione. Siano Xn insiemi tali che |Xn| ≤ ω e dimostriamo che |⋃nXn| ≤

ω.Sia N :⋃nXn → ω:

N(x) = min n ∈ ω|x ∈ Xn.

Per ACω possiamo scegliere delle funzioni iniettive fn : Xn ω e quindi definirel’iniezione:

F :⋃nXn ω × ω, F (x) = (N(x), fN(x)(x)).

Un’altra forma dell’Assioma della scelta e quello delle Scelte Dipendenti(DC(X)).Per ogni insieme X 6= ∅, se R e una relazione su X tale che ∀x∃y(xRy), allora perogni x0 ∈ X c’e una f ∈ω X tale che f(0) = x0 e ∀n(f(n)Rf(n + 1)). Come perl’assioma delle scelte numerabili ho che, DC(X) e dimostrabile quando X e beneordinabile, ma non in generale.

64

6.2 La misura di Lebesgue

Una famiglia di insiemi S ⊆ ℘(X) e una σ-algebra se e una sub-algebra di Boole di℘(X) e se e numerabilmente completa, cioe per ogni A ⊆ S numerabile,

⋃A ∈ S.

Per ogni A ⊆ ℘(X) possiamo quindi definire la σ-algebra generata da A come la piupiccola σ-algebra contenente A,⋂S ⊆ ℘(X)|S e una σ-algebra e A ⊆ S.

Se assumiamo ACω(R), e possibile dare una descrizione alternativa di questa σ-algebra:

S0 = A∪^

A ∪∅, XSα+1 =

⋃n∈ω An|An ∈ Sα∪

^

Sα

Sλ =⋃α<λ Sα λ limite

dove^

B= X \B|B ∈ B, per ogni B ⊆ ℘(X). Si verifica per induzione che:

1)β < α⇒ Sβ∪^

Sβ⊆ Sα.2)Sα e contenuto nella σ-algebra generata da A.

Se X e uno spazio topologico con topologia T ,la σ-algebra dei Boreliani

Bor(X, T )

e la piu piccola σ-algebra su X contenente T . Quando T e chiara dal contestoscriveremo semplicemente Bor(X). Uno spazio di misura e una tripla 〈X,S, µ〉 taleche:1)S e una σ-algebra su X.2)µ : S → [0,+∞] soddisfa:a)µ(∅) = 0,b)se An ∈ S sono a due a due disgiunti, allora

µ

(⋃n

An

)=∞∑n=0

µ(An).

La serie sopra e a termini positivi,quindi la sua somma e ben definita. Gli insiemiin S si dicono S-misurabili, o misurabili secondo S,mentre la funzione µ si dicemisura. La proprieta sopra e detta di σ-additivita. Osserviamo che la nozione dispazio di misura e ridondante,dato che dalla misura µ possiamo ricavare la σ-algebraS = dom(µ) e da questa si ricava l’insieme X =

⋃S. Tuttavia spesso non si distingue

tra una misura µ ed una sua restrizione ad una sotto-σ-algebra, per cui la nozione dispazio di misura risulta molto comoda.Uno spazio di misura 〈X,S, µ〉 si dice:Spazio di misura completo se ∀A ∈ S∀B ⊆ A(µ(A) = 0⇒ B ∈ S ∧ µ(B) = 0).Spazio di probabilita se µ(X) = 1.

Spazio di misura finito se µ(X) <∞.Spazio di misura σ-finito se esistono Xn ∈ S tali che X =

⋃nXn e µ(Xn) <∞.

Capitolo 7

Teorema di completezza

7.1 Problema della riduzione

Dato un sistema formale F ci si chiede quali sono le condizioni necessarie e sufficientiaffinche una formula sia teorema di F .

Definizione 7.1.1. L′ e estensione di un linguaggio L se ogni simbolo di L e simbolodi L′.

Definizione 7.1.2. T ′ e estensione di T se e solo se L(T ′) e estensione di L(T ) eogni teorema di T e un teorema di T ′ (ovvero ogni assioma non logico di T e teoremadi T ′).

Definizione 7.1.3. Una estensione conservativa di T e una estensione T ′ tale cheper ogni formula A di L(T ) derivabile in T ′ era gia derivabile in T .

Esempio 7.1.1. Ad esempio quando T ′ e ottenuto da T aggiungendo delle costanti,ma non assiomi non logici, ho che T ′ e estensione conservativa.

Due teorie T e T ′ sono equivalenti se ciascuna e estensione dell’altra,cioe hannostesso linguaggio e stessi teoremi.Se T ′ e estensione conservativa di T ,allora ogniteoria equivalente a T ′ e estensione (conservativa) di ogni teoria equivalente a T .Nonaggiunge potere dimostrativo alle vecchie formule.

Teorema 7.1.1 (di Riduzione). Sia Γ un insieme di formule nel linguaggio L(T ) esia A una formula di L(T ). Allora T ∪ Γ ` A se e solo se esistono B1, · · · , Bn ∈ Γtali che T ` B1 ⇒ · · · ⇒ Bn ⇒ A(con Bi la chiusura universale di Bi).

Dimostrazione. Se T ` B1 ⇒ · · · ⇒ Bn ⇒ A allora T ∪ Γ ` B1 ⇒ · · · ⇒ Bn ⇒ A,ma B1, · · · , Bn sono teoremi di T ∪ Γ dunque per modus pones T ∪ Γ ` A.Viceversasupponiamo che T ∪Γ ` A allora esistono B1, · · · , Bn ∈ Γ tali che T ∪B1, · · · , Bn `A e per il teorema di deduzione T ` B1 ⇒ · · · ⇒ Bn ⇒ A.

Definizione 7.1.4. Una teoria e incoerente se dimostra ogni formula.

67

Definizione 7.1.5. Una teoria e coerente se non e incoerente.

Osservazione 51. Se T dimostra A e dimostra ¬A allora per il teorema dellatautologia dimostra qualunque formula quindi T e incoerente.Vale anche il viceversa.

Osservazione 52. Se T ′ e estensione di T ,allora se T ′ e coerente anche T e coerente.

Osservazione 53. Se T ′ e estensione conservativa di T allora T ′ e coerente se e solose T e coerente.

Teorema 7.1.2 (di riduzione per coerenza). Sia T una teoria e Γ 6= ∅ un insiemedi formule di L(T ).T ∪ Γ e incoerente se e solo se esistono A1, · · · , An ∈ Γ tali cheT ` ¬A1 ∨ · · · ∨ ¬An.

Dimostrazione. Se ho A1, · · · , An come nell’enunciato ho che T ∪ Γ ` Ai per gene-ralizzazione, dunque T ∪ Γ e incoerente per il teorema della tautologia. Viceversa,supponiamo T ∪ Γ sia incoerente, allora T ∪ Γ ` B ∧ ¬B, con B formula fissata.Dunque per il teorema di deduzione T ` A1 ⇒ · · · ⇒ An ⇒ B ∧ ¬B e quindi peril teorema della tautologia T ` ¬A1 ∨ · · · ∨ ¬An ∨ (¬B ∨ B), per il teorema dellatautologia T ` ¬A1 ∨ · · · ∨ ¬An.

Corollario 7.1.3. Sia A la chiusura universale di A.T ` A se e solo se T ∪ ¬A eincoerente.

Dimostrazione. T ∪ ¬A e incoerente se e solo se T ` A (per il teorema dellatautologia) se e solo se T ` A (per il teorema della chiusura).

Osservazione 54. E’ importante che A sia chiusa. Per esempio, se T e la teoriadei numeri (introdotta nel capitoli precedenti), T ∪ x = 0 e incoerente ma, questonon significa che T ` x 6= 0. Non mi autorizza a dire che dimostra la negazione.

7.2 Teorema di completezza

Esistono due versioni del teorema di completezza,una forma debole e una forte dovutea K.Godel nel 1930.

Teorema 7.2.1 (Completezza forma debole). A e un teorema di T se e solo se A evalida in T . In simboli

T ` A se e solo se T |= A.

Osservazione 55. Per il teorema di validita dimostro solamente che se T |= A alloraT ` A.(dalla semantica passo alla sintassi).

Teorema 7.2.2 (Completezza forte). T e coerente se e solo se T ha un modello.

Osservazione 56. Se T ha un modello A, dato che A 6|= A ∧ ¬A, per qualsiasi A,allora per il teorema di validita T e coerente. E’ sufficiente dimostrare che se T ecoerente,allora T ha un modello.

Lemma 7.2.3. Il teorema di completezza forte implica il teorema di completezzadebole.

Dimostrazione. Suppongo T |= A e cerco di dimostrare che T ` A. Per assurdoT 6` A allora T ∪ ¬A e coerente e ha un modello A |= T ∪ ¬A. Ma inoltre hoche A |= A: assurdo.

7.3 Dimostrazione del teorema di completezza

Quindi e sufficiente dimostrare che

Teorema 7.3.1. Se T e coerente, allora T ha un modello.

La dimostrazione si articola in molti passi.

Definizione 7.3.1. Se A′ e una L′-struttura dove L′ e una estensione di L, alloraomettendo le interpretazioni dei simboli non di L si ottiene una L-struttura A′ L.Se A = A′ L diremo che A e la riduzione (o restrizione) di A′ ad L e che A′ eun’espansione di A ad L′.

Osservazione 57. |A| = |A′| e useremo lo stesso nome in L (A) = L (A′) per unelemento del dominio.

Lemma 7.3.2. Se A e un enunciato del linguaggio L (A), allora A(A) = A′(A).

Lemma 7.3.3. Se T ′ e una estensione di T e A′ e un modello di T ′ allora A′ L(T )e un modello di T .

Sia T una teoria con almeno una costante. La struttura canonica per T e lastruttura A che ha per dominio:

|A| = ClTerm

≈, (7.3.1)

dove ClTerm e l’insieme dei termini chiusi e ≈ e la relazione: a ≈ b se e solo seT ` a = b. La ≈ e una relazione di equivalenza.Infatti a ≈ a per assioma di identita.Poi a ≈ b⇒ b ≈ a per il teorema di simmetria. Ed infine a ≈ b ∧ b ≈ c⇒ a ≈ c pergli assiomi di uguaglianza. La classe di equivalenza b|b ≈ a e indicata come a

. Se

f e P sono simboli di funzione e predicato di L(T ) definiamo

fA(a

1, · · · , a

n

)= (fa1 · · · an)

(a

1, · · · , a

n

)∈ PA

se e solo seT ` Pa1 · · · an.

Verifichiamo che le definizioni non dipendono dal rappresentante. Suppongo che∀i = 1, · · · , n si ha a

i = b

i , allora ∀i, T ` ai = bi, per il teorema di uguaglianza (il

suo corollario) ho che T ` fa1 · · · an = fb1 · · · bn e T ` Pa1 · · · an ⇔ Pb1 · · · bn cioe

(fa1 · · · an)

= (fb1 · · · bn)

e T ` Pa1 · · · an se e solo se T ` Pb1 · · · bn.

Lemma 7.3.4. Se a e un termine chiuso, allora A(a) = a.

Dimostrazione. a = fa1 · · · an, con a1, · · · , an ∈ ClTerm. Per ipotesi induttivaA(a) = A (fa1 · · · an) = fA (A(a1), · · · ,A(an)) = fA

(a1, · · · , a

n

)= (fa1 · · · an)

=

a.

Lemma 7.3.5. Se A e un enunciato atomico allora A |= A se e solo se T ` A.

Dimostrazione. Se A e a = b allora A |= A se e solo se A(a) = A(b) se e solo sea

= b

se e solo se a ≈ b se e solo se T ` a = b. Altrimenti A e Pa1 · · · an conP diverso da =. Allora A |= A se e solo se (A(a1), · · · ,A(an)) ∈ PA se e solo se(a1, · · · , a

n

)∈ PA se e solo se T ` Pa1 · · · an se e solo se T ` A.

Abbiamo dimostrato che la struttura canonica A per T , soddisfa una formulaatomica A se e solo se la formula e un teorema di T . Non si generalizza il fatto aformule complesse per due motivi:1)Se A |= ¬B allora A 6|= B e quindi, per ipotesi induttiva T 6` B, ma questo nonvuol dire che T ` ¬B.2)Puo succedere che T ` ∃xA e tuttavia non c’e nessun termine chiuso a tale cheT ` Ax[a].

Definizione 7.3.2. T e una teoria di Henkin se e solo se per ogni enunciato dellaforma ∃xA c’e una costante e tale che T ` ∃xA⇒ Ax[e].

Definizione 7.3.3. T e una teoria completa se e solo se e coerente e T ` A oppureT ` ¬A per ogni enunciato A.

Lemma 7.3.6. Sia T una teoria di Henkin completa e A una sua struttura canonicaallora, A |= A se e solo se T ` A per ogni enunciato A.

Dimostrazione. La dimostrazione si effettua per induzione sulla complessita di A. SeA e atomica il risultato e gia dimostrato. Se A e ¬B allora A |= A se e solo se A 6|= Bse e solo se T 6` B (per ipotesi induttiva) se e solo se T ` ¬B (per completezza) se esolo se T ` A. Suppongo che A sia B ∨ C. Se A |= A allora A |= B oppure A |= Ccioe T ` B oppure T ` C cioe T ` A.Viceversa se A 6|= A allora A 6|= B eA 6|= Ccioe T 6` B e T 6` C quindi T 6` A. Suppongo A e ∃xB. Allora A |= A se e solo seA |= ∃xB se e solo se A |= Bx[c], per qualche nome canonico c di qualche a

∈ |A|.Poiche a

= A(a) = A(c) si ha A |= Bx[a] e per ipotesi induttiva T ` Bx[a]. Dato che

Bx[a]⇒ ∃xB e assioma di sostituzione, ottengo T ` A per modus pones. Viceversa,se T ` A allora poiche T e una teoria di Henkin T ` ∃xB ⇒ Bx[e] per qualchecostante e,quindi T ` Bx[e] per modus pones. Per ipotesi induttiva A |= Bx[e] da cuiA |= A.

Corollario 7.3.7. Se T e una teoria di Henkin completa, allora la sua strutturacanonica e un modello di T .

Definizione 7.3.4. LH e il linguaggio ottenuto da L aggiungendo nuove costanti c∃xAuna per ogni enunciato della forma ∃xA di L.

Definizione 7.3.5. Lc e il linguaggio ottenuto da L iterando l’operazione L 7→ LH :L0 e L,Ln+1 e (Ln)H e Lc e unione degli Ln.

Osservazione 58. Le costanti aggiunte a L per ottenere Lc si chiamano costantispeciali. Quelle di ordine n sono quelle che aggiungiamo ad Ln per ottenere Ln+1.

Definizione 7.3.6. L’enunciato ∃xA⇒ Ax [c∃xA] e detto assioma speciale per c∃xA.

Definizione 7.3.7. TH e l’estensione di T con linguaggio LH e con tutti gli assiomispeciali per le costanti speciali di ordine 0.

Definizione 7.3.8. Tc e estensione di T con linguaggio Lc e con tutti gli assiomispeciali per le costanti speciali di ogni ordine, cioe Tc e l’unione delle Tn dove T0 e Te Tn+1 e (Tn)H .

Osservazione 59. Tc e una teoria di Henkin.

Lemma 7.3.8. Tc e estensione conservativa di T .

Dimostrazione. Basta dimostrare che TH e estensione conservativa di T . Infatti seTc ` A e A e una formula di L(T ), allora Tn ` A per qualche n,quindi segue applicandon volte questo fatto. Supponiamo che TH ` A e A e una formula di L(T ). AlloraT ′ ` B1 ⇒ · · · ⇒ Bk ⇒ A, dove i Bi sono assiomi speciali per le nuove costantie T ′ e l’estensione ottenuta da T aggiungendo le nuove costanti di LH ma nessunassioma non logico. Per il teorema sulle costanti, T ′ e estensione conservativa diT .Per induzione su k verifico che T ` A. Se k = 0 allora T ′ ` A e T ` A, quindi possosupporre k > 0. Sia B1 l’enunciato ∃xC ⇒ Cx [c∃xC ] e sia y una variabile che nonoccorre nella dimostrazione di T ′ ` B1 ⇒ · · · ⇒ Bk ⇒ A. Per la dimostrazione delteorema sulle costanti, T ′ ` (∃xC ⇒ Cx[y]) RightarrowB2 Rightarrow · · · ⇒ Bk ⇒A, per la regola di ∃-introduzione T ′ ` ∃y (∃xC ⇒ Cx[y]) ⇒ B2 ⇒ · · · ⇒ Bk ⇒ A.Per il teorema della variante T ′ ` (∃xC ⇒ ∃yCx[y]), quindi T ′ ` ∃y (∃xC ⇒ Cx[y])per operazioni prenesse, da cui T ′ ` B2 ⇒ · · · ⇒ Bk ⇒ A per modus pones. Ilrisultato segue per ipotesi induttiva.

Definizione 7.3.9. Sia E un insieme. Diremo che J ⊆ ℘(E) ha carattere finito see solo se

A ∈ J ⇔ ∀B(B ⊆ A ∧B finito ⇒ B ∈ J),

∀A ⊆ E.

Lemma 7.3.9 (di Teichmuller-Tukey). Se ∅ 6= J ⊆ ℘(E) ha carattere finito, alloraJ contiene un elemento massimale.

Definizione 7.3.10. Una estensione T ′ di T e semplice se L(T ) = L(T ′).

Teorema 7.3.10 (di Lindenbaum). Se T e coerente, allora ha un’estensione semplicecompleta.

Dimostrazione. Sia Fml l’insieme delle formule di L(T ). La famiglia J = Σ ⊆Fml|T ∪ Σ e coerente ha carattere finito:se Σ ⊆ Fml e Σ 6∈ J allora T ∪ Σ eincoerente,quindi ci sono A1, · · · , An ∈ Σ tali che T ∪ A1, · · · , An e incoerente,quindi A1, · · · , An 6∈ J .∅ ∈ J per il lemma precedente c’e Σ ∈ J massimale. T ∪ Σe coerente ed e estensione semplice di T quindi basta mostrare che T ∪Σ e completa.Sia A un enunciato di L(T ) tale che T ∪ Σ 6` A. Allora T ∪ Σ ∪ ¬A e coerente,quindi Σ ∪ ¬A ∈ J e ¬A ∈ Σ per la massimalita di Σ da cui T ∪ Σ ` ¬A.

Lemma 7.3.11. Sia T una teoria coerente ed U una estensione semplice e coerentedi Tc. Allora U ha un modello A in cui ogni elemento e della forma A(c) per infinitecostanti speciali c.

Dimostrazione. Per il teorema di Lindembaum c’e estensione semplice e completa U ′

di U . Poiche U ′ e di Henkin, la sua struttura canonica A e un modello di U ′ e quindidi U per il lemma 7.3.3, la riduco. Sappiamo che ogni elemento di A e della formaA(a) per qualche termine chiuso a. Allora:

A(a) = A(c∃x(x=a)

)e dato che di variabili c’e ne sono infinite,ho il risultato.

Corollario 7.3.12. Siano T e T ′ teorie nello stesso linguaggio.1)T ′ e estensione di T se e solo se ogni modello di T ′ e un modello di T .2)T e T ′ sono equivalenti se e solo se hanno gli stessi modelli.

Dimostrazione. Se ogni modello di T ′ e un modello di T , allora ogni formula validain T e valida in T ′, quindi ogni teorema di T e teorema di T ′.

Osservazione 60. Il teorema di completezza ci da un metodo per stabilire se unateoria e coerente o no.

Capitolo 8

Teoria dei modelli

8.1 Teorema della compattezza

Definizione 8.1.1. Una sottoteoria T ′ di T e una teoria del medesimo linguaggio incui tutti gli assiomi non logici di T ′ sono assiomi non logici di T .

Teorema 8.1.1 (di compattezza). ϕ e valida in T se e solo se ϕ e valida in qualchesottoteoria finitamente assiomatizzata T0 in T .

Dimostrazione. T ` ϕ se e solo se T0 ` ϕ per qualche sottoteoria finitamente assio-matizzata T0 di T e per il teorema di completezza ϕ e valida in una teoria se e solose e derivabile dalla teoria.

Corollario 8.1.2. T e soddisfacibile se e solo se ogni sottoteoria finitamente assio-matizzata T0 in T e soddisfacibile.

La teoria F dei campi e formulata nel linguaggio Lfields = 0, 1,−1,+, · e ha perassiomi:((x+ y) + z) = (x+ (y + z))x+ 0 = xx+ (−x) = 0(x+ y) = (y + x)((x · y) · z) = (x · (y · z))1 · x = xz · (x+ y) = (z · x) + (z · y)(x · y) = (y · x)0 6= 1x 6= 0⇒ ∃y(x · y = 1)

I modelli di F sono i campi.Si scrivera xn per indicare x · · ·x eseguito n-volte.Siaσn l’enunciato 1 + · · · + 1 = 0 con la somma eseguita n-volte. Fp = F ∪ σpe la teoria dei campi di caratteristica p. La teoria dei campi di caratteristica 0 e

73

F0 = F ∪ ¬σn|n ≥ 2 ho infiniti assiomi, e una classe pseudo-elementare, non riescoa trovare una quantita finita di assiomi che me lo rappresenti. Sia τn l’enunciato:

∀a0 · · · ∀an∃x(an 6= 0⇒ anxn + · · ·+ a1x+ a0 = 0).

La teoria dei campi algebricamente chiusi:

ACF = F ∪ τn|n ≥ 1e

ACFp = Fp ∪ τn|n ≥ 1e la teoria dei campi di caratteristica p (p primo o p = 0).

Esempio 8.1.1.R |= F0,

ZpZ|= Fp,

C |= ACF0.

Teorema 8.1.3 (principio di Lefschetz). Per ogni enunciato ϕ nel linguaggio dellateoria dei campi Lfields c’e un m ≥ 2 tale che se ϕ vale in ogni campo di caratteristica0 allora vale in ogni campo di caratteristica p > m.

Dimostrazione. Supponiamo che F0 |= ϕ. Allora per compattezza c’e un m taleche F ∪ ¬σn|2 ≤ n ≤ m |= ϕ. I campi di caratteristica p > m sono modelli diF ∪ ¬σn|2 ≤ n ≤ m e quindi soddisfano ϕ.

Corollario 8.1.4. F0 non e finitamente assiomatizzabile.

Dimostrazione. Se ϕ1, · · · , ϕn sono un sistema di assiomi per F0, allora sarebbe-ro dimostrabili in F ∪ ¬σn|2 ≤ n ≤ m per qualche m. Quindi ogni campo dicaratteristica > m soddisferebbe F0.

ε≥n e l’enunciato ∃x1 · · · ∃xn∧

1≤i<j≤n xi 6= xj. Abbiamo ε≥n|n ≥ 1 la teoriadegli insiemi infiniti, F ∪ ε≥n|n ≥ 1 la teoria dei campi infiniti, G ∪ ε≥n|n ≥ 1la teoria dei gruppi infiniti, con G teoria dei gruppi.In particolare queste teorie nonsono finitamente assiomatizzabili.Sia Str(L) la classe delle L-strutture.C ⊆ Str(L) e una classe elementare EC se esolo se

C = Mod(σ) = A|A |= σper qualche enunciato σ.C ⊆ Str(L) e una classe pseudo-elementare EC∆ se e solo se

C = Mod(T ) = A|A |= Tper qualche teoria T .Chiaramente se C e EC allora e EC∆.

Definizione 8.1.2. C = Str(L) \ C e la classe duale di C.

Teorema 8.1.5. C e EC se e solo se C e C sono EC∆.

Dimostrazione. Se C e EC allora C = Mod(σ) e quindi C = Mod(¬σ) e EC.C eEC, implica che e EC∆ e anche C e EC, implica che e EC∆. Viceversa, suppongoC e C sono EC∆ cioe C = Mod(T ) e C = Mod(S). Allora T ∪ S e insoddisfacibilequindi per il teorema di compattezza ci sono T0 ⊆ T e S0 ⊆ S finiti tali che T0 ∪ S0

e insoddisfacibile. Prendendo∧T0 e

∧S0 posso trovare σ e τ tali che T ` τ , S ` σ

e τ, σ insoddisfacibile. Per ogni A ∈ Str(L) si ha che A ∈ C oppure A ∈ C: seA ∈ C allora A |= T quindi A |= τ e se A ∈ C allora A |= S quindi A |= sigma.Quindi C = Mod(τ) e C = Mod(σ) sono EC.

Corollario 8.1.6. La classe dei gruppi finiti, insiemi finiti, campi finiti non e assio-matizzabile in un linguaggio del primo ordine.

Osservazione 61. Affermare che C e EC equivale a dire che e finitamente assioma-tizzabile.

8.2 Teorema di Skolem

Definizione 8.2.1. Un isomorfismo F : A → B tra due L-strutture e una biezioneF : |A| → |B| tale che:

1) F (cA) = cB per ogni simbolo di costante c.

2) F (PA) = PB per ogni simbolo di predicato P .

3) F (fA(a1 · · · an)) = fB(F (a1) · · ·F (an)) per ogni simbolo di funzione f .

La seguente notazione:

A ∼= B,

indica che le due strutture sono isomorfe.

Definizione 8.2.2. Si definisce la teoria di A: Th(A) = σ|A |= σ.

Due L-strutture A e B sono elementarmente equivalenti A ≡ B se e solo seTh(A) = Th(B).

Osservazione 62. Mod(Th(A)) = B|B ≡ A. Inoltre due strutture isomorfe im-plica che siano elementarmente equivalenti ma due strutture elementarmente equi-valenti non implica l’isomorfismo. Ci sono strutture elementarmente equivalenti manon isomorfe.

Lemma 8.2.1. Se T e coerente,sono equivalenti:1)T e completa.2)∀A,B ∈Mod(T )(A ≡ B).3)T e equivalente a Th(A),∀A ∈Mod(T ).

Dimostrazione. 1)⇒2).Se ∀A,B ∈ Mod(T ) e σ e enunciato, allora T ` σ oppureT ` ¬σ, quindi σ vale in A e B oppure ¬σ vale in A e B.2)⇒3). Fissiamo un modello A di T . Chiaramente Th(A) estende T e ogni modellodi T e elementarmente equivalente ad A e quindi e un modello di Th(A). Cioe Testende Th(A).3)⇒1). Th(A) e completa, quindi lo e anche T .

Lemma 8.2.2. Se L e un linguaggio con al piu κ simboli,allora Lc ha al piu κ simboli.

Dimostrazione. Per induzione su n si dimostra che l’insieme delle costanti speciali dilivello n sono ≤ κ da cui si deduce che Lc ha cardinalita ≤ ω · κ = κ.

Teorema 8.2.3 (di Skolem all’insu). Se T e una teoria in un linguaggio di cardinalitaκ che ha un modello infinito, allora ha un modello di cardinalita λ, per ogni λ ≥ κ.

Dimostrazione. Sia A un modello infinito di T . Estendo T aggiungendo nuove co-stanti cα|α < λ e nuovi assiomi cα 6= cβ|α < β < λ. La teoria U cosı ottenutaha cardinalita λ ed e soddisfacibile, in quanto per ogni α1 < · · · < αn < λ, la teoriaT ∪ cαi 6= cαj |1 ≤ i < j ≤ n ha un modello: basta prendere A e interpretarecα1 , · · · , cαn in elementi distinti. M la struttura canonica data dal teorema di com-pletezza per U , ha cardinalita ≤ della cardinalita di Uc, cioe λ. Gli elementi cMα sonodistinti e M ha taglia λ. Sia B la restrizione di M a linguaggio di T : allora B hataglia λ ed e un modello di T .

Corollario 8.2.4. Se T e una teoria numerabile e coerente, allora ha un modello dicardinalita ≤ ℵ0.

PARADOSSO DI SKOLEMSe MK e coerente, allora ha un modello numerabile.

Definizione 8.2.3. Una teoria T e categorica se ha un unico modello a meno diisomorfismi.Una teoria T e κ-categorica se due modelli di cardinalita κ sono sempreisomorfi.

Osservazione 63. Per il teorema di Skolem all’insu,T e categorica se e solo se hasoltanto modelli finiti (e tutti della stessa taglia). La teoria che non ha assiomi eκ-categorica per ogni cardinale κ.

Sia F la chiusura algebrica di F . Utilizzando l’assioma della scelta e possibiledimostrare che la chiusura algebrica e unica,a meno di isomorfismi. Sia:

Fp =

ZpZ p primo

Q se p = 0

Se B0, B1 sono algebricamente indipendenti su Fp,ogni biezione f : B0 → B1

puo essere estesa ad un isomorfismo di F0 su F1, dove Fi e il piu piccolo campoalgebricamente chiuso F di caratteristica p ed e completamente caratterizzato dauna sua base di trascendenza B su Fp e |F | = max (|Fp|, |B<ω|), quindi se |F | > ℵ0

allora |F | = |B|.

Esempio 8.2.1. Q[e, π] e Q[π] sono numerabili entrambe ma non isomorfe.

Osservazione 64. ACFp e κ-categorica per ogni κ > ω.Ma non ℵ0 categorica.

Teorema 8.2.5. Se T e coerente, ha solo modelli infiniti, ha cardinalita ≤ κ ed eκ-categorica, allora T e completa.

Dimostrazione. Se T 6` σ e T 6` ¬σ per qualche enunciato σ, allora T0 = T ∪ σ eT1 = T ∪ ¬σ sono soddisfacibili, quindi hanno un modello Mi |= Ti con i = 0, 1.Per ipotesi gli Mi sono infiniti, quindi per Skolem posso supporre di taglia κ. Perκ-categoricita M0

∼=M1 ma M0 |= σ e M1 |= ¬σ: contraddizione.

Corollario 8.2.6. ACFp e completa.

Teorema 8.2.7 (converso del principio di Lefschetz). Sia σ un enunciato del lin-guaggio della teoria dei campi. Supponiamo che esistano primi p0 < p1 < · · · ecampi algebricamente chiusi Fi tali che la caratteristica di Fi e pi e Fi |= σ. AlloraACF0 ` σ. In particolare C ` σ.

Dimostrazione. Per completezza della teoria si ha che ACFpi |= σ per ogni i ∈ ω. Se,per assurdo, ACF0 6` σ allora per completezza ACF0 ` ¬σ, quindi ACFp ` ¬σ pertutti i primi p sufficientemente grandi: contraddizione.

Capitolo 9

Gruppi, Anelli, Sottoanelli eCampi

9.1 Teorema di isomorfismo per i gruppi

Teorema 9.1.1. Sia f : G, · → G′, · un omomorfismo. Esiste un isomorfismo ϕ :G

Ker(f)→ Im(f) tale da rendere commutativo il diagramma:

Gπ→ G

Ker(f)

↓ ϕf Im(f)

Dimostrazione. Pongo K = Ker(f). ∀c ∈ G e ∀k ∈ K si ha che f(kc) = f(k)f(c) =1′ · f(c) = f(c). Definisco una mappa che ad ogni laterale Kc associa f(c). ϕ : G

K→

Im(f) tale che ϕ(Kc) = f(c). Per definizione f = ϕ π. ϕ e omomorfismo infatti∀c, d ∈ G ho ϕ(KcKd) = ϕ(K(cd)) = f(cd) = f(c)f(d) = ϕ(Kc)ϕ(Kd). Inoltre esuriettivo cioe per ogni f(a) in Im(f) trovo Ka in G

Ktale che ϕ(Ka) = f(a). Inoltre

e iniettivo poiche Ker(ϕ) = Ka|ϕ(Ka) = 1′ = Ka|f(a) = 1′ = Ka|a ∈ K =K = 1G

K.

Osservazione 65. Sia f un omomorfismo di gruppi e K = Ker(f) e sottogrupponormale di G. E’ sottogruppo perche K = f−1(1′) che e sottogruppo, inoltre ∀k ∈ Ke ∀x ∈ G considero xkx−1 ho che f(xkx−1) = f(x)f(k)f(x−1) = f(x) · 1′ · f(x−1) =f(x)f(x)−1 = 1′ ⇒ xkx−1 ∈ K.

Esempio 9.1.1. Sia f : Z → Z2 tale che ad n 7→ [n].Il Ker(f) = n ∈ Z|f(n) =[0] = 2Z. Quindi per il teorema di isomorfismo si ha che Z

2Z∼= Z2.

Osservazione 66. Un omomorfismo tra gruppi f : G → G′ e tale per cui f(1) =1′, f(a−1) = f(a)−1 per ogni a in G e f(an) = f(a)n per ogni n in Z e a in G.

Osservazione 67. L’immagine e la controimmagine di sottogruppi va in sottogruppi.

78

9.2 Teorema di isomorfismo per gli anelli

Definizione 9.2.1 (Criterio per i sottoanelli). Sia A un anello e S ⊂ A e unsottoanello se ∀x, y ∈ S si ha x− y ∈ S e x · y ∈ S.

Definizione 9.2.2 (Ideale). Sia A un anello,si ha che I ⊂ A e detto ideale se ∀x, y ∈I si ha x− y ∈ I e ∀x ∈ I,∀a ∈ A si ha x · a ∈ I e a · x ∈ I.

Definizione 9.2.3. Sia A un anello e x ∈ A,(x) e l’ideale principale generato da xed e il piu piccolo ideale contenente x.

Osservazione 68. Se 1A ∈ A allora (x) = ax|a ∈ A.

Teorema 9.2.1. Sia f : A→ A′ un omomorfismo di anelli di nucleo K e immagineIm(f).Esiste un isomorfismo di anelli ϕ : A

K→ Im(f) tale che ϕ p = f .

Dimostrazione. Sappiamo che un omomorfismo di gruppi esiste gia ϕ(K + a) = f(a)verifico che e un omomorfismo (o morfismo ) di anelli:

ϕ((K + a)(K + b)) = ϕ(K + ab) = ϕ(ab) = f(ab) = f(a)f(b) = ϕ(K + a)ϕ(K + b).

Inoltre se A,A′ sono unitari ϕ(1 AK

) = f(1A) = 1A′ .

Osservazione 69. (K + a)(K + b) = K + ab e la definizione di prodotto in AK

.

Esempio 9.2.1. Sia f : R[X]→ R tale che ad a0 + a1x+ · · ·+ anxn 7→ a0.Si ha che

Ker(f) = a0 + a1x+ · · ·+ anxn|f(a0 + a1x+ · · ·+ anx

n) = 0 = = a0 + a1x+ · · ·+anx

n|a0 = 0 = a1x+· · ·+anxn = x(a1+a2x+· · ·+anxn−1)|a1+a2x+· · ·+anxn−1 ∈R[X] = (X).Quindi R ∼= R[X]

(X).

Definizione 9.2.4. Un ideale I di A e detto massimale se non e contenuto propria-mente in nessun ideale proprio di A.

Osservazione 70. Gli ideali impropri sono A e 0.

Definizione 9.2.5. Un ideali e detto primo se ∀a, b ∈ A,ab ∈ I ⇒ a ∈ I ∨ b ∈ I.

Osservazione 71. I massimale ⇒ I primo.

Definizione 9.2.6. Un anello commutativo con unita e un dominio se non ha divisoridello zero.

Definizione 9.2.7. Un corpo e un anello con unita in cui ogni elemento moltiplicativopossiede un inverso (ogni elemento diverso da 0).

Definizione 9.2.8. Un campo e un anello commutativo con unita in cui ogni ele-mento moltiplicativo diverso da 0 possiede un inverso.

Esempio 9.2.2. Un esempio di corpo e quello dei quaternioni.

Osservazione 72. Un campo e un dominio.

Definizione 9.2.9. Si dice caratteristica di un anello A il minimo intero positivotale che na = 0A questo ∀a ∈ A. In caso contrario A ha caratteristica 0.

Teorema 9.2.2. I ideale di A con unita se e solo se AI

e un dominio di integrita.

Teorema 9.2.3. I e massimale se e solo se AI

e un campo.

Un anello A e un PID se e un dominio a ideali principali, ovvero e un dominio ecome anello ha tutti ideali principali.

Definizione 9.2.10. Un anello A e Noetheriano se ogni suo ideale e finitamentegenerato.

Esempio 9.2.3. Z e un PID e ogni suo sottogruppo e del tipo (n) ed e ideale.

Esempio 9.2.4. Z[X] e Noetheriano.

Teorema 9.2.4. Sia A anello commutativo con unita, se A e Noetheriano lo e ancheA[X1, · · · , Xn].

Esempio 9.2.5. Z[X], (X) e ideale primo di Z[X], infatti se ∀p, h ∈ Z[X] tali che

p · h ∈ (X) allora x|p · h ⇒ x|p ∨ x|h ⇒ p ∈ (X) ∨ h ∈ (X) infatti Z[X](X)∼= Z che e

dominio di integrita. Ma non un campo. In R[X] invece l’ideale (X) e massimale in

quanto R[X](X)∼= R e un campo.

9.3 Estensioni di campi

Definizione 9.3.1. Siano E,F dei campi si ha che a ∈ E e algebrico se esiste unpolinomio non nullo a coefficienti in F tale che p(a) = 0.

Definizione 9.3.2. Tra tutti i polinomi che si annullano in a ne esiste uno di gradominimo detto polinomio minimo di a su F .

Osservazione 73. E’ unico a meno di costanti moltiplicative. L’ideale generato daesso e il nucleo della valutazione ϕ : F [X]→ E tale che g 7→ g(a). Infatti:

Ker(ϕ) = g ∈ F [X]|ϕ(g) = 0E = g ∈ F [X]|g(a) = 0 = g = kp|k ∈ F [X] = (p)

inoltre (p) e primo poiche se per ogni t, h ∈ F [X] tale che th ∈ (p) ⇒ p|th ⇒p|t ∨ p|h ⇒ t ∈ (p) ∨ h ∈ (p) ⇒ F [X]

(p)e un dominio. Per il teorema di isomorfismo

F [X](p)∼= Im(ϕ) = F [a].

La valutazione e detta omomorfismo di sostituzione.Se a e trascendente su F allora(pa) = 0 e F [a] ∼= F [X] che e un anello e non un campo. Se a e algebrico (pa) emassimale per una proprieta fondamentale dei PID quindi

F [X]

(pa)∼= F [a].

Se a ∈ E e algebrico su F ,F [a] e un campo e quindi F (a) = F [a] dove in generale

F (X) =fg|f, g ∈ F [X], g 6= 0

.

Definizione 9.3.3. Dati E,F campi,E|F e estensione se esiste un omomorfismoiniettivo di campi (detto immersione) ϕ : F → E in questo caso ϕ(F ) e sottocampodi E isomorfo a F . Spesso risulta agevole pensare di identificare ogni elemento a£di F con la ϕ(a) e vedere quindi F contenuto in E come sottocampo. Risulta quindipossibile vedere E come spazio vettoriale su F . I vettori sono gli elementi di E e gliscalari quelli di F . La dimensione di E come spazio vettoriale su F si chiama grado= [E : F ].

Esempio 9.3.1. Considero C e R e C|R ogni z ∈ C si scrive in modo unico come

z = a+ ib = 1 · a+ i · b

con a, b reali. Quindi 1, i e una base per C e [C : R] = 2.

Esempio 9.3.2. [R : Q] =∞.

Esempio 9.3.3. [E : E] = 1.

Vale la formula tra gradi, se F,L,M sono campi. Allora se F ≤ L ≤M ho che

[M : F ] = [M : L][L : F ].

Sia E|F estensione, se a ∈ E, sia F [a] il minimo sottoanello che contiene F ∪ ae F (a) il minimo sottocampo che contiene F ∪ a allora

F [a] ⊆ F (a)

se a e algebrico inoltre si e visto F [a] = F (a) = F [X](pa)

, ed inoltre ogni elemento di

F [a] si scrive in un modo unico come b0 + b− 1a+ · · ·+ bn−1an−1 dove n = deg(p) e

b0, · · · , b− n− 1 ∈ F .

[F [a] : F ] = n

Definizione 9.3.4. Una estensione E|F , con E,F campi si dice semplice se esisteb ∈ E tale che E = F (b).

Esempio 9.3.4. C = R[i] e semplice.

Definizione 9.3.5. E|F si dice algebrica se ogni elemento di E e algebrico su F .

Se E|F e una estensione di campi, il campo costituito da tutti gli elementi algebricidi E su F si chiama chiusura algebrica di F in E. Caso notevole e quello di C|Q.

Definizione 9.3.6. Un campo di spezzamento e una estensione di F per f su Fcontenente tutte le radici di f polinomio e questa estensione e proprio generata datali radici.

Esempio 9.3.5. Sia ω ∈ C radice dell’unita allora ω = cos 2πkn

+ i sin 2πkn

con 0 ≤k ≤ n − 1 e (k, n) = 1, allora ωt con 0 ≤ t ≤ n − 1 sono le radici di xn − 1 quindiE = Q(ω) = Q(1, ω, ω2, · · · , ωn−1) e campo di spezzamento di xn − 1 in Q. In E[X]ho che

xn − 1 = (x− 1) · · · (x− ωn−1)

se n = p primo per applicazione del criterio di Eisenstein, il polinomio minimodi ω su Q e 1 + x+ · · ·+ xp−1 e quindi

[E : Q] = p− 1.

Bibliografia

[1] Note del Prof. Andretta Alessandro, “ Istituzioni di Logica ”, Dipartimento diMatematica dell’Universita di Torino.

[2] J.R.Shoenfield, “Mathematical Logic”, ASL.

83