
\documentclass[10pt]{amsart}
\usepackage[T1,T2A]{fontenc}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}



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

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}

\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{Dmitry Ivanovich Ivanov  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Tyumen State University,
\newline\hphantom{iii} Volodarskogo St., 6,
\newline\hphantom{iii} 625003 Tyumen, Russian Federation}%
\email{d.i.ivanov@utmn.ru}%
\address{Olga Vladimirovna Ivanova}  % Контактные данные всех авторов и место работы указываются только на английском языке
\email{i1offa@list.ru}%

\thanks{\sc Ivanov D.I. Ivanova O.V.,
Limited combinatorial-selector sets}
\thanks{\copyright \ 2022 Иванов Д.И, Иванова О.В.}
\thanks{\it Поступила 1 января 2015 г., опубликована 31 декабря 2022 г.}%


\semrtop \vspace{1cm}
\maketitle {\small}


\begin{quote}
\noindent{\sc Abstract. } This article discusses the issue of classification of their own subsets of $N =\lbrace0,1,2,3,... \rbrace $  by means of partial Boolean functions. For an arbitrary partial Boolean function $ \beta $ defines the notion of $ \beta $-limited combinatorial-selector set, which is a generaliza\-tion of the concept of $ \beta $-selector set [1]. Fully describe the classes of these sets, the relationship between these classes by inclusion. \medskip

\noindent{\bf Keywords:} combinatorial sets, combinatorial-selector sets, limited-combinatorial sets, limited combinatorial-selector set.
 \end{quote}



\section{Введение}
Представленная работа является логическим продолжением статьи [11], в которой рассматриваются подмножества множества $N =\lbrace0,1,2,3,... \rbrace $ с точки зрения их классификации посредством булевых функций (БФ) и эффективной вычислимости. Начало такой классификации положил К. Джокуш, определив полурекурсивное множество [8], как множество $A\subseteq N$, для которого существует всюду определенная вычислимая функция 
$f:N \times N \rightarrow N$ такая, что 
\begin{center}
$ \left( \forall x \right) \left( \forall y \right)$ $ \left(f(x,y) \in \lbrace x, y\rbrace \wedge \left( \left( \chi(x)\vee \chi (y)\right)   =1 \Leftrightarrow f(x,y)\in A \right)\right) $ ,
\end{center}
где $ \chi_{A} $ $-$ характеристическая функция множества $A$, то есть
\begin{center}
\begin{equation*}
\chi_{A}(t)= 
\begin{cases}
   1,   \text{если } t \in A;\\
   0,   \text{если } t  \notin A .
\end{cases}
\end{equation*}
\end{center}

Как видно, в определении участвует булева функция – дизъюнкция. По аналогии А.Н. Дегтев предложил использовать в определении произвольную БФ $ \beta $, назвав такие множества $ \beta $-комбинаторными, а именно, множество $A$ называется $ \beta $-комбинаторным, где $ \beta $ $-$ произвольная $n$-местная БФ, если существует $n$-местная всюду определенная на $N$ вычислимая функция $\textit{f}$, принимающая значения из $N$, такая что

\begin{center}
$ \left( \forall x_{1},...,x_{n} \right) $ $ \left( \beta \left( \chi_{A}(x_{1}),...,\chi_{A}(x_{n})\right)  =1 \Leftrightarrow f(x_{1},...,x_{n}) \in A \right) $ .
\end{center}

Накладывая ограничения на функцию $f$, а именно, потребовав, чтобы функция $f$ была селекторной, т. е.

\begin{center}
$(\forall x_{1},...,x_{n} )(f(x_{1},...,x_{n}) \in \lbrace x_{1},…,x_{n} \rbrace)$,
\end{center}
придём к определению понятия $ \beta $-комбинаторно-селекторного ($ \beta $-селекторного) множества [1, 4]. А меняя в нем эквивалентность на импликацию, получим определение $ \beta $-импликативно-селекторного множества [3]. Рассматривая в качестве $f$ произвольную частично вычислимую функцию, получим определения слабо $ \beta $-импликативно-селекторного и $ \beta $-комбинаторно-селекторного множеств, которые изучены и получены соотношения между их классами в работах [2, 5-7, 9, 10].

Ограниченно-комбинаторные множества, описанные в работе [11], являются обобщением понятия $ \beta $-комбинаторных множеств посредством замены всюду определенной БФ на частичную. В настоящей статье рассматриваются ОК-множества с дополнительным требованием селекторности функции $f$, полностью описаны классы этих множеств и установлены их соотношению по включению.



\section{Основные результаты}

Будем называть БФ $\beta$ $\textit{частичной}$, если хотя бы для одного из наборов
\begin{center}
 $\left( \theta_{1},\ldots,\theta_{n}\right)\in\lbrace0,1\rbrace^{n} $ 
 \end{center}
  значение БФ $ \beta $ на  этом   наборе   не   определено
 $ \left( \beta\left( \theta_{1},\ldots,\theta_{n}\right) \uparrow\right)  $.

