Email this article Logical laws for existential monadic second-order sentences with infinite first-order parts
- Authors: Zhukovskii M.E.1,2, Sánchez M.G.1
-
Affiliations:
- Moscow Institute of Physics and Technology (State University)
- RUDN University
- Issue: Vol 96, No 3 (2017)
- Pages: 598-600
- Section: Mathematics
- URL: https://journals.rcsi.science/1064-5624/article/view/225428
- DOI: https://doi.org/10.1134/S1064562417060242
- ID: 225428
Cite item
Open Access
Access granted
Subscription Access
Abstract
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.
About the authors
M. E. Zhukovskii
Moscow Institute of Physics and Technology (State University); RUDN University
Author for correspondence.
Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700; Moscow, 117198
M. G. Sánchez
Moscow Institute of Physics and Technology (State University)
Email: zhukmax@gmail.com
Russian Federation, Dolgoprudnyi, Moscow oblast, 141700
Supplementary files
