Teoria degli insiemi

Teoria degli insiemi

Cos’` e la teoria degli insiemi

La teoria degli insiemi ` e il fondamento della matematica.

Questa affermazione ` e singolare: la teoria degli insiemi ha cominciato a essere svilupata a partire dalla fine del XIX secolo; la matematica esisteva gi` a da qualche millenio.

Il significato ` e:

Tutti i concetti matematici possono essere definiti in termini delle nozioni primitive di insieme e appartenenza da cui tutti i risultati matematici

possono essere dedotti.

Da questa osservazione nasce la teoria degli insiemi.

Cos’` e la teoria degli insiemi

La teoria degli insiemi ` e il fondamento della matematica.

Questa affermazione ` e singolare: la teoria degli insiemi ha cominciato a essere svilupata a partire dalla fine del XIX secolo; la matematica esisteva gi` a da qualche millenio.

Il significato ` e:

Tutti i concetti matematici possono essere definiti in termini delle nozioni primitive di insieme e appartenenza da cui tutti i risultati matematici

possono essere dedotti.

Da questa osservazione nasce la teoria degli insiemi.

Cos’` e la teoria degli insiemi

Si potrebbe quindi anche dare la definizione

matematica = teoria degli insiemi

L’identificaziona appare sensata, ma non si pu` o escludere che in futuro

debba essere soggetta a revisione.

Cos’` e la teoria degli insiemi

Si potrebbe quindi anche dare la definizione

matematica = teoria degli insiemi

L’identificaziona appare sensata, ma non si pu` o escludere che in futuro

debba essere soggetta a revisione.

Quale teoria degli insiemi?

Ci sono varie teorie degli insiemi, non tutte equivalenti fra loro — sebbene con larghe sovrapposizioni: hanno tutte l’ambizione di contenere la matematica ordinaria!

La teoria chiamata usualmente teoria degli insiemi ` e la teoria ZFC:

Zermelo-Fraenkel con assioma della scelta.

Quale teoria degli insiemi?

Ci sono varie teorie degli insiemi, non tutte equivalenti fra loro — sebbene con larghe sovrapposizioni: hanno tutte l’ambizione di contenere la matematica ordinaria!

La teoria chiamata usualmente teoria degli insiemi ` e la teoria ZFC:

Zermelo-Fraenkel con assioma della scelta.

Il linguaggio della teoria degli insiemi

Una teoria matematica ` e espressa attraverso formule in un linguaggio.

Il linguaggio della teoria degli insiemi consiste di

1. Simboli logici:

I

Simbolo di uguaglianza =

I

Connettivi ¬ (negazione), ∨ (disgiunzione), ∧ (congiunzione), ⇒ (implicazione), ⇔ (biimplicazione)

I

Quantificatori ∃ (quantificatore esistenziale), ∀ (quantificatore universale)

I

Variabili v

, v

, v

, . . . 2. Simbolo non logico:

I

Relazione binaria di appartenenza ∈

Il linguaggio della teoria degli insiemi

Una teoria matematica ` e espressa attraverso formule in un linguaggio. Il linguaggio della teoria degli insiemi consiste di

1. Simboli logici:

I

Simbolo di uguaglianza =

I

Connettivi ¬ (negazione), ∨ (disgiunzione), ∧ (congiunzione), ⇒ (implicazione), ⇔ (biimplicazione)

I

Quantificatori ∃ (quantificatore esistenziale), ∀ (quantificatore universale)

I

Variabili v

, v

, v

, . . .

2. Simbolo non logico:

I

Relazione binaria di appartenenza ∈

Il linguaggio della teoria degli insiemi

Una teoria matematica ` e espressa attraverso formule in un linguaggio. Il linguaggio della teoria degli insiemi consiste di

1. Simboli logici:

I

Simbolo di uguaglianza =

I

Connettivi ¬ (negazione), ∨ (disgiunzione), ∧ (congiunzione), ⇒ (implicazione), ⇔ (biimplicazione)

I

Quantificatori ∃ (quantificatore esistenziale), ∀ (quantificatore universale)

I

Variabili v

, v

, v

, . . . 2. Simbolo non logico:

I

Relazione binaria di appartenenza ∈

Il linguaggio della teoria degli insiemi

Dato il linguaggio, si possono definire le formule:

Definizione. Siano x , y delle variabili.

I

x = y , x ∈ y sono formule

I

Se ϕ, ψ sono formule, anche ¬ϕ, ϕ ∨ ψ, ϕ ∧ ψ, ϕ ⇒ ψ, ϕ ⇔ ψ sono formule

I

Se ϕ ` e una formula, anche ∃x ϕ, ∀x ϕ sono formule

Gli assiomi di ZFC (primo blocco)

1. Estensionalit` a: ∀z(z ∈ x ⇔ z ∈ y ) ⇒ x = y

2. Fondazione: ∃x y ∈ x ⇒ ∃y (y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y )) 3. Schema di separazione: Per ogni formula ϕ:

∃y ∀x(x ∈ y ⇔ x ∈ z ∧ ϕ) 4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

5. Unione: ∃A∀Y ∀x (x ∈ Y ∧ Y ∈ F ⇒ x ∈ A) 6. Schema di rimpiazzamento: Per ogni formula ϕ:

∀x ∈ A ∃!y ϕ ⇒ ∃Y ∀x ∈ A ∃y ∈ Y ϕ

Gli assiomi 1–6 permettono di sviluppare le propriet` a elementari della

teoria degli insiemi. Questo facilita anche l’enunciazione degli assiomi

restanti.

Gli assiomi di ZFC (primo blocco)

1. Estensionalit` a: ∀z(z ∈ x ⇔ z ∈ y ) ⇒ x = y

2. Fondazione: ∃x y ∈ x ⇒ ∃y (y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y ))

3. Schema di separazione: Per ogni formula ϕ:

∃y ∀x(x ∈ y ⇔ x ∈ z ∧ ϕ) 4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

5. Unione: ∃A∀Y ∀x (x ∈ Y ∧ Y ∈ F ⇒ x ∈ A) 6. Schema di rimpiazzamento: Per ogni formula ϕ:

∀x ∈ A ∃!y ϕ ⇒ ∃Y ∀x ∈ A ∃y ∈ Y ϕ

Gli assiomi 1–6 permettono di sviluppare le propriet` a elementari della

teoria degli insiemi. Questo facilita anche l’enunciazione degli assiomi

restanti.

Gli assiomi di ZFC (primo blocco)

1. Estensionalit` a: ∀z(z ∈ x ⇔ z ∈ y ) ⇒ x = y

2. Fondazione: ∃x y ∈ x ⇒ ∃y (y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y )) 3. Schema di separazione: Per ogni formula ϕ:

∃y ∀x(x ∈ y ⇔ x ∈ z ∧ ϕ)

4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

5. Unione: ∃A∀Y ∀x (x ∈ Y ∧ Y ∈ F ⇒ x ∈ A) 6. Schema di rimpiazzamento: Per ogni formula ϕ:

∀x ∈ A ∃!y ϕ ⇒ ∃Y ∀x ∈ A ∃y ∈ Y ϕ

Gli assiomi 1–6 permettono di sviluppare le propriet` a elementari della

teoria degli insiemi. Questo facilita anche l’enunciazione degli assiomi

restanti.

Gli assiomi di ZFC (primo blocco)

