Logical laws for existential monadic second-order sentences with infinite first-order parts


Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

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

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML

© Pleiades Publishing, Ltd., 2017