Частично вычислимая функция $ \textit{f} $ называется $ \textit{селекторной} $, если

\begin{center}
$\left( \forall x_{1},\ldots, x_{n}\right) \left( \textit{f}\left( x_{1},\ldots, x_{n}\right) \downarrow \text{ } \Rightarrow\textit{f}\left( x_{1},\ldots, x_{n}\right)\in\lbrace x_{1},\ldots, x_{n}\rbrace\right) $,
\end{center}
где $ \textit{f}\left( x_{1},\ldots, x_{n}\right)\downarrow $ означает, что значение функции $ \textit{f}\left( x_{1},\ldots, x_{n}\right) $ определено.

Подмножества множества $N=\lbrace 0,1,2,\ldots\rbrace$, рассматриваемые в статье, полагаем отличными от $\varnothing$ и $N$.

\begin{definition}
Множество  $A \subseteq N=\lbrace0,1,2,\ldots\rbrace$ называется $ \beta$-ограниченно комбинаторно-селекторным $ \left( \beta \textit{-ОКС}\right)$, если существует $n$-местная частично вычислимая селекторная функция $f$ такая, что для всех, 
$ x_{1},\ldots,x_{n} \in N $ выполнены условия:

$(i)$           $f\left( \textit{x}_{1},\ldots,\textit{x}_{n}\right) \uparrow \Leftrightarrow \beta \left( \chi  \left( \textit{x}_{1}\right) ,\ldots,\chi\left( \textit{x}_{n}\right)\right) \uparrow$,

$(ii)$			$\textit{f}\left( x_{1},\ldots,x_{n}\right) \in A\Leftrightarrow \beta\left( \chi\left( x_{1}\right) ,\ldots,\chi\left( x_{n}\right) \right)=1$,\\
где $ \chi $ $-$ характеристическая функция множества $A$. В этом случае говорим, что $A$ является $ \beta\textit{-OKC} $ множеством с соответствующей частично вычислимой селекторной функцией $f$.
 
\end{definition}

Назовем частичную БФ $ \beta\textit{ допустимой} $ , если она не является нигде не определённой и существует хотя бы одно $ \beta $-ОКС множество $A$, такое что  $\textit{A} \neq\varnothing $,  $ \textit{A}\neq \textit{N}$. Понятие допустимой БФ несколько отличается от аналогичного определения в статье [11], но в обоих вариантах обуславливается исключением из рассмотрения тривиальных случаев.

Будем обозначать класс всех перечислимых множеств $-$ $ \textbf{E}_{1}$, а 
$ \textbf{E}_{0}=\lbrace X:X=\textit{N}\setminus Y,Y\in \textbf{E}_{1}\rbrace$  $-$ класс множеств, имеющих перечислимое дополнение. Тогда $ \textbf{R}=  \textbf{E}_{0}\cap \textbf{E}_{1}$ $-$ класс всех вычислимых множеств.

Рассмотрим ряд вспомогательных утверждений, необходимых для доказательства основного результата.

\begin{lemma}  % лемма 1
Если $ \beta $-допустимая БФ, то $\beta\left( \theta,\ldots,\theta\right) \neq1-\theta\in\lbrace0,1\rbrace  $.
\end{lemma}

\begin{proof}
Пусть $A$ является $ \beta $-ОКС множеством с соответствующей частично вычислимой селекторной функцией $ \textit{f} $ для подходящей допустимой БФ $ \beta, \textit{a}_{\theta} $ $-$ фиксированные элементы, такие что 

\begin{center}
\begin{equation*}
a_{\theta}\in 
\begin{cases}
   A,\text{если } \theta = 1\\
   N \setminus A,  \text{ если } \theta =0 .
\end{cases}
\end{equation*}
\end{center}
Тогда $ \textit{f}\left( a_{\theta},\ldots,a_{\theta}\right) =a_{\theta} $ (или же $ \textit{f}\left( a_{\theta},\ldots,a_{\theta}\right) \uparrow $), поэтому $\beta\left( \theta,\ldots,\theta\right)=\theta$ (или $\beta\left( \theta,\ldots,\theta\right)\uparrow$).
\end{proof}

\begin{lemma}
Любое вычислимое множество является $ \beta $-ОКС множеством для всякой допустимой частичной БФ $ \beta $.
\end{lemma}