1. Estensionalit` a: ∀z(z ∈ x ⇔ z ∈ y ) ⇒ x = y

2. Fondazione: ∃x y ∈ x ⇒ ∃y (y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y )) 3. Schema di separazione: Per ogni formula ϕ:

∃y ∀x(x ∈ y ⇔ x ∈ z ∧ ϕ) 4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

5. Unione: ∃A∀Y ∀x (x ∈ Y ∧ Y ∈ F ⇒ x ∈ A) 6. Schema di rimpiazzamento: Per ogni formula ϕ:

∀x ∈ A ∃!y ϕ ⇒ ∃Y ∀x ∈ A ∃y ∈ Y ϕ

Gli assiomi 1–6 permettono di sviluppare le propriet` a elementari della

teoria degli insiemi. Questo facilita anche l’enunciazione degli assiomi

restanti.

Gli assiomi di ZFC (primo blocco)

1. Estensionalit` a: ∀z(z ∈ x ⇔ z ∈ y ) ⇒ x = y

2. Fondazione: ∃x y ∈ x ⇒ ∃y (y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y )) 3. Schema di separazione: Per ogni formula ϕ:

∃y ∀x(x ∈ y ⇔ x ∈ z ∧ ϕ) 4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

5. Unione: ∃A∀Y ∀x (x ∈ Y ∧ Y ∈ F ⇒ x ∈ A)

6. Schema di rimpiazzamento: Per ogni formula ϕ:

∀x ∈ A ∃!y ϕ ⇒ ∃Y ∀x ∈ A ∃y ∈ Y ϕ

Gli assiomi 1–6 permettono di sviluppare le propriet` a elementari della

teoria degli insiemi. Questo facilita anche l’enunciazione degli assiomi

restanti.

Gli assiomi di ZFC (primo blocco)

1. Estensionalit` a: ∀z(z ∈ x ⇔ z ∈ y ) ⇒ x = y

2. Fondazione: ∃x y ∈ x ⇒ ∃y (y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y )) 3. Schema di separazione: Per ogni formula ϕ:

∃y ∀x(x ∈ y ⇔ x ∈ z ∧ ϕ) 4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

5. Unione: ∃A∀Y ∀x (x ∈ Y ∧ Y ∈ F ⇒ x ∈ A) 6. Schema di rimpiazzamento: Per ogni formula ϕ:

∀x ∈ A ∃!y ϕ ⇒ ∃Y ∀x ∈ A ∃y ∈ Y ϕ

Gli assiomi 1–6 permettono di sviluppare le propriet` a elementari della

teoria degli insiemi. Questo facilita anche l’enunciazione degli assiomi

restanti.

Gli assiomi di ZFC (primo blocco)

1. Estensionalit` a: ∀z(z ∈ x ⇔ z ∈ y ) ⇒ x = y

2. Fondazione: ∃x y ∈ x ⇒ ∃y (y ∈ x ∧ ¬∃z(z ∈ x ∧ z ∈ y )) 3. Schema di separazione: Per ogni formula ϕ:

∃y ∀x(x ∈ y ⇔ x ∈ z ∧ ϕ) 4. Coppia: ∃z(x ∈ z ∧ y ∈ z)

5. Unione: ∃A∀Y ∀x (x ∈ Y ∧ Y ∈ F ⇒ x ∈ A) 6. Schema di rimpiazzamento: Per ogni formula ϕ:

∀x ∈ A ∃!y ϕ ⇒ ∃Y ∀x ∈ A ∃y ∈ Y ϕ

Gli assiomi 1–6 permettono di sviluppare le propriet` a elementari della

teoria degli insiemi. Questo facilita anche l’enunciazione degli assiomi

restanti.

Primi sviluppi della teoria

Definizione.

I

Insieme vuoto: y = ∅ ⇔ ∀x x / ∈ y

I

Inclusione: x ⊆ y ⇔ ∀z(z ∈ x ⇒ z ∈ y )

I

Coppia ordinata: (x , y ) = {{x }, {x , y }

I

Comprensione: y = {z ∈ x | ϕ(z)} ⇔ ∀z(z ∈ y ⇔ z ∈ x ∧ ϕ(z))

I

Unione: S F = S

Y = {x | ∃Y ∈ F x ∈ Y }

I

Prodotto cartesiano: A × B = {(x , y ) | x ∈ A, y ∈ B}

Primi sviluppi della teoria

Definizione.

I

Insieme vuoto: y = ∅ ⇔ ∀x x / ∈ y

I

Inclusione: x ⊆ y ⇔ ∀z(z ∈ x ⇒ z ∈ y )

I

Coppia ordinata: (x , y ) = {{x }, {x , y }

I

Comprensione: y = {z ∈ x | ϕ(z)} ⇔ ∀z(z ∈ y ⇔ z ∈ x ∧ ϕ(z))

I

Unione: S F = S

Y = {x | ∃Y ∈ F x ∈ Y }

I

Prodotto cartesiano: A × B = {(x , y ) | x ∈ A, y ∈ B}

Primi sviluppi della teoria

Definizione.

I

Insieme vuoto: y = ∅ ⇔ ∀x x / ∈ y

I

Inclusione: x ⊆ y ⇔ ∀z(z ∈ x ⇒ z ∈ y )

I

Coppia ordinata: (x , y ) = {{x }, {x , y }

I

Comprensione: y = {z ∈ x | ϕ(z)} ⇔ ∀z(z ∈ y ⇔ z ∈ x ∧ ϕ(z))

I

Unione: S F = S

Y = {x | ∃Y ∈ F x ∈ Y }

I

Prodotto cartesiano: A × B = {(x , y ) | x ∈ A, y ∈ B}

Primi sviluppi della teoria

Definizione.

I

Insieme vuoto: y = ∅ ⇔ ∀x x / ∈ y

I

Inclusione: x ⊆ y ⇔ ∀z(z ∈ x ⇒ z ∈ y )

I

Coppia ordinata: (x , y ) = {{x }, {x , y }

I

Comprensione: y = {z ∈ x | ϕ(z)} ⇔ ∀z(z ∈ y ⇔ z ∈ x ∧ ϕ(z))

I

Unione: S F = S

Y = {x | ∃Y ∈ F x ∈ Y }

I

Prodotto cartesiano: A × B = {(x , y ) | x ∈ A, y ∈ B}

Primi sviluppi della teoria

Definizione.

I

Insieme vuoto: y = ∅ ⇔ ∀x x / ∈ y

I

Inclusione: x ⊆ y ⇔ ∀z(z ∈ x ⇒ z ∈ y )

I

Coppia ordinata: (x , y ) = {{x }, {x , y }

I

Comprensione: y = {z ∈ x | ϕ(z)} ⇔ ∀z(z ∈ y ⇔ z ∈ x ∧ ϕ(z))

I

Unione: S F = S

Y = {x | ∃Y ∈ F x ∈ Y }

I

Prodotto cartesiano: A × B = {(x , y ) | x ∈ A, y ∈ B}

Primi sviluppi della teoria

Definizione.

I

Insieme vuoto: y = ∅ ⇔ ∀x x / ∈ y

I

Inclusione: x ⊆ y ⇔ ∀z(z ∈ x ⇒ z ∈ y )

I

Coppia ordinata: (x , y ) = {{x }, {x , y }

I

Comprensione: y = {z ∈ x | ϕ(z)} ⇔ ∀z(z ∈ y ⇔ z ∈ x ∧ ϕ(z))

I

Unione: S F = S

Y = {x | ∃Y ∈ F x ∈ Y }

I

Prodotto cartesiano: A × B = {(x , y ) | x ∈ A, y ∈ B}

Relazioni e funzioni

Definizione.

I

R ` e una relazione se ` e un insieme di coppie ordinate

I

domR = {x | ∃y (x , y ) ∈ R}

I

f ` e una funzione se ` e una relazione e ∀x ∈ domf ∃!y (x , y ) ∈ f . Tale y ` e denotato f (x ). Se domf = A e f ⊆ A × B, si scrive f : A → B. Una tale f ` e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x ) 6= f (y )) e

∀z ∈ B ∃x ∈ A f (x) = z.

I

Se R, S sono relazioni, A, B sono insiemi ed f : A → B, allora f ` e un isomorfismo tra (A, R) e (B, S ) se f ` e biiettiva e

∀x, y ∈ A (xRy ⇔ f (x)Sf (y ))

I

R ` e un ordine totale (stretto) su A se ` e irriflessiva (∀x ∈ A¬xRx ), transitiva (∀x , y , z ∈ A (xRy ∧ yRz → xRz)) e totale

(∀x , y ∈ A (x = y ∨ xRy ∨ yRx ))

I

. . .

Si pu` o dunque in questo frammento di ZFC cominciare a sviluppare la matematica ordinaria (per garantire l’esistenza di altri enti importanti in matematica c’` e bisogno degli altri assiomi). Ma la teoria risulta

abbastanza interessante da studiare per interesse indipendente.

Relazioni e funzioni

Definizione.

I

R ` e una relazione se ` e un insieme di coppie ordinate

I

domR = {x | ∃y (x , y ) ∈ R}

I

f ` e una funzione se ` e una relazione e ∀x ∈ domf ∃!y (x , y ) ∈ f . Tale y ` e denotato f (x ). Se domf = A e f ⊆ A × B, si scrive f : A → B. Una tale f ` e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x ) 6= f (y )) e

∀z ∈ B ∃x ∈ A f (x) = z.

I

Se R, S sono relazioni, A, B sono insiemi ed f : A → B, allora f ` e un isomorfismo tra (A, R) e (B, S ) se f ` e biiettiva e

∀x, y ∈ A (xRy ⇔ f (x)Sf (y ))

I

R ` e un ordine totale (stretto) su A se ` e irriflessiva (∀x ∈ A¬xRx ), transitiva (∀x , y , z ∈ A (xRy ∧ yRz → xRz)) e totale

(∀x , y ∈ A (x = y ∨ xRy ∨ yRx ))

I

. . .

Si pu` o dunque in questo frammento di ZFC cominciare a sviluppare la matematica ordinaria (per garantire l’esistenza di altri enti importanti in matematica c’` e bisogno degli altri assiomi). Ma la teoria risulta

