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


\usepackage{color}

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

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

\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 Том 17, стр. xxx--xxx (2020) \hspace{65mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.33048/semi.2020.xx.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

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


\thispagestyle{empty}

\title[Специальные классы позитивных предпорядков]{Специальные классы позитивных предпорядков}
\author{{С.А. БАДАЕВ, Б.С. КАЛМУРЗАЕВ, Н.К. МУКАШ, А.А. ХАМИТОВА}}%
\address{Serikzhan Badaev, Birzhan Kalmurzayev, Nazgul Mukash  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Kazakh-British Technical University,
\newline\hphantom{iii} Tole Bi str. 59,
\newline\hphantom{iii} 050000, Almaty, Kazkhstan}%
\email{s.badaev@kbtu.kz, birzhan.kalmurzayev@gmail.com, mukash.nazgul1@gmail.com}%
\address{Aruna Khamitova  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} M.Utemisov WKSU,
\newline\hphantom{iii} Dostyk-Druzhby Ave. 162,
\newline\hphantom{iii} 090000, Uralsk, Kazkhstan}%
\email{arunabaevna@gmail.com}%

\thanks{\sc Badaev, S.A., Kalmurzayev, B.S, Mukash, N.K., Khamitova, A.A.
Specail classes of positive preorders}
\thanks{\copyright \ 2020 Бадаев С.А, Калмурзаев Б.С., Мукаш Н.К}
\thanks{\rm Работа поддержана Комитетом науки МОН РК (грант АР08856493)}
\thanks{\it Поступила 1 января 2020 г., опубликована 31 декабря 2020 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\sc Abstract. } We study positive preorders relative to computable redu\-ci\-bi\-li\-ty. It is suggested an approach to lift well-known notions from the theory of ceers to positive preorders. It is shown that each class of positive preoders of a special type (precomplete, $e$-complete, weakly precomplete, effectively finite precomplete, and effectively inseparable ones) contains infinitely many incomparable elements and has an universal object. We construct a pair of incomparable dark positive preorders that possess an infimum. It is shown that, for every non-universal positive preorder $P$, there are infinitely many pairwise incomparable minimal weakly pre\-com\-p\-lete positive preorders that are incomparable with $P$.

\medskip

\noindent{\bf Keywords:} positive preorder, ceer, computable reducibility, precomplete, weakly precomplete, minimal preorder.
 \end{quote}
}


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

Работа посвящена изучению позитивных предпорядков, заданных на множестве натуральных чисел $\omega$. Под позитивным предпорядком мы понимаем вычислимо перечислимое рефлексивное и транзитивное бинарное отношение. Частный случай позитивных предпорядков -- позитивные эквивалентности -- изучены достаточно хорошо. Классическими работами в этой области можно считать работы Ю.Л.~Ершова \cite{Ersh73}, К.~Бернарди и А.~Сорби \cite{BerSor83}, А.~Лахлана \cite{Lach87}, С.А.~Бадаева \cite{Bad91}, С.~Гао и П.~Гердеса \cite{GaoGer}. Современное состояние исследований позитивных эквивалентностей отражено в обзоре \cite{ABS17}, статьях \cite{UriSorbi}--\cite{BMSY17} и работах других авторов.

Если $E$ -- позитивная эквивалентность, то на фактор-множестве $\omega/E$ можно задавать функции и отношения и получать интересные структуры с относительно вычислимыми свойствами. Мотивацией такого подхода послужила для нас работа Ф.~Монтаньи и А.~Сорби \cite{MS85}, в которой в качестве $E$ берется отношение доказуемой эквивалентности предложений арифметики Пеано, а операции на $\omega/E$ естественно порождаются логическими связками. Некоторые современные исследования в области позитивных эквивалентностей идут в противоположном направлении, решая, например, вопросы о представимости линейных порядков \cite{FKST16}  или булевых алгебр \cite{BMSY17} в виде фактор-структуры $\omega/E$ для подходящей позитивной эквивалентности $E$. В настоящей работе для каждого позитивного предпорядка $P$ мы вводим так называемый \textit{носитель} $E$ предпорядка $P$, т.е. максимальную позитивную эквивалентность, содержащуюся в предпорядке $P$, и фактически работаем с частично упорядоченным множеством $\omega/E$.
На основе понятия  носителя мы обобщаем некоторые известные понятия и результаты теории позитивных эквивалентностей на позитивные предпорядки.

Если $R$ и $S$ -- это предпорядки на $\omega$, то говорят, что $R$ \textit{вычислимо сводится} к $S$ (обозначается через $R\leq_c S$), если существует вычислимая функция $f$, такая что  $xRy \Leftrightarrow f(x)Sf(y)$ для любых $x,y\in\omega$. Предпорядки $R$ и $S$ называют \textit{эквивалентными} (обозначается через $R\equiv_c S$), если $R\leq_c S$ и $S\leq_c R$. Предпорядки $R$ и $S$ называются \textit{вычислимо изоморфными}, если существует вычислимая перестановка множества $\omega$, сводящая $R$ к $S$. Позитивный предпорядок называется \textit{универсальным}, если любой позитивный предпорядок вычислимо сводится к нему. Известное понятие \textit{универсальной позитивной эквивалентности} было введено схожим образом, как максимальной среди всех позитивных эквивалентностей относительно вычислимой сводимости.

