| Математические заметки |
|
|
|
|
|
О М. Х. Файзрахманов Казанский (Приволжский) федеральный университет
Англоязычная версия:
Mathematical Notes, 2024, Volume 116, Issue 3, Pages DOI: https://doi.org/10.1134/S000143462409013X 
Реферативные базы данных:
 1. Введение и постановка задачиИдеи абстрактного изучения нумераций и нумерованных множеств были впервые высказаны Колмогоровым (именно, Колмогоров сформулировал общее понятие нумерации и сводимости нумераций) в начале 1954 г. (см. [1], [2]). Эти идеи получили развитие в исследованиях Успенского [3]–[5], что привело к созданию теории нумераций как самостоятельной области теории алгоритмов. Полученные примерно в те же годы результаты Мальцева [6]–[8] и Ершова [9]–[12] позволили сформировать теорию нумераций в ее современном виде и задали основные направления исследований на десятилетия вперед. Это привело к тому, что в конце 60-ых–начале 70-ых годов прошлого столетия были опубликованы десятки статей, посвященных изучению нумераций и нумерованных множеств (достаточно подробная библиография содержится в монографии Ершова [12] и в его статье [13]). В них по большей части в качестве нумерованных множеств выступали семейства вычислимо перечислимых (в.п.) множеств или частично вычислимых функций, а среди их нумераций рассматривались вычислимые (т.е. позволяющие по номеру в.п. множества или частично вычислимой функции семейства вычислить номер того же множества или функции в геделевской нумерации) нумерации. Во второй половине 90-ых годов прошлого столетия в монографии Ершова [14] и в совместной статье Гончарова и Сорби [15] были предложены различные естественные подходы к обобщению понятия вычислимой нумерации. В рамках одного из них стали исследоваться нумерации семейств множеств, перечислимых относительно произвольного оракула $A$, позволяющие по номеру $A$-в.п. множества семейства вычислить его же номер в геделевской нумерации $x\mapsto W^A_x$ и названные $A$-вычислимыми. Долгое время внимание исследователей привлекал случай, когда нумерованные семейства состоят из арифметических [16]–[18] или гиперарифметических [19], [20] множеств, а в качестве оракула $A$ рассматриваются скачки пустого множества $\varnothing^{(\alpha)}$. В литературе такие нумерации называются $\Sigma^0_{\alpha+1}$-вычислимыми. В середине 2010-ых годов после публикации совместной статьи Бадаева и Гончарова [21] $A$-вычислимые нумерации стали интенсивно исследоваться без каких-либо ограничений, накладываемых на оракул $A$ (см., например, [22]–[24]). Такого рода нумерации являются основным объектом исследований и в настоящей статье. В ней мы рассматриваем $A$-вычислимые нумерации, обладающие обобщенными (согласованной с введенной Дегтевым $e$-сводимостью нумераций [25]) свойствами полноты [7] и универсальности [5]. Эти свойства часто исследуются в контексте друг друга и им посвящено множество работ по теории нумераций (см., например, [10], [12], [26]–[29]). Это связано с тем, что полные нумерации, помимо прочего, удовлетворяют теореме рекурсии Клини (см. [12]), а нумерации, удовлетворяющие свойству универсальности (т.н. накрывающие или главные нумерации) содержат в себе информацию обо всех (обобщенно) вычислимых нумерациях нумеруемого семейства. В обозначениях и терминологии теории вычислимости мы придерживаемся монографии Соара [30]. Через $W_n$ обозначаем в.п. множество с геделевским номером $n$. Для частичной функции $\psi$ ее область определения обозначается как $\operatorname{dom}\psi$, а область ее значений – как $\operatorname{ran}\psi$. Используем запись $\psi(x)\!\downarrow$, если $x\in\operatorname{dom}\psi$, и $\psi(x)\!\uparrow$, в противном случае. Через $c(x,y)$ обозначаем вычислимую биекцию $\mathbb N\times\mathbb N$ на $\mathbb N$. Вместо $c(k,c(x,y))$ пишем просто $c(k,x,y)$. Конечное множество с каноническим индексом $u$ обозначаем через $D_u$. Последовательность конечных множеств $\{F_n\}_{n\in\mathbb N}$ будем называть сильно вычислимой (сильно $A$-вычислимой), если существует такая вычислимая ($A$-вычислимая) функция $f$, что $F_n=D_{f(n)}$ для всех $n$. 2. Нумерации и сводимостиВ обозначениях и терминологии теории нумераций мы придерживаемся монографии Ершова [12] и его статьи [13]. Нумерацией не более чем счетного множества $S\ne \varnothing$ называется любое сюръективное отображение $\nu\colon \mathbb N\to S$. Для произвольного множества $A$ нумерация $\nu$ семейства $A$-в.п. множеств $\mathcal R$ называется $A$-вычислимой (см. [15]), если множество пар
