Аннотация:$k$-Спектром называется множество таких положительных чисел $\alpha$, что биномиальный случайный граф $G(n,n^{-\alpha})$ не подчиняется закону нуля или единицы для формул первого порядка кванторной глубины не более $k$. Мы доказали, что минимальное $k$, при котором $k$-спектр бесконечен, равно 5.
Ключевые слова:логика первого порядка, биномиальный случайный граф, закон нуля или единицы, спектр формулы, игра Эренфойхта.
УДК:
519.175.4
Статья представлена к публикации:В. В. Козлов Поступило: 27.04.2021 После доработки: 07.07.2021 Принято к публикации: 18.08.2021