Известия Российской академии наук. Серия математическая
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Изв. РАН. Сер. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Известия Российской академии наук. Серия математическая, 2022, том 86, выпуск 6, страницы 207–222
DOI: https://doi.org/10.4213/im9340
(Mi im9340)
 

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Об отношении взаимной простоты с точки зрения монадической логики второго порядка

С. О. Сперанскийa, Ф. Н. Пахомовab

a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва
b Гентский университет, Гент, Бельгия
Список литературы:
Аннотация: Обозначим через $\mathfrak{C}$ структуру натуральных чисел с отношением взаимной простоты. Мы доказываем, что для каждого ненулевого натурального числа $n$, если $\Pi^1_n$-множество натуральных чисел замкнуто относительно автоморфизмов $\mathfrak{C}$, то оно определимо в $\mathfrak{C}$ посредством монадической $\Pi^1_n$-формулы сигнатуры $\mathfrak{C}$ с ровно $n$ кванторами по множествам. С другой стороны, мы замечаем, что некоторые обогащения $\mathfrak{C}$ не обладают даже намного более слабой версией этого свойства.
Библиография: 10 наименований.
Ключевые слова: взаимная простота, монадическая логика второго порядка, определимость, слабые арифметики.
Финансовая поддержка Номер гранта
Российский научный фонд 20-41-05002
Результаты в разделах 2 и 3 были получены С. О. Сперанским; результаты в разделе 4 были получены Ф. Н. Пахомовым. Исследование С. О. Сперанского выполнено за счет гранта Российского научного фонда № 20-41-05002 в Математическом институте им. В. А. Стеклова Российской академии наук.
Поступило в редакцию: 23.03.2022
Исправленный вариант: 30.05.2022
Англоязычная версия:
Izvestiya: Mathematics, 2022, Volume 86, Issue 6, Pages 1225–1239
DOI: https://doi.org/10.4213/im9340e
Реферативные базы данных:
Тип публикации: Статья
УДК: 510.6+510.8
MSC: 03F35, 03D55, 03D35

§ 1. Введение

Нас будут интересовать относительно слабые арифметические структуры, поэтому наша работа может рассматриваться как исследование по “слабым арифметикам” (пользуясь терминологией из [1]). Многие интересные вопросы в этой области касаются двух типов определимости:

(i) первопорядковая определимость;

(ii) монадическая второпорядковая определимость1.

В частности, имеются красивые результаты о (i), связанные с делимостью и взаимной простотой, например результаты в [4], вдохновленные фундаментальной работой Робинсон [5] (см. также [6]). Что до (ii), то делимость была изучена в [7]. Настоящая статья будет иметь дело с взаимной простотой.

В дальнейшем под формулой мы будем понимать монадическую второпорядковую формулу, если не указано иное. Отметим, что символ $=$ будет трактоваться как нелогический (который может принадлежать или не принадлежать данной сигнатуре). Для удобства ноль не будет считаться элементом $\mathbb{N}$, т. е.

$$ \begin{equation*} \mathbb{N}=\{ 1, 2, \dots\}. \end{equation*} \notag $$
Подмножество $\mathbb{N}$ называется $\Pi^1_n$-множеством, если оно определимо в стандартной модели арифметики Пеано посредством $\Pi^1_n$-формулы. Пусть $\sigma$ – сигнатура и $\mathfrak{A}$ – $\sigma$-структура с носителем $\mathbb{N}$. Рассмотрим теперь следующее условие: С точки зрения монадической логики второго порядка, если $\mathfrak{A}$ удовлетворяет $(*)$, то мы хорошо понимаем, что может быть определено в $\mathfrak{A}$.

В [3] было доказано, что $(*)$ выполнено для стандартной модели арифметики Пресбургера. Далее, в [7] было показано, что $(*)$ выполнено для структуры натуральных чисел с отношением делимости, так же как и для всех ее обогащений (включая стандартную модель арифметики Сколема). Но что происходит, если мы заменяем делимость на взаимную простоту? Возьмем

$$ \begin{equation*} \sigma_{\circ}:= \{ \bot^2\}. \end{equation*} \notag $$
Здесь $\bot$ – двухместный предикатный символ, чья подразумеваемая интерпретация – отношение взаимной простоты. Обозначим соответствующую $\sigma_{\circ}$-структуру через $\mathfrak{C}$. Значит, для всех $m, n \in \mathbb{N}$
$$ \begin{equation*} \mathfrak{C} \models {m \bot n} \quad \Longleftrightarrow \quad m \text{ и }n\text{ не имеют общих простых делителей}. \end{equation*} \notag $$
В этой статье мы установим, что:

(a) $\mathfrak{C}$ удовлетворяет $(*)$;

(b) существует обогащение $\mathfrak{C}'$ для $\mathfrak{C}$ такое, что некоторые вычислимые подмножества $\mathbb{N}$, которые замкнуты относительно автоморфизмов $\mathfrak{C}'$, не могут быть определены в $\mathfrak{C}'$ посредством монадических второпорядковых формул2.

Очевидно, из (b) следует, что некоторые обогащения $\mathfrak{C}$ не обладают $(*)$. Поэтому случай взаимной простоты довольно сильно отличается от случая делимости.

Замечание. Для простоты $(*)$ сформулировано для подмножеств $\mathbb{N}$, но его можно также сформулировать для подмножеств $\mathbb{N}^2$, $\mathbb{N}^3$ и так далее. Доказательства в нашей статье могут быть легко модифицированы для работы с такими подмножествами, и то же самое применимо к [7]; поскольку доказательства в [3] были намного проще, они были изначально представлены в таком виде. Поэтому, в частности, $\mathfrak{C}$ будет удовлетворять аналогам $(*)$ для подмножеств $\mathbb{N}^2$, $\mathbb{N}^3$ и так далее.

§ 2. Предварительные сведения

Пусть $\sigma$ – сигнатура. Напомним, что $\sigma$-формула лежит в $\Pi^1_n$, если она имеет вид

$$ \begin{equation*} \underbrace{{\forall\, \vec{X}_1}\ {\exists\, \vec{X}_2}\dots \vec{X}_n}_{n-1 \text{ перемена кванторов}} \Psi, \end{equation*} \notag $$
где $\vec{X}_1,\vec{X}_2,\dots,\vec{X}_n$ суть кортежи переменных по множествам и $\Psi$ не содержит кванторов по множествам. Далее, $\Pi^1_n$-$\sigma$-формула будет называться специальной, если каждый из $\vec{X}_1,\vec{X}_2,\dots,\vec{X}_n$ имеет единичную длину. Возьмем
$$ \begin{equation*} \sigma_{\bullet}:= \{ +^3, =^2\}. \end{equation*} \notag $$
Здесь $+$ есть трехместный предикатный символ (не двухместный функциональный символ), чья подразумеваемая интерпретация – график функции сложения. Обозначим соответствующую $\sigma_{\bullet}$-структуру через $\mathfrak{P}$; таким образом, $\mathfrak{P}$ можно рассматривать как стандартную модель арифметики Пресбургера. Чтобы показать, что $(*)$ выполнено для $\mathfrak{C}$, мы будем использовать следующую теорему.

Теорема 2.1 (см. [7]). Пусть $n \in \mathbb{N}$ и $S \subseteq \mathbb{N}$. Допустим, что $S$ является $\Pi^1_n$-множеством. Тогда $S$ определимо в $\mathfrak{P}$ посредством специальной $\Pi^1_n$-формулы. Другими словами, $\mathfrak{P}$ удовлетворяет $(*)$.

Обозначим через $\mathbb{P}$ множество всех простых чисел. Можно легко убедиться, что $\mathbb{P}$ не замкнуто относительно автоморфизмов $\mathfrak{C}$, а потому не определимо в $\mathfrak{C}$. Возьмем

$$ \begin{equation*} \begin{aligned} \, \mathbb{P}^{\operatorname{sh}arp} &:=\text{множество всех степеней простых чисел} \\ &\, =\{ p^n \mid p \in \mathbb{P}\text{ и }n \in \mathbb{N}\}. \end{aligned} \end{equation*} \notag $$
Разумеется, $\{1\}$ и $\mathbb{P}^{\operatorname{sh}arp}$ определимы в $\mathfrak{C}$ посредством первопорядковых формул
$$ \begin{equation*} \operatorname{One}(x) := \forall\, u\ u \bot x\quad \text{и}\quad \operatorname{PPow}(x) := \neg\, \operatorname{One}(x) \wedge \forall\, u\ \forall\, v\ (\neg\, u \bot x \wedge \neg\, v \bot x \to \neg\, u \bot v) \end{equation*} \notag $$
соответственно. Эти формулы будут применяться в наших доказательствах. Далее, для каждого $n \in \mathbb{N}$ обозначим через $[\![n]\!]$ множество всех простых делителей $n$, т. е.
$$ \begin{equation*} [\![n]\!]:= \{ p \in \mathbb{P} \mid p \text{ делит }n\}. \end{equation*} \notag $$
Очевидно, для всех $m, n \in \mathbb{N}$
$$ \begin{equation*} \mathfrak{C} \models m \bot n \quad \Longleftrightarrow \quad [\![m]\!] \cap [\![n]\!]= \varnothing. \end{equation*} \notag $$
Интуитивно, если $[\![m]\!]$ и $[\![n]\!]$ совпадают, то $m$ и $n$ неразличимы в $\mathfrak{C}$ посредством формул второго и даже более высоких порядков. Чтобы сделать это утверждение более точным, рассмотрим
$$ \begin{equation*} \mathcal{N}:= \{ [\![n]\!] \mid n \in \mathbb{N}\}. \end{equation*} \notag $$
Пусть $\mathscr{C}$ – $\sigma_{\circ}$-структура с носителем $\mathcal{N}$, в которой символ $\bot$ интерпретируется как
$$ \begin{equation*} \{(M, N) \in \mathcal{N}^2 \mid M \cap N=\varnothing\}. \end{equation*} \notag $$
Тогда мы имеем следующее.

