In questo paragrafo il risultato ottenuto sugli aperti verrà esteso ai boreliani della topologia2.4.4. La dimostrazione sarà fatta per induzione utilizzando
la gerarchia sui boreliani (vedi [7], pagina 140 ).
In realtà si mostra una proprietà più forte, ossia che i boreliani sono insiemi di Ramsey completi.
Definizione 3.2.1: Un insieme A ⊆ [N]ω è detto di Ramsey completo se per
ogni s ∈ [N]<ω e per ogni U ∈ [N]ω esiste un insieme V ∈ [U]ω tale che
[s, V] ⊆A oppure [s, V] ∩A=∅.
È effettivamente una proprietà più forte: scegliendo s = ∅ e U = N, un
insieme di Ramsey completo è anche di Ramsey.
Lemma 3.2.1: Ogni aperto A ⊆ [N]ω è un insieme di Ramsey completo.
Dimostrazione. Siano s ∈ [N]<ω e U ∈ [N]ω qualsiasi. Poiché U è un sot-
3.2 i boreliani sono insiemi di ramsey 23
F :[N]ω→ [U]ω definita come F(V) ={f(x)|x∈ V}.
Sia inoltre gs: [U]ω → [N]ω la funzione gs(V) = s∪V/s. Essa è una
funzione continua, e dunque anche gs◦F lo è.
Ciò significa che(gs◦F)−1(A)è un aperto di[N]ω, e dunque è un insieme
di Ramsey.
Allora esiste W ∈ [N]ω tale che [W]ω è contenuto in (g
s◦F)−1(A) oppure
ne è disgiunto. Dunque F([W]ω) = [f(W)]ω è contenuto in g−1
s (A) oppure
ne è disgiunto. Ma allora gs([f(W)]ω) = [s, f(W)]è contenuto in A oppure
ne è disgiunto. Si pone V = f(W).
Teorema 3.2.1 (Galvin e Prikry, 1973): I boreliani della topologia 2.4.4 sono insiemi di Ramsey completi.
Dimostrazione. La dimostrazione è fatta per induzione sul rango dato dalla gerarchia sui boreliani.
passo base È il lemma 3.2.1. Inoltre la chiusura per complementare è
banale.
passo induttivo Sia A = Sn∈NAn, dove gli insiemi An sono boreliani di
rango minore.
Siano dunque s ∈ [N]<ω e U ∈ [N]ω due insiemi qualsiasi.
La dimostrazione consiste nel costruire induttivamente un insieme V ∈ [U]ωtale che A∩ [V]ωsia aperto in[V]ω. Esso sarà dunque un insieme
di Ramsey completo, da cui esisterà un insieme X ∈ [V]ω ⊆ [U]ω tale
che[s, X]sia contenuto in A o ne sia disgiunto.
passo base Poiché l’insieme ℘(s) è finito, se ne possono numerare
gli elementi.
Per induzione gli insiemi An sono di Ramsey completi. Usando
ripetutamente questa proprietà per tutti gli sj ∈ ℘(s), si ottiene un
insieme V0 ⊆U/s tale che, per ogni sj, vale che[sj, V0]è contenuto
oppure disgiunto da A0. Sia n0 =min V0.
passo induttivo Siano definiti Vi e n0 < · · · < ni e sia Si = ℘(s∪
{n0, . . . , ni}). Questo è finito e dunque se ne possono numerare
gli elementi.
Per induzione gli insiemi An sono di Ramsey completi. Usando
ripetutamente questa proprietà per tutti gli sj ∈ Si, si ottiene un
insieme Vi+1 ⊆ Vi/{ni}tale che, per ogni sj, vale che[sj, Vi+1]è
contenuto oppure disgiunto da Ai+1. Sia ni+1=min Vi+1.
Sia infine V = s∪ {ni |i∈N}. Allora per ogni i ∈ N vale che
Ai∩ [V]ω è un aperto di[V]ω.
Per dimostrare ciò, si vede che ogni suo elemento ha un intorno che è aperto rispetto a[V]ω e contenuto in A
i∩ [V]ω.
Sia Y ∈ Ai∩ [V]ω. Sia s0 = (s∪ {n0, . . . , ni}) ∩Y.
Per costruzione di V, vale che [s0, V] ⊆ Ai oppure ne è disgiunto. Poi-
ché però Y ∈ Ai∩ [s0, V], quest’ultimo caso non può essere. Allora
[s0, V]è l’intorno cercato. Dunque A∩ [V]ω =S
n∈ω(An∩ [V]
ω)è un aperto di[V]ω, da cui è un
24 teorema di galvin e prikry
Allora esiste X ∈ [V]ω ⊆ [U]ω tale che [s, X] ⊆ A oppure [s, X] ∩A∩
[V]ω = ∅. Poiché [s, X] ⊆ [V]ω, quest’ultima affermazione equivale a
4
S T A B I L I T À D E I B Q O
In questo capitolo si vedranno le migliori proprietà di stabilità dei Better- Quasi-Order rispetto a quelle dei Well-Quasi-Order.
Nella prima parte si verificherà che i quasi ordini generati dalle operazioni "finitarie" (par. 1.7) di Better-Quasi-Order, rimangono Better-Quasi-Order.
Nella seconda si vedrà che effettivamente la classe delle successioni tran- sfinite di un Better-Quasi-Order rimane un Better-Quasi-Order.
Per tale scopo, verranno dimostrati due teoremi fondamentali: il Minimal Bad Array lemma ed il teorema di Nash-Williams.
Si introduce la seguente notazione: dato un sottoinsieme non vuoto X ⊆ N, si scrive X∗ = X\ {min X}.
Prima di iniziare il capitolo, si fa un’importante osservazione. È risaputo che N è isomorfo a tutti i suoi sottoinsiemi infiniti.
Dato allora un quasi ordine (Q,≤) ed un qualsiasi sottoinsieme infinito A ⊆ N, una funzione f : [A]ω → Q che sia Borel-misurabile (rispetto alla
topologia indotta) e con immagine numerabile può essere vista come un Q- array: se h : N→A è l’isomorfismo taN e A, ponendo H : [N]ω → [A]ωtale
che H(X) = {h(x)|x ∈X}, allora f può essere identificata con il Q-array f◦H.
Definizione 4.0.1: Dato un quasi ordine(Q,≤), si dirà Q-array una qual- siasi funzione f : [A]ω → Q, con A ⊆ N infinito, che sia Borel-misurabile
(rispetto alla topologia indotta) e con immagine numerabile.
In tale modo si può dare anche una buona definizione di Q-sotto-array. Definizione 4.0.2: Dati(Q,≤)un quasi ordine e f : [A]ω →Q un Q-array.
Per ogni B⊆ A infinito, la funzione f|[B]ω è detta Q-sotto-array di f .
4.1
prime proprietà di chiusura
Il paragrafo si apre con un’applicazione del teorema di Galvin e Prikry (3.2.1)
agli array di un quasi ordine.
Lemma 4.1.1: Sia(Q,≤)un quasi ordine. Sia R una relazione binaria su Q. Allora ogni Q-array f : [N]ω →Q ammette un Q-sotto-array f|
[B]ωtale che,∀X∈ [B]ω, la relazione f(X)R f(X∗)vale sempre oppure non vale mai.
Dimostrazione. Sia s : [N]ω → [N]ω la funzione di shift tale che s(X) = X∗.
Questa è continua, infatti s−1([s0,N]) =S
n<min s0[{n} ∪s0,N].
Sia allora L : [N]ω → Q×Q tale che L(X) = (f(X), f s(X)). Questa è un
26 stabilità dei bqo
(Q×Q)-array in quanto L−1(p, q) = f−1(p) ∩ (f s)−1(q) che è intersezione
finita di boreliani, ossia è un boreliano. Si partiziona allora[N]ω = C
1tC2, dove C1 = {X| f(X)R f(X∗)}e C2 =
{X| f(X) 6R f(X∗)}.
Si osserva che C1 = L−1({ (p, q)| p R q}) e C2 = L−1({ (p, q)| p 6R q}),
dunque sono boreliani.
Si conclude allora applicando il teorema di Galvin e Prikry3.2.1.
Il lemma permette di dare altre definizioni equivalenti per i BQO. In particolare
Proposizione 4.1.1: Sia(Q,≤)un quasi ordine. Sono fatti equivalenti:
1. (Q,≤)è un Better-Quasi-Order.
2. Tutti i Q-array continui sono buoni.
3. Ogni Q-array ammette un Q-sotto-array per cui vale sempre f(X) ≤ f(X∗).
Dimostrazione. Si vedono le varie inclusioni:
1 ⇒ 2 È banale.
2 ⇒ 1 È una conseguenza del teorema di Mathias [14], dimostrato di segui-
to.
3 ⇒ 1 È banale.
1 ⇒ 3 È una conseguenza del lemma 4.1.1 prendendo come relazione bi-
naria ≤. Infatti esiste un sotto-array di f per cui vale sempre o non vale mai f(X) ≤ f(X∗). Il caso in cui non vale mai non è possibile, altrimenti il sotto-array sarebbe cattivo.
Teorema 4.1.1 (Mathias, 1977): Sia f : [N]ω → Q un Q-array. Allora esiste
B⊆ A infinito tale che f|[B]ω è un Q-array continuo.
Dimostrazione. Innanzitutto si osserva che Im f è numerabile, dunque se ne possono numerare gli elementi. Sia Im f ={qi |i∈ N}.
Si costruisce B induttivamente:
passo base Sia A0 = A e sia n0 =min A0.
passo induttivo Siano definiti Ai e n0< · · · <ni.
Innanzitutto si osserva che Si = ℘({n0, . . . , ni})è finito.
Poiché f−1(qi) è boreliano, si può applicare il teorema di Galvin e Prikry 3.2.1 ripetutamente per tutti gli elementi di Si e si ottiene un
insieme Ai+1 ⊆ Ai/{ni} tale che, per ogni s ∈ Si, vale [s, Ai+1] ⊆
f−1(q
i)oppure[s, Ai+1] ∩f−1(qi) =∅. Sia ni+1 =min Ai+1.
Sia infine B= {ni |i∈N}. Allora per ogni X ∈ [B]ω vale che X ∈ f−1(qi)
se e solo se[s, Ai+1] ⊆ f−1(qi), dove s = X∩ {n0, . . . , ni}. Dunque [B]ω∩
4.1 prime proprietà di chiusura 27
Si dimostra ora la stabilità dei BQO per le varie operazioni "finitarie", definite nel paragrafo1.7.
Lemma 4.1.2 (Sottordini): Sia(Q,≤) un BQO. Allora ogni sottordine A ⊆ Q è un BQO.
Dimostrazione. Sia f : [N]ω → A un A-array. Esso è anche un Q-array,
dunque è buono.
Lemma 4.1.3 (Omomorfismi): L’immagine di un omomorfismo di un BQO è un BQO.
Dimostrazione. Siano Q e B due quasi ordini e sia Q un BQO. Sia g : Q →
B un omomorfismo. Si costruisce allora (con l’assioma della scelta) una funzione inversa g0: Im g → Q, scegliendo l’immagine di ogni elemento x∈Im g nell’insieme g−1(x). Questa è un’immersione.
Allora per ogni array f : [N]ω → Im g, g0f è un Q-array. Dunque ∃X ∈
[N]ω tale che g0f(X) ≤g0f(X∗). Da cui f(X) ≤ f(X∗).
Lemma 4.1.4 (Unione finita): L’unione di due sottordini che sono BQO è un BQO.
Dimostrazione. Sia f : [N]ω →A∪B un array. Allora si partiziona[N]ωcome:
[N]ω =C
1tC2
dove C1 ={X∈ [N]ω | f(X) ∈ A}e C2={X∈ [N]ω | f(X) ∈B}.
Applicando il teorema di Galvin e Prikry3.2.1, si può estrarre un Q-sotto-
array con immagine contenuta tutta in A oppure tutta in B. In ogni caso, il Q-sotto-array è un array di un BQO, dunque è buono.
Lemma 4.1.5 (Prodotto cartesiano finito): Il prodotto cartesiano finito di BQO è un BQO.
Dimostrazione. Si mostra il caso n =2. La generalizzazione è banale.
Siano(A,≤A)e (B,≤B)due BQO. Sia Q = A×B. Sia f : [N]ω → Q un
Q-array.
Innanzitutto si osserva che le proiezioni πA: Q → A e πB: Q → B sono
continue in quanto Q ha la topologia discreta. Allora le funzioni πAf e πBf
sono rispettivamente A-array e B-array. Si può scrivere f = (πAf , πBf).
Si definisce su Q la relazione binaria (a, b)RA(a0, b0) ⇐⇒ a≤A a0.
Per il lemma4.1.1, esiste un Q-sotto-array per cui vale sempre o non vale mai
f(X)RAf(X∗). Ciò significa che vale sempre o non vale mai πAf(X) ≤A πAf(X∗).
Poiché A è BQO e πAf è A-array, allora f si restringe ad un Q-sotto-array
f|[V]ω per cui vale sempre f(X)RA f(X∗).
Analogamente si definisce una relazione binaria(a, b)RB(a0, b0) ⇐⇒ b≤B
b0 e come prima si restringe f|[V]ω ad un ulteriore Q-sotto-array f|[W]ω per
28 stabilità dei bqo