\begin{proof}
Пусть  $A\in\textbf{R}  $, и $ \beta $ $-$  произвольная допустимая $ n$-местная частичная БФ. Определим $n $-местную частично вычислимую функцию \\
$ f\left( x_{1},\ldots, x_{n}\right) $ следующим образом: если $\beta \left( \chi_{A}  \left( x_{1}\right) ,\ldots,\chi_{A}\left( x_{n}\right)\right)\uparrow$, то считаем $ \textit{f}\left( x_{1},\ldots, x_{n}\right)\uparrow $; если $\beta \left( \chi_{A}  \left( x_{1}\right) ,\ldots,\chi_{A}\left( \textit{x}_{n}\right)\right)=1$, то полагаем $ \textit{f}\left( x_{1},\ldots, x_{n}\right)=\textit{x}_{i} $, где $\textit{x}_{i}$ - элемент с наименьшим номером, такой что: $x_{i} \in A$, заметим, такой $ x_{i} $ всегда найдётся для допустимой БФ по лемме 1; аналогично, если $\beta \left( \chi_{A}  \left( x_{1}\right) ,\ldots,\chi_{A}\left( x_{n}\right)\right)=0$, то $ \textit{f}\left( x_{1},\ldots, x_{n}\right)=x_{j} $, где $ x_{j} $ - элемент с наименьшим номером, такой что: $x_{j} \in (N \setminus A) \cap\lbrace x_{1},…,x_{n} \rbrace$. Таким образом, получили, что множество $A$ является $\beta$-ОКС с частично вычислимой селекторной функцией $ f $.
\end{proof}

Поскольку всякое $ \beta $-ОКС множество является и $ \beta $-ОК, следующая лемма является прямым  следствием леммы 2 статьи [11].

\begin{lemma} Всякое $ \beta $-ОКС множество или является перечислимым, или имеет перечислимое дополнение, для любой допустимой частичной БФ $ \beta $.          $\square$
\end{lemma}



В статье [1] описаны $ \beta $-селекторные множества, которые можно получить, если в определении $ \beta $-ОКС множества вместо частичной БФ использовать всюду определенную, при этом частично вычислимая селекторная функция станет всюду определенной. Доказано, что семейство $ \beta $-селекторных множеств совпадает либо с семейством вычислимых, либо с семейством полурекурсивных множеств [1]. 

Замечание. Следует отметить, что в указанной статье [1] из рассмотрения исключается тождественная БФ $ \beta \left( x \right) = x $, для которой любое подмножество множества $N$ является $ \beta $-селекторным множеством.

\begin{lemma} Если частичная БФ $ \beta $ такая, что $ \beta (0,0,…,0)\uparrow$ и $ \beta (1,1,…,1)\uparrow$, или, если $ \beta (0,0,…,0)\downarrow$ и $ \beta (1,1,…,1)\downarrow$, то любое $ \beta $-ОКС множество $A$ вычислимо.
\end{lemma}

\begin{proof} 
Пусть $ \beta (0,0,…,0)\uparrow$, рассмотрим значения
\begin{center}
$\beta(1,0,…,0);  \beta(0,1,…,0);…, \beta(0,0,…,1)$.
\end{center}
Если хотя бы одно из них определено, то, как следует из доказательства леммы 2 [11], $A \in \textbf{E}_{1}$. Иначе, в каждом из $n$ наборов заменим один из 0 на 1. Если хотя бы одно из полученных значений будет определено, то также $ A \in \textbf{E}_{1}$. Продолжая указанную процедуру, в любом случае получим $A \in \textbf{E}_{1}$, так как БФ $ \beta $ не является нигде не определенной. Аналогично, если $\beta (1,1,…,1)\uparrow$, то $ \beta $-ОКС множество $A $ принадлежит классу $ \textbf{E}_{0}$. Следовательно, если значения $\beta(0,0,…,0)$ и $\beta(1,1,…,1)$ не определены одновременно, то $A \in \textbf{R}$.

Далее, пусть для частичной БФ $\beta: \beta(0,0,…,0)\downarrow,$  $\beta(1,1,…,1)\downarrow $ и для некоторого набора $\beta(1,…,1,…,0,…,0)\uparrow$. Меняя 0 на 1, на некотором шаге получим $A \in \textbf{E}_{1}$, а меняя 1 на 0 $-$ $A \in \textbf{E}_{0}$, т. е. $A \in \textbf{R}$. 
\end{proof}

\begin{lemma} Для булевых функций
\begin{center}
\begin{equation*}
\beta_{\theta}\left(\theta_{1},..., \theta_{n}\right) = 
\begin{cases}
   \theta,\text{если } \theta_{1} =...= \theta_{n}=\theta\\
   \uparrow ,  \text{ иначе },
\end{cases}
\end{equation*}
\end{center}
семейство $\beta_{\theta}$-ОКС множеств совпадает с классом $ \textbf{E}_{\theta}$.
\end{lemma}


\begin{proof} 
По лемме 3  $A \in \textbf{E}_{\theta}$ для любого $\beta_{\theta}$-ОКС множества $A$. 
С другой стороны, любое перечислимое (коперечислимое) множество $B$ является $ \beta $-ОКС множеством с частично вычислимой селекторной функцией $ g$, которую можно получить перечисляя множество $B$ $\left( N \setminus B \right) $:

\begin{center}
\begin{equation*}
g\left(x_{1},..., x_{n}\right) = 
\begin{cases}
   x_{1},\text{если } x_{1},...,x_{n} \in B \text{ }  \left( N \setminus B\right)  \\
   \uparrow ,  \text{ в противном случае }.
