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


Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Somente assinantes

Resumo

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.

Sobre autores

M. Zhukovskii

Moscow Institute of Physics and Technology (State University); RUDN University

Autor responsável pela correspondência
Email: zhukmax@gmail.com
Rússia, Dolgoprudnyi, Moscow oblast, 141700; Moscow, 117198

M. Sánchez

Moscow Institute of Physics and Technology (State University)

Email: zhukmax@gmail.com
Rússia, Dolgoprudnyi, Moscow oblast, 141700

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML

Declaração de direitos autorais © Pleiades Publishing, Ltd., 2017