O CEMS.UL - Centro de Estudos Matemáticos promove a realização do seminário "Better-quasi-orders in systems of partial impredicativity", com a participação de Davide Manca (Universidade Técnica de Viena).
Abstract: The notion of better-quasi-order, introduced by Nash-Williams, is a natural strengthening of the fundamental combinatorial property of being a well-quasi-order. Its main use is in dealing with infinitary data types. For example, Higman's theorem states that finite sequences in a well-quasi-order Q form a well-quasi-order under a suitable notion of embedding, but this fact does not hold in general for transfinite sequences. Nash-Williams proved that, if Q is a better-quasi-order rather than just a well-quasi-order, then transfinite sequences in Q form a better-quasi-order.
Proofs of well- and better-quasi-ordering results often use impredicative principles, such as the minimal bad sequence argument. In some cases, it is even known that no fully predicative proof can exist. In reverse mathematics, the strength of those results can be estimated in terms of systems of partial impredicativity, such as Towsner’s TLPP_0.
In joint work with Patrick Uftring, we prove a better-quasi-ordering version of a result by Gordeev, which states that sequences in a well-order form a well-quasi-order even under embeddings that satisfy a symmetrical gap condition. Moreover, we show that for sequences with length ω this fact can be proven in TLPP_0.