Утверждение 2.2. Для любых $\sigma_{\circ}$-формулы $\Phi(x)$ и $n \in \mathbb{N}$

$$ \begin{equation*} \mathfrak{C} \models \Phi(n) \quad \Longleftrightarrow \quad \mathscr{C} \models \Phi([\![n]\!]). \end{equation*} \notag $$

Доказательство. Обозначим через $\approx$ отношение “$m$ и $n$ имеют одни и те же простые делители”, т. е.
$$ \begin{equation*} \approx\ := \{ (m,n) \in \mathbb{N}^2 \mid [\![m]\!]=[\![n]\!]\}. \end{equation*} \notag $$
Очевидно, $\approx$ является отношением конгруэнции на $\mathfrak{C}$. Рассмотрим факторструктуру $\mathfrak{C} /{\approx}$ для $\mathfrak{C}$ по $\approx$. Определим функцию $\eta$ из $\mathbb{N} /{\approx}$ в $\mathcal{N}$ посредством равенства
$$ \begin{equation*} \eta([n]_{\approx}):= [\![n]\!], \end{equation*} \notag $$
где $[n]_{\approx}$ обозначает класс эквивалентности $n$ по $\approx$. Тогда $\eta$ является изоморфизмом из $\mathfrak{C}/{\approx}$ на $\mathscr{C}$. Таким образом, для любых $\sigma$-формулы $\Phi(x)$ и $n\in\mathbb{N}$
$$ \begin{equation*} \mathfrak{C} \models \Phi(n) \quad \Longleftrightarrow \quad \mathfrak{C}/{\approx} \ \models \Phi([n]_{\approx}) \quad \Longleftrightarrow \quad \mathscr{C} \models \Phi([\![n]\!]), \end{equation*} \notag $$
что и требовалось. Утверждение доказано.

Для любого множества $S$ мы будем обозначать через $\operatorname{card}(S)$ мощность $S$. Определим функцию $\iota$ из $\mathbb{N}$ в $\mathbb{N}$ посредством равенства

$$ \begin{equation*} \iota(n):= \operatorname{card}([\![n]\!]) +1. \end{equation*} \notag $$
В частности, $\iota(n)=1$ тогда и только тогда, когда $n=1$. Теперь рассмотрим отношения
$$ \begin{equation*} \begin{aligned} \, \sim &:= \{(m,n) \in \mathbb{N}^2 \mid \iota(m)=\iota(n)\} \quad \text{и} \\ \oplus &:=\{ (m,n,k) \in \mathbb{N}^3 \mid \iota(m)+\iota(n)=\iota(k)\}. \end{aligned} \end{equation*} \notag $$
Пусть $\mathfrak{P}^{\iota}$ – $\sigma_{\bullet}$-структура с носителем $\mathbb{N}$, в которой символы $+$ и $=$ интерпретируются как $\oplus$ и $\sim$ соответственно. Имеется тесная взаимосвязь между $\mathfrak{P}$ и $\mathfrak{P}^{\iota}$.

Утверждение 2.3. Для любых $\sigma$-формулы $\Phi(x)$ и $n \in \mathbb{N}$

$$ \begin{equation*} \mathfrak{P}^{\iota} \models \Phi(n) \quad \Longleftrightarrow \quad \mathfrak{P} \models \Phi(\iota(n)). \end{equation*} \notag $$

Доказательство. Ясно, что $\sim$ является отношением конгруэнции на $\mathfrak{P}^{\iota}$. Рассмотрим факторструктуру $\mathfrak{P}^{\iota}/{\sim}$ для $\mathfrak{P}^{\iota}$ по $\sim$. Определим функцию $\xi$ из $\mathbb{N}/{\sim}$ в $\mathbb{N}$ посредством равенства
$$ \begin{equation*} \xi([n]_{\sim}):= \iota(n), \end{equation*} \notag $$
где $[n]_{\sim}$ обозначает класс эквивалентности $n$ по $\sim$. Тогда $\xi$ является изоморфизмом из $\mathfrak{P}^{\iota}/{\sim}$ на $\mathfrak{P}$. Таким образом, мы получили нужный результат. Утверждение доказано.

Позже будет показано, что $\sim$ и $\oplus$ являются “$\Delta^1_1$-определимыми” в $\mathfrak{C}$. Точнее, мы докажем, что эти отношения и их дополнения определимы в $\mathfrak{C}$ посредством $\Pi^1_1$-формул3.

§ 3. Определимость в $\mathfrak{C}$

Цель этого параграфа – доказать, что $\mathfrak{C}$ удовлетворяет $(*)$.

Теорема 3.1. Пусть $n \in \mathbb{N}$ и $S \subseteq \mathbb{N}$. Допустим, что $S$ является $\Pi^1_n$-множеством, замкнутым относительно автоморфизмов $\mathfrak{C}$. Тогда $S$ определимо в $\mathfrak{C}$ посредством специальной $\Pi^1_n$-формулы.

В нашем рассуждении будут использоваться несколько лемм. Начнем с простого факта о $\iota$.

Лемма 3.2. Для любых $n \in \mathbb{N}$ и $S \subseteq \mathbb{N}$ верно следующее:

(i) если $S$ является $\Pi^1_n$-множеством, то $\iota [S]$ и $\iota^{-1} [S]$ также являются $\Pi^1_n$-множествами;

(ii) $S$ замкнуто относительно автоморфизмов $\mathfrak{C}$ тогда и только тогда, когда $S=\iota^{-1} [\iota[S]]$.

Доказательство. (i) Известно, что класс всех $\Pi^1_n$-подмножеств $\mathbb{N}$ замкнут относительно вычислимых образов и прообразов (см. [8; теорема 16-III]). Заметим, что $\iota$ вычислима.

(ii) Справа налево: допустим, что $S=\iota^{-1} [\iota[S]]$. Заметим, что для каждого $m \in \mathbb{N}$ предикат “$x$ имеет ровно $m$ простых делителей” перворядково определим в $\mathfrak{C}$, например посредством формулы

$$ \begin{equation*} \begin{aligned} \, &\exists\, u_1, u_2, \dots, u_m\ \biggl( \biggl( \bigwedge_{i=1}^{m-1} \bigwedge_{j=i+1}^{m} u_i \bot u_j \biggr) \wedge \biggl( \bigwedge_{i=1}^{m} \neg\, x \bot u_i \biggr) \biggr) \\ &\qquad \wedge \neg\, \exists u_1, u_2, \dots, u_{m+1}\ \biggl( \biggl( \bigwedge_{i=1}^{m} \bigwedge_{j=i+1}^{m+1} u_i \bot u_j \biggr) \wedge \biggl( \bigwedge_{i=1}^{m+1} \neg\, x \bot u_i \biggr) \biggr). \end{aligned} \end{equation*} \notag $$
Значит, если $k \in S$ и $\xi$ – автоморфизм $\mathfrak{C}$, то $\iota(\xi(k))=\iota(k)$, что дает $\xi(k) \in \iota^{-1}[\iota[S]]$, т. е. $\xi(k)\in S$. Таким образом, $S$ замкнуто относительно автоморфизмов $\mathfrak{C}$.

Слева направо: допустим, что $S$ замкнуто относительно автоморфизмов $\mathfrak{C}$. Очевидно, $S$ является подмножеством $\iota^{-1} [\iota[S]]$. С другой стороны, пусть $m \in \iota^{-1} [\iota[S]]$, т. е. $\iota (m)=\iota(k)$ для некоторого $k \in S$. Тогда мы можем найти автоморфизм $\xi$ для $\mathfrak{C}$ такой, что $\xi(k)=m$. Стало быть, $m \in S$. Поэтому $S$ совпадает с $\iota^{-1} [\iota[S]]$. Лемма доказана.

Для дальнейшего введем два расширения $\sigma_{\circ}$:

$$ \begin{equation*} \sigma_{\circ}[U]:= \sigma_{\circ} \cup \{U^1\} \quad \text{и} \quad \sigma_{\circ}[U, V]:= \sigma_{\circ}[U] \cup \{V^1\}. \end{equation*} \notag $$
Здесь $U$ и $V$ суть различные одноместные предикатные символы, которые могут также трактоваться как переменные по множествам при надобности. В доказательствах ниже ключевую роль будут играть первопорядковые $\sigma_{\circ}$-формулы
$$ \begin{equation*} \begin{aligned} \, \operatorname{Cup} (x,y,z) &:= \forall\, u\ ((u \bot x \wedge u \bot y) \leftrightarrow u \bot z) \quad \text{и} \\ \operatorname{DCup}(x,y,z) &:= \operatorname{Cup}(x,y,z) \wedge x \bot y. \end{aligned} \end{equation*} \notag $$
Ясно, что для любых $n, m, k \in \mathbb{N}$
$$ \begin{equation*} \begin{aligned} \, \mathfrak{C} \models \operatorname{Cup}(n,m,k) \quad &\Longleftrightarrow \quad [\![n]\!] \cup [\![m]\!]=[\![k]\!], \\ \mathfrak{C} \models \operatorname{DCup}(n,m,k) \quad &\Longleftrightarrow \quad [\![n]\!] \cup [\![m]\!]=[\![k]\!] \text{ и } [\![n]\!] \cap [\![m]\!]=\varnothing. \end{aligned} \end{equation*} \notag $$
Для данного $S \subseteq \mathbb{N}$ обозначим $\bigcup_{n \in S} [\![n]\!]$ через $[\![S]\!]$.

Лемма 3.3. Допустим, что $A \subseteq \mathbb{N}$ таково, что $[\![A]\!]$ и $\mathbb{P} \setminus [\![A]\!]$ оба бесконечны. Возьмем

$$ \begin{equation*} B:= \{n \in \mathbb{N} \mid \operatorname{card}([\![n]\!] \cap [\![A]\!])= \operatorname{card}([\![n]\!] \setminus [\![A]\!])\}. \end{equation*} \notag $$
Тогда существуют первопорядковые $\sigma_{\circ} [U,V]$-формулы $\operatorname{Eq}(x,y)$ и $\operatorname{Add}(x,y,z)$, которые определяют $\sim$ и $\oplus$ соответственно в $\sigma_{\circ} [U,V]$-обогащении $\langle \mathfrak{C}, A, B \rangle$.

Доказательство. Разумеется, для всех $m, n, k \in \mathbb{N}$
$$ \begin{equation*} \begin{aligned} \, m \sim n \quad &\Longleftrightarrow \quad \operatorname{card}([\![m]\!])=\operatorname{card}([\![n]\!]), \\ (m,n,k) \in \oplus \quad &\Longleftrightarrow \quad 1+\operatorname{card}([\![m]\!])+\operatorname{card}([\![n]\!])=\operatorname{card} ([\![k]\!]). \end{aligned} \end{equation*} \notag $$
Кроме того, если $\operatorname{Eq}(x,y)$ – первопорядковая $\sigma_{\circ}[U,V]$-формула, которая определяет $\sim$ в $\langle \mathfrak{C}, A, B \rangle$, то можно использовать первопорядковую $\sigma_{\circ} [U,V]$-формулу
$$ \begin{equation*} \begin{aligned} \, \operatorname{Add}(x,y,z) := \exists\, \widetilde{x}, \widetilde{y}, u, v \ &\bigl( \operatorname{Eq}(x,\widetilde{x}) \wedge \operatorname{Eq}(y, \widetilde{y}) \wedge \operatorname{DCup}(\widetilde{x}, \widetilde{y}, u) \\ &\qquad\wedge \operatorname{PPow}(v) \wedge \operatorname{DCup}(u,v,z)\bigr) \end{aligned} \end{equation*} \notag $$
для определения $\oplus$ в $\langle \mathfrak{C}, A, B \rangle$. Поэтому мы сосредоточимся на $\sim$.

Начнем с доказательства того, что

$$ \begin{equation*} R:= \{(m,n) \in \mathbb{N}^2 \mid [\![m]\!] \subseteq [\![A]\!], \, [\![n]\!] \subseteq \mathbb{P} \setminus [\![A]\!] \text{ и } \operatorname{card}([\![m]\!])=\operatorname{card}([\![n]\!])\} \end{equation*} \notag $$
первопорядково определима в $\langle \mathfrak{C}, A, B \rangle$. С этой целью рассмотрим первопорядковые $\sigma_{\circ}[U]$-формулы
$$ \begin{equation*} \begin{aligned} \, \Theta_1(x) &:= \forall\, u\ \bigl( \operatorname{PPow}(u) \wedge \neg\, u \bot x \to \exists\, y\ (U(y) \wedge \neg\, u \bot y)\bigr) \quad \text{и} \\ \Theta_2(x) &:= \forall\, u\ \bigl( \operatorname{PPow}(u) \wedge \neg\, u \bot x \to \forall\, y\ (U(y) \to u \bot y) \bigr). \end{aligned} \end{equation*} \notag $$
Очевидно, для любого $n \in \mathbb{N}$ верно
$$ \begin{equation*} \begin{aligned} \, \langle \mathfrak{C}, A \rangle \models \Theta_1(n) \quad &\Longleftrightarrow \quad [\![n]\!] \subseteq [\![A]\!], \\ \langle \mathfrak{C}, A \rangle \models \Theta_2(n) \quad &\Longleftrightarrow \quad [\![n]\!] \subseteq \mathbb{P} \setminus [\![A]\!]. \end{aligned} \end{equation*} \notag $$
Стало быть, первопорядковая $\sigma_{\circ}[U,V]$-формула
$$ \begin{equation*} \Phi_R(x,y) := \Theta_1(x) \wedge \Theta_2(y) \wedge \exists\, z\ \bigl( \operatorname{Cup}(x,y,z) \wedge V(z) \bigr) \end{equation*} \notag $$
определяет $R$ в $\langle \mathfrak{C}, A, B \rangle$. Далее, мы желаем показать, что
$$ \begin{equation*} Q:= \{(m,n) \in \mathbb{N}^2 \mid [\![m]\!] \subseteq [\![A]\!] \text{ и } \operatorname{card}([\![m]\!])= \operatorname{card}([\![n]\!])\} \end{equation*} \notag $$
тоже первопорядково определимо в $\langle \mathfrak{C}, A, B \rangle$. Неформально это можно сделать следующим образом:

(a) найдем $k \in \mathbb{N}$ такое, что $[\![k]\!] \subseteq \mathbb{P} \setminus [\![A]\!]$, $[\![k]\!] \cap [\![n]\!]=\varnothing$ и $\operatorname{card} ([\![k]\!])=\operatorname{card}([\![n]\!] \cap [\![A]\!])$;

(b) проверим, верно ли $\operatorname{card}([\![m]\!])=\operatorname{card}([\![k]\!] \cup ([\![n]\!] \setminus [\![A]\!]))$.

Формально мы используем первопорядковую $\sigma_{\circ} [U,V]$-формулу

$$ \begin{equation*} \begin{aligned} \, \Phi_Q(x,y) &:= \Theta_1(x) \wedge \exists\, u, v, \widetilde{u}, \widetilde{y}\ \bigl( \Theta_1(u) \wedge \Theta_2(v) \wedge \operatorname{Cup}(u,v,y) \\ &\qquad \wedge \Theta_2(\widetilde{u}) \wedge \Phi_R(u, \widetilde{u}) \wedge \operatorname{DCup}(\widetilde{u}, v, \widetilde{y}) \wedge \Phi_R(x, \widetilde{y}) \bigr) \end{aligned} \end{equation*} \notag $$
для определения $Q$ в $\langle \mathfrak{C}, A, B \rangle$. Наконец, рассмотрим первопорядковую $\sigma_{\circ} [U,V]$-формулу
$$ \begin{equation*} \operatorname{Eq}(x,y) := \exists\, u\ \bigl( \Phi_Q(u,x) \wedge \Phi_Q(u,y)\bigr). \end{equation*} \notag $$
Легко убедиться, что она определяет $\sim$ в $\langle \mathfrak{C}, A, B \rangle$. Лемма доказана.

Более того, мы имеем следующее.

Лемма 3.4. Существует первопорядковое $\sigma_{\circ} [U,V]$-предложение $\operatorname{PrA}$ такое, что для любого $\sigma_{\circ} [U,V]$-обогащения $\mathfrak{A}$ для $\mathfrak{C}$

$$ \begin{equation*} \begin{aligned} \, \mathfrak{A} \models \operatorname{PrA} \quad \Longleftrightarrow \quad &\operatorname{Eq}(x,y) \textit{ и } \operatorname{Add}(x,y,z) \textit{ определяют } \sim \textit{ и }\oplus \\ &\qquad \textit{ соответственно в }\mathfrak{A}. \end{aligned} \end{equation*} \notag $$