В разделе 1 данной работы мы приводим определения предполноты, слабой предполноты, $e$-полноты, равномерно конечной предполноты и эффективной неотделимости позитивных предпорядков и доказываем существование универсальных позитивных предпорядков указанных выше типов. В разделе 2 мы исследуем вопросы существования точных верхних и нижних граней несравнимых позитивных предпорядков. А в разделе 3 для произвольного не универсального позитивного   предпорядка $P$ мы показываем существование бесконечного числа попарно не сравнимых слабо предполных минимальных позитивных Предпорядков, не сравнимых с $P$.


\section{Специальные классы позитивных предпорядков}

Напомним некоторые понятия, оказавшиеся плодотворными при исследовании универсальных позитивных эквивалентностей. Понятие предполной эквивалентности  было введено А.И. Мальцевым в работе \cite{Mal61}. Оно сыграло значительную роль в различных областях теории вычислимости, в том числе в теории позитивных эквивалентностей. Эквивалентность $E$ называется \textit{предполной}, если она содержит хотя бы два класса эквивалентности и для любой частично вычислимой функции $\varphi$ найдется вычислимая функция $f$ такая, что $\varphi(x)E f(x)$ для всех $x\in\mathrm{dom}(\varphi)$.

Согласно определению А. Лахлана \cite{Lach87}, позитивная эквивалентность $S$ называется \textit{$e$-полной} (от \textit{extension complete}), если для любой позитивной эквивалентности $R$ и любой конечной функции $f$, являющейся вложением $\langle \mathrm{dom}(f), R\upharpoonright\mathrm{dom}(f) \rangle$ в $\langle\omega, S\rangle$, и для любого $i\in\omega\smallsetminus\mathrm{dom}(f)$ можно по  числу $i$, каноническому номеру функции $f$ и вычислимо перечислимому индексу отношения $R$ эффективно найти число $j$ такое, что $f\cup \{\langle i,j \rangle\}$ является вложением $\langle \mathrm{dom}(f)\cup\{i\}, R \rangle$ в $\langle \omega, S \rangle$.
В \cite{Lach87} установлено, что $e$-полные позитивные эквивалентности и предполные позитивные эквивалентности являются универсальными и образуют два различных типа вычислимого изоморфизма.

\begin{definition}
Пусть $P$ -- произвольный предпорядок. Отношение эквивалентности $E=\{(x,y):~xPy~\&~yPx\}$ назовем \textsl{носителем} предпорядка $P$ и обозначим эквивалентность $E$ через $\mathrm{supp}(P)$.
\end{definition}

Очевидно, что носитель $\mathrm{supp}(P)$ позитивного предпорядка $P$ является позитивной эквивалентностью. Однако, обратное не верно. Действительно, если $X$ -- не вычислимо перечислимое множество, то предпорядок $Q=\{(2x,2x+1):~x\in X\}$ не является позитивным, но его носитель является тождественным отношением эквивалентности $\mathrm{Id}$.

\begin{remark}
Для любых предпорядков $P_1, P_2$, если $P_1\leq_c P_2$, то $\mathrm{supp}(P_1)\leq_c \mathrm{supp}(P_2)$.
\end{remark}

Обратное утверждение не верно. Например, $\mathrm{supp}(Q)\leq_c \mathrm{supp(Id)}$ но $Q\nleq_c \mathrm{Id}$.\\

\begin{definition}
Предпорядок $P$ назовём предполным (слабо предполным, $e$-полным, равномерно конечно предполным, или эффективно неотделимым), если носитель предпорядка $\mathrm{supp}(P)$ является предполной (соответственно, слабо предполной, $e$-полной, равномерно конечно предполной, или эффективно неотделимой) эквивалентностью.
\end{definition}

\begin{theorem}
Для любого позитивного предпорядка $P$ существует предполный позитивный предпорядок $Q$ такой, что $P\leq_c Q$.
\end{theorem}

\begin{proof}

Пусть $P$ -- произвольный позитивный предпорядок, а $E$ -- универсальная предполная эквивалентность. Тогда $\mathrm{supp}(P)\leq_c E$ посредством некоторой вычислимой фуркции $f$. Определим позитивный предпорядок $Q$ следующим образом: для любых $x,y\in\omega$
$$xQy\Leftrightarrow xEy\vee (\exists u) (\exists v) [xEf(u)~ \&~ yEf(v)~ \&~ uPv]$$

Не сложно заметить, что $P\leq_c Q$ и $\mathrm{supp}(Q)=E$. В силу выбора $E$ предпорядок $Q$ является предполным.
\end{proof}

\begin{corollary}
Универсальные предполные позитивные предпорядки существуют.
\end{corollary}
\begin{proof}
В качестве $P$ в доказательстве теоремы достаточно взять любой универсальный позитивный предпорядок, \cite{BKKA}.
\end{proof}

Предполные позитивные эквивалентности являются универсальными, \cite{BerSor83},  и, следовательно, все они попарно эквивалентны. Более того, нетривиальные предполные позитивные эквивалентности образуют единственный тип вычислимого изоморфизма, \cite{Lach87}. Для предполных позитивных предпорядков картина совершенно иная, как это вытекает из следующего следствия. В частности, предполные позитивные эквивалентности могут быть и не универсальными.

\begin{corollary}
Существует бесконечно много неэквивалентных предполных позитивных предпорядков.
\end{corollary}

