Logical Laws for Existential Monadic Second-Order Sentences with Infinite First-Order Parts

摘要

We consider existential monadic second-order sentences there exists X phi(X) about undirected graphs, where there exists X is a finite sequence of monadic quantifiers and phi(X) is an element of L-infinity omega(omega) 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.