.
Non abbiamo ancora gli strumenti necessari ma mostreremo che anche ε0 è un ordinale ancora numerabile (!). La domanda se esistono ordinali non numerabili a questo punto è giustificata e daremo una risposta – che sarà affermativa – solo nel prossimo capitolo. Intanto però vediamo una proprietà di ε0, che dovrebbe essere abbastanza intuitiva per come è stato definito:
Proposizione 7.8.2. Vale ωε0 = ε0.
Dimostrazione. Visto che ε0 è un ordinale limite si ha ωε0 = [
γ<ε0
ωγ= [
n<ω
ωαn = [
n<ω
αn+1= ε0,
ed abbiamo concluso.
7.9 Forma normale
Usando l’esponenziazione si possono rappresentare i numeri ordinali in una forma simile a quella utilizzata per l’espansione decimale degli interi, che chiameremo forma normale, e che utilizza come “base” il numero ω.
Teorema 7.9.1. Ogni α > 0 ordinale può essere espresso unicamente come α = ωβ1 · n1+ ωβ2· n2+ . . . + ωβk· nk,
con β1 > · · · > βk e n1> 0, n2 > 0, . . . , nk> 0 sono finiti.
Dimostrazione. Intanto occupiamoci dell’esistenza della forma normale, e proce-diamo per induzione su α > 0. Supponiamo che α = 1, la tesi è vera in modo banale; sia dunque α > 1. Osserviamo che esistono γ tali che ωγ > α, ad esempio
ωα+1> ωα ≥ α.
Sia β = min{ξ | ωξ > α}: si noti che non può essere limite sennò α < ωβ = S
γ<βωγ e quindi esisterebbe γ < β tale che α < ωγ, assurdo per la minimalità di β. Dunque β = δ + 1. Ora osserviamo che
ωδ≤ α < ωδ+1;
dunque possiamo dividere α per ωδ e ottenere α = ωδ· m + ρ
con ρ < ωδ≤ α. In effetti m < ω (ossia è un naturale) sennò α ≥ ωδ· m ≥ ωδ· ω = ωδ+1 > α. Se ρ = 0 abbiamo finito, altrimenti si applica l’ipotesi induttiva a ρ e dunque
ρ = ωβ1 · n1+ . . . + ωβk· nk, e dobbiamo mostrare che δ > β1. Se così non fosse
ωδ ≤ ωβ1 ≤ ρ.
Adesso dobbiamo mostrare l’unicità. Intanto osserviamo che se γ > β allora ωβ· n < ωγ per ogni n < ω. Infatti ciò discende da
ωβ· n < ωβ· ω = ωβ+1≤ ωγ.
Da ciò discende immediatamente che se γ > β1 e α = ωβ1 · n1+ . . . + ωβk· nk è la forma normale allora ωγ > α. A questo punto, per l’unicità della forma normale si procede per induzione su α ≥ 1. Se α = 1 la forma ω0· 1 è chiaramente unica.
Adesso supponiamo
α = ωβ1 · n1+ . . . + ωβk· nk= ωγ1· m1+ . . . + ωγh· mh.
Da tutta l’osservazione precedente si ha intanto che β1 = γ1 e si pone per comodità δ = ωβ1 = ωγ1, σ = ωβ2· n2+ . . . + ωβk· nk e ρ = ωγ2· m2+ . . . + ωγh· mh. Quindi si può scrivere
α = δ · n1+ σ = δ · m1+ ρ,
e visto che σ, ρ < δ si ha, per il teorema di divisione, che n1 = m1 e che σ = ρ. A questo punto si conclude molto agevolmente.
Capitolo 8
Ordinabilità e aleph
Nei capitoli precedenti abbiamo iniziato l’indagine riguardo alla cardinalità de-gli insiemi infiniti. Benché abbiamo già provato alcuni risultati che coinvolgono il concetto di |X|, la cardinalità di un insieme X, non abbiamo ancora definito formalmente |X| in sé. Quando abbiamo dato le prime nozioni sull’aritmetica car-dinale avevamo fatto l’assunzione che tali cardinali esistessero e che ad ogni insieme si possa associare uno e un solo cardinale, adesso è arrivato il momento di dimo-strarlo: in questo capitolo considereremo la questione di trovare “rappresentanti”
per le cardinalità. Abbiamo generalizzato i numeri naturali e abbiamo mostrato che i risultanti numeri ordinali hanno molte proprietà simili a quelle dei numeri naturali, in particolare le prove per induzione e le definizioni per ricursione sono sempre possibili. Tuttavia gli ordinali non rappresentano le cardinalità, ma rap-presentano invece i tipi d’ordine. E proprio perché un insieme infinito può essere ordinato in diversi modi, ci saranno diversi numeri ordinali della stessa cardinalità, ad esempio
|ω| = |ω + 1| = |ω + ω| = |ω · ω| = ℵ0.
Per scegliere uno degli ordinali come rappresentante di cardinalità di un insieme infinito e ben ordinabile, prenderemo semplicemente il più piccolo ordinale della data cardinalità.
8.1 Lemma di Zorn e teorema di Zermelo
Abbiamo accennato alla fine dell’introduzione precedente che prenderemo un rap-presentante per la cardinalità per gli insiemi ben ordinabili. Abbiamo già accenna-to che la possibilità di bene ordinare ogni insieme è data dal teorema di Zermelo, per il quale è necessario l’assioma della scelta. Abbiamo già anche detto che l’as-sioma della scelta equivale al teorema di Zermelo, ma per ora abbiamo mostrato
solo che se vale il teorema di Zermelo allora vale l’assioma della scelta. In que-sto paragrafo mostreremo l’altra implicazione, passando però anche attraverso il lemma di Zorn. Il nostro programma è il seguente:
assioma di scelta =⇒ lemma di Zorn =⇒ teorema di Zermelo,
e avendo già mostrato che “teorema di Zermelo =⇒ assioma di scelta” si ha che tutti e tre i teoremi scritti sopra sono equivalenti.
Il lemma di Zorn è un risultato sugli ordini parziali equivalente all’assioma della scelta (sulla base degli altri assiomi della teoria degli insiemi). Esso trova molte applicazioni in matematica (esistenza di basi di spezi vettoriali di dimensione in-finita, esistenza di ideali massimali in anelli, ecc...). Per il lemma ci servono delle definizioni:
Definizione 8.1.1. Sia (A, <) un ordine parziale e sia B ⊆ A. Diremo che B è una catena se per ogni a, b ∈ B si ha a < b o b < a.1
Definizione 8.1.2. Un elemento a ∈ A viene detto un maggiorante della catenza B ⊆ A se per ogni b ∈ B si ha b ≤ a.
Ricordiamo che un elemento a ∈ A è massimale se non esistono b ∈ A tali che b > a. Un ordine parziale può avere o non avere un elemento massimale (ad esempio N non ne ha) e nel caso ne abbia può averne più di uno. Non bisogna confondere la definizione di massimale con quella di massimo: di elementi massimi ce ne può essere al più uno e se esiste un massimo esso è anche massimale. Se (A, <) è un ordine totale il concetto di massimo e di massimale coincidono.
Definizione 8.1.3. Dato un ordine parziale (A, <) diciamo che B ⊆ A è una cate-na bene ordicate-nata se B è ucate-na catecate-na che è anche un buon ordine (rispetto all’ordine indotto). Diciamo inoltre che B è una catena bene ordinata non prolungabile se non esiste alcun a ∈ A che maggiora strettamente tutti gli elementi di B (ovvero B non ha maggioranti, o se ne ha uno esso appartiene a B ed è il massimo di B).
Teorema 8.1.1 (lemma di Zorn). Sia (A, <) un ordine parziale in cui ogni catena ha un maggiorante. Allora esiste un elemento massimale in A.
Dimostrazione. L’idea è di definire una catena bene ordinata B ⊆ A più lunga possibile e di prendere come elemento massimale un maggiorante di tale catena.
Per la dimostrazione ci serve il seguente lemma:
Lemma 8.1.1. Sia (A, <) un ordine parziale. Allora esiste una catena bene ordinata D di (A, <) non prolungabile.
1ossia se è un ordine totale rispetto all’ordine indotto da < su B.
Dimostrazione. In base all’assioma della scelta, esiste una funzione f che associa ad ogni sottoinsieme proprio X di A un elemento f (X) ∈ X. Dato un sottoinsieme B di A e b ∈ B si definisce Bb l’insieme degli elementi di A che sono maggiori di ogni elemento minore di b, ossia
Bb = {a ∈ A | (∀c ∈ B)(c < b)(a > c)}.
Diremo poi che B è una f –catena se B è una catena bene ordinata con l’ulteriore proprietà che per ogni b ∈ B si ha che b = f (Bb).
Dimostriamo ora che se B e C sono due f –catene, allora una delle due è un segmento iniziale dell’altra. A tal fine consideriamo l’unione D di tutti segmenti iniziali comuni di B e C:
D = [
S⊆iB S⊆iC
S.
Tale D è evidentemente il più grande segmento iniziale comune a B e C. Ci basta dimostrare che D = B oppure D = C. Se così non fosse, D sarebbe propriamente incluso sia in B che in C. Possiamo allora considerare
a = min(B − D) e b = min(C − D).
Siccome B e C sono f –catene, allora a = f (Ba) e b = f (Cb). Ma evidentenemente Ba = D = Cb, e quindi Ba = Cb perché il primo è l’insieme dei maggioranti di Ba e il secondo è l’insieme dei maggioranti di Cb = Ba. Ma allora segue che a = f (Ba) = f (Cb) = b, e ciò è assurdo perché allora a ∈ D, essendo Ba∪ {a} = Cb∪ {b} un segmento iniziale comune alle due catene B e C.
Sia X ⊆ A l’unione di tutte le f –catene. Per il teorema sulle unioni di buoni ordini di cui uno è segmento iniziale dell’altro sappiamo che X è ancora una catena ben ordinata, di cui ogni f –catena è segmento iniziale. Inoltre X è pure una f – catena in quanto per ogni d ∈ X esiste una f –catena B con d ∈ B e otteniamo d = f (Bd) = f (Xd) (essendo Xd= Bd).
Per finire, dobbiamo mostrare che X non è prolungabile, ossia che non esiste alcun a ∈ A che maggiora strettamente tutti gli elementi di X. Se così non fosse, l’insieme M di tali a sarebbe non vuoto. Ma allora X ∪ {f (M )} è ancora una f – catena, contraddicendo il fatto che X è l’unione di tutte le f –catene e f (M ) /∈ X.
Torniamo ora alla dimostrazione del lemma di Zorn. Sia X una catena bene ordinata non prolungabile in (A, <), che esiste per il lemma appena mostrato.
Per le ipotesi del lemma di Zorn X ha un maggiorante x, che evidentemente deve appartenere ad X perché altrimenti potremmo prolungare X con tale elemento.
Inoltre tale x ∈ X deve essere un elemento massimale di A: se così non fosse esisterebbe a > x, ma X ∪ {a} sarebbe un prolungamento di X, assurdo.
Teorema 8.1.2 (teorema di Zermelo). Ogni insieme X è ben ordinabile.
Dimostrazione. Vogliamo dimostrare l’esistenza di un buon ordinamento su X.
Sia P l’insieme di tutte le coppie della forma (A, <) dove A è un sottoinsieme di X e < è un buon ordine su A. Chiaramente P è non vuoto in quanto ad esempio ogni sottoinsieme finito di X può essere bene ordinato. Mettiamo su P il seguente ordine parziale ≺:
(A, <) (A0, <0) ⇐⇒ A ⊆i A0 e <=<0 |A.
In base al teorema sui limiti di buoni ordini ogni catena in (P, ) ha un maggio-rante, e quindi per il lemma di Zorn esiste un elemento massimale (M, <) in P . Per finire dimostriamo che M = X. Nel caso contrario sia a ∈ X − M , e definiamo un buon ordinamento <0 su M ∪ {a} mantenendo su M il precedente ordinamento
< e stabilendo che a è maggiore rispetto a <0 di ogni elemento di M , ossia
<0=< ∪{(m, a) | m ∈ M }.
Evidentemente (M, <) è un segmento iniziale di (M ∪ {a}, <0), contraddicendo la massimalità di (M, <) in P .
Con ciò abbiamo mostrato l’equivalenza logica tra assioma della scelta, lemma di Zorn e teorema di Zermelo. Il teorema di Zermelo appena mostrato ha anche un in-teressantissimo corollario, ossia la tricotomia dei cardinali. In effetti le cardinalità di due insiemi sono sempre confrontabili:
Corollario 8.1.1. Siano X e Y due insiemi. Allora o |X| = |Y | o |X| < |Y | o
|X| > |Y |.
Dimostrazione. Bene ordiniamo sia X che Y . La tesi segue considerando che i due buoni ordini ottenuti o sono isomorfi, o uno è isomorfo ad un segmento iniziale proprio dell’altro.