\begin{proof}
Рассмотрим вычислимую последовательность $\{P_k\}_{k\in\omega}$ позитивных предпорядков таких, что
\begin{itemize}
\item $\mathrm{supp}(P_k)=\mathrm{Id}_{k+1}$,
\item $(\forall i\leq j\leq k)([i]_{\mathrm{Id}_{n+1}}P_k[j]_{\mathrm{Id}_{n+1}})$.
\end{itemize}
Каждый $P_k$ -- это позитивный предпорядок, фактор которого по носителю является линейным порядком, изоморфным порядку $\{0<1<2<\ldots<k\}$. Очевидно, что $P_j\nleq_c P_i$ для любых $i<j$. Обозначим через $Q_k$ позитивный предпорядок, который можно построить как в доказательстве Теоремы 1, когда в качестве $P$ выступает позитивный предпорядок $P_k$. Тогда $Q_j\nleq_c Q_i$ для любых $i<j$.
\end{proof}

Известно, что в каждом из следующих классов:
\begin{itemize}
  \item позитивных слабо предполных эквивалентностей,
  \item позитивных $e$-полных эквивалентностей,
  \item позитивных равномерно конечно предполных эквивалентностей,
  \item позитивных эффективно неотделимых  эквивалентностей,--
\end{itemize}
существуют универсальные эквивалентности, см. обзорную статью \cite{ABS17}. Применяя конструкцию доказательства Теоремы 1, получаем следующее

\begin{corollary}
Для любого позитивного предпорядка $P$ существует позитивный предпорядок $Q$ из каждого из перечисленных выше классов такой, что $P\leq_c Q$.
\end{corollary}

\section{Точные верхние и нижние грани}

Множество позитивных предпорядков относительно вычислимой сводимости $\leq_c$ является предпорядковой структурой, фактор структура которой по отношению эквивалентности $\equiv_c$ образует частично упорядоченное множество относительно упорядочения, индуцированного $\leq_c$. Допуская некоторую вольность речи, будем говорить, что позитивный предпорядок $P$ состоит из классов эквивалентности (точнее, классов эквивалентности его носителя  $\mathrm{supp}(P)$), связанных отношением $P$.

Одними из важных проблем при изучении любых упорядоченных структур являются вопросы существования наименьших верхних граней и наибольших нижних граней. В работе \cite{UriSorbi} исследовались вопросы существования супремумов и инфимумов степеней позитивных эквивалентностей относительно вычислимой сводимости. Результаты этой работы сведены в нижеследующие таблицы:

$$\begin{array}{c|c|c}
   X & Y & X\wedge Y?  \\
   \hline
   \text{light} & \text{light} & \text{-иногда НЕТ} \\
   \empty & \empty & \text{-иногда ДА}  \\
   \hline
   \text{dark} & \text{dark} & \text{НЕТ} \\
   \hline
   \text{light} & \text{dark} & \text{НЕТ}
 \end{array}
$$
\begin{center}
  \textbf{Таблица 1.} \textit{Существование инфимумов в \\ структуре позитивных эквивалентностей}\\
\end{center}

$$\begin{array}{c|c|c}
   X & Y & X\vee Y?  \\
   \hline
   \text{light} & \text{light} & \text{-иногда НЕТ} \\
   \empty & \empty & \text{-иногда ДА}  \\
   \hline
   \text{dark} & \text{dark} & \text{НЕТ} \\
   \hline
   \text{light} & \text{dark} & \text{-иногда НЕТ} \\
   \empty & \empty & \text{-иногда ДА}
 \end{array}
$$
\begin{center}
  \textbf{Таблица 2.} \textit{Существование супремумов в \\ структуре позитивных эквивалентностей}\\
\end{center}
\bigskip

Конечно же в этих таблицах рассматривались несравнимые позитивные эквивалентности $X$ и $Y$.

Напомним (см., например, \cite{ABS17}), что через $\mathrm{Id}_n$ обозначается эквивалентность с $n$ вычислимыми классами. Через $\mathrm{Id}$ обозначается тождественная эквивалентность. Эквивалентность $E$ называется \textit{тёмной (dark)}, если $E$ не сравнима с $\mathrm{Id}$. Эквивалентность $E$ с бесконечно многими классами называется \textit{светлой (light)}, если она не тёмная.

Используя естественный подход, намеченный в разделе 1, введем понятия тёмного, светлого и конечного предпорядков следующим образом.

\begin{definition}
Позитивный предпорядок $P$ называется \textit{тёмным (конечным, светлым)}, если носитель $\mathrm{supp}(P)$ является тёмной эквивалентностью (состоит из конечного числа классов; не является ни конечной, ни тёмной  эквивалентностью).
\end{definition}

Отметим, что в работе \cite{BazhKal} введено несколько иное понятие тёмного позитивного предпорядка $P$ для случая, когда $P$ индуцирует линейный порядок на $\mathrm{supp}(P)$.

Так как позитивные эквивалентности являются также позитивными предпорядками, то на вопросы существования супремумов и инфимумов в приведённых выше таблицах случаи с ответами "иногда ДА, иногда НЕТ"\, можно не рассматривать. В данной работе мы рассмотрим только случай, когда оба предпорядка являются тёмными.


\begin{theorem}
Существуют несравнимые тёмные позитивные предпорядки, имеющие наибольшую нижнюю грань.
\end{theorem}

\begin{proof}
Пусть $S$ -- простое множество. Тогда $R_S=\{(x,y): x=y\vee \{x,y\}\subseteq S\}$ -- тёмная позитивная эквивалентность. Определим предпорядки $P$ и $Q$ следующим образом:
$$P=R_S\oplus \mathrm{Id}_1;$$
$$Q=R_S\oplus \mathrm{Id}_1 \cup \{(2x,2y+1): x\in S\}.$$