\end{cases}
\end{equation*}
\end{center}

\end{proof}
Воспользуемся понятиями и терминами, сформулированными в работе [11]. 

\begin{definition}
$[11]$ Сужение частичной булевой функции $\beta \left( t_{1},...,t_{n} \right) $, полученное заменой $(n-m)$ ее переменных $ t_{i_{m+1}},...,t_{i_{n}}, 1\leq m\leq (n-1) $ на константы 
$\theta_{i_{p}} \in \lbrace 0,1 \rbrace, p \in \lbrace m+1,…,n \rbrace $, такое, что функция $ \beta_{1} \left( t_{i_{1}},…,t_{i_{m}} \right) $ становится всюду определенной БФ, называется сужением по переменным $t_{i_{1}},…,t_{i_{m}}$ на наборе констант $\left( \theta_{i_{m+1}},…,\theta_{i_{n}} \right) $:
\begin{center}
$\beta_{1} \left( t_{i_{1}},…,t_{i_{m}} \right) =\beta \left( t_{i_{1}},…,t_{i_{m}} \right)  \left[ \theta_{i_{m+1}},…,\theta_{i_{n}}\right]  $.
\end{center}
\end{definition}

\begin{definition}
$[11]$ Сужение называется максимальным, если оно всюду определенное и для любого  $j \in \lbrace m+1,…,n\rbrace$, булева функция 
\begin{center}
$\beta_{1_{j}}(t_{i_{1}},…,t_{i_{m}}, t_{i_{j}} )[\theta_{i_{m+1}},…,\theta_{i_{j-1}},\theta_{i_{j+1}},…,\theta_{i_{n}} ]$
\end{center}
становится частичной БФ для любого набора констант.

\end{definition}

\begin{lemma}  %lemma 6
Если БФ $ \beta(t_{1},…,t_{n})$ допускает сужение по переменным $ t_{i_{1}},…,t_{i_{m}}$ на наборе констант $\left( \theta_{i_{m+1}},…,\theta_{i_{n}}\right) $, причем существуют $l,t \in \left\lbrace i_{m+1},…,i_{n} \right \rbrace$, $l \neq t$, такие что $\theta_{l}=1-\theta_{t}$, то семейство $  \beta $-ОКС множеств совпадает с классом вычислимых множеств.
\end{lemma}

\begin{proof}
Переименовывая, если нужно, переменные, без ограничения общности можно считать, что сужение будет по первым m переменным. 
Если $  \beta$ удовлетворяет условию леммы, то для максимального сужения
\begin{center}
$\beta \left( t_{1},…,t_{m} \right) \left[ \theta_{m+1},…,\theta,…,1-\theta,…,\theta_{n} \right] $ 
\end{center}
существуют наборы  
$\left( \theta_{1},…,\theta_{m}\right) $ и $\left( \delta_{1},…,\delta_{m}\right) $, такие что
\begin{center}
$\beta \left( \theta_{1},…,\theta_{m},\theta_{m+1},…,1-\theta,…,1-\theta,…,\theta_{n} \right) \uparrow$,
$\beta \left( \delta_{1},…,\delta_{m} ,\theta_{m+1},…,\theta,…,\theta,…,\theta_{n} \right) \uparrow.$
\end{center}

Тогда, из доказательства леммы 2 [11], $  \beta$-ОКС будет перечислимым и коперечислимым одновременно, т. е вычислимым.
\end{proof}

Может оказаться, что БФ $\beta$ допускает несколько максимальных сужений.

\begin{definition}
$[11]$ Последовательностью максимальных сужений для БФ $  \beta$ называется набор всех возможных ее максимальных сужений:
\begin{center}
$\beta_{1} \left( t_{11},t_{12},…,t_{1k_{1}} \right) =\beta\left( t_{11},t_{12},…,t_{1k_{1}} \right) \left[ \theta_{1\left(k_{1}+1\right)} ,\theta_{1\left(k_{1}+2\right)},…,\theta_{1n} \right]$,\\

$1 \leq k_{1} < n$,\\
$\beta_{2} \left( t_{21},t_{22},…,t_{2k_{2}} \right) =\beta\left( t_{21},t_{22},…,t_{2k_{2}} \right) \left[ \theta_{2\left(k_{2}+1\right)} ,\theta_{2\left(k_{2}+2\right)},…,\theta_{2n} \right] , $\\

$1 \leq k_{2} < n$,\\
…,\\
$\beta_{r} \left( t_{r1},t_{r2},…,t_{rk_{r}} \right) =\beta\left( t_{r1},t_{r2},…,t_{rk_{r}} \right) \left[ \theta_{r\left(k_{r}+1\right)} ,\theta_{r\left(k_{r}+2\right)},…,\theta_{rn} \right] $, \\
$1 \leq k_{r} < n$
\end{center}
\end{definition}

