The Borel monadic theory of order is decidable

Speaker(s)

Sven Manthe

Affiliation

University of Bonn

Language of the talk

English

Date

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

Room

room 5050

Title in Polish

The Borel monadic theory of order is decidable

Seminar

Seminar Automata Theory

---

When proving decidability of S2S, Rabin derived decidability of the monadic theory of (ℝ,<) with quantification restricted to Fσ-sets. Undecidability of the unrestricted monadic theory of (ℝ,<) was proven by Shelah. We discuss decidability for Borel sets, or even σ-combinations of analytic sets. Moreover, the Boolean combinations of Fσ-sets yield the same theory. The proof relies on Baire category methods. Thus, under determinacy hypotheses, it extends to larger classes of sets.

---