Очевидно, что позитивные предпорядки $P$ и $Q$ являются тёмными. Покажем, что они не сравнимы, а $R_S$ является их точной нижней гранью. Нетрудно заметить, что предпорядок $P$ является позитивной эквивалентностью и что у позитивного предпорядка $Q$ в точности два класса эквивалентности $2S$ и $2\omega+1$ являются связанными, в частности, $Q$ не является эквивалентностью. Ясно, что предпорядок, вычислимо сводимый к любой эквивалентности, сам является эквивалентностью. Отсюда сразу получаем, что $Q\nleq_c P$.

Докажем, что и $P\nleq_c Q$. Допустим, что $P\leq_c Q$ посредством вычислимой функции $f$. В силу сводимости, образ функции $f$ не может пересекать оба связанных $Q$-класса $2S$ и $2\omega+1$. Если $\mathrm{range}(f)\cap 2S=\emptyset$, то $2S$ является прообразом вычислимого множества, а это невозможно. Если же $\mathrm{range}(f)\cap 2S\neq\emptyset$, то функция $f([\frac{x}{2}])$ осуществляет не сюръективную сводимость $R_S\leq_c R_S$, что также невозможно. Таким образом, позитивные предпорядки $P$ и $Q$ не сравнимы.

Ясно, что $R_S$ является нижней гранью $P$ и $Q$. Пусть позитивный предпорядок $T$ является нижней гранью предпорядков $P$ и $Q$. Так как $P$ является эквивалентностью и $T\leq_c P$, то предпорядок $T$ также является эквивалентностью. Пусть $T\leq_c Q$ посредством вычислимой функции $g$. Как и выше, заметим, что $\mathrm{range}(g)$ не может пересекать оба связанных $Q$-класса $2S$ и $2\omega+1$ и рассмотрим два случая.

Случай 1. $\mathrm{range}(g)\cap 2S=\emptyset$. Так как все $Q$-классы эквивалентности, кроме класса $2S$ являются вычислимыми, то все классы эквивалентности $T$ также являются вычислимыми. Докажем от противного, что количество классов эквивалентности в $T$ конечно. Допустим, что $T$  имеет бесконечно много классов эквивалентности. Тогда $\mathrm{range}(g)$ состоит из бесконечного числа $Q$-классов. Следовательно, вычислимо перечислимое множество $\mathrm{range}(g)\smallsetminus (2\omega+1\cup 2S)$ является бесконечным, а это невозможно ввиду простоты множества $S$. Итак, $T$ является разбиением $\omega$ на конечное число вычислимых множеств, и, следовательно, $T\leq_c R_S$.

Случай 2. $\mathrm{range}(g)\cap 2S\neq\emptyset$. Тогда $\mathrm{range}(g)\cap 2\omega+1=\emptyset$ и вычислимая функция $\frac{g(x)}{2}$ осуществляет сводимость эквивалентности $T$ к $R_S$.

Следовательно, $R_S$ является наибольшей нижней гранью позитивных предпорядков $P$ и $Q$.
\end{proof}


\section{Слабо предполные минимальные позитивные предпорядки}

Для позитивных эквивалентностей в работе \cite{UriSorbi} У.Андрюсом и А.Сорби был установлен следующий факт.
\begin{theorem}\label{theo:AS}
Пусть $R$ - не универсальная позитивная эквивалентность. Тогда найдётся бесконечно много попарно не сравнимых позитивных эквивалентностей $\{E_l\}_{l\in\omega}$ таких, что для каждых $l$ и позитивной эквивалентности $X$
\begin{enumerate}
  \item $E_l\nleq R$
  \item $X\leq E_l \Rightarrow (\exists n)[X\leq \mathrm{Id}_n]$
\end{enumerate}
\end{theorem}

Заметим, что в Теореме \ref{theo:AS} нет необходимости строить бесконечную последовательность эквивалентностей $\{E_l\}_{l\in\omega}$, достаточно строить только одну.  Кроме того, можно дополнительно потребовать, чтобы эта эквивалентность была слабо предполной. Используя идеи доказательства Теоремы \ref{theo:AS}, мы докажем её аналог для позитивных предпорядков.

\begin{definition}
Предпорядок  $P$ назовем минимальным, если для любого предпорядка $X$ сводимость $X\leq_c P$ влечёт сводимость  $P\leq_c X$ или конечность числа классов эквивалентности носителя $\mathrm{supp}(P)$.
\end{definition}


\begin{theorem}\label{theo: min wp}
Для любого не универсального позитивного предпорядка $R$ найдется слабо предполный минимальный позитивный предпорядок $P$, не сводящийся к $R$.
\end{theorem}

