|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О вложении первого неконструктивного ординала в полурешетки Роджерса
М. Х. Файзрахманов Казанский (Приволжский) федеральный университет
Аннотация:
Рассматривается вопрос о вложении первого неконструктивного ординала в полурешетки Роджерса семейств арифметических множеств. Доказывается, что для любого бесконечного семейства арифметических множеств первый неконструктивный ординал вкладывается над любым минимальным элементом его полурешетки Роджерса. Устанавливается, что если семейство является
главным или конечным, то первый неконструктивный ординал вкладывается над любым ненаибольшим элементом его полурешетки Роджерса.
Библиография: 12 названий.
Ключевые слова:
нумерация, полурешетка Роджерса, первый неконструктивный ординал.
Поступило: 29.08.2022 Исправленный вариант: 17.10.2022
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$
$$
\begin{equation*}
\sigma\leqslant\beta_0\leqslant\beta_1\leqslant\beta_2\leqslant\dotsb,
\end{equation*}
\notag
$$
удовлетворяющая условиям: Доказательство. Выберем такую частично вычислимую функцию $\psi$, что для всех $e$, если $l(W_e)$ бесконечно, то найдутся $i>e$ и $x$, для которых
$$
\begin{equation*}
\psi(e)=c(i,x)\in W_e,
\end{equation*}
\notag
$$
причем для каждого $i$ существует лишь конечное число $x$, удовлетворяющих условию $c(i,x)\in\mathrm{ran}\psi$. Для всех $e\in\operatorname{dom}\psi$ положим
$$
\begin{equation*}
\beta(\psi(e))=A.
\end{equation*}
\notag
$$
По определению частичной функции $\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$, и В работе [10] было установлено, что множество всех минимальных нумераций любого бесконечного $\Sigma^0_n$-вычислимого семейства эффективно бесконечно (см. [5], [11]). Отсюда следует, что эффективно по (двойной) последовательности минимальных нумераций $\{\mu^m_i\}_{m,i\in\mathbb N}$ можно указать минимальную $\Sigma^0_n$-вычислимую нумерацию $\gamma$ семейства $\mathscr R$, не эквивалентную ни одной из нумераций $\mu^m_i$. Перейдем к определению нумерации $\alpha$. Для каждого $e$, если найдутся $j>e$ и $x\in \mathbb N$, для которых $c(2j,x)\in W_e$, то выберем первую такую пару $c(2j,x)$ и определим
$$
\begin{equation}
\alpha(c(2j,x))=A.
\end{equation}
\tag{2.1}
$$
Отметим, что к настоящему моменту для каждого $j$ существует лишь конечное число $x$, таких что значение $\alpha(c(2j,x))$ определено. Далее, фиксируем произвольные числа $m$, $i$ и определим оставшиеся значения $\alpha(f(m,i,x))$, где
$$
\begin{equation*}
f(m,i,x)=c(2c(m,i),x),
\end{equation*}
\notag
$$
таким образом, чтобы $\alpha$ не сводилась к $\beta_m$ посредством $\varphi_i$. Для этого начинаем одновременное перечисление всех $k$ и всех $y$, проверяя выполнение условий Одно из требуемых $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
$$
Нетрудно видеть, что в этом случае можно выбрать бесконечное вычислимое множество
$$
\begin{equation*}
\{x_0<x_1<x_2<\dotsb\}
\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}
$$
Определим
$$
\begin{equation}
\alpha(f(m,i,x_j))=\gamma(j)
\end{equation}
\tag{2.3}
$$
для всех $j$, а все оставшиеся не определенные значения $\alpha(f(m,i,x))$ положим равными какому-нибудь одному множеству (например, можно определить $\alpha(f(m,i,x))=\gamma(0)$). Согласно такому определению $\xi_{2c(m,i)}$ нумерует все семейство $\mathscr R$ и верна сводимость
$$
\begin{equation*}
\xi_{2c(m,i)}\leqslant\gamma.
\end{equation*}
\notag
$$
Отсюда следует, что $\xi_{2c(m,i)}$ минимальна. В силу (2.3) выполняется
$$
\begin{equation*}
\gamma\leqslant\xi_{2c(m,i)}.
\end{equation*}
\notag
$$
Поскольку $\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$, то определим
$$
\begin{equation*}
\alpha(f(m,i,y))=B.
\end{equation*}
\notag
$$
Поскольку $z\in\beta_m(\varphi_i(f(m,i,y)))\setminus B$, получаем, что $\alpha$ не сводится к $\beta_m$ посредством $\varphi_i$. Пусть коконечное множество
$$
\begin{equation*}
\{x_0<x_1<x_2<\dotsb\}
\end{equation*}
\notag
$$
состоит из всех $x$, на которых значение $\alpha(f(m,i,x))$ к настоящему моменту не определено. Полагаем
$$
\begin{equation*}
\alpha(f(m,i,x_j))=\gamma(j)
\end{equation*}
\notag
$$
для всех $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$. Пусть
$$
\begin{equation*}
g(m,i,x)=c(2c(m,i)+1,x)
\end{equation*}
\notag
$$
для всех $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$ положим
$$
\begin{equation}
\alpha(g(m,i,x))=A.
\end{equation}
\tag{2.5}
$$
Отметим, что, с учетом условия “$m>e$” в (2.4) для каждого $m$ определено лишь конечное число значений вида $\alpha(g(m,i,x))$. Зафиксируем произвольно $m$, $i$ и определим оставшиеся значения $\alpha(g(m,i,x))$. Пусть коконечное множество
$$
\begin{equation*}
X^m_i=\{x_0<x_1<x_2<\dotsb\}
\end{equation*}
\notag
$$
состоит из всех $x$, на которых значение $\alpha(g(m,i,x))$ к настоящему моменту не определено. Полагаем
$$
\begin{equation}
\alpha(g(m,i,x_j))=\mu^m_i(j)
\end{equation}
\tag{2.6}
$$
для всех $j$ (заметим, что если $i$ достаточно велико, то $X^m_i=\mathbb N$). Отсюда получаем, что $\xi_{2c(m,i)+1}$ нумерует все семейство $\mathscr R$ и, поскольку
$$
\begin{equation*}
\xi_{2c(m,i)+1}\leqslant\mu^m_i,
\end{equation*}
\notag
$$
она является минимальной. Также из (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$ выполняется
$$
\begin{equation*}
\alpha(g(m_0,i,x))=\mu^{m_0}_i(x).
\end{equation*}
\notag
$$
Выберем $d$, для которого
$$
\begin{equation*}
W_d=\bigl\{c(i,x)\colon i_0\leqslant i,\,g(m_0,i,x)\in W_e\bigr\}.
\end{equation*}
\notag
$$
Поскольку $X$ бесконечно, то и $l(W_d)$ бесконечно. Согласно условию 2) существуют такие $i\geqslant i_0$ и $x$, что $c(i,x)\in W_d$ (или, равносильно, $g(m_0,i,x)\in W_e$) и
$$
\begin{equation*}
z\in\beta_{m_0}(c(i,x))=\mu^{m_0}_i(x)=\alpha(g(m_0,i,x)).
\end{equation*}
\notag
$$
Таким образом, $\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}$ такие, что
$$
\begin{equation*}
\begin{aligned} \, \nu_0(x) &\subseteq\nu_1(x)\subseteq\nu_2(x) \subseteq\dotsb\subseteq\bigcup_s\nu_s(x)=\nu(x), \\ \beta_{m,0}(x) &\subseteq\beta_{m,1}(x)\subseteq\beta_{m,2}(x) \subseteq\dots\subseteq\bigcup_s\beta_{m,s}(x)=\beta_m(x) \end{aligned}
\end{equation*}
\notag
$$
для всех $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$.
Не ограничивая общности, будем считать, что
$$
\begin{equation*}
\nu(0)\not\subseteq\nu(1).
\end{equation*}
\notag
$$
Выберем число $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$, то определим
$$
\begin{equation*}
\zeta(j,y_0)=\nu(0),\qquad \zeta(j,y)=\nu(1)
\end{equation*}
\notag
$$
для всех $y$, отличных от $y_0$.
2) Предположим, что 1) не выполняется, но существует $y_0$ такое, что $\varphi_j(j,y_0)\!\downarrow$ и $l(\varphi_j(j,y_0))>j$. Определим
$$
\begin{equation*}
\zeta(j,y)=\nu(0)
\end{equation*}
\notag
$$
для каждого $y$. Если найдется пара $(m,x)$, для которой $\varphi_j(j,y_0)=(m,x)$, то, если этого еще не сделано, определим
$$
\begin{equation*}
\alpha(m,x)=\nu(1).
\end{equation*}
\notag
$$
Если найдется пятерка $(e,m,i,k,x)$, для которой $\varphi_j(j,y_0)=(e,m,i,k,x)$, то, если этого еще не сделано, определим
$$
\begin{equation*}
\alpha(e,m,i,k,y)=\nu(1)
\end{equation*}
\notag
$$
для всех $y$.
3) Пусть условия предыдущих случаев не выполняются. Тогда можем выбрать конечную последовательность вычислимых множеств $\{Y_p\}_{p\leqslant j}$ такую, что
$$
\begin{equation*}
\bigcup_{p\leqslant j}Y_p=\mathbb N
\end{equation*}
\notag
$$
и если $\varphi_j$ всюду определена, то для всех $p$ и всех $y_0,y_1\in Y_p$ выполняется
$$
\begin{equation}
l(\varphi_j(j,y_0))=l(\varphi_j(j,y_1)).
\end{equation}
\tag{3.1}
$$
Пусть для каждого $p\leqslant j$ множество $Y_p$, возможно конечное, имеет вид
$$
\begin{equation*}
Y_p=\{y^p_{0}<y^p_1<y^p_2<\dotsb\}.
\end{equation*}
\notag
$$
Определим для всех $p\leqslant j$ и $q$
$$
\begin{equation}
\zeta(j,y^p_q)=\nu(q),
\end{equation}
\tag{3.2}
$$
если $\varphi_j(j,y^p_q)\!\downarrow$ является некоторой парой $(m,x)$, и
$$
\begin{equation*}
\zeta(j,y)=\nu(0)
\end{equation*}
\notag
$$
для всех остальных $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$ выберем коконечное множество
$$
\begin{equation*}
\{x_0<x_1<x_2<\dotsb\},
\end{equation*}
\notag
$$
состоящее из всех $x$, для которых значение $\alpha(m,x)$ к настоящему моменту не определено. Положим
$$
\begin{equation}
\alpha(m,x_j)=\beta_m(j)
\end{equation}
\tag{3.3}
$$
для всех $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$, что
$$
\begin{equation}
z\in\alpha_s(e,m,i,k,y).
\end{equation}
\tag{3.7}
$$
Зафиксируем произвольное $k$, для которого активен процесс (3.4). В случае появления $s$, удовлетворяющего каждому из условий (3.5) и (3.6), выберем первое $(x+1)$, для которого значение $\alpha(e,m,i,k,x+1)$ не определено, и определим
$$
\begin{equation}
\alpha(e,m,i,k,x+1) =\nu(k),
\end{equation}
\tag{3.8}
$$
$$
\begin{equation}
\alpha(e,m,i,k,y) =\nu(1)
\end{equation}
\tag{3.9}
$$
для всех $y>x+1$.
В случае появления $s$, для которого найдется $y\leqslant s$ такое, что выполняется (3.7), определим для всех $x$ и $w$, для которых к настоящему моменту не определено значение $\alpha(e,m,i,w,x)$,
$$
\begin{equation}
\alpha(e,m,i,w,x)=\nu(1),
\end{equation}
\tag{3.10}
$$
при этом прерывая все процессы последовательных присваиваний. Покажем, что $\alpha$ удовлетворяет заключению теоремы. Лемма 3. Для любого $m$ $\alpha\not\leqslant\beta_m$. Доказательство. Выберем произвольные $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$ имеем
$$
\begin{equation*}
\lim_s\operatorname{lh}_2(e,s)=\infty.
\end{equation*}
\notag
$$
Отсюда следует, что предел $\lim_s\operatorname{lh}_1(e,m,i,s)$ конечен. В противном случае, с учетом (3.8), для всех $k$ выполнялось бы
$$
\begin{equation*}
\begin{aligned} \, \nu(k) &=\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,0) =\beta_m(f_i(e,m,i,k,0)). \end{aligned}
\end{equation*}
\notag
$$
Это противоречит тому, что $\nu\not\leqslant\beta_m$. Поскольку предел $\lim_s\operatorname{lh}_1(e,m,i,s)$ конечен, $\alpha$ не сводится к $\beta_m$ посредством $f_i$. Лемма 4. Имеем $\zeta\not\leqslant\alpha$. Доказательство. Выберем произвольное $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$, определим
$$
\begin{equation*}
\alpha(c(0,c(e,m)))=\begin{cases} R_0, &\text{если }\varphi_e(c(0,c(e,m)))\!\downarrow\ \&\ \exists\,i>0\ [F_i \mspace{-1mu} \subseteq \mspace{-1mu} \beta_m(\varphi_e(c(0,c(e,m))))], \\ R_1 &\text{в противном случае}. \end{cases}
\end{equation*}
\notag
$$
Отсюда, для любых $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$?
|
|
|
СПИСОК ЦИТИРОВАННОЙ ЛИТЕРАТУРЫ
|
|
|
1. |
С. С. Гончаров, А. Сорби, “Обобщенно-вычислимые нумерации и нетривиальные полурешетки Роджерса”, Алгебра и логика, 36:6 (1997), 621–641 |
2. |
Ю. Л. Ершов, Теория нумераций, Наука, М., 1977 |
3. |
Yu. L. Ershov, “Theory of numberings”, Handbook of Computability Theory, Stud. Logic Found. Math., 140, Elsevier, Amsterdam, 1999, 473–503 |
4. |
А. Б. Хуторецкий, “О мощности верхней полурешетки вычислимых нумераций”, Алгебра и логика, 10:5 (1971), 561–569 |
5. |
С. А. Бадаев, С. С. Гончаров, “О полурешетках Роджерса семейств арифметических множеств”, Алгебра и логика, 40:5 (2001), 507–522 |
6. |
С. А. Бадаев, С. Ю. Подзоров, “Минимальные накрытия в полурешетках Роджерса $\Sigma_n^0$-вычислимых нумераций”, Сиб. матем. журн., 43:4 (2002), 769–778 |
7. |
С. Ю. Подзоров, “О предельности наибольшего элемента полурешетки Роджерса”, Матем. тр., 7:2 (2004), 98–108 |
8. |
М. Х. Файзрахманов, “О теореме Хуторецкого для обобщённо вычислимых семейств”, Алгебра и логика, 58:4 (2019), 528–541 |
9. |
R. I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin, 1987 |
10. |
М. Х. Файзрахманов, “Минимальные обобщенно вычислимые нумерации и высокие степени”, Сиб. матем. журн., 58:3 (2017), 710–716 |
11. |
S. S. Goncharov, A. Yakhnis, V. Yakhnis, “Some effectively infinite classes of enumerations”, Ann. Pure Appl. Logic, 60:3 (1993), 207–235 |
12. |
S. A. Badaev, S. S. Goncharov, A. Sorbi, “Completeness and universality of arithmetical numberings”, Computability and Models, Springer, Boston, MA, 2003, 11–44 |
Образец цитирования:
М. Х. Файзрахманов, “О вложении первого неконструктивного ординала в полурешетки Роджерса”, Матем. заметки, 113:5 (2023), 764–774; Math. Notes, 113:5 (2023), 723–730
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm13708https://doi.org/10.4213/mzm13708 https://www.mathnet.ru/rus/mzm/v113/i5/p764
|
Статистика просмотров: |
Страница аннотации: | 167 | PDF полного текста: | 6 | HTML русской версии: | 63 | Список литературы: | 31 | Первая страница: | 16 |
|