Dalla congettura di Fraisse' al teorema di Laver

Universit`

a di Pisa

Tesi di laurea triennale

Dalla congettura di Fra¨ıss´

e

al teorema di Laver

Candidato:

Alberto Caccavale Matricola 502557

Relatore:

prof. Alessandro Berarducci

I N D I C E

Introduzione iii

1 ordini e quasi ordini 1

1.1 Prime definizioni 1

1.2 Operazioni tra ordini totali 2

1.3 Tipi d’ordine 2

1.4 Operazioni tra tipi d’ordine 3

1.5 Ordinare la classe dei tipi d’ordine 4

1.6 I quasi ordini 4

1.7 Operazioni tra quasi ordini 5

2 wqo e bqo 9

2.1 Definizioni di WQO 9

2.2 Stabilità dei WQO 11

2.3 Instabilità dei WQO: il controesempio di Rado 14

2.4 Introduzione ai BQO 17

3 teorema di galvin e prikry 21

3.1 Gli aperti sono insiemi di Ramsey 21

3.2 I boreliani sono insiemi di Ramsey 22

4 stabilità dei bqo 25

4.1 Prime proprietà di chiusura 25

4.2 Stabilità sulle successioni transfinite 28

5 congettura di fraïssé 33

5.1 Tipi d’ordine numerabili 33

5.2 Tipi d’ordine sparsi 36

5.3 Classificazione di Hausdorff 37

5.4 Teorema di Laver 40

Bibliografia 45

I N T R O D U Z I O N E

La tesi tratterà di una famosa congettura sulla teoria degli ordini, riguardan-te la classe degli ordini totali numerabili. La congettura è stata enunciata da Roland Fraïssé [4] nel 1948 ed è stata risolta da Richard Laver [9] nel 1971.

L’obiettivo che si prefigge la tesi è quello di presentare tale dimostrazione introducendo i risultati che l’hanno permessa, in particolare la teoria dei Well-Quasi-Order (WQO) e quella dei Better-Quasi-Order (BQO).

Dati due ordini totali A e B, si dice che A si immerge in B, e si indica con A  B, se esiste un’immersione h : A → B, ossia una funzione iniettiva che preserva gli ordini.

Si può osservare che una tale relazione è riflessiva e transitiva, ma non an-tisimmetrica. Una relazione riflessiva e transitiva ma non necessariamente antisimmetrica è detta in letteratura quasi ordine.

Dato un quasi ordine (Q,≤), si può definire su Q un quasi ordine stretto ponendo x<y se x ≤y e yx.

La congettura di Fraïssé afferma che la classe degli ordini totali numerabili ordinata per immersione non ammette catene infinite strettamente decre-scenti, ossia non esistono infiniti ordini totali numerabili tali che A1 A2 

. . . ; né anticatene infinite, ossia non esistono infiniti ordini totali numerabili tali che i6=j implica Ai Aj e Aj  Ai.

Un quasi ordine con tali caratteristiche è detto Well-Quasi-Order (WQO). La congettura di Fraïssé può allora essere enunciata in termini di WQO: il quasi ordine dato dalla classe degli ordini totali numerabili, ordinata per im-mersione, è un WQO.

Per dimostrarla, si osserva innanzitutto che gli ordini totali numerabili si possono dividere in due categorie:

• Gli ordini totali numerabili nei quali si immergeQ.

• Gli ordini totali numerabili nei quali non si immergeQ.

La prima categoria, grazie ad un teorema di Cantor che dimostra che tutti gli ordini totali numerabili si immergono in Q, è formata da elementi che si immergono a vicenda l’uno nell’altro e "massimali" rispetto agli altri, e dunque formano un WQO.

La parte più laboriosa sarà, allora, la dimostrazione della congettura per la seconda categoria di ordini totali numerabili, detti sparsi.

Lo scopo finale sarà la dimostrazione del teorema di Laver: la classe degli or-dini totali sparsi (anche non numerabili) è un WQO.

Un primo teorema sulla struttura degli ordini totali sparsi è dovuto ad Hau-sdorff [6] che, in un articolo del 1908, ha dimostrato che la classe degli ordini

totali sparsi può essere costruita per induzione transfinita.

Sia I un insieme ordinato, si può definire la somma ordinata ∑i∈I Ai di una

famiglia {Ai |i∈ I} di ordini totali come l’unione disgiunta ti∈IAi dove

gli elementi di un certo Ai sono tutti minori degli elementi di un certo Aj,

iv introduzione

quando i< j. Il teorema di Hausdorff afferma che la classe degli ordini tota-li sparsi V può essere definita induttivamente come l’unione V = S

α∈OnVα,

a partire dalla classe V0degli ordini finiti, e costruendo Vα come la classe di

tutte le somme ordinate_∑i∈IAi, indicizzate da un ordinale o dall’inverso di

un ordinale, e tali che gli Ai sono elementi di classi precedenti.

La natura "infinitaria" di tale costruzione rende però difficoltoso utilizzare direttamente i WQO: Richard Rado [18] dimostrò, infatti, che tale nozione

non è stabile per operazioni "infinitarie": ha trovato un WQO le cui succes-sioni infinite, ordinate termine a termine, non lo fossero.

Un progresso fondamentale fu compiuto da Crispin Nash-Williams: con due articoli [15, 16] pubblicati a cavallo degli anni 060, introdusse una nozione

basilare, quella di Better-Quasi-Order (BQO).

Questi sono una sottoclasse dei WQO con ottime proprietà. In particolare:

• I WQO più "interessanti" sono anche BQO.

• I BQO sono stabili per le operazioni "infinitarie" menzionate in prece-denza. In particolare la classe delle successioni transfinite di un BQO, dotata dell’ordinamento termine a termine, è un BQO.

In questa tesi verrà usata una definizione equivalente a quella di Nash-Williams, introdotta successivamente da Simpson [22] nel 1985, meno

com-binatoria e più topologica.

Identificando i sottoinsiemi diN con le successioni crescenti dei propri ele-menti, si definisce una topologia sull’insieme delle parti infinite diN, deno-tato da[N]ω_{, prendendo come aperto base l’insieme di tutte le successioni}

crescenti infinite diN che estendono una fissata successione crescente finita. Dato poi un quasi ordine(Q,≤), si dicono array su Q, o Q-array, le funzioni f : [N]ω _{→ Q con immagine numerabile e tali che le controimmagini dei}

singoletti siano insiemi boreliani. Si dice che un Q-array f : [N]ω _{→ Q è}

buono se esiste un elemento X del dominio tale che f(X) ≤ f(X\ {min X}). Si dice cattivo altrimenti.

Un quasi ordine (Q,≤) è detto Better-Quasi-Order (BQO) se tutti i Q-array sono buoni.

Un teorema che permette di sfruttare appieno tale definizione è presen-te in un articolo [5] del 1973 di Fred Galvin e Karel Prikry.

Identifican-do una colorazione finita c : [N]ω _{→ n di [}N_]ω _{con la relativa partizione}

[N]ω _=c−1_{(0) t · · · tc}−1_{(n−1), il teorema dimostra che, se tale partizione}

è formata da boreliani rispetto alla topologia introdotta in precedenza, allora

N ammette un sottoinsieme H infinito omogeneo, ossia tale che[H]ω _è

mo-nocromatico. Questo è una chiara estensione di un noto teorema di Ramsey. A partire da una qualsiasi colorazione finita di Q, si può allora estrarre da un Q-array dato, un Q-sotto-array monocromatico. Ciò è utile per ottenere dei Q-array che abbiano determinate proprietà sulle immagini.

Si dimostra, quindi, un teorema, detto Minimal Bad Array Lemma, che forni-sce una potente tecnica per stabilire se un quasi ordine sia un BQO o no. Dato un quasi ordine(Q,≤), si dice ranking parziale un ordine parziale<0 su Q che non ammette catene infinite strettamente decrescenti e "più forte" del quasi ordine stretto, ossia tale che x <0 y implica x< y. Si scrive che x≤0 y se x<0 y oppure x=y.

introduzione v

Dato un quasi ordine (Q,≤), se <0 è un suo ranking parziale, si possono ordinare i Q-array cattivi termine a termine. Il Minimal Bad Array Lemma afferma che ogni Q-array cattivo ne ammette uno più piccolo e minimale. Tale risultato permette allora di dimostrare un importante teorema di Nash-Williams. Dato un quasi ordine (Q,≤), se la classe delle sue successioni transfinite, ordinate termine a termine, ammette un array cattivo s, allora ne esiste anche uno f su Q tale che, per ogni elemento del dominio di f , vale f(X) ∈s(X). Un corollario di tale teorema è che la classe delle successioni transfinite di un BQO, con l’ordinamento termine a termine, è un BQO. Tutti questi risultati portano infine a dimostrare il teorema di Laver, ossia che la classe V degli ordini totali sparsi, ordinata per immersione, è un BQO. L’idea della dimostrazione è sostanzialmente quella di supporre che esista un V-array cattivo minimale e di costruirne uno strettamente minore. Per il teorema di Hausdorff, ogni ordine totale sparso è finito o si ottiene a partire da ordini di rango minore come somma indicizzata da un ordinale ∑i∈αAi o dall’inverso di un ordinale∑i∈αopAi.

Ciò induce una 3-colorazione della classe V. Supponendo per assurdo che esista un array f : [N]ω_{→V su V cattivo, si può supporre minimale rispetto}

ad un opportuno ranking parziale. Per Galvin e Prikry, a meno di conside-rare un sotto-array, lo si può supporre anche monocromatico. Senza perdita di generalità, si dice che le immagini dell’array sono solo somme indicizzate da ordinali, e non da inversi di ordinali.

Associando alle somme ∑_i∈αAi le successioni (Ai)i∈α, si può costruire un

array g : [N]ω _→

e

V cattivo sulla classe delle successioni transfinite di V, or-dinate termine a termine.

Per il teorema di Nash-Williams, da questo si ricava un altro array G : [N]ω_→

V cattivo su V che, per costruzione, è strettamente minore di f , contraddi-cendone la minimalità.

Nel primo capitolo saranno presentate le prime definizioni e le prime pro-prietà di ordini, ordini totali e quasi ordini.

Nel secondo capitolo saranno presentati i Well-Quasi-Order: se ne dimostre-ranno le proprietà di stabilità per le principali operazioni "finitarie" e la non stabilità per il passaggio alle successioni infinite. Si introdurrà infine, dopo aver parlato dell’idea che vi sta dietro, la nozione di Better-Quasi-Order. Il terzo capitolo sarà dedicato al teorema di Galvin e Prikry.

Nel quarto capitolo verranno mostrate le proprietà di stabilità dei BQO. In particolare saranno dimostrati il Minimal Bad Array Lemma ed il teorema di Nash-Williams.

Il quinto capitolo è dedicato alla dimostrazione della congettura di Fraïssé. Si dimostreranno il teorema di Cantor, il teorema di classificazione di Hausdorff ed il teorema di Laver.

1

O R D I N I E Q U A S I O R D I N I

In questo capitolo saranno date alcune definizioni di base riguardanti gli or-dini, e in particolare gli ordini totali, e ne verranno mostrate alcune buone proprietà.

Si definiranno poi le nozioni di isomorfismo e immersione che permetteran-no di ottenere i tipi d’ordine, dotati di una particolare relazione binaria. Si introdurrà infine il concetto di quasi ordine.

1.1

prime definizioni

Definizione 1.1.1: Un ordine parziale largo su un insieme A è una relazione binaria R⊆ A×A

transitiva (x, y) ∈R∧ (y, z) ∈R =⇒ (x, z) ∈R.

antisimmetrica ∀x, y∈ A (x, y) ∈ R ∧ (y, x) ∈R =⇒ x=y. riflessiva ∀x∈ A (x, x) ∈ R.

Definizione 1.1.2: Un ordine parziale stretto su un insieme A è una relazione binaria R⊆ A×A

transitiva (x, y) ∈R∧ (y, z) ∈R =⇒ (x, z) ∈R. asimmetrica ∀x, y∈ A (x, y) ∈R =⇒ (y, x)∈/R. irriflessiva ∀x ∈ A (x, x)∈/R.

Si nota subito che ogni ordine largo ha un suo corrispettivo ordine stretto e viceversa: basta aggiungere o togliere gli elementi della forma (x, x)a R. In generale, dunque, quando verrà dato un certo ordine, si considererà dato sia l’ordine largo che quello stretto.

Le classiche notazioni sono:

x <y ⇐⇒ (x, y) ∈R quando R è stretto x ≤y ⇐⇒ (x, y) ∈R quando R è largo Definizione 1.1.3: Un ordine è detto totale se

x6=y =⇒ x≤y ∨ y≤ x

Definizione 1.1.4: Un ordine totale è detto buono se ogni suo sottoinsieme non vuoto ammette un elemento minimo.

In genere gli ordini vengono scritti come coppie(A,≤).

Nel seguito verranno approfonditi gli ordini totali, in quanto oggetto di particolare interesse per la tesi.

2 ordini e quasi ordini

1.2

operazioni tra ordini totali

Esistono molti ordini totali che possono essere costruiti a partire da altri. In questo paragrafo verranno illustrati i principali.

Definizione 1.2.1 (Sottordine): Sia(A,≤_A)un ordine totale. Si dice sottor-dine l’orsottor-dine totale definito su un sottoinsieme B⊆ A come

x≤B y ⇐⇒ x, y∈B ∧ x≤A y

Esempio 1: Alcuni esempi conosciuti sonoN⊆Z⊆Q⊆R.

Definizione 1.2.2 (Ordine inverso): Sia(A,≤_A)un ordine totale. Si dice ordine inverso l’ordine totale definito su A come

x≤op_A y ⇐⇒ y ≤_Ax Tale ordine verrà indicato con Aop.

Definizione 1.2.3 (Ordine somma lessicografica): Sia(I,≤_I)un ordine to-tale. Per ogni i∈ I, siano(Li,≤i)ordini totali a due a due disgiunti. Si dice

somma lessicografica l’ordine totale definito suS

i∈ILi come x≤y ⇐⇒        ∃i<_I j x∈ L_i ∧ y ∈L_j oppure ∃i∈ I x, y∈ Li ∧ x ≤i y

Questo ordine si indica con∑_i∈ILi.

Lo si può immaginare pensando di rimpiazzare gli elementi i di I con gli insiemi Li.

Definizione 1.2.4 (Ordine prodotto lessicografico): Siano(I,≤_I)e(A,≤_A)

due ordini totali. Si dice prodotto lessicografico l’ordine totale definito su A×I come∑i∈I(A× {i}).

1.3

tipi d’ordine

Finora gli ordini (totali) sono stati visti come "modi" per disporre gli elemen-ti di un determinato insieme. Dunque potevano essere definielemen-ti solo a parelemen-tire da un insieme già dato.

Non è però difficile riuscire ad immaginarli come una struttura già esistente nella quale andare a posizionare gli elementi di un certo insieme. In questo caso, quindi, gli ordini (totali) sarebbero definiti a priori.

Questa è l’idea dietro alla definizione di tipi d’ordine. Il primo passo è dun-que dun-quello di raggruppare gli ordini totali con la stessa "struttura".

Definizione 1.3.1: Dati due ordini totali(A,≤_A)e(B,≤_B), si dice isomorfi-smo una funzione f : A→B bigettiva e che preserva l’ordine stretto.

1.4 operazioni tra tipi d’ordine 3

Non è difficile osservare che essere isomorfi è una relazione d’equivalenza. Le classi di equivalenza saranno proprio gli ordini totali con la stessa "strut-tura".

Definizione 1.3.2: Le classi di equivalenza della relazione essere isomorfi sono dette tipi d’ordine.

Vengono in genere denotate con delle lettere greche.

Osservazione 1.3.1: La famiglia di tutti gli ordini totali è una classe propria. Di conseguenza non è garantito che i tipi d’ordine siano insiemi.

Possono però essere considerati tali usando il trucco di Scott che sfrutta la gerarchia di Von Neumann ([7], pagina 65).

Notazione 1: I tipi d’ordine più importanti hanno una loro notazione universale:

• Il tipo d’ordine diN è denotato con ω.

• Il tipo d’ordine diZ è denotato con ζ.

• Il tipo d’ordine diQ è denotato con η.

• Il tipo d’ordine diR è denotato con λ.

Osservazione 1.3.2: I tipi d’ordine dei buoni ordini sono gli ordinali.

1.4

operazioni tra tipi d’ordine

Dopo aver costruito alcune operazioni sugli ordini totali, in questo paragra-fo verrà mostrato che il tipo d’ordine di tali costruzioni non dipende dai rappresentanti scelti. Di conseguenza si possono considerare definite anche le operazioni sui tipi d’ordine.

Lemma 1.4.1: Siano (A,≤_A) e (B,≤_B) due ordini totali isomorfi. Allora i rispettivi ordini inversi sono isomorfi.

Dimostrazione. L’isomorfismo tra A e B mantiene anche gli ordini inversi. Lemma 1.4.2: Sia (I,≤_I) un ordine totale. Per ogni i ∈ I, siano (Li,≤i) e

(Mi,≤0i) ordini totali isomorfi a due a due disgiunti. Allora ∑i∈ILi è isomorfo a

∑i∈IMi.

Dimostrazione. Se fi è l’isomorfismo tra Li e Mi, alloraSi∈I fi è un

isomorfi-smo tra le somme.

Grazie a questi lemmi sono ben definiti i tipi d’ordine inverso, somma e prodotto lessicografico.

4 ordini e quasi ordini

1.5

ordinare la classe dei tipi d’ordine

Il modo più naturale di ordinare queste "strutture" è quello di vedere se una delle due contiene una copia dell’altra.

Definizione 1.5.1: Siano(A,≤_A)e(B,≤_B)ordini totali. Si dice immersione una funzione f : A→B che preserva l’ordine stretto.

Definizione 1.5.2: Siano τ1e τ2 tipi d’ordine.

Si dice che τ1 si immerge in τ2 se ∃f : τ1 → τ2 immersione. In tal caso si

scrive τ1 τ2.

• Si dice che τ1 e τ2 sono equivalenti, e lo si indica con τ1 ≡ τ2, se τ1  τ2 ∧ τ2 τ1.

• Si dice che τ1si immerge strettamente in τ2, e lo si indica con τ1≺ τ2, se τ1 τ2 ∧ τ2τ1.

• Si dice che τ1 e τ2 sono inconfrontabili e lo si indica con τ1|τ2, se τ1 

τ2 ∧ τ2τ1.

Le definizioni appena date non dipendono dai rappresentanti dei tipi d’or-dine.

Lemma 1.5.1: Valgono i seguenti:

1. La composizione di immersioni (isomorfismi) è un’immersione (isomorfismo). 2. L’inversa di un isomorfismo è un isomorfismo.

3. f1◦ f2◦f3, dove f1 e f3sono isomorfismi e f2 è un’immersione, è

un’immer-sione.

Notazione 2: Si indica con Tp la classe dei tipi d’ordine. Si indica con Tp_num la classe dei tipi d’ordine numerabili.

La definizione1.5.2fornisce allora una relazione binariasu Tp.

Si verifica facilmente che essa è riflessiva e transitiva ma non simmetrica. Ad esempio, è chiaro che η+1 ed η si immergono uno nell’altro, però non sono isomorfi in quanto η+1 ha un massimo.

Una relazione di questo tipo è detta in letteratura quasi ordine.

1.6

i quasi ordini

Definizione 1.6.1: Un quasi ordine è una relazione binaria R⊆ A×A

riflessiva ∀x ∈ A (x, x) ∈R

1.7 operazioni tra quasi ordini 5

La definizione del corrispettivo quasi ordine stretto non può essere la stessa data per gli ordini parziali, in quanto si perderebbe una tra l’ irriflessività e la transitività. Si dice allora che

x< y ⇐⇒ x ≤y ∧ yx

Si può notare che, con questa definizione, il quasi ordine stretto è in realtà un ordine parziale.

Si danno ora alcune definizioni di base sui quasi ordini, che saranno utili nel prosieguo della tesi.

Definizione 1.6.2: Un sottoinsieme X ⊆ Q di un quasi ordine (Q,≤) è detto segmento iniziale se

p ∈X ∧ q≤ p =⇒ q∈ X

Si denota l’insieme dei segmenti iniziali di Q conD(Q).

Il segmento iniziale generato da un qualsiasi S ⊆ Q è indicato con ↓S = {q∈ Q| ∃s∈ S q≤s}.

Si può osservare che l’inclusione è un quasi ordine suD(Q).

Definizione 1.6.3: Un sottoinsieme X ⊆ Q di un quasi ordine (Q,≤) è detto cofinale se

∀x∈ Q ∃y∈ X y≥x È detto coiniziale se

∀x∈ Q ∃y∈ X y≤x

Definizione 1.6.4: Sia(Q,≤) un quasi ordine. Sia α ∈ On. Si dice catena strettamente decrescente una successione(qγ)γ∈α tale che γ< δ =⇒ qγ> qδ.

Definizione 1.6.5: Si dice che un quasi ordine è ben fondato se non ammette catene infinite strettamente decrescenti.

Definizione 1.6.6: Sia(Q,≤) un quasi ordine. Un’anticatena è un sottoin-sieme X⊆ Q di elementi tra loro inconfrontabili.

Ciò significa che∀x, y∈ X x 6=y =⇒ xy ∧ y x.

1.7

operazioni tra quasi ordini

Così come accadeva per gli ordini totali, esistono molti quasi ordini che possono essere costruiti a partire da altri.

Definizione 1.7.1 (Sottordine): Sia(Q,≤_Q)un quasi ordine. Si dice sottor-dine il quasi orsottor-dine definito sui sottoinsiemi X ⊆Q come

x≤Xy ⇐⇒ x, y∈ X ∧ x≤Q y

Definizione 1.7.2 (Quasi ordine inverso): Sia (Q,≤) un quasi ordine. Si dice quasi ordine inverso il quasi ordine definito su Q come

6 ordini e quasi ordini

Tale quasi ordine è indicato con Qop_.

Definizione 1.7.3 (Somma lessicografica): Sia(I,≤I)un quasi ordine. Per

ogni i ∈ I, siano(Li,≤i)quasi ordini a due a due disgiunti. Si dice somma

lessicografica il quasi ordine definito suS

i∈ILi come x≤y ⇐⇒        ∃i<_I j x∈ Li ∧ y ∈Lj oppure ∃i∈ I x, y∈ Li ∧ x ≤i y

Questo quasi ordine si indica con∑_i∈ILi.

Definizione 1.7.4 (Prodotto lessicografico): Siano (I,<_I) e (A,<_A) due quasi ordini. Si dice prodotto lessicografico il quasi ordine definito su A×I come∑i∈I(A× {i}).

Definizione 1.7.5 (Prodotto cartesiano finito): Siano (L1,≤1), . . .(Ln,≤n)

quasi ordini. Si dice prodotto cartesiano finito il quasi ordine definito su L1×

· · · ×Lncome

(li)i=1,...,n ≤ (li0)i=1,...,n ⇐⇒ ∀i=1, . . . , n li ≤i li0

Inoltre si può costruire un quasi ordine anche sulle successioni transfinite. Definizione 1.7.6: Sia(Q,≤)un quasi ordine. Una successione transfinita di Q è una funzione del tipo s : α→Q, con α∈On.

Il dominio di tale funzione è detto lunghezza della successione ed è denotato con lh(s) =α.

Si denota con eQ = {s : α→Q|α∈On} la classe di tutte le successioni

transfinite di Q.

Si indica con sθla restrizione della funzione s ad un certo θ <lh(s).

Si ordina infine eQ termine a termine, ossia:

s≤_Tt ⇐⇒ ∃h : lh(s) →lh(t)immersione ∀ξ ∈lh(s) s(ξ) ≤t(h(ξ))

Osservazione 1.7.1: Si può osservare che, per ogni n∈ N, il quasi ordine≤_T

sull’insieme ns∈ Qe  

 l h(s) =n o

è isomorfo a quello definito sul prodotto cartesiano finito Qn.

Dato un qualsiasi ordinale α ∈ On, si scrive Qα ₌

n s ∈Qe    l h(s) =α o e Q<α ₌ n s∈ Qe    l h(s) <α o .

Il quasi ordine appena definito sulle successioni transfinite ha anche una proprietà interessante: dati s, t ∈Q qualsiasi, allora s ammette una restrizio-e ne massimale minore di t.

Nel caso in cui s≤_T t, la restrizione massimale sarà ovviamente s stesso. Lemma 1.7.1: Sia(Q,≤)un quasi ordine. Siano s, t ∈Q tali che se _T t. Allora esiste θ< lh(s)tale che sθ ≤Tt e s (θ+1) T t.

1.7 operazioni tra quasi ordini 7

Dimostrazione. La dimostrazione consiste nel costruire induttivamente un’im-mersione h che ad ogni passo i faccia in modo che s(i) ≤t(h(i)), scegliendo come h(i)il più piccolo possibile. Questa sarà l’immersione con dominio il più grande possibile.

Poiché sT t, ad un certo punto il processo di induzione dovrà

interromper-si.

Si supponga di aver definito h(ξ0)per ogni ξ0 <ξ.

I candidati per h(ξ)sono gli ordinali η ∈lh(t)tali che ξ0 <ξ =⇒ η>h(ξ0)

(per fare in modo che h sia strettamente crescente) e tali che s(ξ) ≤t(η)(per

fare in modo che s(ξ) ≤t(h(ξ))).

h(ξ)dovrà dunque essere un elemento dell’insieme

Aξ =



η∈lh(t)(ξ0 <ξ =⇒ η>h(ξ0)) ∧ (s(ξ) ≤t(η))

Se Aξ 6=∅, allora si pone h(ξ) =min Aξ.

Visto che una tale funzione h non può essere definita per tutti gli elementi di lh(s), allora esiste ξ∈ lh(s)tale che Aξ =∅.

2

W Q O E B Q O

In questo capitolo, a partire dalla congettura di Fraïssé, verrà introdotto il concetto di Well-Quasi-Order (WQO). In particolare si mostrerà quali opera-zioni tra WQO rimangono WQO. Si vedrà che saranno solo quelle di natura "finitaria".

Il controesempio di Rado mostrerà che, in generale, la classe delle suc-cessioni infinite e l’insieme dei segmenti iniziali di un Well-Quasi-Order non sono WQO.

Verrà di conseguenza introdotta, provandone a capire l’idea trainante, una sottoclasse dei WQO "migliore": i Better-Quasi-Order (BQO).

Si introducono qui alcune notazioni che verranno usate per tutto il resto della tesi.

Si osserva innanzitutto che i sottoinsiemi di N possono essere identificati con le successioni strettamente crescenti dei propri elementi. In base al con-testo, le notazioni seguenti si riferiranno all’una o all’altra interpretazione. Per un qualsiasi A ⊆N infinito e per un qualsiasi α∈On, si indica con[A]α

l’insieme delle α-successioni strettamente crescenti di A e con [A]<α

l’insie-me di tutte le successioni strettal’insie-mente crescenti di A "più corte" di α.

Siano s e t due successioni di N. Si indica con s v t la relazione essere seg-mento iniziale di, ossia per ogni i∈ lh(s)vale s(i) =t(i).

Dati due insiemi U ∈ [N]ω _{e s ∈ [}N_]<ω_{, si indica con [s, U] l’insieme}

di tutte le successioni strettamente crescenti di A aventi come segmento iniziale s e come coda una sottosuccessione infinita di U, ossia [s, U] = {V ∈ [N]ω _{|svV e V\s⊆U}.}

Congettura (di Fraïssé, [4]): La classe Tp

num dei tipi d’ordine numerabili,

ordinata per immersione, non ammette catene infinite strettamente decrescenti né anticatene infinite.

2.1

definizioni di wqo

In letteratura si trovano diverse definizioni di WQO.

Prima di enunciarle, si anticipa che, per dimostrarne le equivalenze, si farà pesantemente uso del teorema di Ramsey infinito. È bene dunque ricordarlo. Teorema 2.1.1 (di Ramsey infinito, 1930): Sia X un insieme infinito. Per ogni k∈N, ogni colorazione finita delle k-uple di X

[X]k =C0t · · · tCn−1

10 wqo e bqo

ammette un insieme infinito omogeneo, ossia esiste H⊆ X infinito tale che[H]k_è

monocromatico (cioè è tutto contenuto in uno solo dei Ci).

Osservazione 2.1.1: Il teorema di Ramsey, enunciato in questo modo, identi-fica una funzione di colorazione finita f : [X]k _{→n con la partizione [X]}k ₌

f−1(0) t · · · tf−1(n−1).

Teorema 2.1.2: Sia(Q,≤_Q)un quasi ordine. Sono fatti equivalenti:

1. Ogni X⊆ Q ammette un sottoinsieme finito coiniziale.

2. (Q,≤_Q)è ben fondato e non ammette anticatene infinite.

3. Per ogni successione(qi)i∈ω ⊆ Q esistono i < j tali che qi ≤Q qj. In breve,

ogni ω-successione ammette una coppia crescente.

4. Ogni ω-successione di Q ammette una ω-sottosuccessione crescente.

Dimostrazione. Si mostrano le varie inclusioni:

4 ⇒ 3 Ovvia.

3 ⇒4 Sia(qi)i∈ω⊆ Q una ω-successione di Q.

Si consideri la colorazione finita

[N]2 =C1tC2 dove C1 ={ (n, m)|qn≤Q qm} C2 =  (n, m)q_n_Qq_m

Per il teorema di Ramsey infinito, esiste H ⊆ _{N insieme infinito}

omo-geneo.

Se fosse [H]2 ⊆ C2, allora la successione (qi)i∈H non rispetterebbe le

ipotesi del punto 3. Dunque[H]2_⊆C

1, da cui(qi)i∈H è una ω-sottosuccessione crescente.

3 ⇒ 2 Se esistessero per assurdo catene strettamente decrescenti infinite o

anticatene infinite, vi si potrebbero estrarre delle ω-successioni che non rispettino il punto 3.

2 ⇒ 3 Sia per assurdo(qi)i∈ωuna successione di Q senza coppie crescenti.

Si consideri la colorazione finita

[N]2 =C1tC2 dove C1={ (n, m)|qn >qm} C2=  (n, m)q_nq_m

Allora esiste H⊆N insieme infinito omogeneo.

Se fosse[H]2_⊆C

2, allora(qi)i∈H sarebbe un’anticatena infinita.

Se fosse [H]2 ⊆ C1, allora (qi)i∈H sarebbe una catena infinita

2.2 stabilità dei wqo 11

1 ⇒ 3 Sia (qi)i∈ω una successione di Q. Sia X = {qi |i∈ω} l’insieme

degli elementi della successione.

Per il punto 1, X ammette un sottoinsieme finito F coiniziale con X. Per ogni f ∈F, siano If ={i∈ω|qi = f }. Sia I =  min If

 f ∈F . I è un insieme finito, dunque ammette un massimo i0=max I.

Allora per ogni j> i0, esiste i≤i0< j tale che qi ≤Q qj.

2 ⇒ 1 Si indica con x ≡ y la relazione d’equivalenza x ≤ y ∧y ≤ x su Q.

Questa induce un ordine parziale sull’insieme quoziente(Q/≡). Sia X ⊆ Q qualsiasi. Se (X/ ≡) è finito, si definisce un sottoinsie-me finito coiniziale di X prendendo un rappresentante da ogni classe d’equivalenza di(X/≡).

Sia(X/≡)infinito. Lo si partiziona

(X/≡) =C1tC2

dove

C1 ={x∈ (X/≡) | ∃y∈ (X/≡) y< x}

C2 ={x∈ (X/≡) | @y∈ (X/≡) y<x}

Se C2 fosse infinito, un insieme formato da un rappresentante di ogni

sua classe d’equivalenza sarebbe un’anticatena infinita di Q.

Allora C2 è finito. Si supponga dunque che esista un certo x ∈ C1 tale

che y<x =⇒ y ∈C1.

Allora si può estrarre da {y∈ (X/≡) |y< x} ⊆C1 una successione

infinita strettamente decrescente di (Q/≡). Scegliendo un rappresen-tante da ogni classe di equivalenza, si ottiene una successione infinita strettamente decrescente di Q.

Allora, per ogni x∈C1, esiste un elemento y∈C2tale che y<x.

Scegliendo quindi un rappresentante da ogni classe d’equivalenza di C2, si ottiene un sottoinsieme di X finito e coiniziale.

Si osservi che, per il punto 2, la congettura di Fraïssé può essere enunciata anche come segue

Congettura: La classe Tp_num dei tipi d’ordine numerabili, ordinata per immer-sione, è un WQO.

2.2

stabilità dei wqo

In questo paragrafo si mostrerà che i quasi ordini che si generano dalle principali operazioni "finitarie" tra WQO viste nel paragrafo1.7, rimangono

WQO.

12 wqo e bqo

Dimostrazione. Sia(Q,≤_Q)un WQO. Sia X⊆Q.

Sia Y⊆X⊆ Q. Poiché Q è WQO, allora Y ammette un sottoinsieme finito e coiniziale.

Lemma 2.2.2 (Omomorfismi): L’immagine di un omomorfismo di un WQO è un WQO.

Dimostrazione. Sia f : Q → B un omomorfismo tra quasi ordini e sia Q un WQO.

Sia A⊆Im(f). Allora f−1(A)è sottoinsieme di Q.

Poiché Q è WQO, allora esiste F⊆ f−1_{(A)finito e coiniziale.}

Da cui l’insieme f(F) ⊆A è finito e coiniziale.

Lemma 2.2.3 (Unione): Sia(Q,≤_Q)un quasi ordine e siano A, B due sottordini tali che Q= A∪B.

Se A e B sono WQO, allora lo è anche Q.

Dimostrazione. Sia X⊆Q= A∪B. Allora X= (X∩A) ∪ (X∩B).

Poiché X∩ A e X∩B sono sottordini rispettivamente di A e B, esistono FA⊆ (X∩A)e FB ⊆ (X∩B)finiti e coiniziali.

Allora F= FA∪FB ⊆Q è finito e coiniziale.

Si può osservare che, in generale, i WQO non sono stabili per la somma lessicografica. Sia infatti∑_i∈ILi una somma di WQO. Prendendo come I un

insieme infinito di elementi tutti equivalenti tra loro (e dunque un WQO) e scegliendo un elemento da ogni Li, si costruisce un’anticatena infinita.

Nel caso, però, che I sia un ordine parziale, anche la somma di WQO rimane un WQO.

Lemma 2.2.4: Sia (I,≤_I) un ordine parziale senza anticatene infinite e senza catene strettamente decrescenti infinite. Siano(Li,≤i)WQO a due a due disgiunti.

Allora_∑i∈ILiè un WQO.

Dimostrazione. Sia X ⊆ _∑i∈ILi un qualsiasi sottoinsieme. Si può scrivere

X=_∑i∈I(X∩Li). Per ogni i∈ I, vale X∩Li ⊆ Li. Siccome gli Lisono WQO,

allora ogni X∩Li è vuoto o ammette un sottoinsieme finito coiniziale.

Sia I0 = {i∈ I |X∩Li 6=∅}. Per ogni i ∈ I0, siano Fi ⊆ X∩Li gli insiemi

finiti coiniziali menzionati sopra.

Siccome I è un WQO, allora anche I0 ⊆ I ammette un sottoinsieme finito

coiniziale. Sia esso E⊆ I0.

Allora_∑i∈EFi è un sottoinsieme finito e coiniziale di X.

Lemma 2.2.5 (Prodotto cartesiano finito): Sia(Q,≤_Q)un WQO. Allora, per ogni n∈N, il prodotto cartesiano finito(Qn,≤_T)è un WQO. Dimostrazione. Sia(q1_i, . . . , qn_i)_i∈ω una ω-successione di elementi di Qn. Si ricava una ω-sottosuccessione crescente:

passo base Poiché (qni)i∈ω è una ω-successione di Q, che è WQO, si può

2.2 stabilità dei wqo 13

passo induttivo Siano In⊇ · · · ⊇ Ij+1.

Poiché (q_ij)_i∈Ij+1 è una ω-successione di Q, che è WQO, si può estrarre una ω-sottosuccessione crescente(q_ij)_i∈Ij, con Ij ⊆ Ij+1.

(q1_i, . . . , qn_i)_i∈I1 è, allora, una ω-sottosuccessione crescente di(q

1

i, . . . , qni)i∈ω.

Lemma 2.2.6 (Successioni finite): Sia(Q,≤_Q)un WQO. Allora l’insieme delle successioni finite(Q<ω_,≤

T)è un WQO.

Dimostrazione. Innanzitutto si dimostra che è ben fondato.

Se per assurdo non lo fosse, sia (sn)n∈ω una catena infinita strettamente

decrescente di Q<ω_{. Allora lh(s}

1) ≥lh(s2) ≥. . .

Questi sono ordinali, dunque si stabilizzano, ossia esiste n0 ∈ ω tale che

n≥n0 =⇒ lh(sn) =lh(sn0) = L0.

Allora(sn)n≥n0 è una catena infinita strettamente decrescente di Q

L0_{, che è}

un WQO. Assurdo.

Si supponga ora per assurdo che Q<ω _{non sia un WQO. Ciò significa che}

l’insieme C = f : ω →Q<ω 

∀i< j f(i) _T f(j) non è vuoto. Si costruisce induttivamente la seguente ω-successione di Q<ω_:

• Sia C0= {f(0)| f ∈ C}. Esso è ben fondato in quanto è sottoinsieme

di Q<ω_{, dunque ogni catena ha almeno un minimale. Sia s}

0 ∈ Q<ω

uno di questi minimali.

• Sia Cn+1 ={ f(n+1)| f ∈C ∧ f(0) =s0, . . . , f(n) =sn}. Esso è ben

fondato in quanto è sottoinsieme di Q<ω_{, dunque ogni catena ha}

alme-no un minimale. Sia sn+1 uno di questi minimali.

Siano ora ai = si(0)gli elementi di testa delle successioni finite si.

(ai)i∈ω è una successione di Q. Siccome questo è un WQO, allora ammette

una ω-sottosuccessione crescente (a_ik)_k∈ω. Siano ora s0_i

k le successioni sik private del loro elemento di testa. Allora

s0_i

k <Tsik. Di conseguenza una funzione tale che

f(0) =s0 .. . f(i0−1) =si0−1 f(i0) =s0i0 f(i0+1) =si01 .. .

non può appartenere a C. Dunque esistono n <m tali che f(n) ≤_T f(m). Per costruzione non possono valere sn ≤T sm, né sn ≤T s0im. Allora deve

14 wqo e bqo

2.3

instabilità dei wqo: il controesempio di rado

In questo paragrafo si vedrà, grazie al controesempio di Rado, che essere WQO non passa alle successioni infinite, né ai segmenti iniziali. In generale, quindi, dato un WQO (Q,≤), non è vero che (Qω_,≤

T) e (D(Q),⊆) sono

WQO.

La nozione di Better-Quasi-Order (BQO) fu introdotta da Nash-Williams, in due articoli degli anni060, come sottoclasse dei WQO con proprietà migliori. In particolare:

• I WQO non patologici sono anche BQO.

• I BQO sono stabili per successioni infinite e segmenti iniziali.

La prima cosa da osservare è che, se (Q,≤) è un WQO, allora (Qω_,≤

T)

e(D(Q),⊆) sono ben fondate. Di conseguenza la non stabilità dei WQO è dovuta alla sola esistenza di anticatene infinite.

Lemma 2.3.1: (Q,≤)è un WQO se e solo se(Qω_,≤

T)è ben fondato.

Dimostrazione. Si mostrano le due inclusioni:

⇒ Sia Qω _{non ben fondato. Sia(s}

i)i∈ω una sua catena infinita strettamente

decrescente. Lo scopo è costruire una successione infinita di Q<ω _che

non ammetta alcuna coppia crescente. Si costruisce induttivamente. Per ogni m∈ω e per ogni k>m vale sm T sk. Dunque, per il lemma 1.7.1, esiste nk

m tale che smnkm ≤Tsk ma sm (nkm+1) T sk.

Si osserva che per ogni m < k < h vale che smnmh ≤T sh <T sk, di

conseguenza la successione(nk

m)k>m è decrescente.

Allora sm (nmm+1+1) T sk per ogni k> m.

La successione(sm (nmm+1+1))m∈ω di Q

<ω _{non ammette coppie}

cre-scenti.

⇐ Sia Q non WQO.

Sia(qi)i∈ωuna successione di Q che non ammette coppie crescenti.

Definendo sn = (qi)i≥n, allora (sn)n∈ω è una successione infinita e

strettamente decrescente di Qω_.

Lemma 2.3.2: (Q,≤)è un WQO se e solo se(D(Q),⊆)è ben fondato. Dimostrazione. Si mostrano le due inclusioni.

⇒ SiaD(Q)non ben fondato.

Sia(Dn)n∈ωuna sua catena infinita strettamente decrescente.

Allora per ogni n ∈ ω, vale che Dn\Dn+1 6= ∅. Siano quindi qn ∈

Dn\Dn+1.

La successione(qn)n∈ω di Q non ammette coppie crescenti.

⇐ Sia Q non WQO.

Sia(qn)n∈ω una successione di Q che non ammette coppie crescenti.

2.3 instabilità dei wqo: il controesempio di rado 15

Allora(Dn)n∈ωè una catena infinita strettamente decrescente diD(Q).

Il controesempio di Rado [18] mostra che le successioni infinite ed i

seg-menti iniziali di un WQO non sono, in generale, WQO.

Esempio 2 (Controesempio di Rado): Sia Q = [ω]2 e lo si ordini come

segue: (n1, m1) ≤ (n2, m2) ⇐⇒        n1 =n2 ∧m1≤ m2 oppure m1<n2

Lemma 2.3.3: Q è un WQO ma Qω_{e D(Q)non lo sono.}

Dimostrazione. Si dimostrano i tre punti:

• Q è WQO.

Sia((nk, mk))k∈ω una successione di Q.

Si estrae la successione (nk)k∈ω e sia N = {nk |k∈ ω}l’insieme dei

suoi elementi.

Se N è finito, si può estrarre da (n_k)_k∈ω una sottosuccessione infinita costante. Sia I ⊆ω infinito tale che(nk)k∈I è costante.

Prendendo allora la successione (mk)k∈I, si ha che ∃i < j ∈ I tali che

m_i ≤ m_j. Da cui(n_i, mi) ≤ (nj, mj).

Se N è infinito, allora N∩ {n∈ ω|n>m0} 6=∅. Dunque esiste k>0

tale che nk >m0. Da cui(n0, m0) < (nk, mk). • Qω_{non è WQO.}

Per ogni n∈ ω, sia sn = ((n, m))m>n. Dunque(sn)n∈ωè ω-successione

di Qω _{che non ammette coppie crescenti.}

Infatti per ogni k <h, vale che(k, h) ∈sk ma non è minore di nessuno

degli elementi di sh. Dunque skTsh. • D(Q)non è WQO.

Per ogni n ∈ ω, sia Dn = { (h, k) ∈Q| ∃m>n (h, k) ≤ (n, m)},

os-sia l’insieme↓{ (n, m)|m>n}. Allora(Dn)n∈ω non ammette coppie

crescenti.

Infatti per ogni n< m, vale che(n, m) ∈ Dnma(n, m)∈/ Dm. Dunque

Dn*Dm.

L’idea della nozione di Better-Quasi-Order è quella di rendere WQO anche tutte le successioni transfinite di un WQO, di conseguenza, dato un Well-Quasi-Order (Q,≤), la naturale definizione sarebbe quella in cui, per ogni

α∈On,(Qα,≤T)è un WQO.

È però evidente che una definizione data in questo modo sarebbe poco utile, in quanto estremamente complicata da utilizzare.

16 wqo e bqo

Il grande lavoro di Nash-Williams è stato quello di trovare una condizio-ne su (Q,≤) più maneggevole, che stabilisse se effettivamente tutte le sue successioni transfinite fossero un WQO.

Già nel caso di(Qω_,≤

T), trovare una tale condizione non è affatto banale.

La ricerca sarà fatta, allora, a partire dai segmenti iniziali. Una volta trovata tale condizione, si vedrà come poterla generalizzare, confrontandola con le successioni infinite.

Sia(Q,≤)un Well-Quasi-Order tale che(D(Q),⊆) non lo sia.

Per il lemma2.3.2, ciò significa che esiste un’anticatena infinita (D_n)_n∈N di

D(Q).

Allora per ogni n < m, vale che Dn * Dm. Dunque Dn\Dm 6= ∅. Siano

allora qm_n ∈Dn\Dm.

Si ottiene così la funzione q :[N]2 →Q che mappa(n, m) 7→qm_n.

Si può osservare che per ogni n < m < l, vale che qm_n  qlm, altrimenti,

essendo Dm un segmento iniziale, anche qmn dovrebbe appartenergli.

Definizione 2.3.1: Sia(Q,≤) un quasi ordine. Una funzione f :[N]2→ Q è detta cattiva se∀n<m<l f((n, m))  f((m, l)).

È detta buona altrimenti.

Imponendo allora che tutte le funzioni del tipo f : [N]2→Q siano buone, si può vedere che effettivamenteD(Q)diventa un WQO.

Teorema 2.3.1: Sia(Q,≤)un WQO. Allora sono fatti equivalenti:

1. (D(Q),⊆)è un WQO

2. Tutte le funzioni f : [N]2 →Q sono buone. Dimostrazione. Si dimostrano le due inclusioni:

2 ⇒ 1 Se(D(Q),⊆)non è WQO, si è appena costruita una funzione cattiva

a partire da un’anticatena infinita diD(Q).

1 ⇒ 2 Si supponga che esista f : [N]2 → Q tale che per ogni n < m < l,

valga f((n, m))  f((m, l)).

Per ogni n ∈ N, sia D_n = {p∈ Q| ∃m>n p≤ f(n, m)} , ossia Dn= ↓{ f((n, m))|n<m}.

Allora per ogni n< m vale che Dn* Dm. Infatti f((n, m)) ∈ Dn\Dm,

altrimenti dovrebbe esistere l>m tale che f((n, m)) ≤ f((m, l)).

Osservazione 2.3.1: Le funzioni f : [N]2 → Q possono identificare gli ele-menti di Qω2_{. Se s è un elemento di Q}ω2_{, ossia è una funzione s : ω}2 _{→ Q,}

allora lo si identifica come segue: f((n, m)) =s(ωn+ (m−n−1)).

In maniera analoga si può fare tra le funzioni f : [N]n → Q e gli ele-menti di Qωn_{. Un certo s ∈ Q}ωn _{lo si identifica come f(m}

0, . . . , mn−1) =

2.4 introduzione ai bqo 17

Continuando così, si può dire che gli elementi di Qωω

, che sono le funzio-ni s : ωω _{→ Q, possono essere identificati con le funzioni f : [}N_]<ω _{→ Q, in}

quanto ωω₌ S

n∈ωω

n_e[N]<ω ₌S

n∈N[N]n.

Generalizzando ulteriormente, si può vedere che gli elementi di(Qωω₎ω ₌

Qωω+1 _{possono essere identificati con le funzioni f : [}N_]1_{× [}N_]<ω _{→Q, e in}

generale gli elementi di Qωω+n _{possono essere identificati con le funzioni}

f : [N]n_{× [N]}<ω _→Q.

Si può però osservare che [N]n× [N]<ω _{è isomorfo ad un certo}

sottoin-sieme di [N]<ω _{mappando (m}

1, . . . , mn) × (a1, . . . , ak) 7→ (m1, . . . , mn, a1+

mn, . . . , ak+mn).

In generale tutti gli insiemi del tipo(([N]<ω₎<ω₎..._{sono isomorfi ad un certo}

sottoinsieme di[N]<ω_.

Osservazione 2.3.2: Dato un quasi ordine(Q,≤), si può osservare che dire che tutte le funzioni f : [N]1 → Q sono buone, ossia esistono sempre i < j tali che f(i) ≤ f(j), è proprio la definizione di WQO.

2.4

introduzione ai bqo

Dato un Well-Quasi-Order(Q,≤), l’osservazione2.3.1fornisce lo spunto per

ottenere la condizione cercata. Questa sarà fornita dalle funzioni del tipo f : B→ Q, dove B è un sottoinsieme di[N]<ω _{con determinate}

caratteristi-che. In particolare si può osservare che ogni sottoinsieme infinito diN deve avere almeno un segmento iniziale contenuto in B.

Definizione 2.4.1: Si dice blocco un insieme B ⊆ [N]<ω _{tale che ogni}

sottoinsieme infinito diN ammette un segmento iniziale in B.

Notazione 3: Dati due elementi s, t ∈ [N]<ω_{, si scrive s/t per indicare}

che s\ {min s} vt.

Si osserva che questa relazione non è transitiva.

Definizione 2.4.2: Dato un quasi ordine(Q,≤)ed un blocco B, si dice che f : B → Q è buona se esistono s/t ∈ B tali che f(s) ≤ f(t). Si dice cattiva altrimenti.

La definizione data da Nash-Williams di Better-Quasi-Order è dunque la seguente

Definizione 2.4.3: Un quasi ordine(Q,≤)si dice Better-Quasi-Order (BQO) se, per ogni blocco B, ogni funzione f : B→Q è buona.

In un articolo [22] del 1985, Simpson propose una definizione alternativa,

meno combinatoria e più topologica.

Innanzitutto si può osservare che da ogni blocco B si può ricavare un blocco "minimale" B0, ossia tale che se s v t ∈ B0, allora s = t. Per fare ciò, basta prendere le catene in B date dalla relazione v e definire B0 prendendo i

18 wqo e bqo

minimi di ogni catena.

A partire dalle funzioni definite sui blocchi, se ne possono ricavare delle "analoghe" con dominio[N]ω_.

Dato infatti un blocco B, si considera il relativo blocco minimale B0 ⊆B. Da una funzione f : B → Q, si definisce allora ef : [N]ω _{→ Q tale che ef(X) =}

f(s), dove s è l’unico segmento iniziale di X che appartiene a B0.

Si osserva che l’immagine di ef ha cardinalità numerabile e che, per ogni q∈ Q, vale che ef−1(q)è vuoto o valeS

[s,N] s∈ f−1(q) ∧ s∈ B0 . Definizione 2.4.4: Si definisce su [N]ω _{la topologia avente come base di}

aperti B={ [s,N]|s∈ [N]<ω_}

Ponendo su Q la topologia discreta, si può osservare che ef è continua, e in particolare Borel-misurabile.

Definizione 2.4.5: Sia(Q,≤)un quasi ordine. Una funzione f :[N]ω_{→ Q}

Borel-misurabile e con immagine numerabile è detta Q-array.

Si osserva infine che, dati un quasi ordine(Q,≤)e un blocco B, se s/t ∈B, allora esiste un certo X∈ [N]ω _{tale che svX e tv X\ {min X}.}

Definizione 2.4.6: Un Q-array f : [N]ω _{→ Q è detto buono se∃X ∈ [}N_]ω

tale che f(X) ≤ f(X\ {min X}). È detto cattivo altrimenti.

Definizione 2.4.7 (alternativa, di Simpson [22]): Un quasi ordine (Q,≤) è

detto Better-Quasi-Order (BQO) se ogni Q-array è buono.

La definizione di BQO viene data sfruttando tutti gli array di un quasi ordine, e non solo quelli continui.

In seguito si vedrà, grazie al teorema di Mathias4.1.1, che dare la definizione

di BQO utilizzando tutti gli array o solo quelli continui, risulta equivalente. È chiaro che i Better-Quasi-Order sono una sottoclasse dei Well-Quasi-Order. Inoltre, si può anche osservare che i buoni ordini sono, a loro volta, una sottoclasse dei BQO.

Lemma 2.4.1: Sia(Q,≤)un buon ordine. Allora è anche un BQO.

Dimostrazione. Sia f : [N]ω _{→ Q un Q-array. Si supponga per assurdo che}

sia cattivo, ossia che per ogni X∈ [N]ω_{, valga f(X)  f(X\ {min X}). Sia}

allora (Ai)i∈ω la successione tale che A0 è un qualsiasi elemento di [N]ω e

Ai+1 = Ai\ {min Ai}. Si definisce allora la successione(f(Ai))i∈ω in Q.

È chiaro che per ogni i∈ ωdeve valere f(Ai)  f(Ai+1).

Poiché (Q,≤) è un buon ordine, e in particolare è un ordine totale, allora vale che f(Ai) > f(Ai+1).

Dunque(f(Ai))i∈ω è una successione strettamente decrescente di Q.

Lemma 2.4.2: Sia (Q,≤) un Better-Quasi-Order. Allora è anche un Well-Quasi-Order.

2.4 introduzione ai bqo 19

Dimostrazione. Si supponga per assurdo che esista una successione (qi)i∈ω

tale che per ogni n<m valga qnqm.

La si scrive sotto forma di funzione q : N→Q. Alloraq :e [N]

ω _{→Q dato da}

e

q(X) =qmin X è un Q-array cattivo.

In questa tesi verrà utilizzata la definizione di Better-Quasi-Order data da Simpson (2.4.7).

Un teorema che risulterà fondamentale per maneggiare i BQO sarà visto nel capitolo successivo.

Esso è il teorema di Galvin e Prikry. Identificando una colorazione f : [N]ω_→

n con la partizione finita[N]ω _{= f}−1_{(0) t · · · t f}−1_{(n−1), tale teorema}

ge-neralizza il noto teorema di Ramsey nel caso in cui la partizione sia formata da boreliani rispetto alla topologia2.4.4.

Il seguente controesempio, dovuto a Erd˝os e Rado [3], mostra che senza

l’ipotesi di borelianità della partizione, il teorema è falso.

Esempio 3 (Controesempio): Prima di iniziare, un’osservazione che si può fare è che un eventuale controesempio deve necessariamente fare uso del-l’assioma della scelta. Infatti in [13,23] è stato mostrato che l’affermazione è

vera nel modello di Solovay dove non vale AC e dove ogni sottoinsieme dei reali è Lebesgue misurabile.

Lo scopo è cercare una partizione[N]ω _=K

1tK2 per la quale non

esista-no insiemi infiniti omogenei. In altre parole∀Y∈ [N]ω_{deve valere che[Y]}ω

interseca sia K1 che K2.

Per Zermelo (AC) esiste un buon ordinamento Y< Z su[N]ω_.

Sia K1= {Y ∈ [N]ω | ∃Y0 ∈ [Y]ω Y0 <Y}e sia K2 =K{₁.

Si può vedere che questa partizione soddisfa la richiesta.

Sia infatti Y ∈ [N]ω _{qualsiasi. Si mostra che esistono A, B ∈ [Y]}ω _{tali che}

A∈K1 e B∈K2.

Sia B = min[Y]ω_{. Evidentemente B ∈ K}

2, infatti per ogni B0 ∈ [B]ω ⊆

[Y]ω_{, vale B<B}0 _{per minimalità.}

Si ricava ora A:

Si possono numerare gli elementi di B:

B={b0, b1, . . .}

Per ogni m ∈ N, sia allora Am = {b0, b2, . . . , b2m, b1, b3, . . .} e sia L =

{Am |m∈N}. È evidente che L ⊆ [Y]ω, dunque ammette un minimo.

Si scrive Am0 =min L.

Allora per costruzione Am0 ⊆ Am0+1 e Am0 < Am0+1, da cui Am0+1 ∈ K1. Si

3

T E O R E M A D I G A L V I N E P R I K R Y

In questo capitolo si dimostrerà il teorema di Galvin e Prikry [5].

Identifi-cando una colorazione finita f : [N]ω _{→ n di [}N_]ω _{con la partizione finita}

[N]ω _{= f}−1_{(0) t · · · t f}−1_{(n−1), si vedrà che, se tale partizione è formata}

da boreliani rispetto alla topologia definita nel precedente capitolo (2.4.4),

al-lora N ammette un sottoinsieme infinito e monocromatico. In realtà Galvin e Prikry dimostrarono una cosa equivalente, ossia che tutti i boreliani sono insiemi di Ramsey (completi) (si daranno le varie definizioni nel seguito).

Si introducono qui alcune notazioni che verranno usate nel capitolo. Dati s ∈ [N]<ω _{e U ∈ [}N_]ω_{, si scrive U/s per indicare l’insieme definito}

come {u∈U| ∀i∈ s u>i}.

Definizione 3.0.1: Un insieme A ⊆ [N]ω _{è detto di Ramsey se esiste U ∈}

[N]ω _{tale che[U]}ω_{⊆ A oppure [U]}ω_∩A= ∅.

3.1

gli aperti sono insiemi di ramsey

Il primo passo è mostrare che gli aperti rispetto alla topologia 2.4.4 sono

insiemi di Ramsey.

Definizione 3.1.1: Sia A⊆ [N]ω _{e siano U ∈ [}N_]ω_{e s∈ [}N_]<ω_.

Si dice che U accetta s se[s, U] ⊆ A.

Si dice che U rifiuta s se non esistono V ∈ [U]ω _{tali che [s, V] ⊆A.}

Si dice che U rifiuta fortemente s se U rifiuta sia s sia s∪ {n} per ogni n ∈

U/s.

Sia A un aperto di [N]ω_{. Se esiste un certo U ∈ [}N_]ω _{che accetta} ∅,

significa che[∅, U] = [U]ω _{⊆ A.}

Il caso interessante sarà allora quello in cui un tale U non esiste. Ciò vorrà dire che N rifiuta ∅. La dimostrazione consisterà dunque nel costruire un insieme V ∈ [_N]ω _{tale che[V]}ω_∩A= ∅.

Lemma 3.1.1: Sia A⊆ [_N]ω_{, siano U∈ [}N_]ω _{e s∈ [}N_]<ω_.

Se U rifiuta s, allora esiste V∈ [U]ω _{tale che V rifiuta fortemente s.}

Dimostrazione. Si supponga per assurdo che ciò non sia vero. Dunque ogni V ∈ [U]ω _{ammette un n∈V/s tale che V non rifiuta s∪ {n}.}

Si costruisce induttivamente un insieme V ∈ [U]ω _{che accetti s.}

passo base Sia W0 =U/s

22 teorema di galvin e prikry

passo induttivo Siano definiti Wi ⊆U e n0< · · · <ni−1<min Wi.

Per ipotesi Wi rifiuta s, ma esiste ni ∈ Wi tale che Wi non rifiuta s∪

{ni}. Allora esiste W ⊆Wiche accetta s∪ {ni}. Sia Wi+1 =W/{ni}.

Sia infine V ={ni |i∈N}. Allora V accetta s.

Sia infatti X ∈ [s, V], allora esiste i ∈ N tale che X ∈ [s∪ {ni}, V] ⊆

[s∪ {ni}, Wi+1] ⊆ A.

Ma allora U non rifiuta s.

Teorema 3.1.1: Ogni aperto A ⊆ [N]ω _{è un insieme di Ramsey.}

Dimostrazione. Si suppone cheN rifiuti ∅ e si costruisce induttivamente un insieme V tale che[V]ω_∩A= ∅.

passo base Sia U0=N.

passo induttivo Siano definiti Ui ∈ [N]ω e n0 < · · · <ni−1 <min Ui tali

che Ui rifiuta ogni s∈ ℘({n0, . . . , ni−1}).

Siccome tale insieme è finito, lo si può numerare {s0, . . . , s2i₋₁}. Si

applica quindi ripetutamente il lemma3.1.1per ognuno degli s_j,

otte-nendo Vi ⊆Ui che rifiuta fortemente ogni sj.

Siano ni =min Vi e Ui+1 =Vi/{ni}.

Sia infine V ={ni |i∈N}. Allora[V]ω∩A=∅.

Si supponga per assurdo che non sia così. Allora esiste Y∈ [V]ω_∩A.

Poiché A è un aperto, allora contiene un intorno aperto di Y. Sia dunque Y∈ [s,N] ⊆ A.

Poiché Y ∈ [V]ω_{, allora s ∈ [V]}<ω_{. Dunque esiste i ∈} N tale che s _∈

℘({n0, . . . , ni−1}).

Ciò significa che[s, Ui] ⊆ [s,N] ⊆A, da cui Ui accetta s.

3.2

i boreliani sono insiemi di ramsey

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}

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-Better-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(q_i) è boreliano, si può applicare il teorema di Galvin e Prikry 3.2.1 ripetutamente per tutti gli elementi di S_i 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]ω∩