Logical laws for existential monadic second-order sentences with infinite first-order parts
- Авторы: Zhukovskii M.1,2, Sánchez M.1
-
Учреждения:
- Moscow Institute of Physics and Technology (State University)
- RUDN University
- Выпуск: Том 96, № 3 (2017)
- Страницы: 598-600
- Раздел: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225428
- DOI: https://doi.org/10.1134/S1064562417060242
- ID: 225428
Цитировать
Аннотация
We consider existential monadic second-order sentences ∃X φ(X) about undirected graphs, where ∃X is a finite sequence of monadic quantifiers and φ(X) ∈ +∞ωω is an infinite first-order formula. We prove that there exists a sentence (in the considered logic) with two monadic variables and two first-order variables such that the probability that it is true on G(n, p) does not converge. Moreover, such an example is also obtained for one monadic variable and three first-order variables.
Об авторах
M. Zhukovskii
Moscow Institute of Physics and Technology (State University); RUDN University
Автор, ответственный за переписку.
Email: zhukmax@gmail.com
Россия, Dolgoprudnyi, Moscow oblast, 141700; Moscow, 117198
M. Sánchez
Moscow Institute of Physics and Technology (State University)
Email: zhukmax@gmail.com
Россия, Dolgoprudnyi, Moscow oblast, 141700