| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) О вложении первого неконструктивного ординала в полурешетки Роджерса М. Х. Файзрахманов Казанский (Приволжский) федеральный университет
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 5, Pages DOI: https://doi.org/10.1134/S0001434623050127 
Реферативные базы данных:
  1. Введение и постановка задачиПонятие $\Sigma^0_n$-вычислимой нумерации семейства арифметических множеств введено Гончаровым и Сорби в рамках предложенного ими в [1] подхода к определению понятия вычислимости для семейств объектов, допускающих описание в конструктивно заданном языке. Оно является обобщением понятия вычислимой нумерации [2], [3] – традиционного объекта исследований в теории нумераций. В процитированной монографии Ершова [2] можно найти множество теорем, относящихся к структурным свойствам полурешеток Роджерса вычислимых семейств. К ним относится и теорема Хуторецкого [4], утверждающая, что в любую такую полурешетку над каждым, за исключением наибольшего, элементом можно вложить линейный порядок, изоморфный первому неконструктивному ординалу. Изучение алгебраических свойств полурешеток Роджерса семейств арифметических множеств было начато Бадаевым, Гончаровым, Подзоровым в работах [5]–[7]. В этих работах исследован ряд алгебраических особенностей таких полурешеток, в том числе в [7], вместе с результатами работы [8], было установлено, что над любым их, за исключением наибольшего, элементом можно вложить линейный порядок типа $\omega$. Как отмечается в [7], справедлива или нет для таких полурешеток исходная теорема Хуторецкого в настоящий момент неизвестно. Неизвестно также вкладывается ли в них хотя бы над каким-то элементом порядок, изоморфный первому неконструктивному ординалу $\omega^{CK}_1$. В настоящей статье доказывается, что ответ на второй вопрос положителен. Причем показано, что если семейство арифметических множеств является главным или конечным, то порядок типа $\omega^{CK}_1$ можно вложить над любым ненаибольшим элементом его полурешетки Роджерса. Основные понятия, относящиеся к вычислимым функциям и множествам, можно найти в [9], к теории нумераций – в [2], [3]. До конца статьи зафиксируем число $n\geqslant 2$. Нумерацией не более чем счетного непустого множества $S$ называется любое сюръективное отображение $\mathbb N$ на $S$. Скажем, что нумерация $\alpha$ множества $S$ сводится к его нумерации $\beta$, если существует такая вычислимая функция $f$, что для всех $x$ выполняется $\alpha(x)=\beta(f(x))$. Пусть $\mathscr R$ – непустое семейство $\Sigma^0_n$-множеств и $\alpha$ – его нумерация. Мы называем $\alpha$ $\Sigma^0_n$-вычислимой, если множество
