| Известия Российской академии наук. Серия математическая |
|
|
|
|
|
Эта публикация цитируется в 5 научных статьях (всего в 5 статьях) Решетка определимости (редуктов) для целых чисел с операцией следования А. Л. Семёновabc, С. Ф. Сопруновd a Московский государственный университет имени М. В. Ломоносова b Институт кибернетики и образовательной информатики им. А. И. Берга, Федеральный исследовательский центр «Информатика и управление» Российской академии наук c Московский физико-технический институт (национальный исследовательский университет), Московская облаcть, г. Долгопрудный d Центр педагогического мастерства, г. Москва
Англоязычная версия:
Izvestiya: Mathematics, 2021, Volume 85, Issue 6, Pages DOI: https://doi.org/10.1070/IM9107 
Реферативные базы данных:
   § 1. Введение. История вопросаРезультаты настоящей работы относятся к теории определимости, к вопросу о том, можно ли определить одни отношения через другие. Альфред Тарский сказал: “Mathematicians, in general, do not like to operate with the notion of definability; their attitude towards this notion is one of distrust and reserve” [1; с. 110]. (“Математики вообще не любят оперировать понятием определимости; они относятся к этому понятию с недоверием и сдержанностью”.) И действительно, результатов (и публикаций) в теории определимости намного меньше, чем в теории моделей или теории доказательств. В 1959 г. Ларс Свенониус установил фундаментальный результат в данной области (см. ниже), который можно считать аналогом теоремы о полноте. С параллели между определимостью и доказуемостью Тарский начинает свою статью “Some methodological investigations on the definability of concepts” [1; с. 296–310]. В начале 1970-х годов Альберт Абрамович Мучник (1934–2019), ученик П. С. Новикова и научный руководитель А. Л. Семенова, поставил перед последним ряд задач, относящихся к определимости в структурах, связанных с конечными автоматами. Одной из этих задач было – обобщить теорему Кобхема об определимости через сложение свойств, конечно-автоматных в двух системах счисления, на многомерный случай. Решение этой задачи составило один из результатов кандидатской диссертации А. Л. Семенова, см. [2]. В дальнейшем Андрей Альбертович Мучник (1958–2007), сын Альберта Абрамовича и ученик А. Л. Семенова, нашел новое доказательства теоремы Кобхема–Семенова, использующее введенное им понятие самовыразимости (самоопределимости). Результаты Семенова и Андрея Мучника использовались и обсуждались в ряде работ, среди недавних публикаций, например, см. [3]. Тогда же, в начале 1970-х, Альберт Мучник, со ссылкой на П. С. Новикова, сформулировал проблему описания решетки пространств определимости (термин возник позднее) для сложения целых чисел. Задача не казалось такой уж сложной, и А. Л. Семенов предлагал ее своим студентам, двое из них – Л. В. Костюков (в дальнейшем – известный писатель) и О. В. Митина (в дальнейшем – кандидат психологических наук, сотрудник МГУ) – предложили эквивалентные гипотезы о составе элементов этой решетки, но в их доказательствах содержались пробелы. Стало ясно, что проблема совсем не проста. С другой стороны, авторов настоящей работы заинтересовала и общая проблематика решеток определимости. В частности, в классической работе Элгота и Рабина [4] в связи с расширениями пространства конечно-автоматной определимости был поставлен вопрос о существовании максимальных разрешимых пространств определимости. Для слабого монадического случая эта проблема была решена С. Сопруновым в [5]. Для логики первого порядка и монадической логики проблема остается открытой. В последующие годы авторы настоящей работы и Андрей Мучник предприняли исследование различных вопросов, связанных с решетками определимости, см., например, [6]. В частности, авторами настоящей работы был получен комбинаторный аналог теоремы Свенониуса [7]. Были построены примеры пространств произвольной ширины [8]. Чтобы проиллюстрировать спектр результатов в данной области, укажем несколько примеров. Первый значительный результат – описание решетки определимости рациональных чисел с порядком – был получен Клодом Френе в 1965 г. [9] (как это указано в [10]). С тех пор этот результат неоднократно переоткрывался (см. [11], [6]). Как показано в этих работах, решетка подпространств для порядка рациональных чисел содержит 5 элементов. Если к структуре добавить нуль, то элементов будет 116, см. [12]; решетка для случайного графа – это 5 элементов, для случайного линейного порядка – это 42 элемента [13]. Среди последних результатов отметим доказательство [14] отсутствия пространств, лежащих строго между пространством, порожденным отношением $+$, и всеми константами на носителе $\mathbb Z$, и пространством, порожденным отношениями $+$, $<$ на том же носителе. Некоторые итоги авторы настоящей статьи подвели вместе с Владимиром Андреевичем Успенским в обзоре [15]. Там же был объявлен основной результат настоящей статьи. Далее в тексте статьи мы даем необходимые определения, формулируем теорему Свенониуса и следствие из нее, которое будем использовать; описываем изучаемую решетку; наконец, формулируем гипотезы и открытые проблемы. § 2. ОпределенияПусть $S$ – семейство отношений на носителе $A$ и $R$ – имя отношения на $A$. Определимость отношения $R$ через $S$ в логическом языке $L$ означает, что: (1) выбраны имена для отношений из конечного подмножества $S$, и (2) имеется формула в языке $L$, эквивалентная $R$ (на $A$), содержащая выбранные имена в качестве внелогических символов. Определимое замыкание набора $S$ (обозначаемое $[S]$) состоит из всех определимых через $S$ отношений. Эта операция является обычным топологическим и алгебраическим замыканием (замыканием Куратовского). Множество $S$ является базой определимого замыкания $[S]$. Замкнутые множества отношений называются пространствами определимости. Семейство пространств определимости на заданном носителе образуют решетку определимости с операциями пересечения и замыкания теоретико-множественного объединения. Если $S_1$ и $S_2$ – наборы отношений на одном и том же носителе, то $S_1 \succcurlyeq S_2$ означает, что пространство определимости, порожденное набором $S_2$ вложено в пространство, порожденное $S_1$. Если $S_1 \succcurlyeq S_2$ и $S_2 \succcurlyeq S_1$, то $S_1 \approx S_2$. Соответственно понимается и символ $\succ$. Пространство определимости счетно, если оно счетно или конечно и носитель счетный. В данной работе язык $L$ – это язык первого порядка с равенством, и рассмотрение ограничивается счетными пространствами определимости. Пространство определимости структуры – это семейство всех определимых в данной структуре отношений. Решетку определимости образуют все подпространства этого пространства. Ясно, что если структуры элементарно эквивалентны, то их решетки изоморфны. Среди хорошо известных примеров пространств определимости имеются арифметические отношения, алгебраические отношения, автоматно-определимые отношения, пресбургеровы (т. е. порожденные на $\mathbb Z$ отношениями $+$, $\leqslant$) отношения. Подпространства пространства называются также редуктами исходного пространства или исходной структуры. Целью данной работы является описание решетки определимости структуры целых чисел с операцией следования. § 3. Перестановки и теорема СвенониусаПерестановкой на множестве $A$ называется биекция множества $A$ на $A$. Группа всех перестановок множества $A$ обозначается $\operatorname{Sym}(A)$. Перестановка $\varphi$ на множестве $A$ сохраняет отношение $R$ на множестве $A$ тогда и только тогда, когда для любого набора $\overline a$ элементов множества $A$ выполнено $R(\overline a) \equiv R(\varphi (\overline a))$, где $\varphi (\overline a)$ – набор образов элементов $\overline a$ при отображении $\varphi$. Перестановка сохраняет множество отношений $S$, если она сохраняет все отношения из множества $S$. Семейство $F$ перестановок сохраняет $S$, если каждая перестановка из $F$ сохраняет $S$. Каждому набору отношений $S$ можно сопоставить группу $G_S \subseteq \operatorname{Sym}(A)$. Группа $G_S$ содержит все перестановки, сохраняющие множество $S$. Имеет место $S_1 \subseteq S_2 \Rightarrow G_{S_1} \supseteq G_{S_2}$ (антимонотонное соответствие Галуа). Однако восстановить пространство определимости по соответствующей группе обычно непросто. Группа, соответствующая подпространству, называется надгруппой группы исходного пространства. Пусть $S_1$ – пространство определимости на носителе $A$, множество $B \subseteq A$, и пусть $S_2$ – семейство отношений на $B$, являющихся ограничениями отношений из $S_1$. Предположим, что заданы имена для отношений из конечного подмножества $F$ множества $S_1$, и те же самые имена используются для ограничения отношений из набора $F$ на $B$. Каждая формула, содержащая только эти имена, определяет два отношения: одно на $A$ и второе на $B$. Второе отношение не обязано быть ограничением первого на множестве $B$, но если оно является ограничением для любой формулы, то пространство $S_2$ называется элементарным ограничением пространства $S_1$ (а $S_1$ является элементарным расширением пространства $S_2$). Любое элементарное ограничение пространства определимости является пространством определимости. Основным инструментом в данной работе является теорема Свенониуса [16], точнее, следствие из нее, приведенное ниже. Эта теорема может быть сформулирована следующим образом, см. [17; с. 516]. Теорема Свенониуса. Пусть $S^-$, $S$ – счетные пространства определимости на носителе $A$, причем $S^-\subset S$. Тогда для любого отношения $R \in S$ следующие два утверждения равносильны: (a) $R \in S^-$; и (b) для любого счетного пространства определимости $S'$, являющегося элементарным расширением пространства $S$, и любых $S_0 \subset {S}', R_0 \in {S}'$, таких, что ограничение $S_0$ на $A$ совпадает с $S^-$, ограничение $R_0$ на $A$ совпадает с $R$, группа перестановок носителя пространства $S'$, сохраняющая все отношения из $S_0$, сохраняет и $R_0$. Таким образом, теорема Свенониуса утверждает, что если мы рассматриваем перестановки не только исходного пространства, но и перестановки элементарных расширений, то возможно различить подпространства исходного пространства. Примеры использования групп перестановок для описания решеток определимости см., например, в [10]. Счетное пространство определимости назовем максимальным, если структуры всех его счетных элементарных расширений изоморфны (при надлежащем выборе имен для отношений). В случае максимальных пространств формулировка теоремы Свенониуса особенно проста. Следствие 3.1. Пусть $S^-$, $S$ – счетные пространства определимости на носителе $A$, причем $S^- \subset S$ и пространство $S$ максимально. Тогда для любого отношения $R \in S$ следующие два утверждения равносильны: (a) $R \in S^-$; и (b) группа перестановок на $A$, сохраняющая все отношения из $S^-$, сохраняет $R$. § 4. РезультатыВ данном параграфе описывается решетка пространства определимости структуры $\langle \mathbb Z, \{'\}\rangle$ – множества целых чисел с отношением следования. Для каждого натурального числа $n$ положим: $A_{0,n}(x_1,x_2)\leftrightharpoons |x_1-x_2|=n$; $A_{1,n}(x_1,x_2,x_3,x_4) \leftrightharpoons x_1-x_2=x_3-x_4=n \lor x_1-x_2=x_3-x_4=-n$; $A_{2,n}(x_1,x_2) \leftrightharpoons x_1-x_2=n$. Таким образом, для любого натурального $n$ выполнено
$$
\begin{equation*}
A_{0,n} (x_1 , x_2) \equiv A_{1,n} (x_1 , x_2 ,x_1 , x_2)
\end{equation*}
\notag
$$
и $A_{1,n}$ явно определимо через $A_{2,n}$. Естественно продолжить $A_{0,n}$ до $A_{0,0}$ как равенства. Таким образом,
$$
\begin{equation*}
A_{2,n} \succcurlyeq A_{1,n}\succcurlyeq A_{0,n} \succcurlyeq A_{0,0}.
\end{equation*}
\notag
$$
Следуя [6], будем считать, что отношение ложно всегда, когда значения двух его аргументов совпадают. Такие отношения мы называем несклеивающими. Нетрудно заметить, что для любого отношения $R$ можно построить конечный набор несклеивающих отношений, порождающий то же самое пространство определимости, что и отношение $R$. Всюду в дальнейшем определимое отношение – это несклеивающее определимое отношение. Теорема 4.1. Если отношение $R$ определимо в $\langle \mathbb Z, \{'\}\rangle$, то $R \approx A_{i,d}$ для некоторого натурального $d$ и некоторого $i;$ кроме того (i) все $[A_{i,d}]$ различны; (ii) $[A_{i,d}] \cup [A_{j,k}] = [A_{m,n}]$, где $m=\max\{i,j\}, n=\operatorname{\textrm{НОД}}(d,k)$; (iii) $[A_{i,d}] \cap [A_{j,k}] = [A_{m,n}]$, где $m=\min\{i,j\}, n= \operatorname{\textrm{НОК}}(d,k)$. Все дальнейшее изложение состоит в доказательстве теоремы 4.1. Доказательство основано на использовании следствия 3.1 теоремы Свенониуса. Всякая структура $M$, элементарно эквивалентная $\langle \mathbb Z, \{'\}\rangle$, представляет из себя объединение отдельных экземпляров множества $\mathbb Z$. Эти копии называются галактиками. Все структуры, состоящие из счетного семейства галактик, изоморфны. Таким образом, все они максимальны. Эту единственную (с точностью до изоморфизма) структуру мы обозначим $\mathbb Z^\omega$. Таким образом, следствие 3.1 применимо к $\mathbb Z^\omega$. Определим упорядоченное множество $Z_\infty = \mathbb Z \cup \{\infty\}$ так, что порядок на $\mathbb Z$ стандартный, и $z<\infty$ для всех $z \in \mathbb Z$. Далее, функцию модуля ($||$) определим на $Z_\infty$ так, что она стандартна на $\mathbb Z$ и $|\infty|=\infty$. Функция вычитания ($-$) отображает $\mathbb Z^\omega$ на $Z_\infty$, совпадает с разностью на каждой галактике (являющейся копией $\mathbb Z$) и равна $\infty$, если аргументы в разных галактиках. Выражение $a>b$ при $a,b \in \mathbb Z^\omega$ является сокращением для $\infty >a-b>0$. Далее перестановкой мы называем перестановку на носителе структуры $\mathbb Z^\omega$. Перестановка $\gamma$ называется сдвигом, если $\gamma(a)-\gamma(b) = a-b$ для любых $a,b \in \mathbb Z^\omega$. Группа всех перестановок, сохраняющих отношение $'$, является группой всех сдвигов, обозначим ее через $\Gamma$. Для любых $a,b \in \mathbb Z^\omega$ найдется сдвиг $s$, такой, что $s(a)=b$, поэтому очевидно, что любое $1$-местное отношение, определимое в $\mathbb Z^\omega$, является константой. Лемма 4.1. Пусть наборы $a_0, \dots, a_{n-1}, b_0, \dots, b_{n-1} \in \mathbb Z^\omega $ таковы, что $ a_i-a_j=b_i-b_j$ выполнено для всех $i, j$. Пусть, далее, частичное отображение $\gamma$ для каждого $a_0, \dots, a_{n-1}$ задано равенством $\gamma(a_i)=b_i$. Тогда частичное отображение $\gamma$ может быть продолжено до сдвига. Лемма 4.1 очевидна, достаточно рассмотреть элементы из одной и той же и из разных галактик. Пусть группа перестановок $\Gamma'$ содержит группу сдвигов $\Gamma$. Тогда $z_1,z_2 \in \mathbb Z$ называются эквивалентными (относительно группы $\Gamma'$), если для некоторых $\gamma \in \Gamma'$, $a \in \mathbb Z^\omega$ выполнено $\gamma(a+z_1) - \gamma(a)=z_2$. Данное отношение является отношением эквивалентности ввиду свойств надгруппы группы сдвигов. Докажем транзитивность (прочие свойства доказываются еще проще). По определению, если $z_1 \sim z_2, z_2 \sim z_3$, то для некоторых $\gamma_1$, $a_1$, $\gamma_2$, $a_2$ выполнены равенства $\gamma_1(a_1+z_1) - \gamma_1(a_1)=z_2,\gamma_2(a_2+z_2) - \gamma_2(a_2)=z_3$. Тогда $\gamma(a_1+z_1)-\gamma(a_1)=z_3$, где $\gamma=\gamma_2 \circ s \circ \gamma_1$, а $s$ – такой сдвиг, что $s(\gamma_1(a_1))=a_2$, следовательно, $z_1 \sim z_3$. Класс эквивалентности элемента $z$ (относительно группы $\Gamma'$) обозначается $K_z$. Число $z \in \mathbb Z$, $z \ne 0$, является регулярным (относительно группы $\Gamma'$), если $K_z$ конечно и $|\gamma (a+z)-\gamma(a)|<\infty $ для всех $a\in \mathbb Z^\omega$, $\gamma \in \Gamma'$. Несмотря на свою простоту, понятие эквивалентности чрезвычайно полезно в нашем рассмотрении. Укажем базовые примеры. Если $\Gamma'=\Gamma$, то эквивалентность тривиальна. Если группа $\Gamma'$ порождена семейством $\Gamma$ и перестановкой $x \mapsto-x$ на каждой копии $\mathbb Z$ в $\mathbb Z^\omega$, то каждое $z \in \mathbb Z$, $z\ne 0$, регулярно и $K_z=\{z, -z\}$. Чуть более сложным является типичный для нашего рассмотрения случай: пусть $\Gamma'$ порождена семейством $\Gamma$ и такой перестановкой $\gamma$, что $\gamma (x)=x$, для всех элементов $\mathbb Z^\omega$, кроме одной копии $\mathbb Z$, на которой для нечетных $x$ выполнено $\gamma (x)=-x$, а для четных $x$ выполнено $\gamma(x)=x$. Тогда каждое четное $z \ne 0$ регулярно и $K_z=\{z ,-z\}$, а каждое нечетное – не регулярно. И, наконец, у группы всех перестановок нет регулярных чисел. Лемма 4.2. (a) Если числа $z_1$ и $z_2$ регулярны, то число $z_1 \pm z_2$ тоже регулярно. (b) Наибольший общий делитель двух регулярных чисел регулярен. Доказательство. (a) Пусть числа $z_1$ и $z_2$ регулярны и пусть $\gamma \in \Gamma'$. Тогда выполнены соотношения: и Таким образом, множество $K_{z_1+z_2}$ конечно и не содержит $\infty$.
Случай $z_1-z_2$ полностью аналогичен. Пункт (b) следует из (a). Лемма доказана. Лемма 4.3. Пусть группа перестановок $\Gamma'$ содержит $\Gamma$, а число $d$ – $\operatorname{\textrm{НОД}}$ всех регулярных относительно $\Gamma'$ чисел. Тогда $K_d=\{d\}$ или $K_d=\{d, -d\}$. Кроме того, если $K_{d} =\{d\}$, то $K_z=\{z\}$ для любого числа $z$, кратного $d$. А если $K_{d}=\{d, -d\}$, то $K_z=\{z, -z\}$ для любого числа $z$, кратного $d$. Доказательство. Через $D$ обозначим число максимальной абсолютной величины, эквивалентное $d$ относительно $\Gamma'$. Тогда $D=N \cdot d$ или $D=-N \cdot d$ для некоторого натурального числа $N$.
Предположим, что $N>1$ и выберем такие $\gamma \in \Gamma'$, $a,b \in \mathbb Z^\omega$, что $ b-a=D$, $\gamma(b) - \gamma(a)=d$. Для каждого $0 \leqslant k < N$ положим
$$
\begin{equation*}
C_k=\{c_{k,i} \mid c_{k,i}=a+k \cdot d + i\cdot D,\, i \in \mathbb Z\}.
\end{equation*}
\notag
$$
Семейство $\{C_k\}$ является разбиением множества $\{a+z \cdot d \mid z \in \mathbb Z\}$. Поскольку $d$ регулярно, то для любого $c \in C_k$, $0 \leqslant k < N$, разность $\gamma (c) - \gamma (a)$ кратна $d$. Следовательно, семейство $\{\gamma(C_k)\}$ является разбиением множества $\{\gamma(a)+z \cdot d \mid z \in \mathbb Z\}$. Рассмотрим набор
$$
\begin{equation*}
E=\{\gamma(a), \gamma(a)+d, \dots, \gamma(a)+(N-1) \cdot d\}.
\end{equation*}
\notag
$$
Поскольку $\gamma(a),\gamma(b) \in \gamma(C_0) \cap E$ и в множестве $E$ содержится ровно $N$ элементов, то для некоторого $0 \leqslant k' < N$ выполнено $\gamma(C_{k'}) \cap E = \varnothing$. Поскольку абсолютное значение $D$ максимально в классе эквивалентности числа $d$, то все элементы множества $\gamma(C_{k'})$ должны лежать с одной стороны от сегмента $E$. Таким образом, или $\gamma(c) < \gamma(a)$ для всех $c \in C_{k'}$, или $\gamma(a)+(N-1) \cdot d < \gamma (c)$ для всех $c \in C_{k'}$. В противном случае нашлось бы такое $c_{k',i}$, что $|\gamma(c_{k',i+1}) - \gamma(c_{k',i})| > D$, но $c_{k',i+1} - c_{k',i} = D$, а абсолютное значение $D$ максимально в его классе эквивалентности. Предположим, что $\gamma(c) < \gamma(a)$ для всех $c \in C_{k'}$ (другой случай полностью аналогичен). Тогда найдется такое $0 \leqslant k'' < N$, что множество $\{c \in C_{k''} \mid \gamma(c) > \gamma(a)\}$ бесконечно. Тогда абсолютное значение разности $|\gamma (a+k' \cdot d +z \cdot D) - \gamma (a+k'' \cdot d +z \cdot D)|$ будет неограничено при $z \in \mathbb Z$, что противоречит регулярности $(k' - k'') \cdot d$.
Итак, $N=1$ и $K_d =\{d\}$ или $K_d =\{d, -d\}$. Если $K_d =\{d\}$, то $K_z=\{z\}$ для любого $z$, кратного $d$. Предположим, что $K_d=\{d,-d\}$ и $z=n\cdot d$, где $n$ – натуральное число (случай $z=-n\cdot d$ аналогичен). Тогда для всех $0 \leqslant i <n$ и любых $\gamma \in \Gamma'$, $a \in \mathbb Z^\omega$ выполнено или Более того, поскольку то все разности имеют один и тот же знак. Поэтому или для любого $a \in \mathbb Z^\omega$; т. е. $K_z \subset \{z, -z\}$. Поскольку имеются такие $\gamma \in \Gamma', a \in \mathbb Z^\omega$, что $\gamma(a+d) - \gamma(a)=-d$, то $\gamma(a+z) - \gamma(a) = -z$ и $-z\in K$, аналогично получаем, что $ z\in K$, т. е. $K_z=\{z, -z\}$. Лемма доказана.Пусть группа перестановок $\Gamma'$ содержит $\Gamma$ и число $d$ – $\operatorname{\textrm{НОД}}$ всех регулярных относительно группы $\Gamma'$ чисел. Тогда для любой перестановки $\gamma \in \Gamma'$ имеются три возможности: (1) $\gamma(a+n\cdot d)-\gamma(a)=n\cdot d$ для всех $a \in \mathbb Z^\omega$ и любого натурального числа $n$. Такую перестановку $\gamma$ назовем перестановкой первого типа; (2) $\gamma(a+n\cdot d)-\gamma(a)=-n\cdot d$ для всех $a \in \mathbb Z^\omega$ и любого натурального числа $n$. Такую перестановку $\gamma$ назовем перестановкой второго типа; (3) для любого $a \in \mathbb Z^\omega$ и любого $n$ $\gamma(a+n\cdot d)-\gamma(a)=n\cdot d$ или $\gamma(a+n\cdot d)-\gamma(a)=-n\cdot d$ и каждое из этих двух равенств реализуется для некоторых $a$, $n$. Такую перестановку $\gamma$ назовем перестановкой третьего типа. Если $K_d=\{d\}$, то все перестановки $\gamma \in \Gamma'$ – первого типа. Если $K_d=\{d,-d\}$, то перестановка $\gamma \in \Gamma'$ может быть как первого, так и второго или третьего типа. Всюду далее $\Gamma_R$ обозначает группу всех перестановок, сохраняющих определимое в структуре $\langle \mathbb Z^\omega, \{'\}\rangle$ отношение $R$. Для любого $d \in \mathbb Z$, $d > 0$: – группа $\Gamma_{A_{0,d}}$ – это группа всех таких перестановок $\gamma$, что $|\gamma(a + d)-\gamma(a)|=d$ для всех $a \in \mathbb Z^\omega$; нетрудно заметить, что регулярными числами этой группы являются числа вида $\{z\cdot d\mid z-\text{целое}\}$, таким образом, эта группа содержит перестановки всех трех типов; – группа $\Gamma_{A_{1,d}}$ – это (собственная) подгруппа группы $\Gamma_{A_{0,d}}$, состоящая из перестановок первого и второго типов; – группа $\Gamma_{A_{2,d}}$ – это (собственная) подгруппа группы $\Gamma_{A_{1,d}}$, состоящая из перестановок первого типа. Следствие 4.1. Для любых натуральных чисел $d$, $k$, и $0\leqslant i,j \leqslant 2$ выполнено: (i) $i\ne j \lor d\ne k \to [A_{i,d}] \ne [A_{j,k}]$; (ii) $[A_{i,d}] \succ [A_{i-1,d}]$; (iii) $[A_{i,d}] \succ [A_{i,d\cdot k}]$; (iv) $[A_{i,d}] \cup [A_{j,k}] = [A_{m,n}]$, где $m=\max\{i,j\}$, $n=\operatorname{\textrm{НОД}}(d,k)$; (v) $[A_{i, l}] \cap [A_{j,k}] = [A_{m,n}]$, где $m=\min\{i,j\}$, $n=\operatorname{\textrm{НОК}}(l,k)$. Доказательство. Пункты (i)–(iv) непосредственно вытекают из следствия 3.1 и сравнения соответствующих групп.
Дадим эскиз доказательства (v). Ввиду следствия 3.1 требуется показать, что группа $\Gamma_{A_{m,n}}$ порождается объединением групп $\Gamma_{A_{i,l}}$ и $\Gamma_{A_{j,k}}$. В одну сторону это очевидно, поскольку группы $\Gamma_{A_{i,l}}$ и $\Gamma_{A_{j,k}}$ являются подгруппами $\Gamma_{A_{m,n}}$. Пусть перестановка $\gamma \in \Gamma_{A_{m,n}}$, мы намерены показать, что $\gamma$ является композицией перестановок из групп $\Gamma_{A_{i,l}}$ и $\Gamma_{A_{j,k}}$. Для простоты ограничимся рассмотрением одной галактики. Выберем произвольный элемент $a$ в этой галактике и предположим, что $l=l_1 \cdot d; k=k_1 \cdot d; n=l_1\cdot k_1 \cdot d$, где $d=\operatorname{\textrm{НОД}}(l,k)$. Поскольку $\gamma(a+n)= \gamma(a) \pm n$, то в одной из двух групп (предположим, что в $\Gamma_{A_{i,l}}$) найдется такая перестановка $\gamma'$, что знак $\gamma(a+l)- \gamma(a)$ совпадает со знаком $\gamma'(a+n)- \gamma'(a)$. Положим $|l'| = l$, знак $l'$ совпадает со знаком $\gamma'(a+n)- \gamma'(a)$. Мы можем считать, что перестановка $\gamma'$ переставляет между собой пары элементов $\langle a+z\cdot l$, $\gamma(a)+z\cdot l'\rangle$ и тождественна на всех остальных элементах. Отметим, что на элементах вида $a+z \cdot n$ перестановки $\gamma, \gamma'$ совпадают. Выберем теперь такую перестановку $\gamma'' \in \Gamma_{A_{j,k}}$, которая переставляет между собой пары элементов $\langle a+z_1\cdot l +z_2\cdot k$, $\gamma(a)+z_1\cdot l' +z_2\cdot k \rangle$, где $0<z_1<k_1$, $z_1, z_2\in \mathbb Z$, – и тождественна на всех остальных элементах (и, в частности, на элементах вида $\gamma(a+z \cdot n$)). Нетрудно заметить, что перестановка $\gamma_0=\gamma'' \circ \gamma'$ совпадает с перестановкой $\gamma$ на всех элементах вида $a+z \cdot n$ и тождественна на всех остальных элементах. Подставляя вместо $a$ элементы вида $a+c$, $c<n$, мы построим набор из $n$ перестановок, композиция которых совпадает на данной галактике с $\gamma$. Следствие доказано. Если $m$ – натуральное число, то два вектора $\overline a, \overline b \in \mathbb Z^\omega$ одинаковой длины называются $m$-неразличимыми, если $a_i - a_j=b_i-b_j$ для всех таких $i$, $j$, что $|a_i-a_j|<m$ или $|b_i-b_j|<m$. Лемма 4.4. Для любой формулы $R$ в сигнатуре $\{'\}$ найдется такое натуральное число $w$, что для любых двух $w$-неразличимых наборов $\overline a, \overline b \in \mathbb Z^\omega$ выполнено $ R(\overline a)\equiv R(\overline b)$. Доказательство. Возьмем формулу $Q(w, \overline x, \overline y)$ в сигнатуре $\{+, < \}$, утверждающую, что векторы $\overline x$, $\overline y$ являются $w$-неразличимыми. Тогда утверждение леммы может быть записано в виде
Рассмотрим структуру $M_0$ – нестандартное элементарное расширение структуры $\langle \mathbb Z, \{+,<\}\rangle$ и возьмем произвольное нестандартное число $w_0>0$ в $M_0$. Для наборов $\overline a, \overline b \in M_0$ из $Q(w_0, \overline a, \overline b)$ следует, что для любого стандартного $k$ выполнено $a_i - a_j=k$ тогда и только тогда, когда $b_i - b_j=k$. Структуры $M_0$ и $\mathbb Z^\omega$ изоморфны (как структуры с единственным отношением $'$), поэтому с помощью Леммы 4.1 отображение $f(a_i)=b_i$ может быть продолжено до сдвига. Следовательно, выполнено в $M_0$. Тогда выполнено также и для некоторого стандартного числа $m$. Очевидно, что структура $M_0$ является обогащением максимальной структуры с единственным отношением $'$, поэтому соответствующее обеднение структуры $M_0$ изоморфно $Z^\omega$. Таким образом, утверждение леммы выполнено в $\mathbb Z^\omega$.Натуральное число $w$ называется границей определимого отношения $R$ тогда и только тогда, когда для любых $w$-неразличимых векторов $\overline a, \overline b \in \mathbb Z^\omega$ выполнено $ R(\overline a)\equiv R(\overline b)$. Следующая лемма утверждает, что если разности между некоторыми элементами вектора $\overline a$ нерегулярны (относительно группы $\Gamma_R$), то они могут быть заменены такими элементами, что соответствующие разности будут бесконечны, с сохранением значений отношения $R$. Лемма 4.5. Для любого $n$-арного отношения $R$, определимого в $\langle \mathbb Z^\omega, \{'\}\rangle$, и набора $\overline a=\langle a_0,\dots,a_{n-1}\rangle \in \mathbb Z^\omega$ можно построить такой набор что (i) $R(\overline a) \equiv R(\overline b)$; (ii) если разность $a_i-a_j \ne 0$ нерегулярна относительно $\Gamma_R$, то $b_i-b_j= \infty$; (iii) если разность $a_i-a_j$ регулярна, то $|a_i-a_j|=|b_i-b_j|$. Кроме того, если $\Gamma_R$ содержит перестановки только первого типа, то $a_i-a_j=b_i-b_j$; (iv) если $\Gamma_R$ не содержит перестановок третьего типа, то – или $a_i-a_j=b_i-b_j$ для всех $i$, $j$, для которых разность $a_i-a_j$ регулярна, – или $a_i-a_j=b_j-b_i$ для всех $i$, $j$, для которых разность $a_i-a_j$ регулярна. Доказательство осуществляется индукцией по количеству таких пар $i$, $j$, что $a_i-a_j$ – конечное ненулевое нерегулярное число. Допустим, что $a_0-a_1 \ne 0$ конечно и нерегулярно. Построим такой вектор $\overline b$ и такую перестановку $\gamma \in \Gamma_R$, что выполнено следующее:
(a) $R(\overline a) \equiv R(\overline b)$; (b) $b_0-b_1=\infty$; (c) для всех $i,j < n$, если $a_i-a_j=\infty$, то $b_i-b_j=\infty$; (d) для всех $i,j < n$, если $b_i-b_j=\infty$, то $a_i-a_j$ нерегулярно; (e) для всех $i,j < n$, если $b_i-b_j<\infty$, то $b_i-b_j=\gamma(a_i)-\gamma(a_j)$. Пусть $w$ – это граница отношения $R$, а $w'$ – это максимальное абсолютное значение элементов множества $\bigcup\{K_{a_i-a_j} \mid \text{разность }a_i-a_j \text{ регулярна}\}$. В предположении, что ненулевая конечная разность $a_0-a_1$ нерегулярна, выберем такую перестановку $\gamma' \in \Gamma_R$, что $|\gamma'(a_0)-\gamma'(a_1)| > n \cdot \max(w,w')$. Возьмем такой сдвиг $s$, что $s(a_0)=a_0$, $s(a_1)=a_1$, и если $a_i - a_j = \infty$, то $|\gamma'(s(a_i)) - \gamma'(s(a_j))| > n \cdot \max(w,w')$. Положим $\gamma=\gamma' \circ s$. Тогда $|\gamma(a_0)-\gamma(a_1)| > n \cdot \max(w,w')$ и $|\gamma(a_i) - \gamma(a_j)|>n \cdot \max(w,w')$, если $a_i-a_j=\infty$. Положим $\overline a'=\gamma(\overline a)$. Тогда – если $a_i - a_j < \infty$, то $a'_i - a'_j=\gamma(a_i) - \gamma(a_j)$. Теперь мы хотим преобразовать вектор $a'$ в такой вектор $b$, что – если $|a'_i - a'_j|<n \cdot \max(w,w')$, то $b_i-b_j=a'_i - a'_j$; – если $|a'_i - a'_j|>n \cdot \max(w,w')$, то $b_i-b_j=\infty$ (в частности, $b_1-b_0=\infty$). В процессе преобразования мы последовательно рассматриваем такие пары элементов вектора $a'$, что $|a'_i - a'_j|>n \cdot \max(w,w')$ и $|a'_i - a'_j| \ne \infty$. Таким образом, элементы $a'_i $ и $a'_j$ лежат в одной галактике $U$. Предположим, что $a'_i\,{<}\, a'_j$, и пусть $c_0<\dots<c_k$ – все элементы вектора $\overline a'$ из галактики $U$. Найдется такой элемент $c_m$, что $a'_0 \leqslant c_m<c_{m+1} \leqslant a'_1$ и $c_{m+1}- c_{m}>\max(w,w')$. Выберем вектор $\overline b$ так, что – $b_i=a'_i$, если $a'_i \notin U$ или $a'_i \leqslant c_m$; – все элементы $\{b_i \mid a '_i \geqslant c_{m+1},\, a'_i \in U\}$ лежат в некоторой отдельной галактике, не содержащей элементов вектора $\overline a'$. Согласно лемме 4.4 выполнено $R(\overline a')\equiv R(\overline b)$ и $R(\overline a) \equiv R(\overline a')$. Поскольку $c_{m+1}- c_{m}>w'$, разность $b_i-b_j$ регулярна тогда и только тогда, когда $a_i-a_j$ – регулярное число. Ясно, что условия (a)–(e) выполнены. Очевидно, что п. (i) следует из (a) и (iii)–(iv) следуют из (d) и (e). Из (b)–(e) находим, что количество конечных ненулевых нерегулярных разностей между элементами вектора $\overline b$ меньше, чем у вектора $\overline a$. Таким образом, можно считать, что нет пар $i,j$, при которых $a_i-a_j$ конечно и нерегулярно, в этом случае $\overline b$ является искомым вектором. Лемма доказана. Следующее утверждение говорит, что для любого определимого в $\langle \mathbb Z^\omega, \{'\}\rangle$ нетривиального отношения $R$ соответствующая группа перестановок $\Gamma_R$ совпадает с группой $\Gamma_{A_{i,j}}$ для некоторых $i,j$. Таким образом, в соответствии со следствием 3.1 имеет место $R\approx A_{i,j}$. Утверждение 4.1. Всякое несклеивающее отношение тривиально или для него существует $\operatorname{\textrm{НОД}}d$ всех регулярных относительно $\Gamma_R$ чисел. Тогда справедливо следующее: (i) если $\Gamma_R$ не содержит перестановок второго или третьего типа, то $R \approx A_{2,d}$; (ii) если $\Gamma_R$ не содержит перестановок третьего типа, но содержит перестановки второго типа, то $R \approx A_{1,d}$; (iii) если $\Gamma_R$ содержит перестановки третьего типа, то $R \approx A_{0,d}$. Доказательство. Во-первых, заметим, что если не существует регулярных чисел относительно группы $\Gamma_R$, то в соответствии с леммой 4.5 для любых двух наборов $\overline a$, $\overline{b}$ таких, что $a_i\ne a_j$, $b_i-b_j=\infty$ выполнено $R(\overline a)\equiv R(\overline b)$, т. е. несклеивающее отношение без регулярных чисел тривиально определимо через равенство.
Во-вторых, легко видеть, что если группа $\Gamma_R$ не содержит перестановок второго или третьего типа, то $R \succcurlyeq A_{2,d}$; если $\Gamma_R$ не содержит перестановок третьего типа, но содержит перестановки второго типа, то $R \succcurlyeq A_{1,d}$; если $\Gamma_R$ содержит перестановки третьего типа, то $R \succcurlyeq A_{0,d}$. Для доказательства в обратную сторону нужно показать, что любая перестановка, сохраняющая $A_{2,d}$ ($A_{1,d}$, $A_{0,d}$), принадлежит $\Gamma_R$ при выполнении соответствующих условий. Через $\Gamma'$ обозначим семейство таких перестановок $\gamma$, что $|\gamma(a+d)-\gamma(a)|=d$ для всех $a \in \mathbb Z^\omega$. Как было ранее замечено, $\Gamma'=\Gamma_{A_{0,d}}$. Подгруппа группы $\Gamma'$, состоящая из перестановок первого и второго типа, образует группу $\Gamma_{A_{1,d}}$; подгруппа группы $\Gamma'$, состоящая из перестановок первого типа, – это группа $\Gamma_{A_{2,d}}$. Доказательства всех утверждений (i)–(iii) следуют одной и той же схеме: мы предполагаем, что существуют набор $\overline a \in \mathbb Z^\omega$ и перестановка $\gamma \in \Gamma_{A_{i,d}}\,{\setminus}\,\Gamma_R$ такие, что $R(\overline{a})\not\equiv R(\gamma(\overline{a}))$. Далее применяется лемма 4.5 для построения таких векторов $\overline{b}$, $\overline{c}$, что $R(\overline{a})\equiv R(\overline{b})$; $R(\gamma(\overline{a}))\equiv R(\overline{c})$. С помощью леммы 4.4 находится граница $w$ отношения $R$. Далее, при необходимости, строятся такие $w$-неразличимые наборы $\overline{v_1}$, $\overline{v_2}$, что $R(\overline{b})\equiv R(\overline{v_1})$; $R(\overline{c})\equiv R(\overline{v_2})$, а это противоречит лемме 4.4. Для доказательства (i) предположим, что в множестве $\Gamma' \setminus \Gamma_R$ имеется перестановка $\gamma$ первого типа. Тогда найдется такой вектор $\overline a=\langle a_0,\dots,a_{n-1}\rangle \in \mathbb Z^\omega$, что $R(\overline a) \not \equiv R(\gamma(\overline a))$. По определению группы $\Gamma'$, если $a_i-a_j$ нерегулярно относительно $\Gamma_R$, то разность $\gamma(a_i)-\gamma(a_j)$ также нерегулярна. По определению перестановок первого типа, если $a_i-a_j$ регулярно относительно группы $\Gamma_R$, то $\gamma(a_i)-\gamma(a_j)= a_i-a_j$. Используя лемму 4.5, выберем векторы $\overline b$ и $\overline c$, соответствующие наборам $\overline a$ и $\gamma(\overline a)$. Поскольку $\Gamma_R$ содержит лишь перестановки первого типа, регулярные разности в векторах $\overline b$, $\overline c$ совпадают, т. е. векторы $\overline b$, $\overline c$ являются $w$-неразличимыми для любого конечного числа $w$. Поэтому $R(\overline b) \equiv R(\overline c)$. Пришли к противоречию. Доказывая (ii), предположим, что в множестве $\Gamma' \setminus \Gamma_R$ найдется перестановка $\gamma$ первого или второго типа. Выберем векторы $\overline a$, $\overline b$ и $\overline c$ так же, как в доказательстве п. (i). Если $b_i-b_j=c_i-c_j$ для какой-то регулярной разности $b_i-b_j$, то это равенство выполнено для всех регулярных разностей, поэтому данный случай совпадает с п. (i). Если $b_i-b_j=c_j-c_i$ для какой-то регулярной разности $b_i-b_j$ то это равенство выполнено для всех регулярных разностей вектора $\overline b$. В группе $\Gamma_R$ имеется перестановка $\gamma'$ второго типа, т. е. $\gamma' (t+z\,{\cdot}\, d) - \gamma'(t)=-z \,{\cdot}\, d$ для всех $z \in \mathbb Z$, $t \in \mathbb Z^\omega$. Фиксируем некоторое $t \in \mathbb Z^\omega$ и рассмотрим множество $S=\{t+d \cdot z \mid z \in \mathbb Z\}$. Пусть $w$ – граница отношения $R$. Найдется такой вектор $\overline s$ в $S$, что – если $|c_i - c_j| < \infty$, то $s_i-s_j=c_i-c_j$; – если $|c_i - c_j| = \infty$, то $|s_i - s_j| > w$. По лемме 4.4 выполнено $R(\overline c) \equiv R(\overline s)$. Поскольку $s_i-s_j=\gamma'(s_j)-\gamma'(s_i)$ для всех $i,j < n$, то векторы $\overline b$ и $\gamma'(\overline s)$ являются $w$-неразличимыми. Противоречие. Для доказательства (iii) предположим, что в множестве $\Gamma' \setminus \Gamma_R$ найдется какая-то перестановка $\gamma$. Векторы $\overline a$, $\overline b$, и $\overline c$ выберем также, как в п. (i). Если перестановка $\gamma$ – первого типа, то доказательство совпадает с п. (i). Если это перестановка второго или третьего типа, то возьмем перестановку $\gamma'$ третьего типа из группы $\Gamma_R$ и такие $t_1,t_2 \in \mathbb Z^\omega$, что для любого $z \in \mathbb Z$ выполнено
$$
\begin{equation*}
\gamma' (t_1+z \cdot d) - \gamma'(t_1)=z \cdot d,\qquad \gamma' (t_2+z \cdot d) - \gamma'(t_2)=-z \cdot d.
\end{equation*}
\notag
$$
Положим $S_1=\{t_1+z \cdot d \mid z \in \mathbb Z\}$ и $S_2=\{t_2+z \cdot d \mid z \in \mathbb Z\}$. Если перестановка $\gamma$ – второго типа, то доказательство совпадает с доказательством п. (ii), если в качестве множества $S$ взять множество $S_2$. Если, наконец, это перестановка третьего типа, то выполнено следующее: если разность $b_i-b_j$ регулярна, то $b_i-b_j=c_i-c_j$ или $b_i-b_j=c_j-c_i$. Если $b_i-b_j=c_i-c_j$ и $b_k - b_l=c_l-c_k$, то разность $b_k-b_i$ нерегулярна, поэтому $c_i$ и $c_k$ лежат в разных галактиках. Пусть $w$ – граница отношения $R$. Выберем такой набор $\{s_0,\dots,s_{n-1}\} \subset S_1 \cup S_2$, что – если $|c_i - c_j| < \infty$, то $s_i-s_j=c_i - c_j$; – если $|c_i - c_j|=\infty$, то $|s_i - s_j| >w$ и $|\gamma'(s_i) - \gamma'(s_j)| >w$; – если разность $b_i - b_j$ регулярна и $b_i - b_j=c_i-c_j$, то $s_i, s_j \in S_1$; – если разность $b_i - b_j$ регулярна и $b_i - b_j=c_j-c_i$, то $s_i, s_j \in S_2$. Ввиду леммы 4.4 имеет место $R(\overline s) \equiv R(\overline c)$. Поскольку для любой регулярной разности $b_i-b_j$ выполнено $\gamma'(s_i)-\gamma'(s_j)=b_i-b_j$, то векторы $\overline b$ и $\gamma' (\overline s)$ являются $w$-неразличимыми. Пришли к противоречию. Утверждение доказано. Утверждение 4.1 вместе со следствием 4.1 составляют теорему 4.1. § 5. Открытые проблемы и гипотезыКонкретные структуры. 1. Получить явное описание решетки для порядка на неотрицательных рациональных числах на основе общего описания из [12] или независимо от него. Ясно, что в такую решетку входят пространства с базами: – отношение, выделяющее нуль; – порядок на всем носителе; – обычные порождающие для порядка рациональных, суженные на положительные рациональные и ложные, если один из аргументов – нуль. Что еще? 2. Порядок на целых числах. Получается ли решетка определимости для него естественной комбинацией отношений из данной работы и аналогов для целых чисел отношений из решетки для порядка рациональных? Поиски структур, элементарно эквивалентных максимальным. Что можно сказать о существовании максимальных структур, элементарно эквивалентных следующим. 3. Порядок на целых числах. 4. Следование на натуральных числах. 5. Бесконечный неориентированный связный граф без циклов, все вершины которого имеют степень $3$. БлагодарностиАвторы признательны Альберту Абрамовичу Мучнику, который привлек их внимание к данной проблематике, Андрею Мучнику за творческое обсуждение, Сергею Ивановичу Адяну, который всегда поддерживал нашу работу и на семинаре которого докладывались ее результаты, Владимиру Андреевичу Успенскому за поддержку нашей уверенности в важности и естественности данной проблематики. Мы потеряли коллег и друзей в годы нашей работы, и тем важнее для нас упомянуть их здесь. Авторы благодарны рецензенту за весьма тщательное и чрезвычайно ценное рецензирование. Мы благодарны также Б. Д. Бармак и Д. С. Посицельскому за нахождение опечаток.
Цитирование в формате AMSBIB
\RBibitem{SemSop21} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|