The Borel monadic theory of order is decidable

Prelegent(ci)

Sven Manthe

Afiliacja

University of Bonn

Język referatu

angielski

Termin

14 maja 2025 16:15

Pokój

p. 5050

Seminarium

Seminarium „Topologia i teoria mnogości”

---

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.

---