$$
\begin{equation*}
G_{\nu}=\{\langle x,y\rangle\in\mathbb N\times\mathbb N\colon y\in\nu(x)\}
\end{equation*}
\notag
$$
$A$-в.п. cемейства, обладающие $A$-вычислимыми нумерациями, также называются $A$-вычислимыми. Опуская оракул $A$ или полагая $A=\varnothing^{(n)}$, приходим соответственно к определениям вычислимых и $\Sigma^0_{n+1}$-вычислимых нумераций и семейств. Семейства, содержащие по крайней мере два множества, будем называть нетривиальными. Для нумераций $\nu_0$ и $\nu_1$ определим их прямую сумму $\nu_0\oplus\nu_1$, для всех $x$ положив $(\nu_0\oplus\nu_1)(2x+i)=\nu_i(x)$, $i=0,1$. Для нумераций $\mu$ некоторого подмножества $S$ и $\nu$ множества $S$, если существует вычислимая функция $f$ такая, что $\mu(x)=\nu(f(x))$ для всех $x$, то говорим, что $\mu$ сводится к $\nu$ (посредством $f$) и используем при этом обозначение $\mu\leqslant\nu$. Если для любой нумерации $\alpha\leqslant\mu$ множества $S$ выполняется $\mu\leqslant\alpha$, то нумерация $\mu$ называется минимальной. Произвольная $A$-вычислимая нумерация $\beta$ семейства $\mathcal R$ называется накрывающей или главной, если $\alpha\leqslant\beta$ для любой $A$-вычислимой нумерации $\alpha$ семейства $\mathcal R$. Если семейство $A$-в.п. множеств обладает $A$-вычислимой главной нумерацией, то оно также называется главным. Напомним, что отображение $\Phi\colon 2^{\mathbb N}\to 2^{\mathbb N}$ называется $e$-оператором (см. [31]), если существует в.п. множество $W$, называемое множеством его аксиом, такое, что для всех $X\subseteq\mathbb N$ выполняется
$$
\begin{equation*}
\Phi(X)=\bigl\{x\colon \exists\, F\ [c(x,F)\in W\ \&\ F\subseteq X]\bigr\},
\end{equation*}
\notag
$$
где $F$ – конечное множество, (здесь и далее по тексту) отождествляемое со своим каноническим индексом. В дальнейшем мы будем отождествлять $e$-операторы с множествами их аксиом и для любого $n$ через $\Phi_n$ обозначать $e$-оператор с множеством аксиом $W_n$. Для нумераций $\mu$ некоторого подмножества $S_0\subseteq S$ и $\nu$ множества $S$, если существует $e$-оператор $\Phi$ такой, что для любого $a\in S_0$ выполняется равенство то, следуя работе Дегтева [25], будем говорить, что $\mu$ $e$-сводится к $\nu$ (посредством $\Phi$) и использовать при этом обозначение $\mu\leqslant_e\nu$. Естественность этой сводимости подчеркивается в том числе тем, что полурешетка вычислимых нумераций семейства, состоящего из двух различных сравнимых по включению в.п. множеств, ассоциированная с $e$-сводимостью нумераций, изоморфна полурешетке тьюринговых степеней в.п. множеств (см. [25]), в то время как полурешетка вычислимых нумераций того же семейства, ассоциированная с классической сводимостью $\leqslant$, изоморфна полурешетке $m$-степеней в.п. множеств (см. [12]). Поскольку для любой вычислимой функции $f$ отображение
$$
\begin{equation*}
\Phi(X)=\{x\colon f(x)\in X\},\qquad X\subseteq\mathbb N,
\end{equation*}
\notag
$$
является $e$-оператором и для любых нумераций $\mu$ и $\nu$ одного и того же множества сводимость $\mu\leqslant\nu$ посредством $f$ равносильна $e$-сводимости $\mu\leqslant_e\nu$ посредством $\Phi$, имеет место импликация $\mu\leqslant\nu$ $\Longrightarrow$ $\mu\leqslant_e\nu$. Нумерация $\mu$ множества $S$ называется $e$-минимальной (см. [32]), если для любой нумерации $\alpha\leqslant_e\mu$ множества $S$ выполняется $\mu\leqslant_e\alpha$. Произвольная $A$-вычислимая нумерация $\beta$ семейства $\mathcal R$ называется $e$-главной (см. [33]), если $\alpha\leqslant_e\beta$ для любой $A$-вычислимой нумерации $\alpha$ семейства $\mathcal R$. Если семейство $A$-в.п. множеств обладает $A$-вычислимой $e$-главной нумерацией, то оно также называется $e$-главным. В дальнейшем изложении мы будем использовать обозначение $\mu$ не только для нумераций, но и для морфизмов, однако в каждом из этих случаев из контекста будет очевидно в каком качестве оно используется. 3. Полные и $e$-полные нумерацииВ данном разделе приводятся сведения, связанные с понятием полноты нумераций и его обобщениями. Пусть $S$ – не более чем счетное множество и $a$ – произвольный его элемент. Определение 1 (Мальцев [7]). Нумерация $\nu$ множества $S$ называется полной относительно $a$, если для любой частично вычислимой функции $\psi$ существует такая вычислимая функция $f$, что для всех $x$. Элемент $a$ называется особым для $\nu$. Нумерацию $\nu$ будем называть полной, если для нее существует особый элемент. Отметим, что геделевская нумерация $x\mapsto W_x$ является полной относительно $\varnothing$. Свойство ее полноты использовалось для доказательства теоремы Клини о рекурсии, теоремы Райса и т.д. Определение 2 (Ершов [11]). Нумерация $\nu$ называется предполной, если для любой частично вычислимой функции $\psi$ существует такая вычислимая функция $f$, что $\nu(f(x))=\nu(\psi(x))$ для всех $x\in\operatorname{dom}\,\psi$. Предполные нумерации могут быть охарактеризованы выполнением в них теоремы рекурсии с параметрами. А именно, имеет место следующая Теорема 1 (Ершов [12]). Нумерация $\nu$ является предполной тогда и только тогда, когда для любой двухместной частично вычислимой функции $\psi$ существует такая вычислимая функция $h$, что $\nu(\psi(x,h(x)))=\nu(h(x))$ для всех $x$, удовлетворяющих условию $\langle x,h(x)\rangle\in\operatorname{dom}\psi$. В частности, если $\nu$ предполна, то для любой вычислимой функции $f$ существует число $n$ такое, что $\nu(f(n))=\nu(n)$. Ершовым было сформулировано эквивалентное определение полной нумерации [10], [12], не использующее особого элемента. Именно оно было использовано Дегтевым для формулировки определения $e$-полной нумерации [34]. Чтобы привести эти определения и мотивировать изучение второго из них, понадобятся некоторые сведения о категориях нумерованных множеств $\mathfrak N$ и $\mathfrak N_e$ (см. [10], [12], [13], [34]). Однако читатель может пропустить эти сведения и сразу перейти к равносильному определению $e$-полноты, приведенному в последней теореме этого раздела. Объектами категорий $\mathfrak N$ и $\mathfrak N_e$ являются все нумерованные множества, т.е. пары $\mathfrak S=\langle S,\nu\rangle$, где $S\ne \varnothing$ – не более чем счетное множество и $\nu$ – его нумерация, а также “пустое” нумерованное множество $\mathbf{0}$. Существует единственный морфизм $\theta$ из $\mathbf{0}$ в любое нумерованное множество $\mathfrak S$. Если $\mathfrak S_0=\langle S_0,\nu_0\rangle$ и $\mathfrak S_1=\langle S_1,\nu_1\rangle$ – произвольные непустые нумерованные множества, то морфизмом из $\mathfrak S_0$ в $\mathfrak S_1$ в категории $\mathfrak N$ называется произвольное отображение $\mu\colon S_0\to S_1$, для которого существует вычислимая функция $f$ такая, что $\mu\nu_0=\nu_1f$. Определение морфизмов $\mathfrak N$ согласовано со сводимостью нумераций в следующем смысле: тождественное отображение $\mu\colon R\to R$ является морфизмом из $\mathfrak R_0=\langle R,\nu_0\rangle$ в $\mathfrak R_1=\langle R,\nu_1\rangle$ тогда и только тогда, когда $\nu_0\leqslant\nu_1$. Морфизмом из $\mathfrak S_0$ в $\mathfrak S_1$ в категории $\mathfrak N_e$ называется всякое отображение $\mu\colon S_0\to S_1$, для которого существует $e$-оператор $\Phi$ такой, что выполнены следующие два условия:
Пусть $\mathfrak S_0=\langle S_0,\nu_0\rangle$ и $\mathfrak S_1=\langle S_1,\nu_1\rangle$ два нумерованных множества и $\mu\colon\mathfrak S_0\to\mathfrak S_1$ – мономорфизм в $\mathfrak N$ или $\mathfrak N_e$. Тогда пару $\langle\mathfrak S_0,\mu\rangle$ назовем подобъектом $\mathfrak S_1$. Назовем подобъект $\langle\mathfrak S_0,\mu_0\rangle$ объекта $\mathfrak S$ главным, если для любого морфизма $\mu_1\colon\mathfrak S_1\to\mathfrak S$, такого, что $\mu_1(S_1)\subseteq\mu_0(S_0)$, существует единственный морфизм $\mu\colon\mathfrak S_1\to\mathfrak S_0$ с условием $\mu_0\mu=\mu_1$. Для произвольного нумерованного множества $\mathfrak S=\langle S,\nu\rangle$ подмножество $S'\subseteq S$ называется вполне перечислимым, если $\nu^{-1}(S')$ в.п. Подобъект $\langle\mathfrak S_0,\mu_0\rangle$ объекта $\mathfrak S$ назовем $e$-подобъектом, если он является главным и $\mu_0(S_0)$ является вполне перечислимым подмножеством $S$. Следующая теорема имеет место для категории $\mathfrak N$. Теорема 2 (Ершов [10], [12]). Нумерация $\nu$ множества $S$ полна тогда и только тогда, когда для любого $e$-подобъекта $\langle\mathfrak S_0,\mu_0\rangle$ любого нумерованного множества $\mathfrak S_1$ и любого морфизма $\mu\colon\mathfrak S_0\to\mathfrak S=\langle S,\nu\rangle$ существует морфизм $\mu_1\colon\mathfrak S_1\to\mathfrak S$, такой, что $\mu=\mu_1\mu_0$. Если в этой теореме заменить категорию $\mathfrak N$ на $\mathfrak N_e$ и ограничиться рассмотрением множеств $S$, для которых $|S|\geqslant 2$, то сформулированное в ней необходимое и достаточное условие полноты берется за определение $e$-полной нумерации. Далее мы будем использовать эквивалентное определение $e$-полной нумерации, которое имеет место согласно следующей теореме. Теорема 3 (Дегтев [34]). Нумерация $\nu$ множества $S$, $|S|\geqslant 2$, является $e$-полной тогда и только тогда, когда для некоторого элемента $a\in S$ имеет место сводимость $\overline{\varnothing'}\leqslant_e\nu^{-1}(a)$. Элемент $a$ называется особым для $\nu$. В этом случае также говорим, что $\nu$ $e$-полна относительно $a$. Согласно классическому результату Мальцева [7] множество номеров особого элемента полной нумерации $\nu$ множества $S$, $|S|\geqslant 2$, продуктивно. Таким образом, $\overline{\varnothing'}$ к нему $m$-сводимо и, следовательно, $\nu$ является $e$-полной. 4. О $e$-главных нумерацияхОдним из направлений исследований $A$-вычислимых семейств является изучение их абсолютных, т.е. не зависящих от оракула $A$, свойств [23]. Согласно классическому результату теории нумераций любое конечное семейство в.п. множеств обладает вычислимой главной нумерацией (см. [12]). В [23] установлено, что для конечных семейств, содержащих наименьший по включению элемент, это свойство является абсолютным, однако для произвольных конечных семейств это неверно. Так в работе [17] доказано, что если в качестве $A$ взять любой скачок $\varnothing^{(n+1)}$, то существует конечное семейство $A$-в.п. множеств, не обладающее $A$-вычислимой главной нумерацией. В следующей теореме доказывается, что, заменив сводимость $\leqslant$ на $\leqslant_e$, исходное свойство принимает абсолютный характер. Теорема 4. Для произвольного множества $A$ каждое конечное семейство $A$-в.п. множеств обладает $A$-вычислимой $e$-главной нумерацией. Доказательство. Пусть $\mathcal R=\{R_0,\dots,R_n\}$ – конечное семейство $A$-в.п. множеств. Не ограничивая общности, будем считать, что $n>0$ и $R_0\ne R_1$. Как и в доказательстве предложения 4 из гл. I § 2 [12], зафиксируем набор конечных множеств $F_0,\dots,F_n$, такой, что для любых $i,j\leqslant n$ выполняются условия Определим $A$-вычислимую $e$-главную нумерацию $\nu$ семейства $\mathcal R$ следующим образом. Для всех $x$, $s$ полагаем если для любого $i\leqslant n$ имеет место $F_i\not\subseteq W^A_{x,s}$. В противном случае, определим множество $P$, а затем положим Положим $P_0=R_i$ для наименьшего $i\leqslant n$ такого, что $F_i\subseteq W^A_{x,s}$. Для каждого $t$ если существует $j\leqslant n$, для которого где $P_t=R_i$, то выберем наименьшее такое $j$ и определим $P_{t+1}=R_j$. Если нужного $j$ не существует, то оставляем $P_{t+1}=P_t$. Пусть $P=\bigcup_tP_t$. Отметим, что $P_t\subseteq P_{t+1}$ для всех $t$, поэтому нумерация $\nu$ $A$-вычислима. Кроме того, по определению $P$ имеем, что $P=W^A_x$, если $W^A_x\in\mathcal R$.
Покажем, что нумерация $\nu$ является $e$-главной. Для этого выберем произвольную $A$-вычислимую нумерацию $\mu$ семейства $\mathcal R$ и вычислимую функцию $f$ такую, что $\mu(x)=W^A_{f(x)}$ для всех $x$. Тогда $\mu\leqslant\nu$ посредством $e$-оператора где $F^s_x=\{2 c(f(x),s),2 c(f(x),s)+1\}$. В самом деле, если $F_i\not\subseteq W^A_{f(x),s}$ для всех $i\leqslant n$, то В противном случае Этим завершается доказательство теоремы.Из результатов работ [21], [35] следует, что тьюринговая полнота произвольного множества $A$ равносильна полноте каждой $A$-вычислимой главной нумерации. Согласно следующему предложению равносильные тьюринговой полноте свойства полноты и главности нумераций можно заменить на проще проверяемые свойства $e$-полноты и $e$-главности. Доказательство. Сначала докажем импликацию (1 $\Longrightarrow$ 2). Пусть $\varnothing'\leqslant_TA$ и $\mathcal R$ – нетривиальное семейство с $A$-вычислимой $e$-главной нумерацией $\nu$. Для произвольного элемента $B\in\mathcal R$ выберем отличный от него элемент $C\in\mathcal R$ и определим $A$-вычислимую нумерацию $\mu$, положив для всех $x$ Поскольку нумерация $\nu$ является $e$-главной, имеем $\mu\oplus\nu\leqslant_e\nu$ и, следовательно, $\mu\leqslant_e\nu$. Пусть $\mu\leqslant_e\nu$ посредством $e$-оператора $\Phi$. Для каждого $x$ выполняется Отсюда следует, что $\nu$ $e$-полна относительно произвольно выбранного $B\in\mathcal R$.
Импликация ($2$ $\Longrightarrow$ $ 3$) очевидна. Докажем импликацию ($3$ $\Longrightarrow$ $1$). Пусть $B$ и $C$ – два несравнимых по включению $A$-в.п. множества. Согласно теореме 4 семейство $\mathcal R=\{B,C\}$ обладает $e$-главной нумерацией $\nu$. Не ограничивая общности, будем считать, что $\nu$ $e$-полна относительно $B$. Зафиксируем элемент $b\in B\setminus C$. Выберем $e$-оператор $\Phi$, для которого Поскольку $\overline{\varnothing'}$ является $A$-в.п. Отсюда следует, что $\varnothing'\leqslant_TA$. Этим завершается доказательство предложения.5. Предполные и $e$-полные нумерацииКак известно, особый элемент полной вычислимой нумерации всегда является наименьшим по включению элементом нумеруемого ей семейства (см., например, [26]). Согласно следующему предложению вычислимые нумерации нетривиальных семейств могут быть $e$-полными относительно всех элементов нумерованного семейства. В нем формулируется достаточное для этого условие на вычислимое семейство, которое совпадает с достаточным условием существования однозначных вычислимых нумераций, полученным Мальцевым [8]. Предложение 2. Пусть $A$ – произвольное множество, $\mathcal R$ – $A$-вычислимое семейство и $\{F_n\}_{n\in\mathbb N}$ – сильно $A$-вычислимая последовательность конечных множеств, принадлежащих $\mathcal R$, удовлетворяющая условиям: Тогда семейство $\mathcal R$ обладает $A$-вычислимой нумерацией $\nu$, которая $e$-полна относительно каждого из его элементов. Доказательство. Зафиксируем некоторую $A$-вычислимую нумерацию $\mu$ семейства $\mathcal R$ и сильно $A$-вычислимую двойную последовательность конечных множеств $\{\mu_s(x)\}_{s,x\in\mathbb N}$, удовлетворяющую для всех $s$ и $x$ условиям
$$
\begin{equation*}
\mu_s(x)\subseteq\mu_{s+1}(x),\qquad \bigcup_t\mu_t(x)=\mu(x).
\end{equation*}
\notag
$$
Для всех $x$, $y$ положим
$$
\begin{equation*}
\nu(c(x,y))=\begin{cases} \mu(x), & \text{если}\ y\notin\varnothing', \\ F_n, & \text{если}\ y\in\varnothing', \end{cases}
\end{equation*}
\notag
$$
где $n$ – такой наименьший индекс, что $\mu_s(x)\subsetneq F_n$ для наименьшего $s$, для которого $y\in\varnothing'_s$. Нетрудно видеть, что $\nu$ вычислима и нумерует все семейство $\mathcal R$. Выберем произвольно $x$ и покажем, что она $e$-полна относительно $\mu(x)$. Если $\mu(x)$ бесконечно, то для всех $y$ имеет место
$$
\begin{equation}
\nu(c(x,y))=\mu(x)\quad\Longleftrightarrow\quad y\notin\varnothing'
\end{equation}
\tag{5.1}
$$
и, стало быть, $\nu$ $e$-полна относительно $\mu(x)$. Если же $\mu(x)$ конечно, то зафиксируем $s$, для которого $\mu(x)=\mu_s(x)$. Тогда (5.1) выполняется для всех $y\notin\varnothing'_s$. Таким образом, снова получаем, что $\nu$ $e$-полна относительно $\mu(x)$. Этим завершается доказательство предложения. Следствие 1. Для любого множества $A$ семейства всех $A$-в.п. множеств и всех конечных множеств обладают $A$-вычислимыми нумерациями, которые $e$-полны относительно всех их элементов. По своим определениям каждая полная нумерация является как $e$-полной относительно того же особого элемента так и предполной. Естественно возникает вопрос о взаимосвязи последних двух свойств, который рассматривается в последующих следствии и теореме. Следствие 2. Существует семейство, обладающее $e$-полной относительно всех своих элементов вычислимой нумерацией, которое не имеет предполных вычислимых нумераций. Доказательство. Пусть
$$
\begin{equation*}
\mathcal R=\{F\colon F\ -\ \text{конечно}\ \&\ |F\cap\{0,1\}|=1\}.
\end{equation*}
\notag
$$
Поскольку $\mathcal R$ удовлетворяет условиям предложения 2 при $A=\varnothing$, оно обладает $e$-полной относительно всех своих элементов вычислимой нумерацией. Но для каждой из его вычислимых нумераций $\mu$ вычислимая функция
$$
\begin{equation*}
f(x)=\begin{cases} x_0, & \text{если}\ 1\in\mu(x), \\ x_1, & \text{если}\ 0\in\mu(x), \end{cases}
\end{equation*}
\notag
$$
где $\mu(x_0)=\{0\}$ и $\mu(x_1)=\{1\}$, для всех $x$ удовлетворяет условию $\mu(f(x))\ne \mu(x)$. По теореме 1 получаем, что $\mu$ не является предполной. В силу произвольности выбора нумерации $\mu$ следствие доказано. Теорема 5. Пусть $\varnothing'\nleqslant_TA$. Существует бесконечное семейство, обладающее предполной $A$-вычислимой нумерацией, которое не имеет $e$-полных относительно каких-либо из его элементов $A$-вычислимых нумераций. Доказательство. В доказательстве теоремы 6 работы [21] для произвольного множества $A$ было построено бесконечное семейство $\mathcal R$, все элементы которого непустые и попарно не пересекаются, обладающее $A$-вычислимой главной нумерацией $\nu$, такой, что для всех $x$, $y$ имеет место $x\in\nu(x)$ и если $W^A_x\in\mathcal R$, то $\nu(x)=W^A_x$, а также $y\in\nu(x)$, если $y$ – первый элемент, перечисленный в $W^A_x$. Напомним его построение. Пусть $\theta$ – $A$-в.п. отношение эквивалентности на $\mathbb N$, порожденное множеством всех пар $\langle x,y\rangle$, для которых $y$ является первым элементом, перечисленным в $W^A_x$. Тогда семейство $\mathcal R$ полагается равным фактормножеству $\mathbb N_{/\theta}$, а его $A$-вычислимая главная нумерация $\nu$ определяется как где $x\in\mathbb N$ и $[x]_{\theta}$ – класс $\theta$-эквивалентности элемента $x$. В доказательстве теоремы 6 [21] устанавливается, что $\nu(x)\ne \nu(y)$ для любых различных $x$, $y$, таких, что $W^A_x=W^A_y=\varnothing$. Поэтому $\mathcal R$ бесконечно.
Покажем, что $\nu$ предполна. Для этого выберем произвольную частично вычислимую функцию $\psi$ и определим вычислимую функцию $f$, для всех $x$ положив
$$
\begin{equation*}
W^A_{f(x)}=\begin{cases} \{\psi(x)\}, & \text{если}\ \psi(x)\!\downarrow\,, \\ \varnothing, & \text{если}\ \psi(x)\!\uparrow. \end{cases}
\end{equation*}
\notag
$$
Для каждого $x\in\operatorname{dom}\psi$ имеем Стало быть, $\nu$ предполна.
Предположим, что $\mu$ – $A$-вычислимая нумерация семейства $\mathcal R$, $e$-полная относительно некоторого $\nu(z)$. Выберем $e$-оператор $\Phi$, для которого Поскольку все элементы $\mathcal R$ попарно не пересекаются и $z\in\nu(z)$, имеем, что Отсюда следует, что $\overline{\varnothing'}$ является $A$-в.п. и, следовательно, $\varnothing'\leqslant_TA$. Этим завершается доказательство теоремы.Из результатов работы [27] следует, что если $\varnothing'\leqslant_TA$, то любое $A$-вычислимое семейство обладает полной относительно произвольного его заранее выбранного элемента $A$-вычислимой нумерацией (этим свойством обладают, например, пополнения [11] $A$-вычислимых нумераций). В следующей теореме доказывается, что это условие является и достаточным для тьюринговой полноты множества $A$, причем вместо полных нумераций можно рассматривать $e$-полные. Теорема 6. Для множества $A$ следующие условия эквивалентны: Доказательство. Сначала докажем импликацию ($1$ $\Longrightarrow$ $ 2$). Для множества $\varnothing'\leqslant_TA$ и бесконечного $A$-вычислимого семейства $\mathcal R$ построим его $A$-вычислимую не $e$-главную нумерацию $\nu$, $e$-полную относительно каждого элемента $\mathcal R$. Чтобы $\nu$ не была $e$-главной, одновременно с его построением будем определять $A$-вычислимую нумерацию $\mu$ семейства $\mathcal R$ такую, что $\mu\nleqslant_e\nu$.
Зафиксируем два различных множества $B,C\in\mathcal R$. Пусть последовательность $\{c(x_n,F_n)\}_{n\in\mathbb N}$ для всех $n$ удовлетворяет условиям
$$
\begin{equation*}
M=\{n\colon c(x_n,F_n)\notin W_n\}=\{n_0<n_1<n_2<\dotsb\}
\end{equation*}
\notag
$$
бесконечно, поскольку если $W_n=\varnothing$, то $n\in M$. Пусть $\alpha$ – некоторая $A$-вычислимая нумерация $\mathcal R$. Для всех $n\notin M$ и всех $z\in F_n$ определим $\nu(z)=B$ и $\mu(x_n)=C$ (ниже мы покажем, что тем самым обеспечивается $\mu\nleqslant_e\nu$). Для каждого $i$ определим $\mu(x_{n_i})=\alpha(i)$ и на всех оставшихся номерах $x$ положим $\mu(x)=B$. Для каждой тройки $x$, $p$, $q$ если значение $\nu(c(x,p,q))$ не определено, то положим
$$
\begin{equation*}
\nu(c(x,p,q))=\begin{cases} \alpha(p), & \text{если}\ x\notin\varnothing', \\ \alpha(q), & \text{если}\ x\in\varnothing'. \end{cases}
\end{equation*}
\notag
$$
По определению $\nu$ и выбору последовательности $\{c(x_n,F_n)\}_{n\in\mathbb N}$ имеем, что для всех $x$ и всех (за исключением конечного числа) $d=c(p,q)$ либо $x\notin\varnothing'$ и $\nu(c(x,p,q))=\alpha(p)$, либо $x\in\varnothing'$ и $\nu(c(x,p,q))=\alpha(q)$. Отсюда следует, что если $\alpha(p)\ne \alpha(q)$, то $\nu$ $e$-полна относительно $\alpha(p)$. Таким образом, $\nu$ $e$-полна относительно каждого элемента $\mathcal R$.
Покажем, что $\mu\nleqslant_e\nu$. Предположим, напротив, $\mu\leqslant_e\nu$ посредством $\Phi_n$. Поскольку $\mu$ нумерует все бесконечное семейство $\mathcal R$, а для всех $d$ семейство конечно, получаем, что существует $c(x,F)\in W_n$, удовлетворяющее (5.2). Отсюда, $c(x_n,F_n)\in W_n$. Поскольку для всех $z\in F_n$ имеет место приходим к противоречию с $e$-сводимостью $\mu$ к $\nu$ посредством $\Phi_n$.Импликация ($2$ $\Longrightarrow$ $ 1$) сразу вытекает из теоремы 5. Докажем импликацию ($2$ $\Longrightarrow$ $3$). Если нетривиальное $A$-вычислимое семейство $\mathcal R$ бесконечно, то справедливость этой импликации очевидна. Если же $\mathcal R$ конечно, то согласно теореме 4 оно обладает $A$-вычислимой $e$-главной нумерацией, которая согласно предложению 1 и сводимости $\varnothing'\leqslant_TA$ $e$-полна относительно каждого его элемента. Импликация ($3$ $\Longrightarrow$ $ 4$) очевидна. В доказательстве импликации ($3$ $\Longrightarrow$ $ 1$) предложения 1 показано, что существование $e$-полной $A$-вычислимой нумерации семейства, состоящего их двух несравнимых по включению $A$-в.п. множеств, влечет $\varnothing'\leqslant_T A$. Отсюда сразу следует справедливость импликации ($4$ $\Longrightarrow$ $1$). Этим завершается доказательство теоремы. 6. Минимальная $e$-полная нумерацияОдним из отличительных и особо важных свойств $\Sigma^0_{n+2}$-вычислимых семейств является, как было доказано в работе Бадаева и Гончарова [16], существование их минимальных $\Sigma^0_{n+2}$-вычислимых нумераций (причем если семейство бесконечно, то оно имеет бесконечно много попарно не сводимых друг к другу минимальных $\Sigma^0_{n+2}$-вычислимых нумераций). В [27] дискутировалось может ли для бесконечных семейств алгоритмическая “выразительность” таких минимальных нумераций быть усилена свойством полноты, а в [29] было установлено, что любое бесконечное $\Sigma^0_{n+3}$-вычислимое семейство обладает полной относительно любого наперед выбранного элемента минимальной $\Sigma^0_{n+3}$-вычислимой нумерацией. Последнее утверждение остается верным и после замены оракула $\varnothing^{(n+2)}$ на любое множество $A$, для которого $\varnothing''\leqslant_TA$. Однако для оракулов $A$, таких, что $\varnothing'\leqslant_TA$, этот вопрос остается открытым. Тем не менее для таких оракулов $A$ “выразительность” минимальных (и $e$-минимальных) $A$-вычислимых нумерацией может быть усилена свойством их $e$-полноты. Теорема 7. Пусть $\varnothing'\leqslant_TA$ и пусть $\mathcal R$ – бесконечное $A$-вычислимое семейство. Тогда для любого $B\in\mathcal R$ семейство $\mathcal R$ обладает $e$-полной относительно $B$ $A$-вычислимой нумерацией $\mu$, такой, что $\mu\leqslant\nu$ для каждой его нумерации $\nu\leqslant_e\mu$. Доказательство. Выберем $A$-вычислимую нумерацию $\alpha$ семейства $\mathcal R$, для которой Определим монотонно неубывающую по включению последовательность $\{\mu_n\}_{n\in\mathbb N}$ частичных отображений $\mathbb N$ в $\mathcal R$, такую, что $\mu=\bigcup_m\mu_m$ является нумерацией $\mathcal R$, а также последовательности вычислимых функций $\{f_n\}_{n\in\mathbb N}$ и $A$-вычислимых функций $\{g_n\}_{n\in\mathbb N}$, удовлетворяющих для всех $n$ условиям:
$$
\begin{equation*}
\mu_0(2x+1)=\begin{cases} B, & \text{если}\ x\notin\varnothing', \\ \alpha(1), & \text{если}\ x\in\varnothing'. \end{cases}
\end{equation*}
\notag
$$
Таким образом, получаем, что $\overline{\varnothing'}\leqslant_e\mu^{-1}(B)$ и, следовательно, нумерация $\mu$ будет $e$-полной относительно $B$. Положим $f_0(y)=\{y\}$ для всех $y$ и $g_0(s)$ равным геделевскому номеру $f_0$ для всех $s$. Нетрудно видеть, что при $n=0$ условия 1–4 выполняются. Согласно (6.1), если для некоторой нумерации $\nu$ семейства $\mathcal R$ имеет место $\nu\leqslant_e\mu$ посредством $\Phi_0$, то $\mu\leqslant\nu$ посредством тождественной функции. Стало быть, условие 5 также выполняется. Предположим по индукции, что для некоторого $n$ определены частичное отображение $\mu_n$, вычислимая функция $f_n$ и $A$-вычислимая функция $g_n$, которые удовлетворяют условиям 1–5. Построим функции $f_{n+1}$ и $g_{n+1}$, а затем определим частичное отображение $\mu_{n+1}$. Построение. Шаг 0. Положим функции $f^0_{n+1}$ и $g^0_{n+1}$ нигде не определенными. Шаг $s+1$. Если не существует числа $d=c(x,F,t)$, удовлетворяющего условиям
$$
\begin{equation*}
\psi(w)=\begin{cases} f^{s+1}_{n+1}(w), & \text{если}\ w\in\operatorname{dom}f^{s+1}_{n+1}, \\ \varphi_{g^s_n(s)}(2(y+w-z)), & \text{если}\ w\notin\operatorname{dom} f^{s+1}_{n+1}. \end{cases}
\end{equation*}
\notag
$$
Предположим, что число $d=c(x,F,t)$, удовлетворяющее условиям i)–iii), существует. В этом случае зафиксируем наименьшее такое $d$ и начнем выполнять последовательность действий, нацеленную на выполнение условия
$$
\begin{equation*}
\forall\,a\in F\quad\forall\,b\in F \quad[\mu(a)=\mu(b)],
\end{equation*}
\notag
$$
которое, в свою очередь, будет использоваться для доказательства сводимости $\mu\,{\leqslant}\,\nu$, при условии, что $\nu$ является нумерацией $\mathcal R$, $e$-сводимой к $\mu$ посредством $\Phi_{n+1}$. Если то полагаем $g^{s+1}_{n+1}(s+1)=g^{s}_{n+1}(s)$ и переходим к следующему шагу. Иначе, выберем наименьшие $z\notin\operatorname{dom}f^s_{n+1}$ и $y$, такое, что
$$
\begin{equation*}
z>0\quad\Longrightarrow\quad\min f_n(2y)>\max f^{s}_{n+1}(z-1),
\end{equation*}
\notag
$$
а также наименьшее $k$, для которого
$$
\begin{equation}
F\subseteq f_n(2y)\cup f_n(2(y+1))\cup\dots\cup f_n(2(y+k)),
\end{equation}
\tag{6.3}
$$
и определим
$$
\begin{equation}
f^{s+1}_{n+1}(z)=f_n(2y)\cup f_n(2(y+1))\cup \dots\cup f_n(2(y+k)).
\end{equation}
\tag{6.4}
$$
Если $f^{s+1}_{n+1}(z)\ne \varphi_{g^{s}_{n+1}(s)}(z)$, то положим $g^{s+1}_{n+1}(s+1)$ равным геделевскому номеру частично вычислимой функции $\psi$, определенной следующим образом. Для всех $w\in\operatorname{dom}\,f^{s+1}_{n+1}$ полагаем Далее, для всех $u>z$ если $\psi(u-1)\!\downarrow$, то выберем наименьшее $c(v,D,t)$ (если оно существует), удовлетворяющее условиям
$$
\begin{equation}
\psi(u)=\varphi_{g^s_n(s)}(2y)\cup\varphi_{g^s_n(s)}(2y+1) \cup\dots \cup\varphi_{g^s_n(s)}(2y+k)
\end{equation}
\tag{6.5}
$$
для наибольшего $y$, такого, что
$$
\begin{equation*}
\psi(u-1)\cap \varphi_{g^s_n(s)}(2(y-1))\!\downarrow\,\ne \varnothing \quad \&\quad \psi(u-1)\cap \varphi_{g^s_n(s)}(2y)\!\downarrow\,=\varnothing,
\end{equation*}
\notag
$$
и наименьшего $k$, для которого
$$
\begin{equation}
D\subseteq\varphi_{g^s_n(s)}(2y)\!\downarrow\cup\,\varphi_{g^s_n(s)}(2(y+1)) \!\downarrow\cup\dots\cup\varphi_{g^s_n(s)}(2(y+k))\!\downarrow,
\end{equation}
\tag{6.6}
$$
если такие $y$ и $k$ существуют. Этим завершается описание построения. Согласно присваиваниям (6.2), (6.4) построения имеем, что для всех $z$ существуют $y$, $k$ и $l>0$, такие, что
$$
\begin{equation*}
\begin{gathered} \, f_{n+1}(z)=f_n(2y)\cup f_n(2(y+1))\cup \dots\cup f_n(2(y+k)), \\ f_{n+1}(z+1)=f_n(2(y+k+1))\cup f_n(2(y+k+2))\cup \dots\cup f_n(2(y+k+l)). \end{gathered}
\end{equation*}
\notag
$$
Отсюда следует, что $f_{n+1}$ удовлетворяет условию 2 (здесь и далее мы рассматриваем условия 1–5 с $n+1$ вместо $n$). Стало быть, следующее определение частичного отображения $\mu_{n+1}$:
$$
\begin{equation*}
\mu_{n+1}(x)=\begin{cases} \mu_n(x), & \text{если}\ x\in\operatorname{dom}\mu_n, \\ \alpha(n), & \text{если}\ x\in f_{n+1}(1), \\ \mu_0(2y+1), & \text{если}\ x\in f_{n+1}(2y+3), \end{cases}
\end{equation*}
\notag
$$
корректно. Отметим, что $\mu_{n+1}$ удовлетворяет условиям 1 и 3. Покажем что оставшиеся условия 4 и 5 также выполнены. Доказательство. Используя индукционное предположение, выберем $s'_0$ такое, что $f_{n}=\varphi_{g_{n}(s)}$ для всех $s\geqslant s'_0$. Если на некотором шаге $s_0+1$, для которого $s_0\geqslant s'_0$, не существует числа $d$, удовлетворяющего условиям i)–iii), то на каждом шаге $s+1$, где $s\geqslant s_0$, определяется одна и та же функция $\psi$ такая, что Таким образом, условие 4 выполняется.
Предположим, что на каждом шаге $s+1$, для которого $s\geqslant s'_0$, существует $d$, удовлетворяющее условиям i)–iii). Стало быть, на каждом из этих шагов существует $c(v,D,t)$, удовлетворяющее условиям (a)–(c). В силу проверок (6.3), (6.6) и присваиваний (6.4), (6.5) опять приходим к справедливости равенств (6.7). Таким образом, условие 4 снова выполняется. Этим завершается доказательство леммы. Лемма 2. Пусть $\nu$ – нумерация семейства $\mathcal R$ такая, что $\nu\leqslant_e\mu$ посредством $\Phi_n$. Тогда $\mu\leqslant\nu$. Доказательство. Как уже отмечалось, при $n=0$ лемма верна. Покажем, что она верна для любого индекса вида $n+1$. Пусть $\nu$ – нумерация $\mathcal R$ такая, что $\nu\leqslant_e\mu$ посредством $\Phi_{n+1}$. Тогда на всех (за исключением конечного числа) шагах $s+1$ существует число $d$, удовлетворяющее условиям i)–iii). В силу проверок (6.3) и присваиваний (6.4) имеем, что для всех (за исключением конечного числа) $z$ существует $c(x,F)\in W_{n+1}$ такое, что $F\subseteq f_{n+1}(z)$. Согласно определению нумерации $\mu$ для всех $a,b\in f_{n+1}(z)$ имеет место $\mu(a)=\mu(b)$. Отсюда следует, что $\mu(a)=\nu(x)$ для всех $a\in f(z)$. Кроме того, нетрудно видеть, что такое $c(x,F)$ может быть найдено эффективно по $z$. Согласно определению отображений $\mu_{0},\dots,\mu_{n+1}$ имеем, что эффективно по каждому $x\in\operatorname{dom}\,\mu_n$ мы можем либо указать $m<n$, для которого $\mu_n(x)=\alpha(m)$, либо $y$, для которого $\mu_n(x)=\mu_0(2y+1)$, а, следовательно, и $a\in\bigcup_zf_{n+1}(z)$, для которого $\mu_{n+1}(a)=\mu_0(2y+1)=\mu_n(x)$. Таким образом, $\mu\leqslant\nu$. Для завершения доказательства теоремы остается заметить, что по своему определению отображение $\mu$ является всюду определенным и, поскольку для всех $n$ имеем место $\alpha(n)\in\operatorname{ran}\mu_{n+1}$, нумерует все семейство $\mathcal R$. 
Цитирование в формате AMSBIB
\RBibitem{Fai24} |
|
||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|