| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях) Ранги и аппроксимации для семейств упорядоченных теорий Б. Ш. Кулпешовab, Ин. И. Павлюкc, С. В. Судоплатовcd a Казахстанско-Британский технический университет, г. Алматы, Казахстан b Институт математики и математического моделирования, г. Алматы, Казахстан c Новосибирский государственный технический университет d Институт математики им. С. Л. Соболева Сибирского отделения Российской академии наук, г. Новосибирск
Англоязычная версия:
Mathematical Notes, 2024, Volume 116, Issue 4, Pages DOI: https://doi.org/10.1134/S0001434624090256 
Реферативные базы данных:
 1. Введение и постановка задачиПусть $L$ – счетный язык первого порядка. Всюду в данной статье мы рассматриваем $L$-структуры и предполагаем, что $L$ содержит символ бинарного отношения $<$, который интерпретируется как линейный порядок в этих структурах. Настоящая работа касается понятий о-минимальности (введенной и первоначально исследованной Пиллэем и Стайнхорном в [1]) и слабой о-минимальности (первоначально глубоко исследованного Макферсоном, Маркером и Стайнхорном в [2]). Открытый интервал $I$ в структуре $\mathcal{M}$ есть параметрически определимое подмножество структуры $\mathcal{M}$ вида $I=\{c\in M\colon M\models a<c<b\}$ для некоторых $a, b \in M\cup \{-\infty, \infty\}$, где $a<b$. Аналогично, мы можем определить замкнутые, полуоткрытые-полузамкнутые и т.п. интервалы в $\mathcal{M}$, так что, например, произвольная точка структуры $\mathcal{M}$ является сама (тривиальным) замкнутым интервалом. Подмножество $A$ линейно упорядоченной структуры $\mathcal{M}$ называется выпуклым, если для любых $a, b\in A$ и $c\in M$ всякий раз, когда $a<c<b$, мы имеем $c\in A$. Слабо о-минимальной структурой называется линейно упорядоченная структура $\mathcal{M}=\langle M,=,<,\dots \rangle$ такая, что любое определимое (с параметрами) подмножество структуры $\mathcal{M}$ является объединением конечного числа выпуклых множеств в $\mathcal{M}$. Вспомним, что такая структура $\mathcal{M}$ называется о-минимальной, если каждое определимое (с параметрами) подмножество структуры $\mathcal{M}$ является объединением конечного числа интервалов и точек в $\mathcal{M}$. Упорядоченное поле вещественных чисел обеспечивает пример о-минимальной структуры. Вещественно замкнутые поля с собственным выпуклым кольцом нормирования обеспечивают важный пример слабо о-минимальных (не о-минимальных) структур [3], [4]. В работе изучаются значения рангов $\operatorname{RS}(\cdot)$ [5], аппроксимации [6] и свойства генеричности предложений [7], [8] для ряда естественных семейств упорядоченных теорий. Ранги $\operatorname{RS}(\cdot)$, являющиеся естественными вариациями рангов Кантора–Бендиксона, адаптированными для семейств теорий, определяют меру сложности заданного семейства. Аппроксимации позволяют выражать теории в виде предельных переходов относительно данного семейства, а генерические предложения указывают, какая информация является самой объемлющей при описании подсемейств данного семейства. Ранги и аппроксимации для различных семейств теорий изучались в работах [9]–[12]. В недавней работе [13] изучались свойства рангов для семейств сильно минимальных теорий. Настоящая работа состоит из четырех пунктов, первые три из которых содержат основные результаты. В п. 1 описываются значения рангов для различных семейств упорядоченных теорий в зависимости от рассматриваемых сигнатур, а также дается описание $\mathrm{e}$-тотальной трансцендентности в терминах этих сигнатур. Это позволяет отслеживать количество точек накопления при аппроксимациях теорий из замыканий данных семейств. В п. 2 исследованы аппроксимации упорядоченных теорий, включая аппроксимации конечными и счетно категоричными порядками. В п. 3 исследованы замыкания и описаны ранги для семейств упорядоченных теорий, включая семейства о-минимальных и слабо о-минимальных теорий различных сигнатур, а также теорий чистых линейных порядков с различными ограничениями на дискретные части. 2. Ранги семейств теорий линейных порядковПусть $\mathcal{T}$ – семейство полных теорий фиксированной сигнатуры $\Sigma$, $\phi$ – произвольное $\Sigma$-предложение. Тогда множество $\mathcal{T}_{\phi}:=\{T\in\mathcal{T}\mid T\models \phi\}$ называется $\phi$-окрестностью семейства $\mathcal{T}$, или $\mathrm{s}$-определимым подсемейством семейства $\mathcal{T}$, задаваемым предложением $\phi$. Определение 1 [5]. Пусть $\mathcal{T}$ – семейство полных теорий фиксированной сигнатуры $\Sigma$. Определим ранг $\operatorname{RS}$ для семейства теорий следующим образом: Мы полагаем $\operatorname{RS}(\mathcal{T})=\alpha$, если $\operatorname{RS}(\mathcal{T})\geqslant\alpha$ и $\neg[\operatorname{RS}(\mathcal{T})\geqslant\alpha+1]$. Если $\operatorname{RS}(\mathcal{T})\geqslant\alpha$ для любого $\alpha$, то мы полагаем $\operatorname{RS}(\mathcal{T})=\infty$. Семейство $\mathcal{T}$ называется $\mathrm{e}$-тотально трансцендентным или тотально трансцендентным, если $\operatorname{RS}(\mathcal{T})$ является ординалом. Если семейство $\mathcal{T}$ $\mathrm{e}$-тотально трансцендентно, с $\operatorname{RS}(\mathcal{T})=\alpha\geqslant 0$, то в качестве степени $\operatorname{ds}(\mathcal{T})$ семейства $\mathcal{T}$ рассматривается максимальное число попарно несовместных предложений $\phi_i$, для которых $\operatorname{RS}(\mathcal{T}_{\varphi_i})=\alpha$. По определению если $\operatorname{RS}(\mathcal{T})=\alpha\in\mathrm{Ord}$, то $\operatorname{ds}(\mathcal{T})\in\omega\setminus\{0\}$. Замечание 1. Сокращение $\operatorname{RS}$ образуется от двух слов rank и sentence, поскольку в определении данного ранга используются исключительно предложения (формулы без свободных переменных). Замечание 2. Функция ранга $\operatorname{RS}$ обладает следующим свойством монотонности: если $\mathcal{T}_1$ и $\mathcal{T}_2$ – два семейства полных теорий и $\mathcal{T}_1\subset\mathcal{T}_2$, то $\operatorname{RS}(\mathcal{T}_1)\leqslant\operatorname{RS}(\mathcal{T}_2)$. Напомним, что теория $T$ называется счетно категоричной или $\aleph_0$-категоричной, если $T$ имеет единственную счетную модель, с точностью до изоморфизма. Лемма 1. Пусть $\mathcal{T}$ – семейство полных теорий чистого линейного порядка, т.е. теорий линейного порядка в сигнатуре $\Sigma=\{<\}$. Тогда для любой счетно категоричной теории $T\in\mathcal{T}$ существует $\Sigma$-предложение $\phi$ такое, что $\mathcal{T}_{\phi}=\{T\}$, т.е. $\operatorname{RS}(\mathcal{T}_{\phi})=0$ и $\operatorname{ds}(\mathcal{T}_{\phi})=1$. Доказательство леммы 1 вытекает из конечной аксиоматизируемости счетно категоричных линейных порядков [14], которые описываются предложениями, задающими плотные перемежания максимальных конечных дискретных частей, а также наличие/отсутствие наименьшего и (или) наибольшего элементов. Пример 1. Пусть $\mathcal{T}$ – семейство полных теорий чистого линейного порядка. Рассмотрим следующее предложение: Мы утверждаем, что $\operatorname{RS}(\mathcal{T}_{\phi_0})=0$ и $\operatorname{ds}(\mathcal{T}_{\phi_0})=5$. Действительно, рассмотрим следующие предложения:
