Zero–One Laws for Sentences with k Variables

Abstract

The k-variable fragment of first-order logic on graphs is considered. It is proved that, for \(\alpha \leqslant \frac{1}{{k - 1}},\) the random graph \(G(n,{{n}^{{ - \alpha }}})\) obeys the zero–one law with respect to this logic. Moreover, for every \(\varepsilon > 0\), there exists \(\alpha \in \left( {\frac{1}{{k - 1}},\frac{1}{{k - 1}} + \varepsilon } \right)\) such that \(G(n,{{n}^{{ - \alpha }}})\) does not obey the law.