abbastanza interessante da studiare per interesse indipendente.

Relazioni e funzioni

Definizione.

I

R ` e una relazione se ` e un insieme di coppie ordinate

I

domR = {x | ∃y (x , y ) ∈ R}

I

f ` e una funzione se ` e una relazione e ∀x ∈ domf ∃!y (x , y ) ∈ f . Tale y ` e denotato f (x ). Se domf = A e f ⊆ A × B, si scrive f : A → B.

Una tale f ` e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x ) 6= f (y )) e

∀z ∈ B ∃x ∈ A f (x) = z.

I

Se R, S sono relazioni, A, B sono insiemi ed f : A → B, allora f ` e un isomorfismo tra (A, R) e (B, S ) se f ` e biiettiva e

∀x, y ∈ A (xRy ⇔ f (x)Sf (y ))

I

R ` e un ordine totale (stretto) su A se ` e irriflessiva (∀x ∈ A¬xRx ), transitiva (∀x , y , z ∈ A (xRy ∧ yRz → xRz)) e totale

(∀x , y ∈ A (x = y ∨ xRy ∨ yRx ))

I

. . .

Si pu` o dunque in questo frammento di ZFC cominciare a sviluppare la matematica ordinaria (per garantire l’esistenza di altri enti importanti in matematica c’` e bisogno degli altri assiomi). Ma la teoria risulta

abbastanza interessante da studiare per interesse indipendente.

Relazioni e funzioni

Definizione.

I

R ` e una relazione se ` e un insieme di coppie ordinate

I

domR = {x | ∃y (x , y ) ∈ R}

I

f ` e una funzione se ` e una relazione e ∀x ∈ domf ∃!y (x , y ) ∈ f . Tale y ` e denotato f (x ). Se domf = A e f ⊆ A × B, si scrive f : A → B.

Una tale f ` e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x ) 6= f (y )) e

∀z ∈ B ∃x ∈ A f (x) = z.

I

Se R, S sono relazioni, A, B sono insiemi ed f : A → B, allora f ` e un isomorfismo tra (A, R) e (B, S ) se f ` e biiettiva e

∀x, y ∈ A (xRy ⇔ f (x)Sf (y ))

I

R ` e un ordine totale (stretto) su A se ` e irriflessiva (∀x ∈ A¬xRx ), transitiva (∀x , y , z ∈ A (xRy ∧ yRz → xRz)) e totale

(∀x , y ∈ A (x = y ∨ xRy ∨ yRx ))

I

. . .

Si pu` o dunque in questo frammento di ZFC cominciare a sviluppare la matematica ordinaria (per garantire l’esistenza di altri enti importanti in matematica c’` e bisogno degli altri assiomi). Ma la teoria risulta

abbastanza interessante da studiare per interesse indipendente.

Relazioni e funzioni

Definizione.

I

R ` e una relazione se ` e un insieme di coppie ordinate

I

domR = {x | ∃y (x , y ) ∈ R}

I

f ` e una funzione se ` e una relazione e ∀x ∈ domf ∃!y (x , y ) ∈ f . Tale y ` e denotato f (x ). Se domf = A e f ⊆ A × B, si scrive f : A → B.

Una tale f ` e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x ) 6= f (y )) e

∀z ∈ B ∃x ∈ A f (x) = z.

I

Se R, S sono relazioni, A, B sono insiemi ed f : A → B, allora f ` e un isomorfismo tra (A, R) e (B, S ) se f ` e biiettiva e

∀x, y ∈ A (xRy ⇔ f (x)Sf (y ))

I

R ` e un ordine totale (stretto) su A se ` e irriflessiva (∀x ∈ A¬xRx ), transitiva (∀x , y , z ∈ A (xRy ∧ yRz → xRz)) e totale

(∀x , y ∈ A (x = y ∨ xRy ∨ yRx ))

I

. . .

Si pu` o dunque in questo frammento di ZFC cominciare a sviluppare la matematica ordinaria (per garantire l’esistenza di altri enti importanti in matematica c’` e bisogno degli altri assiomi). Ma la teoria risulta

abbastanza interessante da studiare per interesse indipendente.

Relazioni e funzioni

Definizione.

I

R ` e una relazione se ` e un insieme di coppie ordinate

I

domR = {x | ∃y (x , y ) ∈ R}

I

f ` e una funzione se ` e una relazione e ∀x ∈ domf ∃!y (x , y ) ∈ f . Tale y ` e denotato f (x ). Se domf = A e f ⊆ A × B, si scrive f : A → B.

Una tale f ` e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x ) 6= f (y )) e

∀z ∈ B ∃x ∈ A f (x) = z.

I

Se R, S sono relazioni, A, B sono insiemi ed f : A → B, allora f ` e un isomorfismo tra (A, R) e (B, S ) se f ` e biiettiva e

∀x, y ∈ A (xRy ⇔ f (x)Sf (y ))

I

R ` e un ordine totale (stretto) su A se ` e irriflessiva (∀x ∈ A¬xRx ), transitiva (∀x , y , z ∈ A (xRy ∧ yRz → xRz)) e totale

(∀x , y ∈ A (x = y ∨ xRy ∨ yRx ))

I

. . .

Si pu` o dunque in questo frammento di ZFC cominciare a sviluppare la matematica ordinaria (per garantire l’esistenza di altri enti importanti in matematica c’` e bisogno degli altri assiomi). Ma la teoria risulta