$$
\begin{equation*}
\phi_{\geqslant 2}:=\exists\, x\,\exists\, y \ [x<y],
\end{equation*}
\notag
$$
т.е. $\phi_{\geqslant 2}$ означает, что существует не менее двух, а значит, бесконечно много линейно упорядоченных элементов;
$$
\begin{equation*}
\phi_{[,)}:=\exists\, x \,\forall\, y [x\leqslant y] \wedge \forall\, x\,\exists\, y[x<y],
\end{equation*}
\notag
$$
т.е. $\phi_{[,)}$ означает, что существует наименьший элемент и не существует наибольшего элемента;
$$
\begin{equation*}
\phi_{(,]}:=\exists\, x\,\forall\, y\ [x\geqslant y]\wedge \forall\, x\,\exists\, y\ [y<x],
\end{equation*}
\notag
$$
т.е. $\phi_{(,]}$ означает, что существует наибольший элемент и не существует наименьшего элемента;
$$
\begin{equation*}
\phi_{[,]}:=\exists\, x \,\forall\, y \ [x\leqslant y] \wedge \exists\, x\,\forall\, y\ [x\geqslant y],
\end{equation*}
\notag
$$
т.е. $\phi_{[,]}$ означает, что существуют наименьший и наибольший элементы;
$$
\begin{equation*}
\phi_{(,)}:=\forall\, x \,\exists\, y \ [x< y] \wedge \forall\, x\,\exists\, y\ [y<x],
\end{equation*}
\notag
$$
т.е. $\phi_{(,)}$ означает, что не существует ни наименьшего, ни наибольшего элементов. Очевидно, что предложения $\phi_{[,)}$, $\phi_{(,]}$, $\phi_{[,]}$, $\phi_{(,)}$ попарно несовместны, и в предположении $\phi_0\wedge\phi_{\geqslant 2}$ выполняется в точности одно из них, при этом $\operatorname{RS}(\mathcal{T}_{\phi_0\wedge\neg\phi_{\geqslant 2}})=0$, $\operatorname{ds}(\mathcal{T}_{\phi_0\wedge\neg\phi_{\geqslant 2}})=1$, а также $\operatorname{RS}(\mathcal{T}_{\phi_0\wedge\phi_{\geqslant 2}\wedge\phi_{[,)}})=0$ и $\operatorname{ds}(\mathcal{T}_{\phi_0\wedge\phi_{\geqslant 2}\wedge\phi_{[,)}})=1$ (аналогично для остальных случаев). Если $\langle M_1, <_1\rangle$ и $\langle M_2, <_2\rangle$ – линейные порядки, то их конкатенация, обозначаемая через $M_1+M_2$, есть линейный порядок $\langle M_1\cup M_2, <\rangle$, где
$$
\begin{equation*}
a<b \quad\ \Longleftrightarrow\quad\ [a, b\in M_1\wedge a<_1 b] \quad\text{или}\ \ [a, b\in M_2\wedge a<_2 b] \quad\text{или}\ \ [a\in M_1\wedge b\in M_2].
\end{equation*}
\notag
$$
Вспомним также, что $\omega$ обозначает упорядочение множества натуральных чисел, $\omega^*$ – обратный порядок на множестве натуральных чисел и $\mathbb{Q}$ – упорядочение множества рациональных чисел. Пример 2. Пусть $\mathcal{T}$ – семейство полных теорий чистого линейного порядка. Рассмотрим следующие формулы: Пусть
$$
\begin{equation*}
\begin{aligned} \, \phi_1 &:=\exists\, x\,\exists\, v \ \bigl(L(x)\wedge S(x,v)\bigr)\wedge \exists\,y \ \neg\theta(y)\wedge C_{\theta}\wedge \forall\, z \ \neg G(z) \\ &\qquad \wedge\forall\, u\ \bigl[\neg L(u)\wedge \theta(u)\to \exists\, t\ S(t,u)\bigr]\wedge \exists\,^{\leqslant 2}v\ \bigl[\theta(v)\wedge\neg\exists\, w \ S(v,w)\bigr]. \end{aligned}
\end{equation*}
\notag
$$
Можно понять, что $\mathcal{T}_{\phi_1}$ – семейство полных теорий чистого линейного порядка с наименьшим элементом и без наибольшего элемента, состоящих из двух непустых выпуклых частей, левая часть которого дискретно упорядочена, а правая часть является плотно упорядоченной. Причем в дискретно упорядоченной части каждый элемент, отличный от наименьшего, имеет непосредственного предшественника, и в этой части имеется не более двух элементов, не имеющих непосредственных последователей. Таким образом, семейство $\mathcal{T}_{\phi_1}$ включает в точности счетное количество теорий следующих структур:
$$
\begin{equation*}
\begin{gathered} \, n +\mathbb{Q}, \qquad n+\omega^*+\mathbb{Q}, \qquad n+\omega^*+\omega+\mathbb{Q}, \qquad n+\omega^*+\omega+1+\mathbb{Q}, \\ n+\omega^*+\omega^*+\omega+\mathbb{Q}, \qquad n+\omega^*+\omega^*+\omega+1+\mathbb{Q}, \qquad n\geqslant 2; \\ \omega+\mathbb{Q}, \qquad \omega +1+\mathbb{Q}, \qquad \omega+\omega^*+\mathbb{Q}, \qquad \omega+\omega^*+\omega^*+\mathbb{Q}, \\ \omega+\omega^*+\omega^*+\omega+\mathbb{Q}, \qquad \omega+\omega^*+\omega^*+\omega+1+\mathbb{Q}, \\ \omega+\omega^*+\omega^*+\omega^*+\omega+\mathbb{Q}, \qquad \omega+\omega^*+\omega^*+\omega^*+\omega+1+\mathbb{Q}. \end{gathered}
\end{equation*}
\notag
$$
Тогда утверждаем, что $\operatorname{RS}(\mathcal{T}_{\phi_1})=1$ и $\operatorname{ds}(\mathcal{T}_{\phi_1})=6$. Действительно, поскольку семейство $\mathcal{T}_{\phi_1}$ бесконечно, то очевидно, что $\operatorname{RS}(\mathcal{T}_{\phi_1})\geqslant 1$. Поймем, что $\operatorname{RS}(\mathcal{T}_{\phi_1})= 1$. Рассмотрим следующие предложения:
$$
\begin{equation*}
\mathrm{Dis}_n:=\exists\, x\,\exists\, y_1 \dots y_{n-1} \ \biggl[L(x)\wedge S(x,y_1)\wedge \bigwedge_{i=1}^{n-2} S(y_i, y_{i+1})\wedge \neg \exists\, t \ S(y_{n-1}, t)\biggr],
\end{equation*}
\notag
$$
где $n\geqslant 2$, т.е. $\mathrm{Dis}_n$ утверждает, что существует конечный дискретный порядок, состоящий в точности из $n$ элементов (где начальным элементом такого порядка является наименьший элемент рассматриваемой структуры);
$$
\begin{equation*}
\mathrm{Dis}_{\omega}:=\forall\, t\ \bigl[\neg \theta(t)\to \forall\, y\ \bigl(y<t \wedge \theta(y)\to \exists\, z\ S(y,z)\bigr)\bigr],
\end{equation*}
\notag
$$
т.е. $\mathrm{Dis}_{\omega}$ утверждает, что дискретно упорядоченная часть образует порядок, элементарно эквивалентный порядку $\omega$ (с учетом того, что в $\mathcal{T}_{\phi_1}$ входят теории с аксиомой существования наименьшего элемента);
$$
\begin{equation*}
\mathrm{Dis}_G:=\exists\, t \ \bigl[\theta(t)\wedge \forall\, y\ (t<y\to \neg \theta(y))\bigr],
\end{equation*}
\notag
$$
т.е. дискретно упорядоченная часть имеет наибольший элемент;
$$
\begin{equation*}
\mathrm{Den}_L:=\exists\, t\ \bigl[\neg \theta(t)\wedge \forall\, y\ (y<t\to \theta(y))\bigr],
\end{equation*}
\notag
$$
т.е. плотно упорядоченная часть имеет наименьший элемент. Замечаем, что $\operatorname{RS}(\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_n})=0$ и $\operatorname{ds}(\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_n})=6$ для каждого $n\geqslant 2$, поскольку $\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_n}$ состоит из теорий следующих шести структур:
$$
\begin{equation*}
\begin{gathered} \, n+\mathbb{Q}, \qquad n+\omega^*+\mathbb{Q}, \qquad n+\omega^*+\omega+\mathbb{Q}, \qquad n+\omega^*+\omega+1+\mathbb{Q}, \\ n+\omega^*+\omega^*+\omega+\mathbb{Q}, \qquad n+\omega^*+\omega^*+\omega+1+\mathbb{Q}. \end{gathered}
\end{equation*}
\notag
$$
Таким образом, получаем, что $\operatorname{RS}(\mathcal{T}_{\phi_1})\geqslant 1$ и $\operatorname{ds}(\mathcal{T}_{\phi_1})\geqslant 6$. Также замечаем, что $\operatorname{RS}(\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_{\omega}})=0$ и $\operatorname{ds}(\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_{\omega}})=2$, поскольку $\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_{\omega}}$ состоит из теорий структур $\omega+\mathbb{Q}$ и $\omega+1+\mathbb{Q}$. Далее, $\operatorname{RS}(\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_G})\geqslant 1$, поскольку семейство $\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_G}$ бесконечно и состоит из теорий следующих структур:
$$
\begin{equation*}
n +\mathbb{Q}, \qquad n+\omega^*+\mathbb{Q}, \qquad n\geqslant 2; \qquad \omega+\omega^*+\mathbb{Q}, \qquad \omega+\omega^*+\omega^*+\mathbb{Q}.
\end{equation*}
\notag
$$
При этом для каждого $n\geqslant 2$ мы имеем, что
$$
\begin{equation*}
\operatorname{RS}(\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_G\wedge \mathrm{Dis}_n})=0, \qquad \operatorname{ds}(\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_G\wedge \mathrm{Dis}_n})=2,
\end{equation*}
\notag
$$
поскольку данное семейство состоит из теорий следующих двух структур: $n +\mathbb{Q}$ и $n+\omega^*+\mathbb{Q}$. Откуда заключаем, что $\operatorname{RS}(\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_G})=1$. Аналогично показывается, что $\operatorname{RS}(\mathcal{T}_{\phi_1\wedge \mathrm{Den}_L})=1$ и $\operatorname{RS}(\mathcal{T}_{\phi_1\wedge \neg \mathrm{Dis}_G\wedge \neg \mathrm{Den}_L})=1$. Также можно заметить, что не существует теории в семействе $\mathcal{T}_{\phi_1}$, для которой выполняются одновременно $\mathrm{Dis}_G$ и $\mathrm{Den}_L$. Поскольку семейства $\mathcal{T}_{\phi_1\wedge \mathrm{Dis}_G}$, $\mathcal{T}_{\phi_1\wedge \mathrm{Den}_L}$ и $\mathcal{T}_{\phi_1\wedge \neg \mathrm{Dis}_G\wedge \neg \mathrm{Den}_L}$ попарно не пересекаются и в объединении образуют $\mathcal{T}_{\phi_1}$, то заключаем, что $\operatorname{RS}(\mathcal{T}_{\phi_1})=1$ и $\operatorname{ds}(\mathcal{T}_{\phi_1})=6$. Пример 3. Пусть $\mathcal{T}$ – семейство полных теорий чистого линейного порядка. Будем предполагать, что множество реализаций формулы $\theta(x)$ состоит в точности из двух выпуклых множеств. Рассмотрим следующие формулы: Пусть
$$
\begin{equation*}
\begin{aligned} \, \phi_2 &:=C^2_{\theta}\wedge \exists\, x_1 \,\exists\, v_1 \ \bigl[L(x_1)\wedge S(x_1, v_1)\bigr]\wedge \exists\, y_1 \ \bigl[\neg \theta_1(y_1)\wedge \forall\, w \ (\theta_2(w)\to y_1<w)\bigr] \\ &\qquad\wedge \exists\, x_2\,\exists\, v_2 \ \bigl[L_2(x_2)\wedge S(x_2, v_2)\bigr] \wedge \exists\, y_2 \ \bigl[\neg \theta_1(y_2)\wedge \forall\, w \ (\theta_2(w)\to w<y_2)\bigr] \\ &\qquad\wedge \forall\, t \ \bigl[\neg L_2(t)\wedge \theta_2(t)\to \exists\, u \ S(u,t)\bigr]\wedge \forall\, z \ \neg G(z) \\ &\qquad\wedge \exists\,^{\leqslant 2}v_1\ \bigl[\theta_1(v_1)\wedge\neg\exists\, w_1 \ S(v_1,w_1)\bigr] \wedge\exists\,^{\leqslant 2}v_2\ \bigl[\theta_2(v_2)\wedge\neg\exists\, w_2 \ S(v_2,w_2)\bigr], \end{aligned}
\end{equation*}
\notag
$$
где $L(x), S(x,y), G(z)$ – формулы из предыдущего примера. Можно понять, что $\mathcal{T}_{\phi_2}$ – семейство полных теорий чистого линейного порядка с наименьшим элементом и без наибольшего элемента, состоящих из четырех непустых выпуклых частей, первая (левая) и третья части которого дискретно упорядочены, а вторая и четвертая (правая) части плотно упорядочены. Причем в каждой дискретно упорядоченной части имеется наименьший элемент, и каждый элемент, отличный от наименьшего, имеет непосредственного предшественника. Таким образом, семейство $\mathcal{T}_{\phi_2}$ состоит в точности из теорий линейных порядков следующего вида: $\mathrm{Discrete}_1+\mathbb{Q}+\mathrm{Discrete}_2+\mathbb{Q}$, где каждая $\mathrm{Discrete}_i$, $i\in\{1,2\}$, есть один из следующих дискретных порядков:
$$
\begin{equation}
\begin{gathered} \, n, \qquad n+\omega^*, \qquad n+\omega^*+\omega, \qquad n+\omega^*+\omega+1, \\ n+\omega^*+\omega^*+\omega, \qquad n+\omega^*+\omega^*+\omega+1, \qquad\text{где}\quad n\geqslant 2; \\ \omega, \qquad \omega +1, \qquad\omega+\omega^*, \qquad \omega+\omega^*+\omega^*, \qquad\omega+\omega^*+\omega^*+\omega, \\ \omega+\omega^*+\omega^*+\omega+1, \qquad \omega+\omega^*+\omega^*+\omega^*+\omega, \qquad \omega+\omega^*+\omega^*+\omega^*+\omega+1. \end{gathered}
\end{equation}
\tag{2.1}
$$
По аналогии с примером 2 может быть установлено, что $\operatorname{RS}(\mathcal{T}_{\phi_2})=2$ и $\operatorname{ds}(\mathcal{T}_{\phi_2})=6^2=36$. Пример 4. Пусть $\mathcal{T}$ – семейство полных теорий чистого линейного порядка. Будем предполагать, что множество реализаций формулы $\theta(x)$ состоит в точности из $m$ выпуклых множеств ($m\geqslant 2$). По аналогии с примером 3 конструируем следующие формулы:
Далее, также конструируем предложение $\phi_m$ таким образом, чтобы $\mathcal{T}_{\phi_m}$ являлось семейством полных теорий чистого линейного порядка с наименьшим элементом и без наибольшего элемента, состоящих из $2m$ непустых выпуклых частей, первая (левая) и остальные нечетные части которого дискретно упорядочены, а все четные части – плотно упорядочены. Причем в каждой дискретно упорядоченной части имеется наименьший элемент, и каждый элемент, отличный от наименьшего, имеет непосредственного предшественника. Таким образом, семейство $\mathcal{T}_{\phi_m}$ состоит в точности из теорий следующего вида:
$$
\begin{equation*}
\mathrm{Discrete}_1+\mathbb{Q}+\mathrm{Discrete}_2+\mathbb{Q}+\dots +\mathrm{Discrete}_m+\mathbb{Q},
\end{equation*}
\notag
$$
где каждая $\mathrm{Discrete}_i$, $i\in\{1,2, \dots, m\}$, есть один из дискретных порядков вида (2.1). По аналогии с примерами 2 и 3 может быть установлено, что $\operatorname{RS}(\mathcal{T}_{\phi_m})=m$ и $\operatorname{ds}(\mathcal{T}_{\phi_m})=6^m$. Пример 5. Пусть $\mathcal{T}$ – семейство полных теорий чистого линейного порядка. Будем предполагать, что множество реализаций формулы $\theta(x)$ состоит в точности из $m+1$ выпуклых множеств ($m\geqslant 1$). По аналогии с предыдущим примером конструируем предложение $\psi^n_m$, где $n\in\omega\setminus\{0\}$, таким образом, чтобы $\mathcal{T}_{\psi_m}$ являлось семейством полных теорий чистого линейного порядка с наименьшим и наибольшим элементами, состоящего из $2m+1$ непустых выпуклых частей, первая (левая) и остальные нечетные части которого дискретно упорядочены, а все четные части плотно упорядочены. Причем в каждой дискретно упорядоченной части имеется как наименьший, так и наибольший элементы, а каждый элемент, отличный от наименьшего или наибольшего, имеет как непосредственного предшественника, так и непосредственного последователя. Кроме того, потребуем, чтобы последняя дискретная часть состояла не менее чем из двух и не более чем из $n+1$ элементов. Таким образом, семейство $\mathcal{T}_{\psi^n_m}$ состоит в точности из теорий следующего вида:
$$
\begin{equation*}
\mathrm{Discrete}_1+\mathbb{Q}+\mathrm{Discrete}_2+\mathbb{Q}+\dots +\mathrm{Discrete}_m+\mathbb{Q}+\mathrm{Discrete}_{m+1},
\end{equation*}
\notag
$$
где $\mathrm{Discrete}_i$ для каждого $1\leqslant i\leqslant m$ есть конечный дискретный порядок, состоящий из $k$ элементов, где $k\geqslant 2$, или $\omega+\omega^*$, а $\mathrm{Discrete}_{m+1}$ есть дискретный порядок, состоящий из $l$ элементов, где $2\leqslant l\leqslant n+1$. По аналогии с предыдущими примерами можно установить, что $\operatorname{RS}(\mathcal{T}_{\psi^n_m})=m$. Заметим, что $\operatorname{ds}(\mathcal{T}_{\psi^n_m})$ зависит от $\mathrm{Discrete}_{m+1}$: действительно, если $\mathrm{Discrete}_{m+1}$ есть дискретный порядок, состоящий из двух элементов, то $\operatorname{ds}(\mathcal{T}_{\psi^n_m})=1$; если же $\mathrm{Discrete}_{m+1}$ есть дискретный порядок, состоящий из двух или трех элементов, то $\operatorname{ds}(\mathcal{T}_{\psi^n_m})=2$. Таким образом, если $\mathrm{Discrete}_{m+1}$ есть дискретный порядок, состоящий из $l$ элементов, где $2\leqslant l\leqslant n+1$, то $\operatorname{ds}(\mathcal{T}_{\psi^n_m})=n$. Таким образом, мы установили следующую теорему. Теорема 1. Пусть $\mathcal{T}$ – семейство полных теорий чистого линейного порядка. Тогда для любых $m,n<\omega$ с условием $n\geqslant 1$ существует предложение $\phi$ такое, что $\operatorname{RS}(\mathcal{T}_{\phi})=m$, $\operatorname{ds}(\mathcal{T}_{\phi})=n$. 3. Аппроксимации упорядоченных теорийОпределение 2 [6]. Пусть $\mathcal{T}$ – семейство теорий и $T$ – произвольная теория, не принадлежащая $\mathcal{T}$. Теория $T$ называется $\mathcal{T}$-аппроксимируемой или аппроксимированной семейством $\mathcal{T}$, или псевдо-$\mathcal{T}$-теорией, если для любой формулы $\varphi\in T$ существует $T'\in\mathcal{T}$, для которой $\varphi\in T'$. Если теория $T$ является $\mathcal{T}$-аппроксимируемой, то $\mathcal{T}$ называется аппроксимирующим семейством для $T$, а теории $T'\in\mathcal{T}$ – аппроксимациями для $T$. Частными случаями определения $\mathcal{T}$-аппроксимируемости являются следующие определения. Определение 3 [15], [16]–[18]. Бесконечная структура $\mathcal{M}$ называется псевдоконечной, если любое предложение, истинное в $\mathcal{M}$, имеет конечную модель. Если $T=\operatorname{Th}(\mathcal{M})$ для псевдоконечной структуры $\mathcal{M}$, то теория $T$ также называется псевдоконечной. Определение 4. Элементарная теория $T$ бесконечной структуры $\mathcal{M}$, не являющейся $\aleph_0$-категоричной, называется псевдо-$\aleph_0$-категоричной или псевдо-счетно-категоричной, если любое предложение, истинное в $\mathcal{M}$, имеет $\aleph_0$-категоричную модель $\mathcal{N}$. При этом модели $\mathcal{N}$ называются аппроксимациями модели $\mathcal{M}$, а сама модель $\mathcal{M}$ называется псевдо-$\aleph_0$-категоричной. Пример 6. Рассмотрим структуру Напомним представленную в работе [16] характеризацию псевдоконечности бесконечных линейных порядков и снабдим ее доказательством, опирающимся не на ультрапроизведения, а на аппроксимации структур и их теорий [6]: Теорема 2. Пусть $T$ – полная теория бесконечного линейного порядка. Тогда следующие условия эквивалентны: Доказательство. (1) $\Longleftrightarrow$ (2). Пусть $T$ – псевдоконечная теория. Покажем вначале, что в теории $T$ совместно следующее предложение: $LE:=\exists\, x\,\forall\, y \ [x\leqslant y]$. Действительно, если это не так, то совместно $\neg LE$, которое не имеет конечной модели. Аналогично показывается, что в теории $T$ совместно следующее предложение:
Покажем теперь, что наименьший элемент имеет непосредственного последователя
$$
\begin{equation*}
\Phi:=\exists\, x \ [L(x)\wedge \exists\, y \ S(x,y)],
\end{equation*}
\notag
$$
где $L(x)$ означает, что $x$ – наименьший элемент, а $S(x,y)$ означает, что $y$ является непосредственным последователем элемента $x$. Если это не так, то совместно $\neg \Phi$, которое не имеет конечной модели. Аналогично показывается, что наибольший элемент имеет непосредственного предшественника.
Далее убеждаемся, что совместно следующее предложение:
$$
\begin{equation*}
\exists\, x\,\exists\, y \ \bigl[L(x)\wedge G(y)\wedge x<y\bigr],
\end{equation*}
\notag
$$
где $G(y)$ означает, что $y$ – наибольший элемент. Если это не так, то $T$ – теория конечной линейно упорядоченной структуры, состоящей из одного элемента.
Покажем теперь, что в теории $T$ совместно следующее предложение:
$$
\begin{equation*}
\forall\, x \ \bigl[\neg L(x)\to \exists\, y \ S(y,x)\bigr].
\end{equation*}
\notag
$$
Если это не так, то совместно его отрицание, которое не имеет конечной модели. Аналогично показывается, что любой немаксимальный элемент имеет непосредственного последователя. Пусть
$$
\begin{equation*}
\begin{aligned} \, P&:=\exists\, x\,\exists\, y \ \bigl[x<y\wedge L(x)\wedge G(y)\wedge \forall\, t\ (\neg L(t)\to \exists\, t_1 \ S(t_1, t)) \\ &\qquad\qquad\wedge\forall\, z\ (\neg G(z)\to \exists\, z_1 \ S(z,z_1))\bigr], \\ \phi_n&:=P\wedge \exists\, x_1\dots \exists\, x_n \ \bigwedge^{n-1}_{i=1} S(x_i, x_{i+1}). \end{aligned}
\end{equation*}
\notag
$$
Пусть
$$
\begin{equation*}
T_0:=\{\phi_n\mid n\geqslant 2\}\cup \{\text{аксиомы линейного порядка}\}.
\end{equation*}
\notag
$$
Покажем, что $T_0$ задает полную теорию. Рассмотрим следующие формулы:
$$
\begin{equation*}
\theta_n:=\exists\, x_1 \dots \exists\, x_n \ \bigwedge_{i\ne j} x_i\ne x_j, \qquad n\geqslant 2.
\end{equation*}
\notag
$$
Ясно, что $T_0\vdash \theta_n$ для каждого $n\geqslant 2$. Таким образом, любая модель для $T_0$ является бесконечной. Кроме того, существуют наименьший и наибольший элементы, любой элемент, не являющийся наименьшим, имеет непосредственного предшественника, а любой элемент, не являющийся наибольшим, имеет непосредственного последователя. Тем самым, каждая модель для $T_0$ имеет начальный порядок $\omega$, заключительный порядок $\omega^\ast$ и некоторое, возможно нулевое, количество конкатенаций с промежуточными копиями порядка $\omega^\ast+\omega$. При этом количество и взаимосвязь промежуточных копий не определяется средствами сигнатуры линейных порядков. Откуда заключаем, что любые две модели для $T_0$ элементарно эквивалентны, и, следовательно, $T_0$ однозначно расширяется до полной теории. Учитывая, что $T_0\subseteq \operatorname{Th}(\langle \omega+\omega^*, <\rangle)$, получаем $T=\operatorname{Th}(\langle \omega+\omega^*, <\rangle)$. Обратно, из задания теории $T=\operatorname{Th}(\langle \omega+\omega^*, <\rangle)$ множеством $T_0$, состоящим из предложений, имеющих конечные модели, следует псевдоконечность теории $T$. Для доказательства $(2)\ \Longleftrightarrow\ (3)$ заметим, что структуры $\langle\omega+\omega^\ast, <\rangle$ и $\langle\omega+\sum_{i\in I}(\omega^\ast+\omega)_i+\omega^\ast, <\rangle$ элементарно эквивалентны, поскольку описываются условиями бесконечности и дискретности порядка, а также условиями наличия непосредственного предшественника у каждого неминимального элемента и наличия непосредственного последователя у каждого немаксимального элемента. Далее вспомним, что счетно категоричные линейные порядки были классифицированы Розенштейном в [14], где он конструировал их из конечных линейных порядков, используя две операции: конкатенацию и $\mathbb{Q}$-перемешивание. Рассмотрим линейно упорядоченную структуру $\mathbb{Q}_n:=\langle \mathbb{Q}_n, <_{\mathbb{Q}_n}, C^1_1, \dots, C^1_n\rangle$, являющуюся счетным плотным линейным порядком с взаимно плотными $n$ цветами, т.е. для любых $a, b\in \mathbb{Q}_n$ с условием $a<b$ существуют $c_1, \dots, c_n$ такие, что $a<c_i<b\wedge C_i(c_i)$ для каждого $1\leqslant i\leqslant n$. Такая структура называется Фраиссе генерическим $n$-цветным линейным порядком. Пусть $\langle M_1, <_1\rangle, \dots, \langle M_n, <_n\rangle$ – линейные порядки. Для каждого $q\in \mathbb{Q}_n$ обозначаем через $M(q)$ копию линейного порядка $\langle M_i, <_i\rangle$, если $\mathbb{Q}_n\models C_i(q)$. $\mathbb{Q}_n$-Перемешиванием (или просто $\mathbb{Q}$-перемешиванием) порядков $\langle M_1, <_1\rangle, \dots, \langle M_n, <_n\rangle$, обозначаем через $\mathbb{Q}_n(M_1, \dots, M_n)$, является линейный порядок $\langle \bigcup_{q\in \mathbb{Q}_n}M(q), <\rangle$, где
$$
\begin{equation*}
\begin{aligned} \, &a<b \quad\Longleftrightarrow \quad \bigl[a,b\in M(q),\, M(q)\simeq M_i \text{ для некоторого } 1\leqslant i\leqslant n \text{ и } a<_i b\bigr] \\ &\qquad \text{ или } \bigl[a\in M(q), \,b\in M(p)\wedge q<_{\mathbb{Q}_n} p\bigr]. \end{aligned}
\end{equation*}
\notag
$$
Например, $\mathbb{Q}_1(1)$ – это копия множества всех рациональных чисел $\mathbb{Q}$; $\mathbb{Q}_1(2)$ – это множество дуплетов, упорядоченное по типу $\mathbb{Q}$; $\mathbb{Q}_2(2, 3)$ – это взаимно плотно упорядоченное множество дуплетов и троек. Теорема 3 [14]. Порядок $\mathcal{M}$ – счетно категоричный линейный порядок тогда и только тогда, когда $\mathcal{M}$ может быть построен из синглетонов (изолированных точек) с помощью конечного числа конкатенаций и $\mathbb{Q}$-перемешиваний. Пример 7. Бесконечный линейный порядок $\mathcal{M}:=\langle \omega+\omega^*+\mathbb{Q},<\rangle$ не является $\aleph_0$-категоричным, поскольку имеет бесконечно много типов, задаваемых псевдоконечным начальным отрезком $\omega+\omega^*$. Нетрудно установить, что теория данного порядка является псевдо-$\aleph_0$-категоричной, так как аппроксимируется $\aleph_0$-категоричными теориями $T_n=\operatorname{Th}(\langle n+\mathbb{Q},<\rangle)$, $n<\omega$. При этом теории $T_n$ конечно аксиоматизируемы, и тем самым, не являются аппроксимируемыми. Аналогично можно рассмотреть конечные суммы (конкатенации) псевдоконечных и бесконечных счетно категоричных линейных порядков, такие как
$$
\begin{equation*}
\omega+\omega^*+\mathbb{Q}+n+\mathbb{Q}, \qquad \mathbb{Q}_2(\mathbb{Q}_1(1),2)+\omega+\omega^*+\mathbb{Q}+\omega+\omega^* \qquad\text{ и т.д.},
\end{equation*}
\notag
$$
в которых хотя бы одно из слагаемых является псевдоконечным, и убедиться, что такая сумма является псевдо-$\aleph_0$-категоричным не $\aleph_0$-категоричным линейным порядком. Таким образом, нами установлено следующее предложение. Предложение 1. Пусть $\mathcal{M}$ – конкатенация конечного числа псевдоконечных и бесконечных $\aleph_0$-категоричных линейных порядков. Тогда $\mathcal{M}$ – псевдо-$\aleph_0$-категоричный не $\aleph_0$-категоричный линейный порядок тогда и только тогда, когда хотя бы одно из слагаемых является псевдоконечным линейным порядком и хотя бы одно слагаемых является бесконечным $\aleph_0$-категоричным линейным порядком. Доказательство. ($\Longrightarrow$) Если среди слагаемых нет псевдоконечных линейных порядков, то $\mathcal{M}$ – бесконечный $\aleph_0$-категоричный линейный порядок. Если среди слагаемых нет бесконечных $\aleph_0$-категоричных линейных порядков, то $\mathcal{M}$ является псевдоконечным линейным порядком. В этом случае истинно следующее предложение:
Очевидно, что предложение $\Psi$ не имеет бесконечной $\aleph_0$-категоричной модели, откуда $\mathcal{M}$ не является псевдо-$\aleph_0$-категоричной. ($\Longleftarrow$) Не умаляя общности, предположим, что для некоторого $1\leqslant k<\omega$, где $P_i$ – псевдоконечный линейный порядок, а $C_i$ – бесконечный $\aleph_0$-категоричный линейный порядок для каждого $1\leqslant i\leqslant k$. Тогда $\operatorname{Th}(\mathcal{M})$ псевдо-$\aleph_0$-категорична, поскольку аппроксимируется $\aleph_0$-категоричными теориями где $n_1, n_2, \dots, n_k<\omega$.Рассмотрим теперь некоторые конкатенации счетного числа бесконечных $\aleph_0$-категоричных линейных порядков. Пример 8. Пусть $\mathcal{M}:=\langle 2+\mathbb{Q}+2+\mathbb{Q}+\dots, <\rangle$, и пусть формула $\phi^l_2(x)$ определяет элемент $x$ структуры $\mathcal{M}$, являющийся левой концевой точкой дуплета. Рассмотрим следующее предложение: Очевидно, что $\Phi_2$ не имеет бесконечной $\aleph_0$-категоричной модели, откуда $\operatorname{Th}(\mathcal{M})$ не является псевдо-$\aleph_0$-категоричной. Пример 9. Пусть теперь Очевидно, что $\operatorname{Th}(\mathcal{M})$ не является $\aleph_0$-категоричной, поскольку длина конечных порядков не ограничена. Тем не менее, мы утверждаем, что теория $\operatorname{Th}(\mathcal{M})$ является псевдо-$\aleph_0$-категоричной. Действительно, данный порядок аппроксимируется $\aleph_0$-категоричными линейными порядками $\mathbb{Q}_1(2)+\mathbb{Q}_1(3)+\dots+\mathbb{Q}_1(n)$, $n\geqslant 2$. Следующие предложения истинны в $\mathcal{M}$: не существует наименьшего элемента; не существует наибольшего элемента; любой элемент имеет непосредственного предшественника или непосредственного последователя; для каждого $n\geqslant 2$ существует элемент конечного порядка из $n$ элементов и так далее. Очевидно, что любая конечная комбинация этих предложений имеет бесконечную $\aleph_0$-категоричную модель. Замечание 3. Иллюстрация, данная в примере 9, показывает, что псевдо-$\aleph_0$-категоричность могут задавать неограниченные цепочки 4. Замыкания и ранги семейств упорядоченных теорийВ статье [19] определено и охарактеризовано понятие $\mathrm{E}$-замыкания $\operatorname{Cl}_{\mathrm E}(\mathcal{T})$ для семейства теорий $\mathcal{T}$, где $\mathcal{T}_\Sigma$ – множество всех полных теорий сигнатуры $\Sigma$: Предложение 2. Если $\mathcal{T}\subseteq\mathcal{T}_\Sigma$ – конечное множество, то $\operatorname{Cl}_{\mathrm E}(\mathcal{T})=\mathcal{T}$. Если $\mathcal{T}$ бесконечно и $T\in\mathcal{T}_\Sigma\setminus\mathcal{T}$, то $T\in\operatorname{Cl}_{\mathrm E}(\mathcal{T})$ (т.е. $T$ является точкой накопления для $\mathcal{T}$ относительно $\mathrm{E}$-замыкания $\operatorname{Cl}_{\mathrm E}$) тогда и только тогда, когда для любого предложения $\phi\in T$ $\mathrm{s}$-определимое семейство $\mathcal{T}_\phi$ бесконечно. Теорема 4 [5]. Для любого семейства $\mathcal{T}$ выполнено $\operatorname{RS}(\mathcal{T})=\operatorname{RS} (\operatorname{Cl}_{\mathrm E}(\mathcal{T}))$, и если семейство $\mathcal{T}$ непусто и $\mathrm{e}$-тотально трансцендентно, то $\operatorname{ds}(\mathcal{T})=\operatorname{ds}(\operatorname{Cl}_{\mathrm E}(\mathcal{T}))$. Следуя [20], через $\mathrm{e}$-$\operatorname{Sp}(\mathcal{T})$ обозначается $\mathrm{e}$-спектр семейства $\mathcal{T}$, задаваемый в виде супремума мощностей множеств $\operatorname{Cl}_{\mathrm E}(\mathcal{T})\setminus\mathcal{T}_0$, где $\mathcal{T}_0$ – подсемейства семейства $\operatorname{Cl}_{\mathrm E}(\mathcal{T})$, удовлетворяющие условию $\operatorname{Cl}_{\mathrm E}(\mathcal{T}_0)=\operatorname{Cl}_{\mathrm E}(\mathcal{T})$. Определение 5 (ср. [21]). Для семейства $\mathcal{T}\subseteq\mathcal{T}_\Sigma$ назовем $2$-деревом $\operatorname{Tree}(\mathcal{T})$ семейство $\{\mathcal{T}_{\phi_\delta}\mid\delta\in^{<\omega}2\}$ непустых $\mathrm{s}$-определимых множеств $\mathcal{T}_{\phi_\delta}$, для $\phi_\delta\in\operatorname{Sent}(\Sigma)$, удовлетворяющее следующим условиям: Множество $\{\phi_\delta\mid\delta\in^{<\omega}2\}$ также называется $2$-деревом для семейства $\mathcal{T}$. Теорема 5 [5], [8]. Для любого семейства теорий $\mathcal{T}$, удовлетворяющего неравенству $|\Sigma(\mathcal{T})|\leqslant\omega$, следующие условия эквивалентны: Определение 6 [22]. Если $\mathcal{T}$ – семейство теорий и $\Phi$ – множество предложений, то полагаем $\mathcal{T}_\Phi=\bigcap_{\varphi\in\Phi}\mathcal{T}_\varphi$ и множество $\mathcal{T}_\Phi$ называем (типово- или диаграммно-) определимым (посредством множества $\Phi$) относительно семейства $\mathcal{T}$, или (диаграммно-) $\mathcal{T}$-определимым, или просто $\mathrm{d}$-определимым. Отметим, что конечные объединения $\mathrm{d}$-определимых множеств снова являются $\mathrm{d}$-определимыми. Рассматривая бесконечные объединения $\mathcal{T}'$ $\mathrm{d}$-определимых множеств $\mathcal{T}_{\Phi_i}$, $i\in I$, мы можем представить их посредством формул с бесконечными дизъюнкциями $\bigvee_{i\in I}\varphi_i$, $\varphi_i\in\Phi_i$. Мы называем эти объединения $\mathcal{T}'$ $\mathrm{d}_\infty$-определимыми множествами. Теорема 6 [22]. Пусть $\mathcal{T}$ – семейство теорий счетной сигнатуры $\Sigma$ с условием $\operatorname{RS}(\mathcal{T})=\infty$, $\alpha$ – счетный ординал, $n\in\omega\setminus\{0\}$. Тогда существует $\mathrm{d}_\infty$-определимое подсемейство $\mathcal{T}^\ast\subset\mathcal{T}$, для которого $\operatorname{RS}(\mathcal{T}^\ast)=\alpha$ и $\operatorname{ds}(\mathcal{T}^\ast)=n$. Пусть $F$ – множество всех конечных линейных порядков и
$$
\begin{equation*}
G:=F\cup\{\omega, \omega^*, \omega+\omega^*, \omega^*+\omega, \mathbb{Q}\}.
\end{equation*}
\notag
$$
Также пусть $WO$ – множество всех упорядоченных сумм вида $C_1+\dots+C_m$, где $C_i$ элементарно эквивалентно некоторому элементу из $G$ для каждого $i\leqslant m$. Теорема 7 [23]. Любая слабо о-минимальная структура $\mathcal{M}$, ограниченная на сигнатуру $\{<\}$, является элементом множества $WO$, и обратно, теория первого порядка любого элемента из $WO$ является слабо о-минимальной теорией линейного порядка. Обозначим через $\mathcal{T}_{\mathrm{womlo}}$ и $\mathcal{T}^{\aleph_0}_{\mathrm{womlo}}$ семейство всех слабо о-минимальных теорий чистого линейного порядка и семейство всех счетно категоричных слабо о-минимальных теорий чистого линейного порядка соответственно. Следствие 1. Имеет место равенство $\operatorname{RS}(\mathcal{T}_{\mathrm{womlo}})=\operatorname{RS}(\mathcal{T}^{\aleph_0}_{\mathrm{womlo}})=\infty$. Доказательство. В силу теоремы 7 количество выпуклых дискретных и плотных частей должно быть конечно, но при этом их количество может быть сколь угодно большим для фиксированной слабо о-минимальной теории, в том числе и для счетно категоричной слабо о-минимальной теории. Следовательно, количество псевдо-$\mathcal{T}^{\aleph_0}_{\mathrm{womlo}}$-теорий континуально посредством бесконечных чередований различных дискретных и плотных частей. Тогда по теоремам 4 и 5 и включению $\mathcal{T}_{\mathrm{womlo}} \supseteq\mathcal{T}^{\aleph_0}_{\mathrm{womlo}}$ имеет место $\operatorname{RS}(\mathcal{T}_{\mathrm{womlo}})=\operatorname{RS}(\mathcal{T}^{\aleph_0}_{\mathrm{womlo}})=\infty$. Из теоремы 6 и следствия 1 непосредственно вытекает Следствие 2. Для любого счетного ординала $\alpha$ и натурального $n\in\omega\setminus\{0\}$ существует подсемейство $\mathcal{T}^\ast\subset\mathcal{T}_{\mathrm{womlo}}$, у которого $\operatorname{RS}(\mathcal{T}^\ast)=\alpha$ и $\operatorname{ds}(\mathcal{T}^\ast)=n$. Поскольку равенство $\operatorname{RS}(\mathcal{T})=\infty$ означает наличие $2$-дерева предложений [8], [9] и при обогащениях это $2$-дерево сохраняется, то произвольное обогащение семейства $\mathcal{T}$ до семейства $\mathcal{T}'$ сигнатуры $\Sigma\subseteq\Sigma(\mathcal{T})$ удовлетворяет условию $\operatorname{RS}(\mathcal{T}')=\infty$. Таким образом, в силу следствия 1 имеет место следующая теорема. Теорема 8. Для любой сигнатуры $\Sigma$, включающей символ отношения $<$ для линейного порядка, семейство $\mathcal{T}_{\mathrm{wom},\Sigma}$ всех слабо о-минимальных теорий сигнатуры $\Sigma$ не является $\mathrm{e}$-тотально трансцендентным: $\operatorname{RS}(\mathcal{T}_{\mathrm{wom},\Sigma})=\infty$. Обозначение 1. Пусть $\kappa, \gamma$ – элементы множества $\omega\cup\{\infty\}$, $\gamma\geqslant 2$. Обозначим через $\mathcal{T}_{\mathrm{lo}}(\kappa, {\leqslant}\gamma)$ ($\mathcal{T}_{\mathrm{lo}}({\leqslant}\kappa$, ${\leqslant}\gamma)$, $\mathcal{T}_{\mathrm{lo}}({\leqslant}\kappa$, ${<}\gamma)$) семейство всех теорий бесконечных чистых линейных порядков, имеющих в точности (не более) $\kappa$ максимальных выпуклых дискретных частей с длинами не меньше $2$ и не более (менее) $\gamma$ и не имеющих максимальных дискретных выпуклых частей большей мощности. Здесь мы считаем, что при $\kappa=\infty$ и $\gamma\in\omega$ имеется бесконечное (произвольное) количество максимальных выпуклых дискретных частей с длинами не меньше $2$ и не более (менее) $\gamma$, а если $\gamma=\infty$, то длины этих частей могут быть произвольными, начиная с $2$. При этом каждый внутренний элемент каждой максимальной выпуклой дискретной части имеет как непосредственного предшественника, так и непосредственного последователя. В частности, $\mathcal{T}_{\mathrm{lo}}(\kappa, {\leqslant}\gamma)$ включает теории, в которых $\kappa$ максимальных выпуклых дискретных частей чередуются с плотными частями. Например, элементарная теория структуры $\langle 2+\mathbb{Q}+3+\mathbb{Q}+4+\mathbb{Q}, <\rangle$ принадлежит семейству $\mathcal{T}_{\mathrm{lo}}(3, {\leqslant}4)$. Также мы используем следующие обозначения, имеющие аналогичный смысл где $v,w$ – какие-либо из символов $\leqslant$, $<$, $\geqslant$, $>$ или пустые слова. Более того, возникающие на $\omega\cup\{\infty\}$ произвольные подмножества $K$ и $G$ могут рассматриваться как области изменения параметров $\kappa$ и $\gamma$, которые задают подходящие семейства $\mathcal{T}_{\mathrm{lo}}(K,G)$ с этими областями.Отметим, что для бесконечных линейных порядков можно рассматривать случай $\mathcal{T}_{\mathrm{lo}}(\kappa, 1)$ как семейство теорий плотных линейных порядков, имеющее вид как $\mathcal{T}_{\mathrm{lo}}(\kappa, {\leqslant} 1)$, так и $\mathcal{T}_{\mathrm{lo}}({\leqslant}\kappa$, ${\leqslant} 1)$, и допустимое только при $\kappa=\infty$ с нестрогим неравенством $\leqslant 1$. Предложение 3. Для любого семейства $\mathcal{T}_{\mathrm{lo}}({\leqslant}\kappa, {\leqslant}\gamma)$, где $\kappa, \gamma\in\omega\cup\{\infty\}$, $\gamma\geqslant 2$, имеет место следующее: Доказательство. (1) По определению слабая о-минимальность теории $T$ означает представление любого определимого множества в виде конечного объединения определимых выпуклых множеств. Если $\kappa<\infty$, то количество максимальных дискретных выпуклых частей конечно и эти части могут перемежаться лишь друг с другом и с плотными частями, откуда вытекает слабая о-минимальность произвольной теории $T\in\mathcal{T}_{\mathrm{lo}}({\leqslant}\kappa, {\leqslant}\gamma)$. Если же $\kappa=\infty$, то допускается бесконечное количество максимальных дискретных выпуклых частей и из их конечности вытекает невозможность их совокупного представления в виде конечного объединения определимых выпуклых множеств, т.е. нарушается слабая о-минимальность некоторой теории $T\in\mathcal{T}_{\mathrm{lo}}({\leqslant}\kappa, {\leqslant}\gamma)$.
(2) Применяя описание слабо о-минимальных теорий из пункта (1), при $\kappa<\infty$ и $\gamma<\infty$ получаем представление определимых множеств произвольной теории $T\in\mathcal{T}_{\mathrm{lo}}({\leqslant}\kappa, {\leqslant}\gamma)$ в виде конечного объединения определимых выпуклых множеств, отделяемых границами дискретных частей, т.е. в виде конечного объединения интервалов. Это означает, что теория $T$ о-минимальна. Так как имеется лишь конечное число типов, описывающих попадание реализаций в дискретные или плотные части, теория $T$ счетно категорична. Из доказательства предложения 3 непосредственно вытекает Следствие 3. Для произвольного семейства $\mathcal{T}_{\mathrm{lo}}(K,G)$ имеют место следующие утверждения: Замечание 4. В силу предложения 3 конечные параметры $\kappa$ и $\gamma$ задают нетривиальную совокупность семейств $\mathcal{T}_{\mathrm{lo}}({\leqslant}\kappa, {\leqslant}\gamma)$ о-минимальных, счетно категоричных линейно упорядоченных теорий с условиями Предложение 4. 1) Для любых $m,n\in\omega$ с условием $n\geqslant 2$ имеет место 2) Для любого $m\in\omega\setminus\{0\}$ выполняется
$$
\begin{equation*}
\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(m, {<}\infty))=m, \qquad \operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(m, {\leqslant}\infty))=m, \qquad \operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(m,\infty))=0.
\end{equation*}
\notag
$$
3) Для любого $\gamma\in(\omega\setminus\{0,1\})\cup\{\infty\}$ имеет место $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(\infty,\gamma))=\infty$. Такое же соотношение выполняется после одновременной или некоторой замены символа $\infty$ на ${<}\infty$ или ${\leqslant}\infty$, и $\gamma$ на ${\leqslant}\gamma$, а также $\gamma$ на ${<}\gamma$ при $\gamma\geqslant 3$. Доказательство. 1) Рассмотрим следующую формулу:
Очевидно, $\phi(x)$ означает, что $x$ не имеет ни непосредственного предшественника, ни непосредственного последователя. Тогда $\theta(x):=\neg\phi(x)$ означает, что $x$ имеет непосредственного предшественника или непосредственного последователя. Рассмотрим следующие предложения:
$$
\begin{equation*}
\begin{gathered} \, \psi_1(x):=\exists\, x \ \theta(x), \\ \psi_m:=\exists\, x_1 \dots x_m \,\exists\, t_1 \dots t_{m-1} \ \biggl[\bigwedge_{i=1}^m x_i<t_i<x_{i+1} \wedge \bigwedge_{s=1}^m \theta(x_s)\wedge \bigwedge_{j=1}^{m-1} \phi(t_j)\biggr], \qquad m\geqslant 2. \end{gathered}
\end{equation*}
\notag
$$
Очевидно, что $\psi_m$ утверждает существование хотя бы $m$ максимальных выпуклых дискретных частей длины не менее 2. Следовательно, предложение
$$
\begin{equation*}
\psi_{\leqslant m}:=\bigvee_{i=1}^m \psi_i \wedge \neg \psi_{m+1}
\end{equation*}
\notag
$$
утверждает, что существует не более чем $m$ максимальных выпуклых дискретных частей.
Пусть формула $s(x,y)$ означает, что элемент $x$ – непосредственный предшественник элемента $y$. Рассмотрим следующее предложение:
$$
\begin{equation*}
\theta_k:=\exists\, x_1 \dots \,\exists\, x_k\ \biggl[\bigwedge_{i=1}^k \theta(x_i) \wedge \bigwedge_{j=1}^{k-1} s(x_j, x_{j+1})\biggr].
\end{equation*}
\notag
$$
Очевидно, что $\theta_k$ утверждает существование выпуклой дискретной части длины не менее $k$. Тогда для любых $m<\omega$ и $n<\omega$ мы имеем лишь конечное число полных теорий, лежащих в $\mathcal{T}_{\mathrm{lo}}({\leqslant}m, {\leqslant}n)$. Следовательно, $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}({\leqslant}m, {\leqslant}n))=0$. Тогда в силу включений $\mathcal{T}_{\mathrm{lo}}(m,n)\subseteq\mathcal{T}_{\mathrm{lo}}(m, {\leqslant}n)\subseteq\mathcal{T}_{\mathrm{lo}}({\leqslant}m, {\leqslant}n)$ и монотонности $\operatorname{RS}$-ранга выполняется также $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(m, {\leqslant}n))=\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(m, n))=0$. 2) Равенство $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(m, {<}\infty))=m$ вытекает из того, что для каждой из $m$ максимальных выпуклых дискретных частей, упорядоченных по возрастанию, имеется счетное число возможностей для длин этих частей. В силу теоремы 4 это же относится к равенству $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}} (m, {\leqslant}\infty))=m$, так как $\mathcal{T}_{\mathrm{lo}}(m, {\leqslant}\infty)=\operatorname{Cl}_{\mathrm E}(\mathcal{T}_{\mathrm{lo}}(m, {<}\infty))$. Равенство $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(m,\infty))=0$ означает, что семейство $\mathcal{T}_{\mathrm{lo}}(m,\infty)$ является конечным, а это выполняется, поскольку в этом случае все дискретные части элементарно эквивалентны. 3) Рассмотрим следующую структуру
$$
\begin{equation*}
\underbrace{2+\mathbb{Q}+\dots +2+\mathbb{Q}}_{n_1 {\text{ раз}}}+\mathbb{Q}_2(2,\mathbb{Q})+\dots +\underbrace{2+\mathbb{Q}+\dots +2+\mathbb{Q}}_{n_k {\text{ раз}}}+\mathbb{Q}_2(2,\mathbb{Q})+\dotsb,
\end{equation*}
\notag
$$
которую можем закодировать $\omega$-последовательностью $(n_1, \dots, n_k, \dots)$. Таким образом, для такой структуры получаем бесконечное число максимальных выпуклых дискретных частей длины 2, откуда, варьируя $n_i$, получаем $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(\infty, 2))=\infty$. Следовательно, $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}(\infty, \gamma))=\infty$ и $\operatorname{RS}(\mathcal{T}_{\mathrm{lo}}({\leqslant}\infty, \gamma))=\infty$ для любого $\gamma\geqslant 2$.
Оставшиеся равенства справедливы в силу свойства монотонности значений $\operatorname{RS}$-ранга при расширении семейств теорий, а также в силу сохранения $\operatorname{RS}$-ранга при переходе к $\mathrm{E}$-замыканиям. Из предложения 4 непосредственно вытекает Следствие 4. Непустое семейство $\mathcal{T}_{\mathrm{lo}}(K,G)$ при $G\cap(\omega\setminus\{0,1\})\ne\varnothing$ является $\mathrm{e}$-тотально трансцендентным тогда и только тогда, когда $K$ – конечное подмножество множества $\omega$. Далее, обозначим через $\mathcal{T}^{\mathrm{dense}}_{\mathrm{\Sigma}}$, $\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}}$ и $\mathcal{T}^{\mathrm{dense}}_{\mathrm{wom},\mathrm{\Sigma}}$ семейства всех плотно упорядоченных теорий сигнатуры $\Sigma$, всех о-минимальных плотно упорядоченных теорий сигнатуры $\Sigma$ и всех слабо о-минимальных плотно упорядоченных теорий сигнатуры $\Sigma$ соответственно. Очевидно, что $\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}} \subset\mathcal{T}^{\mathrm{dense}}_{\mathrm{wom},\mathrm{\Sigma}} \subset \mathcal{T}^{\mathrm{dense}}_{\mathrm{\Sigma}}$, откуда получаем, что
$$
\begin{equation}
\operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}}) \leqslant \operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{wom},\mathrm{\Sigma}})\leqslant \operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{\Sigma}}),
\end{equation}
\tag{4.3}
$$
а также
$$
\begin{equation}
\operatorname{ds}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}}) \leqslant \operatorname{ds}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{wom},\mathrm{\Sigma}})\leqslant \operatorname{ds}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{\Sigma}}),
\end{equation}
\tag{4.4}
$$
при наличии равенств в двойном неравенстве (4.3). Пример 10. Если $\Sigma^0$ – сигнатура чистого линейного порядка, то $\mathcal{T}^{\mathrm{dense}}_{\mathrm{\Sigma}^0}$ состоит из четырех теорий, содержащих предложения о существовании/отсутствии наибольшего / наименьшего элемента. Те же четыре теории составляют множество $\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}^0}$ (и $\mathcal{T}^{\mathrm{dense}}_{\mathrm{wom}, \mathrm{\Sigma}^0}$). Тогда Предложение 5. Если сигнатура $\Sigma^1$ содержит символ $<$ линейного порядка и одноместный предикатный символ $P$, то Доказательство. В силу (4.3) достаточно показать, что $\operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}^1})=\infty$. Действительно, выпуклые компоненты реализации предиката $P$ образуют интервалы, которых имеется конечное число. Пусть $n$ обозначает количество идущих подряд выпуклых компонент вида $[a,b]$, а $m$ – количество идущих подряд выпуклых компонент вида $(a,b)$. Тогда посредством таких компонент можно закодировать любую конечную последовательность, откуда, применяя доказательство пункта 3 предложения 4, получаем требуемое. Предложение 6. Пусть $\Sigma^c_{\kappa}:=\{<, c_i\}_{i<\kappa}$, где $\kappa$ – некоторый кардинал. Тогда имеет место следующее: Доказательство. Если $\kappa<\omega$, то семейство $\mathcal{T}^{\mathrm{dense}}_{\mathrm{\Sigma}^c_{\kappa}}$ конечно в силу конечного числа вариантов взаимного расположения констант на плотном линейно упорядоченном множестве.
Если $\kappa\geqslant\omega$, то существует по меньшей мере континуум вариантов взаимного расположения констант на плотном линейно упорядоченном множестве и можно построить бесконечное $2$-дерево предложений, чередуя плотные и дискретные части, составленные из констант. Это свидетельствует о значении $\operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{\Sigma}^c_{\kappa}})=\infty$. Комбинируя рассуждения для доказательства предложений 5 и 6, получаем Следствие 5. Пусть $\Sigma^{1,c}_{\kappa, \eta}:=\{<,P^1_i, c_j\}_{i<\kappa,j<\eta}$, где $\kappa, \eta$ – некоторые кардиналы. Тогда следующие условия эквивалентны: Предложение 7. Пусть $\Sigma^f_1:=\{<, f^1\}$, где $f$ – одноместный функциональный символ или предикатный символ одноместной частичной функции. Тогда имеет место следующее: $\operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}^f_1})=\infty$. Доказательство. Рассмотрим $\operatorname{Dom}(f)$. Оно $\varnothing$-определимо, и, следовательно, может быть интерпретацией произвольного одноместного предикатного символа. Тогда в силу доказательства предложения 5 заключаем, что $\operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}^f_1})=\infty$. Если рассматривать всюду определенные функции, то в качестве $f$ можно взять характеристическую функцию произвольного подмножества носителя и повторить рассуждение. Следующая теорема является критерием $\mathrm{e}$-тотальной трансцендентности для семейств о-минимальных, слабо о-минимальных и произвольных плотно упорядоченных теорий произвольной сигнатуры $\Sigma$: Теорема 9. Семейство $\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}}$ ($\mathcal{T}^{\mathrm{dense}}_{\mathrm{wom},\mathrm{\Sigma}}$; $\mathcal{T}^{\mathrm{dense}}_{\Sigma}$) $\mathrm{e}$-тотально трансцендентно тогда и только тогда, когда сигнатура $\Sigma$ помимо бинарного предикатного символа, выражающего отношение линейного порядка, содержит лишь конечное число нульместных предикатных и константных символов. Доказательство. В силу предложения 7 если бы сигнатура $\Sigma$ содержала хотя бы один одноместный функциональный символ, то $\operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\Sigma})=\infty$. Далее, если бы сигнатура $\Sigma$ содержала хотя бы один двухместный функциональный символ, то мы смогли бы образовать хотя бы одну определимую одноместную функцию, откуда в силу предложения 7 пришли бы к противоречию. Аналогично, если бы сигнатура $\Sigma$ содержала хотя бы один бинарный предикатный символ, то мы смогли бы образовать либо бесконечное число определимых одноместных функций, либо бесконечное число определимых унарных предикатов, откуда в силу предложения 5 пришли бы к противоречию с $\mathrm{e}$-тотальной трансцендентностью. Далее, обозначим через $\mathcal{T}^{\mathrm{dense}}_{\mathrm{qom},\Sigma}$ семейство всех вполне о-минимальных плотно упорядоченных теорий сигнатуры $\Sigma$. Вполне о-минимальные теории (введенные в [24] и исследованные в работах [25]–[27]) – это подкласс класса слабо о-минимальных теорий, наследующих свойство биективности отображения между множествами реализаций не слабо ортогональных 1-типов, выполняемое в о-минимальных теориях. Поэтому
$$
\begin{equation*}
\operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{om},\mathrm{\Sigma}}) \leqslant \operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{qom},\mathrm{\Sigma}})\leqslant \operatorname{RS}(\mathcal{T}^{\mathrm{dense}}_{\mathrm{wom},\mathrm{\Sigma}}).
\end{equation*}
\notag
$$
Откуда получаем, что теорема 9 верна и для семейства вполне о-минимальных плотно упорядоченных теорий сигнатуры $\Sigma$. Замечание 5. Приведенные результаты позволяют отслеживать количество точек накопления при аппроксимациях теорий из замыканий данных семейств упорядоченных теорий согласно предложению 2 и теоремам 4, 5. Например, в силу предложения 4 для любых $m,n\in\omega$, где $n\geqslant 2$, семейство $\mathcal{T}_{\mathrm{lo}}(m, n)$ не имеет точек накопления; для любого $m\in\omega\setminus\{0\}$ семейство $\mathcal{T}_{\mathrm{lo}}(m, \infty)$ имеет счетное число точек накопления, а семейство $\mathcal{T}_{\mathrm{lo}}(\infty,\lambda)$ при $\lambda\in(\omega\setminus\{0,1\})\cup \{\infty\}$ имеет $2^\omega$ точек накопления. Замечание 6. Отметим, что среди рассмотренных семейств упорядоченных теорий семейства Действительно, свойства счетной категоричности, о-минимальности и слабой о-минимальности как заданного $\operatorname{RC}$-ранга [23], так и произвольного $\operatorname{RS}$-ранга могут нарушаться при переходе к $\mathrm{E}$-замыканиям как произвольным наращиванием неэквивалентных формул, так и определимого числа интервалов заданного $\operatorname{RS}$-ранга. Тем самым, для $\mathrm{E}$-замкнутых семейств описанные характеристики $\operatorname{RS}$-рангов могут определяться через описание точек накопления, соответствующих значениям ранга Кантора–Бендиксона, а для семейств, не являющихся $\mathrm{E}$-замкнутыми, значения $\operatorname{RS}$-рангов могут быть найдены через значения ранга Кантора–Бендиксона лишь при переходе к $\mathrm{E}$-замыканиям. Таким образом, описанные методы нахождения ранговых значений через ветвления деревьев предложений, лежащих в основе определения $\operatorname{RS}$-ранга, имеют преимущество по сравнению с нахождением этих значений на основе ранга Кантора–Бендиксона. В заключение авторы благодарят анонимных рецензентов, чьи конструктивные замечания и предложения способствовали улучшению содержания статьи. 
Цитирование в формате AMSBIB
\RBibitem{KulPavSud24} |
|
||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|