f : N → A tale che:

1 Teorema di ricorsione

Teorema 1 Siano a ∈ A, g : A × N → A, allora esiste ed `e unica

f : N → A tale che:

( f (0) = a

f (n + 1) = g(f (n), n) Dim:

La dimostrazione ` e divisa in due parti:

Esistenza Utilizziamo le “approssimazioni finite” (AF).

Definizione 1 φ ` e una approssimazione finita (AF) se ` e una funzione che ha per dominio un numero naturale N e

∀n n + 1 ∈ dom φ ⇒ φ(n + 1) = g(φ(n), n) Ad esempio

• φ = {(0, a)} `e un’approssimazione finita con dominio 1

• φ = {(0, a), (1, g(a, 0))} ` e un’approssimazione finita con dominio 2

• se A = N, g(x, n) = nx (la ricorsione del fattoriale) φ = {(0, 1), (1, 1), (2, 2), (3, 6), . . . } Prendiamo ora

F = {φ ∈ P(N × A) | φ `e una AF}

che esiste per lo schema di assiomi di separazione. Allora valgono 1. Se φ, ψ ∈ F e se u ∈ (dom φ) ∩ (dom ψ) allora φ(n) = ψ(n) 2. ∀n ∈ N ∃φ ∈ F : dom φ = n + 1 = {0, 1, . . . , n}

Osserviamo che se valgono (1) e (2) allora f := [

φ∈F

φ ` e la funzione cercata, quindi otteniamo l’esistenza (da (1) segue che f ` e una funzione ben definita, da (2) segue che dom f = N e per la costruzione delle AF segue facilmente che f (n + 1) = g(f (n), n)). Dimostriamo le propriet` a enunciate sopra

1. Per induzione su n

• n = 0 ∈ dom φ ∩ dom ψ e φ(0) = ψ(0)

• n + 1 ∈ dom φ ∩ dom ψ e

φ(n + 1) = g(φ(n), n) = g(ψ(n), n) = ψ(n + 1) 2. Per induzione su n

• n = 0: φ = {(0, a)} ` e una AF con dom φ = {0} = 1 = n + 1

• n → n + 1 per l’ipotesi induttiva esiste una AF φ tale che dom φ = n + 1. Prendiamo allora ˜ φ := φ ∪ {(n + 1, g(φ(n), n)}. Questa ` e chiaramente una AF con dominio n + 2.

Unicit` a Siano f 1 , f 2 : N → A che sodisfano le propriet`a volute. Procediamo per induzione e proviamo che f ₁ (n) = f ₂ (n) per tutti gli n.

• n = 0 ` E ovvio vedere che f ₁ (0) = a = f ₂ (0)

• n → n + 1 Per l’ipotesi induttiva f ₁ (n) = f ₂ (n). Quindi f 1 (n + 1) = g(f 1 (n), n) = g(f 2 (n), n) = f 2 (n + 1) CVD

Teorema 2 Ricorsione numerabile “forte” Siano a ∈ A, G : SF (A) × N → A.

Allora esiste unica

f : N → A tale che

( f (0) = a

f (n) = G(f _|n , n) Dove f _|n = hf (0), . . . , f (n − 1)i.

La dimostrazione di questo risultato ` e lasciata per esercizio.

2 Teorema di Cantor-Bernstein

Teorema 3 Dati due insiemi A, B, se esistono f : A → B, g : B → A iniettive allora esiste h : A → B biunivoca

Dim:

Poich` e f : A → B ` e iniettiva, posto A ⁰ = f [A] = Im f si ha che f : A → A ⁰ ` e bigettiva. Analogamente per g, B posto B <sup>0</sup> = g[B], g : B → B <sup>0</sup> ` e biunivoca. Ma allora

g ◦ f : A → g[A ⁰ ] = g[f [A]]

` e biunivoca. Quindi abbiamo che

• |A| = |g[A ⁰ ]|

• |B| = |B ⁰ |

• g[A ⁰ ] ⊆ B ⁰ ⊆ A

Quindi ci basta dimostare il seguente lemma

Lemma 1 Siano X, Y, Z tre insiemi tali che X ⊇ Y ⊇ Z e che |X| = |Z| allora

|X| = |Y |.

Noi sappiamo che c’` e una bigezione f : X → Z e vorremmo definire h : X → Y . Definiamo

( E ₀ = X\Y

E n+1 = f [E n ] e E := [

n∈N

E _n A questo punto possiamo infine definire

h(x) =

( x se x ∈ Y \E

f (x) altrimenti, cio` e se x ∈ (X\Y ) ∪ E Dimostriamo che h ` e biunivoca.

• g suriettiva:

1. y 6∈ E ⇒ h(y) = f (y) = y

2. y ∈ E ⇒ ∃n ≥ 1 y ∈ E n = f [E n−1 ] ⇒

⇒ ∃x ∈ E n−1 f (x) = y ⇒ h(x) = f (x) = y

• g iniettiva: siano x 1 , x 2 ∈ X tali che f (x 1 ) = f (x 2 ) 1. x 1 , x 2 ∈ (X\Y ) ∪ E

h(x ₁ ) = h(x ₂ ) ⇒ f (x ₁ ) = f (x ₂ ) ⇒ x ₁ = x ₂ per l’iniettivit` a di f .

2. x ₁ , x ₂ ∈ Y \E

h(x 1 ) = h(x 2 ) ⇒ x 1 = x 2

per la definizione di h

3. x 1 ∈ (X\Y ) ∪ E, x 2 ∈ Y \E ma questo ` e assurdo perch` e in questo caso f (x 1 ) ∈ f [(X\Y ) ∪ E] = E mentre f (x 2 ) ∈ f [Y \E] = Y \E CVD

Esercizio 1 Dimostrare che esistono gli insiemi E n utilizzando il teorema di ricorsione.

3 Buoni ordinamenti

Definizione 2 Un insieme totalmente ordinato (A, <) si dice bene ordinato se ogni suo sottoinsieme non vuoto ha minimo

Osservazione 1 Sia A bene ordinato allora per ogni elemento x non massimo definiamo

x + 1 := min{y ∈ A | y > x}

Osservazione 2 Ogni insieme ben ordinato A ha un minimo, indicato con 0 _A

Ricordiamo l’assioma della scelta: Assioma della scelta (AC)

Sia F una famiglia non vuota di insiemi non vuoti. Allora esiste una “funzione di scelta”

f : F → [

X∈F

X tale che ∀X ∈ F f (X) ∈ X

Proposizione 1 (A, <) ` e un insieme bene ordinato ⇔ non esistono catene dis- cendenti, cio` e successioni ha _n | n ∈ N tali che ∀n ∈ N a n+1 < a _n

(⇒) Per assurdo sia ha _n | n ∈ N una catena discendente. Allora l’insieme {a n | n ∈ N} ⊆ A non ha minimo, assurdo.

(⇐) (Usando l’AC) Lasciamo per esercizio di dimostrare che se A non ` e bene ordinato, allora esiste una catena discendente.

Osservazione 3 Ogni segmento iniziale (proprio) S ⊂ A di un insieme bene ordinato ` e della forma:

S = A a := {x ∈ A | x < a}segmento iniziale generato da a ∈ A Infatti basta prendere a = min{x ∈ A | x 6∈ S}.

Proposizione 2 Siano A, B insiemi ben ordinati

1. Sia φ : A → A che preserva l’ordine (cio` e ∀a, b ∈ A a < b ⇒ φ(a) < φ(b)).

Allora ∀a ∈ A φ(a) ≥ a 2. Per ogni a ∈ A, A _a 6∼ = A

3. L’unico automorfismo φ : A → A ` e l’identit` a

4. Se A ∼ = B allora esiste un unico isomorfismo φ : A → B 5. Per ogni b, b ⁰ ∈ B se B b ∼ = B b

allora b = b ⁰

Dim:

1. Per assurdo sia

Γ := {a ∈ A | φ(a) < a} 6= ∅ Allora, poich` e A ` e ben ordinato, esiste ξ := min Γ. Quindi

φ(ξ) < ξ ⇒ φ(φ(ξ)) < φ(ξ) ⇒ φ(ξ) ∈ Γ

Ma questo ` e assurdo perch` e ξ ` e il minimo elemento di Γ e φ(ξ) < ξ.

2. Per assurdo esista a ∈ A tale che A a ∼ = A. Ma allora esiste φ : A → A a

isomorfismo, cio` e la funzione φ : A → A preserva l’ordine, perci` o φ(a) ≥ a.

Ma φ(a) ∈ A a ⇒ φ(a) < a, assurdo.

Le dimostrazioni dei punti 3,4,5 sono lasciate per esercizio.

Teorema 4 (Tricotomia dei buoni ordini) Siano A, B insiemi ben ordinati. Al- lora vale esattamente uno dei casi seguenti

1. A ∼ = B

2. ∃b ∈ B A ∼ = B b

3. ∃a ∈ A A a ∼ = B Dim:

Consideriamo Γ := {(a, b) ∈ A × B | A a ∼ = B b }. Γ non ` e vuoto ad esempio perch` e (0 A , 0 B ) ∈ Γ. L’idea ` e quella di descrivere il “grafico” della funzione che sar` a l’isomorfismo tra A e B.

• Γ ` e una funzione.

(a, b), (a, b ⁰ ) ∈ Γ ⇒ A a ∼ = B b , A a ∼ = B b

⇒ B b ∼ = B _b ⁰ ⇒ b = b ⁰

• Γ preserva l’ordine.

Siano a ⁰ < a Allora A _a ∼ = B Γ(a) e A _a

∼ = B Γ(a

) . Quindi esiste ψ : A _a → B _Γ(a) isomorfismo. Allora ψ _|A

a

: A _a

→ B _ψ(a

) ` e ancora un’isomorfismo.

Cio` e B _Γ(a

) ∼ = A ⁰ _a ∼ = B ψ(a

) , quindi

Γ(a ⁰ ) = ψ(a ⁰ ) ∈ B _Γ(a) ⇒ Γ(a ⁰ ) < Γ(a)

Notiamo che dal fatto che Γ preserva l’ordine segue immediatamente che Γ ` e iniettiva.

• dom Γ ` e un segmento iniziale di A.

Infatti se a ⁰ < a ∈ dom Γ ne segue che esiste ψ : A _a → B _Γ(a) , ma allora anche ψ _|A

a0

: A _a

→ B _ψ(a

) ` e un isomorfismo, e a ⁰ ∈ dom Γ

• Im Γ `e un segmento iniziale di B.

Come sopra

• dom Γ e Im Γ non possono essere entrambi segmenti iniziali propri.

Infatti se per assurdo dom Γ = A a e Im Γ = B b allora Γ sarebbe un’isomorfismo tra A a e B b , cio` e (a, b) ∈ Γ e quindi a ∈ dom Γ = A a , assurdo.

Quindi dalle tre possibilit` a rimaste (al massimo uno tra dom Γ e Im Γ pu` o essere un segmento iniziale proprio) abbiamo i tre casi della tesi. CVD.

Definizione 3 Come notazione per il tipo d’ordine abbiamo che

• ot(A) = ot(B) significa A ∼ = B

• ot(A) < ot(B) significa A ∼ = B b per un opportuno b ∈ B.

Corollario 1 Per ogni A, B, C insiemi ben ordinati

1. ot(A) < ot(B) ∧ ot(B) < ot(C) ⇒ ot(A) < ot(B)

2. ot(A) = ot(B) ∨ ot(A) < ot(B) ∨ ot(A) > ot(B) 3. ot(A) 6< ot(A)

Osservazione 4 Abbiamo qui un “ordine totale” ma come per le classi d’equipotenza anche qui le collezioni d’oggetti sono troppo grandi per essere insiemi.

Osservazione 5 Sia A un insieme bene ordinato

• X ⊆ A ⇒ ot(X) ≤ ot(A)

• X ⊂ A 6⇒ ot(X) < ot(A) Infatti come controesempio basta prendere il sottoinsieme X di ω costituito dai numeri pari, in cui ot(X) = ot(ω) Esercizio 2 1. Due ordini totali sullo stesso insieme finito sono isomorfi

(per induzione)

2. Ogni ordine totale su un insieme finito ` e un buon ordine, cio` e se (A, <) ` e un insieme totalmente ordinato e |A| = n finito allora (A, <) ∼ = (n, ∈).

3. Sia (A, <) un insieme ben ordinato infinito. Allora

(A, <) ∼ = ω ⇔ ∀X ⊆ A infinto ` e privo di massimo Esempio 1 Prendiamo ω e ω + 1 := ω ∪ {ω}S. Allora

|ω| = |ω + 1| tuttavia (ω, ∈) 6∼ = (ω + 1, ∈)

perch` e ω ` e un segmento iniziale di ω + 1. Inoltre ω + 1 ` e infinito e ha max, mentre ogni sottoinsieme infinito di ω non ha max.

3.1 Operazioni sugli insiemi ordinati

Definizione 4 Siano A, B due insiemi totalmente ordinati. Definiamo A ⊕ B := ((A × {0}) ∪ (B × {1}), <)

dove



 

 

(a, 0) < (a ⁰ , 0) ⇔ a < _A a ⁰ (b, 1) < (b ⁰ , 1) ⇔ b < B b ⁰ (a, 0) < (b, 1) ⇔ ∀a ∈ A, b ∈ B

Osservazione 6 Se A, B 6= ∅ allora A ⊕ B 6= B ⊕ A. Inoltre ot(A ⊕ B) >

ot(B). Ma pu` o capitare che ot(A ⊕ B) = ot(B). Per esempio 1 ⊕ ω = ω, ma ot(ω ⊕ 1) > ot(ω). Tuttavia vale che A ⊕ (B ⊕ C) ∼ = (A ⊕ B) ⊕ C.

Definizione 5 Siano A, B due insiemi totalmente ordinati. Definiamo A ⊗ B := (A × B. <)

dove (a, b) < (a ⁰ , b ⁰ ) ⇔ b < B b ⁰ ∨ (b = b ⁰ ∧ a < A a ⁰ ) (ordinamento lessicografico)

Esempio 2 • Se |A| ∼ = |B| ∼ = ω abbiamo che

A ⊕ B = 0 A , 1 A , . . . , 0 B , 1 B , . . .

A ⊗ B = (0 _A , 0 _B ), (1 _A , 0 _B ), . . . , (0 _A , 1 _B ), (1 _A , 1 _B ), . . . , . . .

• Notiamo che, ad esempio ω ⊗ 3 6∼ = 3 ⊗ ω. Infatti

ω ⊗ 3 = (0, 0), (1, 0), . . . , (0, 1), (1, 1), . . . , (0, 2), (1, 2), . . . 3 ⊗ ω = (0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), . . . Esercizio 3 Siano A, B, C insiemi bene ordinati

• (A ⊗ B) ⊗ C ∼ = A ⊗ (B ⊗ C)

• ot(A) < ot(B) ⇒ ∃C A ⊕ C ∼ = B (insieme differenza)

• Leggi di cancellazione:

A ⊕ B ∼ = A ⊕ C ⇒ B ∼ = C A ⊗ B ∼ = A ⊗ C ⇒ B ∼ = C

• Non vale invece

A ⊗ B ∼ = C ⊗ B 6⇒ A ∼ = C

Proposizione 3 Sia F una famiglia non vuota di insiemi ben ordinati, allora esiste ( ˜ F , <) ∈ F che ha tipo d’ordine minimo.

Dim:

Fissiamo (F, <) ∈ F . Se ∀F ⁰ ∈ F ot(F ) ≤ ot(F ⁰ ), abbiamo che F ⁰ ` e minimo.

Altrimenti Γ := {a ∈ F | ∃F ⁰ ∈ F F ⁰ ∼ = F a } ` e non vuoto. Prendiamo quindi a = min Γ, ˜ F ∈ Γ ˜ F ∼ = F a . ` E ovvio che ˜ F ha tipo d’ordine minimo. CVD Esercizio 4 (Cantor) Ogni insieme totalmente ordinato numerabile ` e isomorfo a un sottoinsieme di Q

Esercizio 5 A quale sottoinsieme di Q `e isomorfo N ⊕ N?

E N ⊕ · · · ⊕ N

| {z }

k volte

? E N ⊗ N? E N ⊗ · · · ⊗ N

| {z }

k volte

?

3.2 Esponenziali di buoni ordini

Definizione 6 Siano A, B insiemi totalmente ordinati. L’insieme B ^A := {f | f : A → B ∧ f ` e definitivamente uguale a min Im f } si pu` o dotare di un ordine se A ` e bene ordinato: ( ordine della minima differenza)

∀f, g ∈ B ^A f < g ⇔ f (a) < g(a) dove a = min{x ∈ A | f (x) 6= g(x)}

Esercizio 6 Se A ` e un insieme bene ordinato B <sup>A</sup> ` e un insieme totalmente

ordinato. Inoltre, se B ` e bene ordinato, anche B <sup>A</sup> ` e bene ordinato.

4 Ordinali

Nel caso dei cardinali finiti ω forma una classe di rappresentanti canonici. Inoltre si ha che gli ordinamenti totali su di un insieme finito sono isomorfi. Lo scopo ora ` e introdurre una speciale classe di insiemi bene ordinati tale che per ogni insieme ben ordinato esiste ed ` e unico un ordinale che gli ` e isomorfo (ovvero un unico rappresentante canonico per ogni possibile tipo di buon ordine).

Definizione 7 Un insieme A si dice ordinale se 1. (A, ∈) ` e un insieme bene ordinato

2. a ⁰ ∈ a ∈ A ⇒ a ⁰ ∈ A (A ` e un insieme transitivo) 2’. a ∈ A ⇒ A a = a

Esercizio 7 • Ogni A ∈ ω soddisfa la (1)

• Ogni A ∈ ω infinito ` e tale che (A, ∈) ∼ = (ω, ∈)

• (2)⇔(2’)

Proposizione 4 Sia α un ordinale

1. Se x ∈ α non ` e il massimo, allora ˆ x ∈ α ¹ 2. α 6∈ α

3. ˆ α ` e un ordinale

4. Se β ∈ α, allora β ` e un ordinale 5. Se α, β sono ordinali allora

α ∈ β ⇔ α ` e un segmento iniziale proprio di β ⇔ α ⊂ β 6. Se α, β sono ordinali e α ∼ = β allora α = β

7. Se α, β sono ordinali, vale una e una sola:

α = β ∨ α ∈ β ∨ β ∈ α Dim:

1. Poich` e α ` e transitivo abbiamo che x, {x} ⊆ α perci` o anche la loro unione

`

e un sottoinsieme di α. Inoltre deve essere un sottoinsieme proprio perch` e se fosse ˆ x = α ⇒ x = max ˆ x = max α assurdo. Quindi x ⊂ α ⇒ x ∈ α 2. Se fosse α ∈ α, visto che (α, ∈) ` e ben ordinato, in particolare ` e ordinato e

perci` o ∀x ∈ α x 6∈ x ⇒ α 6∈ α, assurdo.

1

Ricordiamo che per ogni insieme x, ˆ x := x ∪ {x}

3. Notiamo che ˆ α ` e transitivo. Infatti se x ∈ y ∈ ˆ α allora ci sono due casi:

y ∈ α ⇒ (x ∈ y ∈ α) ⇒ x ∈ α ⇒ x ∈ ˆ α y = α ⇒ (x ∈ y = α) ⇒ x ∈ α ⇒ x ∈ ˆ α

Inoltre ˆ α ` e banalmente ordinato da ∈ con α come elemento massimo.

4. • β ` e transitivo

Siano x ∈ y ∈ β, ma allora x ∈ y ∈ β ∈ α ⇒ x, y, β ∈ α, e quindi poich` e (α, ∈) ` e un ordinamento x ∈ y ∈ β ⇒ x ∈ β.

• β ∈ α ⇒ β ⊂ α e quindi ` e ordinato perch` e sottoinsieme di un insieme bene ordinato.

5. Per la transitivit` a di β, α ∈ β ⇒ α ⊂ β e inoltre poich` e α ` e transitivo ` e un segmento iniziale. Inoltre ` e un segmento iniziale proprio perch` e α ∈ β ma β 6∈ β.

Resta da vedere solo α ⊂ β ⇒ α ∈ β. Sia quindi α ⊂ β. Posto γ = min(β\α) allora γ = β γ perci` o

x ∈ β γ ⇒ x ∈ β ∧ x < γ ⇒ x ∈ α per la definizione di γ, e quindi γ ⊆ α

x ∈ α ⇒ x ∈ β e inoltre x < γ ⇒ x ∈ γ

perch` e se fosse γ < x ∈ α per la transitivit` a di α avremmo γ ∈ α assurdo.

Quindi γ ⊇ α ⇒ α = γ ∈ β.

6. Sia ψ : α → β isomorfismo. Basta mostrare che ∀x ∈ α ψ(x) = x. Se cos`ı non fosse, prendiamo ξ = min{x ∈ α | ψ(x) 6= x}. Allora avremmo un isomorfismo ψ _|α

: α ξ → β _ψ(ξ) , cio` e un isomorfismo ϕ : ξ → ψ(ξ) in cui ϕ(x) = x per tutti gli x ∈ ξ, cio` e ξ = ψ(ξ), contro l’ipotesi ξ 6= ψ(ξ).

7. Esercizio CVD

Esercizio 8 1. X insieme di ordinali ` e un ordinale se e solo se ` e transitivo 2. X insieme di ordinali, S

x∈X x ` e un ordinale e sup X = S

x∈X x 3. X insieme di ordinali, T

x∈X x ` e un ordinale e min X = T

x∈X x

4. Se α ` e un ordinale allora α + 1 := α ∪ {α} ` e un ordinale ed ` e il pi` u piccolo tra gli ordinali maggiori di α.

Teorema 5 Per ogni insieme ben ordinato (A, <) esiste un unico ordinale α

tale che (A, <) ∼ = (α, ∈).

Dim:

Unicit` a: Se (A, <) ∼ = (α, ∈) e (A, <) ∼ = (β, ∈) segue che α ∼ = β ⇒ α = β per la proposizione precedente.

Esistenza: Sia X := {x ∈ A | esiste un ordinale β tale che A x ∼ = β}. X ` e non vuoto poich` e A 0

∼ = ∅. Notiamo che X ` e un segmento iniziale di A. Infatti sia y < x ∈ X. Allora esiste φ : A _x → α, α ordinale. Ma allora φ _|A

: A _y → α _φ(y) = φ(y) ` e un isomorfismo da A _y a un ordinale, quindi y ∈ X. Quindi

∀x ∈ X esiste ed `e unico un ordinale β ^(x) tale che A _x ∼ = β ^(x) . Quindi esiste una funzione θ che manda x → β ^(x) .

N.B.: L’esistenza di θ non ` e garantita dagli assiomi dati finora. Infatti servirebbe che {β <sup>(x)</sup> | x ∈ X} fosse un insieme. L’esistenza di questo insieme ` e garantita dall’assioma di rimpiazzamento.

Notiamo che Im θ ` e un insieme transitivo di ordinali, e quindi un ordinale.

Infatti se α ∈ β ^(x) ∈ Im θ esiste un ϕ : β ^(x) → A x e, restringendo, ϕ _|β

α

≡α : α → ϕ(α) ≡ A _ϕ(α)

` e un isomorfismo. Quindi α ∼ = A ϕ(α) e dunque α = θ(ϕ(α)) ∈ Im θ. Sia quindi γ = Im θ ordinale.

Vediamo ora che θ : X → γ rispetta l’ordine, e che quindi ` e un isomorfismo.

Siano y < x Allora β ⁽ y) ∼ = A y che ` e un segmento iniziale proprio di A x ∼ = β <sup>(x)</sup> . Quindi β <sup>(y)</sup> ` e congruo ad un segmento iniziale proprio di β ^(x) , ma siccome sono ordinali, β ^(y) ∈ β ^(x) . Quindi esiste

θ : X → γ isomorfismo.

Tutto quello che resta da vedere ` e che X = A. Per assurdo sia X = A <sub>ξ</sub> segmento iniziale proprio. Ma allora A <sub>ξ</sub> ∼ = γ sotto l’isomorfismo θ, quindi ξ ∈ X = A <sub>ξ</sub> , assurdo perch` e sarebbe ξ < ξ. CVD

5 Insiemi e classi

In ZFC esistono solo insiemi, tuttavia possiamo parlare di “collezioni” di oggetti che non possono essere insiemi. Ad esempio la classe universale

V = {x | x = x}

NON ` e un insieme. Infatti se V fosse un insieme, lo sarebbe anche P(V), ma allora P(V) ⊆ V e quindi esisterebbe una funzione iniettiva f : P(V) → V, assurdo.

Tuttavia di queste “collezioni” possiamo parlare, ad esempio:

R = {x | x 6∈ x} classe di Russel, non ` e un insieme

ON = {α | α ` e un ordinale} non ` e un insieme (vedi oltre, paradosso di Burali-Forti)

Data una formula σ(x) (eventualmente con parametri) denotiamo con {x | σ(x)}

la classe degli elementi che la soddisfano. Una classe che non ` e un insieme si dice classe propria. Osserviamo che la propriet` a di essere una classe non ` e esprimibile, cio` e non esiste la classe delle classi (cio` e siamo in un metalinguaggio.

5.1 Assioma di rimpiazzamento e classi

Definizione 8 Una funzione-classe ` e una classe che ` e di tipo “funzionale”, cio` e una classe F tale che (a, b), (a, b <sup>0</sup> ) ∈ F ⇒ b = b <sup>0</sup> . Cio` e F = {(x, y) | φ(x, y)}

dove

∀x, y, y ⁰ (φ(x, y) ∧ φ(x, y ⁰ ) ⇒ y = y ⁰

N.B. se sapessi che x, y variano in certi insiemi, dall’assioma di separazione ne seguirebbe che F non `e una classe propria.

Notazione:

• Se C = {x | ϕ(x)} (classe estrusione di ϕ) allora “x ∈ C” significa ϕ(x).

• A × B = {(a, b) | a ∈ A ∧ b ∈ B}

• Se F `e una funzione-classe, allora

dom F = {x | ∃y : (x, y) ∈ F}

Im F = {y | ∃x : (x, y) ∈ F}

F(a) denota l’unico b tale che (a, b) ∈ F.

Esempio 3 1. x → P(x) ` e una “funzione-classe”

2. Funzione classe singoletto F(x) = {x}

3. x → β ^(x) nella dimostrazione precedente Assioma di rimpiazzamento

Se F `e una funzione classe e A `e un insieme allora F[A] = {F(a) | a ∈ A} `e un insieme.

(Equivalentemente F |A = {(a, b) ∈ F | a ∈ A} `e una funzione).

Esercizio 9 Preso l’insieme ω, per rimpiazzamento {{u} | u ∈ ω}

` e un insieme, con la funzione classe singoletto. In realt` a questo insieme esisteva

gi` a per separazione di P(ω).

6 Alcuni esercizi

Esercizio 10 α, β ordinali, allora vale una ed una sola tra α = β, α ∈ β, β ∈ α

Dim:

Segue immediatamente dalla tricotomia tra buoni ordini e dalle propriet` a degli ordinali. CVD

Esercizio 11 Se X ` e un insieme di ordinali allora T X `e un ordinale e T X = min X

Dim:

T X `e un ordinale perch`e

• T X `e transitivo. y ∈ ξ ∈ T X ⇒ ∀x ∈ X y ∈ ξ ∈ x Ma poich`e gli elementi di X sono transitivi ∀x ∈ X y ∈ x ⇒ y ∈ T X.

• T X `e totalmente ordinato da ∈. Siano y, z ∈ T X Fissiamo x 0 ∈ X, allora y, z ∈ x 0 . Ma poich` e x 0 ` e un ordinale ne segue che

y = z ∨ y ∈ z ∨ z ∈ y

• T X `e bene ordinato. Come prima

Inoltre γ = T X `e minimo perch`e ∀x ∈ X γ ≤ x ⇒ γ ⊆ min X ma ∀x ∈ X min X ⊆ x ⇒ min X ⊆ X = γ CVD

Esercizio 12 Sia X un insieme di ordinali. Allora X ` e un ordinale ⇔ X ` e transitivo Dim:

(⇒) Per la definizione di ordinale

(⇐) Notiamo che X ` e totalmente ordinato da ∈ per la tricotomia degli ordinali.

Inoltre dall’esercizio precedente segue che, se Γ ⊆ X allora min Γ = T Γ, quindi X ` e bene ordinato. Inoltre ` e tranisitivo per ipotesi, quindi ` e un ordinale. CVD Esercizio 13 Dato X un insieme di ordinali allora S X `e un ordinale e sup X = S X.

Dim:

• S X `e transitivo. Infatti se z ∈ y ∈ S X vuol dire che ∃x ∈ X z ∈ y ∈ x ⇒ z ∈ X ⇒ z ∈ S X perch`e x `e un ordinale.

• S X `e un ordinale per l’esercizio precedente (`e unione di ordinali, quindi unione di insiemi di ordinali, quindi insieme di ordinali). Poniamo Γ :=

S X

• ∀x ∈ X Γ ⊇ x ⇒ X ` e maggiorante

• Sia δ ordinale maggiorante di X, cio` e

∀x ∈ X δ ⊇ x ⇒ δ ⊇ [ X = Γ Quindi Γ ` e il minimo dei maggioranti. CVD

Esempio 4 Sia X = {0, 1, 2, . . . } l’insieme dei naturali di Von Neumann. Al- lora S X = ω = sup X ma ω 6∈ X quindi ω non `e max.

Esercizio 14 L’unione di insiemi totalmente ordinati ` e ordinata?

NO: Infatti se prendiamo {1, 2} con l’ordinamento 1 < 2 e {1, 2} con l’ordinamento 2 < 1 la loro unione non ` e ordinata dall’unione degli ordini (che non ` e un ordine).

A parte questo caso banale consideriamo due insiemi ordinati (A, < _A ) e (B, < B ) compatibili, tali cio` e che

∀x, y ∈ A ∩ B ⇒ (x < A y ⇔ x < B y)

Esercizio 15 Sia F = {(A i , < i )} i∈I una famiglia di ordini compatibili. Allora

[ F = [

i∈I

A _i , [

i∈I

< _i

!

` e un ordine.

Definizione 9 Un insieme ordinato (A, < A ) si dice sottoinsieme di un altro insieme ordinato (B, < B ) se A ⊆ B e

< A =< B ∩(A × A) cio` e se l’ordine di A ` e quello indotto da (B, < B ).

Esercizio 16 Se F ` e una famiglia di ordini totali uno sottoinsieme dell’altro, allora S F (definito come sopra) `e un ordine totale.

Vale la stessa propriet` a con i buoni ordini?

Dim:

1. (Esercizio)

2. NO. Infatto sia A n := {−n, −n + 1, . . . , −1, 0} con l’ordine indotto da Z.

Allora tutti gli A n sono bene ordinati ma [

n∈N

A n = {. . . , −2, −1, 0} non ` e

bene ordinato.

CVD

Un unione di buoni ordini non ` e necessariamente un buon ordine perch` e gli ordini in pi` u possono venir aggiunti “a sinistra” generando cos`ı una catena discendente. Questo non accade, ad esempio, con gli ordinali, perch` e gli elementi aggiuntivi vengono aggiunti sempre “a destra”

Esercizio 17 Sia F una famiglia di buoni ordini che sono l’uno un segmento iniziale dell’altro, allora S F `e un buon ordine.

Dim:

Per assurdo esista una catena discendente x ₀ > x ₁ > x ₂ > . . . . Allora pren- diamo A ₀ ∈ F tale che x ₀ ∈ A ₀ . Ma allora prendiamo per ogni i A _i tale che x _i ∈ A _i . Se A _i ⊆ A ₀ si ha evidentemente che x _i ∈ A ₀ . Supponiamo invece che A 0 sia segmento iniziale di A i . Allora x i < x 0 deve appartenere ugualmente a A 0 . Quindi, riassumendo ∀i ∈ N x ⁱ ∈ A 0 , cio` e esiste una catena discendente in A 0 , assurdo perch` e A 0 ` e bene ordinato. CVD

Esercizio 18 Sia (A, <) un insieme ordinato infinito. Allora (A, <) ` e isomorfo a ω ⇔ ∀X ⊆ A infinito non ha max Dim:

(⇒) Sia X ⊆ A infinito. Se X avesse un massimo, sia Y il corrispondente sottoinsieme di ω. Allora anche Y ha massimo, sia max Y = n. Ma allora Y ⊆ {0, 1, . . . , n}, assurdo perch` e Y ` e infinito.

(⇐) Notiamo intanto che A ` e bene ordinato perch` e se ci fosse una catena discendente sarebbe un sottoinsieme infinito di A con un massimo.Allora per la tricotomia tra buoni ordini, segue che o A ∼ = ω o uno dei due ` e isomorfo a un segmento iniziale dell’altro. Notiamo che A non pu` o essere isomorfo a un segmento iniziale di ω perch` e tutti i segmenti iniziali di ω sono finiti, mentre A ` e infinito. Supponiamo per assurdo che esista a ∈ A tale che ω ∼ = A a . Ma allora A a ∪ {a} ` e un sottoinsieme di A infinito (contiene ω) che ha massimo (a), assurdo. Quindi deve essere A ∼ = ω. CVD

Esercizio 19 (Q, <) `e universale tra gli insiemi ordinati al pi` u numerabili, cio` e per ogni (A, <) insieme ordinato con |A| ≤ ℵ 0 (A, <) ` e isomorfo a un sottoinsieme di Q.

Dim:

Se A ` e finito ` e ovvio per induzione. Supponiamo |A| = ℵ ₀ . Allora posso enumerare gli elementi di A, cio` e trovare n → a _n biunivoca da ω ad A. Allora definiamo per ricorsione una funzione θ : A → Q

θ(a 0 ) = 0

θ(a n+1 ) =



 

 

 

 

min{θ(a ₀ ), . . . , θ(a _n )} se a _n+1 < a ₀ , . . . , a _n max{θ(a 0 ), . . . , θ(a n )} se a n+1 > a 0 , . . . , a n

a

+a

2 se a _i = min{a _k | a _k > a _n+1 },

a j = max{a k | a k < a n+1 }

E chiaro dalla definizione di θ che Im θ ∼ ` = A, cio` e che θ ` e un isomorfismo. CVD Esercizio 20 La propriet` a tricotomica vale anche tra insiemi ordinati?

Dim:

NO. Ad esempio N e Z. CVD

Proposizione 5 Sia X ⊂ R bene ordinato con l’ordinamento indotto da R.

Allora |X| ≤ ℵ ₀ . Dim:

Sia X ⊂ R bene ordinato. Allora ∀x ∈ X eccettuato il massimo di X ∃x ⁺ successore di x. Allora

∀x ∈ X\{max X} ∃q x ∈ Q ∩ (x, x ⁺ )

per la densit` a di Q in R. Ma allora la funzione che associa x a q <sup>x</sup> ` e una funzione iniettiva da X\{max X} a Q, perci`o:

|X| ≤ |Q| = ℵ 0

CVD

NB: Nella “scelta” di q _x non ` e necessario usare l’assioma della scelta, perch` e basta fissare una numerazione di Q = {q 1 , q ₂ , . . . } e scegliere il q _x che cor- risponde al q _i con il minimo indice i per cui vale la propriet` a.

Definizione 10 Un insieme ordinato (X, <) ` e separabile se ha un sottoin- sieme denso numerabile

Esercizio 21 Sia (X, <) separabile. Allora |X| ≤ 2 ^ℵ

= c.

Dim:

Sia Y ⊆ X numerabile e denso. Consideriamo θ : X → P(Y ) che manda x in {y ∈ Y | y < x}. θ `e iniettiva perch` e Y ` e denso, da cui la tesi. CVD

Esercizio 22 Dati A, B ∈ F in(N) definiamo 1. A < B ⇔ ∃n ∈ B\A : A ∩ n = B ∩ n

Dimostrare che < ` e un ordine totale ma non un buon ordine (ordine della minima differenza)

2. A ≺ B ⇔ ∃n ∈ B\A : A ∩ {n + 1, n + 2, . . . } = B ∩ {n + 1, n + 2, . . . } Dimostrare che ≺ ` e un buon ordine e che (F in(N), ≺) ∼ = ω (ordine della massima differenza).

Esercizio 23 A, B ⊆ R ⁺ ben ordinati. Allora A + B = {a + b | a ∈ A, b ∈ B}

` e ben ordinato.

Esercizio 24 Se |X| ≤ ℵ 0 , allora R\X separabile.

7 Induzione e ricorsione transfinite

7.1 Ancora sull’assioma di rimpiazzamento

L’assioma di rimpiazzamento pu` o essere visto in questo modo: se ϕ(x, y) ` e una formula “funzionale”, cio` e tale che

∀ x∀y∀y ⁰ (ϕ(x, y) ∧ ϕ(x, y ⁰ ) ⇒ y = y ⁰

(detto in altri termini, per ogni x esiste al pi` u un unico y tale che ϕ(x, y)), allora il seguente ` e un assioma

∀A∃B(∀b b ∈ B ⇔ ∃a ∈ A ϕ(a, b))

Esercizio 25 1. Se F `e una funzione-classe iniettiva definita sulla classe propria A allora F[A] `e una classe propria

2. Se A `e una classe propria e B `e una classe tale che A ⊆ B allora B `e una classe propria.

Esercizio 26 Per ogni A 6= ∅ {X | |X| = |A|} ` e una classe propria.

Dim:

Come classi proprie che conosciamo a cui vogliamo ricondurci (vedi es. prece- dente) abbiamo

V = {x | x = x}

R = {x | x 6∈ x}

ON = {α | α ordinale }

Basta trovare una funzione-classe iniettiva F : V → A = {x | |x| = |A|}. Ad esempio prendiamo ˜ a ∈ A e prendiamo ∗ tale che ∀ξ ∈ A (∗, ξ) 6∈ A. Allora definiamo la funzione classe tale che:

X − → (A\{˜ ^F a}) ∪ {(∗, X)}

Notiamo che poich` e A ` e un insieme ha senso la scelta di ∗ e che F[V] ⊆ A, Inoltre F `e chiaramente iniettiva, da cui per il punto precedente A `e una classe propria. CVD

7.2 Funzione-classe di Hartogs

Definizione 11 Per ogni insieme A, definiamo la funzione-classe di Hartogs come

H(A) = {α ordinale | |α| ≤ |A|}

1. H(A) `e un insieme Dim:

B := {(X, < X ) bene ordinato | X ⊆ A} ` e un insieme? S`ı per l’assioma di separazione perch´ e:

B ⊆ P(A) × P(A × A)

Consideriamo la funzione classe F che associa ad ogni buon ordine l’unico ordinale ad esso isomorfo. Osserviamo che per l’assioma di rimpiazza- mento F[B] `e un insieme. Inoltre vale

F[B] = H(A) Infatti

(⊆) (X, < X ) ∈ B e F[(X, < ^X )] = α, allora esiste θ : (X, < X ) → α isomor- fismo. In particolare θ ` e una bigezione, per cui |α| = |X| ≤ |A| perch` e X ⊆ A. Quindi α ∈ H(A).

(⊇) Sia α ∈ H(A) allora esiste f : α → A iniettiva. Prendiamo X = Im f ⊆ A. Poich` e α ` e bene ordinato anche X ` e bene ordinabile con l’ordinamento indotto da f . Quindi, posto < X l’ordinamento indotto, (X, < X ) ∈ B e α ∈ F(X, < ^X ).

2. Dal punto precedente segue che A → H(A) `e una funzione classe.

3. H(A) `e un ordinale Dim:

Visto che si tratta di un insieme di ordinali, basta dimostrare che ` e tran- sitivo, cio` e che

β ∈ α ∈ H(A) ⇒ β ∈ H(A)

Per ipotesi esiste f : α → A iniettiva. Allora β ∈ α ⇒ β ⊂ α e perci` o f <sub>|β</sub> : β → A ` e iniettiva, e quindi |β| ≤ |A| ⇒ β ∈ H(A) CVD

Definizione 12 Un ordinale α si dice cardinale se ` e iniziale, cio` e se

∀β ∈ α |β| < |α|

4. H(A) `e un cardinale.

Dim:

Altrimenti esiste α ∈ H(A) tale che |α| = |H(A)|. Ma allora esiste f : H(A) → A iniettiva e g : α → H(A) biunivoca, quindi esiste f ◦ g ⁻¹ : H(A) → A iniettiva, dunque H(A) ∈ H(A), assurdo perch` e H(A) `e un ordinale. CVD

5. |H(A)| 6≤ |A| cio`e 6 ∃f : H(A) → A iniettiva. Notare che questo non vuol dire che |H(A)| > |A| perch`e la tricotomia tra cardinalit`a dipende dalla scelta.

Dim:

Se per assurdo esistesse f : H(A) → A iniettiva, allora H(A) ∈ H(A),

assurdo. CVD

6. Se α ` e un ordinale, H(α) `e il pi` u piccolo ordinale di cardinalit` a pi` u grande di α. Dim:

Notiamo che |H(α)| > |α| perch`e la tricotomia vale tra gli ordinali. Se H(α) non fosse il pi` u piccolo tra gli ordinali con |β| > |α|, allora esisterebbe β ∈ H(A) con |α| < |β|, assurdo per la definizione di H. CVD

Esempio 5 • H(100) = 101

• H(ω) = {β ordinale | β finito o numerabile } `e il pi`u piccolo cardinale non numerabile. Si indica con ω ₁ o ℵ ₁ .

7.3 La sequenza degli Aleph

( ℵ 0 = ω ℵ _n+1 = H(ℵ n ) sono cardinali ℵ ₀ < ℵ ₁ < · · · < ℵ _n < . . . .

E la funzione ℵ : N →? esiste per ricorsione numerabile pi` u rimpiazzamento.

Osservazione 7 Gli ordinali non nulli sono di due tipi ben distinti: i successori (cio` e quelli che hanno max, cio` e quelli della forma α = β + 1 = β ∪ {β}), e gli ordinali limite (quelli che non hanno max, cio` e quelli tali che α = S α).

7.4 Induzione transfinita

Se P ` e una propriet` a-formula (eventualmente con parametri) e α ` e un ordinale I Forma:

( P (0)

(∀β < α P (β)) ⇒ P (α) ⇒ P (α) II Forma:



 

  P (0)

P (β) ⇒ P (β + 1) (caso successore

∀β < λ P (β) ⇒ P (λ) (caso limite

⇒ P (α)

Proposizione 6 I Forma ⇔ II Forma, ed entrambe valgono.

Dim:

1. Per assurdo supponiamo che l’insieme Γ = {β ∈ α | P (β) non vale } sia diverso dal vuoto. Allora esiste γ = min Γ. Ma allora:

• γ 6= 0 perch`e P (0) vale.

• Se γ > 0, visto che γ ` e il minimo per cui non vale P , vale P (δ) per tutti i δ < γ. Ma allora per ipotesi vale anche P (γ). Assurdo.

2. Per la II forma si procede analogamente

3. Il fatto che sono equivalenti segue perch` e sono entrambe propriet` a vere.

L’induzione transfinita pu` o essere facilmente generalizzata da un ordinale gener- ico all’intera classe degli ordinali ON.

( P (0)

∀β(∀γ < β P (γ)) ⇒ P (β) ⇒ ∀α ∈ ON P (α) Dim:

Per assurdo se esistesse un ordinale α tale che P (α) non vale, consideriamo ξ = min{γ ≤ α | P (γ) non vale } e procediamo come nella dimostrazione precedente.

N.B. Il minimo ` e fatto dentro α, che ` e un insieme, e non nella classe propria ON. CVD

7.5 Ricorsione transfinita

Osservazione 8 Vogliamo ora procedere con alcuni esempi di ricorsione trans- finita che verranno giustificate dal teorema di ricorsione transfinita.

Definizione 13 Per ogni ordinale α, definisco α + ξ prendendo



 

 

α + 0 = α

α + (β + 1) = (α + β) + 1 α + λ = S

γ<λ α + γ

N.B. Con gli ordinali S ⇔ sup e per δ + 1 si intende δ ∪ {δ}.

Esercizio 27

ω + ω = [

n<ω

ω + n

Il teorema di ricorsione transfinita ci garantisce che per ogni alpha esiste una funzione classe F ^α tale che dom F ^α = ON e inoltre:



 

 

F α (0) = α

F α (β + 1) = F α (β) + 1 F α (λ) = S

γ<λ F α (γ) Un’altra definizione possibile ` e il prodotto tra ordinali:

Definizione 14



 

 

α · 0 = 0

α · (β + 1) = (α · β) + α α · λ = S

γ<λ α · γ

Esercizio 28 Siano ⊕, ⊗ le operazioni tra buoni ordini. Allora

1. α + β ∼ = α ⊕ β 2. α · β ∼ = α ⊗ β Esercizio 29

(ω + 3) + ω = ω + ω

Infatti per definizione (ω + 3) + ω = sup _n∈ω ω + 3 + n = sup _k∈ω ω + k = ω + ω.

Proposizione 7 Vale la propriet` a associativa dell’addizione Dim:

Infatti vale α ⊕ (β ⊕ γ) ∼ = (α ⊕ β) ⊕ γ e dall’esercizio precedente segue la tesi.

CVD

Esercizio 30 (ω + 3) · ω = ω · ω

Proposizione 8 Vale la distributivit` a a destra (ma non vale a sinistra) α · (β + γ) = α · β + α · γ

Dim:

Segue dall’esercizio precedente e dall’analoga propriet` a di ⊕, ⊗. CVD Per un esempio in cui non vale la distributivit` a a sinistra

ω · ω = (ω + 3) · ω 6= ω · ω + 3 · ω Esercizio 31 (ω · 7) · ω = ω · ω

ω ² · (ω · 7 + 25) = ω ³ · 7 + ω ² · 25

Proposizione 9 (Differenza a destra) Se α < β allora esiste un unico ξ tale che

α + ξ = β Dim:

Esistono γ tali che α + γ > β (ad esempio α + (β + 1) > β). Prendiamo η = min{γ | α + γ > β}

(il minimo si pu` o fare all’interno di un opportuno insieme, ad es β + 1). Allora η ` e un successore. Infatti

• η 6= 0 perch` e α + 0 = α < β.

• η non `e limite, perch` e se lo fosse allora α + η = sup _γ<η α + γ > β, per cui esisterebbe γ < η per cui α + γ > β contro la minimalit` a di η.

Quindi η = ξ + 1 per cui α + ξ ≤ β < α + ξ + 1 ⇒ β = α + ξ.

Inoltre lasciamo per esercizio da dimostrare che ξ < ξ ⁰ ⇒ α + ξ < α + ξ ⁰ , da cui

segue l’unicit` a. CVD

Teorema 6 Divisione euclidea Se α > β ≥ 1, allora∃!γ, ρ tali che α = β · γ + ρ con ρ < β

Esercizio 32 ω ² + ω · 4 + 3 diviso per ω + 5

(ω + 5) · ω = ω ² < ω ² + ω · 4 + 3 (ω + 5) · (ω + 1) = ω ² + ω + 5 < ω ² + ω · 4 + 3 (ω + 5) · (ω + 3) = ω ² + ω · 3 + 5 < ω ² + ω · 4 + 3 (ω + 5) · (ω + 4) = ω ² + ω · 4 + 5 > ω ² + ω · 4 + 3

Quindi il quoziente ` e ω + 3. Cerchiamo il resto, ovvero l’unico ξ tale che ω ² + ω · 3 + 5 + ξ = ω ² + ω · 4 + 3

Basta prendere ξ = ω + 3 Il resto allora ` e ω + 3 < ω + 5. Dim:

Esistono δ tali che β · δ > α (ad esempio α + 1).

Esercizio 33 1. ξ ≤ ξ ⁰ ⇒ ∀η ξ · η ≤ ξ ⁰ · η 2. ξ ≤ ξ ⁰ ⇒ ∀η η · ξ ≤ η · ξ ⁰

Quindi possiamo prendere

η = min{ξ | β · ξ > α}

Ora, η ` e un successore. Infatti

• η 6= 0 perch`e β · 0 = 0 ≤ α.

• Se η fosse limite allora esisterebbe ξ < η tale che β · ξ > α, contro la minimalit` a di η.

Allora η = γ + 1 e β · γ ≤ α < β · (γ + 1) per cui γ ` e il qoziente. Il resto ρ ` e quell’unico ordinale tale che β · γ + ρ = α (Nota che ρ < β, se no α = β · γ + ρ ≥ β(γ + 1) > α, assurdo).

Unicit` a. Siano α = β · γ + ρ = β · γ <sup>0</sup> + ρ <sup>0</sup> . Senza perdita di generalit` a γ < γ ⁰ , per cui γ + 1 ≤ γ ⁰ . Allora

α = β · γ + ρ < β · γ + β = β · (γ + 1) ≤ β · γ ⁰ ≤ β · γ ⁰ + ρ ⁰ = α Assurdo. L’unicit` a di ρ segue dall’unicit` a della differenza.CVD

Esercizio 34 Dividere ω ² per ω · 5 + 7 e dividere ω per 7.

Definizione 15 Potenza di ordinali



 

  α ⁰ = 1

α ^β+1 = (α ^β ) · α α ^λ = S

γ<λ α ^γ

Esercizio 35 α ^β ∼ = Exp(α, β) dove Exp ` e l’esponenziale di buoni ordini.

N.B. L’esponenziale di ordinali ` e molto diverso come operazione dall’esponenziale

dei corrispondenti cardinali. Infatti 2 ^ω = ω mentre 2 ^ℵ

> ℵ 0

8 Alcuni esercizi

Esercizio 36 α + β ∼ = α ⊕ β

Per induzione transfinita dimostriamo che la seguente propriet` a con parametro α vale per tutti i β ∈ ON.

P (β) : α + β ∼ = α ⊕ β

P (0) ` e chiaramente vera, infatti α ⊕ 0 ` e per definizione isomorfo a α = α + 0.

P (β) ⇒ P (β + 1): Per ipotesi induttiva α + β ∼ = α ⊕ β. ` E immediato vedere che α + (β + 1) = (α + β) + 1 ∼ = (α + β) ⊕ 1 ∼ = (α ⊕ β) ⊕ 1

Ma per la definizione di β + 1 si vede immediatamente che α ⊕ (β + 1) ∼ = (α ⊕ β) ⊕ 1 P (λ): Abbiamo che α + λ = S

γ<λ α + γ Ma per ipotesi induttiva, per ogni γ < λ esiste un isomorfismo ψ γ : α + γ → α ⊕ γ. L’idea ` e quella di dimostrare che ψ = S

γ<λ ψ _γ ` e un isomorfismo tra α + λ e α ⊕ λ. Notiamo che se λ > γ ⁰ > γ allora

ψ _α+γ

|α+γ = ψ _α+γ

perch` e l’isomorfismo tra due insiemi bene ordinati ` e necessariamente unico.

Quindi

ψ = [

γ<λ

ψ _γ

` e una funzione biunivoca da α + λ a S

γ<λ α ⊕ γ = α ⊕ λ. Vediamo ora che ψ preserva l’ordine. Infatti se

x, y ∈ α + λ = [

γ<λ

α + γ allora ∃γ ₁ , γ ₂ < λ x ∈ α + γ ₁ , y ∈ α + γ ₂

Ma, ponendo γ = max(γ 1 , γ 2 ) allora x, y ∈ γ e ψ(x) = ψ γ (x), ψ(y) = ψ γ (y) (deve essere cos`ı perch` e ψ _|γ ` e un isomorfismo tra α + γ e α ⊕ γ, e l’isomorfismo tra due insiemi ordinati ` e necessariamente unico). Perci` o, visto che ψ γ ` e un isomorfismo abbiamo la tesi. CVD

Esercizio 37 α ^ξ+η = α ^ξ · α ^η Per induzione transfinita su η.

η = 0: α ^ξ+0 = α ^ξ = α ^ξ · 1 = α ^ξ · α ⁰

η ⇒ η + 1: Per ipotesi induttiva sappiamo che α ^ξ+η = α ^ξ · α ^η α ^ξ+(η+1) = α ^(ξ+η)+1 = α ^ξ+η · α = α ^ξ · α ^η · α = α ^ξ · α ^η+1 η limite:

α ^ξ · α ^λ = α ^ξ · [

γ<λ

α ^γ = α ^ξ · sup

γ<λ

α ^γ = sup

γ<λ

α ^ξ · α ^γ = sup

γ<λ

α ^ξ+γ = sup

γ<ξ+λ

α ^γ = α ^ξ+λ

CVD

Esercizio 38 Siano A, B ⊆ R ⁺ bene ordinati. Allora A + B := {a + b | a ∈ A, b ∈ B}

` e bene ordinato Dim:

Per assurdo esista una catena discendente della forma

a 0 + b 0 > a 1 + b 1 > a 2 + b 2 + · · · > a n + b n > . . .

Se sapessi che a ₀ ≤ a ₁ ≤ a ₂ ≤ . . . potrei dedurre che b ₀ > b ₁ > . . . e avrei concluso per assurdo (infatti B ` e bene ordinato). Purtroppo questo non ` e vero in generale. Tuttavia notiamo che basterebbe dimostrare l’esistenza di una sottosuccessione a n

≤ a n

≤ . . . . E infatti una sottosuccessione di quel tipo si costruisce facilmente in questo modo

a _n

= min{a _n } _n∈N e a _n

= min{a _n | n > n _i } CVD

Esercizio 39 Sia α > 0. Allora sono equivalenti

• α ` e additivamente chiuso, cio` e

∀β, γ < α β + γ < α

• ∀β < α β + α = α

• Esiste un δ tale che α = ω ^δ

8.1 Gerarchia di Von Neumann

Definiamo per ogni ordinale α un insieme V α tale che



 

  V 0 = ∅ V _α+1 = P(V _α ) V λ = S

γ<λ V λ

Ad esempio V ₀ = ∅, V ₁ = P(∅) = {∅}, V ₂ = {∅, {∅}}, . . . Notiamo che V _ω sod- disfa tutti gli assiomi della teoria di Zermelo-Frankael tranne quello dell’infinito.

La gerarchia di Von Neumann ` e strettamente collegata all’assioma di Fon- dazione, che dice che ogni insieme ` e ben fondato. Un insieme a si dice ben fondato se non esiste una catena infinita a 3 a 1 3 a 2 3 . . . . Si pu` o dimostrare che la classe degli insiemi ben fondati ` e

[

α∈ON

V _α

cio` e la classe degli x tali che esiste un ordinale α tale che x ∈ V α .

9 Ancora sulla ricorsione

Teorema 7 (Ricorsione Transfinita I) Sia data una funzione classe G e un elemento a. Allora esiste una funzione-classe F tale che

dom F = ON e F(0) = a, F(α) = G(F |α ) Esempio 6 Consideriamo la funzione classe G tale che

G(x) =



 

 

∅ se x = ∅

P(f (α)) se x = f ` e una funzione con dominio un ordinale successore α + 1 S

γ<λ f (λ) se x = f ` e una funzione con dominio un ordinale limite λ Allora il nostro teorema ci dice che esite un unica F che ha per dominio gli ordinali e tale che F(0) = ∅, F(α) = G(F |α ). Se introduciamo la notazione F(α) = V α vediamo che ` e giustificata la definizione precedente della gerarchia di Von Neumann.

Teorema 8 (Ricorsione Transfinita II) Siano date due funzioni-classi G ¹ , G ² e un elemento α. Allora esiste ed ` e unica una funzione classe F con dom F = ON e tale che



 

 

F (0) = α

F (α + 1) = G ¹ (F(α)) F (λ) = G 2 (F |λ )

Ad esempio, nel caso precedente possiamo porre G ¹ (x) = P(x) e G ² (x) = ( S

γ<λ f (γ) se x ` e una funzione con dominio un ordinale limite λ

∗ altrimenti

Teorema 9 (Ricorsione Transfinita III) Siano dati un ordinale α, un elemento a e una funzione-classe G con dom G = {f | dom f ∈ α}. Allora esiste un unica funzione F con dominio α tale che F (0) = a e che ∀γ < α F (γ) = G(F |α ).

Un altro esempio pu` o essere



 

 

F (0) = 0

F (α + 1) = F (α) · (α + 1) F (λ) = S

γ<λ F (γ) Dim:

(Teorema di Ricorsione Transfinita I)

Definiamo α-approssimazione una funzione f tale che dom f = α+1 = {0, 1, . . . , α}

tale che f (0) = a e f (β) = G(f |β ) per ogni β ≤ α. Dimostriamo che

1. se f ` e una α-approssimazione e g ` e una β-approssimazione e α < β allora f ⊆ g (cio` e g _|α+1 = f ).

2. Per ogni ordinale α esiste una α-approssimazione.

1. Dimostriamo per induzione transfinita su β che per ogni β esiste al pi` u un’unica β-approssimazione.

Per β = 0 ` e vero, perch` e l’unica β-approssimazione possibile ` e {(0, a)}.

Se ` e vero per β allora siano f, g due β+1-approssimazioni. Allora f _|β+1 , g _|β+1 sono β approssimazioni, per cui per ipotesi induttiva sono uguali. Ma al- lora

f (β + 1) = G(f |β+1 ) = G(g |β+1 ) = g(β + 1) Quindi f = g.

Supponiamo ora β = λ ordinale limite e siano f, g due λ-approssimazioni.

Ma allora per ogni γ < λ f _|γ = g| γ per ipotesi induttiva (sono due γ- approssimazioni), quindi in particolare per ogni γ < λ f (γ) = g(γ) quindi f _|λ = g _|λ . Ma allora come sopra f (λ) = G(f |λ ) = G(g |λ ) = g(λ).

2. Dimostriamo ora che per ogni α esiste un α-approssimazione Se α = 0 {(0, a)} ` e una 0-approssimazione.

Supponiamolo vero per α allora esiste una α-approssimazione f . Quindi g = f ∪ G(f )

`

e una α + 1 approssimazione.

Supponiamo infine che α = λ ordinale limite. Per ipotesi induttiva e per quanto dimostrato prima per ogni γ < λ esiste ed ` unica f _γ γ-approssimazione.

Se prendo g = S

γ<λ f _γ ho una “quasi” λ-approssimazione. Infatti dom g = λ e non λ + 1. Ma se prendo

f = g ∪ {(λ, G(g))}

ottengo una λ approssimazione.

Infine per ottenere la funzione-classe della tesi basta fissare F(α) = f (α) dove f ` e l’unica α-approssimazione. CVD

9.1 La sequenza degli aleph



 

 

ℵ ₀ = ω

ℵ α+1 = H(ℵ ^α ) = {β ∈ ON | |β| ≤ |ℵ ^α |}

ℵ _λ = S

γ<λ ℵ _γ

Ricordiamoci che per ogni insieme A H(A) `e un cardinale (cio`e un ordinale tale che ogni ordinale precedente ha una cardinalit` a strettamente inferiore alla sua).

Dimostriamo ora che

Proposizione 10 Tutti i cardinali sono aleph, cio` e per ogni cardinale κ esiste

α ordinale tale che κ = ℵ α .

Dim:

Dimostriamo per induzione transfinita che tutti gli aleph sono cardinali.

α = 0 ⇒ ℵ 0 = ω ok

Se α = β + 1 ` e un ordinale successore ℵ α = H(ℵ <sup>β</sup> ) e quindi ` e un cardinale perch` e H(A) `e un cardinale per ogni insieme A.

α = λ ordinale limite. Per questo caso faremo uso di un lemma

Lemma 2 Se F = {κ _i | i ∈ I} ` e una famiglia di cardinali allora κ = S F `e un cardinale.

Dim:

Intanto κ ` e un ordinale perch` e unione di ordinali. Se γ = κ allora esiste i ∈ I tale che γ ∈ κ i Ma κ i ` e un cardinale dunque |γ| < |κ i | = |κ|. CVD

Quindi anche ℵ λ = S

γ<λ ℵ γ ` e un cardinale perch` e unione di cardinali.

Esercizio 40 La sequenza degli aleph ` e strettamente crescente.

Per dimostrare il risultato principale utilizzaremo un altro lemma.

Lemma 3 ∀α ∈ ON α ≤ ℵ ^α Dim:

Per induzione transfinita su α α = 0 0 ≤ ℵ ₀ = ω, vero.

α = β + 1 per ipotesi induttiva α + 1 ≤ ℵ _α + 1 ≤ H(ℵ α ) = ℵ _α+1 (perch` e H(ℵ α ) > ℵ _α ).

α = λ ordinale limite, allora per ogni γ < λ si ha che γ ≤ ℵ γ . Ma allora per ipotesi induttiva.

λ = sup

γ<λ

γ ≤ sup

γ<λ

ℵ γ = ℵ λ

CVD

N.B.: Esistono α tali che ℵ α = α. Ad esempio definiamo per ricorsione ( κ 0 = ℵ 0

κ n+1 = ℵ κ

e sia κ = sup _n<ω κ n Allora si ha che ℵ κ = κ. Infatti κ ≤ ℵ κ . Se per assurdo κ < ℵ κ = S

γ<κ ℵ γ = sup _n<ω ℵ κ

= κ.

Analizzando l’esempio inoltre si dimostra che ∀γ∃κ > γ ℵ κ = κ

Veniamo dunque alla dimostrazione che tutti i cardinali sono aleph.

Sia κ un generico cardinale. Allora posso definire β := min{α | κ < ℵ α } (certamente non vuoto per il lemma: κ ≤ ℵ _κ < ℵ _κ+1 ). Ora β 6= 0 perch` e ` e infinito. Ma β 6= λ limite, perch` e altrimenti κ < ℵ <sub>λ</sub> = sup <sub>γ<λ</sub> ℵ γ perci` o κ < ℵ _γ per un opportuno γ < λ.

Ma allora β = α + 1 e ℵ _α ≤ κ < ℵ _α+1 = H(ℵ α ). Cio` e |κ| ≤ |ℵ <sub>α</sub> |. Ma κ ` e un

cardinale per cui κ ≤ ℵ _α , che da’ la tesi. CVD

Osservazione 9 Ogni insieme bene ordinabile ` e equipotente ad un aleph. In- fatti se A ` e bene ordinabile, sia (A, <) un buon ordinamento e α l’unico ordinale a cui ` e isomorfo come insieme bene ordinato. In particolare esiste una funzione biunivoca da A su α, quindi |A| = |α|. Sia κ = min{γ ordinale | |γ| = |α|} che

` e un cardinale. Allora per il teorema precedente esiste un β per cui |κ| = |ℵ β |.

Quindi

|A| = |α| = |κ| = |ℵ β |

Indicheremo ℵ _β , cio` e l’unico aleph equipotente ad A come |A|.

NOTA: IL TEOREMA SEGUENTE VIENE SOLO ENUNCIATO E NON DIMOSTRATO SUGLI APPUNTI. LA FORMULAZIONE CON CUI ` E ENUN- CIATO NEGLI APPUNTI ` E PALESEMENTE FALSA. CERCANDO IN IN- TERNET NON L’HO TROVATO MA NE PROPONGO UGUALMENTE UNA

“RICOSTRUZIONE”. SE QUALCUNO PU ` O OTTENERE QUALCOSA DI PI ` U PRECISO (ES. CHIEDENDO A QUALCUNO CHE HA SEGUITO IL CORSO) ` E BENVENUTO

Teorema 10 (Pincus) Senza assumere l’assioma della scelta non ` e dimostrabile l’esistenza di alcuna funzione classe F definita su tutto V tale che

• |A| = |B| ⇔ F(A) = F(B)

• |F(A)| = |A|

F(A) sarebbe il rappresentante canonico della classe di equipotenza di A.

Adesso vedremo, invece, che con l’assioma di scelta ` e possibile dimostrare che ogni insieme ` e bene ordinabile, e quindi l’osservazione precedente ci consente di costruire la funzione-classe.

10 L’assioma di scelta

Assumendo la teoria di ZF senza scelta le seguenti proposizioni sono equivalenti:

1. L’Assioma di Scelta 2. Il Lemma di Zorn

3. Il Teorema di Zermelo (ogni insieme ` e bene ordinabile)

4. La tricotomia delle cardinalit` a (per ogni coppia di insiemi A, B o |A| = |B|

o |A| > |B| o |A| < |B|

5. ∀A infinito |A × A| = |A|

L’Assioma di Scelta ha quattro formulazioni equivalenti:

I ∀x∃f : P(x)∅{∅} → x tale che f (A) ∈ A (Per ogni insieme esiste una

funzione di scelta)

II ∀F famiglia di insiemi non vuoti e disgiunti, allora esiste un x tale che

∀F ∈ F |F ∩ x| = 1 (Per ogni famiglia di insiemi esiste un insieme di scelta)

III ∀f : A → B suriettiva, ∃g : B → A tale che f ◦ g = id B

IV ∀ < A i | i ∈ I > sequenza di insiemi non vuoti, Q

i∈I A i 6= ∅ Esercizio 41 Verificare l’equivalenza di (I), (II), (III), (IV).

Dimostriamo ora l’equivalenza di (1),(2),(3),(4),(5) Dim:

(3) ⇒ (1)

Se X ` e un insieme, per (3) possiamo ben ordinarlo (X,¡). Allora ` e facile definire una funzione f : P(x)\{∅} → X tale che f (A) = min A.

(3) ⇒ (4)

Abbiamo visto che ogni insieme bene ordinabile ` e equipotente ad un aleph.

Allora, se vale Zermelo

∀A, B ∃α, β |A| = |ℵ α | |B| = |ℵ β | Visto che α = β o α < β o α > β segue la tricotomia

(4) ⇒ (3)

Sia A un insieme. Abbiamo visto che |H(A)| 6≤ |A|. Per la tricotomia deve essere |A| < |H(A)|, cio`e esiste ϕ : A → H(A) iniettiva. Definisco una relazione

< su A tale che a < a ⁰ ⇔ ϕ(a) < ϕ(a ⁰ ). Visto che H(A) `e un ordinale, `e bene ordinato, quindi anche (A, <) ` e bene ordinato perch` e ` e isomorfo a Im ϕ ⊆ H(A).

(3) ⇒ (5)

Basta dimostrare che |ℵ _α × ℵ α | = |ℵ α |. Diamo un ordine sulle coppie di ordinali (ξ, η)

(ξ, η) < (ξ ⁰ , η ⁰ ) ⇔



 

 

max{ξ, η} < max{ξ ⁰ , η ⁰ } oppure max = max ⁰ e ξ < ξ ⁰ oppure max = max ⁰ , ξ = ξ ⁰ , η < η ⁰

Esercizio 42 Per ogni ordinale α, (α × α, <) ` e bene ordinato.

Notiamo che per ogni segmento iniziale, se ξ ≥ η S ₍ ξ, η) ⊆ {0, . . . , ξ} × {0, . . . , ξ}

Per dimostrare la tesi procediamo per induzione su α. Ovviamente |ℵ 0 × ℵ 0 | = |ℵ 0 |. Per assurdo sia α tale che |ℵ α × ℵ α | 6= |ℵ α |. Allora ovviamente

|ℵ α × ℵ α | < |ℵ α | (basta l’immersione canonica).

Ma (ℵ α × ℵ α , <) ` e bene ordinato, perci` o per la tricotomia dei buoni ordini esiste un isomorfismo

ϕ : ℵ α → S (ξ,η) segmento iniziale di (ℵ α × ℵ α , <)

Ma ξ ∈ ℵ _α perci` o |{0, . . . , ξ}| = |ξ + 1| < ℵ <sub>α</sub> (perch` e ℵ _α ` e un ordinale limite, e quindi non pu` o essere un successore). E quindi |ξ + 1| = |ℵ _β | con β < α. Allora

S _(ξ,η) ⊆ {0, . . . , ξ} × {0, . . . , ξ} ⇒

|S _(ξ,η) | ≤ |{0, . . . , ξ} × {0, . . . , ξ}| ≤ |ℵ _β × ℵ _β | Ma per ipotesi induttiva

|ℵ β × ℵ β | = |ℵ β | < |ℵ α | Cio` e

|ℵ α | = |S _(ξ,η) | ≤ |ℵ β | < |ℵ α | Assurdo.

(5) ⇒ (3)

Fissiamo un insieme A infinito (il caso finito ` e banale), e supponiamo senza perdita di generalit` a che A ∩ H(A) = ∅. Ma

(A∪H(A))×(A∪H(A)) = (A×A)∪(A×H(A))∪(H(A)×A)∪(H(A)×H(A)) ⊇ A×H(A) Visto che |(A ∪ H(A)) × (A ∪ H(A))| = |A ∪ H(A)| esiste una funzione iniettiva ψ : A × H(A) → A ∪ H(A)

Per ogni a ∈ A sia allora ψ a : H(A) → A ∪ H(A) definita da ψ ^a (ξ) = ψ(a, ξ).

Per ogni a ψ a ` e iniettiva perch` e lo era ψ. Inoltre poich` e H(A) 6≤ A abbiamo che Im ψ a ∩ H(A) 6= ∅. Quindi ha senso definire per ogni a ∈ A,

ξ a = min{ξ ∈ H(A) | ψ ^a (ξ) ∈ H(A)}

Infine definisco θ : A → H(A) tale che θ(a) = ψ(a, ξ ^a ). θ ` e iniettiva, perch` e lo ` e ψ, quindi, visto che H(A) `e ben ordinato, essendo un ordinale, `e possibile indurre un buon ordinamento anche in A

Teorema 11 Lemma di Zorn (2) Sia (P, ≤) un insieme parzialmente ordinato dove ogni catena ammette maggioranti. Allora in (P, ≤) esistono elementi mas- simali.

• C ⊆ P `e una catena se ∀p, q ∈ C p ≤ q o q ≤ p, cio` e se ` e totalmente ordinato dalla restrizione di ≤.

• p ∈ P ` e maggiorante di un insieme A ⊆ P se ∀x ∈ A x ≤ p

• p ∈ P ` e massimale se ∀x 6= p p < x

(2) ⇒ (3)

Sia A un insieme fissato. Consideriamo l’insieme di insiemi ordinati P = {(X, ≤) | X ⊆ A e (X, ≤) ` e ben ordinato}

E lo ordiniamo parzialmente con l’ordine

(X, ≤ X ) ≤ (Y, le Y ) ⇔ X ` e un segmento iniziale di Y o meglio

• X ⊆ Y

• l’ordine di Y ristretto a X coincide con l’ordine di X

• X `e un segmento iniziale di (Y, ≤ Y )

Vogliamo dimostrare che P ` e nelle ipotesi del lemma di Zorn. Sia quindi C = {(X i , ≤ i ) | i ∈ I} una catena. Consideriamo

X := ˜ [

i∈I

X _i

Si dimostra facilmente dalla propriet` a di catena di C che ˜ < := S

i∈I < i ` e un buon ordine su ˜ X. Quindi ( ˜ X, ˜ <) ` e un maggiorante per C e posso applicare il lemma di Zorn a P .

Sia quindi (X ^∗ , < ∗) un elemento massimale per P . Se riesco a dimostrare che X ^∗ = A concludo. Se cos`ı non fosse prendo a ∈ A\X ^∗ e considero X ^∗

:=

X ^∗ ∪ {a}. Inoltre posso dotare X ^∗

di un ordinamento prendendo quello di X ^∗ e mettendo a come elemento massimo. Chiaramente anche X ^∗

` e bene ordinato, e X ^∗ < X ^∗

, contro la massimalit` a di X ^∗ , assurdo. Quindi X ^∗ = A e ho concluso.

(1) ⇒ (2)

Sia (P, ≤) che soddisfa le ipotesi di Zorn. Fissiamo allora f : P(P )\∅ → P funzione di scelta. Fissiamo inoltre ∗ 6∈ P . Per ricorsione transfinita definiamo



 

 

p ₀ = f (P )

p α = ∗ se esiste β < α con p β = ∗ o se {p β | β < α} non ha maggioranti stretti p _α = f ({x ∈ P | x ` e maggiorante stretto di {p _β | β < α}}) altrimenti

Intanto notiamo che se a un certo punto p _α = ∗ allora da l`ı in poi p _β = ∗ ∀β ≥ α.

Inoltre notiamo che se α > β, e p _α , p _β ∈ P , p α > p _β .

Quindi se la funzione-classe α → p _α non assumesse mai il valore ∗ sarebbe iniettiva, ma questo ` e assurdo perch` e non pu` o esistere una funzione-classe iniet- tiva che ha per dominio una classe propria e per codominio un insieme. Quindi ha senso definire α = min{ξ | p <sub>ξ</sub> = ∗}. Questo deve essere successore perch` e ` e chiaramente diverso da 0 e, inoltre, se fosse limite, la catena {p ξ | ξ < α} non avrebbe maggiorante (non ha maggiorante stretto per la definizione di α e non ha massimo perch` e α ` e un ordinale limite).

Quindi α = β + 1, e p β deve essere elemento massimale perch` e la catena

{p ξ | ξ < α} non ha maggioranti stretti, e quindi non esiste alcun elemento

q ∈ P tale che q 6= p β e q ≥ p β . CVD

11 Propriet` a dei cardinali

11.1 Operazioni cardinali

Definizione 16 Fissati κ, ν cardinali siano A, B due insiemi tali che |A| = κ, |B| = ν, A ∩ B = ∅. Allora definiamo

κ + ν = l’unico cardinale equipotente a A ∪ B κν = l’unico cardinale equipotente a A × B κ ^ν = l’unico cardinale equipotente a F un(B, A) (Indichiamo con |A| quell’unico cardinale equipotente ad A).

Notiamo che sono buone definizioni perch` e non dipendono dalla scelta degli insiemi A, B. Notiamo che

2 ^ℵ

= |F un(ℵ ₀ , 2)| = |P(ℵ ₀ )| e ℵ ₀ < 2 ^ℵ ₀

(cardinalit` a del continuo). L’ipotesi del continuo dice che ℵ ₁ = 2 ^ℵ

. Teorema 12 Per ogni κ, ν cardinali κ + ν = κν = max κ, ν Dim:

Sia ξ = max κ, ν. Allora

κ + ν ≤ ξ + ξ = 2ξ ≤ ξξ = ξ ≤ κ + ν κν ≤ ξξ = ξ ≤ κν

Definizione 17 (Somme infinite) Sia < k i | i ∈ I > una sequenza di cardinali.

Allora definiamo X

i∈I

k _i la cardinalit` a dell’unione [

i∈I

A _i dove |A _i | = k i e A _i ∩ A j = ∅ per i 6= j

Definizione 18 (Prodotto infinito) Y

i∈I

k i ` e la cardinalit` a del prodotto cartesiano Y

i∈I

A i con |A i | = k i

Esercizio 43 Dimostrare che:

• κ i ≤ ν i per ogni i ⇒ P

i∈I κ i ≤ P

i∈I ν i e Q

i∈I κ i ≤ Q

i∈I ν i

• P

i∈I κ = κ|I|

• Q

i∈I κ ^ν

= κ ^P

^ν

• Q

i∈I κ _i
ν

= Q

i∈I κ ^ν _i

Teorema 13 X

i∈ν

κ i = max{κ, ν} dove κ = sup

i∈I

κ i e κ i 6= 0

Esempio: P

i∈ℵ

1 = ℵ ₁ . Dim:

X

i∈ν

κ i ≥ X

i∈ν

1 = ν Inoltre

∀i 0 ∈ ν κ i

≤ X

i∈ν

κ i ⇒ κ = sup

i∈ν

κ i ≤ X

i∈ν

κ i

Quindi max{κ, ν} ≤ P

i∈ν κ _i . Viceversa X

i∈ν

κ i ≤ X

i∈ν

κ = κν = max{κ, ν}

CVD

11.2 Cardinalit` a dei Boreliani

Definizione 19 La famiglia B degli insiemi Boreliani ` e la pi` u piccola famiglia di sottoinsiemi di R che contiene gli aperti ed `e chiusa per complemento e unione e intersezione numerabile

Per calcolare la cardinalit` a della famiglia dei Boreliani, cerchiamo di “descriverli”

tramite la ricorsione transfinita.



 

 

B 0 = {Ω | Ω aperto}

B _α+1 = B _α ∪ {B ^C | B ∈ B α } ∪ {∩ _n∈N f (n) | f : N → B α }

B λ = S

γ<λ B γ

Notiamo che B ω ` e chiuso solo per unione e intersezione finita. (Unione perch` e [ B i = \

B _i ^C  ^C

). L’insieme di tutti i Boreliani ` e invece B _ω

. Infatti banalmente B _ω

` e sot- toinsieme dei boreliani perch` e tutti i suoi elementi si possono ottenere dagli aperti con unioni e intersezioni numerabili e complementi. Ma si vede immedi- atamente che B ω

` e chiuso per intersezione, unione numerabile e complemento (le intersezioni numerabili e i complementi di B α si ottengono in B α+1 ) e inoltre B ω

⊇ B 0 e quindi contiene gli aperti. Quindi B ω

` e l’insieme di tutti i Boreliani

Dimostriamo ora che i Boreliani hanno la cardinalit` a del continuo

|B ω

| = c = 2 ^ℵ