Teoria dei wqo e dei bqo e applicazioni
a.a. 2023/24
Responsabile didattico: Alberto G. Marcone
Docenti: Alberto G. Marcone, Gabriele Puppis
Durata: 28 ore
Programma: I wqo (well quasi-orders) sono un'importante classe di ordini parziali che sono stati introdotti e studiati in varie aree della matematica. Mostreremo l'equivalenza delle varie definizioni e dimostreremo i risultati fondamentali della teoria. Negli anni '60 del secolo scorso Nash-Williams introdusse un rafforzamento della nozione di wqo e la chiamò bqo (better quasi-order): questa nozione ha permesso di dimostrare la congettura di Fraïssé secondo cui gli ordini numerabili formano un wqo quando sono confrontati per immergibilità. I wqo e i bqo hanno trovato applicazioni in campo informatico, per esempio nell'area della verifica automatica, e alcune lezioni del corso saranno dedicate a queste applicazioni.