\begin{proof}
Пусть $R$ -- не универсальный позитивный предпорядок. Построим позитивный предпорядок $P$, удовлетворяя следующие требования для любых $i,j,k,e \in \omega:$

 $P_{i,j}:$ Если множество $W_i$ пересекает бесконечно много классов эквивалентности $\mathrm{supp}(P)$, то оно пересекает класс $[j]_{\mathrm{supp}(P)}.$

 $T_{k}:$ $\varphi_k$ не является сводящей функцией $P$ к $R.$

 $WP_{e}:$ Если $\varphi_e$ всюду определена, то $\exists x_e((x_e,\varphi_e (x_e))\in \mathrm{supp}(P)).$

 Основной операцией в нашем построении является операция рефлексивного и транзитивного замыкания, обозначаемая символом $*$: для произвольного бинарного отношения $X$ через $X^*$ обозначается наименьший предпорядок, содержащий $X$. Каждый раз, когда в строящийся предпорядок добавляется одна или несколько пар чисел, для полученного бинарного отношения немедленно выполняется операция $*$.

 Через $(R^s)_{s\in\omega}$ обозначим равномерно вычислимую последовательность позитивных предпорядков со свойствами:
 $R^0=\mathrm{Id}, \bigcup_{s\in\omega}R^s=R,$ для каждого $s$ имеет место следующее соотношение: $R^{s+1}=(R^s\cup\{(x_s,y_s)\})^*$ для некоторой пары чисел $(x_s,y_s)$.

 Под \textit{большим} числом мы понимаем число, которое больше всех чисел, уже использованных в построении.

 \textbf{Изолированная стратегия удовлетворения требования $P_{i,j}$:}

 (1) Выбираем большое число $t.$

 (2) Если $W_i\cap[j]_{\mathrm{supp}(P)}=\emptyset,$ то ждём пока $W_{i}\cap[k]_{\mathrm{supp}(P)}\neq\emptyset$ для некоторого $k\geq t.$

 (3) Добавляем пары $(j,k)$ и $(k,j)$ в  $P$.

 \textbf{Изолированная стратегия удовлетворения требования $T_{k}$:}

 Фиксируем универсальный позитивный предпорядок $U$.

 (1) Выбираем \textit{свежие} (т.е. ранее не использованные) числа $a_0,a_1$ и полагаем параметр $r$ этой стратегии равным 1.

 (2) Для всех различных $i,j\leq r$ ставим запрет на добавление пар $(a_{i},a_{j})$  в $P$, если они уже не находятся в $P$. Этот запрет относится только к стратегиям, отличным от $T_{k}$.

 (3) Ждём, пока все значения $\varphi_{k}(a_0),\varphi_{k}(a_1),...,\varphi_{k}(a_r)$ станут определёнными на некотором шаге $s$.

 (4) Если для всех  $i,j\leq r $
 \begin{center}
 $a_{i}P^sa_{j}\Leftrightarrow\varphi_{k}(a_i)R^s\varphi_{k}(a_j), \qquad \qquad (\dag)$
 \end{center}
 то добавляем пары $(a_{i},a_{j})$ в $P$ для всех $i,j\leq r$ таких, что $iU^sj$, увеличиваем на $1$ значение параметра $r$, выбираем свежий элемент $a_{r}$ и переходим к пункту (2).

  \textbf{Изолированная стратегия удовлетворения требования $WP_{e}$:}

 (1) Выбираем свежее число $x_e.$

 (2) Ждём, пока определится значение $\varphi_{e}(x_e)$.

 (3) Добавляем пары $(\varphi_{e}(x_e),x_e)$ и $(x_e,\varphi_{e}(x_e))$ в $P.$

\medskip

Понятно, что выполнение всех требований $T_{k},k\in\omega,$ и $WP_{e},e\in\omega,$ гарантирует несводимость предпорядка $P$ к $R$ и слабую предполноту $P$. Покажем, что выполнение всех требований
$P_{i,j}, i,j\in\omega,$ гарантирует минимальность предпорядка $P$. Действительно, пусть $X$ -- произвольный позитивный предпорядок, сводящийся к $P$ посредством некоторой вычислимой функции $f$. И пусть $W_i$ есть $\mathrm{range}(f)$. Если множество $W_i$ пересекает только конечное число классов эквивалентности $\mathrm{supp}(P)$, то прообразом  $f$ может быть только позитивный предпорядок, носитель которого состоит из конечного числа классов эквивалентности. Если же $W_i$ пересекает бесконечно много классов эквивалентности, то стратегии $P_{i,j},j\in\omega,$ в совокупности дают равенство $[\mathrm{range}(f)]_{\mathrm{supp}(P)}=\omega$ и вследствие позитивности предпорядка $P$ не сложно построить вычислимую сводящую функцию для сводимости $P\leq_c X$. Таким образом, $P$ является минимальным позитивным предпорядком.


