Per il lemma5.1.4, gli intervalli Di sono densi.
Se ne esiste uno infinito, allora il corrispondente Li è denso. Assurdo.
Si suppone che nessuno sia infinito. Allora hanno tutti cardinalità 0 oppure 1.
Sia I1= {i∈ I | |Di| =1}. Allora I1' D ed è sottoinsieme di I.
Poiché I è sparso, si deduce che I1 non può essere infinito, da cui |I1| = 1.
Quindi|D| =1, ossia∑i∈ILi è sparso.
5.3
classificazione di hausdorff
La classe dei tipi d’ordine sparsi può essere costruita induttivamente. Di conseguenza può essere definito un rango.
Questo fatto è dato dal teorema di classificazione di Hausdorff [6].
Per dimostrarlo, si costruisce una classe di ordini totali V induttivamente e poi si dimostra che V è effettivamente la classe di tutti gli ordini totali sparsi.
Definizione 5.3.1: La classe V è costruita come segue:
passo base Sia V0la classe di tutti gli ordini totali finiti.
passo induttivo Siano definite le classi Vβ per ogni β <α.
Allora Vα è la classe degli ordini totali che si possono scrivere come
somma indicizzata da un buon ordine o dall’inverso di un buon ordine, di elementi appartenenti alle classi Vβ, tali che β<α.
In formule, L ∈Vα se e solo se L= ∑i∈ILi, dove I è un buon ordine o
l’inverso di un buon ordine e Li ∈Vβ per qualche β< α.
Sia V= S
α∈OnVα.
Poiché tale classificazione è definita usando somme di ordini totali, che per il lemma1.4.2sono invarianti per isomorfismo, allora essa è anche una
classificazione dei tipi d’ordine sparsi.
Osservazione 5.3.1: Alcune banali osservazioni su V. Innanzitutto è chiaro che β<α =⇒ Vβ ⊆Vα.
Inoltre è evidente che tutti i buoni ordini appartengono a V1.
Lemma 5.3.1: Se un ordine totale L appartiene a Vα, allora vi appartengono anche
tutti i suoi sottordini.
Dimostrazione. La dimostrazione è per induzione transfinita sugli ordinali.
passo base Se L ∈ V0, allora L è finito. Di conseguenza tutti i suoi sottor-
dini sono finiti, ovvero appartengono a V0.
passo induttivo Sia L∈ Vα. Allora si può scrivere L= ∑i∈ILi, dove I ha
38 congettura di fraïssé
tale che β<α. Sia L0 ⊆ L un qualsiasi sottordine di L.
Allora L0 = L∩L0 = ∑i∈ILi∩L0 = ∑i∈I(Li∩L0). Poiché Li∩L0 ⊆ Li,
per induzione Li∩L0 ∈Vβ per qualche β< α.
Si definisce infine il rango su V come segue:
Definizione 5.3.2: Sia L∈V. Si chiama rango di L, e lo si indica con rk(L), il minimo ordinale per cui L∈Vα.
In formule, rk(L) =min{α∈On|L∈Vα}.
Il lemma5.3.1mostra che il rango si comporta "bene" per i sottordini: il
rango di ogni ordine di V è maggiore o uguale rispetto a quello di ogni suo sottordine.
Rimane da dimostrare che V è effettivamente la classe di tutti gli ordini totali sparsi. Questo fatto va sotto il nome di teorema di classificazione di Hausdorff.
Si vede prima un lemma preliminare.
Lemma 5.3.2: Sia(A,<A)un ordine totale qualsiasi. Allora esistono (B,<B)e
(C,<C)sottordini ben ordinati e, rispettivamente, coiniziale e cofinale con(A,<A). Dimostrazione. Si costruisce il sottoinsieme C ⊆ A con un induzione transfi- nita sugli ordinali.
passo base Se A6=∅, sia x0∈ A un elemento qualsiasi.
passo induttivo Siano definiti xβ per ogni ordinale β <α.
Se la successione costruita (xβ)β<α è cofinale con A, si pone C =
xβ
β<α .
Si può allora supporre che ciò non sia vero. L’insieme Aα = x∈ A
∀β<α (xβ <A x) è non vuoto. Sia xα ∈ Aα un elemento qualsiasi.
Si vede poi che deve esistere un ordinale α per cui Aα = ∅, ovvero per cui
(xβ)β<α sia cofinale con A.
Se ciò non fosse vero, allora esisterebbe la funzione iniettiva f : On → A data da f(α) =xα. Questa però sarebbe una funzione iniettiva da una classe
propria in un insieme. Si pone infine C= xβ
β< α .
La costruzione di (B,<B) è analoga: basta prendere come Aα l’insieme
x∈ A ∀β<α (xβ >A x) .
Osservazione 5.3.2: Si nota che in realtà gli unici casi in cui la successione
(xβ)β∈αnon è banale sono quelli in cui α è limite.
Contrariamente, se α=β+1, l’ elemento xβ sarebbe il minimo o il massimo
di A, di conseguenza B e C sarebbero formati da un solo elemento.
Teorema 5.3.1 (Classificazione di Hausdorff, [6]): La classe V è la classe degli
5.3 classificazione di hausdorff 39
Dimostrazione. Si mostrano le due inclusioni L è sparso ⇐⇒ L∈V:
⇐ Per induzione sul rango:
passo base L ∈ V0 significa che L è finito, per cui è banalmente
sparso.
passo induttivo Sia rk(L) = α. Allora L ∈ Vα, dunque si può scri-
vere L= ∑i∈ILi, dove I è un buon ordine o l’inverso di un buon
ordine (e dunque è sparso), e per ogni i∈ I vale rk(Li) <α.
Per induzione, tutti gli Li sono sparsi. Per il lemma5.2.4, anche L
è sparso.
⇒ Si introduce la seguente notazione: siano x, y∈ L.
[x, y] =
(
{z∈ L|x≤Lz≤L y} se x≤Ly
{z∈ L|y≤L z≤Lx} se y≤L x
Dunque [x, y] indica l’intervallo con estremi x e y, senza però specifi- care quale dei due sia l’estremo inferiore e quale quello superiore: in pratica[x, y] = [y, x].
Per ogni x∈ L, si definiscono poi c(x) ={y∈ L| [x, y] ∈V}.
Il primo obiettivo è dimostrare che tutti gli intervalli del tipo [x, y]so- no elementi di V. L’obiettivo successivo è poi quello di scrivere L come somma indicizzata da un buon ordine o dall’inverso di un buon ordine di tali intervalli.
Quali proprietà hanno i c(x)? 1. Sono intervalli.
Siano a <Lz<Lb con a, b∈ c(x)e z∈ L. Si mostra che z∈ c(x). Chiaramente se x <La oppure b <L x, si ha che[x, z]è contenuto
rispettivamente in [x, b] oppure in [x, a], che appartengono a V. Per il lemma5.3.1anche [x, z] ∈V.
Se a <L x <L b, allora [x, z] ⊆ [x, a] + [x, b] e si conclude come
prima.
2. y∈c(x) =⇒ c(y) =c(x).
Innanzitutto è ovvio che y∈c(x) ⇐⇒ x ∈c(y). Basta dunque mostrare che y ∈c(x) =⇒ c(y) ⊆c(x).
Sia z ∈ c(y). Ciò significa che [y, z] ∈ V. Si deve mostrare che
[x, z] ∈V.
Si presentano sostanzialmente 3 casi:
a) Se z è compreso tra x e y, allora[x, z] ⊆ [x, y] ∈V. b) Se x è compreso tra y e z, allora[x, z] ⊆ [y, z] ∈V.
c) Se y è compreso tra x e z, allora [x, z] è contenuto in [x, y] + [y, z](o viceversa in base all’ordinamento tra x e z).
Dunque i c(x)sono intervalli che partizionano L.
Sia dunque c[L] = {c(x)|x ∈L}l’insieme quoziente di tale partizio- ne. Il fatto che gli elementi di c[L]siano intervalli rende ben definito l’ordinamento dato da I1 I2 ⇐⇒ ogni elemento x∈ I1è minore di
40 congettura di fraïssé
ogni elemento y∈ I2.
Mostrare che tutti gli intervalli del tipo[x, y]appartengono a V è equi- valente a dire che in realtà tutti i c(x)sono lo stesso insieme, ossia che c[L] '1.
Si supponga che ciò non sia vero. Siano dunque c(x) c(y). Si mostra allora che c[L]è denso, ossia esiste z∈ L per cui c(x) c(z) c(y). Se ciò non fosse vero, allora ogni elemento x <L z <L y dovreb- be appartenere a uno tra c(x) e c(y). Per il lemma 5.3.2, esistono
(xi)i∈γ1 ⊆ c(x) e (yi)i∈γ2 ⊆ c(y) successioni rispettivamente cofinale
e coiniziale. Per l’osservazione5.3.2si considerano γ
1e γ2 limite.
Ma allora z appartiene a∑i∈γ1[xi, xi+1]oppure a∑j∈γop2 [yj, yj+1].
Da cui[x, y] = ∑i∈γ
1[xi, xi+1] +∑j∈γ2op[yj, yj+1], e quindi [x, y] ∈V. As-
surdo.
Dunque c[L]è denso. Se fosse anche infinito, allora L non sarebbe spar- so: prendendo infatti un elemento da ogni classe di equivalenza della partizione di c[L], si definirebbe un sottordine di L denso e infinito. Assurdo.
Dunque c[L] '1.
A questo punto si scrive L come somma indicizzata da un ordinale o dall’inverso di un ordinale di intervalli.
Per il lemma5.3.2, esistono due successioni(x
i)i∈φ1 e (yj)j∈φ2 rispetti-
vamente cofinale e coiniziale con L. Ma allora L=∑i∈φ
1[xi, xi+1] + [x0, y0] +∑j∈φop2 [yj, yj+1].
Dunque V è effettivamente la classe degli ordini totali sparsi.
5.4
teorema di laver
Si definisce un ranking parziale sulla classe degli ordini totali sparsi utiliz- zando il rango rk definito dal teorema di classificazione di Hausdorff5.3.1:
L≺0 M ⇐⇒ L M ∧ rk(L) <rk(M)
Teorema 5.4.1 (Laver [9]): La classe degli ordini totali sparsi (V,), ordinata
per immersione, è un BQO.
Dimostrazione. Sia A⊆N infinito e sia f : [A]ω →V un V-array cattivo. Per
il Minimal Bad Array Lemma (4.2.1), lo si può supporre minimale. Si scrive
f(X) =LX.
Per la classificazione di Hausdorff, gli elementi L di V possono essere di 3 tipi:
1. L è finito.
5.4 teorema di laver 41
3. L è somma indicizzata dall’inverso di un ordinale di elementi di rango inferiore.
Si può allora costruire una funzione H : V →V che mappa un ordine totalee sparso L in:
• Se L è un ordine finito, allora H(L) = (L), la successione formata solo da sé stesso.
• Se rk(L) > 0, allora H(L) = (Li)i∈α è una successione tale che L =
∑i∈αLi, oppure L=∑i∈αopLi e, per ogni i ∈α, rk(Li) <rk(L).
Siano V1 ={L∈ V|L è finito}, V2={L∈V |H(L) = (Li)i∈α ∧ L= ∑i∈αLi}
e V3 = {L∈V |H(L) = (Li)i∈α ∧ L= ∑i∈αopLi}. Questi inducono una 3-
colorazione di V, che induce una 3-colorazione di [A]ω data da [A]ω =
f−1(V
1) ∪ f−1(V2) ∪f−1(V3).
Per il teorema di Galvin Prikry (3.2.1), esiste un V-sotto-array cattivo f|[ B]ω
monocromatico.
Senza perdita di generalità, si può supporre che f([B]ω) ⊆V
2.
Si definisce il eV-array cattivo g= H◦f|[B]ω.
Per ogni X ∈ [B]ω, si scrive g(X) =s
X= (LiX)i∈αX.
Il fatto che g sia un eV-array è banale. Si osserva che g è cattivo:
Se per assurdo non lo fosse, allora esisterebbe X ∈ [B]ω tale che g(X) ≤
g(X∗), ossia sX≤T sX∗.
Allora esisterebbe un’immersione h : αX → αX∗ tale che, ∀i ∈ αX, dovrebbe
valere LiX LhX(∗i). Ma allora f(X) = LX = ∑i∈αX LiX ∑i∈α
X∗ L
i
X∗ = LX∗ =
f(X∗).
Per il lemma di Nash-Williams (4.2.2), esiste un V-array cattivo G : [B0]ω →
V, con B0 ⊆ B infinito, tale che, per ogni X ∈ [B0]ω, vale G(X) ∈ s
X =
(LiX)i∈αX.
Questo significa che per ogni X ∈ [B0]ω, esiste un certo i
X ∈ αX tale che G(X) = LiX X. Siccome rk(L iX X) < rk(LX), allora L iX X ≺0 LX, ossia G(X) ≺0 f(X).
Dunque G<∗ f , contro la minimalità di f .
La congettura di Fraïssé è allora un corollario del teorema di Laver. Corollario 5.4.1 (Fraïssé): La classe Tpnum dei tipi d’ordine numerabili, ordi- nata per immersione, è un BQO.
Dimostrazione. Si partiziona Tpnum come:
Tpnum ={τ∈Tpnum|ητ} ∪τ∈Tpnum ητ
Il primo insieme è un BQO in quanto, per il lemma di Cantor5.1.1, tutti i
suoi elementi sono equivalenti tra loro.
Il secondo è l’insieme dei tipi d’ordine numerabili sparsi, che è contenuto nella classe dei tipi d’ordine sparsi. Quest’ultima è BQO per il teorema di Laver 5.4.1.
42 congettura di fraïssé
Si mostra infine che la congettura di Fraïssé non si può estendere ai tipi d’ordine non numerabili.
Ciò fu dimostrato da Sierpi ´nski (1950), ispirato da un risultato di Dushnik e Miller (1940) [2,21].
Teorema 5.4.2 (Dushnik e Miller, [2]): L’insieme dei reali R contiene un sot-
toinsieme denso E che non è isomorfo ad alcuno dei suoi sottoinsiemi propri.
Dimostrazione. La costruzione di E è fatta con una sorta di argomento diago- nale, quello che poi ha ispirato Sierpi ´nski nel trovare un controesempio alla congettura di Fraïssé nel caso di ordini non numerabili.
Innanzitutto si può notare che gli isomorfismi tra R ed un suo sottoinsie- me (o, equivalentemente, le immersioni da R in sé ) sono funzioni mono- tone e strettamente crescenti. Esse hanno cardinalità c = 2ℵ0. Sia dunque
Ω = {fα |α<c} l’insieme di tali funzioni, esclusa l’identità. Si può osser-
vare che i punti fissi di tali funzioni non possono essere densi ovunque. Di conseguenza, per ogni α<c, l’insieme{p∈R| fα(p) 6= p}ha cardinalità c.
Si definiscono ora induttivamente due sottoinsiemi come segue:
passo base Sia x0 ∈ R tale che f0(x0) 6= x0. Siano X0 = {x0} e F0 =
{f0(x0)}.
passo induttivo Si supponga di aver definito, per ogni β <α, gli insiemi
Xβ = {xγ |γ≤ β}e Fβ ={fγ(xγ)|γ≤β}, che siano disgiunti e tali
che δ6=γ =⇒ xδ 6=xγ.
Siccome esistono c punti tali che fα(x) 6= x, se ne può scegliere uno
tale che∀β < αvalga x 6= xβ, x 6= fβ(xβ)e fα(x) 6= xβ. Sia xα un tale
punto. Siano Xα = S β<αXβ∪ {xα}e Fα = S β<αFβ∪ { fα(xα)}. Sia X = S
α<cXα. Innanzitutto si può notare che X è denso in R. Sia infatti
I un qualsiasi intervallo di R. Esiste allora un’immersione definita come l’identità in R\I e diversa dall’identità in I. Essa deve appartenere a Ω, dunque sarà una fα per qualche α<c. Allora xα ∈ I∩X.
Inoltre X non può essere isomorfo ad un suo sottoinsieme proprio. Se lo fosse, sia f un tale isomorfismo diverso dall’identità. Siccome X è denso in