Paper: The Uniformisation of Monadic Second-Order Logic over Countable Ordinals (at LICS 2026)

Authors: Thomas Colcombet Alexander Rabinovich

Open access: https://doi.org/10.4230/LIPIcs.LICS.2026.30

Abstract

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.

BibTeX

  @InProceedings{ColcombetRabinovich-TheUniformisationof,
    author = 	 {Thomas Colcombet and Alexander Rabinovich},
    title = 	 {The Uniformisation of Monadic Second-Order Logic over Countable Ordinals},
    booktitle =  {Proceedings of the Forty-First Annual Symposium on Logic in Computer Science (LICS 2026)},
    year =	 {2026},
    month =	 {July}, 
    pages =      {30:1--30:24},
    location =   {Lisbon, Portugal}, 
    publisher =	 {Schloss Dagstuhl -- Leibniz-Zentrum für Informatik},
    doi =        {10.4230/LIPIcs.LICS.2026.30}
  }