Доказательство. Ясно, что если $\operatorname{Eq}(x,y)$ определяет $\sim$ в $\mathfrak{A}$, то $\operatorname{Add}(x,y,z)$ определяет $\oplus$ в $\mathfrak{A}$. Поэтому мы сосредоточимся на $\operatorname{Eq}(x,y)$. Пусть $\operatorname{PrA}$ – конъюнкция следующих первопорядковых $\sigma_{\circ} [U,V]$-предложений:

(i) $\forall\, x, y\ \bigl(\operatorname{One}(x) \to (\operatorname{Eq}(x,y) \leftrightarrow \operatorname{One}(y)) \bigr)$;

(ii) $\forall\, x, y\ \bigl( \operatorname{One}(y) \to (\operatorname{Eq}(x,y) \leftrightarrow \operatorname{One}(x)) \bigr)$;

(iii) $\forall\, x, y\ \bigl( \operatorname{PPow}(x) \wedge \operatorname{PPow}(y) \to \operatorname{Eq}(x,y) \bigr)$;

(iv) $\forall \, x, y, z, u, v, w\ \bigl(\operatorname{DCup} (x,y,z) \wedge \operatorname{DCup}(u,v,w) \wedge \operatorname{Eq}(x,u) \to (\operatorname{Eq}(y,v) \leftrightarrow \operatorname{Eq}(z,w)) \bigr)$.

Допустим, что $\operatorname{Eq}(x,y)$ определяет $\sim$ в $\mathfrak{A}$. Тогда $\operatorname{PrA}$ верно в $\mathfrak{A}$, как можно без труда убедиться. С другой стороны, допустим, что $\mathfrak{A} \models \operatorname{PrA}$. Мы хотим показать, что для всех $m, n \in \mathbb{N}$

$$ \begin{equation*} \mathfrak{A} \models \operatorname{Eq}(m,n) \quad \Longleftrightarrow \quad m \sim n. \end{equation*} \notag $$
Индукция по $\lambda (m,n):= \min\{\iota(m), \iota(n)\}$.

– Допустим, что $\lambda (m,n)=1$. Тогда $m=1$ или $n=1$. Значит, нужный результат следует из (i) или (ii).

– Допустим, что $\lambda(n,m) \ge 2$. Тогда существуют $p, q \in \mathbb{P}^{\operatorname{sh}arp}$ и $i, j \in \mathbb{N}$ такие, что

$$ \begin{equation*} \mathfrak{C} \models \operatorname{DCup}(p,i,m) \quad \text{и} \quad \mathfrak{C} \models \operatorname{DCup}(q,j,n). \end{equation*} \notag $$

Заметим, что $\mathfrak{A} \models \operatorname{Eq}(p,q)$ ввиду (iii). Кроме того, поскольку $\lambda(i,j)=\lambda(n,m) -1 < \lambda(n,m)$, мы можем применить индуктивную гипотезу к $i$, $j$. Стало быть,

$$ \begin{equation*} \mathfrak{A} \models \operatorname{Eq}(m,n) \quad \stackrel{\text{(iv)}}{\Longleftrightarrow} \quad \mathfrak{A} \models \operatorname{Eq}(i, j) \quad \Longleftrightarrow \quad i \sim j \quad \Longleftrightarrow \quad n \sim m. \end{equation*} \notag $$

Таким образом, $\operatorname{Eq}(x,y)$ определяет $\sim$ в $\mathfrak{A}$. Лемма доказана.

Нам также понадобится следующая лемма.

Лемма 3.5. Пусть $n \in \mathbb{N}$ и $S \subseteq \mathbb{N}$. Допустим, что $S$ определяется в $\mathfrak{C}$ формулой $\Phi(x)$ вида

$$ \begin{equation*} \mathrm{Q}_1 X_1 \dots \mathrm{Q}_n X_n \mathrm{Q}_n X_n' \Psi, \end{equation*} \notag $$
где $X_1$, …, $X_n$, $X_n'$ – различные переменные по множествам, $\{\mathrm{Q}_1, \dots, \mathrm{Q}_n\} \subseteq \{ \forall, \exists\}$ и $\Psi$ не содержит кванторов по множествам. Тогда $S$ также может быть определено в $\mathfrak{C}$ формулой вида
$$ \begin{equation*} \mathrm{Q}_1 X_1 \dots \mathrm{Q}_n X_n \widetilde{\Psi}, \end{equation*} \notag $$
где $\widetilde{\Psi}$ не содержит кванторов по множествам.

Доказательство. В силу утверждения 2.2 мы можем использовать $\mathscr{C}$ вместо $\mathfrak{C}$. Для данного $p \in \mathbb{P}$ возьмем
$$ \begin{equation*} \begin{aligned} \, \mathcal{N}_p &:= \bigl\{N \in \mathcal{N} \mid \mathscr{C} \models N \bot \{p\} \bigr\} \\ &\, = \{N \in \mathcal{N} \mid p \notin N\}. \end{aligned} \end{equation*} \notag $$
Обозначим через $\mathscr{C}_p$ подструктуру $\mathscr{C}$ с носителем $\mathcal{N}_p$. Легко показать, что для любых $p \in \mathbb{P}$ и $N \in \mathcal{N}_p$ существует изоморфизм $\xi^N_p$ из $\mathscr{C}$ на $\mathscr{C}_p$ такой, что $\xi^N_p(N)=N$. Эти изоморфизмы будут играть ключевую роль в дальнейшем.

Теперь пусть $n$, $S$ и $\Phi(x)$ таковы, как в формулировке нашей леммы. Без ограничения общности мы можем считать, что $\mathrm{Q}_n=\forall$; иначе можно перейти от $S$ к его дополнению. Очевидно, часть $\Psi$ может содержать свободные вхождения не только $x$, но также $X_1$, …, $X_n$ или $X_n'$. Таким образом,

