The Uniformisation of Monadic Second-Order Logic over Countable Ordinals

We study the uniformisation problem for monadic second-order logic (MSO) over countable ordinal chains. Given a formula defining a relation between subsets of the input structure, the question is whether there exists a formula that defines a function selecting, for every set in the domain of the relation, a unique set such that the pair belongs to the relation. It is known, due to Lifsches and Shelah [Lifsches and Shelah, 1998], that MSO cannot, in general, be uniformised over the class of countable ordinals. We show that the maximal uniformisation degree is reached by extending the logic with a predicate that, given a set, selects (when possible) a cofinal subset of order type ω. Equivalently, every MSO formula can be uniformised over the class of countable ordinal chains using a formula in this extended logic.