\textbf{Конфликты стратегий.} Очевидно, что стратегии $P_{i,j}$ и $WP_{e}$ не конфликтуют между собой. Конфликты могут возникнуть, когда одна из этих стратегий желает добавить некоторую пару чисел в $P$, а эта пара уже находится под запретом, наложенным некоторой стратегией $T_{k}$. Заметим, что запреты налагаются только стратегиями $T_{k}$. Казалось бы, что стратегия $T_{k'}$ для $k'\neq k$ может препятствовать стратегии $T_{k}$ перечислить в $P$ пару  $(a_i,a_j)$ при выполнении пункта (4), налагая запрет на эту пару. Однако это не происходит, поскольку выбор параметров $a_0, a_1,\dots, a_r$ в обеих стратегиях $T_{k'}$ и $T_{k}$ производится из свежих чисел. По той же причине, параметры $x_e$, выбираемые стратегией $WP_{e}$, не могут быть компонентой ни одной пары, запрещённой ни одной из стратегий $T_{k}$. Таким образом, в нашем построении предпорядка $P$ мы должны заботиться только о разрешении конфликтов стратегий  $P_{i,j}$ и $T_{k}$.

Способ разрешения такого рода конфликтов давно известен -- это метод приоритета, в данном случае метод приоритета с конечными нарушениями. Мы считаем, что все стратегии линейно упорядочены: $S_0,S_1,S_2,\dots,S_k,\dots$, причём по номеру $k$ можно эффективно восстановить вид стратегии и её индексы. Будем говорить, что стратегия $S_k$ имеет больший приоритет, чем  $S_n,$ если  $k<n.$


 На каждом шаге $s$ конструкции рассматривается в точности одна из стратегий $S_l,l\in\omega,$ обозначаемая через $S^s$, при этом
  $S^s$ является вычислимой функцией аргумента $s$ и для любого $l$ существует бесконечно много $s$ таких, что $S^s=S_l$. К концу любого шага $s$ стратегия $S_l$ может быть либо \textit{активной}, либо \textit{пассивной}. На шаге $0$ все стратегии пассивны. Активная (пассивная) на шаге $s$ стратегия остаётся таковой до тех пор, пока на некотором большем шаге она не объявляется пассивной (соответственно, активной). Активная стратегия, ставшая пассивной, может быть реактивизирована на некотором большем шаге.

 \textit{Активизация (реактивизация)} стратегии $S_l$ означает выбор её параметров: для стратегий $P_{i,j}$, $T_{k}$ и $WP_{e}$ это выполнение пункта (1) этих стратегий, параметрами являются соответственно числа $t$, $r$, $a_0$, $a_1$ и $x_e$. По ходу конструкции значение параметра $r$ стратегии $T_{k}$ может быть увеличено, а в список её параметров могут быть добавлены свежие числа $a_r$, как это описано в пункте (4) этой стратегии. Кроме параметров $r$, $a_0$, $a_1$ стратегия $T_{k}$ при активизации формирует множество $\mathrm{res}(k)$, состоящее из пар чисел, которые стратегия $T_{k}$ запрещает добавлять в $P$ всем стратегиям меньшего приоритета. При активизации (реактивизации) $\mathrm{res}(k)$ состоит из двух пар $(a_0,a_1)$ и $(a_1,a_0)$, к которым при увеличении параметра $r$ добавляются новые пары в соответствии с пунктом (4) описания стратегии $T_{k}$.

 Объявление стратегии пассивной сопровождается тем, что все её параметры становятся неопределёнными, а множество запретов $\mathrm{res}(k)$ стратегии $T_{k}$ опустошается. После этого стратегия реактивизируется на большем шаге.

\medskip

 \textbf{Конструкция.}  Предпорядок $P$ строится по шагам. Через $P^s$ обозначается предпорядок на $\omega$, содержащий конечное число пар $(x,y)$ с $x\neq y$, построенный к концу шага $s$.

 Будем говорить, что активная стратегия $S^{s+1}$ \textit{требует внимания}, если
\begin{enumerate}
\item $S^{s+1}=S_l$ и $S_l$  есть стратегия $P_{i,j}$ для некоторых $i,j$ и выполнено условие: если $W_{i}^s\cap[j]_{\mathrm{supp}(P^{s})}=\emptyset$, то $W_{i}^s\cap[m]_{\mathrm{supp}(P^{s})}\neq\emptyset$ для некоторого $m\geq t$ такого, что $\{(j,m),(m,j)\}\cap\mathrm{res}(l')=\emptyset$ для всех $l'<l$, либо
\item $S^{s+1}=S_l$ и $S_l$  есть стратегия $T_{k}$ и значения $\varphi_{k}(a_0),\varphi_{k}(a_1),...,\varphi_{k}(a_r)$ определены на шаге $s$ для всех параметров $a_0,a_1,\dots,a_r$ стратегии $T_{k}$ и выполнено (\dag), либо
\item $S^{s+1}=S_l$ и $S_l$  есть стратегия $WP_{e}$ для некоторого $e$, $(y,\varphi_e(y))\notin\mathrm{supp}(P^{s})$ для каждого $y\in\mathrm{dom}(\varphi_e^s)$ и $\varphi_e^s(x_e)$ определено.
\end{enumerate}

 \textbf{Шаг 0.} Полагаем $P^{0}=\mathrm{Id}, \mathrm{res}(l)=\emptyset$ для любых $l$.    Все стратегии на шаге $0$ объявляем пассивными. Переходим к следующему шагу.

 \textbf{Шаг $s+1$.} Если стратегия $S^{s+1}$ является пассивной, то активизируем (реактивизируем) её и переходим к следующему шагу. Если стратегия $S^{s+1}$ является активной, но не требует внимания, то ничего на изменяя переходим к следующему шагу. Наконец, если стратегия $S^{s+1}$ требует внимания, то рассмотрим три случая.

\begin{enumerate}
  \item $S^{s+1}=S_l$ и $S_l$ есть стратегия $P_{i,j}$ для некоторых $i,j$. Если $W_{i}^s\cap[j]_{\mathrm{supp}(P^{s})}\neq\emptyset$, то сразу переходим к следующему шагу. В противном случае выбираем наименьшее число  $m\geq t$ такое, что  класс эквивалентности $[m]_{\mathrm{supp}(P^{s})}$ содержит число из $W_{i}^s$ и обе пары $(j,m),(m,j)$ не содержатся ни в одном из множеств $\mathrm{res}(l'), l'<1$; полагаем $P^{s+1}=(P^s\cup\{(j,m),(m,j)\})^*$; объявляем все стратегии  $S_l', l>l',$ пассивными.
  \item $S^{s+1}=S_l$ и $S_l$  есть стратегия $WP_{e}$ для некоторого $e$. Пусть $x_e$ -- параметр стратегии $WP_{e}$. Полагаем $P^{s+1}=(P^s\cup\{(x_e,\varphi_e(x_e)),(\varphi_e(x_e),x_e)\})^*$. Объявляем все стратегии  $S_l', l>l',$ пассивными.
  \item $S^{s+1}=S_l$ и $S_l$  есть стратегия $T_{k}$ для некоторого $k$. Пусть $r, a_0,a_1,\dots,a_r$ -- её параметры.  Полагаем $P^{s+1}=(P^s\cup\{(a_i,a_j): i,j\leq r \,\&\, (i.j)\in U^s\})^*$. Увеличиваем значение параметра $r$ на единицу. Полагаем параметр $a_{r+1}$ равным наименьшему свежему числу.  Добавляем в $\mathrm{res}_k$ все пары чисел $(a_1,a_{r+1}),(a_{r+1},a_i), i\leq r$. Объявляем все стратегии  $S_l', l>l',$ пассивными.
\end{enumerate}

Переходим к следующему шагу.

 \textbf{Верификация.} Очевидно, что для любого $s$ каждая стратегия, являющаяся пассивной на шаге $s$, будет активизирована (реактивизирована) на некотором большем шаге.

 \begin{lemma}\label{lem:1}
 Каждая стратегия требует внимания только конечное число раз.
  \end{lemma}

 \begin{proof}
 Для упрощения доказательства будем считать, что $S_0$ -- это $T_0$, а $\varphi_0$ -- нигде не определённая функция.  Тогда стратегия $S_0$ активизируется ровно один раз и никогда не требует внимания.

 Индукционный шаг. Пусть после некоторого шага $s_0$ ни одна из стратегий $S_0,S_1,\dots,S_{l-1}$ не требует внимания. Докажем, что после некоторого шага $s_1\geq s_0$ стратегия $S_l$ также не будет требовать внимания. Не трудно заметить, что если $S_l$ это одна из стратегий $P_{i,j}$ или $WP_{e}$, то после шага $s_0$ стратегия $S_l$ может потребовать внимания не более одного раза.

 Предположим теперь, что $S_l$  есть стратегия $T_{k}$ для некоторого $k$ и $S_l$ требует внимания на бесконечно многих шагах $s>s_0$. В силу выбора $s_0$, стратегия $S_l$ не может быть объявлена пассивной и на всех этих шагах выполняется соотношение $\dag$. Тогда последовательность параметров $a_0,a_1,a_2,\dots$ является бесконечной, функция $\varphi_e$ является всюду определённой, и, следовательно, вычислимая функция $\varphi_e(a_i)$ переменной $i$ сводит универсальный позитивный предпорядок $U$ к предпорядку $R$, что невозможно.
 \end{proof}

\begin{lemma}
Все требования $P_{i,j}$, $WP_{e}$, $T_{k}$ удовлетворены.
\end{lemma}
\begin{proof}
Пусть $S_l$  есть любая из стратегий $P_{i,j}$, $WP_{e}$, $T_{k}$ и пусть $s_0$ -- наименьший шаг, после которого ни одна из стратегий $S_0,S_1,\dots,S_l$ не требует внимания. Существование такого шага следует из Леммы \ref{lem:1}. Покажем, что стратегия $S_l$ будет удовлетворена на или после шага $s_0$. Рассмотрим три возможных случая.

Случай 1. $S_l$ есть стратегия $P_{i,j}$ для некоторых $i,j$, причем $W_i$ пересекает бесконечно много классов эквивалентности $\mathrm{supp}(P)$, а число $j$ произвольное. Ввиду выбора $s_0$ множество $\bigcup_{l'<l}\mathrm{res}_{l'}$ конечно. Следовательно, существует бесконечно много чисел $m\in W_i$, отличных от компонентов всех пар этого множества. Пусть $s_1+1>s_0$ некоторый шаг, для которого одно из таких достаточно больших чисел $m$ содержится в $W_i^{s_1}$, и $S^{s_1+1}$ есть стратегия $P_{i,j}$. Тогда $W_{i}^{s_1}\cap[j]_{\mathrm{supp}(P^{s})}\neq\emptyset$, иначе на шаге $s_1+1$ стратегия $S_l$ потребует внимания, что противоречит выбору шага $s_0$.

Случай 2. $S_l$  есть стратегия $WP_{e}$ для некоторого $e$, причём функция $\varphi_e$ является всюду определённой. Пусть на шаге $s_2+1>s_0$ параметр $x_e$ и значение $\varphi_e(x_e)$ определены, и $S^{s_2+1}$ есть стратегия $WP_{e}$. Тогда $(y,\varphi_e(y))\in \mathrm{supp}(P^{s_2})$  для некоторого $y\in\mathrm{dom}(\varphi_e^{s_2})$, иначе на шаге $s_2+1$ стратегия $S_l$ потребует внимания, что противоречит выбору шага $s_0$.

Случай 3. $S_l$  есть стратегия $T_{k}$ для некоторого $k$, причём функция $\varphi_k$ является всюду определённой. Поскольку стратегия $T_{k}$ не требует внимания после шага $s_0$, список её параметров стабилизируется на некотором конечном множестве $a_0,a_1,\dots,a_r$, стабилизируется множество запретов $\mathrm{res}_k$, и к некоторому шагу $s_3+1>s_0$, для которого $S^{s_3+1}$ есть $T_{k}$, все значения $\varphi_k(a_0),\varphi_k(a_1),\dots,\varphi_k(a_r)$ будут определены и для всех $i,j\leq r$ выполнятся соотношения:  $$\varphi_{k}(a_i)R\varphi_{k}(a_j)\iff \varphi_{k}(a_i)R^{s_3}\varphi_{k}(a_j), \quad iUj\iff iU^{s_3}j.$$
Следовательно, на шаге $s_3+1$ нарушено соотношение $\dag$. В силу выбора $s_0$, ни одна из пар $(a_i,a_j), i,j\leq r,$ не может быть перечислена в $P$ стратегиями большего приоритета и тем более не может быть перечислена в $P$ стратегиями меньшего приоритета, чем $S_l$. Отсюда вытекает, что $a_iP^{s_3}a_j\iff a_iPa_j$ для всех $i,j\leq r$. Следовательно, сводимость $P\leq_c R$ посредством вычислимой функции $\varphi_k$ нарушается хотя бы на одной паре чисел $(a_i,a_j)\in\mathrm{res}_k$.

Таким образом, в каждом из рассмотренных выше трёх случаев конструкция обеспечивает выполнение соответствующего требования.
\end{proof}

Теорема доказана.

\end{proof}

\begin{corollary}
Для любого не универсального позитивного предпорядка $R$ найдется бесконечно много попарно не сравнимых слабо предполных минимальных позитивных предпорядков, каждый из которых не сводится к $R$.
\end{corollary}

\begin{proof}
По Теореме \ref{theo: min wp} для предпорядка $R$ найдется слабо предполный минимальный предпорядок $P_0$, не сравнимый с $R$. Рассмотрим позитивный предпорядок $R_1=R\oplus P_0$. Тогда $\mathrm{supp}(R_1)$ не является универсальной позитивной эквивалентностью, поскольку универсальная позитивная эквивалентность не разлагается в прямую сумму несравнимых эквивалентностей, \cite{Ersh73}. Следовательно, $R_1$ не является универсальным позитивным предпорядком. Применяя Теорему \ref{theo: min wp}, получим слабо предполный минимальный предпорядок $P_1$, не сравнимый с $R_1$, а, значит, не сравнимый ни с $R$, ни с $P_0$.   Итерируя этот процесс, получим требуемую последовательность слабо предполных минимальных предпорядков.
\end{proof}

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

\bibitem{Ersh73}
Ershov Yu.L., {\it Positive equivalence}, Algebra and Logic, \textbf{10}:6, (1973), 378--394.

\bibitem{BerSor83}
Bernardi C., and Sorbi A., {\it Classifying positive equivalence relations}, Journal of Symbolic Logic, \textbf{48}:3, (1983), 529--538.

\bibitem{Lach87}
Lachlan A.H., {\it A note on positive equivalence relations}, Zeitschr. f. math. Logik und Grundlagen d. Math., \textbf{33}:1, (1987), 43--46.

\bibitem{Bad91} Badaev S.A., {\it On weakly-precomplete positive equivalences}, Siberian Mathematical Journal, \textbf{32}:2, (1991), 321--323.

\bibitem{GaoGer} Gao S., Gerdes P., {\it Computably enumerable equivalence relations}, Studia Logica, \textbf{67}:1, (2001), 27--59.
    
\bibitem{ABS17} Andrews U., Badaev S., Sorbi A., {\it A survey on universal computably enumerable equivalence relations}.
In: Day A., Fellows M., Greenberg N., Khoussainov B., Melnikov A., Rosamond F. (eds) Computability and Complexity.
Lecture Notes in Computer Science, \textbf{10010}, (2017), 418--451.

\bibitem{UriSorbi} Andrews U., Sorbi A., {\it Join and meets in the structure of ceers}, Computability, \textbf{8}:3-4, (2019), 193--241.

\bibitem{BazhKal} Bazhenov N.A., Kalmurzayev B.S., {\it On dark computably enumerable relations}, Siberian Mathematical Journal, \textbf{59}:1, (2018) , 22–30.

\bibitem{FKST16} Fokina E., Khoussainov B., Semukhin P., Turetsky D., {\it Linear orders realised by c.e. equivalence relations}, Journal of Symbolic Logic, \textbf{81}:2, (2016), 463--482.

\bibitem{BMSY17} Bazhenov N., Mustafa M., Stephan F., Yamaleev M., {\it Boolean algebras realised by c.e. equivalence relations}, Siberian Eletronic Mathematical Reports, \textbf{14}:1, (2017), 848--855.

\bibitem{MS85} Montagna F., Sorbi A., {\it Universal recursion-theoretic properties of r.e. preordered structures}, Journal of Symbolic Logic, \textbf{50}, (1985), 397--406.

    

\bibitem{Mal61} Mal'tsev A.I., {\it Constructive algebras. 1}, Uspekhi Mat. Nauk, \textbf{16}:3, (1961), 3--60.

\bibitem{BKKA} Badaev S.A., Kalmurzayev B.S., Kabylzhanova D.K., Abeshev K.Sh, \textit{Universal positive preorders}, News of the National
Academy of Sciences of the Republic of Kazakhstan – Series Physico-Mathematical, \textbf{322}:6 (2018), 49--53.

\end{thebibliography}
\end{document}