abbastanza interessante da studiare per interesse indipendente.

Relazioni e funzioni

Definizione.

I

R ` e una relazione se ` e un insieme di coppie ordinate

I

domR = {x | ∃y (x , y ) ∈ R}

I

f ` e una funzione se ` e una relazione e ∀x ∈ domf ∃!y (x , y ) ∈ f . Tale y ` e denotato f (x ). Se domf = A e f ⊆ A × B, si scrive f : A → B.

Una tale f ` e biiettiva se ∀x , y ∈ A (x 6= y ⇒ f (x ) 6= f (y )) e

∀z ∈ B ∃x ∈ A f (x) = z.

I

Se R, S sono relazioni, A, B sono insiemi ed f : A → B, allora f ` e un isomorfismo tra (A, R) e (B, S ) se f ` e biiettiva e

∀x, y ∈ A (xRy ⇔ f (x)Sf (y ))

I

R ` e un ordine totale (stretto) su A se ` e irriflessiva (∀x ∈ A¬xRx ), transitiva (∀x , y , z ∈ A (xRy ∧ yRz → xRz)) e totale

(∀x , y ∈ A (x = y ∨ xRy ∨ yRx ))

I

. . .

Si pu` o dunque in questo frammento di ZFC cominciare a sviluppare la matematica ordinaria (per garantire l’esistenza di altri enti importanti in matematica c’` e bisogno degli altri assiomi). Ma la teoria risulta

abbastanza interessante da studiare per interesse indipendente.

Buoni ordini

Un concetto importante in molte aree della matematica e fondamentale in teoria degli insiemi ` e quello di buon ordine.

Definizione. Una relazione d’ordine (A, R) ` e un buon ordine se ogni sottoinsieme non vuoto B ⊆ A ha un elemento minimo rispetto a R.

Lemma. Se (A, R) ` e un buon ordine e a ∈ A, allora (A, R) non ` e isomorfo al suo segmento iniziale ({x ∈ A | xRa}, R).

Dimostrazione. Se f : A → {x ∈ A | xRa} ` e un isomorfismo, l’elemento min{y ∈ A | f (y ) 6= y } produce una contraddizione.

Lemma. Se (A, R), (B, S ) sono buoni ordini isomorfi, l’isomorfismo tra loro ` e unico.

Dimostrazione. Se f , g : A → B sono isomorfismi, l’esistenza di

min{y ∈ A | f (y ) 6= g (y )} fornisce una contraddizione.

Buoni ordini

Un concetto importante in molte aree della matematica e fondamentale in teoria degli insiemi ` e quello di buon ordine.

Definizione. Una relazione d’ordine (A, R) ` e un buon ordine se ogni sottoinsieme non vuoto B ⊆ A ha un elemento minimo rispetto a R.

Lemma. Se (A, R) ` e un buon ordine e a ∈ A, allora (A, R) non ` e isomorfo al suo segmento iniziale ({x ∈ A | xRa}, R).

Dimostrazione. Se f : A → {x ∈ A | xRa} ` e un isomorfismo, l’elemento min{y ∈ A | f (y ) 6= y } produce una contraddizione.

Lemma. Se (A, R), (B, S ) sono buoni ordini isomorfi, l’isomorfismo tra loro ` e unico.

Dimostrazione. Se f , g : A → B sono isomorfismi, l’esistenza di

min{y ∈ A | f (y ) 6= g (y )} fornisce una contraddizione.

Buoni ordini

Un concetto importante in molte aree della matematica e fondamentale in teoria degli insiemi ` e quello di buon ordine.

Definizione. Una relazione d’ordine (A, R) ` e un buon ordine se ogni sottoinsieme non vuoto B ⊆ A ha un elemento minimo rispetto a R.

Lemma. Se (A, R) ` e un buon ordine e a ∈ A, allora (A, R) non ` e isomorfo al suo segmento iniziale ({x ∈ A | xRa}, R).

Dimostrazione. Se f : A → {x ∈ A | xRa} ` e un isomorfismo, l’elemento min{y ∈ A | f (y ) 6= y } produce una contraddizione.

Lemma. Se (A, R), (B, S ) sono buoni ordini isomorfi, l’isomorfismo tra loro ` e unico.

Dimostrazione. Se f , g : A → B sono isomorfismi, l’esistenza di

min{y ∈ A | f (y ) 6= g (y )} fornisce una contraddizione.

Buoni ordini

Un concetto importante in molte aree della matematica e fondamentale in teoria degli insiemi ` e quello di buon ordine.

Definizione. Una relazione d’ordine (A, R) ` e un buon ordine se ogni sottoinsieme non vuoto B ⊆ A ha un elemento minimo rispetto a R.

Lemma. Se (A, R) ` e un buon ordine e a ∈ A, allora (A, R) non ` e isomorfo al suo segmento iniziale ({x ∈ A | xRa}, R).

Dimostrazione. Se f : A → {x ∈ A | xRa} ` e un isomorfismo, l’elemento min{y ∈ A | f (y ) 6= y } produce una contraddizione.

Lemma. Se (A, R), (B, S ) sono buoni ordini isomorfi, l’isomorfismo tra loro ` e unico.

Dimostrazione. Se f , g : A → B sono isomorfismi, l’esistenza di

min{y ∈ A | f (y ) 6= g (y )} fornisce una contraddizione.

Buoni ordini

Teorema. Se (A, R), (B, S ) sono buoni ordini, vale esattamente una delle alternative seguenti:

1. (A, R), (B, S ) sono isomorfi

2. (A, R), ({y ∈ B | ySb}, S ) sono isomorfi, per qualche b ∈ B 3. ({x ∈ A | xRa}, R), (B, S ) sono isomorfi, per qualche a ∈ A

Dimostrazione. Sia