$$ \begin{equation*} \Psi = \Psi(x, X_1, \dots, X_n, X_n'). \end{equation*} \notag $$
Зафиксируем индивидную переменную $\mathtt{p}$, которая не входит в $\Psi$ – она будет трактоваться как параметр специального типа. Возьмем
$$ \begin{equation*} \Psi^{\mathtt{p}}:= \text{релятивизация }\Psi\text{ на }x \bot \mathtt{p}. \end{equation*} \notag $$
Другими словами, $\Psi^p$ получается из $\Psi$ посредством замены всех подформул видов $\forall\, u\ \Theta$ и $\exists\, u\ \Theta$ на
$$ \begin{equation*} \forall\, u\ (u \bot p \to \Theta) \quad \text{и} \quad \exists\, u\ (u \bot p \to \Theta) \end{equation*} \notag $$
соответственно. Интуитивно, если $\mathtt{p}$ присваивается $\{p\}$, то все кванторы в $\Psi^{\mathtt{p}}$ бегают по $\mathcal{N}_p$. Тогда для любых $p \in \mathbb{P}$, $N \in \mathcal{N}_p$ и $S_1, \dots, S_n, S_n' \subseteq \mathcal{N}$
$$ \begin{equation*} \mathscr{C} \models \Psi(N, S_1, \dots, S_n, S_n') \quad \Longleftrightarrow \quad \mathscr{C} \models \Psi^{\mathtt{p}}\bigl(\{p\}, N, \xi^N_p[S_1], \dots, \xi^N_p[S_n], \xi^N_p[S_n'] \bigr), \end{equation*} \notag $$
что легко влечет
$$ \begin{equation*} \begin{aligned} \, &\mathscr{C} \models \forall\,X_n\ \forall\, X_n'\ \Psi(N, S_1, \dots, S_{n-1}, X_n, X_n') \\ &\qquad \Longleftrightarrow \quad \mathscr{C} \models \forall\, X_n\ \forall\, X_n'\ \Psi^{\mathtt{p}}\bigl(\{p\}, N, \xi^N_p[S_1], \dots, \xi^N_p[S_{n-1}], X_n, X_n'\bigr). \end{aligned} \end{equation*} \notag $$
Здесь не имеет значения, бегают ли $\forall\, X_n$ и $\forall\, X_n'$ слева по подмножествам $\mathcal{N}$ или по подмножествам $\mathcal{N}_p$. В дальнейшем мы будем использовать для
$$ \begin{equation*} (S_1, \dots, S_{n-1}) \quad \text{и} \quad (\xi^N_p[S_1], \dots, \xi^N_p[S_{n-1}]) \end{equation*} \notag $$
сокращения $\vec{S}$ и $\xi^N_n[\vec{S}]$ соответственно. Заметим, что $\bigl\{\{p\} \mid p \in \mathbb{P} \bigr\}$ может быть определено в $\mathscr{C}$ посредством первопорядковой формулы $\operatorname{PPow}(x)$, т. е. для любого $N \in \mathcal{N}$
$$ \begin{equation*} \mathscr{C} \models \operatorname{PPow}(N) \quad \Longleftrightarrow \quad N=\{p\} \text{ для некоторого }p \in \mathbb{P}. \end{equation*} \notag $$
Стало быть, для любых $N \in \mathcal{N}$ и $S_1, \dots, S_{n-1} \subseteq \mathcal{N}$
$$ \begin{equation*} \begin{aligned} \, &\mathscr{C} \models \forall\, X_n\ \forall\, X_n'\ \Psi(N,\vec{S}, X_n, X_n') \\ &\qquad \Longleftrightarrow \quad \mathscr{C} \models \forall\, \mathtt{p}\ \bigl( \operatorname{PPow}(\mathtt{p}) \wedge N \bot \mathtt{p} \to \forall\, X_n\ \forall\, X_n'\ \Psi^{\mathtt{p}}(\mathtt{p}, N, \xi^N_p[\vec{S}], X_n, X_n')\bigr). \end{aligned} \end{equation*} \notag $$
Далее, для любых $p \in \mathbb{P}$ и $A, B \subseteq \mathcal{N}_p$ существует $C \subseteq \mathcal{N}$ такое, что
$$ \begin{equation*} A=C \cap \mathcal{N}_p \quad \text{и} \quad B=\bigl\{ M \setminus \{p\} \bigm| M \in C \text{ и }p \in M \bigr\}. \end{equation*} \notag $$
Значит, пары подмножеств $\mathcal{N}_p$ могут восприниматься как подмножества $\mathcal{N}$, и наоборот. Более формально, пусть $\widetilde{\Psi}^{\mathtt{p}}$ – результат замены любой $y \in X_n'$ на $\exists\, u\ (\operatorname{DCup}(u, \mathtt{p}, y) \wedge u \in X_n)$ в $\Psi^{\mathtt{p}}$. Тогда
$$ \begin{equation*} \begin{aligned} \, &\mathscr{C} \models \forall\, X_n\ \forall\, X_n'\ \Psi(N, \vec{S}, X_n, X_n') \\ &\qquad \Longleftrightarrow \quad \mathscr{C} \models \forall\, \mathtt{p}\ \bigl( \operatorname{PPow}(\mathtt{p}) \wedge N \bot \mathtt{p} \to \forall\, X_n\ \widetilde{\Psi}^{\mathtt{p}}(\mathtt{p}, N, \xi^N_p[\vec{S}], X_n) \bigr) \\ &\qquad \Longleftrightarrow \quad \mathscr{C} \models \forall\, X_n\ \forall\, \mathtt{p}\ \bigl( \operatorname{PPow}(\mathtt{p}) \wedge N \bot \mathtt{p} \to \widetilde{\Psi}^{\mathtt{p}}(\mathtt{p}, N, \xi^N_p[\vec{S}], X_n) \bigr). \end{aligned} \end{equation*} \notag $$
Следовательно, множество $S$, определенное в $\mathscr{C}$ посредством $\Phi(x)$, может быть также определено посредством
$$ \begin{equation*} \mathrm{Q}_1 X_1,\dots, \mathrm{Q}_{n-1} X_{n-1}\ \forall\, X_n\ \forall\, \mathtt{p}\ \bigl( \operatorname{PPow}(\mathtt{p}) \wedge x \bot \mathtt{p} \to \widetilde{\Psi}^{\mathtt{p}}(\mathtt{p}, x, X_1, \dots, X_{n-1}, X_n) \bigr). \end{equation*} \notag $$
Таким образом, нам удалось элиминировать $X_n'$ в $\Phi(x)$. Лемма доказана.

Теперь мы готовы к получению главного результата.

Доказательство теоремы 3.1. В силу леммы 3.2 $\iota [S]$ является $\Pi^1_n$-множеством и $S=\iota^{-1}[\iota[S]]$. Более того, в силу теоремы 2.1 существует специальная $\Pi^1_n$-$\sigma_{\bullet}$-формула $\Phi(x)$, определяющая $\iota[S]$ в $\mathfrak{P}$. В частности, $\Phi(x)$ имеет вид
$$ \begin{equation*} \forall\, X_1\ \exists\, X_2\dots X_n\ \Psi, \end{equation*} \notag $$
где $\Psi$ не содержит кванторов по множествам. Без ограничения общности мы можем считать, что ни $U$, ни $V$ среди $X_1, X_2, \dots, X_n$ не встречается4. Очевидно, каждая атомарная подформула $\Psi$ имеет вид
$$ \begin{equation*} +(x,y,z), \quad =(x,y) \quad \text{или} \quad x \in X. \end{equation*} \notag $$
Теперь обозначим через $\Psi^{\iota}$ результат замены любой $+ (x,y,z)$ на $\operatorname{Add}(x,y,z)$ и любой $=(x,y)$ на $\operatorname{Eq}(x,y)$ в $\Psi$. Возьмем
$$ \begin{equation*} \Phi^{\iota}:= \begin{cases} \forall\, X_1\ \exists\, X_2\ \dots\ \forall\, X_n\ \forall\, U\ \forall\, V\ (\operatorname{PrA} \to \Psi^{\iota}), &\text{если } n\text{ нечетно}, \\ \forall\, X_1\ \exists\, X_2\ \dots \ \exists\, X_n\ \exists\, U\ \exists\, V\ (\operatorname{PrA} \wedge \Psi^{\iota}), &\text{если }n \text{ четно}. \end{cases} \end{equation*} \notag $$
Ясно, что для всех $n \in \mathbb{N}$
$$ \begin{equation*} \mathfrak{C} \models \Phi^{\iota}(n) \quad \stackrel{\text{леммы 3.3,\, 3.4}}{\Longleftrightarrow} \quad \mathfrak{P}^{\iota} \models \Phi(n) \quad \stackrel{\text{утверждение 2.3}}{\Longleftrightarrow} \quad \mathfrak{P} \models \Phi(\iota(n)). \end{equation*} \notag $$
Таким образом, $\Pi^1_n$-$\sigma_{\circ}$-формула $\Phi^{\iota}$ определяет $S$ в $\mathfrak{C}$. Наконец, мы можем применить лемму 3.5 (дважды), чтобы превратить $\Phi^{\iota}$ в специальную $\Pi^1_n$-$\sigma_{\circ}$-формулу. Теорема 3.1 доказана.

Используя теорему 3.1, можно легко доказать что для каждого $n \in \mathbb{N}$ множество всех специальных $\Pi^1_n$-предложений, истинных в $\mathfrak{C}$, является $\Pi^1_n$-полным – таким образом мы усиливаем результат о сложности $\mathfrak{C}$ в [7] (см. теорему 5.3).

§ 4. По поводу обогащений $\mathfrak{C}$

Цель этого параграфа – привести пример обогащения $\mathfrak{C}$, которое не удовлетворяет $(*)$. В нашем примере будет использоваться расширенная сигнатура

$$ \begin{equation*} \{\operatorname{sq}^1, \bot^2, =^2\}, \end{equation*} \notag $$
где $\operatorname{sq}$ – одноместный функциональный символ, чья подразумеваемая интерпретация – функция возведения в квадрат. Мы будем обозначать соответствующую структуру через $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$.

Теорема 4.1. Существует вычислимое $S \subseteq \mathbb{N}$ такое, что:

$\bullet$ $S$ замкнуто относительно автоморфизмов $\langle \mathbb{N}; \operatorname{sq}, \bot,= \rangle$;

$\bullet$ $S$ не определимо в $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ (посредством монадической формулы).

В нашем рассуждении будет использоваться некоторое количество двухсортной монадической логики второго порядка. Напомним, что в этой логике мы имеем два сорта индивидных переменных:

$$ \begin{equation*} x^0,\ y^0,\ z^0,\ \dots \quad \text{и} \quad x^1,\ y^1,\ z^1,\ \dots\,. \end{equation*} \notag $$
Также имеется два сорта переменных по множествам:
$$ \begin{equation*} X^0,\ Y^0,\ Z^0,\ \dots \quad \text{и} \quad X^1,\ Y^1,\ Z^1,\ \dots\,. \end{equation*} \notag $$
Для каждого $\varepsilon \in \{ 0, 1 \}$ обозначим через $\operatorname{Var}^{\varepsilon}$ совокупность всех переменных сорта $\varepsilon$. Далее, пусть $\sigma_0$ и $\sigma_1$ – две непересекающиеся (односортные) сигнатуры. Под атомарной $(\sigma_0, \sigma_1)$-формулой мы понимаем атомарную $\sigma_0$-формулу над $\operatorname{Var}^0$ или атомарную $\sigma_1$-формулу над $\operatorname{Var}^1$. Например:

$\bullet$ $x^0 \in X^0$ и $x^1 \in X^1$ обе являются атомарными $(\sigma_0, \sigma_1)$-формулами;