\begin{definition}
$[11]$ Булева функция называется разложимой, если для каждого $i$ $(1 \leq i \leq r)$ функции последовательности максимальных сужений $\beta_{i}$ получены на наборах одних и тех же констант $\left( \theta,…,\theta\right) , \theta \in \lbrace 0,1 \rbrace$
\begin{center}
$\beta_{1} \left( t_{11},t_{12},…,t_{1k_{1} } \right) =\beta\left( t_{11},t_{12},…,t_{1k_{1}}\right) \left[ \theta,\theta,…,\theta\right] ,1 \leq k_{1}<n $,\\

$\beta_{2} \left( t_{21},t_{22},…,t_{2k_{2}} \right) =\beta\left( t_{21},t_{22},…,t_{2k_{2}}\right) \left[ \theta,\theta,…,\theta\right] ,1 \leq k_{2}<n$,\\
…,\\
$\beta_r \left( t_{r1},t_{r2},…,t_{rk_{r}} \right) =\beta\left( t_{r1},t_{r2},…,t_{rk_{r}}\right) \left[ \theta,\theta,…,\theta\right] ,1 \leq k_{r} < n$,
\end{center}
а в остальных случаях значение $ \beta$ не определено.

\end{definition}

\begin{lemma}
Если допустимая частичная булева функция не является разложимой и отлична от функций
\begin{center}
\begin{equation*}
\beta_{\theta}\left(\theta_{1},..., \theta_{n}\right) = 
\begin{cases}
   \theta,\text{если } \theta_{1} =...= \theta_{n}=\theta\\
   \uparrow ,  \text{ иначе },
\end{cases}
\end{equation*}
\end{center}
то любое $  \beta$-ОКС множество $A$ будет вычислимым $(A\in \textbf{R})$.

\end{lemma}

\begin{proof}
По лемме 4, для функций, одновременно определённых или одновременно неопределённых на наборах из «нулей» и «единиц», $  \beta$-ОКС множества будут вычислимыми.

Иначе, пусть $\beta(\theta,…,\theta)\downarrow$. Так как БФ не является разложимой и отлична от функций $\beta_{\theta}$, значит, существует набор переменных (без ограничения общности считаем $t_{1},t_{2},…,t_{k},$ $1 \leq k  < n)$, не входящих одновременно ни в одно из максимальных сужений, такой что $\beta(t_{1},t_{2},…,t_{k},t_{k+1},…,t_{n} )\downarrow$ при
\begin{center}
$t_{1}=1-\theta, t_{2}=1-\theta,...,t_{k}=1-\theta, 1\leq k <n, t_{k+1}=\theta,...,t_{n}=\theta.$
\end{center}
Зафиксируем этот набор констант. Если окажется, что переменная $t_{1}$ входит в одно из сужений на наборе из соответствующих констант данного набора, то при $k=1$, получим $\beta(\theta,…,\theta)\uparrow$. Поэтому $k>1$, и, если это максимальное сужение по одной переменной, то по лемме 6 семейство $\beta$-ОКС множеств совпадает с классом $\textbf{R}$. Иначе, полагая, что переменная $t_{s}$ так же участвует в этом максимальном сужении на наборе оставшихся констант и $s\in\lbrace 2,3,…, k \rbrace$, получим $k>2$, и любое $\beta$-ОКС множество $A$ так же попадет в класс $\textbf{R}$ $($лемма $6)$. Если же $s \in \lbrace k+1,k+2,…, n \rbrace $, то $n-k\neq1$ $($т.к. иначе $\beta(1-\theta,…,1-\theta)\downarrow)$ и снова $A\in \textbf{R}$. Продолжая аналогичные рассуждения, получим, что семейство $\beta$-ОКС множеств является вычислимым, иначе придем к противоречию $($так как $t_{1},t_{2},…,t_{k} $ не входят одновременно ни в одно из максимальных сужений$)$. 

Может оказаться, что ни одно из максимальных сужений БФ $\beta$ на наборе констант из зафиксированного набора не содержит ни одной переменной из множества $\lbrace t_{1},t_{2},…,t_{k}\rbrace$. Тогда, поменяв значение переменной $t_{1}$ на $\theta$, получим, что для этого набора значение БФ не определено и $A\in \textbf{E}_{1-\theta}$. Далее, присвоим $t_{2}$ значение $\theta$, и, если значение функции для нового набора будет определено, то $A\in \textbf{E}_{\theta}$, а, стало быть,  $A$ $-$ вычислимо. Иначе, $t_{3}$ присвоим значение $\theta$ и продолжим процедуру. Тогда, либо на некотором шаге получим, что $A\in \textbf{R}$, либо $\beta(\theta,…,\theta)\uparrow$, что противоречит условию.
\end{proof}

