Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив

Поиск
RSS
Новые поступления






Международная конференция «Novikov-125», посвящённая 125-летию со дня рождения П.С. Новикова
26 августа 2026 г. 15:50–16:30, Секция А, г. Москва, МИАН, ауд. 104
 


MSO logic of the real order with the set quantifiers ranging over the Borel sets

M. Džamonja
Дополнительные материалы:
Adobe PDF 489.8 Kb

Количество просмотров:
Видеофайлы:21
Материалы:8

M. Džamonja
Фотогалерея



Аннотация: A celebrated 1969 theorem of Michael Rabin is that the monadic second-order (MSO) theory of the real order where the monadic quantifier is allowed only to range over the closed or $F_\sigma$-sets, is decidable. In 1975 Saharon Shelah conjectured that if the monadic quantifier is allowed to range over the Borel subsets of the reals, the resulting MSO theory is still decidable. We confirm this conjecture. In fact, the conjecture can be understood in the weak form, in the language where there is a special symbol for each level of the Borel hierarchy, or in a strong form where the language simply has a symbol for Borel sets. We confirm both versions of the conjecture, the former one by interpreting it in $\mathrm{S2S}$ and the latter one by in addition using Büchi's theorem that $\mathrm{MSO} \left( \omega_1, \lt \right)$ is decidable.

Дополнительные материалы: dzamonja_slides.pdf (489.8 Kb)

Язык доклада: английский
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2026