$\bullet$ ни $x^0 \in X^1$, ни $x^1 \in X^0$ не является атомарной $(\sigma_0, \sigma_1)$-формулой.

Теперь $(\sigma_0, \sigma_1)$-формулы строятся из атомарных $(\sigma_0, \sigma_1)$-формул, используя символы связок и кванторы обычным образом. Само собой, $(\sigma_0, \sigma_1)$-формулы, не содержащие переменных сорта $0$ или $1$, могут отождествляться с $\sigma_1$-формулами или $\sigma_0$-формулами соответственно.

Обращаясь к семантике, для каждого $\varepsilon \in \{0, 1\}$ пусть $\mathfrak{A}_{\varepsilon}$ – $\sigma_{\varepsilon}$-структура. Обозначим через $(\mathfrak{A}_0, \mathfrak{A}_1)$ соответствующую двухсортную $(\sigma_0, \sigma_1)$-структуру. Значит, для любого $\varepsilon \in \{0,1\}$:

– индивидные переменные сорта $\varepsilon$ бегают по элементам носителя $\mathfrak{A}_{\varepsilon}$;

– переменные по множествам сорта $\varepsilon$ бегают по подмножествам носителя $\mathfrak{A}_{\varepsilon}$;

– символы $\sigma_{\varepsilon}$ интерпретируются в $(\mathfrak{A}_0, \mathfrak{A}_1)$ в точности так же, как они интерпретируются в $\mathfrak{A}_{\varepsilon}$.

Приведем простой, но полезный факт.

Лемма 4.2. Пусть $\sigma_0$ и $\sigma_1$ – две непересекающиеся сигнатуры, и пусть $\Phi$ – $(\sigma_0, \sigma_1)$-формула. Тогда $\Phi$ эквивалентна булевой комбинации $\sigma_0$-формул над $\operatorname{Var}^0$ и $\sigma_1$-формул над $\operatorname{Var}^1$.

Доказательство. Индукция по сложности $\Phi$. Без ограничения общности мы можем считать, что $\vee$, $\to$ и $\forall$ не входят в $\Phi$, хотя $\wedge$, $\neg$ и $\exists$ могут входить в $\Phi$.

– Допустим, что $\Phi$ атомарна. Тогда она уже имеет требуемый вид.

– Допустим, что $\Phi=\Psi \wedge \Theta$. В силу индуктивной гипотезы, $\Psi$ и $\Theta$ эквивалентны подходящим булевым комбинациям $\Psi'$ и $\Theta'$ соответственно. Таким образом, $\Phi$ эквивалентна $\Psi' \wedge \Theta'$, которая имеет требуемый вид.

– Допустим, что $\Phi=\neg \Psi$. Тогда мы можем рассуждать так же, как в предыдущем случае.

– Допустим, что $\Phi=\exists\, \mathfrak{u}\ \Psi$, где $\mathfrak{u} \in \operatorname{Var}^0 \cup \operatorname{Var}^1$. В силу индуктивной гипотезы, $\Psi$ эквивалентна подходящей булевой комбинации $\Psi'$. Используя пропозициональную логику, мы можем привести $\Psi'$ к виду

$$ \begin{equation*} (\Theta_1^0 \wedge \Theta_1^1) \vee \dots \vee (\Theta_n^0 \wedge \Theta_n^1), \end{equation*} \notag $$
где $\Theta^0_1$, …, $\Theta^0_n$ являются $\sigma_0$-формулами над $\operatorname{Var}^0$ и $\Theta^1_1$, …, $\Theta^1_n$ являются $\sigma_1$-формулами над $\operatorname{Var}^1$. Значит, $\Phi$ эквивалентна
$$ \begin{equation*} \exists\, \mathfrak{u}\ \bigl((\Theta_1^0 \wedge \Theta_1^1) \vee \dots \vee (\Theta_n^0 \wedge \Theta_n^1) \bigr), \end{equation*} \notag $$
которая, в свою очередь, эквивалентна:

$\bullet$ $(\exists\, \mathfrak{u}\ \Theta_1^0 \wedge \Theta_1^1) \vee \dots \vee (\exists\, \mathfrak{u}\ \Theta_n^0 \wedge \Theta_n^1)$, если $\mathfrak{u} \in \operatorname{Var}^0$;

$\bullet$ $(\Theta_1^0 \wedge \exists\, \mathfrak{u}\ \Theta_1^1) \vee \dots \vee (\Theta_n^0 \wedge \exists\, \mathfrak{u}\ \Theta_n^1)$, если $\mathfrak{u} \in \operatorname{Var}^1$.

В каждом случае мы получаем желаемую булеву комбинацию. Лемма доказана.

Вспомним, что $S \subseteq \mathbb{N}$ называется почти периодичным, если существуют натуральные числа $p$ и $a$ такие, что для любого натурального числа $n$ большего, чем $a$,

$$ \begin{equation*} n\in S \quad \Longleftrightarrow \quad n+p\in S. \end{equation*} \notag $$
Рассмотрим сигнатуру $\{ \mathsf{s}^1, =^2\}$, где $\mathsf{s}$ – одноместный функциональный символ, чья подразумеваемая интерпретация – функция последователя; обозначим соответствующую структуру через $\langle \mathbb{N}; \mathsf{s},=\rangle$. Следующий результат можно легко извлечь из работ Бюхи.

Теорема 4.3 (см. [9], [10]). Подмножество $\mathbb{N}$ определимо в $\langle \mathbb{N}; \mathsf{s},=\rangle$ (посредством монадической формулы) тогда и только тогда, когда оно почти периодично.

Доказательство. Как следствие теоремы 1 в [10] (см. четвертое замечание после нее), Бюхи показывает, что для любого $S \subseteq \mathbb{N}$ следующие условия эквивалентны:

(i) $S$ определимо в $\langle \mathbb{N}; \mathsf{s},=\rangle$;

(ii) $S$ определимо в $\langle \mathbb{N}; \mathsf{s},=\rangle$ в “слабом смысле”, а именно в случае, когда все кванторы по множествам ограничиваются так, чтобы бегать по конечным подмножествам $\mathbb{N}$.

Кроме того, в силу следствия 2 в [9; § 5] условие (ii) верно тогда и только тогда, когда $S$ почти периодично. Теорема доказана.

Ясно, что поскольку обычное отношение порядка определимо в $\langle \mathbb{N}; \mathsf{s},=\rangle$ и функция последователя определима в $\langle \mathbb{N}; \le \rangle$, мы можем переформулировать теорему 4.3 с $\langle \mathbb{N}; \le \rangle$ вместо $\langle \mathbb{N}; \mathsf{s},=\rangle$.

Лемма 4.4. Пусть $S \subseteq \mathbb{N}$ и $m \in \mathbb{N}$. Допустим, что:

$\bullet$ $S$ определимо в $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ (посредством монадической формулы);

$\bullet$ $m$ не является квадратом натурального числа, т. е. $\sqrt{m} \notin \mathbb{N}$.

Тогда существует почти периодичное $K \subseteq \mathbb{N}$ такое, что для любого $n \in \mathbb{N}$

$$ \begin{equation*} m^{2^n}\in S \quad \Longleftrightarrow \quad n\in K. \end{equation*} \notag $$

Доказательство. Мы будем иметь дело с двумя специальными сигнатурами:
$$ \begin{equation*} \sigma_0:= \{ \operatorname{sq}^1, \bot^2, \operatorname{Co}_m^1, =^2\} \quad \text{и} \quad \sigma_1:= \{ \operatorname{sq}^1, =^2 \}. \end{equation*} \notag $$
Здесь $\operatorname{Co}_m$ – одноместный предикатный символ, чья подразумеваемая интерпретация – отношение “$x$ и $m$ не имеют общих простых делителей”. Формально $\sigma_0$ и $\sigma_1$ должны быть непересекающимися, но интерпретации $\operatorname{sq}$ и $=$ всегда будут ясны из контекста, так что данное требование может быть опущено. Ясно, что любой терм из $\sigma_0$/$\sigma_1$ содержит ровно одну (индивидную) переменную. Положим
$$ \begin{equation*} D:= \{ m^{2^n} \mid n \in \mathbb{N}\}. \end{equation*} \notag $$
Мы используем $\chi_D$ для обозначения характеристической функции $D$. Она может быть расширена на конечные последовательности натуральных чисел посредством равенства
$$ \begin{equation*} \chi_D(i_1, \dots, i_n):= (\chi_D(i_1), \dots, \chi_D(i_n)). \end{equation*} \notag $$
Заметим, что $D$ и $\mathbb{N} \setminus D$ оба замкнуты относительно функции возведения в квадрат. Теперь возьмем
$$ \begin{equation*} \mathfrak{A}_0:= \langle \mathbb{N} \setminus D; \operatorname{sq}, \bot, \operatorname{Co}_m,=\rangle \quad \text{и} \quad \mathfrak{A}_1:= \langle D; \operatorname{sq},=\rangle. \end{equation*} \notag $$
Мы предполагаем, что в этих структурах символы из $\sigma_0$ и $\sigma_1$ интерпретируются как ограничения их стандартных интерпретаций на $\mathbb{N} \setminus D$ и $D$ соответственно.