f = {(a, b) ∈ A × B | {x ∈ A | xRa} ' {y ∈ B | ySb}}.

Allora f ` e un isomorfismo tra un segmento iniziale di A e un segmento

iniziale di B, e non possono essere entrambi propri.

Buoni ordini

Teorema. Se (A, R), (B, S ) sono buoni ordini, vale esattamente una delle alternative seguenti:

1. (A, R), (B, S ) sono isomorfi

2. (A, R), ({y ∈ B | ySb}, S ) sono isomorfi, per qualche b ∈ B 3. ({x ∈ A | xRa}, R), (B, S ) sono isomorfi, per qualche a ∈ A Dimostrazione. Sia

f = {(a, b) ∈ A × B | {x ∈ A | xRa} ' {y ∈ B | ySb}}.

Allora f ` e un isomorfismo tra un segmento iniziale di A e un segmento

iniziale di B, e non possono essere entrambi propri.

Ordinali

Definizione.

I

Un insieme x ` e transitivo se ogni elemento di x ` e sottoinsieme di x :

∀y ∈ x y ⊆ x

I

x ` e un numero ordinale se ` e transitivo e la relazione ∈ ` e un buon ordine su x

Esempi d’ordinali (i numeri naturali)

I

0 = ∅

I

1 = {0}

I

2 = {0, 1} = {∅, {∅}}

I

3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}

I

. . .

Con gli assiomi introdotti finora non si pu` o dimostrare l’esistenza di altri

ordinali.

Ordinali

Definizione.

I

Un insieme x ` e transitivo se ogni elemento di x ` e sottoinsieme di x :

∀y ∈ x y ⊆ x

I

x ` e un numero ordinale se ` e transitivo e la relazione ∈ ` e un buon ordine su x

Esempi d’ordinali (i numeri naturali)

I

0 = ∅

I

1 = {0}

I

2 = {0, 1} = {∅, {∅}}

I

3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}

I

. . .

Con gli assiomi introdotti finora non si pu` o dimostrare l’esistenza di altri

ordinali.

Ordinali

Definizione.

I

Un insieme x ` e transitivo se ogni elemento di x ` e sottoinsieme di x :

∀y ∈ x y ⊆ x

I

x ` e un numero ordinale se ` e transitivo e la relazione ∈ ` e un buon ordine su x

Esempi d’ordinali (i numeri naturali)

I

0 = ∅

I

1 = {0}

I

2 = {0, 1} = {∅, {∅}}

I

3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}

I

. . .

Con gli assiomi introdotti finora non si pu` o dimostrare l’esistenza di altri

ordinali.

Ordinali

Definizione.

I

Un insieme x ` e transitivo se ogni elemento di x ` e sottoinsieme di x :

∀y ∈ x y ⊆ x

I

x ` e un numero ordinale se ` e transitivo e la relazione ∈ ` e un buon ordine su x

Esempi d’ordinali (i numeri naturali)

I

0 = ∅

I

1 = {0}

I

2 = {0, 1} = {∅, {∅}}

I

3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}

I

. . .

Con gli assiomi introdotti finora non si pu` o dimostrare l’esistenza di altri

ordinali.

Ordinali

Definizione.

I

Un insieme x ` e transitivo se ogni elemento di x ` e sottoinsieme di x :

∀y ∈ x y ⊆ x

I

x ` e un numero ordinale se ` e transitivo e la relazione ∈ ` e un buon ordine su x

Esempi d’ordinali (i numeri naturali)

I

0 = ∅

I

1 = {0}

I

2 = {0, 1} = {∅, {∅}}

I

3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}

I

. . .

Con gli assiomi introdotti finora non si pu` o dimostrare l’esistenza di altri

ordinali.

Ordinali

Definizione.

I

Un insieme x ` e transitivo se ogni elemento di x ` e sottoinsieme di x :

∀y ∈ x y ⊆ x

I

x ` e un numero ordinale se ` e transitivo e la relazione ∈ ` e un buon ordine su x

Esempi d’ordinali (i numeri naturali)

I

0 = ∅

I

1 = {0}

I

2 = {0, 1} = {∅, {∅}}

I

3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}

I

. . .

Con gli assiomi introdotti finora non si pu` o dimostrare l’esistenza di altri

ordinali.

Ordinali

Definizione.

I

Un insieme x ` e transitivo se ogni elemento di x ` e sottoinsieme di x :

∀y ∈ x y ⊆ x

I

x ` e un numero ordinale se ` e transitivo e la relazione ∈ ` e un buon ordine su x

Esempi d’ordinali (i numeri naturali)

I

0 = ∅

I

1 = {0}

I

2 = {0, 1} = {∅, {∅}}

I

3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}

I

. . .

Con gli assiomi introdotti finora non si pu` o dimostrare l’esistenza di altri

ordinali.

Ordinali

Teorema.

1. Se x ` e un ordinale e y ∈ x , allora y ` e un ordinale e y ` e l’insieme dei

∈-predecessori di se stesso in x

2. Se x , y sono ordinali e x ' y , allora x = y

3. Se x , y sono ordinali, esattamente una delle seguenti alternative vale: x ∈ y , x = y , y ∈ x

4. Se x , y , z sono ordinali e x ∈ y , y ∈ z, allora x ∈ z 5. Se C ` e un insieme non vuoto di ordinali, allora

∃x ∈ C ∀y ∈ C (x = y ∨ x ∈ y )

6. Se ϕ ` e una formula soddisfatta da almeno un ordinale, allora c’` e un minimo ordinale che la soddisfa

Dimostrazione. (5) Sia x ∈ C . Se x ∩ C = ∅, allora x ` e ∈-minimo in C . Altrimenti min(x ∩ C ) = min C .

(6) Simile a (5). Si esprime anche dicendo che ogni classe non vuota di

ordinali ha un minimo.

Ordinali

Teorema.

1. Se x ` e un ordinale e y ∈ x , allora y ` e un ordinale e y ` e l’insieme dei

∈-predecessori di se stesso in x

2. Se x , y sono ordinali e x ' y , allora x = y

3. Se x , y sono ordinali, esattamente una delle seguenti alternative vale: x ∈ y , x = y , y ∈ x

4. Se x , y , z sono ordinali e x ∈ y , y ∈ z, allora x ∈ z 5. Se C ` e un insieme non vuoto di ordinali, allora

∃x ∈ C ∀y ∈ C (x = y ∨ x ∈ y )

6. Se ϕ ` e una formula soddisfatta da almeno un ordinale, allora c’` e un minimo ordinale che la soddisfa

Dimostrazione. (5) Sia x ∈ C . Se x ∩ C = ∅, allora x ` e ∈-minimo in C . Altrimenti min(x ∩ C ) = min C .

(6) Simile a (5). Si esprime anche dicendo che ogni classe non vuota di

ordinali ha un minimo.

Ordinali

Teorema.

1. Se x ` e un ordinale e y ∈ x , allora y ` e un ordinale e y ` e l’insieme dei

∈-predecessori di se stesso in x

2. Se x , y sono ordinali e x ' y , allora x = y

3. Se x , y sono ordinali, esattamente una delle seguenti alternative vale: x ∈ y , x = y , y ∈ x

4. Se x , y , z sono ordinali e x ∈ y , y ∈ z, allora x ∈ z 5. Se C ` e un insieme non vuoto di ordinali, allora

∃x ∈ C ∀y ∈ C (x = y ∨ x ∈ y )

6. Se ϕ ` e una formula soddisfatta da almeno un ordinale, allora c’` e un minimo ordinale che la soddisfa

Dimostrazione. (5) Sia x ∈ C . Se x ∩ C = ∅, allora x ` e ∈-minimo in C . Altrimenti min(x ∩ C ) = min C .

(6) Simile a (5). Si esprime anche dicendo che ogni classe non vuota di

ordinali ha un minimo.

Ordinali

Teorema.

1. Se x ` e un ordinale e y ∈ x , allora y ` e un ordinale e y ` e l’insieme dei

∈-predecessori di se stesso in x

2. Se x , y sono ordinali e x ' y , allora x = y

3. Se x , y sono ordinali, esattamente una delle seguenti alternative vale: x ∈ y , x = y , y ∈ x

4. Se x , y , z sono ordinali e x ∈ y , y ∈ z, allora x ∈ z

5. Se C ` e un insieme non vuoto di ordinali, allora

∃x ∈ C ∀y ∈ C (x = y ∨ x ∈ y )

6. Se ϕ ` e una formula soddisfatta da almeno un ordinale, allora c’` e un minimo ordinale che la soddisfa

Dimostrazione. (5) Sia x ∈ C . Se x ∩ C = ∅, allora x ` e ∈-minimo in C . Altrimenti min(x ∩ C ) = min C .

(6) Simile a (5). Si esprime anche dicendo che ogni classe non vuota di

ordinali ha un minimo.

Ordinali

Teorema.

1. Se x ` e un ordinale e y ∈ x , allora y ` e un ordinale e y ` e l’insieme dei

∈-predecessori di se stesso in x

2. Se x , y sono ordinali e x ' y , allora x = y

3. Se x , y sono ordinali, esattamente una delle seguenti alternative vale: x ∈ y , x = y , y ∈ x

4. Se x , y , z sono ordinali e x ∈ y , y ∈ z, allora x ∈ z 5. Se C ` e un insieme non vuoto di ordinali, allora

∃x ∈ C ∀y ∈ C (x = y ∨ x ∈ y )

6. Se ϕ ` e una formula soddisfatta da almeno un ordinale, allora c’` e un minimo ordinale che la soddisfa

Dimostrazione. (5) Sia x ∈ C . Se x ∩ C = ∅, allora x ` e ∈-minimo in C . Altrimenti min(x ∩ C ) = min C .

(6) Simile a (5). Si esprime anche dicendo che ogni classe non vuota di

ordinali ha un minimo.

Ordinali

Lemma. Se A ` e un insieme transitivo di ordinali, allora A ` e un ordinale.

Teorema. Se (A, R) ` e un buon ordine, allora c’` e un unico ordinale C isomorfo a (A, R).

Dimostrazione. (Esistenza) Siano

B = {a ∈ A | ∃x (x ` e un ordinale e {b ∈ A | bRa} ' x )} f (a) = l’unico x tale che {b ∈ A | bRa} ' x .

Se C = imf ` e l’immagine di f , per il lemma precedente C ` e un ordinale e f : B → C ` e un isomorfismo. Se fosse B 6= A, sia m = min(A \ B). Allora B = {a ∈ A | aRm}, da cui m ∈ B, contraddizione.

Gli ordinali sono dunque rappresentanti dei tipi d’ordine dei buoni ordini.

Ordinali

Lemma. Se A ` e un insieme transitivo di ordinali, allora A ` e un ordinale.

Teorema. Se (A, R) ` e un buon ordine, allora c’` e un unico ordinale C isomorfo a (A, R).

Dimostrazione. (Esistenza) Siano

B = {a ∈ A | ∃x (x `e un ordinale e {b ∈ A | bRa} ' x)}

f (a) = l’unico x tale che {b ∈ A | bRa} ' x .

Se C = imf ` e l’immagine di f , per il lemma precedente C ` e un ordinale e f : B → C ` e un isomorfismo. Se fosse B 6= A, sia m = min(A \ B). Allora B = {a ∈ A | aRm}, da cui m ∈ B, contraddizione.

Gli ordinali sono dunque rappresentanti dei tipi d’ordine dei buoni ordini.

Ordinali

Lemma. Se A ` e un insieme transitivo di ordinali, allora A ` e un ordinale.

Teorema. Se (A, R) ` e un buon ordine, allora c’` e un unico ordinale C isomorfo a (A, R).

Dimostrazione. (Esistenza) Siano

B = {a ∈ A | ∃x (x `e un ordinale e {b ∈ A | bRa} ' x)}

f (a) = l’unico x tale che {b ∈ A | bRa} ' x .

Se C = imf ` e l’immagine di f , per il lemma precedente C ` e un ordinale e f : B → C ` e un isomorfismo. Se fosse B 6= A, sia m = min(A \ B).

Allora B = {a ∈ A | aRm}, da cui m ∈ B, contraddizione.

Gli ordinali sono dunque rappresentanti dei tipi d’ordine dei buoni ordini.

Ordinali

Lemma. Se A ` e un insieme transitivo di ordinali, allora A ` e un ordinale.

Teorema. Se (A, R) ` e un buon ordine, allora c’` e un unico ordinale C isomorfo a (A, R).

Dimostrazione. (Esistenza) Siano

B = {a ∈ A | ∃x (x `e un ordinale e {b ∈ A | bRa} ' x)}

f (a) = l’unico x tale che {b ∈ A | bRa} ' x .

Se C = imf ` e l’immagine di f , per il lemma precedente C ` e un ordinale e f : B → C ` e un isomorfismo. Se fosse B 6= A, sia m = min(A \ B).

Allora B = {a ∈ A | aRm}, da cui m ∈ B, contraddizione.

Gli ordinali sono dunque rappresentanti dei tipi d’ordine dei buoni ordini.

Ordinali

La relazione α ∈ β tra ordinali si scrive di solito α < β.

α ≤ β significa α = β ∨ α < β.

Lemma. Per ogni α, β ordinali, α ≤ β ⇔ α ⊆ β.

Definizione. Il successore di un ordinale α ` e S α = α ∪ {α}. Lemma. Per ogni ordinale α:

I

S (α) ` e un ordinale

I

α < S α

I

∀β(β < Sα ⇔ β ≤ α)

Inoltre, se X ` e un insieme non vuoto di ordinali, sup X = S X .

Ordinali

La relazione α ∈ β tra ordinali si scrive di solito α < β.

α ≤ β significa α = β ∨ α < β.

Lemma. Per ogni α, β ordinali, α ≤ β ⇔ α ⊆ β.

Definizione. Il successore di un ordinale α ` e S α = α ∪ {α}. Lemma. Per ogni ordinale α:

I

S (α) ` e un ordinale

I

α < S α

I

∀β(β < Sα ⇔ β ≤ α)

Inoltre, se X ` e un insieme non vuoto di ordinali, sup X = S X .

Ordinali

La relazione α ∈ β tra ordinali si scrive di solito α < β.

α ≤ β significa α = β ∨ α < β.

Lemma. Per ogni α, β ordinali, α ≤ β ⇔ α ⊆ β.

Definizione. Il successore di un ordinale α ` e S α = α ∪ {α}.

Lemma. Per ogni ordinale α:

I

S (α) ` e un ordinale

I

α < S α

I

∀β(β < Sα ⇔ β ≤ α)

Inoltre, se X ` e un insieme non vuoto di ordinali, sup X = S X .

Ordinali

La relazione α ∈ β tra ordinali si scrive di solito α < β.

α ≤ β significa α = β ∨ α < β.

Lemma. Per ogni α, β ordinali, α ≤ β ⇔ α ⊆ β.

Definizione. Il successore di un ordinale α ` e S α = α ∪ {α}.

Lemma. Per ogni ordinale α:

I

S (α) ` e un ordinale

I

α < S α

I

∀β(β < Sα ⇔ β ≤ α)

Inoltre, se X ` e un insieme non vuoto di ordinali, sup X = S X .

Ordinali

La relazione α ∈ β tra ordinali si scrive di solito α < β.

α ≤ β significa α = β ∨ α < β.

Lemma. Per ogni α, β ordinali, α ≤ β ⇔ α ⊆ β.

Definizione. Il successore di un ordinale α ` e S α = α ∪ {α}.

Lemma. Per ogni ordinale α:

I

S (α) ` e un ordinale

I

α < S α

I

∀β(β < Sα ⇔ β ≤ α)

Inoltre, se X ` e un insieme non vuoto di ordinali, sup X = S X .

Ordinali

La relazione α ∈ β tra ordinali si scrive di solito α < β.

α ≤ β significa α = β ∨ α < β.

Lemma. Per ogni α, β ordinali, α ≤ β ⇔ α ⊆ β.

Definizione. Il successore di un ordinale α ` e S α = α ∪ {α}.

Lemma. Per ogni ordinale α:

I

S (α) ` e un ordinale

I

α < S α

I

∀β(β < Sα ⇔ β ≤ α)

Inoltre, se X ` e un insieme non vuoto di ordinali, sup X = S X .

Ordinali

La relazione α ∈ β tra ordinali si scrive di solito α < β.

α ≤ β significa α = β ∨ α < β.

Lemma. Per ogni α, β ordinali, α ≤ β ⇔ α ⊆ β.

Definizione. Il successore di un ordinale α ` e S α = α ∪ {α}.

Lemma. Per ogni ordinale α:

I

S (α) ` e un ordinale

I

α < S α

I

∀β(β < Sα ⇔ β ≤ α)

Inoltre, se X ` e un insieme non vuoto di ordinali, sup X = S X .

Ordinali

Definizione. Un ordinale α ` e

I

un ordinale successore se α = S β per qualche β

I

un ordinale limite se non ` e 0 n` e un ordinale sucessore Definizione. α ` e un numero naturale se

∀β ≤ α (β = 0 ∨ β ` e successore).

I naturali formano quindi un segmento iniziale degli ordinali.

Ordinali

Definizione. Un ordinale α ` e

I

un ordinale successore se α = S β per qualche β

I

un ordinale limite se non ` e 0 n` e un ordinale sucessore

Definizione. α ` e un numero naturale se

∀β ≤ α (β = 0 ∨ β ` e successore).

I naturali formano quindi un segmento iniziale degli ordinali.

Ordinali

Definizione. Un ordinale α ` e

I

un ordinale successore se α = S β per qualche β

I

un ordinale limite se non ` e 0 n` e un ordinale sucessore Definizione. α ` e un numero naturale se

∀β ≤ α (β = 0 ∨ β ` e successore).

I naturali formano quindi un segmento iniziale degli ordinali.

Operazioni sugli ordinali

Si definiscono, per induzione transfinita, alcune operazioni sugli ordinali (che coincidono sui naturali con le corrispondenti operazioni aritmetiche):

Addizione.

I

α + 0 = α

I

α + S β = S (α + β)

I

Se λ ` e un ordinale limite, α + λ = sup{α + β | β < λ}

α + β ` e il tipo d’ordine di un’unione disgiunta di un tipo d’ordine α con in coda un tipo d’ordine β.

Per esempio, α + 1 = S α.

Operazioni sugli ordinali

Si definiscono, per induzione transfinita, alcune operazioni sugli ordinali (che coincidono sui naturali con le corrispondenti operazioni aritmetiche):

Addizione.

I

α + 0 = α

I

α + S β = S (α + β)

I

Se λ ` e un ordinale limite, α + λ = sup{α + β | β < λ}

α + β ` e il tipo d’ordine di un’unione disgiunta di un tipo d’ordine α con in coda un tipo d’ordine β.

Per esempio, α + 1 = S α.

Operazioni sugli ordinali

Si definiscono, per induzione transfinita, alcune operazioni sugli ordinali (che coincidono sui naturali con le corrispondenti operazioni aritmetiche):

Addizione.

I

α + 0 = α

I

α + S β = S (α + β)

I

Se λ ` e un ordinale limite, α + λ = sup{α + β | β < λ}

α + β ` e il tipo d’ordine di un’unione disgiunta di un tipo d’ordine α con in coda un tipo d’ordine β.

Per esempio, α + 1 = S α.

Operazioni sugli ordinali

Moltiplicazione

I

α0 = 0

I

αS β = αβ + α

I

Se λ ` e un ordinale limite, αλ = sup{αβ | β < λ}

αβ ` e il tipo d’ordine di α × β ordinato antilessicograficamente. Esponenziazione.

I

α

= 1

I

α

= α

α

I

Se λ ` e un ordinale limite, α

= sup{α

| β < λ}

Operazioni sugli ordinali

Moltiplicazione

I

α0 = 0

I

αS β = αβ + α

I

Se λ ` e un ordinale limite, αλ = sup{αβ | β < λ}

αβ ` e il tipo d’ordine di α × β ordinato antilessicograficamente.

Esponenziazione.

I

α

= 1

I

α

= α

α

I

Se λ ` e un ordinale limite, α

= sup{α

| β < λ}

Operazioni sugli ordinali

Moltiplicazione

I

α0 = 0

I

αS β = αβ + α

I

Se λ ` e un ordinale limite, αλ = sup{αβ | β < λ}

αβ ` e il tipo d’ordine di α × β ordinato antilessicograficamente.

Esponenziazione.

I

α

= 1

I

α

= α

α

I

Se λ ` e un ordinale limite, α

= sup{α

| β < λ}

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x )

8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X ) L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile. Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).) Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x ) 8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X ) L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile. Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).) Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x ) 8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X )

