
\documentclass[10pt]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}

\usepackage{cite}
\usepackage[unicode, pdftex]{hyperref}

\def\udcs{510.5} %Здесь автор определяет УДК своей работы
\def\mscs{03D45} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{lemma}{Лемма}
\newtheorem{lemma1}{Лемма}
\newtheorem{lemma2}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem*{theorem1}{Теорема}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}
\newtheorem{question}{Вопрос}
\theoremstyle{definition}
\newtheorem{definition}{Определение}
\newtheorem{remark}{Замечание}

\newcommand{\nc}[1]{\mathrm{#1}}
\newcommand{\mc}[1]{\mathcal{#1}}
\newcommand{\mb}[1]{\mathbb{#1}}
\newcommand{\mf}[1]{\mathfrak{#1}}
\newcommand{\N}{\mathbb N}
\newcommand{\dg}[1]{\mathbf{#1}}
\newcommand{\ang}[1]{\big\langle #1\big\rangle}
\newcommand{\nl}{\nolimits}
\newcommand{\dfn}{\stackrel{\textrm{\clap{\scriptsize def}}}{=}}

\def\logo{{\bf\huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}

\def\semrtop
     {
  \vbox{
     \noindent\logo
     \hspace{80mm}\raisebox{1ex}{ISSN 1813-3304 }

     \vspace{5mm}

     \begin{center}
     {\huge СИБИРСКИЕ \ ЭЛЕКТРОННЫЕ} \\[2mm]
     {\huge МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ} \\[2mm]
     {\large Siberian Electronic Mathematical Reports} \\[1mm]
     {\LARGE\tt{http://semr.math.nsc.ru}}\\[0.5mm]
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
     \vspace{-3mm}
     \noindent
     \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa} \\
     \hline\hline
     \end{tabular}

     \vspace{1mm}
     {\flushleft\it Том 16, стр. 144--144 (2019) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.33048/semi.2019.16.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[Эффективно бесконечные классы нумераций]{Эффективно бесконечные классы нумераций и теоремы о неподвижной точке}
\author{{М.Х. ФАЙЗРАХМАНОВ}}%
\address{Marat Khaidarovich Faizrahmanov
\newline\hphantom{iii} Volga Region Scientific-Educational Centre of Mathematics,
\newline\hphantom{iii} Kremlevskaya str., 35,
\newline\hphantom{iii} Kazan Federal University,
\newline\hphantom{iii} Kremlevskaya str., 18,
\newline\hphantom{iii} 420008, Kazan, Russia}%
\email{marat.faizrahmanov@gmail.com}%

\thanks{\sc Faizrahmanov, M.Kh.,
Effectively infinite classes of numberings and fixed point theorems}
\thanks{\copyright \ 2015 Файзрахманов М.Х.}
\thanks{\rm Работа поддержана грантом Российского научного фонда (проект 23-21-00181) и
выполнена в рамках реализации программы развития Научно-образовательного
математического центра Приволжского федерального округа (соглашение 075-02-2022-882)
}
\thanks{\it Поступила 1 января 2015 г., опубликована 31 декабря 2015 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } 
In this paper, we prove a sufficient condition for the effective infinity of classes of complete and precomplete numberings, as well as numberings satisfying the recursion theorem, of computable families.
A sufficient condition for the effective infinity of classes of non-precomplete numberings of computable families satisfying the recursion theorem is also obtained. These conditions are satisfied by the families of all c.e. sets and graphs of all partially computable functions. For finite families of c.e. sets, we prove a criterion for the effective infinity of classes of their numberings that satisfy the recursion theorem. Finally, it is established that the classes of complete and precomplete numberings of finite families of c.e. sets are not effectively infinite.
\medskip

\noindent{\bf Keywords:} computable numbering, complete numbering, precomplete numbering, recursion theorem, effective infinity.
 \end{quote}
}


\section{Введение}

Статья имеет целью изучение особенностей распределения вычислимых нумераций семейств вычислимо перечислимых (в.п.) множеств и 
частично вычислимых (ч.в.) функций, принадлежащих распространенным в теории нумераций и теории вычислимости классам нумераций, 
среди всех нумераций этих семейств. Такое распределение изучается с позиции разных <<уровней>> бесконечности
классов нумераций, выделенных в совместной работе С.С.~Гончарова, А.~Яхниса и В.~Яхниса~\cite{GYY93}.
Так в процитированной работе кроме классического понятия бесконечности рассматривались и его эффективные версии.
А именно, для бесконечных классов нумераций рассматривались вопросы существования бесконечных вычислимых последовательностей 
попарно неэквивалентных друг другу их элементов и их \textit{эффективная бесконечность}. Последняя была введена и впервые изучена
в той же статье~\cite{GYY93} и имеет место, если по любой вычислимой последовательности нумераций, принадлежащих заданному классу, можно
эффективно указать вычислимую нумерацию, принадлежащую тому же классу и не эквивалентную ни одной из нумераций
этой последовательности.
В~\cite{GYY93} также получена серия достаточных условий эффективной бесконечности таких фундаментальных классов нумераций, как классы однозначных, разрешимых, минимальных,
позитивных (и неразрешимых), негативных (и неразрешимых) нумераций вычислимых семейств, которым удовлетворяет в том числе
и семейство всех в.п. множеств.

В настоящей статье изучаются вопросы эффективной бесконечности классов нумераций, удовлетворяющих теореме рекурсии с той или иной степенью равномерности.
К ним, кроме нумераций, удовлетворяющих теореме о неподвижной точке в ее классической постановке, относятся более тонкие классы \textit{полных} и \textit{предполных} нумераций, введенных соответственно в работах А.И.~Мальцева~\cite{M63,M71} 
и Ю.Л.~Ершова~\cite{E69a, E77}, которые с разных позиций интенсивно исследуются со второй половины прошлого века по настоящее время
(см., напр., работы~\cite{E69b, E70, S88, BGS03, BT19, A21}). В обзоре В.Л.~Селиванова~\cite{S21} можно найти все необходимые сведения,
большую часть ключевых результатов и подробную библиографию по этим классам нумераций.
Отметим, что в теории нумераций изучаются и другие естественные классы нумераций~\cite{P73,B91,F22}, удовлетворяющие разным формам теоремы рекурсии,
исследование которых входит за рамки настоящей статьи.

В разделе~\ref{s1} настоящей статьи доказывается (теорема~\ref{cprf}) достаточное условие эффективной бесконечности классов $K_c(\mc A)$, $K_p(\mc A)$ и $K_r(\mc A)$  соответственно полных (относительно
наименьшего по включению элемента $\mc A$), предполных нумераций
и нумераций, удовлетворяющих теореме рекурсии, вычислимого семейства $\mc A$.
 Этому условию удовлетворяют семейства всех в.п. множеств $\mc E$ и всех ч.в. функций $\mc F$.
Там же приводится достаточное условие полноты каждой предполной вычислимой нумерации заданного семейства (предложение~\ref{pc}), которому так же удовлетворяют семейства $\mc E$ и $\mc F$.

В разделе~\ref{s2} доказывается (теорема~\ref{rp}), что для любого нетривиального (неодноэлементного) вычислимого семейства $\mc A$, обладающего разрешимой вычислимой нумерацией
и содержащего наименьший по включению элемент, класс $K_r(\mc A)\setminus K_p(\mc A)$ эффективно бесконечен.

В разделе~\ref{s3} изучаются классы $K_c(\mc A)$, $K_p(\mc A)$ и $K_r(\mc A)$ конечных семейств в.п. множеств $\mc A$.
В нем доказываются критерий эффективной бесконечности классов $K_r(\mc A)$ (предложение~\ref{cr}) и
необходимое условие эффективной бесконечности классов $K_c(\mc B)$ и $K_p(\mc B)$ вычислимых семейств $\mc B$ (теорема~\ref{nonei}),
которому не удовлетворяет никакое конечное семейство в.п. множеств. Также в этом разделе получено достаточное условие существования бесконечного числа попарно неэквивалентных
полных вычислимых нумераций конечных семейств в.п. множеств (предложение~\ref{inf}).

\section{Предварительные сведения}

В обозначениях и терминологии мы придерживаемся монографий Ю.Л. Ершова~\cite{E77} (и его статьи~\cite{E99}) и Р.И. Соара~\cite{S87,S16}.
Через $\varphi_e$ и $W_e$ будем обозначать соответственно ч.в. функцию и в.п. множество с геделевским номером~$e$.
Для частичной функции $\psi$ ее область определения обозначается как $\nc{dom}\,\psi$.
Используем запись $\psi(x)\downarrow$, если $x\in\nc{dom}\,\psi$, и $\psi(x)\uparrow$ в противном случае.
Определим $\nc{Tot}\dfn\{e:W_e=\N\}$.
Через $c(x,y)$ будем обозначать вычислимую биекцию $\N\times\N$ на $\N$.

Для не более чем счетного непустого множества $S$ любое сюръективное отображение $\alpha:\N\to S$ называется его
\textit{нумерацией}. Множество всех нумераций $S$ будем обозначать как $H(S)$. Если $\alpha, \beta\in H(S)$, то говорим,
что $\alpha$ \textit{сводится} к $\beta$ (в этом случае используется обозначение $\alpha\leqslant\beta$), если существует такая вычислимая функция $f$, что $\alpha(x)=\beta(f(x))$ для всех $x$. Если $\alpha\leqslant\beta$ и $\beta\leqslant\alpha$, то нумерации $\alpha$ и $\beta$ называются \textit{эквивалентными} (в этом случае
используется запись $\alpha\equiv\beta$).
Для нумераций $\alpha_0,\alpha_1\in H(S)$ их \textit{прямая сумма} $\alpha_0\oplus\alpha_1\in H(S)$ определяется следующим образом:
$$(\alpha_0\oplus\alpha_1)(2x+i)=\alpha_i(x),\ i=0,1.$$
Назовем нумерацию $\alpha$ \textit{разрешимой}, если ее \textit{нумерационная эквивалентность}
$$\eta_{\alpha}=\{\ang{x,y}\in\N\times\N:\alpha(x)=\alpha(y)\}$$
вычислима, и \textit{однозначной}, если она совпадает с отношением равенства.
\begin{definition}[А.И. Мальцев~\cite{M63}]\label{def1}
Нумерация $\alpha\in H(S)$ называется \textit{полной относительно особого элемента} $b\in S$, если для любой ч.в. функции $\psi$
существует вычислимая функция $h$ такая, что для всех $x$ выполняется
$$
\alpha(h(x))=
\begin{cases}
\alpha(\psi(x)), & \mbox{если}\ \psi(x)\downarrow,\cr
b, & \mbox{если}\ \psi(x)\uparrow.
\end{cases}
$$
\end{definition}
\noindent Заметим, что геделевская нумерация семейства всех в.п. множеств $\alpha:x\mapsto W_x$ является полной относительно $\emptyset\in\mc E$.
Равносильным условием полноты нумерации $\alpha\in H(S)$ относительно особого элемента $b\in S$ является существование
двухместной вычислимой функции $f$ такой, что для всех $e,x$ выполняется
$$
\alpha(f(e,x))=
\begin{cases}
\alpha(\varphi_e(x)), & \mbox{если}\ \varphi_e(x)\downarrow,\cr
b, & \mbox{если}\ \varphi_e(x)\uparrow.
\end{cases}
$$
Его можно получить, взяв в определении~\ref{def1} частично вычислимую функцию $\psi$, определенную для всех $e,x$ равенством
$\psi(c(e,x))=\varphi_e(x)$, и положив $f(e,x)=h(c(e,x))$.

\begin{definition}[Ю.Л. Ершов~\cite{E69a}]\label{def2}
Нумерация $\alpha$ называется \textit{предполной}, если для любой ч.в. функции $\psi$
существует вычислимая функция $h$ такая, что $\nu(h(x))=\nu(\psi(x))$ для всех $x\in\nc{dom}\,\psi$.
\end{definition}
\noindent Взяв в определении~\ref{def2} частично вычислимую функцию $\psi$, определенную для всех $e,x$ равенством
$\psi(c(e,x))=\varphi_e(x)$, и положив $f(e,x)=h(c(e,x))$, получим, что нумерация $\alpha$ является предполной тогда и только тогда,
когда существует двухместная вычислимая функция $f$ такая, что  $\nu(f(e,x))=\nu(\varphi_e(x))$ для всех $e,x$, удовлетворяющих
условию $x\in\nc{dom}\,\varphi_e$. Следующая характеризация предполных нумераций в терминах неподвижных точек подчеркивает естественность и важность двух последних понятий.
\begin{theorem1}[Ю.Л. Ершов~\cite{E75}]
Нумерация $\alpha$ является предполной тогда и только тогда, когда для любой двухместной ч.в. функции $\psi$
существует такая вычислимая функция $h$, что $\alpha(\psi(x,h(x)))=\alpha(h(x))$ для всех $x$, удовлетворяющих
условию $\ang{x,h(x)}\in\nc{dom}\,\psi$.
\end{theorem1}
\noindent Будем говорить, что нумерация $\alpha$ \textit{удовлетворяет теореме рекурсии}, если для
любой вычислимой функции $f$ существует такое $n$, что $\alpha(f(n))=\alpha(n)$.

Нумерация $\alpha$ семейства в.п. множеств $\mc A$ называется \textit{вычислимой}, если множество пар
$$G_\alpha=\{\ang{x,y}\in\N\times\N:y\in\alpha(x)\}$$
в.п. Для каждого $e$ обозначим через $\alpha_e$ вычислимую нумерацию $\alpha$, для которой $G_{\alpha}=W_e$.
Семейства, обладающие вычислимыми нумерациями, будем так же называть \textit{вычислимыми}.
Класс нумераций $C\subseteq H(\mc A)$ назовем \textit{вычислимым}, если существует в.п. множество $H$ такое, что
$$C=\{\alpha_e:e\in H\}.$$
Если $H=W_x$, то класс $C$ будем обозначать как $C_x$. Нетрудно видеть, что вычислимость непустого класса $C\subseteq H(\mc A)$ равносильно существованию
вычислимой функции $d$, для которой
$$C=\{\alpha_{d(x)}:x\in\N\}.$$
Вычислимую нумерацию $\alpha\in H(\mc A)$ назовем \textit{главной}, если $\beta\leqslant\alpha$ для всех вычислимых нумераций $\beta\in H(\mc A)$.

Все возникающие в дальнейшем изложении нумерации $\alpha$ будут нумеровать семейства в.п. множеств.
\begin{remark}
Если вычислимая нумерация $\alpha$  семейства $\mc A$ полна относительно $B\in\mc A$, то $B$ является наименьшим по 
включению элементом $\mc A$.
\end{remark}
\noindent
В самом деле, предположим, напротив, что существует вычислимая нумерация~$\alpha$ семейства $\mc A$, полная 
относительно некоторого не наименьшего по включению элемента $B\in\mc A$.
Выберем числа $y$ и $z$ такие, что $B\not\subseteq\alpha(y)$ и $z\in B\setminus\alpha(y)$.
Определим ч.в. функцию $\psi$, положив для всех $x$
$$
\psi(x)=
\begin{cases}
y, & \mbox{если}\ x\in\emptyset',\cr
\mbox{не определено}, & \mbox{если}\ x\not\in\emptyset'.
\end{cases}
$$
Тогда для вычислимой функции $h$ из определения~\ref{def1} выполняется
$$z\in\alpha(h(x))\Leftrightarrow x\not\in \emptyset'$$
для каждого $x\in\N$. 
Отсюда $\overline{\emptyset'}$ в.п., что противоречит его невычислимости.
Поэтому все полные нумерации, возникающие в дальнейшем изложении, будут полными относительно наименьших
по включению элементов нумерованных ими семейств, и мы не будем явно это указывать.

Через $K_c(\mc A)$, $K_p(\mc A)$ и $K_r(\mc A)$ будем обозначать соответственно классы всех полных, предполных нумераций семейства $\mc A$
и нумераций $\mc A$, удовлетворяющих теореме рекурсии.
\begin{definition}[С.С. Гончаров, А. Яхнис, В. Яхнис~\cite{GYY93}]
Класс нумераций $K\subseteq H(\mc A)$ называется \textit{эффективно бесконечным}, если существует
ч.в. функция~$\gamma$ такая, что для каждого $x$, если $C_x\subseteq K$, то $\gamma(x)\downarrow$, $\alpha_{\gamma(x)}\in K$ и 
$\alpha_{\gamma(x)}\not\equiv\xi$ для всех $\xi\in C_x$.
\end{definition}
\noindent Эффективная бесконечность классов нумераций схожа с продуктивностью~\cite{S87} подмножеств $\N$ и, как демонстрируется в~\cite{GYY93},
сопоставима с ней по значимости.


\section{Семейства с эффективно бесконечными классами $K_c(\mc A)$, $K_p(\mc A)$~и~$K_r(\mc A)$}\label{s1}

В настоящем разделе доказывается достаточное условие эффективной бесконечности классов $K_c(\mc A)$, $K_p(\mc A)$ и $K_r(\mc A)$,
из которого выводится эффективная бесконечность этих классов как при $\mc A=\mc E$, так и при $\mc A=\mc F$.

\begin{theorem}\label{cprf}
Пусть $\mc A$~--- семейство, содержащее наименьший по включению элемент, обладающее однозначной вычислимой нумерацией и удовлетворяющее для каждого конечного множества $F$
условию
\begin{equation}\label{sv}
\mc R_F\dfn\{X\in\mc A:F\subseteq X\}\not=\emptyset\Rightarrow\mc R_F\ \mbox{бесконечно}.
\end{equation}
Тогда существует вычислимая функция $g$ такая, что для всех~$x$, если $C_x\subseteq H(\mc A)$, то $\alpha_{g(x)}\in K_c(\mc A)$ и
$\xi\not\leqslant\alpha_{g(x)}$ какова бы ни была нумерация $\xi\in C_x$.
\end{theorem}
\begin{proof}
Достаточно доказать, что по любой вычислимой последовательности $\{\beta_k\}_{k\in\N}$ нумераций семейства $\mc A$ (т.е. последовательности, для
которой $\beta_k=\alpha_{f(k)}$, $k\in\N$, для некоторой вычислимой функции $f$) можно эффективно (по индексу $f$)
построить такую полную вычислимую нумерацию $\alpha$ семейства $\mc A$, что $\beta_k\not\leqslant\alpha$ для всех $k$.
Для этого нам понадобится в.п. отношение эквивалентности $\eta$ на $\N$, порожденное множеством пар
$$\{\ang{c(e,x),\varphi_e(x)}:\varphi_e(x)\downarrow,\ e,x\in\N\}.$$
 Через $\{\eta_s\}_{s\in\N}$ будем обозначать его вычислимое перечисление.
Используя теорему рекурсии, выберем бесконечную последовательность попарно различных чисел $\{n_i\}_{i\in\N}$ такую, что
$$\varphi_{n_i}(0)=c(n_i,0)$$
для всех $i$. Для любых различных $i$ и $j$ имеем
$$\ang{c(n_i,0),c(n_j,0)}\not\in\eta.$$
Это следует из того, что для всех $e, x, i$ тогда и только тогда выполняется $\ang{c(e,x),c(n_i,0)}\in\eta$, когда найдется конечная последовательность
$$c(e,x)=c(e_0,x_0), c(e_1,x_1),\dots,c(e_k,x_k)=c(n_i,0),$$
для которой
$$\varphi_{e_j}(x_j)=c(e_{j+1},x_{j+1})$$
для всех $j<k$.
Определим в.п. множество $A$, положив
$$A=\bigcup_i[c(n_i,0)]_{\eta},$$
где через $[y]_{\eta}$ обозначается класс эквивалентности $\eta$ элемента $y$.

Перейдем к построению нужной нумерации $\alpha$. Для этого выберем однозначную вычислимую нумерацию $\mu$ семейства
$\mc A$ такую, что $\mu(0)$~--- наименьший по включению элемент $\mc A$, и сильно вычислимую двойную последовательность $\{\mu_s(x)\}_{s,x\in\N}$, для которой $\mu_t(x)\subseteq\mu_{t+1}(x)$ и
$\mu(x)=\bigcup_s\mu_s(x)$ для всех $t, x$. Также выберем сильно вычислимую тройную последовательность $\{\beta_{k,s}(x)\}_{s,x\in\N}$, для которой $\beta_{k,t}(x)\subseteq\beta_{k,t+1}(x)$ и
$\beta_k(x)=\bigcup_s\beta_{k,s}(x)$ для всех $k, t, x$.
В построении $\alpha$ для всех $y$ и $z$ таких, что $y,z\in[c(n_i,0)]_{\eta}$ для некоторого  $i$, 
выполним равенство $\alpha(y)=\alpha(z)$, а для всех $x\not\in A$ выполним $\alpha(x)=\mu(0)$. Тогда $\alpha$ будет полной,
поскольку для всех $e, x$ будет справедливо
\begin{equation}\label{comp}
\alpha(c(e,x))=
\begin{cases}
\alpha(\varphi_e(x)), & \mbox{если}\ \varphi_e(x)\downarrow,\cr
\mu(0), & \mbox{если}\ \varphi_e(x)\uparrow.
\end{cases}
\end{equation}
Через $l$ будем обозначать функцию, определенную для всех $k,e,s$ равенством
$$
l(k,e,s+1)=\max\{y\leqslant s:\forall x\leqslant y\,[\varphi_{e,s}(x)\downarrow\,\&\,\beta_{k,s}(x)\upharpoonright y=\alpha_s(\varphi_{e,s}(x))\upharpoonright y]\}
$$
(для определенности положим $l(e,k,0)=0$). В конце построения будем иметь, что для всех $k, e$ существует предел $\lim_sl(k,e,s)$ и
$$
\beta_k=\alpha\circ\varphi_e\Leftrightarrow\lim_sl(k,e,s)=\infty.
$$
Одновременно с построением нумерации $\alpha$ будут определяться функции $m, r, h$, которые будут использоваться для выполнения условия
 $$\beta_k\not=\alpha\circ\varphi_e$$
 для всех $k,e$, и функции  $q$ и снова $h$, которые будут использоваться для выполнения $\alpha(\N)=\mc A$.


 
 \medskip\noindent\textit{Построение}
 
 \medskip\noindent Шаг $0$. Полагаем $\alpha_0(c(n_i,0))=\emptyset$ для всех $i$, и $\alpha_0(x)=\mu(0)$ для всех $x$, таких что
 $$x\not\in\{c(n_i,0):i\in\N\}.$$
  Для всех $k,e$ определим
 $$m(k,e,0)=r(k,e,0)=q(k,0)=h(k,0)=0.$$
 На каждом шаге $s+1$ для всех $k,e,x$ будем полагать $m(k,e,s+1)=m(k,e,s)$, $r(k,e,s+1)=r(k,e,s)$, $q(k,s+1)=q(k,s)$,
 $h(k,s+1)=h(k,s)$ и $\alpha_{s+1}(x)=\alpha_s(x)$, если явно не указано обратное. Это же соглашение мы будем использовать и в последующих построениях.
 
  \medskip\noindent Шаг $s+1=3c(c(k,e),u)+1$. Выполняем $\beta_k\not=\alpha\circ\varphi_e$. Если $l(k,e,s+1)>m(k,e,s)$, то
   для каждого $i\leqslant s$, удовлетворяющего условиям
 $$\forall c(p,d)<c(k,e)\,[r(p,d,s)<i],$$
 $$\forall b\leqslant c(k,e)\,[q(b,s)<i],$$
 $$h(i,s)\leqslant 2i,$$
выберем $z>2i$ и $t$, для которых
$$\alpha_s(c(n_i,0))\subseteq\mu_t(z),$$
и определим 
$$h(i,s+1)=z.$$
  Отметим, что в силу справедливости для каждого конечного множества $F$ условия~(\ref{sv}), требуемые $t$ и $z$ существуют.
  Также положим
  $$m(k,e,s+1)=r(k,e,s+1)=s.$$

 
 \medskip\noindent Шаг $s+1=3c(z,u)+2$. Выполняем  $\mu(z)\in\alpha(\N)$.
Если не существует $i\leqslant q(z,s)$ такого, что $h(i,s)=z$ и 
  $$\forall c(p,d)< z\,[r(p,d,s)<i],$$
 $$\forall b<z\,[q(b,s)<i],$$
 то выберем наименьшее $i$, удовлетворяющее последним двум условиям, для которого
 $$\alpha_s(c(n_i,0))=\emptyset,$$
 и определим
 $$h(i,s+1)=z,$$
 $$q(z,s+1)=i.$$
 Если требуемое $i$ существует, то переходим к следующему шагу.
 
  \medskip\noindent Шаг $s+1=3c(c(x,i),u)+3$. Выполняем $\alpha(c(n_i,0))=\alpha(x)$, если $\ang{x,c(n_i,0)}\in\eta$, и
  $\alpha(\N)=\{\alpha(c(n_j,0)):j\in\N\}$.
  Полагаем 
  $$\alpha_{s+1}(x)=\alpha_s(x)\cup\alpha_s(c(n_i,0)),$$
  если $\ang{x,c(n_i,0)}\in\eta_s$, и
  $$\alpha_{s+1}(c(n_i,0))=\alpha_{s}(c(n_i,0))\cup\mu_s(h(i,s)).$$
  Этим завершается построение. Для каждого $x$ положим $\alpha(x)=\bigcup_s\alpha_s(x)$. Покажем, что нумерация $\alpha$ является искомой.
  
  \begin{lemma1}
  Для всех $p,d$ существует конечный предел $\lim_sr(p,d,s)$.
  \end{lemma1}
  \begin{proof}
  Поскольку для любых $p$ и $d$ функция $s\mapsto r(p,d,s)$ не убывает, предел $\lim_sr(k,e,s)$, возможно бесконечный, существует.
  Предположим, что, для некоторых $k,e$ выполняется $$\lim_sr(k,e,s)=\infty.$$
  Будем считать, что такое $c(k,e)$ наименьшее из возможных.
Согласно шагам $s+1=3c(c(k,e),u)+1$, $u\in\N$, построения, выполняется также 
$$\lim_sl(k,e,s)=\infty.$$
  Тогда $\beta_k=\alpha\circ\varphi_e$ и действия, выполняемые на шагах $s+1=3c(c(k,e),u)+1$ и $s+1=3c(c(x,i),u)+3$, $i,u\in\N$,
 влекут, что $\mc A\setminus\alpha(\N)$ бесконечно. Действительно,  
 если на шаге $s+1=3c(c(k,e),u)+1$ для некоторого $i$ определяется $h(i,s+1)=z$,
 то $z>2i$ и $q(z,s+1)=i$. Отсюда и из построения следует, что для всех, за исключением лишь конечного числа, $i$ выполняется $\alpha(c(n_i,0))=\mu(z)=\alpha(x)$ для некоторого $z>2i$
 и для любого $x$ такого, что $\ang{x,c(n_i,0)}\in\eta$.
 Учитывая однозначность нумерации $\mu$, приходим к бесконечности разности $\mc A\setminus\alpha(\N)$.
  Таким образом, получаем противоречие с равенством $\mc A=\beta_k(\N)$.
  \end{proof}
\noindent Из конечности для всех $k,e$ предела $\lim_sr(k,e,s)$ следует выполнение 
$$\beta_k\not=\alpha\circ\varphi_e,$$
а также конечность пределов $\lim_sq(k,s)$ и $\lim_sh(k,s)$.
По определению $\alpha$ имеем, что $\alpha(\N)\subseteq\mc A$.
Действия, выполняемые на шагах $s+1=3c(z,u)+2$ и $s+1=3c(c(x,i),u)+3$, влекут, что для каждого $z$ найдется $i$, для которого
$$\alpha(c(n_i,0))=\mu(z)$$ (отсюда, $\mc A\subseteq\alpha(\N)$), и для всех $x,y$ таких, что $\ang{x,y}\in\eta$, выполняется 
$$\alpha(x)=\alpha(y).$$
Наконец, поскольку в построении $\alpha$ затрагиваются только номера $x\in A$, имеем $\alpha(y)=\mu(0)$ для всех $y\not\in A$. 
Таким образом, для всех $e,x$ выполняется~(\ref{comp}).
Этим
завершается доказательство теоремы.
\end{proof}

\begin{corollary}	
Пусть $\mc A$~--- семейство всех в.п. множеств или (графиков) всех ч.в. функций. Тогда классы $K_c(\mc A)$, $K_p(\mc A)$ и $K_r(\mc A)$ эффективно бесконечны.
\end{corollary}
\begin{proof}
Согласно~\cite{F58} семейство $\mc A$ обладает однозначной вычислимой нумерацией.
Поскольку оно также для каждого конечного множества $F$ удовлетворяет условию~(\ref{sv}), применяя теорему~\ref{cprf},
получаем заключение следствия.
\end{proof}

\noindent Из следующего предложения вытекает, что  класс $K_p(\mc A)\setminus K_c(\mc A)$ не является эффективно бесконечным
как при $\mc A=\mc E$, так и при $\mc A=\mc F$.

\begin{proposition}\label{pc}
Пусть $\mc A$~--- вычислимое семейство, для которого $\emptyset\in\mc A$. Тогда любая его предполная вычислимая нумерация является полной.
\end{proposition}
\begin{proof}
Пусть $\nu$~--- предполная вычислимая нумерация семейства $\mc A$. Не ограничивая общности, будем считать, что $\nu(0)=\emptyset$.
Выберем вычислимую двухместную функцию $f$ такую, что для всех $e$ и всех $x\in\nc{dom}\,\varphi_e$
выполняется равенство
$$\nu(f(e,x))=\nu(\varphi_e(x)).$$
Пусть $\psi$~--- произвольная частично вычислимая функция. Определим частично вычислимую функцию $\varphi_n$, считая по теореме рекурсии
изначально известным ее индекс $n$. Для произвольного $x$ выберем (если оно существует) наименьшее~$s$, удовлетворяющее одному из двух условий:
\begin{enumerate}
\item[1)] $\nu_s(f(n,x))\not=\emptyset$ и $\varphi_{n,s}(x)\uparrow$,
\item[2)] предыдущее условие не выполняется и $\psi_s(x)\downarrow$.
\end{enumerate}
Если выбранное для $x$ наименьшее $s$ удовлетворяет первому условию, то определим  $\varphi_n(x)=0$, а если второму, то полагаем $\varphi_n(x)=\psi(x)$.
Если не существует~$s$, удовлетворяющего одному из этих условий, то положим $\varphi_n(x)\uparrow$.
Покажем, что для всех $x$ справедливо
$$
\nu(f(n,x))=\begin{cases}
\nu(\psi(x)), & \mbox{если}\ \psi(x)\downarrow,\cr
\emptyset, & \mbox{если}\ \psi(x)\uparrow.
\end{cases}
$$
Предположим, напротив, существует $x$, не удовлетворяющий этому условию. Тогда либо $\psi(x)\uparrow$ и $\nu(f(n,x))\not=\emptyset$, либо $\psi(x)\downarrow$ и 
$\nu(f(n,x))\not=\nu(\psi(x))$. В каждом из этих случаев приходим к тому, что $\nu(f(n,x))\not=\emptyset$ и $\varphi_n(x)=0$.
Тогда
$$\emptyset\not=\nu(f(n,x))=\nu(\varphi_n(x))=\nu(0)=\emptyset.$$
Из полученного противоречия следует, что любой $x$ удовлетворяет требуемому условию. В силу произвольности выбора $\psi$, нумерация $\nu$ полна.
\end{proof}

\noindent Нетрудно видеть, что в предложении~\ref{pc} условие <<$\emptyset\in\mc A$>> можно заменить на <<$B\in\mc A$>>, где $B$~---
вычислимый и наименьший по включению элемент $\mc A$.
Если семейство $\mc A$ не содержит вычислимый наименьший по включению элемент, то приходим к следующему вопросу.
\begin{question}
Существует ли вычислимое семейство $\mc A$, для которого класс $K_p(\mc A)\setminus K_c(\mc A)$ эффективно бесконечен?
\end{question}

\section{Семейства с эффективно бесконечными классами $K_r(\mc A)\setminus K_p(\mc A)$}\label{s2}

В настоящем разделе доказывается достаточное условие эффективной бесконечности классов $K_r(\mc A)\setminus K_p(\mc A)$,
которому так же удовлетворяют семейства $\mc E$ и $\mc F$.

\begin{theorem}\label{rp}
Пусть $\mc A$~--- семейство, содержащее наименьший по включению элемент и обладающее разрешимой вычислимой нумерацией.
Тогда существует такая вычислимая функция $g$, что для всех $x$, если $C_x\subseteq H(\mc A)$ и $C_x$ не содержит разрешимых нумераций,
то $\alpha_{g(x)}\in K_r(\mc A)\setminus K_p(\mc A)$ и
$\xi\not\leqslant\alpha_{g(x)}$ какова бы ни была нумерация $\xi\in C_x$.
\end{theorem}

\begin{proof}
Достаточно доказать, что по любой вычислимой последовательности $\{\beta_k\}_{k\in\N}$ неразрешимых нумераций семейства $\mc A$  можно эффективно 
построить такую удовлетворяющую теореме рекурсии непредполную вычислимую нумерацию $\alpha$ семейства $\mc A$, что $\beta_k\not\leqslant\alpha$ для всех $k$.

Определим функцию $l(k,e,s)$ как в доказательстве теоремы~\ref{cprf}. Одновременно с построением нумерации $\alpha$ будут определяться функции $m, r, h, q$, которые будут использоваться  для выполнения
 тех же условий, что и в доказательстве теоремы~\ref{cprf}, а также функции $v$ и $w$ для выполнения в $\alpha$ теоремы рекурсии и условия ее непредполноты
 соответственно. 
 Также, чтобы $\alpha$ не была предполной, построим частично вычислимую функцию $\psi$ такую, что для каждой вычислимой функции $f$ будет существовать $x$, для которого
 $\psi(x)\downarrow$ и $\alpha(\psi(x))\not=\alpha(f(x))$.
 Пусть $\mu$~--- разрешимая вычислимая нумерация семейства~$\mc A$ такая, что $\mu(0)$~--- наименьший по включению
 элемент $\mc A$.
 
 \medskip\noindent\textit{Построение}
 
 \medskip\noindent Шаг $0$.  Полагаем $\alpha_0(x)=\mu(0)$ и $\psi_0(x)\uparrow$ для всех $x$.
  Для всех $k,e$ определим
 $$m(k,e,0)=r(k,e,0)=q(k,0)=h(k,0)=v(k,0)=w(k,0)=0.$$
 
  
  \medskip\noindent Шаг $s+1=5c(c(k,e),u)+1$. Выполняем $\beta_k\not=\alpha\circ\varphi_e$. Если $l(k,e,s+1)>m(k,e,s)$, то
полагаем $m(k,e,s+1)=r(k,e,s+1)=s$.

 \medskip\noindent Шаг $s+1=5c(z,u)+2$. Выполняем  $\mu(z)\in\alpha(\N)$.
Если не существует $x\leqslant q(z,s)$ такого, что $h(x,s)=z$ и 
  \begin{equation}\label{cov1}
    \forall c(p,d)< z\,[r(p,d,s)<x],
  \end{equation}
  \begin{equation}\label{cov2} 
  \forall b<z\,[\max\{q(b,s),v(b,s),w(b,s)\}<x],
\end{equation} 
 то выберем наименьшее $x$, удовлетворяющее последним двум условиям, для которого
 \begin{equation}\label{cov3} 
 h(x,s)=0,
\end{equation} 
 и определим
 \begin{equation}\label{cov4} 
 h(x,s+1)=z,\ q(z,s+1)=x.
 \end{equation} 
 Если требуемое $x$ существует, то переходим к следующему шагу.

 \medskip\noindent Шаг $s+1=5c(e,u)+3$. Выполняем  $\exists n\,[\alpha(\varphi_e(n))=\alpha(n)]$, если $\varphi_e$ всюду определена.
 Если не существует $n\leqslant v(e,s)$ такого, что
\begin{equation}\label{r1}
 \forall c(p,d)<e\,[r(p,d,s)<n],
\end{equation}
\begin{equation}\label{r2}
 \forall b\leqslant e\,[q(b,s)<n],
 \end{equation}
\begin{equation}\label{r3}
\forall b<e\,[\max\{v(b,s),w(b,s)\}<n],
\end{equation}
$$
\varphi_{e,s}(n)\uparrow\,\vee\,\varphi_{e,s}(n)\downarrow\leqslant v(e,s)\,\&\,h(n,s)=h(\varphi_e(n),s),
$$
то выберем наименьшее $n$, удовлетворяющее условиям (\ref{r1})--(\ref{r3}), для которого
$h(n,s)=0$, и определим
\begin{equation}\label{r4}
h(n,s+1)=h(\varphi_{e}(n),s),\ v(e,s+1)=\max\{n,\varphi_{e,s}(n)\},
\end{equation}
(полагаем  $v(e,s+1)=n$, если $\varphi_{e,s}(n)\uparrow$).
Если нужное $n$ существует, то переходим к следующему шагу.

 \medskip\noindent Шаг $s+1=5c(e,u)+4$. Выполняем  $\exists x\,[\psi(x)\downarrow\,\&\,\alpha(\psi(x))\not=\alpha(\varphi_e(x))]$, если $\varphi_e$ всюду определена.
 Если существует $y$ такое, что 
 $$\psi_s(x)\downarrow\leqslant w(e,s),\ \varphi_{e,s}(x)\downarrow\leqslant w(e,s),\ \mu(h(\psi(x),s))\not=\mu(h(\varphi_{e}(x),s))$$
 при $x=c(y,e)$, то переходим к следующему шагу.
 В противном случае, если существует $y$, для которого $\varphi_{e,s}(x)\downarrow$ при $x=c(y,e)$, то выбираем
 первое $z$, удовлетворяющее условиям
 \begin{equation}\label{p1}
 \forall c(p,d)<e\,[r(p,d,s)<z],
\end{equation}
\begin{equation}\label{p2}
 \forall b\leqslant e\,[\max\{q(b,s),v(b,s)<z],
 \end{equation}
\begin{equation}\label{p3}
\forall b<e\,[w(b,s)<z],
\end{equation}
\begin{equation}\label{p4}
h(z,s)=0,
\end{equation}
и полагаем
\begin{equation}\label{p5}
\psi_{s+1}(x)=z,\ w(e,s+1)=\max\{z,\varphi_{e}(x)\},\  h(z,s+1)=a,
\end{equation}
для наименьшего $a$ такого, что $\mu(a)\not=\mu(h(\varphi_{e,s}(x),s))$.
Если требуемого $y$ не существует, то переходим к следующему шагу.

 \medskip\noindent Шаг $s+1=5c(x,u)+5$. Полагаем 
 \begin{equation}\label{cov5}
  \alpha_{s+1}(x)=\mu_{s}(h(x,s)).
 \end{equation}
 \noindent Этим завершается построение. Положим $\alpha(x)=\bigcup_s\alpha_s(x)$ для каждого $x$ и $\psi=\bigcup_s\psi_s$. Покажем, что нумерация $\alpha$ является искомой.
 \begin{lemma2}
  Для всех $p,d$ существует конечный предел $\lim_sr(p,d,s)$.
  \end{lemma2}
  \begin{proof}
  Поскольку для любых $p$ и $d$ функция $s\mapsto r(p,d,s)$ не убывает, предел $\lim_sr(k,e,s)$, возможно бесконечный, существует.
  Предположим, что, для некоторых $k,e$ выполняется $$\lim_sr(k,e,s)=\infty.$$
  Будем считать, что такое $c(k,e)$ наименьшее из возможных.
Согласно шагам $s+1=5c(c(k,e),u)+1$, $u\in\N$, построения, выполняется также 
$$\lim_sl(k,e,s)=\infty.$$
  Тогда $\beta_k=\alpha\circ\varphi_e$.
Для любых, за исключением лишь конечного числа, пар~$\ang{s, x}$ выполняется  
$$x\leqslant r(k,e,s)\Rightarrow \alpha(x)=\mu(h(x,s)).$$
Поскольку нумерация $\mu$ разрешима, то разрешимой будет и нумерация $\beta_k$.
Таким образом, приходим к противоречию с выбором нумераций $\{\beta_i\}_{i\in\N}$.
  \end{proof}
  
  \noindent Из конечности для всех $k,e$ предела $\lim_sr(k,e,s)$ следует выполнение 
$$\beta_k\not=\alpha\circ\varphi_e,$$
а также конечность пределов $\lim_sq(k,s)$, $\lim_sh(k,s)$, $\lim_sv(k,s)$, $\lim_sw(k,s)$.

По определению $\alpha$ имеем, что $\alpha(\N)\subseteq\mc A$.
Поскольку для каждого $z$ существуют сколь угодно большие $x$ и $s$, удовлетворяющие условиям (\ref{cov1})--(\ref{cov3}), а все перечисленные выше пределы конечны,
в силу действий (\ref{cov4}) и (\ref{cov5}) имеем $\mc A\subseteq\alpha(\N)$.

Покажем, что $\alpha$ удовлетворяет теореме рекурсии. Пусть $\varphi_e$ всюду определена. Поскольку существуют сколь угодно большие $n$ и $s$,
удовлетворяющие условиям (\ref{r1})--(\ref{r3}), в силу конечности тех же пределов и действий (\ref{r4}) получаем существование $n$, для которого $\alpha(\varphi_e(n))=\alpha(n)$.

Осталось показать, что нумерация $\alpha$ не является предполной. Пусть $\varphi_e$ всюду определена. Поскольку существует бесконечно много $z$, удовлетворяющих
условиям (\ref{p1})--(\ref{p4}), в силу действий (\ref{p5}) приходим к существованию $x\in\nc{dom}\,\psi$, для которого $\alpha(\psi(x))\not=\alpha(\varphi_e(x))$.
Этим завершается доказательство теоремы.
\end{proof}

\begin{corollary}
Пусть $\mc A$~--- нетривиальное семейство, содержащее наименьший по включению элемент и обладающее разрешимой вычислимой нумерацией.
Тогда класс $K_r(\mc A)\setminus K_p(\mc A)$ эффективно бесконечен.
\end{corollary}

\begin{proof}
Покажем, что никакая разрешимая вычислимая нумерация~$\mu$ нетривиального семейства не удовлетворяет теореме рекурсии.
После этого применением теоремы~\ref{rp} сразу придем к заключению следствия. Выберем номера $x_0$ и $x_1$, для которых $\mu(x_0)\not=\mu(x_1)$.
Тогда вычислимая функция
$$
f(x)=
\begin{cases}
x_0, & \mbox{если}\ \mu(x)=\mu(x_1),\cr
x_1, & \mbox{если}\ \mu(x)\not=\mu(x_1),
\end{cases}
$$
не имеет неподвижных точек в нумерации $\mu$.
\end{proof}

\begin{corollary}	
Пусть $\mc A$~--- семейство всех в.п. множеств или всех ч.в. функций. Тогда класс $K_r(\mc A)\setminus K_p(\mc A)$ эффективно бесконечен.
\end{corollary}



\section{Эффективная бесконечность классов $K_r(\mc A)$, $K_p(\mc A)$, $K_c(\mc A)$ конечных семейств в.п. множеств}\label{s3}

Перейдем к формулировке и доказательству критерия эффективной бесконечности классов $K_r(\mc A)$ конечных семейств в.п. множеств.
\begin{proposition}\label{cr}
Пусть $\mc A$~--- нетривиальное конечное семейство в.п. множеств. Тогда следующие условия эквивалентны:
\begin{enumerate}
\item $\mc A$ содержит наименьший по включению элемент,
\item класс $K_r(\mc A)$ эффективно бесконечен,
\item существует вычислимая нумерация семейства $\mc A$, удовлетворяющая теореме рекурсии.
\end{enumerate}
\end{proposition}	

\begin{proof}
Импликация ($1\Rightarrow 2$) сразу следует из теоремы~\ref{rp}. Импликация ($2\Rightarrow 3$) очевидна.
Докажем справедливость импликации ($3\Rightarrow 1$). Предположим, что семейство $\mc A$ не содержит наименьший
по включению элемент. Пусть 
$$R_0,\dots,R_n, n>0,$$
все минимальные по включению элементы $\mc A$. Следуя \cite{E77} (предложение~4, I\,\S 2), выберем конечные множества
$$F_0\subseteq R_0,\dots,F_n\subseteq R_n$$
такие, что $F_i\not\subseteq R_j$ для любых различных $i,j\leqslant n$.
Пусть  $\alpha$~--- произвольная вычислимая нумерация $\mc A$. Зафиксируем $x_0, x_1$, для которых $\alpha(x_0)=R_0$ и $\alpha(x_1)=R_1$.
 Определим вычислимую функцию $f$, не обладающую
неподвижными точками в нумерации $\alpha$, выбрав для каждого $x$ наименьшее $s$  такое, что $F_i\subseteq\alpha_s(x)$
для некоторого $i\leqslant n$, и положив
$$
f(x)=
\begin{cases}
x_1, & \mbox{если}\ F_0\subseteq\alpha_s(x),\cr
x_0, & \mbox{если}\ F_0\not\subseteq\alpha_s(x).
\end{cases}
$$
По определению функции $f$ для каждого $x$ выполняется $\alpha(f(x))\not=\alpha(x)$.
\end{proof}

\noindent Из следующей теоремы вытекает необходимое условие эффективной бесконечности классов $K_c(\mc A)$
и $K_p(\mc A)$, которое показывает, что для всех конечных семейств в.п. множеств эти классы не являются эффективно бесконечными.

\begin{theorem}\label{nonei}
Пусть $\mc A$~--- семейство, обладающее главной вычислимой нумерацией $\nu$ и нумерацией $\mu$, сводимой
к любой вычислимой нумерации $\mc A$. Пусть~$K$~--- класс его нумераций,
замкнутый относительно эквивалентности, такой,
что 
$$I(K)\dfn\{e\in\nc{Tot}:\mu\oplus(\nu\circ\varphi_e)\in K\}\in\Sigma^0_3\ \mbox{и}\ I(K)\not=\emptyset.$$
Тогда существует такая вычислимая функция $g$, что $\alpha_{g(x)}\in K$ для любого $x$ и для любой вычислимой нумерации
$\xi\in K$ найдется $y$, для которого выполняется $\xi\equiv\alpha_{g(y)}$.
\end{theorem}

\begin{proof}
Поскольку $I(K)\in\Sigma^0_3$, существует вычислимая двухместная функция $h$ такая,
что для всех $e$ справедливо
$$e\in I(K)\Leftrightarrow\exists z\,[W_{h(e,z)}\ \mbox{бесконечно}].$$
Зафиксируем вычислимую нумерацию $\beta\in K$.
Равномерно по произвольной паре $\ang{e,z}$ определим нумерацию $\alpha=\alpha_{g(c(e,z))}$, удовлетворяющую условиям
\begin{enumerate}
\item[1)] $\mu\oplus\alpha\in K$;
\item[2)] если $W_{h(e,z)}$ бесконечно, то $\mu\oplus\alpha\equiv\mu\oplus(\nu\circ\varphi_e)$,
\item[3)] если $W_{h(e,z)}$ конечно, то $\mu\oplus\alpha\equiv\beta$.
\end{enumerate}
Для каждого $x$ обозначим через $t_x$ наименьшее $t$ (если оно существует), для которого
$$\varphi_{e,t}(x)\downarrow\,\&\,|W_{h(e,z),t}|>x.$$
Обозначим через $A$ вычислимое (возможно конечное) множество
$$A=\{t_0<t_1<\dots\}.$$
Для каждого $x$, если $t_x$ определено, то полагаем
$$\alpha(t_x)=\nu(\varphi_e(x)).$$
Для каждого $y\not\in A$ и каждого $s$ определим
$$\alpha_s(y)=\beta_s(y),$$
если не существует $t\in A$, для которого $y<t\leqslant s$.
В противном случае выберем наименьшее $t\in A$, для которого $y<t\leqslant s$, а для него, в свою очередь, наименьшее $c(x,u)$, для которого 
$\beta_{t}(y)\subseteq\mu_u(x)$,
и определим 
$$\alpha_s(y)=\mu(x).$$
Положим $\alpha(y)=\bigcup_s\alpha_s(y)$.

Если $W_{h(e,z)}$ бесконечно, то бесконечным будет и $A$. Тогда по определению $\alpha$ для всех $x$ выполняется $\alpha(t_x)=\nu(\varphi_e(x))$
и для каждого $y\not\in A$ можно эффективно указать $x$, для которого $\alpha(y)=\mu(x)$. Отсюда следует, что $\mu\oplus\alpha\equiv\mu\oplus(\nu\circ\varphi_e)$.
Если же $W_{h(e,z)}$ конечно, то для всех, за исключением лишь конечного числа, $y$ выполняется $\alpha(y)=\beta(y)$.
Отсюда и в силу выбора нумерации $\mu$ имеем $\mu\oplus\alpha\equiv\beta$. Этим завершается доказательство теоремы.
\end{proof}

\begin{corollary}\label{noneipc}
Пусть $\mc A$~--- семейство, обладающее главной вычислимой нумерацией $\nu$ и нумерацией $\mu$, сводимой
к любой вычислимой нумерации $\mc A$. Тогда классы $K_p(\mc A)$ и $K_c(\mc A)$ не являются эффективно бесконечными.
\end{corollary}
\begin{proof}
Для всех $e$ имеем
$$e\in I(K_p(\mc A))\Leftrightarrow e\in\nc{Tot}\,\&\,\exists i\,[i\in\nc{Tot}\,\&\,\forall j\forall x\,[\varphi_{i}(c(j,x))\downarrow\,\&\,
\varphi_{j}(x)\downarrow\rightarrow$$ 
$$\rightarrow(\mu\oplus(\nu\circ\varphi_e))(\varphi_{i}(c(j,x)))=(\mu\oplus(\nu\circ\varphi_e))(\varphi_{j}(x))]]\Leftrightarrow$$
$$\Leftrightarrow \Pi^0_2\,\&\,\exists\,[\Pi^0_2\,\&\,\forall [\Sigma^0_1\rightarrow\Pi^0_2]]\Leftrightarrow\Sigma^0_3.$$
Отсюда $I(K_p(\mc A))\in\Sigma^0_3$ и, по теореме~\ref{nonei}, класс $K_p(\mc A)$ не является эффективно бесконечным.
Если $\mc A$ содержит наименьший по включению элемент $X$, то, добавив в предыдущем выражении после <<$i\in\nc{Tot}$>>
конъюнкт 
$$\forall j\forall x\,[\varphi_j(x)\uparrow\rightarrow\varphi_{i}(c(j,x))\downarrow\,\&\,(\mu\oplus(\nu\circ\varphi_e))(\varphi_{i}(c(j,x)))=X]$$
$$(\Leftrightarrow \forall\,[\Pi^0_1\rightarrow\Sigma^0_1\,\&\,\Pi^0_2]\Leftrightarrow\Pi^0_2),$$
получим, что $I(K_c(\mc A))\in\Sigma^0_3$. Следовательно, $K_c(\mc A)$ также не является эффективно бесконечным.
\end{proof}
\noindent Согласно~\cite{E77} любое конечное семейство в.п. множеств $\mc A$ удовлетворяет условиям следствия~\ref{noneipc}. Поэтому
получаем
\begin{corollary}\label{finpc}	
Пусть $\mc A$~--- конечное семейство в.п. множеств. Тогда классы $K_p(\mc A)$ и $K_c(\mc A)$ не являются эффективно бесконечными.
\end{corollary}	
\noindent Закончим эту работу предложением, которое показывает, что существование бесконечного числа вычислимых нумераций, принадлежащих классам $K_p(\mc A)$ и $K_c(\mc A)$, не влечет их эффективную бесконечность. Напомним, что элемент $R\in\mc A$ называется \textit{существенным}~\cite{E77}, если существует такое $Q\in\mc A$,
что $R\subsetneq Q$.
\begin{proposition}\label{inf}
Пусть $\mc A$~--- конечное семейство в.п. множеств, содержащее наименьший по включению элемент и отличный от него существенный элемент.
Тогда  $\mc A$ обладает бесконечным числом попарно неэквивалентных полных вычислимых нумераций.
\end{proposition}
\begin{proof}
Пусть $\mc A=\{R_0,R_1,R_2,\dots, R_k\}$, где $R_0$~---  наименьший по включению элемент $\mc A$ и
$$R_0\subsetneq R_1\subsetneq R_2.$$
Пусть $\{B_j\}_{j\in\N}$~--- последовательность попарно не $m$-сводимых друг к другу в.п. множеств.
Используя теорему рекурсии, выберем бесконечную последовательность попарно различных чисел $\{n_i\}_{i\in\N}$ такую, что
$$\varphi_{n_i}(0)=c(n_i,0)$$
для всех $i$.
Для каждого $j$ определим полную вычислимую нумерацию $\beta_j$ семейства $\mc A$, положив
$$\beta_j(c(n_0,0))=R_3,\dots,\beta_j(c(n_{k-3},0))=R_k,$$
$$
\beta_j(c(n_{k-2+i},0))=
\begin{cases}
R_1, & \mbox{если}\ i\not\in B_j,\cr
R_2, & \mbox{если}\ i\in B_j.
\end{cases}
$$
Для всех $x\not\in\{c(n_i,0):i\in\N\}$
положим
$$
\beta_j(x)=
\begin{cases}
R_0, & \mbox{если}\ \forall i\,[\ang{x,c(n_i,0)}\not \in\eta],\cr
\beta_j(c(n_i,0)), & \mbox{если}\ [\ang{x,c(n_i,0)}\in\eta],
\end{cases}
$$
где $\eta$~--- отношение эквивалентности, определенное в доказательстве теоремы~\ref{cprf}.
По определению нумераций $\beta_j$, $j\in\N$, имеем, что для любых $u,v$
$$\beta_u\leqslant\beta_v\Rightarrow B_u\leqslant_mB_v.$$
Отсюда следует, что $\mc A$ обладает бесконечным числом попарно неэквивалентных полных вычислимых нумераций.
\end{proof}
\noindent Применяя следствие~\ref{finpc} и предложение~\ref{inf}, получаем
\begin{corollary}
Существует вычислимое семейство $\mc A$, для которого классы $K_p(\mc A)$ и $K_c(\mc A)$ являются бесконечными, но
не являются эффективно бесконечными.
\end{corollary}

\begin{question}
Пусть семейство $\mc A$ обладает бесконечным числом попарно неэквивалентных вычислимых нумераций, удовлетворяющих
теореме рекурсии. Является ли класс $K_r(\mc A)$ эффективно бесконечным?
\end{question}

\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).

\bibitem{GYY93}
S.S. Goncharov, A. Yakhnis, V. Yakhnis, 
{\it Some effectively infinite classes of enumerations},
 Ann. Pure App. Log., \textbf{60}:3 (1993), 207--235.
 
 \href{https://doi.org/10.1016/0168-0072(93)90076-P}{https://doi.org/10.1016/0168-0072(93)90076-P}
 
\medskip
\bibitem{M63}
A.I. Mal'tsev, 
{\it Completely enumerated sets}, Seminar ``Algebra and Logic'', \textbf{2}:2 (1963), 4--29.

\href{https://www.mathnet.ru/rus/al979}{https://www.mathnet.ru/rus/al979}

\medskip
\bibitem{M71}
A.I. Mal'tsev, 
{\it The metamathematics of algebraic systems}, North-Holland, Amsterdam, 1971.

\href{https://lib.ugent.be/catalog/rug01:000004761}{https://lib.ugent.be/catalog/rug01:000004761}


\medskip
\bibitem{E69a}
Yu.L. Ershov, 
{\it Theorie der numerierungen I}, Z. Math. Log. Grundl. Math., \textbf{19}:19--25 (1973), 289--388.

\href{https://doi.org/10.1002/malq.19730191901}{https://doi.org/10.1002/malq.19730191901}

\medskip
\bibitem{E77} Yu.L. Ershov, {\it Theory of numberings}, Nauka, Moscow, 1977.

\href{https://www.ispras.ru/mathbib/pub/pub2879.php?sphrase\_id=5208427}{https://www.ispras.ru/mathbib/pub/pub2879.php?sphrase\_id=5208427}

\medskip
\bibitem{E69b}
Yu.L. Ershov,
{\it Completely enumerated sets},
 Sib. Math. J., \textbf{10}:5 (1969),  773--784.
 
 \href{https://doi.org/10.1007/BF00971653}{https://doi.org/10.1007/BF00971653}
 
 \medskip
\bibitem{E70}
Yu.L. Ershov, 
{\it On inseparable pairs}, Algebra and Logic, \textbf{9}: 6 (1970), 396--399. 
\href{https://doi.org/10.1007/BF02219043}{https://doi.org/10.1007/BF02219043}
 
 
 \medskip
 \bibitem{S88}
 V.L. Selivanov, 
 {\it Index sets of quotient objects of the Post numeration}, Algebra and Logic, \textbf{27}:3 (1988), 215--224.

\href{https://doi.org/10.1007/BF01978567}{https://doi.org/10.1007/BF01978567}
 
 \medskip
 \bibitem{BGS03}
 S.A. Badaev, S.S. Goncharov, A. Sorbi, 
 {\it Completeness and universality of arithmetical numberings}, in:
Computability and Models. The University Series in Mathematics. Springer, Boston, MA, 2003.

\href{https://doi.org/10.1007/978-1-4615-0755-0\_2}{https://doi.org/10.1007/978-1-4615-0755-0\_2}

\medskip
\bibitem{BT19}
H. Barendregt, S.A. Terwijn, 
{\it Fixed point theorems for precomplete numberings}, Ann. Pure App. Log., \textbf{170}:10
(2019), 1151--1161.

\href{https://doi.org/10.1016/j.apal.2019.04.013}{https://doi.org/10.1016/j.apal.2019.04.013}

\medskip
\bibitem{A21}
M.M. Arslanov, 
{\it Fixed-point selection functions}, Lob. J. Math., \textbf{42}:4 (2021), 685--692. 

\href{https://doi.org/10.1134/S1995080221040041}{https://doi.org/10.1134/S1995080221040041}

\medskip
\bibitem{S21}
V.L. Selivanov, 
{\it Precomplete numberings}, J. Math. Sci., \textbf{256}:1 (2021), 96--124.

\href{https://doi.org/10.1007/s10958-021-05422-2}{https://doi.org/10.1007/s10958-021-05422-2}

\medskip
\bibitem{P73}
T.H. Payne, 
{\it Effective extendability and fixed points},
Notre Dame J. Form. Log., 
\textbf{14}:1 (1973), 123--124.

\href{https://doi.org/10.1305/ndjfl/1093890819}{https://doi.org/10.1305/ndjfl/1093890819}

\medskip
\bibitem{B91}
S.A. Badaev, 
{\it On weakly pre-complete positive equivalences}, Sib. Math. J., \textbf{32}:2 (1991), 321--323.

\href{https://doi.org/10.1007/BF00972779}{https://doi.org/10.1007/BF00972779}

\medskip
\bibitem{F22}
M. Faizrahmanov, 
{\it Extremal numberings and fixed point theorems},
Math. Log. Q., \textbf{68}:4 (2022), 398--408.

\href{https://doi.org/10.1002/malq.202200035}{https://doi.org/10.1002/malq.202200035}

\medskip
\bibitem{E99}
Yu.L. Ershov, 
{\it Theory of numberings}, in: Handbook of Computability Theory, Studies in Logic and the Foundations of
Mathematics Vol. 140, edited by E.R. Griffor, Elsevier Science, Amsterdam, 1999, 473--506.

\href{https://doi.org/10.1016/S0049-237X(99)80030-5}{https://doi.org/10.1016/S0049-237X(99)80030-5}

\medskip
\bibitem{S87}
R.I. Soare, 
{\it Recursively enumerable sets and degrees}. A Study of Computable Functions
and Computably Generated Sets. Perspectives in Mathematical Logic. Springer-Verlag, Berlin,
Heidelberg, New York, etc., 1987.

\href{https://link.springer.com/book/9783540666813}{https://link.springer.com/book/9783540666813}

\medskip
 \bibitem{S16}
 R.I. Soare,
 {\it Turing computability, theory and applications},
  Berlin, Springer, 2016.
  
  \href{https://link.springer.com/book/10.1007/978-3-642-31933-4}{https://link.springer.com/book/10.1007/978-3-642-31933-4}
  
    \medskip
 \bibitem{E75}
  Yu.L. Ershov, 
  {\it Theorie der numerierungen II}, Z. Math. Log. Grundl. Math., \textbf{21}:1 (1975), 473--584.

\href{https://doi.org/10.1002/malq.19750210164}{https://doi.org/10.1002/malq.19750210164}

\medskip
\bibitem{F58}
R.M. Friedberg,
{\it Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication}, J. Symb. Log., \textbf{23}:3 (1958) 309--316.

\href{https://doi.org/10.2307/2964290}{https://doi.org/10.2307/2964290}

\end{thebibliography}
\end{document}
