logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11242020-164248


Tipo di tesi
Elaborati finali per laurea triennale
Autore
CACCAVALE, ALBERTO
URN
etd-11242020-164248
Titolo
Dalla congettura di Fraisse' al teorema di Laver
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Prof. Berarducci, Alessandro
Parole chiave
  • better-quasi-order
  • ordine totale
  • quasi-ordine
  • teoria degli ordini
  • well-quasi-order
Data inizio appello
23/10/2020
Consultabilità
Completa
Riassunto
La tesi tratta di una famosa congettura di Fraisse' del 1948 sugli ordini totali numerabili, risolta da Laver nel 1971. Si illustrano tutti i risultati che sono stati necessari per dimostrarla, in particolare quelli sui Well-Quasi-Orders e sui Better-Quasi-Orders. Si conclude quindi affrontando la dimostrazione di Laver.
Per enunciare la congettura si definisce l'ordinamento sulla classe degli ordini totali dato dall'immersione, dicendo che due ordini totali A e B sono uno minore o uguale dell'altro se esiste una funzione da A in B iniettiva e che preserva l'ordine. Si osserva che questo ordinamento è riflessivo e transitivo ma non simmetrico, ossia è un quasi-ordine.
La congettura di Fraisse' afferma che la classe degli ordini totali numerabili, ordinata per immersione, non ammette catene infinite strettamente decrescenti, né anticatene infinite.
Si enuncia un teorema di Cantor, grazie al quale la congettura si riduce a dover essere dimostrata solo sugli ordini totali sparsi numerabili.
Per tale scopo si richiama un importante teorema di Hausdorff sulla classe degli ordini totali sparsi.
In seguito si introduce la nozione di Well-Quasi-Order, vedendone le varie proprietà ed osservando che non sono sufficienti per il nostro scopo.
Si introduce quindi la nozione di Better-Quasi-Order. Questi sono una sottoclasse dei WQO in un certo senso più "stabile". Passando per un teorema dovuto a Galvin e Prikry, si illustrano i principali risultati sui BQO, in particolare il Minimal Bad Array Lemma ed il teorema di Nash-Williams.
Si conclude vedendo la dimostrazione di Laver e la costruzione di un controesempio, dovuta a Sierpiski, alla congettura, nel caso in cui si rinunci all'ipotesi di numerabilità degli ordini totali.
File