L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile. Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).) Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x ) 8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X ) L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile.

Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).) Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x ) 8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X ) L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile.

Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).) Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x ) 8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X ) L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile.

Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).)

Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x ) 8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X ) L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile.

Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).) Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x ) 8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X ) L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile.

Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).) Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Gli assiomi di ZFC (secondo blocco)

7. Infinito: ∃x (0 ∈ x | ∀y ∈ x Sy ∈ x ) 8. Potenza: ∃y ∀z(z ⊆ x ⇒ z ∈ y )

9. Scelta: ∃f : F → S F ∀X ∈ F (X 6= ∅ ⇒ f (X ) ∈ X ) L’assioma della scelta ` e equivalente al

Principio del buon ordinamento. Ogni insieme ` e bene ordinabile.

Lemma di Zorn. Se A ` e un insieme (parzialmente) ordinato tale che ogni suo sottoinsieme totalmente ordinato ha un maggiorante, allora A ha un elemento massimale.

(Un ordine parziale ≤ ` e una relazione riflessiva: ∀x x ≤ x ; transitiva:

∀x, y , z (x ≤ y ∧ y ≤ z ⇒ x ≤ z); antisimmetrica:

∀x, y (x ≤ y ∧ y ≤ x ⇒ x = y ). ` E totale se ∀x , y (x ≤ y ∨ y ≤ x ).) Definizione. L’insieme dei numeri naturali, che esiste per gli assioma dell’infinito e di separazione, ` e indicato con ω.

