Logic Colloquium 2024


Giovanni Solda

Ghent University

Talks at this conference:

  Wednesday, 15:40, J431

Better quasi-orders and iterated ideals

Authors: Giovanni Solda and Fedor Pakhomov

The notion of better quasi-order (henceforth bqo) is a natural evolution of that of well quasi-order (henceforth wqo). Intuitively, a wqo is bqo if all of its iterated powersets are also wqo’s: this gives bqo’s much stronger closure properties than the ones wqo’s enjoy.

In this talk, we give a new characterization of bqo’s. Inspired by the intuition we gave above, we look at the class of iterated ideals of a wqo: this produces a much smaller object than the iterated powerset. Our main result is that this smaller object still contains a lot of information on the original wqo: namely, a wqo \(Q\) is bqo if and only if the iterated ideals of \(Q\) form a wqo, and the formalization of this result in second-order arithmetic is provable over \(\mathsf{ATR}_0\). We will then show some properties of the class of iterated ideals, and point at some (potential) applications.