Для удобства обозначим $\{\operatorname{sq}^1, \bot^2, =^2\}$ через $\sigma$. Рассмотрим произвольную $\sigma$-формулу

$$ \begin{equation*} \Phi(x_1, \dots,x_n, X_1, \dots, X_k). \end{equation*} \notag $$
Наша следующая задача – построить индексированное семейство $(\sigma_0,\sigma_1)$-формул
$$ \begin{equation*} \langle \Phi^{\tau}(x_1^{\tau_1}, \dots, x_n^{\tau_n}, X_1^0, \dots, X_k^0, X_1^1, \dots, X_k^1) \colon \tau \in \{0,1\}^n \rangle \end{equation*} \notag $$
такое, что для любых $a_1, \dots, a_n \in \mathbb{N}$ и $A_1, \dots, A_k \subseteq \mathbb{N}$ следующие условия эквивалентны:

(i) $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle \models \Phi(a_1, \dots, a_n, A_1, \dots, A_k)$;

(ii) $(\mathfrak{A}_0, \mathfrak{A}_1) \models \Phi^{\chi_D(a_1, \dots, a_n)} (a_1, \dots, a_n, A_1 \setminus D, \dots, A_k \setminus D, A_1 \cap D, \dots, A_n \cap D)$.

Без ограничения общности мы считаем, что $\vee$, $\to$ и $\forall$ не входят в $\Phi$. Формулы $\Phi^\tau$ тогда определяются индукцией по сложности $\Phi$:

– если $\Phi$ имеет вид $t(x_i) \in X_l$, то возьмем $\Phi^\tau$ равным $t(x_i^{\tau_i}) \in X_l^{\tau_i}$;

– если $\Phi$ имеет вид $s(x_i) \bot t(x_j)$, то возьмем

$$ \begin{equation*} \Phi^\tau:= \begin{cases} s(x_i^0) \bot t(x_j^0), &\text{если }\tau_i=\tau_j=0, \\ \operatorname{Co}_m(s(x_i^0)), &\text{если } \tau_i=0\text{ и }\tau_j=1, \\ \operatorname{Co}_m(t(x_j^0)), &\text{если } \tau_i=1 \text{ и } \tau_j=0, \\ x_i^1 \ne x_i^1, &\text{если } \tau_i=\tau_j=1; \end{cases} \end{equation*} \notag $$

– если $\Phi$ имеет вид $s (x_i)=t (x_j)$, то возьмем

$$ \begin{equation*} \Phi^\tau:= \begin{cases} s(x_i^{\tau_i})=t(x_j^{\tau_i}), &\text{если } \tau_i=\tau_j, \\ x_i^{\tau_i} \ne x_i^{\tau_i}, &\text{если } \tau_i \ne \tau_j; \end{cases} \end{equation*} \notag $$

– если $\Phi$ имеет вид $\Psi \wedge \Theta$, то возьмем $\Phi^\tau$ равным $\Psi^\tau \wedge \Theta^\tau$;

– если $\Phi$ имеет вид $\neg\, \Psi$, то возьмем $\Phi^\tau$ равным $\neg\, \Psi^\tau$;

– если $\Phi$ имеет вид $\exists\, y\ \Psi(x_1, \dots, x_n, y, X_1, \dots, X_k)$, то возьмем

$$ \begin{equation*} \Phi^\tau:= \bigvee_{\varepsilon \in\{0,1\}} \exists\, x_{n+1}^{\varepsilon}\ \bigl( \Psi(x_1, \dots, x_n, x_{n+1}, X_1, \dots, X_k) \bigr)^{(\tau_1, \dots, \tau_n, \varepsilon)}; \end{equation*} \notag $$

– если $\Phi$ имеет вид $\exists\, Y\ \Psi(x_1, \dots, x_n, X_1, \dots, X_k, Y)$, то возьмем

$$ \begin{equation*} \Phi^\tau:= \exists\, X_{k+1}^0\ \exists\, X_{k+1}^1\ \bigl( \Psi(x_1, \dots, x_n, X_1, \dots, X_k, X_{k+1}) \bigr)^\tau. \end{equation*} \notag $$

Непосредственно проверяется, что результирующее семейство обладает требуемым свойством.

Наконец, пусть $\Phi(x)$ – $\sigma$-формула, которая определяет $S$ в $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$. Тогда конструкция из предыдущего абзаца дает нам $(\sigma_0, \sigma_1)$-формулы $\Phi^0(x^0)$ и $\Phi^1(x^1)$ такие, что для всех $a \in \mathbb{N}$:

$$ \begin{equation*} \begin{aligned} \, a \notin D \quad &\Longrightarrow \quad \bigl( \langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle \models \Phi (a) \ \ \Longleftrightarrow \ \ (\mathfrak{A}_0, \mathfrak{A}_1) \models \Phi^0 (a)\bigr); \\ a \in D \quad &\Longrightarrow \quad \bigl( \langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle \models \Phi (a) \ \ \Longleftrightarrow \ \ (\mathfrak{A}_0, \mathfrak{A}_1) \models \Phi^1(a)\bigr). \end{aligned} \end{equation*} \notag $$
Далее, в силу леммы 4.2 $\Phi^1 (x^1)$ эквивалентна булевой комбинации $\sigma_0$-предложений $\Psi_i$ и $\sigma_1$-формул $\Theta_j (x^1)$. Разумеется, мы можем заменить каждое $\Psi_i$ в этой булевой комбинации на:

$\bullet$ $x^1=x^1$, если $\mathfrak{A}_0 \models \Psi_i$;

$\bullet$ $x^1 \ne x^1$, если $\mathfrak{A}_0 \not \models \Psi_i$.

Таким образом, $\Phi^1 (x^1)$ может быть преобразована в $\sigma_1$-формулу $\widetilde{\Phi}(x^1)$. Значит, для любого $a \in D$

$$ \begin{equation*} a\in S \quad \Longleftrightarrow \quad \langle D; \operatorname{sq},=\rangle \models \widetilde{\Phi}(a). \end{equation*} \notag $$
Заметим, что $\bigl(m^{2^n}\bigr)^2 = m^{2^{n+1}}$ для всех $n \in \mathbb{N}$. Значит, если $\operatorname{sq}$ и $\mathsf{s}$ трактовать как один и тот же символ, то функция $n \mapsto m^{2^n}$ является изоморфизмом из $\langle \mathbb{N}; \mathsf{s},=\rangle$ на $\langle D; \operatorname{sq},=\rangle$. Возьмем
$$ \begin{equation*} \widehat{\Phi}:= \text{результат замены }\operatorname{sq}\text{ в }\widetilde{\Phi}\text{ на } \mathsf{s}. \end{equation*} \notag $$
Обозначим через $K$ множество, определенное в $\langle \mathbb{N}; \mathsf{s},=\rangle$ посредством $\widehat{\Phi}$. Следовательно, для любого $n \in \mathbb{N}$
$$ \begin{equation*} m^{2^n}\in S \quad \Longleftrightarrow \quad \langle D; \operatorname{sq},=\rangle \models \widetilde{\Phi}(m^{2^n}) \quad \Longleftrightarrow \quad \langle \mathbb{N}; \mathsf{s},=\rangle \models \widehat{\Phi}(n) \quad \Longleftrightarrow \quad n\in K. \end{equation*} \notag $$
Кроме того, $K$ является почти периодичным по теореме 4.3. Лемма доказана.

Мы готовы к тому, чтобы доказать теорему 4.1.

Доказательство теоремы 4.1. Возьмем
$$ \begin{equation*} S:= \bigl\{ m^{2^{2^k}} \bigm| m, k \in \mathbb{N} \text{ и }\sqrt{m} \notin \mathbb{N} \bigr\}. \end{equation*} \notag $$
Разумеется, $S$ вычислимо и замкнуто относительно автоморфизмов $\langle \mathbb{N}; \operatorname{sq}, \bot,= \rangle$. Теперь допустим, что $S$ определимо в $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ (посредством монадической формулы). Зафиксируем какое-нибудь $\mathtt{m} \in \mathbb{N}$ такое, что $\sqrt{\mathtt{m}} \notin \mathbb{N}$, например можно взять $\mathtt{m} := 2$. Тогда в силу леммы 4.4 существует почти периодичное $K \subseteq \mathbb{N}$ такое, что для любого $n \in \mathbb{N}$
$$ \begin{equation*} \mathtt{m}^{2^n}\in S \quad \Longleftrightarrow \quad n\in K. \end{equation*} \notag $$
Стало быть, $K$ совпадает с $\{ 2^k \mid k \in \mathbb{N}\}$, что противоречит почти периодичности $K$. Теорема доказана.

