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

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

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



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






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


Математические заметки, 2023, том 113, выпуск 5, страницы 764–774
DOI: https://doi.org/10.4213/mzm13708
(Mi mzm13708)
 

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

О вложении первого неконструктивного ординала в полурешетки Роджерса

М. Х. Файзрахманов

Казанский (Приволжский) федеральный университет
Список литературы:
Аннотация: Рассматривается вопрос о вложении первого неконструктивного ординала в полурешетки Роджерса семейств арифметических множеств. Доказывается, что для любого бесконечного семейства арифметических множеств первый неконструктивный ординал вкладывается над любым минимальным элементом его полурешетки Роджерса. Устанавливается, что если семейство является главным или конечным, то первый неконструктивный ординал вкладывается над любым ненаибольшим элементом его полурешетки Роджерса.
Библиография: 12 названий.
Ключевые слова: нумерация, полурешетка Роджерса, первый неконструктивный ординал.
Финансовая поддержка Номер гранта
Российский научный фонд 22-21-20024
Министерство науки и высшего образования Российской Федерации 075-02-2023-944
Работа поддержана грантом Российского научного фонда (проект № 22-21-20024, https://rscf.ru/project/22-21-20024/) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2023-944).
Поступило: 29.08.2022
Исправленный вариант: 17.10.2022
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 5, Pages 723–730
DOI: https://doi.org/10.1134/S0001434623050127
Реферативные базы данных:
Тип публикации: Статья
УДК: 510.5
MSC: 03D45

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  mathnet
2. Ю. Л. Ершов, Теория нумераций, Наука, М., 1977  mathscinet
3. Yu. L. Ershov, “Theory of numberings”, Handbook of Computability Theory, Stud. Logic Found. Math., 140, Elsevier, Amsterdam, 1999, 473–503  mathscinet  zmath
4. А. Б. Хуторецкий, “О мощности верхней полурешетки вычислимых нумераций”, Алгебра и логика, 10:5 (1971), 561–569  mathnet  mathscinet
5. С. А. Бадаев, С. С. Гончаров, “О полурешетках Роджерса семейств арифметических множеств”, Алгебра и логика, 40:5 (2001), 507–522  mathnet  mathscinet  zmath
6. С. А. Бадаев, С. Ю. Подзоров, “Минимальные накрытия в полурешетках Роджерса $\Sigma_n^0$-вычислимых нумераций”, Сиб. матем. журн., 43:4 (2002), 769–778  mathnet  mathscinet  zmath
7. С. Ю. Подзоров, “О предельности наибольшего элемента полурешетки Роджерса”, Матем. тр., 7:2 (2004), 98–108  mathnet  mathscinet  zmath
8. М. Х. Файзрахманов, “О теореме Хуторецкого для обобщённо вычислимых семейств”, Алгебра и логика, 58:4 (2019), 528–541  mathnet  crossref
9. R. I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, Berlin, 1987  mathscinet
10. М. Х. Файзрахманов, “Минимальные обобщенно вычислимые нумерации и высокие степени”, Сиб. матем. журн., 58:3 (2017), 710–716  mathnet  crossref
11. S. S. Goncharov, A. Yakhnis, V. Yakhnis, “Some effectively infinite classes of enumerations”, Ann. Pure Appl. Logic, 60:3 (1993), 207–235  crossref  mathscinet
12. S. A. Badaev, S. S. Goncharov, A. Sorbi, “Completeness and universality of arithmetical numberings”, Computability and Models, Springer, Boston, MA, 2003, 11–44  mathscinet

Образец цитирования: М. Х. Файзрахманов, “О вложении первого неконструктивного ординала в полурешетки Роджерса”, Матем. заметки, 113:5 (2023), 764–774; Math. Notes, 113:5 (2023), 723–730
Цитирование в формате AMSBIB
\RBibitem{Fai23}
\by М.~Х.~Файзрахманов
\paper О вложении первого неконструктивного ординала в~полурешетки Роджерса
\jour Матем. заметки
\yr 2023
\vol 113
\issue 5
\pages 764--774
\mathnet{http://mi.mathnet.ru/mzm13708}
\crossref{https://doi.org/10.4213/mzm13708}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4602434}
\transl
\jour Math. Notes
\yr 2023
\vol 113
\issue 5
\pages 723--730
\crossref{https://doi.org/10.1134/S0001434623050127}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85163177660}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/mzm13708
  • https://doi.org/10.4213/mzm13708
  • https://www.mathnet.ru/rus/mzm/v113/i5/p764
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические заметки Mathematical Notes
    Статистика просмотров:
    Страница аннотации:167
    PDF полного текста:6
    HTML русской версии:63
    Список литературы:31
    Первая страница:16
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024