$$
\begin{equation*}
G_\alpha\leftrightharpoons\{\langle x,y\rangle\colon x\in\alpha(y)\}
\end{equation*}
\notag
$$
принадлежит классу $\Sigma^0_n$ арифметической иерархии. Последовательность нумераций $\{\beta_m\}_{m\in\mathbb N}$ семейства $\mathscr R$ назовем $\Sigma^0_n$-вычислимой, если для каждого $m$ $\Sigma^0_n$-индекс ($\varnothing^{(n-1)}$-в.п. геделевский номер) множества $G_{\beta_m}$ определяется равномерно по $m$. Для семейства $\mathscr R$ множество всех его $\Sigma^0_n$-вычислимых нумераций является предпорядком относительно сводимости нумераций. Ассоциированный с ним частичный порядок является верхней полурешеткой, которую мы называем полурешеткой Роджерса и обозначаем символом $L^0_n(\mathscr R)$. Элемент $L^0_n(\mathscr R)$, содержащий нумерацию $\alpha$, обозначаем через $[\alpha]$. Для нумераций $\alpha_0$ и $\alpha_1$ семейства $\mathscr R$ через $\alpha_0\oplus\alpha_1$ мы обозначаем прямую сумму этих нумераций: $(\alpha_0\oplus\alpha_1)(2x+i)=\alpha_i(x)$, $i=0,1$. Наименьшей верхней гранью элементов $[\alpha],[\beta]\in L^0_n(\mathscr R)$ является элемент $[\alpha\oplus\beta]\in L^0_n(\mathscr R)$. Если элемент $[\nu]\in L^0_n(\mathscr R)$ является наибольшим, то нумерацию $\nu$ назовем $\Sigma^0_n$-вычислимой главной нумерацией семейства $\mathscr R$. При этом само семейство $\mathscr R$ будем также называть главным. Если элемент $[\mu]\in L^0_n(\mathscr R)$ является минимальным, то назовем нумерацию $\mu$ минимальной. Через $c(x,y)$ обозначаем стандартную вычислимую функцию, взаимно однозначно нумерующую пары натуральных чисел. Пусть $l(c(x,y))=x$ и $r(c(x,y))=y$. Для произвольной частичной функции $\psi$ пишем $\psi(x)\!\downarrow$, если ее значение определено на аргументе $x$, и $\psi(x)\!\uparrow$ в противном случае. 2. Вложение $\omega^{CK}_1$ над минимальными элементамиКак было установлено в [5], полурешетка Роджерса любого бесконечного $\Sigma^0_n$-вычислимого семейства $\mathscr R$ содержит минимальные элементы (которых, в свою очередь, бесконечно много). Этот результат вместе со следующей теоремой позволяет показать, что в $L^0_n(\mathscr R)$ можно вложить линейный порядок, изоморфный первому неконструктивному ординалу. Теорема 1. Пусть $\mathscr R$ – бесконечное $\Sigma^0_n$-вычислимое семейство. Если $c$ – минимальный элемент $L^0_n(\mathscr R)$, то существует вполне упорядоченное подмножество $L^0_n(\mathscr R)$ типа $\omega^{CK}_1$ с наименьшим элементом $c$. Доказательство. Пусть $\mathscr R$ – бесконечное $\Sigma^0_n$-вычислимое семейство. Выберем множества $A,B\in\mathscr R$, для которых $A\not\subseteq B$. Зафиксируем элемент $z$, такой что $z\in A\setminus B$.
Выберем минимальную $\Sigma^0_n$-вычислимую нумерацию $\sigma$, для которой $[\sigma]=c$. Далее нам понадобится следующая лемма. Лемма 1. Существует $\Sigma^0_n$-вычислимая последовательность нумераций семейства $\mathscr R$ удовлетворяющая условиям: Доказательство. Выберем такую частично вычислимую функцию $\psi$, что для всех $e$, если $l(W_e)$ бесконечно, то найдутся $i>e$ и $x$, для которых причем для каждого $i$ существует лишь конечное число $x$, удовлетворяющих условию $c(i,x)\in\mathrm{ran}\psi$. Для всех $e\in\operatorname{dom}\psi$ положим По определению частичной функции $\psi$ для каждого $i$ существует лишь конечное число $x$ таких, что значение $\beta(c(i,x))$ определено. Определим оставшиеся значения $\beta(c(i,x))$, $i,x\in\mathbb N$, таким образом, чтобы для всех $i$ нумерация $\mu_i(x)\leftrightharpoons\beta(c(i,x))$ была эквивалентна $\sigma$. Стало быть, последовательность $\sigma\leqslant\beta_0\leqslant\beta_1\leqslant\dotsb$, в которой $\beta_m=\beta$ для всех $m$, удовлетворяет условиям 1) и 2). Второе условие леммы будет применяться для построения нумерации $\alpha$, не сводимой ни к одной из нумераций $\beta_m$, $m\in\mathbb N$. Теперь эффективно по $\Sigma^0_n$-вычислимой последовательности
$$
\begin{equation*}
\sigma\leqslant\beta_0\leqslant\beta_1\leqslant\beta_2\leqslant\dotsb
\end{equation*}
\notag
$$
нумераций $\mathscr R$, удовлетворяющей условиям 1) и 2), определим $\Sigma^0_n$-вычислимую нумерацию $\alpha$ семейства $\mathscr R$ такую, что $\alpha\not\leqslant\beta_m$, $m\in\mathbb N$, и
Перейдем к определению нумерации $\alpha$. Для каждого $e$, если найдутся $j>e$ и $x\in \mathbb N$, для которых $c(2j,x)\in W_e$, то выберем первую такую пару $c(2j,x)$ и определим Отметим, что к настоящему моменту для каждого $j$ существует лишь конечное число $x$, таких что значение $\alpha(c(2j,x))$ определено. Далее, фиксируем произвольные числа $m$, $i$ и определим оставшиеся значения $\alpha(f(m,i,x))$, где таким образом, чтобы $\alpha$ не сводилась к $\beta_m$ посредством $\varphi_i$. Для этого начинаем одновременное перечисление всех $k$ и всех $y$, проверяя выполнение условий
$$
\begin{equation*}
W_e=\bigl\{\varphi_i(f(m,i,x))\colon \varphi_i(f(m,i,x))\!\downarrow,\, x\in\mathbb N\bigr\}.
\end{equation*}
\notag
$$
Если $l(W_e)$ конечно, то существует требуемое $k$. В противном случае из условия 2) следует существование требуемого $y$. Если первым перечислится $k$, удовлетворяющее a), то для некоторого $k_0\leqslant k$ выполняется
$$
\begin{equation*}
\exists^\infty\,x \qquad \bigl[\varphi_i(f(m,i,x))\!\downarrow\ \Rightarrow\ l(\varphi_i(f(m,i,x)))=k_0\bigr].
\end{equation*}
\notag
$$
Нетрудно видеть, что в этом случае можно выбрать бесконечное вычислимое множество и число $k_0\leqslant k$ такие, что для всех $j$ значение $\alpha(f(m,i,x_j))$ не определено и
$$
\begin{equation}
\exists\,j_0\quad \forall\,j\geqslant j_0 \qquad \bigl[\varphi_i(f(m,i,x_j))\!\downarrow\ \Rightarrow\ l(\varphi_i(f(m,i,x_j)))=k_0\bigr].
\end{equation}
\tag{2.2}
$$
Определим для всех $j$, а все оставшиеся не определенные значения $\alpha(f(m,i,x))$ положим равными какому-нибудь одному множеству (например, можно определить $\alpha(f(m,i,x))=\gamma(0)$). Согласно такому определению $\xi_{2c(m,i)}$ нумерует все семейство $\mathscr R$ и верна сводимость Отсюда следует, что $\xi_{2c(m,i)}$ минимальна. В силу (2.3) выполняется Поскольку $\gamma\not\leqslant\mu^m_{k_0}$, то и $\xi_{2c(m,i)}\not\leqslant\mu^m_{k_0}$. С учетом (2.2) получаем, что $\alpha$ не сводится к $\beta_m$ посредством $\varphi_i$.Если же $y$, удовлетворяющий условию b), перечислится не позже $k$, то определим Поскольку $z\in\beta_m(\varphi_i(f(m,i,y)))\setminus B$, получаем, что $\alpha$ не сводится к $\beta_m$ посредством $\varphi_i$. Пусть коконечное множество состоит из всех $x$, на которых значение $\alpha(f(m,i,x))$ к настоящему моменту не определено. Полагаем для всех $j$. Снова получаем, что $\xi_{2c(m,i)}$ нумерует все семейство $\mathscr R$ и $\xi_{2c(m,i)}\leqslant \gamma$. Следовательно, $\xi_{2c(m,i)}$ минимальна.Перейдем к определению значений вида $\alpha(c(2j+1,x))$. Одновременно с определением будем для всех $m$ обеспечивать сводимость $\beta_m\leqslant\alpha$. Пусть для всех $m$, $i$, $x$. Для каждого $e$, если выполняется условие
$$
\begin{equation}
\exists\,m>e \quad \exists\,i \quad \exists\,x \qquad [g(m,i,x)\in W_e],
\end{equation}
\tag{2.4}
$$
то для одной из подходящих троек $m$, $i$, $x$ положим Отметим, что, с учетом условия “$m>e$” в (2.4) для каждого $m$ определено лишь конечное число значений вида $\alpha(g(m,i,x))$. Зафиксируем произвольно $m$, $i$ и определим оставшиеся значения $\alpha(g(m,i,x))$. Пусть коконечное множество состоит из всех $x$, на которых значение $\alpha(g(m,i,x))$ к настоящему моменту не определено. Полагаем для всех $j$ (заметим, что если $i$ достаточно велико, то $X^m_i=\mathbb N$). Отсюда получаем, что $\xi_{2c(m,i)+1}$ нумерует все семейство $\mathscr R$ и, поскольку она является минимальной. Также из (2.6) следует, что $\mu^m_i\leqslant\alpha$. Кроме того, в силу условия “$m>e$” в (2.4) получаем, что для каждого $m$, начиная с некоторого $i$ (для которого $X^m_i=\mathbb N$), сводимость $\mu^m_i\leqslant\alpha$ будет равномерной по $i$. Стало быть, $\beta_m\leqslant\alpha$ для всех $m$. Таким образом, нумерация $\alpha$ удовлетворяет условиям 3) и 4). Докажем справедливость для нее условия 5). Лемма 2. Для каждого $e$, если $l(W_e)$ бесконечно, то найдутся $i$ и $x$, для которых $c(i,x)\in W_e$ и $z\in\alpha(c(i,x))$. Доказательство. Выберем произвольно $e$, для которого $l(W_e)$ бесконечно. Если оно содержит бесконечно много четных чисел, то 5) выполняется в силу (2.1). Пусть $l(W_e)$ содержит бесконечно много нечетных чисел. Если выполняется условие (2.4), то 5) выполняется в силу (2.5). Пусть (2.4) не выполняется. Зафиксируем $m_0$, $i_0$ такие, что множество
$$
\begin{equation*}
X=\bigl\{i\colon \exists\,x\ [g(m_0,i,x)\in W_e]\bigr\}
\end{equation*}
\notag
$$
бесконечно и $X^{m_0}_i=\mathbb N$ для всех $i\geqslant i_0$. В силу (2.6) и выбора $m_0$, $i_0$ для всех $i\geqslant i_0$ и $x$ выполняется Выберем $d$, для которого Поскольку $X$ бесконечно, то и $l(W_d)$ бесконечно. Согласно условию 2) существуют такие $i\geqslant i_0$ и $x$, что $c(i,x)\in W_d$ (или, равносильно, $g(m_0,i,x)\in W_e$) и Таким образом, $\alpha$ удовлетворяет условию 5). Непосредственно из конструкции вытекает, что нумерация $\alpha$ строится по последовательности $\sigma\leqslant\beta_0\leqslant\beta_1\leqslant\dotsb$ эффективно. Кроме того, мы можем итерировать и продолжать применять описанную конструкцию на всех вычислимых ординалах на основании теоремы о рекурсии. Отсюда следует, что $L^0_n(\mathscr R)$ содержит вполне упорядоченное подмножество типа $\omega^{CK}_1$ с наименьшим элементом $c=[\sigma]$. 3. Вложение $\omega^{CK}_1$ над ненаибольшими элементамиВ настоящем разделе доказывается, что в полурешетку Роджерса как главного, так и конечного $\Sigma^0_n$-вычислимого семейства над любым, за исключением наибольшего, элементом, можно вложить линейный порядок типа $\omega^{CK}_1$. Теорема 2. Пусть $\mathscr R$ – $\Sigma^0_n$-вычислимое главное семейство. Тогда для любой $\Sigma^0_n$-вычислимой неубывающей последовательности $\beta_0\leqslant\beta_1\leqslant\dotsb$ неглавных нумераций $\mathscr R$ найдется такая его $\Sigma^0_n$-вычислимая неглавная нумерация $\alpha$, что $\beta_m\leqslant\alpha$ и $\alpha\not\leqslant\beta_m$ для всех $m$. Доказательство. Пусть $\nu$ – $\Sigma^0_n$-вычислимая главная нумерация неодноэлементного семейства $\mathscr R$. Зафиксируем сильные $\varnothing^{(n-1)}$ вычислимые двойные и тройные последовательности конечных множеств $\{\nu_s(x)\}_{s,x\in\mathbb N}$ и $\{\beta_{m,s}(x)\}_{m,s,x\in\mathbb N}$ такие, что для всех $x$ и $m$. Пусть $\{f_e\}_{e\in\mathbb N}$ – $\varnothing'$-вычислимая последовательность всех всюду определенных вычислимых функций.
Чтобы определить нумерацию $\alpha$, удовлетворяющую заключению теоремы, представим множество всех натуральных чисел в виде двух непересекающихся множеств всех пар и всех пятерок натуральных чисел. Дополнительно будем предполагать, что при фиксированном $m$ множество всех пар $(m,x)$, $x\in\mathbb N$, совпадает с множеством всех чисел вида $c(u,y)$, $y\in\mathbb N$, для некоторого $u$, и при фиксированных $e$, $m$, $i$ множество всех пятерок $(e,m,i,k,x)$, $k,x\in\mathbb N$, совпадает с множеством всех чисел вида $c(v,y)$, $y\in\mathbb N$, для некоторого $v$. Определяя $\alpha$ на парах $(m,x)$, обеспечим условие $\beta_m\leqslant\alpha$. Определяя $\alpha$ на пятерках $(e,m,i,k,x)$, обеспечим, что $\alpha$ не будет сводиться к $\beta_m$ посредством функции $f_i$ при условии, что $\alpha\leqslant\nu$ посредством функции $f_e$. Вместе с $\alpha$ определим также $\Sigma^0_n$-вычислимую нумерацию $\zeta$ некоторого подсемейства $\mathscr R$, для которой $\zeta\not\leqslant\alpha$. Поскольку нумерация $\nu$ главная, будет выполняться $\zeta\oplus\nu\leqslant\nu\not\leqslant\alpha$. Не ограничивая общности, будем считать, что Выберем число $z$ такое, что $z\in\nu(0)\setminus\nu(1)$. Определяя нумерацию $\alpha$, для каждого номера $x$ будем явно указывать номер $y$ и число $m$, для которых
$$
\begin{equation*}
\alpha(x)=\nu(y)\qquad \text{или}\qquad \alpha(x)=\beta_m(y).
\end{equation*}
\notag
$$
Примем соглашение, что $\alpha_s(x)$, $s\in\mathbb N$, есть множество $\nu_s(y)$ или $\beta_{m,s}(y)$ соответственно.
Зафиксируем произвольно $j$ и для каждого $y$ определим значение $\zeta(j,y)$. Рассмотрим несколько случаев. 1) Если существуют различные $y_0$, $y_1$, для которых $\varphi_j(j,y_0)\!\downarrow=\varphi_j(j,y_1)\!\downarrow$, то определим для всех $y$, отличных от $y_0$.2) Предположим, что 1) не выполняется, но существует $y_0$ такое, что $\varphi_j(j,y_0)\!\downarrow$ и $l(\varphi_j(j,y_0))>j$. Определим для каждого $y$. Если найдется пара $(m,x)$, для которой $\varphi_j(j,y_0)=(m,x)$, то, если этого еще не сделано, определим Если найдется пятерка $(e,m,i,k,x)$, для которой $\varphi_j(j,y_0)=(e,m,i,k,x)$, то, если этого еще не сделано, определим для всех $y$.3) Пусть условия предыдущих случаев не выполняются. Тогда можем выбрать конечную последовательность вычислимых множеств $\{Y_p\}_{p\leqslant j}$ такую, что и если $\varphi_j$ всюду определена, то для всех $p$ и всех $y_0,y_1\in Y_p$ выполняется Пусть для каждого $p\leqslant j$ множество $Y_p$, возможно конечное, имеет вид Определим для всех $p\leqslant j$ и $q$ если $\varphi_j(j,y^p_q)\!\downarrow$ является некоторой парой $(m,x)$, и для всех остальных $y$. Заметим, что если $\varphi_j$ всюду определена, то в силу (3.1) для всех $p$, $q_0$, $q_1$ либо найдутся $m$, $x_0$, $x_1$, для которых
$$
\begin{equation*}
\varphi_j(j,y^p_{q_0})=(m,x_0),\qquad \varphi_j(j,y^p_{q_1})=(m,x_1),
\end{equation*}
\notag
$$
либо найдутся $e$, $m$, $i$, $k_0$, $k_1$, $x_0$, $x_1$, для которых
$$
\begin{equation*}
\varphi_j(j,y^p_{q_0})=(e,m,i,k_0,x_0),\qquad \varphi_j(j,y^p_{q_1})=(e,m,i,k_1,x_1).
\end{equation*}
\notag
$$
Перейдем к определению значений $\alpha(y)$. Действия при рассмотрении случаев 1)–3) обеспечивают то, что для каждого $m$ существует лишь конечное число $x$, для которых определено значение $\alpha(m,x)$. Для произвольного $m$ выберем коконечное множество состоящее из всех $x$, для которых значение $\alpha(m,x)$ к настоящему моменту не определено. Положим для всех $j$. Таким образом получаем, что $\beta_m\leqslant\alpha$ для всех $m$.Выберем произвольную тройку $e$, $m$, $i$. Действия при рассмотрении случаев 1)–3) обеспечивают то, что существует лишь конечное число $k$, для которых все значения $\alpha(e,m,i,k,y)$, $y\in\mathbb N$, определены. Для всех остальных $k$ начинаем процесс последовательных присваиваний
$$
\begin{equation}
\begin{aligned} \, \alpha(e,m,i,k,0) &=\nu(f_e(e,m,i,k,1)), \\ \alpha(e,m,i,k,1) &=\nu(f_e(e,m,i,k,2)), \\ \alpha(e,m,i,k,2) &=\nu(f_e(e,m,i,k,3)), \\ &\dotsb \\ \alpha(e,m,i,k,x) &=\nu(f_e(e,m,i,k,x+1)), \\ &\dotsb \end{aligned}
\end{equation}
\tag{3.4}
$$
который прерывается в случае появления $s$, удовлетворяющего условиям
$$
\begin{equation}
k <\operatorname{lh}_1(e,m,i,s) \leftrightharpoons\max\bigl\{r\leqslant s\colon \forall\,t\leqslant r \nonumber
\end{equation}
\notag
$$
$$
\begin{equation}
\qquad\phantom{<\operatorname{lh}_1(e,m,i,s) \leftrightharpoons\max\bigl\{} [\alpha_s(e,m,i,t,0)\upharpoonright r=\beta_{m,s}(f_i(e,m,i,t,0))\upharpoonright r]\bigr\},
\end{equation}
\tag{3.5}
$$
$$
\begin{equation}
k <\mathrm{lh}_2(e,s) \leftrightharpoons\max\bigl\{r\leqslant s\colon \forall\,t\leqslant r\ [\alpha_s(t)\upharpoonright r =\nu_s(f_e(t))\upharpoonright r]\bigr\},
\end{equation}
\tag{3.6}
$$
или для которого найдется такое $y\leqslant s$, что Зафиксируем произвольное $k$, для которого активен процесс (3.4). В случае появления $s$, удовлетворяющего каждому из условий (3.5) и (3.6), выберем первое $(x+1)$, для которого значение $\alpha(e,m,i,k,x+1)$ не определено, и определим для всех $y>x+1$.
В случае появления $s$, для которого найдется $y\leqslant s$ такое, что выполняется (3.7), определим для всех $x$ и $w$, для которых к настоящему моменту не определено значение $\alpha(e,m,i,w,x)$, при этом прерывая все процессы последовательных присваиваний. Покажем, что $\alpha$ удовлетворяет заключению теоремы. Доказательство. Выберем произвольные $m$ и $i$. Зафиксируем $e$ такое, что $\alpha\leqslant\nu$ посредством $f_e$. Покажем, что $\alpha$ не сводится к $\beta_m$ посредством $f_i$.
Если для некоторых $s$, $y\leqslant s$ и $k$ процесс (3.4) прерывается условием (3.7), то, с учетом (3.10), будем иметь, что для некоторого $x\geqslant y$ справедливы равенства
$$
\begin{equation*}
\begin{aligned} \, \nu(1) &=\alpha(e,m,i,k,x+1)=\nu(f_e(e,m,i,k,x+1)) =\alpha(e,m,i,k,x)=\dotsb \\ &=\alpha(e,m,i,k,y)=\dots=\alpha(e,m,i,k,0). \end{aligned}
\end{equation*}
\notag
$$
Поскольку $z\in\alpha(e,m,i,k,y)\setminus\nu(1)$, получаем противоречие со сводимостью $\alpha\leqslant\nu$ посредством $f_e$.
Ввиду сводимости $\alpha\leqslant\nu$ посредством $f_e$ имеем Отсюда следует, что предел $\lim_s\operatorname{lh}_1(e,m,i,s)$ конечен. В противном случае, с учетом (3.8), для всех $k$ выполнялось бы Это противоречит тому, что $\nu\not\leqslant\beta_m$. Поскольку предел $\lim_s\operatorname{lh}_1(e,m,i,s)$ конечен, $\alpha$ не сводится к $\beta_m$ посредством $f_i$. Доказательство. Выберем произвольное $j$, для которого $\varphi_j$ всюду определена, и покажем, что $\zeta$ не сводится к $\alpha$ посредством $\varphi_j$. Если $j$ удовлетворяет условию случая 1), то для некоторых $y_0$, $y_1$ выполняется
$$
\begin{equation*}
\varphi_j(j,y_0)=\varphi_j(j,y_1), \qquad \zeta(j,y_0) =\nu(0)\not=\nu(1)=\zeta(j,y_1).
\end{equation*}
\notag
$$
Если $j$ удовлетворяет условию случая 2), то найдется такое $y_0$, что
$$
\begin{equation*}
\zeta(j,y_0)=\nu(0)\not=\nu(1)=\alpha(\varphi_j(j,y_0)).
\end{equation*}
\notag
$$
Пусть $j$ удовлетворяет условию случая 3). Поскольку $\varphi_j$ всюду определена, можем выбрать $p\leqslant j$, для которого $Y_p$ бесконечно. Если значения $\varphi_j(j,y^p_q)$, $q\in\mathbb N$, являются парами, то, в силу (3.2) и (3.3) $\zeta$ не сводится к $\alpha$ посредством $\varphi_j$, так как в противном случае была бы справедлива сводимость $\nu\leqslant\beta_m$ для некоторого $m$.
Пусть значения $\varphi_j(j,y^p_q)$, $q\in\mathbb N$, являются пятерками вида $(e,m,i,k,x)$ для фиксированных $e$, $m$, $i$. Как было установлено в доказательстве предыдущей леммы, один из пределов $\lim_s\operatorname{lh}_1(e,m,i,s)$ и $\lim_s\operatorname{lh}_2(e,s)$ конечен. Если для некоторого $k$ процесс (3.4) прерывается условием (3.7), то, с учетом (3.9) и (3.10), для всех пар $k$, $x$, за исключением лишь конечного числа, будет выполнено $\alpha(e,m,i,k,x)=\nu(1)$. В противном случае будем иметь лишь конечное число пар $k$, $x$, для которых $z\in\alpha(e,m,i,k,x)$. В каждом из этих двух случаев, поскольку для всех $q$ выполняется $\zeta(j,y^p_q)=\nu(0)$, получаем, что $\zeta$ не сводится к $\alpha$ посредством $\varphi_j$. Этим завершается доказательство теоремы. Следующее утверждение есть следствие доказательства теоремы 2, а именно того, что $\alpha$ строится по последовательности $\beta_0\leqslant\beta_1\leqslant\dotsb$ эффективно. Следствие 1. Пусть $\mathscr R$ – $\Sigma^0_n$-вычислимое главное семейство и $b$ – ненаибольший элемент полурешетки $L^0_n(\mathscr R)$. Тогда существует вполне упорядоченное подмножество $L^0_n(\mathscr R)$ типа $\omega^{CK}_1$ с наименьшим элементом $b$. Покажем, что заключение теоремы 2 справедливо и для конечных семейств. Следствие 2. Пусть $\mathscr R$ – конечное семейство $\Sigma^0_n$-множеств, и пусть $b$ – ненаибольший элемент $L^0_n(\mathscr R)$. Тогда существует вполне упорядоченное подмножество $L^0_n(\mathscr R)$ типа $\omega^{CK}_1$ с наименьшим элементом $b$. Доказательство. Если семейство $\mathscr R$ является главным, то следствие сразу вытекает из теоремы 2. Если $\mathscr R$ не является главным, то, согласно [6], [12], оно не содержит наименьшего по включению элемента. Пусть $R_0,\dots,R_k$ – все попарно различные минимальные по включению элементы $\mathscr R$. Выберем конечные попарно несравнимые по включению множества $F_0\subseteq R_1$, $\dots$, $F_k\subseteq R_k$ и для любой $\Sigma^0_n$-вычислимой неубывающей последовательности $\beta_0\leqslant\beta_1\leqslant\dotsb$ нумераций $\mathscr R$ определим такую его $\Sigma^0_n$-вычислимую нумерацию $\alpha$, что $\beta_m\leqslant\alpha$ и $\alpha\not\leqslant\beta_m$ для всех $m$. Пусть $\alpha(c(m+1,x))=\beta_m(x)$ для всех $m$, $x$. Таким образом, $\beta_m\leqslant\alpha$ для всех $m$. Чтобы для всех $m$ выполнялось $\alpha\not\leqslant\beta_m$, определим Отсюда, для любых $m$ и $e$ нумерация $\alpha$ не сводится к $\beta_m$ посредством $\varphi_e$. Следствие 3. Пусть $\mathscr R$ – неодноэлементное $\Sigma^0_n$-вычислимое семейство. Тогда существует вполне упорядоченное подмножество $L^0_n(\mathscr R)$ типа $\omega^{CK}_1$. Доказательство. Если $\mathscr R$ бесконечно, то следствие вытекает из теоремы 1. В противном случае, применяем следствие 2. Остается нерешенным следующий вопрос. Вопрос 1. Пусть $\mathscr R$ – бесконечное неглавное $\Sigma^0_n$-вычислимое семейство. Можно ли над любым ее элементом вложить линейный порядок типа $\omega^{CK}_1$? 
Цитирование в формате AMSBIB
\RBibitem{Fai23} |
|
||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|