Dalla congettura di Fraïssé al teorema di Laver
Candidato: Alberto Caccavale Relatore: prof. Alessandro Berarducci
Corso di Laurea in Matematica Università di Pisa
1 Congettura di Fraïssé
2 Well-Quasi-Order
3 Better-Quasi-Order
4 Teorema di Nash-Williams
Congettura di Fraïssé
Congettura di Fraïssé
Definizione
Dati due ordini totali A e B, si scrive A B se A si immerge in B. Si scrive A ≺ B se valgono A B ma B A.
Si scrive A|B se A B e B A. Si scrive A ≡ B se A B e B A. Esempio
Alcuni esempi possono essere N Z Q R.
Si osserva che Q≥0 e Q sono equivalenti ma non isomorfi. Congettura (di Fraïssé, 1948)
La famiglia degli ordini totali numerabili non ammettesuccessioni strettamente decrescenti infinite A1 A2 . . . , né sottoinsiemi infiniti
Congettura di Fraïssé
Teorema di Cantor
Teorema (di Cantor, 1897)
Tutti gli ordini totali numerabili si immergono in Q.
Gli ordini totali numerabili in cui si immerge Q sono tutti equivalenti tra loro, in particolare sono "maggiori" di tutti gli altri.
La congettura di Fraïssé si riduce agli ordini totali numerabili in cui Q non si immerge.
Definizione
Congettura di Fraïssé
Teorema di Hausdorff sugli ordini totali sparsi
Definizione
Sia { Ai | i ∈ I } una famiglia ordinata di ordini totali. Si definisce l’ordine
somma P
i ∈IAi come l’unione disgiunta ordinata ponendo tutti gli
elementi di Ai minori di tutti gli elementi di Aj quando i < j.
Teorema (Classificazione di Hausdorff, 1908) La classe degli ordini totali sparsi è l’unione V =S
α∈OnVα dove
• V0 è la classe degli ordini finiti.
• Vα è la classe degli ordini totali ottenibili come somme ordinate
P
i ∈IAi, dove gli Ai sono elementi di classi precedenti e I è un
ordinale o un suo inverso. Definizione
Il rango di un ordine totale sparso L è il minimo ordinale α ∈ On tale che L ∈ Vα.
Congettura di Fraïssé
Quasi ordini
Definizione
Una coppia (Q, ≤) è detta quasi ordinese la relazione ≤ è riflessiva e transitiva. La sua relazione stretta è x < y ⇐⇒ x ≤ y ∧ y x . Quest’ultima è un ordine parziale.
Si dice che due elementi x e y sonoinconfrontabili se x y e y x . Si dice che due elementi x e y sonoequivalenti se x ≤ y e y ≤ x .
Well-Quasi-Order
Well-Quasi-Order
Definizione
• Un quasi ordine (Q, ≤) è detto ben fondatose non ammette successioni x1> x2 > . . . infinite strettamente decrescenti.
• Un sottoinsieme S ⊆ Q di un quasi ordine è dettoanticatenase tutti i suoi elementi sono a due a due inconfrontabili.
Definizione (Well-Quasi-Order)
Un quasi ordine (Q, ≤) è dettoWell-Quasi-Order (WQO) se è ben fondato e non ammette anticatene infinite.
Riformulazione della congettura di Fraïssé
Well-Quasi-Order
Controesempio di Rado
Definizione (Successioni)
Sia (Q, ≤) un quasi ordine. Si chiama Q = { s : α → Q | α ∈ On } lae
classe delle successioni transfinite di Q ordinate termine a termine.
Se (Q, ≤) è un WQO, si dimostra che la classe delle sue successionifinite, ordinate termine a termine, è un WQO.
Non è però detto che lo sia la classe di tutte le successioni transfinite Q.e
Controesempio (Rado, 1954) • Q = { (n, m) ∈ N × N | n < m } • (n1, m1) ≤ (n2, m2) ⇐⇒ n1 = n2 ∧ m1≤ m2 oppure m1< n2
Better-Quasi-Order
Introduzione ai Better-Quasi-Order
Nash-Williams introdusse una sottoclasse dei WQO, detta
Better-Quasi-Order (BQO), con migliori proprietà di stabilità. In particolare:
• I WQO "interessanti" sono anche BQO. • I BQO sono stabili per successioni transfinite.
La definizione di Nash-Williams ha una natura puramente combinatoria. Si userà una definizione alternativa, più topologica, dovuta a Simpson.
Better-Quasi-Order
Definizione di Better-Quasi-Order
Si identificano i sottoinsiemi di N con le successioni crescenti dei propri elementi. Si pone su [N]ω, le parti infinite di N, una topologia.
Topologia
Un aperto base è dato dalle successioni infinite che estendono una fissata successione finita.
Definizione
Sia (Q, ≤) un quasi ordine. Un Q-arrayè una funzione f : [N]ω → Q tale che l’immagine è numerabile e le controimmagini dei singoletti di Q sono boreliani. Si dice che f è buona se esiste X ∈ [N]ω tale che
f (X ) ≤ f (X \ { min X }). Si dice cattiva altrimenti. Definizione
Better-Quasi-Order
Sotto-array
L’insieme dei naturali N è isomorfo ad ogni suo sottoinsieme infinito. Definizione
Sia (Q, ≤) un quasi ordine. A meno di isomorfismo, per ogni A ⊆ N infinito, le funzioni f : [A]ω → Q con immagine numerabile e tali che le controimmagini dei singoletti sono boreliani (rispetto alla topologia indotta) sono tutteQ-array.
Definizione
Sia (Q, ≤) un quasi ordine, sia A ⊆ N infinito e sia f : [A]ω→ Q un Q-array. Si dice sotto-arraydi f una sua restrizione f |[B]ω, dove B ⊆ A infinito.
Better-Quasi-Order
Teorema di Galvin e Prikry
Definizione
Una colorazione finita c : [N]ω → n delle parti infinite di N è detta
borelianase la controimmagine di ogni elemento è un boreliano. Teorema (di Galvin e Prikry, 1973)
Per ogni colorazione finita e boreliana c : [N]ω→ n delle parti infinite di N, esiste un sottoinsieme infinito H di N omogeneo, ovvero tale che c
ristretta a [H]ω è costante. Osservazione
Sia (Q, ≤) un BQO. Ogni Q-array ammette un Q-sotto-array tale che,per ogni X nel dominio, f (X ) ≤ f (X \ { min X }).
Better-Quasi-Order
Minimal Bad Array Lemma
Definizioni preliminariDefinizione
Sia (Q, ≤) un quasi ordine. Un ranking parziale è un ordine parziale (Q, <0) ben fondato e tale che x <0 y =⇒ x < y .
Si dice che x ≤0 y se x <0 y oppure x = y . Definizione (Ordinamento dei Q-array cattivi)
Sia (Q, ≤) un quasi ordine. Siano A e B sottoinsiemi infiniti di N. Siano f : [A]ω → Q e g : [B]ω→ Q due Q-array cattivi. Si dice che:
f ≤∗g se • A ⊆ B • ∀X ∈ [A]ω f (X ) ≤0 g (X ) f <∗ g se • A ⊆ B • ∀X ∈ [A]ω f (X ) <0 g (X )
Better-Quasi-Order
Minimal Bad Array Lemma
Lemma
Sia (Q, ≤) un quasi ordine e sia <0 un ranking parziale. Sia A0 un
sottoinsieme infinito di N.
Allora ogni Q-array cattivo f0: [A0]ω→ Q ammette un Q-array cattivo
Teorema di Nash-Williams
Teorema di Nash-Williams
Teorema (di Nash-Williams, 1968)
Sia (Q, ≤) un quasi ordine e sia s : [N]ω →Q une Q-array cattivo. Allorae
esiste un Q-array cattivo f tale che per ogni X vale f (X ) ∈ s(X ) Corollario
La classe delle successioni transfinite di un BQO, ordinate termine a termine, è un BQO.
Teorema di Laver
Teorema di Laver
Teorema (di Laver, 1971)
La classe (V , ) degli ordini totali sparsi è un Better-Quasi-Order. La dimostrazione è per assurdo. Sia f : [N]ω → V un V -array cattivo.
• Con un opportuno ranking parziale dato dal rango di Hausdorff, si può supporre che f sia minimale.
• Per Hausdorff, ogni ordine sparso L è finito o è sommaP i ∈ILi
indicizzata da un ordinale o da un suo inverso, di elementi di rango strettamente inferiore di L. Ciò fornisce una 3-colorazione di V . • Per Galvin e Prikry, a meno di V -sotto-array, f è monocromatico.
Senza perdite di generalità, f (X ) è sempre somma indicizzata da un ordinale di ordini sparsi di rango inferiore f (X ) =P
i ∈αXL
i X.
• Associando alla somma P i ∈αX L
i
X, la successione (LiX)i ∈αX, si ottiene ilV -array cattivo g : [N]e ω →V tale che g (X ) = (Le iX)i ∈α
X. • Per il teorema di Nash-Williams, si può estrarre da g un V -array
Bibliografia essenziale
Bibliografia essenziale I
[1] Roland Fraïssé. «Sur la comparaison des types d’ordres». In: Comptes
Rendus Hebdomadaires des Séances de l’Académie des Sciences.
1948.
[2] Fred Galvin e Karel Prikry. «Borel Sets and Ramsey’s Theorem». In:
Journal of Symbolic Logic (1973).
[3] Richard Laver. «On Fraisse’s Order Type Conjecture».In: Annals of
Mathematics (1971).
[4] Richard Laver. «Well-quasi-orderings and sets of finite sequences».In:
Mathematical Proceedings of the Cambridge Philosophical Society
(1976).
[5] C. St. J. A. Nash-Williams.«On better-quasi-ordering transfinite sequences». In: Mathematical Proceedings of the Cambridge
Bibliografia essenziale
Bibliografia essenziale II
[6] C. St. J. A. Nash-Williams. «On well-quasi-ordering infinite trees».In:
Mathematical Proceedings of the Cambridge Philosophical Society
(1965).
[7] Stephen G. Simpson. «Bqo Theory and Fraïssé Conjecture». In:
