Logical laws for existential monadic second-order sentences with infinite first-order parts
Maksim Evgen'evich Zhukovskii, Mickel González Sánchez · Doklady Mathematics · 2017
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.