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

%%%
\usepackage{hyperref}
%%%

\def\udcs{510.5} %Here the author places classificators of the paper according to Russian classification system
\def\mscs{03C57, 03D30} %Here the author places  classificators according to the AMS classification list.
\setcounter{page}{1}

\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}[section]

\newtheorem{observation}{Observation}


\theoremstyle{definition}
\newtheorem{problem}{Problem}

\newtheorem*{Proof}{Proof}
\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]  %Headings in Russian
     {\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 Том 20, \textnumero\,X, стр. XXX--XXX (2023) \hspace{50mm}{\rm\small УДК \udcs}}
     \newline
     	{\rm\small DOI~10.33048/semi.2023.20.xxx}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{\rm\small MSC\ \ \mscs }
  }%\vbox
}

\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof.}
\renewcommand{\figurename}{Fig.}							 

\thispagestyle{empty}

\title[A NOTE ON JOINS AND MEETS FOR POSITIVE LINEAR PREORDERS]{A NOTE ON JOINS AND MEETS FOR POSITIVE LINEAR PREORDERS}

\author{{N. Bazhenov}}%
\address{Nikolay Bazhenov % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} 4 Acad. Koptyug Avenue,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{bazhenov@math.nsc.ru}%

\author{{B. Kalmurzayev}}%
\address{Birzhan Kalmurzayev
\newline\hphantom{iii} Kazakh-British Technical University,
\newline\hphantom{iii} 59 Tole bi St.,
\newline\hphantom{iii} 050000, Almaty, Kazakhstan; and \vspace{1mm}
\newline\hphantom{iii} Al-Farabi Kazakh National University,
\newline\hphantom{iii} 71 Al Farabi Avenue,
\newline\hphantom{iii} 050040, Almaty, Kazakhstan; and \vspace{1mm}
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} 4 Acad. Koptyug Avenue,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{birzhan.kalmurzayev@gmail.com}%

\author{{M. Zubkov}}%
\address{Maxim Zubkov
\newline\hphantom{iii} Kazan (Volga Region) Federal University, 
\newline\hphantom{iii} 35 Kremlevskaya St.,
\newline\hphantom{iii} 420008, Kazan, Russia; and \vspace{1mm}
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} 4 Acad. Koptyug Avenue,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{maxim.zubkov@kpfu.ru}%




\thanks{\sc Bazhenov N., Kalmurzayev B., Zubkov M., 
A note on joins and meets for positive linear preorders}
\thanks{\copyright \ 2023 Bazhenov N., Kalmurzayev B., Zubkov M}
\thanks{\rm The work of the authors is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2022-281 with the Ministry of Science and Higher Education of the Russian Federation. N.~Bazhenov and B.~Kalmurzyev were supported by the Ministry of Education and Science of
the Republic of Kazakhstan, grant AP08856493 ``Positive graphs and computable reducibility on them as mathematical model of databases''.}
\thanks{\it Received June, 20, 2022, published \dots.}%


\semrtop \vspace{1cm}
\maketitle 

\selectlanguage{english}

{\small
\begin{quote}
\noindent{\sc Abstract. } 
A positive preorder $R$ is linear if the corresponding quotient poset is linearly ordered. Following the recent advances in the studies of positive preorders, the paper investigates the degree structure \textbf{Celps} of positive linear preorders under computable reducibility. We prove that if a positive linear preorder $L$ is non-universal and the quotient poset of $L$ is infinite, then $L$ is a part of an infinite antichain inside \textbf{Celps}. 

For a pair $L,R$ from \textbf{Celps}, we obtain sufficient conditions for when the pair has neither join, nor meet (with respect to computable reducibility). We give an example of a pair from \textbf{Celps} that has a meet. Inside the substructure $\Omega$ of \textbf{Celps} containing only computable linear orders of order-type $\omega$, we build a pair that has a join inside $\Omega$.

\medskip

\noindent{\bf Keywords:} computable reducibility, computably enumerable preorder, positive linear preorder.
\end{quote}
}


\section{Introduction}

The paper studies computable reducibility for positive (computably enumerable) preorders. Let $R$ and $S$ be binary relations on the set of natural numbers $\omega$. The relation $R$ is \emph{computably reducible} to $S$ (denoted by $R\leq_c S$) if there is a total computable function $f(x)$ such that 
\[
	\forall x \forall y [ (x \,R\, y) \, \Leftrightarrow \, (f(x) \,S\, f(y))].
\]

The systematic studies of computable reducibility for positive equivalence relations were initiated by Ershov~\cite{Ershov-71,Ershov-Book}: in particular, he constructed one of the earliest examples of a universal positive equivalence, i.e., a positive equivalence $E$ such that every positive equivalence $F$ is computably reducible to $E$ (Proposition~8 in~\cite{Ershov-71}). In 1980s, the research in this area was mainly focused on natural subclasses of universal positive equivalences~--- see, e.g., papers \cite{Ber-81,BS-83,Lach} and the recent survey~\cite{ABS-17}.