\begin{definition}
Назовём сужение разложимой БФ особым, если оно отлично от константы и для него справедливо: 
\begin{center}
$\beta(1-\theta,1-\theta,…,1-\theta)[\theta,\theta,…,\theta]=\theta,$ для $\theta=0$ или $\theta=1.$

\end{center}

\end{definition}

\begin{lemma}
Для любой разложимой БФ $\beta$, допускающей особое сужение, класс $\beta$-ОКС множеств совпадает с классом $\textbf{R}$.
\end{lemma}

\begin{proof}
Пусть $A$ $-$ $\beta$-ОКС множество с частично вычислимой селекторной функцией $f$ для разложимой БФ $\beta$, а $k$-местная функция 
\begin{center}
$\beta(\chi_{A}(x_{i_{1}}),\ldots,\chi_{A}(x_{i_{k}}))[1,\ldots,1]:\beta(0,\ldots,0)[1,\ldots,1]=1$
\end{center}
является ее особым сужением. Может оказаться, что при некотором \\ $l: 1\leq l<k-1$ $($в случае равенства получим недопустимую БФ$)$, функция на наборе из $l$ «единиц» и $(k-l)$ «нулей» принимает значение $1$, а из $(l+1)$ «единиц» и $(k-l-1)$ «нулей» $-$ 0, т. е. с точностью до перестановки переменных
\begin{center}
$\beta(1,\ldots,1,0,0,\ldots,0)[1,\ldots,1]=1$ \\
$\beta(1,\ldots,1,1,0,\ldots,0)[1,\ldots,1]=0$
\end{center}
Выберем наименьшее из возможных $l$. Обозначим в $f$ переменную, стоящую на  $(l+1)$ месте за $x$. Отождествим остальные переменные, принимающие в функции $\beta$ значение 0 с y, а принимающие  1 $-$ c z. Тогда  

\begin{center}
$\beta(\chi_{A}(x),\chi_{A}(y),\chi_{A}(z)):\beta(0,0,1)=1,\beta(1,0,1)=0$
\end{center}
Пусть $g$ – частично вычислимая селекторная функция, полученная из $f$ отождествлением соответствующих переменных, а $a\in A,$ $\overline{a} \in N\setminus A,$ тогда 

\begin{center}
$g(x,\overline{a},a) \in A\Leftrightarrow x\notin A,$
\end{center}
т. к., вычислимая функция $g$ определена для любого аргумента $x$, значит, при $x\neq a$ и $x\neq \overline{a}$ , верно $g(x,\overline{a},a)\neq x$, что означает
\begin{center}
$x\in A\Leftrightarrow g(x,\overline{a},a)=\overline{a}.$
\end{center}
Поэтому, $A$ является вычислимым множеством.

Если особым сужением $\beta$ является функция $\beta(1,…,1)[0,…,0]=0,$ то, заменив все 0 на 1 и наоборот, и рассуждая аналогичным образом, получим, что и в этом случае $A$ является вычислимым. 
\end{proof}

Замечание. Если же сужение (без ограничения общности - по первым $k$ переменным) является константой, т. е. 
\begin{center}
$(\forall x_{1},…,x_{k} )\beta(\chi_{A} (x_{1} ),…,\chi_{A} (x_{k} ))[\theta,…,\theta]=\theta,\theta=1 (0).$
\end{center}
то по лемме 3 $\beta$-ОКС множество $A$ будет перечислимым (коперечислимым). Обратно, для любого перечислимого (коперечислимого) множества $B$, определим функцию $f$, перечисляя множество $B$ $(N\setminus B):$
\begin{center}
\begin{equation*}
f(x_{1},…,x_{k},x_{k+1},…,x_{n })= 
\begin{cases}
   x_{n},\text{если вычислятся } x_{k+1},...,x_n\\
   \uparrow ,  \text{ в противном случае }.
\end{cases}
\end{equation*}
\end{center}
Тогда B будет $\beta$-ОКС множеством с частично вычислимой селекторной функцией $f$.


\begin{theorem}
Для произвольной допустимой частичной БФ $\beta$, семейство $\beta$-ОКС множеств совпадает с семейством вычислимых множеств $\textbf{R}$ или с семейством полурекурсивных перечислимых $\textbf{E}_{1}\cap \textbf{S}$ или с семейством полурекурсивных коперечислимых множеств $\textbf{E}_{0}\cap \textbf{S} $ или же с семейством перечислимых $ \textbf{E}_{1} $ или коперечислимых $\textbf{E}_{0}$ множеств.
\end{theorem}

\begin{proof}
Как было доказано ранее (лемма 7), для неразложимой БФ $\beta$, любое $\beta$-ОКС множество является вычислимым. Исключением являются функции $\beta_{\theta}$, для которых семейство $\beta_{\theta}$-ОКС множеств совпадает с классом $\textbf{E}_{\theta}$ (лемма 5).