Teorema. ω ` e un ordinale. ` E il minimo degli ordinali infiniti (cio` e non in biiezione con un numero naturale).

Definizione. P(x ) = {z | x ⊆ x } ` e l’insieme potenza di x .

Numeri cardinali

Definizione. Dato un insieme A, la cardinalit` a di A, denotata |A|, ` e il minimo ordinale α in biiezione con A (l’esistenza di α ` e l’enunciato dell’assioma della scelta).

Se α ` e tale che |A| = α per qualche α (equivalentemente, α = |α|), allora α ` e un numero cardinale.

L’insieme A ` e finito se |A| ` e un numero naturale.

L’insieme A ` e numerabile se |A| ≤ ω.

Teorema. Se κ, λ sono cardinali

I

κ = λ sse

esiste una bijezione κ → λ sse esistono iniezioni κ → λ, λ → κ

I

κ ≤ λ sse

esiste una iniezione κ → λ sse

esiste una suriezione λ → κ

Numeri cardinali

Definizione. Dato un insieme A, la cardinalit` a di A, denotata |A|, ` e il minimo ordinale α in biiezione con A (l’esistenza di α ` e l’enunciato dell’assioma della scelta).

Se α ` e tale che |A| = α per qualche α (equivalentemente, α = |α|), allora α ` e un numero cardinale.

L’insieme A ` e finito se |A| ` e un numero naturale.

L’insieme A ` e numerabile se |A| ≤ ω.

Teorema. Se κ, λ sono cardinali

I

κ = λ sse

esiste una bijezione κ → λ sse esistono iniezioni κ → λ, λ → κ

I

κ ≤ λ sse

esiste una iniezione κ → λ sse

esiste una suriezione λ → κ

Il teorema di Cantor

Esistono cardinali arbitrariamente grandi:

Teorema. |A| < |P(A)|.

Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.

Viceversa, si mostra che non c’` e alcuna suriezione A → P(A). Sia g : A → P(A) una funzione. Allora I = {x ∈ A | x / ∈ g (x)} / ∈ img . Definizione.

I

α

` e il minimo cardinale pi` u grande di α.

I

κ ` e un cardinale successore se κ = α

per qualche α.

I

Un cardinale κ ` e un cardinale limite se κ > ω e κ non ` e un cardinale

successore.

Il teorema di Cantor

Esistono cardinali arbitrariamente grandi:

Teorema. |A| < |P(A)|.

Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.

Viceversa, si mostra che non c’` e alcuna suriezione A → P(A). Sia g : A → P(A) una funzione. Allora I = {x ∈ A | x / ∈ g (x)} / ∈ img . Definizione.

I

α

` e il minimo cardinale pi` u grande di α.

I

κ ` e un cardinale successore se κ = α

per qualche α.

I

Un cardinale κ ` e un cardinale limite se κ > ω e κ non ` e un cardinale

successore.

Il teorema di Cantor

Esistono cardinali arbitrariamente grandi:

Teorema. |A| < |P(A)|.

Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.

Viceversa, si mostra che non c’` e alcuna suriezione A → P(A). Sia g : A → P(A) una funzione. Allora I = {x ∈ A | x / ∈ g (x)} / ∈ img .

Definizione.

I

α

` e il minimo cardinale pi` u grande di α.

I

κ ` e un cardinale successore se κ = α

per qualche α.

I

Un cardinale κ ` e un cardinale limite se κ > ω e κ non ` e un cardinale

successore.

Il teorema di Cantor

Esistono cardinali arbitrariamente grandi:

Teorema. |A| < |P(A)|.

Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.

Viceversa, si mostra che non c’` e alcuna suriezione A → P(A). Sia g : A → P(A) una funzione. Allora I = {x ∈ A | x / ∈ g (x)} / ∈ img . Definizione.

I

α

` e il minimo cardinale pi` u grande di α.

I

κ ` e un cardinale successore se κ = α

per qualche α.

I

Un cardinale κ ` e un cardinale limite se κ > ω e κ non ` e un cardinale

successore.

Il teorema di Cantor

Esistono cardinali arbitrariamente grandi:

Teorema. |A| < |P(A)|.

Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.

Viceversa, si mostra che non c’` e alcuna suriezione A → P(A). Sia g : A → P(A) una funzione. Allora I = {x ∈ A | x / ∈ g (x)} / ∈ img . Definizione.

I

α

` e il minimo cardinale pi` u grande di α.

I

κ ` e un cardinale successore se κ = α

per qualche α.

I

Un cardinale κ ` e un cardinale limite se κ > ω e κ non ` e un cardinale

successore.

Il teorema di Cantor

Esistono cardinali arbitrariamente grandi:

Teorema. |A| < |P(A)|.

Dimostrazione. a 7→ {a} testimonia |A| ≤ |P(A)|.

Viceversa, si mostra che non c’` e alcuna suriezione A → P(A). Sia g : A → P(A) una funzione. Allora I = {x ∈ A | x / ∈ g (x)} / ∈ img . Definizione.

I

α

` e il minimo cardinale pi` u grande di α.

I

κ ` e un cardinale successore se κ = α

per qualche α.

I

Un cardinale κ ` e un cardinale limite se κ > ω e κ non ` e un cardinale

successore.

La sequenza degli ℵ

Si definisce la sequenza dei cardinali ℵ

= ω

:

Definizione.

I

ω

= ω

I

ω

= ω

I

Se λ ` e un ordinale limite, ω

= sup{ω

| α < λ} Teorema.

1. La sequenza degli ℵ

contiene tutti e soli i numeri cardinali 2. α < β ⇒ ℵ

< ℵ

3. ℵ

` e un cardinale successore sse α ` e un ordinale successore; ℵ

` e un

cardinale limite sse α ` e un ordinale limite

La sequenza degli ℵ

Si definisce la sequenza dei cardinali ℵ

= ω

: Definizione.

I

ω

= ω

I

ω

= ω

I

Se λ ` e un ordinale limite, ω

= sup{ω

| α < λ} Teorema.

1. La sequenza degli ℵ

contiene tutti e soli i numeri cardinali 2. α < β ⇒ ℵ

< ℵ

3. ℵ

` e un cardinale successore sse α ` e un ordinale successore; ℵ

` e un

cardinale limite sse α ` e un ordinale limite

La sequenza degli ℵ

Si definisce la sequenza dei cardinali ℵ

= ω

: Definizione.

I

ω

= ω

I

ω

= ω

I

Se λ ` e un ordinale limite, ω

= sup{ω

| α < λ} Teorema.

1. La sequenza degli ℵ

contiene tutti e soli i numeri cardinali 2. α < β ⇒ ℵ

< ℵ

3. ℵ

` e un cardinale successore sse α ` e un ordinale successore; ℵ

` e un

cardinale limite sse α ` e un ordinale limite

La sequenza degli ℵ

Si definisce la sequenza dei cardinali ℵ

= ω

: Definizione.

I

ω

= ω

I

ω

= ω

I

Se λ ` e un ordinale limite, ω

= sup{ω

| α < λ}

Teorema.

1. La sequenza degli ℵ

contiene tutti e soli i numeri cardinali 2. α < β ⇒ ℵ

< ℵ

3. ℵ

` e un cardinale successore sse α ` e un ordinale successore; ℵ

` e un

cardinale limite sse α ` e un ordinale limite

La sequenza degli ℵ

Si definisce la sequenza dei cardinali ℵ

= ω

: Definizione.

I

ω

= ω

I

ω

= ω

I

Se λ ` e un ordinale limite, ω

= sup{ω

| α < λ}

Teorema.

1. La sequenza degli ℵ

contiene tutti e soli i numeri cardinali 2. α < β ⇒ ℵ

< ℵ

3. ℵ

` e un cardinale successore sse α ` e un ordinale successore; ℵ

` e un

cardinale limite sse α ` e un ordinale limite

Operazioni sui cardinali

Si possono definire operazioni di somma, prodotto e esponenziazione cardinale. Estendono le corrispondenti operazioni sui naturali, ma non coincidono con le operazioni definite sugli ordinali infiniti.

Addizione. κ + λ ` e la cardinalit` a di un’unione disgiunta di un insieme di cardinalit` a κ e uno di cardinalit` a λ:

κ + λ = |(κ × {0}) ∪ (λ × {1})|.

Moltiplicazione. κ + λ ` e la cardinalit` a di un prodotto cartesiano di un insieme di cardinalit` a κ e uno di cardinalit` a λ:

κλ = |κ × λ|.

Tuttavia queste operazioni non sono interessanti: se almeno uno tra κ e λ ` e infinito,

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

Operazioni sui cardinali

Si possono definire operazioni di somma, prodotto e esponenziazione cardinale. Estendono le corrispondenti operazioni sui naturali, ma non coincidono con le operazioni definite sugli ordinali infiniti.

Addizione. κ + λ ` e la cardinalit` a di un’unione disgiunta di un insieme di cardinalit` a κ e uno di cardinalit` a λ:

κ + λ = |(κ × {0}) ∪ (λ × {1})|.

Moltiplicazione. κ + λ ` e la cardinalit` a di un prodotto cartesiano di un insieme di cardinalit` a κ e uno di cardinalit` a λ:

κλ = |κ × λ|.

Tuttavia queste operazioni non sono interessanti: se almeno uno tra κ e λ ` e infinito,

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

Operazioni sui cardinali

Definizione. Per A, B insiemi, A

=

A = {f : B → A}.

Se κ, λ sono ordinali, ` e di solito preferibile usare la notazione

κ per questo insieme di funzioni, per evitare confusione col numero cardinale κ

.

Esponenziazione. Se κ, λ sono cardinali, κ

= |

κ|. Esempi.

2

= |P(λ)|

2

= |R| `e la cardinalit`a del continuo

Teorema. Se 2 ≤ κ ≤ λ e λ ` e infinito, λ < 2

= κ

.

Dimostrazione. 2

≤ κ

≤ λ

≤ |P(λ × λ)| = |P(λ)| = 2

.