On the Expansion of Monadic Second-Order Logic with Cantor-Bendixson Rank and Order Type Predicates

Thomas Colcombet, Alexander RabinovichCSL 2025 · DOI

TL;DR

This paper investigates extending monadic second-order logic (MSO) with new predicates for "Cantor-Bendixson rank" and "order type." The core finding is that these extensions are decidable if and only if the new predicates are already expressible in standard MSO. This implies that adding these specific complexity measures doesn't increase the expressive power of MSO without sacrificing decidability.

What Problem Does This Paper Address?

Monadic second-order logic (MSO) is a powerful logic used in areas like automata theory and verification. It's known for its strong decidability properties, meaning there are algorithms to determine if an MSO formula is true for certain structures. Researchers are interested in extending MSO to capture more complex properties while retaining decidability. This paper focuses on two natural extensions:

  1. Cantor-Bendixson Rank: This measures the "branching complexity" of infinite trees. The question is whether MSO can be extended with a predicate that checks if a subtree has a specific Cantor-Bendixson rank, and if this extension remains decidable.
  2. Order Type: This describes the structure of well-founded linear orders. The question is whether MSO can be extended with a predicate that checks if a subset of an ordinal has a specific order type, and if this extension remains decidable.

The authors aim to understand the boundary between expressiveness and decidability for these extensions.

Methods

The paper employs a combination of techniques from logic, set theory, and computability theory.

  • Model Theory and Definability: A central theme is understanding what properties can be defined within MSO. If a new predicate (like Cantor-Bendixson rank or order type) can already be expressed using existing MSO formulas, then adding it as a primitive predicate won't change the logic's expressive power or decidability.
  • Reduction to Undecidability: The core of proving undecidability for the extended logics involves reducing known undecidable problems to them. The paper heavily relies on the undecidability of BMSO (a logic related to MSO with boundedness quantifiers) and MSO+U (MSO with a quantifier for "arbitrarily large cardinality").
  • Ordinal Arithmetic and Structure Theory: The proofs involve intricate arguments about the structure of ordinals and trees, particularly using concepts like Cantor normal form, w-sums of trees, and the Cantor-Bendixson rank definition.
  • Relativization: A standard technique in MSO is used to restrict formulas to substructures, which is crucial for relating properties of ordinals to properties of subsets.

Datasets

Not discussed in the paper. The paper deals with theoretical properties of logical systems and mathematical structures (ordinals, trees), not empirical data.

Key Insights and Ideas

  • Decidability is Tied to Definability: The most striking insight is the tight link between decidability and definability for these extensions. If the new predicate is already definable in MSO, the extended logic is decidable. If it's not definable, the extended logic becomes undecidable. This suggests that these specific extensions don't offer "new" expressive power without a decidability cost.
  • The Role of Ordinal Structure: The paper highlights how the specific structure of ordinals (especially their Cantor normal form and cofinality) dictates the decidability of MSO extensions. For instance, ordinals like $\omega^\omega$ and $\omega_1$ play critical roles as boundaries.
  • Cantor-Bendixson Rank and Order Type are "Just Enough": The results show that adding predicates for Cantor-Bendixson rank and order type to MSO doesn't fundamentally change its decidability status unless the specific rank or order type is already expressible in MSO. This means these predicates, while useful for describing complexity, don't unlock new decidable computational problems beyond what MSO already handles.

Key Results

  • Theorem 1: The MSO extension with Cantor-Bendixson rank predicates ($MSO[CBrank_\alpha]$) is decidable over the full binary tree if and only if the rank $\alpha$ is finite (meaning $CBrank_\alpha$ is MSO-definable).
  • Theorem 2: The MSO extension with order type predicates ($MSO[otp_\alpha]$) is decidable over countable ordinals if and only if $\alpha < \omega^\omega$ (meaning $otp_\alpha$ is MSO-definable for $\alpha < \omega^\omega$).
  • Theorem 54: For ordinals $\alpha < \omega_1$, the $MSO[otp_\alpha]$-theory of $\alpha$ is decidable if and only if $\alpha$ is MSO-definable. This extends the result to uncountable ordinals up to $\omega_1$.
  • The proofs establish undecidability by reducing known undecidable problems (like BMSO satisfiability) to the extended logics.

Limitations and Future Work

  • Uncountable Ordinals Beyond $\omega_1$: The paper focuses on ordinals up to $\omega_1$. The decidability of $MSO[otp_\alpha]$ for $\alpha \ge \omega_1$ remains an open question.
  • Degree of Undecidability: While the paper establishes undecidability for certain extensions, the precise "degree" of this undecidability (e.g., its position in the arithmetic hierarchy) is left as an open problem.
  • Cantor-Bendixson Rank for Undecidable Cases: The paper shows that $MSO[CBrank_\alpha]$ is undecidable for $\alpha \ge \omega$. The exact decidability boundary for this extension is also a subject for future work.
  • Hausdorff Rank: The paper briefly touches upon Hausdorff rank for linear orders and suggests further research into its decidability with MSO extensions, noting that $MSO[Hrank_\alpha]$ is undecidable for $\alpha \ge \omega$.

Summary updated

BibTeX
@inproceedings{colcombet2025expansion,
  author = {Thomas Colcombet and Alexander Rabinovich},
  title = {{On the Expansion of Monadic Second-Order Logic with Cantor-Bendixson Rank and Order Type Predicates}},
  booktitle = {CSL},
  year = {2025},
  doi = {10.4230/lipics.csl.2025.11},
}
Figure