The Borel monadic theory of order is decidable

Speaker(s)

Sven Manthe

Affiliation

University of Bonn

Language of the talk

English

Date

May 14, 2025, 4:15 p.m.

Room

room 5050

Seminar

Topology and Set Theory Seminar

---

The monadic second-order theory S1S of (ℕ,<) is decidable (it essentially describes ω-automata). Undecidability of the monadic theory of (ℝ,<) was proven by Shelah. Previously, Rabin proved decidability if the monadic quantifier is restricted to F_σ-sets.
We discuss decidability for Borel sets, or even σ-combinations of analytic sets. Moreover, the Boolean combinations of F_σ-sets form an elementary substructure. Under determinacy hypotheses, the proof extends to larger classes of sets.

---