The Borel monadic theory of order is decidable

Prelegent(ci)

Sven Manthe

Afiliacja

University of Bonn

Język referatu

angielski

Termin

4 września 2024 14:15

Pokój

p. 5050

Tytuł w języku polskim

The Borel monadic theory of order is decidable

Seminarium

Seminarium „Teoria automatów”

---

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.

---