Seminar series
Date
Thu, 14 Nov 2024
Time
17:00 - 18:00
Location
L3
Speaker
Sven Manthe
Organisation
University of Bonn

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.

Last updated on 21 Oct 2024, 12:20pm. Please contact us with feedback and comments about this page.