| Известия Российской академии наук. Серия математическая |
|
|
|
|
|
Об отношении взаимной простоты с точки зрения монадической логики второго порядка С. О. Сперанскийa, Ф. Н. Пахомовab a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва b Гентский университет, Гент, Бельгия
Англоязычная версия:
Izvestiya: Mathematics, 2022, Volume 86, Issue 6, Pages DOI: https://doi.org/10.4213/im9340e 
Реферативные базы данных:
    § 1. ВведениеНас будут интересовать относительно слабые арифметические структуры, поэтому наша работа может рассматриваться как исследование по “слабым арифметикам” (пользуясь терминологией из [1]). Многие интересные вопросы в этой области касаются двух типов определимости: (i) первопорядковая определимость; (ii) монадическая второпорядковая определимость1. В частности, имеются красивые результаты о (i), связанные с делимостью и взаимной простотой, например результаты в [4], вдохновленные фундаментальной работой Робинсон [5] (см. также [6]). Что до (ii), то делимость была изучена в [7]. Настоящая статья будет иметь дело с взаимной простотой. В дальнейшем под формулой мы будем понимать монадическую второпорядковую формулу, если не указано иное. Отметим, что символ $=$ будет трактоваться как нелогический (который может принадлежать или не принадлежать данной сигнатуре). Для удобства ноль не будет считаться элементом $\mathbb{N}$, т. е. Подмножество $\mathbb{N}$ называется $\Pi^1_n$-множеством, если оно определимо в стандартной модели арифметики Пеано посредством $\Pi^1_n$-формулы. Пусть $\sigma$ – сигнатура и $\mathfrak{A}$ – $\sigma$-структура с носителем $\mathbb{N}$. Рассмотрим теперь следующее условие: С точки зрения монадической логики второго порядка, если $\mathfrak{A}$ удовлетворяет $(*)$, то мы хорошо понимаем, что может быть определено в $\mathfrak{A}$.В [3] было доказано, что $(*)$ выполнено для стандартной модели арифметики Пресбургера. Далее, в [7] было показано, что $(*)$ выполнено для структуры натуральных чисел с отношением делимости, так же как и для всех ее обогащений (включая стандартную модель арифметики Сколема). Но что происходит, если мы заменяем делимость на взаимную простоту? Возьмем Здесь $\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$ имеет единичную длину. Возьмем Здесь $+$ есть трехместный предикатный символ (не двухместный функциональный символ), чья подразумеваемая интерпретация – график функции сложения. Обозначим соответствующую $\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}$ посредством формул второго и даже более высоких порядков. Чтобы сделать это утверждение более точным, рассмотрим Пусть $\mathscr{C}$ – $\sigma_{\circ}$-структура с носителем $\mathcal{N}$, в которой символ $\bot$ интерпретируется как
$$
\begin{equation*}
\{(M, N) \in \mathcal{N}^2 \mid M \cap N=\varnothing\}.
\end{equation*}
\notag
$$
Тогда мы имеем следующее. Доказательство. Обозначим через $\approx$ отношение “$m$ и $n$ имеют одни и те же простые делители”, т. е. Очевидно, $\approx$ является отношением конгруэнции на $\mathfrak{C}$. Рассмотрим факторструктуру $\mathfrak{C} /{\approx}$ для $\mathfrak{C}$ по $\approx$. Определим функцию $\eta$ из $\mathbb{N} /{\approx}$ в $\mathcal{N}$ посредством равенства где $[n]_{\approx}$ обозначает класс эквивалентности $n$ по $\approx$. Тогда $\eta$ является изоморфизмом из $\mathfrak{C}/{\approx}$ на $\mathscr{C}$. Таким образом, для любых $\sigma$-формулы $\Phi(x)$ и $n\in\mathbb{N}$ что и требовалось. Утверждение доказано. Для любого множества $S$ мы будем обозначать через $\operatorname{card}(S)$ мощность $S$. Определим функцию $\iota$ из $\mathbb{N}$ в $\mathbb{N}$ посредством равенства В частности, $\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}$. Доказательство. Ясно, что $\sim$ является отношением конгруэнции на $\mathfrak{P}^{\iota}$. Рассмотрим факторструктуру $\mathfrak{P}^{\iota}/{\sim}$ для $\mathfrak{P}^{\iota}$ по $\sim$. Определим функцию $\xi$ из $\mathbb{N}/{\sim}$ в $\mathbb{N}$ посредством равенства где $[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]\!]$ оба бесконечны. Возьмем Тогда существуют первопорядковые $\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]$-формулу Легко убедиться, что она определяет $\sim$ в $\langle \mathfrak{C}, A, B \rangle$. Лемма доказана. Более того, мы имеем следующее. Лемма 3.4. Существует первопорядковое $\sigma_{\circ} [U,V]$-предложение $\operatorname{PrA}$ такое, что для любого $\sigma_{\circ} [U,V]$-обогащения $\mathfrak{A}$ для $\mathfrak{C}$ Доказательство. Ясно, что если $\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)$ вида где $X_1$, …, $X_n$, $X_n'$ – различные переменные по множествам, $\{\mathrm{Q}_1, \dots, \mathrm{Q}_n\} \subseteq \{ \forall, \exists\}$ и $\Psi$ не содержит кванторов по множествам. Тогда $S$ также может быть определено в $\mathfrak{C}$ формулой вида где $\widetilde{\Psi}$ не содержит кванторов по множествам. Доказательство. В силу утверждения 2.2 мы можем использовать $\mathscr{C}$ вместо $\mathfrak{C}$. Для данного $p \in \mathbb{P}$ возьмем Обозначим через $\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'$. Таким образом, Зафиксируем индивидную переменную $\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)$, может быть также определено посредством Таким образом, нам удалось элиминировать $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)$ имеет вид где $\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}$, которое не удовлетворяет $(*)$. В нашем примере будет использоваться расширенная сигнатура где $\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$, Рассмотрим сигнатуру $\{ \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*}
\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$ содержит ровно одну (индивидную) переменную. Положим Мы используем $\chi_D$ для обозначения характеристической функции $D$. Она может быть расширена на конечные последовательности натуральных чисел посредством равенства Заметим, что $D$ и $\mathbb{N} \setminus D$ оба замкнуты относительно функции возведения в квадрат. Теперь возьмем Мы предполагаем, что в этих структурах символы из $\sigma_0$ и $\sigma_1$ интерпретируются как ограничения их стандартных интерпретаций на $\mathbb{N} \setminus D$ и $D$ соответственно.
Для удобства обозначим $\{\operatorname{sq}^1, \bot^2, =^2\}$ через $\sigma$. Рассмотрим произвольную $\sigma$-формулу Наша следующая задача – построить индексированное семейство $(\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}$ Стало быть, $K$ совпадает с $\{ 2^k \mid k \in \mathbb{N}\}$, что противоречит почти периодичности $K$. Теорема доказана. Техника, разработанная для доказательства теоремы 4.1, может быть адаптирована для получения других примеров обогащений $\mathfrak{C}$, которые не удовлетворяют $(*)$. В частности, рассмотрим сигнатуру где $\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*}
\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}$ Стало быть, $K$ совпадает с $\left\{ 2^k \mid k \in \mathbb{N} \right\}$, что является противоречием. Теорема доказана. 
Цитирование в формате AMSBIB
\RBibitem{SpePak22} |
|
||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|