A Dichotomy Theorem for Ordinal Ranks in MSO

Speaker(s)

Paweł Parys

Affiliation

University of Warsaw

Language of the talk

English

Date

Dec. 4, 2024, 2:15 p.m.

Room

room 5440

Title in Polish

A Dichotomy Theorem for Ordinal Ranks in MSO

Seminar

Seminar Automata Theory

---

We focus on formulae ∃X.ϕ(Y, X) of monadic second-order logic over the 
full binary tree, such that the witness X is a well-founded set. The 
ordinal rank rank(X) < ω_1 of such a set X measures its depth and 
branching structure. We search for the least upper bound for these ranks, 
and discover the following dichotomy depending on the formula ϕ. Let η be 
the minimal ordinal such that, whenever an instance Y satisfies the 
formula, there is a witness X with rank(X) ≤ η. Then η is either strictly 
smaller than ω^2 or it reaches the maximal possible value ω_1. Moreover, 
it is decidable which of the cases holds. The result has potential for 
applications in a variety of ordinal-related problems, in particular it 
entails a result about the closure ordinal of a fixed-point formula.

The talk will be based on a joint work with Damian Niwiński and Michał 
Skrzypczak. Last week Michał presented some motivation for the result that 
I will present. However, I will introduce all necessary definitions, so no 
knowledge from the previous week is needed to understand my talk.

---