Рассмотрим далее разложимые БФ. Пусть множество $A$ является $\beta$-ОКС для некоторой разложимой частичной БФ $\beta$ с соответствующей вычислимой функцией $f(x_{1},…,x_{n} )$. Рассмотрим последовательность максимальных сужений функции  $\beta: \beta_{1},\beta_{2},…,\beta_{r}$. Если хотя бы одно из сужений является особым, то множество $A$ будет вычислимым (лемма 8). Поэтому, считаем данный случай рассмотренным. Иначе, так как 
\begin{center}
$\beta_{1}(\chi_A(x_{11}),\chi_A(x_{12}),...,\chi_A(x_{1k_{1}}))=\beta(\chi_A(x_{11}),\chi_A(x_{12}),...,\chi_A(x_{1k_{1}}))[\theta,\theta,...,\theta]$
\end{center}
всюду определенная БФ, то соответствующая ей вычислимая функция \\
$f_{1} (x_{11},x_{12},…,x_{1k_{1}})$, полученная из $n-$местной функции $f$  подстановкой  
\begin{center}
  $x_{1(k_{1}+1)}=x_{1(k_{1}+2)}=…=x_{1n}=a_{\theta},$ 
  \end{center}
  станет также всюду определенной, где $a_{\theta }$ $-$ фиксированный элемент, такой что
\begin{center}
\begin{equation*}
a_{\theta} \in
\begin{cases} 
A, \text{если }  \theta=1 \\
N\setminus A,\text{если }  \theta=0.
\end{cases}
\end{equation*}
\end{center}
Однако, нельзя утверждать, что функция $f_{1}$ будет селекторной. Поэтому, определим по ней $k_{1}$-местную вычислимую функцию $g_{1}$ следующим образом: учитывая утверждение леммы 3 будем перечислять множество $A$ $(N\setminus A)$, если $\theta =1 (0)$, и положим
\begin{center}
$g_{1}(x_{11},x_{12},...,x_{1k_{1}})=f_{1}(x_{11},x_{12},...,x_{1k_{1}})$, если $f_{1}(x_{11},x_{12},...,x_{1k_{1}})\neq a_{\theta}.$
\end{center}
Если же $f_{1}(x_{11},x_{12},...,x_{1k_{1}})= a_{\theta}$ и вычислилось первым значение
\begin{center}
 $x_{1i}\in \lbrace x_{11},x_{12},...,x_{1k_{1}}\rbrace, $ 
 \end{center}
 то положим $g_{1}(x_{11},x_{12},...,x_{1k_{1}})=x_{1i}$. Заметим, что такое значение вычислится всегда, т. к. сужение не является особым. Таким образом, вычислимая функция $g_1$ будет селекторной, а множество $A$ окажется $\beta_1$-селекторным с соответствующей функцией $g_1$. Такие множества были рассмотрены в работе [1], в которой  доказано, что семейство $\beta$-селекторных множеств совпадает либо с семейством рекурсивных $(\textbf{R})$, либо с семейством полурекурсивных $(\textbf{S})$ множеств. Если снять ограничение и считать функцию $\beta(x)=x$ допустимой, то следует добавить к рассмотрению семейство всех подмножеств множества $N$. Учитывая тот факт, что $A\in \textbf{E}_\theta ,$ где $\theta \in \lbrace 0,1\rbrace,$ можно утверждать: $ A$ принадлежит одному из классов:$ \textbf{E}_\theta,\textbf{E}_\theta \cap \textbf{S},\textbf{R},\theta\in\lbrace0,1\rbrace.$

Аналогично показывается, что множество $A$ является также $\beta_2,…,\beta_r$-селек\-торным множеством с соответствующими всюду определенными вычислимыми функциями $g_2,…,g_r$, т. е. $A\in K_1 \cap K_2\cap \ldots \cap K_r$, где 
\begin{center}
$K_i\in \lbrace \textbf{R},\textbf{E}_\theta,\textbf{E}_\theta \cap \textbf{S}\rbrace,\theta \in \lbrace 0,1 \rbrace,i \in \lbrace 1,…,r\rbrace,$
\end{center} 
а, стало быть, $A$ принадлежит одному из классов:
\begin{center}
$\textbf{R},\textbf{E}_\theta,\textbf{E}_\theta \cap \textbf{S},\theta \in \lbrace 0,1 \rbrace.$
\end{center}
Обратно, возьмём произвольное множество $B$ из того же класса, что и множество $A$. Тогда $ B \in K_{1} \cap K_{2} \cap \ldots \cap K_{r}, $ т. е. $B \in K_j,$ для любого $j \in \lbrace1,…,r\rbrace$. Если для некоторого значения индекса $s$ окажется, что
\begin{center}
$\beta_s (\chi_B(x_{s1}),\chi_B(x_{s2}),…,\chi_B(x_{sk_{s}}))[\theta,…,\theta]=\theta=const, \theta=1 (0),$
\end{center} 
определим соответствующую функцию
\begin{center}
\begin{equation*}
h^{1}_{s} (x_1,…,x_k,x_{k+1},…,x_n )=
\begin{cases} 
x_{sn}, \text{если }   x_{s(k_s+1)},…,x_{sn} \text{ вычислятся в } B   (N\setminus B)\\
\uparrow,\text{ в противном случае}.
\end{cases}
\end{equation*}