The 21st century witnessed a renewed interest in positive equivalences. One of the pioneering works in this regard is the paper~\cite{GG-01}, where the acronym \emph{ceer} (which stands for `computably enumerable equivalence relation') was introduced: nowadays, this is a standard acronym for the term `positive equivalence'. 

Andrews and Sorbi~\cite{AS-19} developed intricate methods for working with the $c$-degrees (i.e., degrees with respect to computable reducibility) for positive equivalences. One of the key technical notions in these developments is the notion of \emph{darkness}. 

\begin{definition}[Definition~3.1 of~\cite{AS-19}] \label{def:dark}
	Let $E$ be a positive equivalence on $\omega$ with infinitely many classes. The equivalence $E$ is \emph{light} if the identity relation $\mathrm{Id}$ is computably reducible to $E$. Otherwise, $E$ is called \emph{dark}.
\end{definition}

Let \textbf{Ceers} denote the poset of the $c$-degrees of positive equivalences. It is known that the interval $[\mathbf{0}_1; \mathbf{0}'_1]$ of $1$-degrees is isomorphically embeddable into the poset \textbf{Ceers} (Theorem~2.4 in~\cite{ALM-14}). This fact implies that \textbf{Ceers} is neither an upper semilattice, nor a lower semilattice. Therefore, in general, $\leq_c$-incomparable positive equivalences $E$ and $F$ do not necessarily have an infimum (meet) or a supremum (join)  w.r.t.\ computable reducibility.  

On the other hand, the notion of darkness provides a deeper insight into the structural properties of \textbf{Ceers}: for example,
\begin{itemize}
	\item[(a)] if $E$ and $F$ are incomparable dark positive equivalences, then $E$ and $F$ have neither supremum, nor infimum (Theorems~5.8 and 7.18  in~\cite{AS-19});
	
	\item[(b)] if $E$ and $F$ are incomparable light positive equivalences, then sometimes they have supremum (Corollary 6.15 in~\cite{AS-19}), and sometimes they don't (Corollary 5.6 in~\cite{AS-19}).
\end{itemize}

%\hrule

One of the recent major advancements in the studies of \textbf{Ceers} was obtained by Andrews, Schweber, and Sorbi~\cite{ASS-20}: they proved that the theory $Th(\mathbf{Ceers})$ is recursively isomorphic to the first-order arithmetic.

\medskip

In recent years, the works~\cite{AS-21,BKKA-18,BBK-20,BKMK-21,ABK-22} studied the $c$-degrees of positive preorders. Following~\cite{BBK-20}, by \textbf{Ceprs} we denote the poset of the $c$-degrees of positive preorders. The paper~\cite{BBK-20} proved that the structure \textbf{Ceers} is first-order definable inside the poset \textbf{Ceprs} (Theorem~2.1 in~\cite{BBK-20}). This fact and the result of~\cite{ASS-20} (discussed above) together imply that similarly to the case of \textbf{Ceers}, the theory $Th(\mathbf{Ceprs})$ is recursively isomorphic to the first-order arithmetic.

\smallskip

The paper~\cite{BBK-20} isolated an important substructure of \textbf{Ceprs} which is of interest on its own: this substructure \textbf{Celps} is induced by \emph{positive linear preorders}. 

Let $R$ be a preorder on $\omega$ (i.e., $R$ is a reflexive and transitive relation). By $\mathrm{supp}(R)$ we denote the following equivalence relation:
\[
	\mathrm{supp}(R) = \{ (x,y) \,\colon (x,y) \in R \text{ and } (y,x) \in R\}.
\]
The quotient relation $R/\mathrm{supp}(R)$ is defined in a natural way: its domain is equal to $\omega/\mathrm{supp}(R)$, and
\[
	([a]_{\mathrm{supp}(R)}, [b]_{\mathrm{supp}(R)}) \in R/\mathrm{supp}(R)\ \Leftrightarrow\ (a,b) \in R.
\]

\smallskip

\begin{definition}
	We say that a positive preorder $R$ is \emph{linear} if the corresponding quotient relation $R/\mathrm{supp}(R)$ is a linear order. Following~\cite{BBK-20}, by \textnormal{\textbf{Celps}} we denote the poset of the $c$-degrees of positive linear preorders.
\end{definition}

Note that we treat \emph{computable linear orders} via the standard approach of computable structure theory (see, e.g., \cite{AK00}):
a computable linear order $L$ is given by a computable binary relation which is reflexive, transitive, linear, and \emph{antisymmetric}.  Notice that every computable linear order $L$ (with domain $\omega$) is a positive linear preorder. We emphasize that in this case, $\mathrm{supp}(L)$ is equal to the identity relation $\mathrm{Id}$. 

\medskip

In this paper, we investigate the structural properties of the poset \textbf{Celps}. The paper is arranged as follows. Section~\ref{sect:prelim} gives the necessary preliminaries. In addition, Section~\ref{sect:prelim} also provides a brief survey of the known results on the structure \textbf{Celps}. In Section~\ref{sect:antichains}, we prove that the $c$-degree of a non-universal positive linear preorder $L$ (s.t.\ $L$ has infinitely many $\mathrm{supp}(L)$-classes) is a part of an infinite antichain inside \textbf{Celps} (Theorem~\ref{theo:antichains}).

The rest of the paper is focused on joins (suprema) and meets (infima) in the structure \textbf{Celps}. In Section~\ref{sect:no-joins-no-meets}, we obtain examples of positive linear preorders $L$ and $R$ such that $L,R$ have neither join, nor meet (Proposition~\ref{prop:example-sup-01} and Theorem~\ref{theo:omega-standard}). In Section~\ref{sect:pair-meet}, we give a simple example of incomparable $L,R$ such that they have an infimum (Proposition~\ref{prop:pair-meet}).

Our paper leaves the following question open:
\begin{problem}\label{problem:main}
	Do there exist incomparable positive linear preorders $L$ and $R$ such that they have a supremum w.r.t.\ computable reducibility?
\end{problem}

It seems that in order to answer this question, one needs to isolate further combinatorial properties (similar to the notion of darkness for equivalence relations) which could shed more light on the structural features of the poset \textbf{Celps}.

In Section~\ref{sect:omega-types}, we prove a partial result related to Problem~\ref{problem:main}. If we restrict our attention \emph{only to} computable linear orders of order-type $\omega$, then inside \emph{this} substructure of \textbf{Celps}, one can find incomparable pairs which have a supremum (Theorem~\ref{theo:omega-types}).



%%%%%%%%%%%%%%%%%
\section{Preliminaries and known results}\label{sect:prelim}

If not specified otherwise, we assume that every considered binary relation has domain $\omega$. For an element $a\in\omega$ and an equivalence relation $E$, by $[a]_E$ we denote the $E$-equivalence class of $a$. By $\leq_{\mathbb{N}}$ we denote the standard ordering of natural numbers. For the background on countable linear orders, we refer to the monograph~\cite{Ros-82}.

Let $R$ be a preorder on $\omega$. As usual, by $R^{\ast}$ we denote the following preorder:
\[
	(x,y) \in R^{\ast}\ \Leftrightarrow\ (y,x) \in R.
\]

\begin{observation}\label{observ:automorphism}
	The map $\Psi \colon R\mapsto R^{\ast}$ induces an automorphism of the poset \textnormal{\textbf{Celps}}.
\end{observation}

We often use the following notations: for elements $x,y\in\omega$,
\begin{itemize}
	\item $x \leq_R y$ means that $(x,y)\in R$;
	
	\item $x \sim_R y$ means that $(x,y) \in \mathrm{supp}(R)$, i.e., $(x,y) \in R$ and $(y,x)\in R$;
	
	\item $x <_R y$ means that $(x,y) \in R$ and $(y,x)\not\in R$.
\end{itemize}

Sometimes we abuse notations and identify a preorder $R$ with $\deg_c(R)$, i.e., the degree of $R$ w.r.t.\ computable reducibility.
As usual, we write $R\equiv_c S$ if $R\leq_c S$ and $S\leq_c R$. For convenience, sometimes we use $\omega_{st}$ to denote the ordering $\leq_{\mathbb{N}}$.


%%%
\begin{definition}\label{def:restriction}
	Let $R$ be a positive preorder, and let $W$ be a c.e.\ set such that $W$ intersects with infinitely many $\mathrm{supp}(R)$-classes. Then we define a new positive preorder $R\upharpoonright W$ as follows. We choose a computable bijection $g$ acting from $\omega$ onto $W$, and we set:
	\[
		(x,y) \in R\upharpoonright W\ \Leftrightarrow\ g(x) \leq_R g(y).
	\]
	Notice that the function $g$ provides a computable reduction $(R\upharpoonright W) \leq_c R$.
\end{definition}

\smallskip

%%%%%%%%%
\subsection{Universal and minimal positive linear preorders}

We say that a positive linear preorder $L$ is \emph{universal} if every positive linear preorder $R$ is computably reducible to $L$.

\begin{theorem}[Theorem~3.1 of~\cite{BK-18}]
	There exists a universal positive linear preorder. Consequently, the poset \textnormal{\textbf{Celps}} has a greatest degree.
\end{theorem}

For a natural number $n\geq 1$, by $\mathrm{Lin}_n$ we denote the following positive linear preorder:
\[
	(x,y) \in \mathrm{Lin}_n \ \Leftrightarrow\ \mathrm{rest}(x,n) \leq_{\mathbb{N}} \mathrm{rest}(y,n),
\]
where $\mathrm{rest}(x,n)$ is the remainder of $x$ divided by $n$. By $\mathbf{li}_n$ we denote the $c$-degree $\deg_c(\mathrm{Lin}_n)$.

Notice the following: if $R$ is a positive linear preorder and $\mathrm{supp}(R)$ has precisely $n$ classes, then $R\equiv_c \mathrm{Lin}_n$.

\begin{observation}\label{observation-01}
	If $L$ is a positive linear preorder such that $\mathrm{supp}(L)$ has infinitely many classes, then $\mathrm{Lin}_n \leq_c L$ for all $n\geq 1$. Consequently, the poset \textnormal{\textbf{Celps}} has an initial segment of order type $\omega$:
	\[
		\mathbf{li}_1 <_c \mathbf{li}_2 <_c \mathbf{li}_3 <_c \dots.
	\]
\end{observation}

Observation~\ref{observation-01} gives rise to the following natural notion (which is similar to the notion of a minimal ceer, see~\cite{AS-19}):

\begin{definition}
	We say that a positive linear preorder $L$ is \emph{minimal} if it satisfies the following:
	\begin{itemize}
		\item $\mathrm{supp}(L)$ has infinitely many classes, and
		
		\item if $R\leq_c L$, then either $R\equiv_c L$, or $R\equiv_c \mathrm{Lin}_n$ for some $n\geq 1$.
	\end{itemize}
	If $L$ is minimal, then we also say that its degree $\deg_c(L)$ is \emph{minimal} inside \textnormal{\textbf{Celps}}.
\end{definition}

The paper~\cite{BBK-20} obtained a complete characterization of minimal degrees in \textbf{Celps}:

\begin{theorem}[Theorem~5.1 of~\cite{BBK-20}]\label{theo:min-degrees}
	The poset \textnormal{\textbf{Celps}} has precisely two minimal degrees: $\deg_c(\omega_{st})$ and $\deg_c(\omega_{st}^{\ast})$.
\end{theorem}

%%%%%%%%%%%%%%%%%
\subsection{Known results about antichains} 

The following results can be found in the literature:

\begin{proposition}[Lemma~2.1 of~\cite{BBK-20}]\label{prop:antichain-01}
	Let $R$ be a positive linear preorder such that $\mathrm{supp}(R)$ has infinitely many classes. If $R$ is not universal, then there exists a positive linear preorder $S$ such that $R$ and $S$ are incomparable w.r.t.\ computable reducibility. 
\end{proposition}

\begin{proposition}[Proposition~3.2 of~\cite{BK-18}, essentially follows from~\cite{Har-98}]\label{prop:antichain-02}
	There exists an infinite antichain of degrees inside \textnormal{\textbf{Celps}}.
\end{proposition}

%%%%%%%%%%%%%%%%%%
\subsection{Connections to computable linear orders}

In this subsection, we assume that all considered computable linear orders have domain $\omega$. Recall that in this paper, computable linear orders are always assumed to be \emph{antisymmetric}.

For every computable linear order $L$, its degree $\deg_c(L)$ belongs to \textbf{Celps}. In addition, one can prove the following:

\begin{lemma}\label{lem:comp-lo}
	Let $L$ be a computable linear order. If $R\leq_c L$ and $\mathrm{supp}(R)$ has infinitely many classes, then there is a computable linear order $Q$ such that $Q\equiv_c R$. 
\end{lemma}
\begin{proof}[Proof Sketch]
	Suppose that $R\leq_c L$ via a computable function $f(x)$. Since $\mathrm{supp}(R)$ has infinitely many classes, the set
	\[
		X = \{ i\,\colon (\forall j < i) (f(j) \neq f(i))\} \subseteq \mathrm{dom}(R)
	\]
	is computable and infinite. We fix a computable bijection $g$ acting from $\omega$ onto $X$, and we define
	\[
		(x,y) \in Q\ \Leftrightarrow\ f(g(x)) \leq_L f(g(y)).
	\]
	
	Since $L$ is a computable linear order, the relation $Q$ is a positive linear preorder. In addition, the choice of the set $X$ implies that $Q$ is an antisymmetric relation. Now it is straightforward to show that $Q$ is the desired linear order that is $\equiv_c$-equ\-ivalent to~$R$.
\end{proof}

Lemma~\ref{lem:comp-lo} shows that computable linear orders (with domain $\omega$) form a down-set in the poset
$\mathbf{Celps} \setminus \{ \mathbf{li}_n\,\colon n\geq 1\}$. In addition, we have the following:

\begin{observation}\label{observ:02}
	Let $L_0$ and $L_1$ be computable linear orders. Then $L_0 \leq_c L_1$ if and only if there is a computable isomorphic embedding from $L_0$ into $L_1$.
\end{observation}


%%%%%%%%%%%%%%%%%
\section{Infinite antichains} \label{sect:antichains}

In this section, we prove the following generalization of Proposition~\ref{prop:antichain-01}.

\begin{theorem}\label{theo:antichains}
	Let $R$ be a positive linear preorder such that $\mathrm{supp}(R)$ has infinitely many classes. If $R$ is not universal, then there exists a uniform sequence of positive linear preorders $(S_i)_{i\in\omega}$ such that:
	\begin{enumerate}
		\item each $S_i$ is $\leq_c$-incomparable with $R$, and
		
		\item the preorders $S_i$, $i\in\omega$, are pairwise $\leq_c$-incomparable.
	\end{enumerate}
	In other words, $R$ is a part of an infinite antichain inside \textnormal{\textbf{Celps}}.
\end{theorem}
\begin{proof}
	The proof is split into two parts. First, we give a detailed proof for the case when the quotient linear order $R/\mathrm{supp}(R)$ is \emph{not} isomorphically embeddable into the ordinal $\omega\cdot 2$. After that, we briefly explain the proof for the remaining case.
	
	\medskip
	
	\textbf{Case I.} Here we assume that the quotient order $R/\mathrm{supp}(R)$ is not embeddable into the well-order $\omega\cdot 2$.

	We will show only how to build \emph{two} positive linear preorders $S_0$ and $S_1$. The described construction can be straightforwardly extended to building an infinite uniform sequence $(S_i)_{i\in\omega}$.
	
	\smallskip
	
	We satisfy the following requirements:
	\begin{itemize}
		\item[$\mathcal{S}_i$:] The quotient order $S_i/\mathrm{supp}(S_i)$ is isomorphic to $\omega\cdot 2$.
		
		\item[$\mathcal{R}^i_e$:] The function $\varphi_e$ does not provide a computable reduction $S_i\leq_c R$.
		
		\item[$\mathcal{P}_j^{i,1-i}$]: The function $\varphi_j$ does not provide a computable reduction $S_i \leq_c S_{1-i}$.
	\end{itemize}
	Since $R/\mathrm{supp}(R)$ is not isomorphically embeddable into $\omega\cdot 2$, it is clear that the $\mathcal{S}_i$-re\-qui\-rement guarantees that $R\nleq_c S_i$. Hence, if all the requirements are satisfied, then the preorders $R$, $S_0$, and $S_1$ will be pairwise $\leq_c$-incomparable.
	
	\smallskip
	
	We fix a universal positive linear preorder $U$, and we fix its approximation $(U[s])_{s\in\omega}$. We also choose an approximation $(R[s])_{s\in\omega}$ of our positive linear preorder $R$.
	
	As usual, we say that at a stage $t+1$, we \emph{$S_i$-collapse} two numbers $a$ and $b$ if we declare that 
	\[
		c\sim_{S_{i,t+1}} d
	\]
	for all $c$ and $d$ such that
	\[
		[(a\leq_{S_{i,t}} c \leq_{S_{i,t}} b) \,\&\, (a\leq_{S_{i,t}} d \leq_{S_{i,t}} b)] \text{ or } [(b\leq_{S_{i,t}} c \leq_{S_{i,t}} a) \,\&\, (b\leq_{S_{i,t}} d \leq_{S_{i,t}} a)].
	\]
	
	\medskip
	
	\emph{The $\mathcal{S}_i$-strategy} is a global one. We describe its arrangements for $i = 0$. Beforehand, we set:
	\begin{gather*}
		2 <_{S_0} 6 <_{S_0} 10 <_{S_0} \dots  <_{S_0} 4k+2 <_{S_0}  4k+6 <_{S_0} \dots,\\
		3 <_{S_0} 7 <_{S_0} 11 <_{S_0} \dots  <_{S_0} 4k+3 <_{S_0}  4k+7 <_{S_0} \dots.
	\end{gather*}
	We also assume that $2k <_{S_0} 2l+1$ for all $k,l\in\omega$. We will never $S_0$-collapse pairs of the form $(4k+2,4k+6)$. In addition, for each $l\in\omega$, the class $[2l+1]_{\mathrm{supp}(S_0)}$ will contain only one element.
	
	At each stage $s$, our construction will take one of the following actions:
	\begin{itemize}
		\item either add finitely many numbers of the form $4m$ inside one of the intervals $(4k+2;4k+6)_{S_0}$ (if it is required by some other strategy, some of these new numbers could be $S_0$-collapsed); 
		
		\item or add finitely many numbers of the form $4m+1$ inside one of the intervals $(4k+3;4k+7)_{S_0}$.
	\end{itemize}
	If each of these intervals gets only finitely many numbers during the construction, then it is clear that the resulting quotient order $S_0/\mathrm{supp}(S_0)$ will be isomorphic to $\omega\cdot 2$.
	
	\smallskip
	
	We say that the interval $(4k+2;4k+6)_{S_0}$ is the \emph{$k$-th $(S_0,R)$-box}: these intervals will be used for satisfying $\mathcal{R}^0_e$-requirements.
	
	We also say that the interval $(4k+3;4k+7)_{S_0}$ is the \emph{$k$-th $(S_0,S_1)$-box}: these intervals will be used for satisfying $\mathcal{P}_j^{0,1}$-requirements.
	
	\medskip
	
	\textbf{Strategy for $\mathcal{R}^0_e$.} The strategy builds its own partial computable function $\psi(n):=x_n$.
	\begin{enumerate}
		\item Choose a fresh $k$-th $(S_0,R)$-box. Let $u := 4k+2$ and $v:=4k+6$. 
		
		\item We set $n :=0$.
		
		\item Choose the least unused (in the construction) number $x_n$ of the form $4m$. We put $u <_{S_0} x_n <_{S_0} v$.
		\begin{itemize}
			\item At each further stage $s$ of the construction, we proceed with the following \emph{background action}: for all $i,j\leq n$ we set
			\begin{equation}\label{equ:Universal-01}
				(x_i,x_j) \in S_{0,s}\ \Leftrightarrow\ (i,j) \in U[s].
			\end{equation}
			This can be achieved by $S_0$-collapsing appropriate elements $x_i$.
		\end{itemize}
		
		\item Wait until the value $\varphi_e(x_n)$ is defined. After $\varphi_e(x_n)$ is computed, wait for a stage $s$ such that for all $i,j\leq n$, we have
		\begin{equation}\label{equ:Universal-02}
			(x_i, x_j) \in S_{0,s}\ \Leftrightarrow\ (\varphi_e(x_i), \varphi_e(x_j)) \in R[s].
		\end{equation}
		
		\item When such a stage $s$ is reached, go to Step~(3) with the parameter $n+1$ (in place of $n$).
	\end{enumerate}
	
	\smallskip
	
	\emph{Possible outcomes.} 
	
	$\texttt{w}_n$: Forever waiting at Step~(4) for the number $n$. Then either $\varphi_e$ is not total, or we never see Eq.~(\ref{equ:Universal-02}) satisfied. In the second case, even if $\varphi_e$ is total, it does not provide a reduction $S_0 \leq_c R$.
	
	$\infty$: For each $n\in\omega$, the strategy eventually chooses the corresponding number $x_n$. But then Eq.~(\ref{equ:Universal-01}) guarantees that the total function $\psi\colon n\mapsto x_n$ provides a computable reduction $U\leq_c S_0$. In addition, since we infinitely often see Eq.~(\ref{equ:Universal-02}) satisfied, we deduce that the function $\varphi_e\circ \psi$ gives computable reduction $U\leq_c R$. 
	
	On the other hand, recall that $U$ is a universal positive linear preorder, and $R$ is not universal. Therefore, we obtain a contradiction, and the $\infty$-outcome cannot be realized.
	
	\smallskip
	
	\emph{The current outcome} of our strategy is equal to $\texttt{w}_n$, where $n$ is the largest number such that $x_n$ is already defined.
	
	\medskip
	
	\textbf{Strategy for $\mathcal{P}^{0,1}_j$.} 
	\begin{enumerate}
		\item Choose a fresh $k$-th $(S_0,S_1)$-box. Let $u := 4k+3$ and $v:=4k+7$. 
		
		\item Wait until the values $\varphi_j(u)$ and $\varphi_j(v)$ are both defined. 
		
		\item Suppose that we have computed $\varphi_j(u)$ and $\varphi_j(v)$ by the stage $s$. If one of the following holds:
		\begin{itemize} 
			\item one of the values $\varphi_j(u)$ or $\varphi_j(v)$ is even (informally speaking, this means that $\varphi_j$ ``wants'' to embed an ordinal $\alpha>\omega$ into the well-order~$\omega$);
			
			\item right now, we have $\varphi_j(u) >_{S_{1,s}} \varphi_j(v)$;
		\end{itemize}
		then proceed to Step~(4).
		
		Otherwise, we have $\varphi_j(u) \leq_{S_{1,s}} \varphi_j(v)$, and the value
			\[
				N = \mathrm{card}([\varphi_j(u); \varphi_j(v)]_{S_{1,s}})
		\] 
		is finite. Add $N+1$ (least unused) numbers of the form $4l+1$ inside the interval $[u;v]_{S_0}$. These newly added numbers will never be $S_0$-collapsed. Proceed to Step~(4).
		
		\item Forbid the lower priority strategies to add fresh numbers inside the set $[\varphi_j(u); \varphi_j(v)]_{S_{1}} \cap \{2k+1\,\colon k\in\omega\}$.
	\end{enumerate}
	
	\smallskip
	
	The strategy has two outcomes:
	\begin{itemize}
		\item[\texttt{w}:] Waiting forever at Step~(2). Then the function $\varphi_j$ is not total.
		
		\item[\texttt{s}:] Eventually stopping at Step~(4). Then it is clear that $\mathcal{P}^{0,1}_j$ is satisfied: the interval $[u;v]_{S_0}$ has more elements (or more formally, one-element classes of the form $[2l+1]_{\mathrm{supp}(S_0)}$) than the corresponding interval $[\varphi_j(u); \varphi_j(v)]_{S_{1}}$.
	\end{itemize}
	
	\medskip
	
	\textbf{Construction.} As usual, we fix some effective $\omega$-ordering of our requirements:
	\[
		R_0 < R_1 < R_2 < \dots.
	\]
	For $m\in\omega$, the $m$-th level of the \emph{tree of strategies} $T$ is devoted to the requirement~$R_m$. If $\alpha$ is a strategy at the $m$-th level, then its children are nodes of the form $\alpha\widehat{\ }o$, where $o$ is one of the possible outcomes of $\alpha$ (i.e., $\texttt{w}_n$, $n\in\omega$, for an $\mathcal{R}^i_e$-strategy, and \texttt{w} or \texttt{s} for a $\mathcal{P}^{i,1-i}_j$-strategy).
	
	The outcomes are ordered as follows: $\texttt{s} < \texttt{w}$, and $\dots < \texttt{w}_2 < \texttt{w}_1 < \texttt{w}_0$.
	
	At a stage $s$ of the construction, one visits strategies $\alpha_0,\alpha_1,\dots,\alpha_s$. Here $\alpha_0 = \emptyset$, and $\alpha_{i+1} = \alpha_i\widehat{\ }o$, where $o$ is the current outcome of $\alpha_i$.
	
	\medskip
	
	\textbf{Verification.} Let $P$ be the true path through the tree of strategies $T$: a strategy $\alpha$ belongs to $P$ iff $\alpha$ is visited infinitely often along the construction.
	
	\begin{lemma}
		Every requirement (among $\mathcal{R}^i_e$ and $\mathcal{P}^{i,1-i}_j$) is eventually satisfied, and the true path $P$ is infinite. 
	\end{lemma}
	\begin{proof}
		Let $\alpha$ be a strategy along the true path. If $\alpha$ is a $\mathcal{P}^{i,1-i}_j$-strategy, then the standard argument for finite injury constructions shows that $\mathcal{P}^{i,1-i}_j$ is eventually satisfied. In addition, it is clear that either $\alpha\widehat{\ }\texttt{w}$ or $\alpha\widehat{\ }\texttt{s}$ lies on the true path.
		
		Suppose that $\alpha$ is an $\mathcal{R}^i_e$-strategy. Then the argument in the strategy description shows that our construction will be eventually stuck at some outcome $\texttt{w}_n$. Hence, $\mathcal{R}^i_e$ is satisfied, and $\alpha\widehat{\ }\texttt{w}_n$ belongs to the true path.
	\end{proof}
	
	\medskip
	
	In order to finish the proof, it is sufficient to show that the quotient order $S_i/\mathrm{supp}(S_i)$ is isomorphic to the ordinal $\omega\cdot 2$. This is a consequence of the following observation: each strategy $\alpha$ chooses its own box $B$, and $\alpha$ could add only finitely many elements into this box. Since a strategy $\beta\neq \alpha$ cannot add numbers to the box $B$, we deduce that each box contains only finitely many numbers. Therefore, it is not hard to deduce that $S_i/\mathrm{supp}(S_i)$ is an isomorphic copy of $\omega\cdot 2$. This concludes the proof of the first case of our theorem.
	
	\medskip
	
	\textbf{Case~II.} Now assume that the quotient order $R/\mathrm{supp}(R)$ is isomorphically embeddable into the ordinal $\omega\cdot 2$. Then the reverse order $R^{\ast}/\mathrm{supp}(R^{\ast})$ is embeddable into $\omega^{\ast} \cdot 2$, and hence, $R^{\ast}/\mathrm{supp}(R^{\ast})$ is not embeddable into $\omega \cdot 2$. 
	
	By applying Case~I of the theorem, we build an antichain $(L_i)_{i\in\omega}$ such that $R^{\ast}$ is incomparable with each $L_i$. By Observation~\ref{observ:automorphism}, we deduce that $R = (R^{\ast})^{\ast}$ is incomparable with each of the members of the antichain $(L^{\ast}_i)_{i\in\omega}$.	
	Theorem~\ref{theo:antichains} is proved.
\end{proof}



%%%%%%%%%%%%%%%%%

\section{Pairs with no joins and no meets} \label{sect:no-joins-no-meets}

Here we give examples of $\leq_c$-incomparable positive linear preorders $L$ and $R$ such that they have neither join, nor meet.

Before introducing these examples, we define the following notion:

\begin{definition}[\cite{BBK-20}]
	Let $L$ and $R$ be positive linear preorders. Then the positive linear preorder $L\veebar R$ is defined as follows: $(x,y)\in (L\veebar R)$ if and only if for some $k,l\in\omega$, one of the following holds:
	\begin{itemize}
		\item $x = 2k$, $y=2l$, and $k \leq_L l$;
		
		\item $x = 2k+1$, $y = 2l+1$, and $k \leq_R l$; or
		
		\item $x = 2k$ and $y = 2l+1$.
	\end{itemize}
\end{definition}

\begin{observation}
	Both linear preorders $L\veebar R$ and $R\veebar L$ are upper bounds (w.r.t.\ computable reducibility) for $L$ and $R$.
\end{observation}

\medskip

Our first example uses simple algebraic properties of linear orderings:

\begin{proposition}\label{prop:example-sup-01}
	Let $L$ and $R$ be positive linear preorders such that:
	\begin{itemize}
		\item both $\mathrm{supp}(L)$ and $\mathrm{supp}(R)$ have infinitely many equivalence classes;
		
		\item the quotient order $L/\mathrm{supp}(L)$ is isomorphic to an ordinal $\alpha$, and
		
		\item the quotient order $R/\mathrm{supp}(R)$ is isomorphic to $\beta^{\ast}$, where $\beta$ is an ordinal.
	\end{itemize}
	Then $\deg_c(L)$ and $\deg_c(R)$ have neither infimum, nor supremum.
\end{proposition}
\begin{proof}
	First, we prove that $L$ and $R$ have no infimum. Recall (see Observation~\ref{observation-01}) that for every $n\geq 1$, the order $\mathrm{Lin}_n$ is a lower bound for both $L$ and $R$. Therefore, if some $Q$ is a meet for $L$ and $R$, then $\mathrm{supp}(Q)$ has infinitely many classes. But then the quotient order $Q/\mathrm{supp}(Q)$ has either an infinite ascending chain, or an infinite descending chain. If there is an infinite descending chain, then this contradicts the fact that $Q/\mathrm{supp}(Q)$ is isomorphically embeddable into $L/\mathrm{supp}(L) \cong \alpha$. If there is an infinite ascending chain, than this contradicts that $Q/\mathrm{supp}(Q)$ is embeddable into $R/\mathrm{supp}(R) \cong \beta^{\ast}$. We conclude that no preorder $Q$ can be an infimum for $L$ and $R$.
	
	Now, towards a contradiction, assume that $Q$ is a join for $L$ and $R$. Since $L\veebar R$ is an upper bound for $\{L,R\}$, there is an isomorphic embedding from $Q/\mathrm{supp}(Q)$ into $(L\veebar R)/\mathrm{supp}(L\veebar R) \cong \alpha + \beta^{\ast}$. Therefore, 
	\[
		Q/\mathrm{supp}(Q) \cong \gamma + \delta^{\ast} \text{ for some ordinals } \gamma\leq \alpha \text{ and } \delta \leq \beta.
	\]
	On the other hand, $Q/\mathrm{supp}(Q)$ is also embeddable into $(R\veebar L)/\mathrm{supp}(R\veebar L) \cong \beta^{\ast} + \alpha$. Hence,
	\[
		Q/\mathrm{supp}(Q) \cong \rho^{\ast} + \xi \text{ for some ordinals } \xi\leq \alpha \text{ and } \rho \leq \beta.
	\]
	We deduce that 
	\begin{equation} \label{equ:sum-00}
		\gamma + \delta^{\ast} \cong \rho^{\ast} + \xi. 
	\end{equation}	
	
	A straightforward analysis of Eq.~(\ref{equ:sum-00}) shows the following:
	\begin{itemize}
		\item either $\gamma$ and $\xi$ are both finite,

		\item or $\delta$ and $\rho$ are both finite.
	\end{itemize}
	On the other hand, since $L\leq_c Q$ and $R\leq_c Q$, we deduce that all four ordinals $\gamma,\delta,\xi,\rho$ should be infinite. We obtained a contradiction, hence, $L$	and $R$ do not have a supremum. Proposition~\ref{prop:example-sup-01} is proved.
\end{proof}

\medskip

Our second example shows the following: if $R$ is incomparable with a minimal linear preorder $L$, then $R$ and $L$ have neither join, nor meet (recall Theorem~\ref{theo:min-degrees} and Observation~\ref{observ:automorphism}).

\begin{theorem}\label{theo:omega-standard}
	Let $R$ be a positive linear preorder such that $R$ is $\leq_c$-incompar\-a\-ble with $\omega_{st}$. Then $R$ and $\omega_{st}$ have neither infimum, nor supremum.
\end{theorem}
\begin{proof}
	It is easy to see that $R$ and $\omega_{st}$ do not have an infimum. Indeed, for any positive linear preorder $S$, we have the following: $S$ is a lower bound for $\{R, \omega_{st}\}$ if and only if $S\equiv_c \mathrm{Lin}_n$ for some $n\geq 1$.
	
	Towards a contradiction, assume that $Q$ is a supremum for $R$ and $\omega_{st}$. Fix a computable reduction $f\colon Q \leq_c (\omega_{st} \veebar R)$. Then one of the following two cases holds.
	
	\smallskip
	
	\textsc{Case~I.} Suppose that there are only finitely many even numbers belonging to $\mathrm{range}(f)$. 
	
	Fix a computable reduction $g\colon \omega_{st} \leq_c Q$. We can choose a natural number $N$ such that
	\[
		(\forall x \geq N) ( f(g(x)) \text{ is odd}).
	\]
	But then a computable function
	\[
		h(y) = \left\lfloor \frac{f(g(y+N))}{2} \right\rfloor
	\]
	provides a reduction $\omega_{st} \leq_c R$, which gives a contradiction.
	
	\smallskip
	
	\textsc{Case~II.} Otherwise, there are infinitely many even numbers belonging to the set $\mathrm{range}(f)$. Consider an infinite c.e.\ set $W = \{ 2k\,\colon 2k\in\mathrm{range}(f)\}$. Without loss of generality, one may assume that $W\neq \mathrm{range}(f)$.
	Then one can show the following: 
	\begin{itemize}
		\item the preorder $(\omega_{st} \veebar R)\upharpoonright W$ (recall Definition~\ref{def:restriction}) is equivalent to $\omega_{st}$, and
	
		\item $Q\equiv_c \omega_{st} \veebar R_1$, where $R_1\leq_c R$.
	\end{itemize}	
	Consider a reduction $g\colon (\omega_{st} \veebar R_1) \leq_c (R\veebar \omega_{st})$.
	
	\smallskip
	
	\textsc{Subcase~II.(a).} Suppose that there is an odd number $y$ such that $g(y)$ is even. This implies that for every even number $z$, the value $g(z)$ is also even. Hence, the function
	\[
		g_1(x) = \left\lfloor \frac{g(2x)}{2} \right\rfloor
	\]
	gives a reduction $\omega_{st} \leq_c R$~--- contradiction.
	
	
	\textsc{Subcase~II.(b).} For every odd $y$, the value $g(y)$ is odd. This implies that $R_1\leq_c \omega_{st}$, and $R_1$ is a lower bound for $\{R, \omega_{st}\}$. Therefore, $R_1\equiv_{c} \mathrm{Lin}_n$ for some $n\geq 1$.
	
	Now we have $Q\equiv_c \omega_{st} \veebar \mathrm{Lin}_n$. Consider a reduction $h\colon R\leq_c (\omega_{st} \veebar \mathrm{Lin}_n)$. The set $V = \{ 2k\,\colon 2k\in\mathrm{range}(h)\}$ is infinite, and one can prove the following:
	\begin{itemize}
		\item the preorder $(\omega_{st} \veebar \mathrm{Lin}_n) \upharpoonright V$ is computably reducible to $R$, and
		
		\item $(\omega_{st} \veebar \mathrm{Lin}_n) \upharpoonright V$ is equivalent to $\omega_{st}$.
	\end{itemize}
	Thus, $\omega_{st} \leq_c R$~--- contradiction.
	
	\smallskip
	
	Each of the cases above gives a contradiction, therefore, $Q$ cannot be a supremum for $R$ and $\omega_{st}$. Theorem~\ref{theo:omega-standard} is proved.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%
\section{Example of a pair with a meet} \label{sect:pair-meet}

Here we show that in general, $\leq_c$-incomparable positive linear preorders $L$ and $R$ can have an infimum.

By $\zeta_{st}$ we denote the computable linear order $\omega^{\ast}_{st} \veebar \omega_{st}$. Notice that this linear order is isomorphic to the standard ordering of integers $\zeta$.

\begin{proposition}\label{prop:pair-meet}
	 The linear preorders $\zeta_{st} \veebar \mathrm{Lin}_1$ and $\mathrm{Lin}_1 \veebar\zeta_{st}$ have infimum $\zeta_{st}$. In addition, these preorders do not have a supremum.
\end{proposition}
\begin{proof}[Proof Sketch]
	It is clear that $\zeta_{st}$ is a lower bound for $\{ \zeta_{st} \veebar \mathrm{Lin}_1, \mathrm{Lin}_1 \veebar\zeta_{st}\}$. Suppose that $R$ is an arbitrary lower bound for $\{ \zeta_{st} \veebar \mathrm{Lin}_1, \mathrm{Lin}_1 \veebar\zeta_{st}\}$. By Lemma~\ref{lem:comp-lo}, we may assume that $R$ is a computable linear order (with domain $\omega$). Fix a computable reduction $f\colon R\leq_c (\zeta_{st} \veebar \mathrm{Lin}_1)$. Then one can prove that one of the following cases holds:
	\begin{itemize}
		\item If the set $\mathrm{range}(f)$ does not contain odd numbers, then we have:
		\[
			(R\equiv_{c} \zeta_{st}) \text{ or } (R\equiv_{c} \omega_{st}) \text{ or } (R\equiv_{c} \omega^{\ast}_{st}).
		\]
		
		\item If $\mathrm{range}(f)$ contains an odd number, then since $R\leq_c (\mathrm{Lin}_1 \veebar\zeta_{st})$, a straightforward order-theoretic analysis shows that $R\equiv_{c} \omega^{\ast}_{st}$.
	\end{itemize}
	In each of the cases, we have $R\leq_c \zeta_{st}$. Hence, $\zeta_{st}$ is an infimum for $\{ \zeta_{st} \veebar \mathrm{Lin}_1, \mathrm{Lin}_1 \veebar\zeta_{st}\}$.
	
	Towards a contradiction, assume that $Q$ is a supremum for $\{ \zeta_{st} \veebar \mathrm{Lin}_1, \mathrm{Lin}_1 \veebar\zeta_{st}\}$. Since $(\zeta_{st}\veebar \mathrm{Lin}_1\veebar \zeta_{st})$ is an upper bound, we deduce that $Q$ can be treated as a computable linear order such that:
	\begin{itemize}
		\item[(a)] both order types $\zeta+1$ and $1+\zeta$ are isomorphically embeddable into $Q$, and
		
		\item[(b)] $Q$ is embeddable into $\zeta+1+\zeta$.
	\end{itemize}
	On the other hand, $(\mathrm{Lin}_1\veebar \zeta_{st} \veebar \mathrm{Lin}_1)$ is another upper bound for $\{ \zeta_{st} \veebar \mathrm{Lin}_1, \mathrm{Lin}_1 \veebar\zeta_{st}\}$. This implies that $Q$ is also isomorphically embeddable into $1+\zeta+1$. One can show that this fact together with Conditions~(a) and~(b) gives a contradiction. Therefore, $Q$ cannot be a supremum for our pair of orders.
\end{proof}


%%%%%%%%%%%%%%%%%
\section{Computable linear orders of order type $\omega$}\label{sect:omega-types}

In this section, we give a partial result on suprema. We restrict our attention to the following substructure in the poset $\mathbf{Celps}$.

\begin{definition}
	By $\mathbf{\Omega}$ we denote the following poset:
	\[
		\mathbf{\Omega} = ( \{ \deg_c(L)\,\colon L \text{ is a computable linear order isomorphic to } \omega_{st}\}; \leq_c).
	\]
\end{definition}

\begin{observation}\label{observ:Omega}
	The set $\mathbf{\Omega} \cup \{ \mathbf{li}_n\,\colon n\geq 1\}$ is a down-set in the poset $\mathbf{Celps}$.
\end{observation}

\smallskip

We prove the following theorem.

\begin{theorem}\label{theo:omega-types}
	There exist $\leq_c$-incomparable orders $L$ and $M$ in $\mathbf{\Omega}$ such that $L,M$ have a supremum $S$ inside $\mathbf{\Omega}$.
\end{theorem}
\begin{proof}
	We build computable linear orders $L$, $M$, and $S$ (all isomorphic to $\omega_{st}$), and satisfy the following requirements:
	\begin{itemize}
		\item[$\mathcal{NR}_e^{L\to M}$:]  The function $\varphi_e$ does not provide a computable reduction $L\leq_c M$.

		\item[$\mathcal{NR}_e^{M\to L}$:]  The function $\varphi_e$ does not provide a computable reduction $M\leq_c L$.

		\item[$\mathcal{SUP}$:]  $L\leq_c S$ and $M\leq_c S$.
	\end{itemize}
	In the verification, we will prove that in addition to these requirements, the constructed order $S$ will be a supremum for $L,M$.
	
	As it is custom in computable structure theory, the order $L$ is built as an increasing sequence of uniformly recursive linear orders:
	\[
		L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots; \qquad  L = \bigcup\!_{s\in\omega} \, L_s.
	\]
	The orders $M$ and $S$ are constructed in a similar way.
	
	\smallskip

	At the stage $0$, we put
	\begin{gather*}
		L_0 = M_0 = S_0 = \{ 0 < 2 < 4 < \dots < 2k < 2k+2 < \dots\}.
	\end{gather*}
	
We build each of the orders $L$ and $M$ implementing the following guidelines. The order $L$ consists of the intervals $I^L_k = [2k;2k+2]_L$, for $k\in\omega$. Whenever we want to add a fresh odd number $z$ inside an interval $I^L_k$, we proceed as follows:
	\begin{itemize}
		\item Find the element $y \in I^L_k$ such that $y <_L 2k+2$, and right now, we have
		\[
			\neg\exists x [ y <_{L_s} x <_{L_s} 2k+2].
		\]
		
		\item Add the element $z$, and declare
		\[
			y <_L z <_L 2k+2.
		\]
	\end{itemize}
	Notice that this procedure guarantees that the elements $y$ and $z$ will be \emph{forever} adjacent~--- i.e., the resulting order $L = \bigcup_{s\in\omega}L_s$ satisfies
	\[
		\neg\exists v [ y<_L v <_L z].
	\]
	
	Therefore, we may assume the following: our construction `automatically' builds a partial computable function $\psi^L_{adj}(k,m)$ satisfying the following:
	\begin{itemize}
		\item for each $k\in\omega$, the domain of $\psi^L_{adj}(k,\cdot)$ is a finite initial segment of $\omega$;
		
		\item the range of $\psi^L_{adj}$ is a subset of odd numbers;
		
		\item if the value $v_{k,0} = \psi^{L}_{adj}(k,0)$ is defined, then $v_{k,0} >_L 2k$ is the element that is $<_L$-adjacent to $2k$;
		
		\item if $v_{k,m+1} = \psi^{L}_{adj}(k,m+1)$ is defined, then $v_{k,m+1} >_L v_{k,m}$ is the element that is $<_L$-adjacent to $v_{k,m}$.
	\end{itemize}
	The construction of the order $M$ also follows similar guidelines: in particular, $M$ has its own partial function $\psi^{M}_{adj}$.
	
	\medskip
	
	\textbf{Strategy for $\mathcal{SUP}$.} This strategy is a global one. The order $S$ consists of the following intervals:
	\[
		J^{L}_k = [4k;4k+2]_{S},\ \ \ J^{M}_k = [4k+2;4k+4]_{S},\ \ k\in\omega.
	\]
	
	For each $k\in\omega$, the interval $J^{L}_k$ ``copies'' the corresponding interval $I^L_k$ from $L$, and the interval $J^{M}_k$ ``copies'' the interval $I^M_k$ from $M$. More formally, this can be arranged as follows: whenever we define a new value $\psi^L_{adj}(k,m)$, we make the following actions:
	\begin{itemize}
		\item Find the element $y \in J^{L}_k$ such that  $y <_{S} 4k+2$, and (at the current stage~$t$) we have
		\[
			\neg\exists x[ y <_{S_t} x <_{S_t} 4k+2].
		\]
		
		\item Choose a fresh odd number $w$, and declare $y <_{S} w <_S 4k+2$.
	\end{itemize}
	Then one can define:
	\begin{itemize}
		\item $h_L(\psi^L_{adj}(k,m)) := \text{this }w$;
		
		\item $h_L(2k) := 4k$.
	\end{itemize}
	Clearly, the resulting total function $h_L$ gives a computable reduction $L\leq_c S$. Similarly, one arranges a computable reduction $h_M\colon M\leq_c S$.
	
	\medskip
	
\textbf{Strategy for $\mathcal{NR}_e^{L\to M}$.}
\begin{enumerate}
	\item Choose a fresh interval $I^L_k$ inside $L$.
	
	\item Wait until the values $\varphi_e(2k)$ and $\varphi_e(2k+2)$ are defined.
	
	\item Initialize all lower priority strategies. If $\varphi_e(2k) <_M \varphi_e(2k+2)$, then proceed as follows:
	\begin{itemize}
		\item[(a)] Forbid to enumerate new elements into all intervals $I^M_l$ such that $I^M_l$ intersects with $[\varphi_e(2k); \varphi_e(2k+2)]_M$.
		
		\item[(b)] For each $r\geq k$, add into the interval $I^L_r$ precisely 
		\[
			N = \mathrm{card}([\varphi_e(2k); \varphi_e(2k+2)]_M)
		\] 
		fresh odd numbers.
	\end{itemize}
\end{enumerate}
The strategy for $\mathcal{NR}_e^{M\to L}$ is defined in a similar way.

Notice that Step~(3.b) of the strategy ensures the following property: 
\begin{equation}\label{equ:main-property}
	\text{If } \psi^L_{adj}(k,m)\!\downarrow, \text{ then } (\forall r\geq k) [\psi^L_{adj}(r,m)\!\downarrow].
\end{equation}
This property will be crucial in our verification (to be elaborated).

The strategy has two outcomes:
	\begin{itemize}
		\item[\texttt{w}:] Waiting forever at Step~(2). Then the function $\varphi_e$ is not total.
		
		\item[\texttt{s}:] Eventually stopping at Step~(3). Then it is clear that $\mathcal{NR}_e^{L\to M}$ is satisfied: indeed, the interval $I^L_k$ has more elements than the corresponding interval $[\varphi_e(2k); \varphi_e(2k+2)]_{M}$.
	\end{itemize}
	
	\medskip
	
	\textbf{Construction.} We fix some effective $\omega$-ordering of our requirements:
	\[
		R_0 < R_1 < R_2 < \dots.
	\]
	The tree of strategies $T$ is arranged similarly to the construction of Theorem~\ref{theo:antichains}. At a stage $s$ of the construction, one visits strategies $\alpha_0,\alpha_1,\dots,\alpha_s$. As usual, here $\alpha_0 = \emptyset$, and $\alpha_{i+1} = \alpha_i\widehat{\ }o$, where $o$ is the current outcome of $\alpha_i$.
	
	\medskip
	
	\textbf{Verification.} A standard argument for finite injury constructions shows that all requirements $\mathcal{NR}_e^{L\to M}$ and $\mathcal{NR}_e^{M\to L}$ are eventually satisfied. Hence, $L$ and $M$ are $\leq_c$-incomparable.
	
	It is clear that for each $k\in\omega$, only $R_e$-strategies satisfying $e\leq k$ could add new odd numbers into the intervals $I^L_k$ and $I^M_k$. Hence, since all requirements are satisfied, the intervals $I^L_k$ and $I^M_k$ are finite. This implies that the computable orders $L$, $M$, and $S$ are isomorphic to $\omega_{st}$. In addition, the actions of the global strategy ensure that $S$ is an upper bound for both $L$ and $M$.
	
	In order to finish the proof, it is sufficient to establish the following:
	
	\begin{lemma}
		If $\deg_c(T) \in\mathbf{\Omega}$ and $T$ is an upper bound for $L$ and $M$, then $S\leq_c T$.
	\end{lemma}
	\begin{proof}
		Fix two computable reductions $f\colon L\leq_c T$ and $g\colon M\leq_c T$. Also, let $h_L \colon L\leq_c S$ and $h_M\colon M\leq_c S$ be computable reductions constructed by the actions of our global $\mathcal{SUP}$-strategy.

		We build the desired computable reduction $\xi\colon S\leq_c T$. 	Roughly speaking, the basic idea behind the reduction $\xi$ is as follows. In order to reduce $S$ to $T$, we just use the given reductions $f$ and $g$. This is achievable, since $S$ was constructed as a kind of special `disjoint sum' of $L$ and $M$. The only (combinatorial) problem is the following. It could be the case that, say, for a given $k$, the images $f(I^L_k)$ and $g(I^M_k)$ intersect, and thus, in order to map the interval $[4k;4k+4]_S$ into $T$, we cannot use the numbers from $f(I^L_k) \cup g(I^M_k)$ in a naive straightforward manner. In order to avoid this problem, we employ the property given by Eq.~(\ref{equ:main-property}).
		
		
		We give a formal definition of the reduction $\xi$. First, we computably recover a sequence of even numbers $(m_i)_{i\in\omega}$ as follows:
		\begin{itemize}
			\item $m_0 := 0$.
			
			\item If $i$ is even, then find some even number $2k > m_i+2$ such that $g(2k) >_T f(m_i+2)$. This is always possible, since $T\cong\omega_{st}$ and hence, the set $\mathrm{range}(g)$ is cofinal in $T$. Put $m_{i+1} := 2k$.
			
			\item If $i$ is odd, then find an even number $2r > m_i+2$ such that $f(2r) >_T g(m_i+2)$. Set $m_{i+1}:= 2r$.
		\end{itemize}
		Notice the following: for all $i,j\in\omega$, we have
		\[
			f([m_{2i};m_{2i}+2]_L) \cap g([m_{2j+1};m_{2j+1}+2]_M) = \emptyset.
		\]				
		Now we are ready to compute the values $\xi(x)$, $x\in\omega$.
		\begin{enumerate}
			\item Put $\xi(4k) = f(m_{2k})$ and $\xi(4k+2) = g(m_{2k+1})$.
			
			\item If $v$ is an odd number, then one of the following two cases holds:
			\begin{itemize}
				\item Suppose that $v = h_L(\psi^L_{adj}(k,t))$ for some $k$ and $t$. Then we put $\xi(v) := f(\psi^L_{adj}(m_{2k}/2,t))$. Note that here the value $\psi^L_{adj}(m_{2k}/2,t)$ is defined: indeed, we have 
				\[
					\frac{m_{2k}}{2} \geq \frac{4\cdot 2k}{2} = 4k \geq k,
				\]
				and hence, we can apply Eq.~(\ref{equ:main-property}).
				
				\item Otherwise, $v = h_M(\psi^M_{adj}(r,t))$ for some $r$ and $t$. Then set $\xi(v) := g(\psi^M_{adj} (m_{2r+1}/2, t))$. A similar argument shows that here the value $\psi^M_{adj} (m_{2r+1}/2, t)$ is defined.
			\end{itemize}
		\end{enumerate}
		
		We have defined a total computable function $\xi(x)$. Using a not difficult argument, now one can show that $\xi\colon S\leq_c T$.
	\end{proof}
	
	Theorem~\ref{theo:omega-types} is proved.
\end{proof}


In conclusion of this section, we observe the following:

\begin{lemma}
	The pair $L,M$ built in Theorem~\ref{theo:omega-types} does not have a supremum inside the structure \textnormal{\textbf{Celps}}.
\end{lemma}
\begin{proof}[Proof Sketch]
	Towards a contradiction, assume that $Q$ is a supremum for $L,M$ inside \textbf{Celps}. Since the order $S$ (constructed in Theorem~\ref{theo:omega-types}) is an upper bound for $\{L,M\}$ inside \textbf{Celps}, we deduce that $Q\leq_c S$, and $\deg_c(Q)$ belongs to $\mathbf{\Omega}$ (by Observation~\ref{observ:Omega}). Since inside $\mathbf{\Omega}$, $S$ is a supremum for $\{ L,M\}$, this implies that $Q\equiv_c S$.	Therefore, there exists a computable reduction $f\colon S\leq_c (L\veebar M)$.
	
	Since both $L$ and $M$ are computable linear orders isomorphic to $\omega_{st}$, one of the following two cases holds.
	
	\emph{Case~1.} The set $\mathrm{range}(f)$ contains an odd number. Then for almost all numbers $x$ from $S$, the value $f(x)$ is odd. Using this fact (and the properties of the construction from Theorem~\ref{theo:omega-types}), one can built a reduction $g\colon S\leq_c M$. Since $L\leq_c S$, we obtain that $L\leq_c M$, which contradicts the fact that $L$ and $M$ are $\leq_c$-incomparable.
	
	\emph{Case~2.} The set $\mathrm{range}(f)$ contains only even numbers. Then one can build a reduction $h\colon S\leq_c L$. Therefore, $M\leq_c S \leq_c L$, which provides a contradiction again.
	
	We conclude that inside \textbf{Celps}, our orders $L$ and $M$ do not have a supremum.
\end{proof}

%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%

%\bigskip

\begin{thebibliography}{1}

\bibitem{Ershov-71}
Yu.\,L. Ershov,
{\it Positive equivalences},
Algebra Logic, \textbf{10}:6 (1971), 378--394. 
MR0307896

\bibitem{Ershov-Book}
Yu.\,L. Ershov,
{\it Theory of numberings},
Nauka, Moscow, 1977. 
In Russian.
MR0506676

\bibitem{Ber-81}
C. Bernardi, 
{\it On the relation provable equivalence and on partitions in effectively inseparable sets}, 
Stud. Log., \textbf{40}:1 (1981), 29--37.
MR0619200

\bibitem{BS-83}
C. Bernardi and A. Sorbi, 
{\it Classifying positive equivalence relations}, 
J. Symb. Log., \textbf{48}:3 (1983), 529--538.
MR0716612

\bibitem{Lach}
A.\,H. Lachlan, 
{\it A note on positive equivalence relations}, 
Z. Math. Logik Grundlagen Math.,
\textbf{33}:1 (1987), 43--46.
MR0885481

\bibitem{ABS-17}
U. Andrews, S. Badaev, and A. Sorbi, 
{\it A survey on universal computably enumerable equivalence relations}, 
In: A. Day, M. Fellows, N. Greenberg, B. Khoussainov, A. Melnikov, and F.~Rosamond, editors, 
{\it Computability and Complexity. Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday}, 
Lect. Notes Comput. Sci., \textbf{10010}, pp.~418--451.
Cham, Springer, 2017.
MR3629733

\bibitem{GG-01}
S. Gao and P. Gerdes, 
{\it Computably enumerable equivalence relations}, 
Stud. Log., \textbf{67}:1 (2001), 27--59.
MR1833652

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

\bibitem{ALM-14}
U. Andrews, S. Lempp, J.\,S. Miller, K.\,M. Ng, L. San Mauro, and A. Sorbi, 
{\it Universal computably enumerable equivalence relations}, 
J. Symb. Log., \textbf{79}:1 (2014), 60--88.
MR3226012

\bibitem{ASS-20}
U. Andrews, N. Schweber, and A. Sorbi, 
{\it The theory of ceers computes true arithmetic}, 
Ann. Pure Appl. Logic, \textbf{171}:8 (2020), 102811.
MR4105603

%%%%%%%%%%%%%%%%%

\bibitem{AS-21}
U. Andrews and A. Sorbi,
{\it Effective inseparability, lattices, and preordering relations},
Rev. Symb. Log., \textbf{14}:4 (2021), 838--865.
MR4354887

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

\bibitem{BBK-20}
S.\,A. Badaev, N.\,A. Bazhenov, and B.\,S. Kalmurzaev,
{\it The structure of computably enumerable preorder relations},
Algebra Logic, \textbf{59}:3 (2020), 201--215.
MR4183163

\bibitem{BKMK-21}
S.\,A. Badaev, B.\,S. Kalmurzayev, N.\,K. Mukash, and A.\,A. Khamitova,
{\it Special classes of positive preorders},
Sib. Elektron. Mat. Izv., \textbf{18}:2 (2021), 1657--1666.
MR4356400

\bibitem{ABK-22}
A. Askarbekkyzy, N.\,A. Bazhenov, and B.\,S. Kalmurzayev,
{\it Computable reducibility for computable linear orders of type $\omega$},
J. Math. Sci., \textbf{267}:4 (2022), 429--443.


%%%%%%%%%%%%%%%%%%%

\bibitem{AK00}
C.\,J. Ash and J.\,F. Knight,
{\it Computable Structures and the Hyperarithmetical Hierarchy}, vol.~144 of Stud. Logic Found. Math.
Elsevier Science B.V., Amsterdam, 2000.
MR1767842

\bibitem{Ros-82}
J.\,G. Rosenstein, 
{\it Linear orderings}, 
vol.~98 of Pure and Applied Mathematics. 
Academic Press, New York, 1982.
MR662564

\bibitem{BK-18}
N.\,A. Bazhenov and B.\,S. Kalmurzaev,
{\it On dark computably enumerable equivalence relations},
Sib. Math. J., \textbf{59}:1 (2018), 22--30.
MR3869935

\bibitem{Har-98}
V.\,S. Harizanov,
{\it Turing degrees of certain isomorphic images of computable relations}, 
Ann. Pure Appl. Logic, \textbf{93}:1--3 (1998), 103--113.
MR1635602

%%%%%%%%%%%%%%%%%
	
\end{thebibliography}


\end{document}



