In questo paragrafo si mostra che la classe delle successioni transfinite di un Better-Quasi-Order è effettivamente un Better-Quasi-Order.
Nash-Williams ha sviluppato una potente tecnica per vedere se un quasi ordine sia un BQO oppure no.
Ha dimostrato che, dando un particolare ordinamento agli array cattivi di un dato quasi ordine, ognuno di essi ne ammette uno più piccolo e minima- le.
La tecnica per dimostrare se un quasi ordine sia un BQO o no consiste dun- que nel supporre per assurdo che non lo sia. Ciò significa allora che am- mette un array cattivo. Questo può essere supposto minimale. Dunque, trovandone uno strettamente più piccolo, si ha l’assurdo.
Ma quale ordinamento si deve definire sugli array cattivi? Il più intuitivo sarebbe quello termine a termine, ossia
f ≤ g ⇐⇒ dom(f) ⊆dom(g) ∧ ∀X∈dom(f) f(X) ≤g(X)
f <g ⇐⇒ f ≤g ∧ ∃X∈dom(f) f(X) <g(X)
In questo modo, però, l’enunciato non può essere vero. Se<non fosse ben fondata, potrebbe esistere una successione infinita strettamente decrescente
f1(X) > f2(X) >. . .
Di conseguenza anche la successione degli fn potrebbe essere strettamente
decrescente.
Inoltre, se anche<fosse ben fondata, si potrebbe comunque avere un nume- ro infinito di catene finite f1(X) > · · · > fn(X).
Ciò potrebbe comunque rendere la successione degli fn strettamente decre-
scente.
Per superare la seconda osservazione, si definiscono allora sugli array cattivi di un certo quasi ordine, due ordini, uno stretto e uno largo, non corrispon- denti, ossia:
f ≤ g ⇐⇒ dom(f) ⊆dom(g) ∧ ∀X∈dom(f) f(X) ≤g(X)
f < g ⇐⇒ dom(f) ⊆dom(g) ∧ ∀X∈dom(f) f(X) <g(X)
Per superare la prima osservazione, si considera una relazione più forte di del quasi ordine stretto e che sia ben fondata:
Definizione 4.2.1: Sia (Q,≤) un quasi ordine. Una relazione d’ordine stretta<0 di Q è un ranking parziale se:
• <0 è ben fondato.
4.2 stabilità sulle successioni transfinite 29
Si può osservare che un quasi ordine stretto è in realtà un ordine parziale, di conseguenza lo è anche un ranking parziale.
Si definisce il ranking parziale largo:
x ≤0 y ⇐⇒ x <0 y ∨ x=y
Dato un quasi ordine (Q,≤) dotato di un ranking parziale <0, si defini- scono gli ordini sugli array cattivi come segue:
Definizione 4.2.2 (Ordine largo): Siano A, B⊆N infiniti.
Siano f : [A]ω→ Q e g : [B]ω →Q due Q-array cattivi.
Si dice che f ≤∗ g se:
• A⊆ B
• ∀X∈ [A]ω vale f(X) ≤0 g(X)
Definizione 4.2.3 (Ordine stretto): Siano A, B⊆N infiniti.
Siano f : [A]ω→ Q e g : [B]ω →Q due Q-array cattivi.
Si dice che f <∗ g se:
• A⊆ B
• ∀X∈ [A]ω vale f(X) <0 g(X)
Lemma 4.2.1 (Minimal Bad Array): Sia (Q,≤) un quasi ordine. Sia <0 un suo ranking parziale. Allora per ogni Q-array cattivo f0: [A0]ω → Q, esiste un
Q-array cattivo minimale f : [A]ω →Q tale che f ≤∗ f
0.
Dimostrazione. La dimostrazione è fatta per assurdo: supponendo che la te- si non sia vera, si dimostra l’esistenza di una catena infinita strettamente decrescente di(Q,<0), ottenendo l’assurdo in quanto<0 è ben fondato.
Si deve costruire quindi una successione di Q-array cattivi fn: [An]ω →Q
strettamente decrescente per cui esista un certo insieme Z ∈ T
n∈ω[An] ω.
In tal modo (fn(Z))n∈ω sarebbe la catena infinita strettamente decrescente
cercata.
Trovare una successione infinita strettamente decrescente(fn)n∈ωè banale;
la condizione che però esista Z ∈T
n∈ω[An]
ωnon lo è affatto.
Si costruisce allora una ω1-successione di Q-array "quasi" strettamente
decrescente (il significato di quel "quasi" è spiegato di seguito).
Mostrando poi che la ω1-successione dei domini ammette una ω- sotto-
successione con intersezione non vuota, si avrà allo stesso modo la tesi. Notazione 4: Si scrive A⊆∗ B per dire che A\B è finito.
successione di Q-array cattivi Si costruisce induttivamente una ω1- suc-
cessione di Q-array cattivi fα: [Xα]ω → Q "quasi" strettamente decre-
scente, ossia tale che∀α< β<ω1 • Xβ ⊆∗ Xα
30 stabilità dei bqo
• ∀α∈ ω1 Xα ⊆ X0
ordinale successore Nel caso di un ordinale successore β=α+1,
si osserva che fα ≤∗ f0 e per ipotesi f0 non ha elemento minimale
più piccolo. Ciò significa che fα non è minimale e dunque esiste
g<∗ fα. Si pone fβ = g.
ordinale limite Sia δ∈ω1 un ordinale limite.
Si costruisce innanzitutto un insieme X tale che[X]ω possa funge-
re da dominio per fδ.
Deve rispettare le seguenti richieste:
• X è infinito
• X⊆X0
• ∀α<δ X⊆∗ Xα
Lo si costruisce induttivamente.
Innanzitutto δ è un ordinale numerabile, dunque esiste una bige- zione h :N→δ.
Per ogni i ∈ N, sia allora xi ∈ T
j≤iXh(j) . Questa intersezione è
infinita (è un’intersezione finita di insiemi "quasi" contenuti l’uno nell’altro); si può allora fare anche in modo da non ripetere gli xj,
ossia prendere xi ∈/ xj
j<i .
Sia X= {xi |i∈N}. Esso soddisfa le ipotesi richieste: per ogni α< δvale infatti X\Xα ⊆ xi
i≤h−1(α) , che è finito.
Si osserva a questo punto che per ogni Z ∈ [X]ω, esiste solo un
numero finito di Xαche lo contengono, altrimenti esisterebbe una
successione fα(Z)infinita e strettamente decrescente di(Q,<0).
Dunque gli insiemi LZ = {α<δ|Z⊆ Xα} sono finiti, e quindi
ammettono un massimo.
Sia g : [X]ω → Q la funzione tale che g(Z) = f
α(Z), con α =
max LZ.
Questa è un Q-array cattivo:
È un Q-array in quanto le controimmagini dei singoletti sono bore- liane, infatti, affinché un determinato Z∈ [X]ω appartenga ad un
certo g−1(q), c’è bisogno che esista un ordinale α per cui fα(Z) =q
e tale che∀α< β<δ, Z /∈ [Xβ]ω.
Dunque la controimmagine di un singoletto sarà data da g−1(q) = [ α<δ fα−1(q) ∩ [ α<β<δ [Xβ] ω{
che è unioni, intersezioni e complementari di boreliani. Dunque è un boreliano.
È cattivo in quanto, se per assurdo non lo fosse, allora esistereb- be Z ∈ [X]ω tale che g(Z) ≤ g(Z∗). Dunque esisterebbero due
ordinali α, β< δ tali che g(Z) = fα(Z)e g(Z∗) = fβ(Z∗). Poiché
Z∗ ⊆ Z, allora α≤β. Ma allora fα(Z) =g(Z) ≤g(Z ∗) = f β(Z ∗) ≤0 f α(Z ∗)
4.2 stabilità sulle successioni transfinite 31
ossia fα non sarebbe cattiva.
Allora g è un Q-array cattivo tale che g≤∗ f
0, che non ha minima-
le. Sia allora fδ <∗ g.
Dalla ω1-successione di Q-array cattivi, si ottiene anche una successio-
ne (Xα)α∈ω1 di elementi di [X0]
ω tali che ∀
α < β < ω1, vale Xβ ⊆
∗
Xα.
successione di insiemi Si mostra ora che la ω1-successione(Xα)α∈ω1 dei
domini ammette una ω-sottosuccessione(Xα)α∈Σed un insieme infini-
to Z ∈ [X0]ω tali che Z⊆Tα∈ΣXα.
Si costruiscono Z eΣ induttivamente. Più precisamente si costruiscono, ad ogni passo, sn l’insieme dei "primi" n elementi di Z e Fn l’insieme
dei "primi" n elementi diΣ.
Si definisce anche la successione(An)n∈ω ⊆ [ℵ1]ω1 come un insieme di
ordinali γ tali che tutti gli elementi di snappartengono a Xγ.
passo base Siano F0 =∅, s0 =∅, A0 = ℵ1.
passo induttivo Sia innanzitutto Fn+1 = Fn∪ {γ}, dove γ è un
qualsiasi ordinale in An.
Per costruire sn+1, si sceglie un elemento in Qn = Tα∈Fn+1Xα
\
sn. Tale insieme è infinito in quanto è intersezione finita di insiemi
"quasi" contenuti uno nell’altro, meno un insieme finito.
Per lo stesso motivo, anche Qn∩Xβ è infinito per ogni β ∈ ω1.
Sia allora G : An → Qn una funzione (di scelta) che mappa ogni
ordinale α∈ An in un certo elemento mα ∈Qn∩Xα.
Poiché Qnè numerabile e Anha cardinalitàℵ1, allora esiste un ele-
mento m ∈ Qn tale che G−1(m) ha cardinalità ℵ1. Siano An+1 =
G−1(m)e sn+1=sn∪ {m}.
Siano infine Σ= S
n∈NFne Z =Sn∈Nsn.
La successione(fα(Z))α∈Σ di elementi di Q è dunque infinita e strettamente
decrescente rispetto al ranking parziale. Assurdo.
Si dimostra poi, utilizzando il Minimal Bad Array Lemma, che le successio- ni transfinite di un BQO, ordinate termine a termine, formano un BQO. In particolare questo fatto può essere visto come corollario di un importante lemma, detto di Nash-Williams. Dato un quasi ordine (Q,≤) e A ⊆ N in-
finito, si può dimostrare che, da un eQ-array cattivo s : [A]ω →
e
Q, si ricava un particolare Q-array cattivo f : [B]ω → Q, con B ⊆ A infinito, tale che
∀X∈ [B]ω vale f(X) ∈s(X).
Lemma 4.2.2 (Nash-Williams): Sia(Q,≤Q)un quasi ordine, sia A⊆N infini-
to. Sia s : [A]ω →
e
Q un eQ-array cattivo.
Allora esiste B ∈ [A]ω ed esiste un Q-array cattivo f : [B]ω → Q tale che∀X ∈
32 stabilità dei bqo
Dimostrazione. Innanzitutto si osserva che per un tale Q-array cattivo deve valere f(X) ∈ s(X). Dunque devono esistere degli ordinali θX ∈ lh(s(X))
per cui f(X) =s(X)(θX).
Si lavorerà dunque con le restrizioni degli s(X). Di conseguenza entrerà in gioco il lemma1.7.1.
Poiché s è cattiva, allora∀X∈ [A]ω vale che s(X) s(X∗).
Applicando il lemma 1.7.1, per ogni X ∈ [A]ω esiste un ordinale θX ∈
lh(s(X))tale che s(X) θX≤ s(X∗)e s(X) (θX+1) s(X∗).
Sia s0: [A]ω →
e
Q il eQ-array cattivo definito come s0(X) =s(X) θX.
Se consideri su eQ il seguente ranking parziale
u <0 v ⇐⇒ ∃θ∈ lh(v)tale che u= vθ
Per il Minimal Bad Array Lemma (4.2.1), si può considerare s minimale.
Chiaramente s0 <∗ s, dunque s0 è un eQ-array buono. Per la proposizione4.1.1, esiste un eQ-sotto-array s0|[
B]ω tale che ∀X ∈ [B]ω
vale che s0(X) ≤s0(X∗), ossia s(X) θX≤ s(X∗) θX∗.
Mettendo insieme questo e il fatto che s(X) (θX+1) s(X∗), si ricava che
s(X)(θX)non può essere minore o uguale di alcuno degli elementi di s(X∗)
successivi a θX∗ (altrimenti un tale elemento potrebbe fungere da immagine
di s(X)(θX)per un’immersione). In particolare s(X)(θX) Q s(X∗)(θX∗).
Allora f : [B]ω →Q tale che f(X) =s(X)(
θX)è il Q-array cercato.
La stabilità dei BQO per il passaggio alle successioni transfinite è dunque una banale conseguenza.
Teorema 4.2.1: Sia(Q,≤)un BQO. Allora la classe delle successioni transfinite e
Q è un BQO.
Dimostrazione. Se non lo fosse, allora esisterebbe un eQ-array cattivo. Per il lemma di Nash-Williams (4.2.2), esisterebbe un Q-array cattivo.
5
C O N G E T T U R A D I F R A Ï S S É
In questo capitolo conclusivo si vedrà la dimostrazione della congettura di Fraïssé.
A tal fine si distingueranno i tipi d’ordine numerabili in due categorie: i tipi d’ordine nei quali si immerge η e quelli nei quali non si immerge.
Nel primo paragrafo si studieranno i primi, scoprendo che sono tutti equiva- lenti tra loro. Essi formeranno dunque un WQO (in realtà anche un BQO). Nel secondo paragrafo si vedranno quelli del secondo tipo, ossia i tipi d’or- dine sparsi, e si mostrerà che sono un WQO.
Per quest’ultimo punto sarà di fondamentale importanza la classificazione di Hausdorff dei tipi d’ordine sparsi [6]. La natura "infinitaria" di tale costruzio-
ne renderà però necessario affrontare il problema utilizzando la sottoclasse dei Better-Quasi-Order.
Laver [9] ha dimostrato che la classe degli ordini totali sparsi (anche non
numerabili) è un BQO.