\end{center} 

Здесь и далее индекс переменной $x_{jl}$, $l\in \lbrace 1,...,n \rbrace$ обозначает ее позицию в функциях $h^1_j$

В других случаях множество B будет $\beta_j$-селекторным множеством, а соответствовать ему $-$ всюду определенная вычислимая селекторная функция $h_j(x_{j1},x_{j2},...,x_{jk_j})$. Доопределим каждую из таких функции $h_j$ до $n$-местных частично вычислимых функций $h_j^1$ следующим образом: перечисляя множество $B$ $(N\setminus B)$, если $B\in \textbf{E}_1 (\textbf{E}_0)$, положим $h_j^1=h_j$, если значения переменных, которые входят в $h_j^1$, но не входят в $h_j$, т.е.
$x_{j(k_{j}+1)},x_{j(k_{j}+2)},…,x_{jn},$ принадлежат $B$ $(N \setminus B)$, и $h_j^1$ не определено иначе. Очевидно, функция $h_j^1$ тоже будет селекторной.

Таким образом, получим множество частично вычислимых селекторных \\функции $h_j^1 (x_1,…,x_n ), j \in \lbrace1,…,r\rbrace$. Будем одновременно вычислять значения этих функций. Если первым вычислится значение $h_k^1 (x_1^0,x_2^0,…,x_n^0 )$, для некоторого набора значений переменных $x_1^0,x_2^0,…,x_n^0,$ то положим 
\begin{center}
$h(x_1^0,x_2^0,…,x_n^0 )=h_k^1 (x_1^0,x_2^0,…,x_n^0 ),$
\end{center} 
 если же ни одно из значений $h_j^1 (x_1^0,x_2^0,…,x_n^0 )$ не вычислится, положим \\ $h(x_1^0,x_2^0,…,x_n^0 )\uparrow$. Тогда множество B будет $\beta$-ОКC множеством с соответствующей вычислимой функцией $h(x_1,…,x_n )$.

\end{proof}

	\section{Заключение}
В качестве визуализации полученных результатов представим диаграмму соотношения между классами $\beta$-ограниченно комбинаторно-селекторных множеств по включению.

\begin{figure}[h]

\centering

\includegraphics[width=0.8\linewidth]{1oummm.jpg}

\caption{Диаграмма включения классов $\beta$-ограниченно комбинаторoно-селекторных множеств.}

\label{fig:mpr}

\end{figure}
 









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


\bibitem{1} Degtev A.N., 
{\it Recursive-combinatorial properties of subsets of the natural numbers}, Algebra and Logic, 29:3 (1990), 204–210. Zbl 0727.03026 


\bibitem{2} Degtev A.N., 
{\it Weak combinatorial selective properties of subsets of the natural numbers}, Algebra and Logic, 29:4 (1990), 280–286. MR1155470. Zbl 0733.03033


\bibitem{3} Degtev A.N.,
{\it Implicatively selector sets}, Algebra and Logic, 35:2 (1996), 80–85. MR1444649

\bibitem{4} Degtev A.N., 
{\it Almost combinatorial selector sets}, Mathematical notes, 68:6 (2000), 721–723. MR1835183. Zbl 0990.03032

\bibitem{5} Degtev A.N., Ivanov D.I., 
{\it Weakly combinatorial selector sets}, Algebra and Logic, 37:6 (1998), 357–362. MR1680420. Zbl 0913.03047


\bibitem{6} Degtev A.N., Ivanov D.I., 
{\it Weakly implicatively selective sets of dimension 3}, Discrete Mathematics and Applications, 9:4 (1999), 395–402. MR1739074. Zbl 0965.03055


\bibitem{7} Degtev A.N., Ivanov D.I., 
{\it About the classes of linear and self-dual weakly implicative selector sets}, Tyumen State University Herald, 4 (2004), 238–241 [in Russian].


\bibitem{8} Jockusch, C. G. Jr., 
{\it Semirecursive sets and positive reducibility}, Transactions of the American Mathematics Society, 131:2 (1968), 420–436. MR220595. Zbl 0198.32402


\bibitem{9} Ivanov D.I., 
{\it Weakly implicative selector sets}, Russian Mathematics, 50:9 (2006), 27–31. Zbl 07092351


\bibitem{10} Ivanov D.I., 
{\it Weakly combinatorial-selector sets}, Russian Mathematics, 50:11 (2006), 20–23 (2006). Zbl 07092373


\bibitem{11}Ivanov, D.I., Platonov, M.L., 
{\it Limited-combinatorial sets}, Siberian Electronic Mathematical Reports, 16 (2019), 1553—1560. [in Russian]. Zbl 1436.03222


\end{thebibliography}
\end{document}