Техника, разработанная для доказательства теоремы 4.1, может быть адаптирована для получения других примеров обогащений $\mathfrak{C}$, которые не удовлетворяют $(*)$. В частности, рассмотрим сигнатуру

$$ \begin{equation*} \{ \bot^2, \sqsubseteq^2\}, \end{equation*} \notag $$
где $\sqsubseteq$ – двухместный предикатный символ, чья подразумеваемая интерпретация – отношение
$$ \begin{equation*} \{ (m,n) \in \mathbb{N}^2 \mid [\![m]\!]=[\![n]\!] \text{ и }m\text{ делит }n \}. \end{equation*} \notag $$
Мы будем обозначать соответствующую структуру через $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. Хотя $\langle \mathbb{N}; \operatorname{sq}, \bot,=\rangle$ может казаться более естественной, чем $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$, последняя ближе к структуре над $\mathbb{N}$ с отношением делимости, которая изучалась в [7]: $=$, $\bot$ и $\sqsubseteq$ первопорядково определимы при помощи отношения делимости, а $\operatorname{sq}$ – нет.

Теорема 4.5. Существует вычислимое $S \subseteq \mathbb{N}$ такое, что:

$\bullet$ $S$ замкнуто относительно автоморфизмов $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$;

$\bullet$ $S$ не определимо в $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$.

Чтобы это доказать, мы будем использовать следующий аналог леммы 4.4.

Лемма 4.6. Пусть $S\,{\subseteq}\, \mathbb{N}$ и $p\,{\in}\,\mathbb{P}$. Допустим, что $S$ определимо в $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. Тогда существует почти периодичное $K \subseteq \mathbb{N}$ такое, что для любого $n \in \mathbb{N}$

$$ \begin{equation*} p^n\in S \quad \Longleftrightarrow \quad n\in K. \end{equation*} \notag $$

Доказательство. На этот раз мы будем иметь дело с
$$ \begin{equation*} \sigma_0:= \{ \bot^2, \operatorname{Co}_p^1, \sqsubseteq^2\} \quad \text{и} \quad \sigma_1:= \{ \sqsubseteq^2 \}. \end{equation*} \notag $$
Как и прежде, $\operatorname{Co}_p$ будет интерпретироваться как отношение “$x$ и $p$ не имеют общих простых делителей”, т. е. “$x$ не делится на $p$”. Положим $D$ равным $\{ p^n \mid n \in \mathbb{N}\}$. Возьмем
$$ \begin{equation*} \mathfrak{A}_0:= \langle {\mathbb{N} \setminus D}; \bot, \operatorname{Co}_p, \sqsubseteq \rangle \quad \text{и} \quad \mathfrak{A}_1:= \langle D; \sqsubseteq \rangle. \end{equation*} \notag $$
Для удобства обозначим $\{ \bot^2, \sqsubseteq^2\}$ через $\sigma$. Как и в доказательстве леммы 4.1, непосредственно показывается, что для каждой $\sigma$-формулы $\Phi$ мы можем индуктивно определить подходящее индексированное семейство $(\sigma_0, \sigma_1)$-формул $\Phi^{\tau}$.

Пусть $\Phi(x)$ – $\sigma$-формула, которая определяет $S$ в $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. То же рассуждение, что и в доказательстве леммы 4.1, дает нам $\sigma_1$-формулу $\widetilde{\Phi}(x^1)$ такую, что для любого $a \in D$,

$$ \begin{equation*} a\in S \quad \Longleftrightarrow \quad \langle D; \sqsubseteq \rangle \models \widetilde{\Phi}(a). \end{equation*} \notag $$
Очевидно, если $\le$ и $\sqsubseteq$ трактовать как один и тот же символ, то функция $n \mapsto p^n$ является изоморфизмом из $\langle \mathbb{N}; \le \rangle$ на $\langle D; \sqsubseteq \rangle$. Возьмем
$$ \begin{equation*} \widehat{\Phi}:= \text{результат замены }\le\text{ в }\widetilde{\Phi}\text{ на }\sqsubseteq. \end{equation*} \notag $$
Обозначим через $K$ множество, определенное в $\langle \mathbb{N}; \sqsubseteq \rangle$ посредством $\widehat{\Phi}$. Следовательно, для любого $n \in \mathbb{N}$
$$ \begin{equation*} p^n\in S \quad \Longleftrightarrow \quad \langle D; \sqsubseteq \rangle \models \widetilde{\Phi}(p^n) \quad \Longleftrightarrow \quad \langle \mathbb{N}; \le \rangle \models \widehat{\Phi}(n) \quad \Longleftrightarrow \quad n\in K. \end{equation*} \notag $$
Кроме того, $K$ является почти периодичным по теореме 4.3. Лемма доказана.

Эта лемма позволяет нам получить желаемый результат.

Доказательство теоремы 4.5. Возьмем
$$ \begin{equation*} S:= \{ p^{2^n} \mid p \in \mathbb{P} \text{ и }n \in \mathbb{N} \}. \end{equation*} \notag $$
Ясно, что $S$ вычислимо и замкнуто относительно автоморфизмов $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. Допустим, что $S$ определимо в $\langle \mathbb{N}; \bot, \sqsubseteq \rangle$. Зафиксируем какое-нибудь $\mathtt{p} \in \mathbb{P}$. Тогда в силу леммы 4.6 существует почти периодичное $K \subseteq \mathbb{N}$ такое, что для любого $n \in \mathbb{N}$
$$ \begin{equation*} \mathtt{p}^n\in S \quad \Longleftrightarrow \quad n\in K. \end{equation*} \notag $$
Стало быть, $K$ совпадает с $\left\{ 2^k \mid k \in \mathbb{N} \right\}$, что является противоречием. Теорема доказана.

Список литературы

1. D. Richard, “What are weak arithmetics?”, Theoret. Comput. Sci., 257:1-2 (2001), 17–29  crossref  mathscinet  zmath
2. J. Y. Halpern, “Presburger arithmetic with unary predicates is $\Pi_1^1$ complete”, J. Symbolic Logic, 56:2 (1991), 637–642  crossref  mathscinet  zmath
3. S. O. Speranski, “A note on definability in fragments of arithmetic with free unary predicates”, Arch. Math. Logic, 52:5-6 (2013), 507–516  crossref  mathscinet  zmath
4. A. Bès, D. Richard, “Undecidable extensions of Skolem arithmetic”, J. Symbolic Logic, 63:2 (1998), 379–401  crossref  mathscinet  zmath
5. J. Robinson, “Definability and decision problems in arithmetic”, J. Symbolic Logic, 14:2 (1949), 98–114  crossref  mathscinet  zmath
6. A. Bès, “A survey of arithmetical definability”, A tribute to Maurice Boffa, Bull. Belg. Math. Soc. Simon Stevin, suppl., Soc. Math. Belgique, Brussels, 2001, 1–54  mathscinet  zmath
7. S. O. Speranski, “Some new results in monadic second-order arithmetic”, Computability, 4:2 (2015), 159–174  crossref  mathscinet  zmath
8. Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость, Мир, М., 1972, 624 с.  mathscinet  zmath; пер. с англ.: H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York–Toronto, ON–London, 1967, xx+482 с.  mathscinet  zmath
9. J. R. Büchi, “Weak second-order arithmetic and finite automata”, Z. Math. Logik Grundlagen Math., 6:1-6 (1960), 66–92  crossref  mathscinet  zmath
10. J. R. Büchi, “On a decision method in restricted second order arithmetic”, Logic, methodology and philosophy of science (1960), Stanford Univ. Press, Stanford, CA, 1962, 1–11  mathscinet  zmath

Образец цитирования: С. О. Сперанский, Ф. Н. Пахомов, “Об отношении взаимной простоты с точки зрения монадической логики второго порядка”, Изв. РАН. Сер. матем., 86:6 (2022), 207–222; Izv. Math., 86:6 (2022), 1225–1239
Цитирование в формате AMSBIB
\RBibitem{SpePak22}
\by С.~О.~Сперанский, Ф.~Н.~Пахомов
\paper Об отношении взаимной простоты с точки зрения монадической логики второго порядка
\jour Изв. РАН. Сер. матем.
\yr 2022
\vol 86
\issue 6
\pages 207--222
\mathnet{http://mi.mathnet.ru/im9340}
\crossref{https://doi.org/10.4213/im9340}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4582553}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2022IzMat..86.1225S}
\transl
\jour Izv. Math.
\yr 2022
\vol 86
\issue 6
\pages 1225--1239
\crossref{https://doi.org/10.4213/im9340e}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000992259900009}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85172021131}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/im9340
  • https://doi.org/10.4213/im9340
  • https://www.mathnet.ru/rus/im/v86/i6/p207
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Статистика просмотров:
    Страница аннотации:388
    PDF русской версии:31
    PDF английской версии:83
    HTML русской версии:198
    HTML английской версии:108
    Список литературы:52
    Первая страница:23
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024