Minicorso di aritmentica ordinale
A.1. La classe degli ordinali
Definizione A.1.1 (Buoni ordini). Un insieme X totalmente ordinato si dice ben ordinato (e l’ordine si dice un buon ordine) se ogni sottoinsieme non vuoto di X ha un minimo:
∀∅ 6= A ⊆ X∃a ∈ A : ∀b ∈ A : a ≤ b.
In particolare ogni insieme non vuoto ben ordinato ha un minimo. Se non vi sono ambiguit`a notazionali, il minimo di un insieme ben ordinato si chiama spesso 0.
Esempio A.1.2. L’insieme vuoto `e ben ordinato, ed `e l’unico ben ordinato che non ha minimo. N `e ben ordinato rispetto all’ordine usuale; Z no, infatti non `e vuoto ma non ha un minimo.
`E da sottolineare che nella definizione di insieme ben ordinato, il minimo di A deve stare in A. Esempio A.1.3. L’insieme [0, ∞) con l’ordine usuale non `e ben ordinato, infatti il suo sottoinsieme A = (1, 2)non ha un minimo. (Verrebbe da dire che 1 sia il minimo di A; ma non sta in A, che ha quindi un estremo inferiore, ma non un minimo!)
Esempio A.1.4. L’insieme {1 − 1
n+1: n ∈ N} `e ben ordinato. L’insieme {n+11 : n ∈ N} no.
Esempio A.1.5. L’insieme {k −n+11 : k, n ∈ N} `e ben ordinato. L’insieme {k +n+11 : k, n ∈ N} no. Nemmeno l’insieme {k − 1
n+1: k ∈ Z, n ∈ N} lo `e. Esempio A.1.6. L’insieme N ∪ {∞} con l’ordine
x ≤ y ⇔
x, y ∈ N e x ≤ y per l’ordine naturale di N xqualsiasi e y = ∞
`e ben ordinato. In quanto ogni sottoinsieme non vuoto o `e il solo ∞ — e allora ∞ `e il minimo — oppure `e un sottoinsieme di N (pi `u eventualmente ∞) e quindi ha minimo.
Esercizio A.1.7. Dimostrare che l’insieme N ∪ {∞1} ∪ {∞2} con l’ordine
x, y ∈ N e x ≤ y per l’ordine naturale di N x < ∞1∀x ∈ N
x < ∞2∀x ∈ N ∞1< ∞2 `e ben ordinato.
Definizione A.1.8. Sia X un insieme ben ordinato. Un punto x ∈ X `e il massimo di X se ∀y ∈ X : y ≤ x.
190 A. MINICORSO DI ARITMENTICA ORDINALE
Chiaramente il massimo se esiste `e unico, ma non tutti gli insiemi ben ordinati hanno un massimo. Esempio A.1.9. L’insieme ben ordinato N non ha un massimo.
Esempio A.1.10. Il massimo di N ∪ {∞} `e ∞. Il massimo di N ∪ {∞1} ∪ {∞2} `e ∞2.
Definizione A.1.11. Sia X un insieme ben ordinato e sia x ∈ X. Se x non `e il massimo, l’insieme Sx= {y ∈ X : y > x}(maggiore stretto) `e non vuoto. In tal caso si definisce il successore di x come
s(x) = min Sx.
Il successore di x, se esiste, si suole indicare spesso con la notazione x + 1 : s(x) = x + 1
Esempio A.1.12. In N il successore di 0 `e 1; quello di n `e n+1. In N∪{∞1}∪{∞2} si ha ∞1+1 = ∞2. Esempio A.1.13. Sia X l’insieme {k −n+11 : k, n ∈ N} con l’ordine indotto da R. Il minimo di X `e −1 (ottenuto per k = n = 0), X non ha massimo. Il successore di 3 (ottenuto per k = 4 e n = 0) `e 7/2 (ottenuto per k = 4 e n = 1). Quindi si pu `o dire
” − 1 = 0” ”3 + 1 = 7/2” (questo `e preziosissimo materiale da aperitivo con ingegneri.)
Definizione A.1.14. Sia X un insieme ben ordinato. Un elemento x ∈ X si dice successore se esiste y tale che x = y + 1 e si dice limite se 0 6= x e x non `e successore. Ci sono quindi tre tipi di punti:
0 (il minimo di X, se non vuoto) successori
limiti
Esempio A.1.15. In N non ci sono numeri limite. Esempio A.1.16. In N ∪ {∞} l’unico punto limite `e ∞.
Esempio A.1.17. In N ∪ {∞1} ∪ {∞2} con l’ordine dell’Esercizio A.1.7 l’unico punto limite `e ∞1. (∞2= ∞1+ 1`e un successore.)
Esempio A.1.18. Sia X l’insieme {k − n+11 : k, n ∈ N} con l’ordine indotto da R. Gli elementi limite sono gli elementi di N. Gli altri, tranne −1 che `e il minimo, sono successori.
Teorema A.1.19(Induzione transfinita). Sia α 6= ∅ un insieme ben ordinato. Sia P (x) una proposizione che dipende da x ∈ α. Se
P (0)`e vera
∀x ∈ α : (∀y < x P (y) `e vera) ⇒ P (x) `e vera allora P (x) `e vera per ogni x ∈ α.
DIMOSTRAZIONE. Sia F l’insieme degli x ∈ α per cui P (x) `e falsa. Se F non `e vuoto allora ha un minimo x0 ∈ F perch´e α `e ben ordinato. Ma allora P (y) `e vera per tutti gli y < x0. Per ipotesi induttiva ne segue che P (x0)`e vera e dunque non pu `o stare in F . Dunque F `e vuoto.
A.1. LA CLASSE DEGLI ORDINALI 191
Si noti che l’induzione usuale `e un caso particolare della transfinita (con α = N). Come l’usuale, anche l’ipotesi induttiva transfinita si pu `o rimpiazzare con un’ipotesi del tipo P (x) ⇒ P (x + 1), ma solo per i successori, per i limiti si deve mantenere l’ipotesi induttiva generale:
P (0)`e vera ∀x ∈ α : (P (x) `e vera) ⇒ P (x + 1) `e vera
∀x ∈ α limite : (∀y < x P (y) `e vera) ⇒ P (x) `e vera
Nella Definizione 0.4.7 si erano introdotti tutti i tipi di intervalli di insiemi ordinati. Nel mondo degli insiemi ben ordinati per `o, ne bastano meno.
Definizione A.1.20(Segmenti). Sia X un insieme ben ordinato. Un segmento di X `e un insieme del tipo:
[a, b) = {x ∈ X : a ≤ x < b} segmento generico [0, b) = {x ∈ X : x < b} segmento iniziale [a, ∞) = {x ∈ X : x ≥ a} segmento finale
Si noti che un segmento pu `o avere un massimo anche se la sintassi `e quella di “aperto in b” e ci `o succede precisamente tutte le volte che b `e un successore. Quindi [a, b] non `e altro che [a, b + 1):
[a, b] = {x ∈ X : a ≤ x ≤ b} = [a, b + 1)
(Se b `e il massimo di X si ha [a, b] = [a, ∞)). Inoltre, siccome X `e ben ordinato, ogni segmento ha un minimo quindi non esistono “segmenti (a, b) aperti in a” in quanto (a, b) non `e altro che [a + 1, b):
(a, b) = {x ∈ X : a < x < b} = [a + 1, b).
Definizione A.1.21. Siano X e Y due insiemi ben ordinati. Una funzione f : X → Y si dice
monotonase x > y ⇒ f (x) > f (y); f si dice immersione se `e monotona e l’immagine di f `e un segmento di Y , si dice isomorfismo se `e biunivoca e monotona. Due insiemi ben ordinati si dicono isomorfi se esiste un isomorfismo tra loro.
Teorema A.1.22. Siano X e Y due insiemi non vuoti e ben ordinati. Una funzione f : X → Y `e
un’immersione se e solo se per ogni 0 < x ∈ X si ha f (x) = min{y ∈ Y : f ([0, x)) < y}.
DIMOSTRAZIONE. Supponiamo che f sia un’immersione e sia x > 0. Per monotonia f (x) > f ([0, x)). Se esistesse y ∈ Y tale che f ([0, x)) < y < f (x) allora, sempre per monotonia, y non starebbe nell’immagine di f che quindi non sarebbe un segmento e dunque f non sarebbe un’immersione.
Viceversa, supponiamo che valga f (x) = min{y ∈ Y : f ([0, x)) < y}. In particolare, siccome f (x) > f ([0, x)), se x > z allora f (x) > f (z). Quindi f `e monotona. Vediamo adesso che l’immagine di f `e un segmento di Y . Sia I l’immagine di f e sia A il suo complementare. Per ogni x > 0 si deve mostrare che A ∩ [f (0), f (x)] `e vuoto. Se cos`ı non fosse, tale insieme avrebbe un minimo y0e detto y1 = min{y ∈ I ∩ [f (0), f (x)] : y > y0}, per definizione y1 sarebbe immagine di un punto x1per il quale non vale f (x1) = min{y ∈ Y : f ([0, x1)) < y}.
Corollario A.1.23. Siano X e Y due insiemi non vuoti e ben ordinati. Allora ogni immersione di X in Y
`e determinata dall’immagine di zero.
DIMOSTRAZIONE. Siano f, g : X → Y due immersioni tali che f (0) = g(0). Se f (z) = g(z) per ogni z < x, allora f ([0, x)) = g([0, x)). Per il Teorema A.1.22, f (x) = min{y ∈ Y : f ([0, x)) < y} = min{y ∈ Y : g([0, x)) < y} = g(x). Siccome f (0) = g(0), per induzione transfinita f (x) = g(x) per
ogni x ∈ X.
Un’immersione `e sempre un’isomorfismo con l’immagine. Di particolare importanza nella teoria dei buoni ordini sono i segmenti iniziali e le loro immersioni in segmenti iniziali.
192 A. MINICORSO DI ARITMENTICA ORDINALE
Definizione A.1.24(Ordinali come tipi d’ordine). Un ordinale `e la classe di isomorfismo di un insieme ben ordinato. Se α = [X] `e un ordinale, un segmento di α `e la classe di un segmento di X. Un segmento iniziale di α `e la classe di un segmento iniziale di X. Dati due ordinali α e β, si dice che α < βse α `e un segmento iniziale di β (cio`e, posto β = [Y ], se X `e isomorfo a un segmento iniziale di Y).
In parole povere, α < β significa che β “comincia” come α. Ci `o definisce un ordine stretto.
Teorema A.1.25. Sia X un insieme ben ordinato. Allora X non `e isomorfo a nessun suo segmento iniziale
proprio.
DIMOSTRAZIONE. Sia A ⊆ X l’insieme degli elementi x ∈ X tali che X `e isomorfo a [0, x). Supponiamo A 6= ∅ e sia a il minimo di A. Siccome X `e isomorfo a [0, a) esite un’immersione f : X → [0, a) con f (0) = 0. Sia b = f (a). Siccome X `e isomorfo a [0, a) allora `e anche isomorfo a f ([0, a)) = [0, b). Quindi b ∈ A e b < a = min A. Assurdo. Quindi A = ∅.
Teorema A.1.26. Siano α = [X] e β = [Y ] due ordinali. Allora uno dei due `e un segmento iniziale
dell’altro.
DIMOSTRAZIONE. Se uno dei due tra X e Y `e vuoto non v’`e nulla da dimostrare. (∅ = [0, 0) `e segmento iniziale di tutto.) Supponiamo quindi X, Y non vuoti e denotiamo con 0 sia il minimo di X che quello di Y . Supponiamo che β non sia un segmento iniziale di α e dimostriamo che α `e un segmento iniziale di β.
Dimostriamo per induzione transfinita che la frase P (x)= “Esiste un’immersione f : [0, x] → Y con f (0) = 0” `e vera per ogni x. P (0) `e ovviamente vera. Se per ogni z < x esiste un’immersione fz : [0, z] → Y tale che fz(0) = 0, per il Corollario A.1.23 tale immersione `e unica. Ne segue che le funzioni fz definiscono un’immersione f : [0, x) → Y con f (0) = 0. Quindi [0, x) `e isomorfo a un segmento iniziale di Y . Siccome Y non `e isomorfo a [0, x) (stiamo supponendo che β 6≤ α), allora f ([0, x)) 6= Y. Ponendo f (x) = min{y ∈ Y : f ([0, x)) < y} si ottiene un’immersione di [0, x] in un segmento iniziale di Y . Quindi P (x) `e vera per ogni x. Le immersioni fx: [0, x] → Y (uniche per il Corollario A.1.23) definiscono un’immersione di X in un segmento iniziale di Y .
Il Teorema A.1.26 dice che dati due ordinali α, β si ha α ≤ β o β ≤ α e si pu `o quindi parafrasare dicendo che la classe1degli ordinali `e totalmente ordinata.
Teorema A.1.27. La classe degli ordinali `e ben ordinata.
DIMOSTRAZIONE. Sia A una classe di ordinali e sia α ∈ A. Gli elementi di A minori di α non sono altro che classi di equivalenza di ordini di segmenti iniziali [0, x) di α. Ad ogni segmento iniziale [0, x) corrisponde il suo estremo superiore x. Quindi l’insieme degli elementi di A minori di α corrisponde a un sottoinsieme di α. Siccome α `e bene ordinato, ha un minimo. Tale minimo `e ovviamente il
minimo di A.
Dato un ordinale si pu `o quindi definire il suo successore come il pi `u piccolo ordinale maggiore di esso. Gli ordinali sono di tre tipi, come gli elementi
0 = ∅ lo zero, l’ordinale pi `u piccolo
successore X `e successore, se esiste Y : X = s(Y ), se e solo se X ha un massimo limite X`e limite, se non `e successore n´e vuoto
1Si `e volutamente usata la parola “classe” al posto di “insieme” perch´e in genere “l’insieme” degli ordinali `e troppo grosso per essere catalogato come insieme senza incorrere in paradossi di tipo Russell.