\documentstyle{SibMatJ}
% \TestXML
\topmatter

  \Author           Bazhenov
    \Initial        N.
    \Initial        A.
    \ORCID          0000-0002-5834-2770
    \Email          bazhenov\@math.nsc.ru
    \AffilRef       1
  \endAuthor

  \Author           Marchuk
    \Initial        M.
    \Initial        I.
    \Email          margaretmarchuk\@gmail.com
    \AffilRef       1
    \Corresponding
  \endAuthor

  \Affil 1
    \Organization   Sobolev Institute of Mathematics
    \City           Novosibirsk
    \Country        Russia
  \endAffil

  \datesubmitted    July 18, 2025\enddatesubmitted
  \daterevised      December 26, 2025\enddaterevised
  \dateaccepted     January 1, 2026\enddateaccepted

  \UDclass
    510.5
  \endUDclass

  \thanks
    The work was carried out in the framework of the State Task to the Sobolev Institute of Mathematics (project FWNF--2026--0032).
    The work of Bazhenov was funded by the Science Committee of the Ministry of Science and Higher Education of the Republic of Kazakhstan
    (grant AP26198617).
  \endthanks

  \title
    On Weihrauch Complexity for Elementary Embeddings into Countable Saturated Models
  \endtitle

  \abstract
    For a class of models $\Cal{K}$, we study the Weihrauch complexity of the following model-theoretical problem: finding an elementary embedding from an arbitrary model $\Cal{M}\in\Cal{K}$ into a countable saturated model $\Cal{N}$ such that $\Cal{N}\in\Cal{K}$ and $\Cal{N}$ is elementarily equivalent to $\Cal{M}$. We prove that for the classes of linear orders, Boolean algebras, and abelian groups, this problem is strongly Weihrauch equivalent to the problem $\lim$ (that is, the problem of finding limit on Baire space). We isolate some natural classes $\Cal{K}$ containing equivalence structures such that the corresponding problem for $\Cal{K}$ has Weihrauch degree that is strictly less than the degree of $\lim$.
  \endabstract

  \keywords
    Weihrauch reducibility,
    elementary embedding,
    countable saturated model
  \endkeywords

\endtopmatter

\head
  1. Introduction
\endhead

The paper studies uniform computational content of elementary embeddability problems. We focus on the Weihrauch complexity of these problems.

Modern mathematical logic provides two well-known approaches to comparing strength of different mathematical theorems. The first approach aims to calibrate the proof-theoretic strength via {\it reverse mathematics}. In reverse mathematics, statements about countably presentable structures are formalized in the second-order arithmetic $Z_2$. One typically chooses $\operatorname{RCA}_0$ as a base subsystem of $Z_2$.
Another familiar subsystem is $\operatorname{ACA}_0$ that has comprehension scheme for each arithmetic formula. We refer to, e.g., the monographs~[1,\,2] for the background on reverse mathematics. We note that there exists a large body of literature that investigates reverse-mathematical aspects of model theory: see, e.g., [3--6].

Another approach is based on the notion of {\it Weihrauch reducibility\/} [7,\,8]. Many familiar mathematical theorems $\xi$ can be written in the following form:
$$
	(\forall x\in X) [ \rho(x)  \rightarrow (\exists y\in Y) \psi(x,y)],
\tag1
$$
where $\rho$ and $\psi$ are arithmetical formulas. Hence, such a theorem $\xi$ can be represented as a (computational) {\it problem\/} $F$ as follows. The problem $F$ is a (partial) multivalued 
function $F :\subseteq X \rightrightarrows Y$. %\? :\subseteq
An element $p\in \operatorname{dom}(F) = \{ x\in X : \rho(x)\}$ is called an {\it instance\/} of $F$, and an arbitrary $q\in Y$ satisfying $\psi(p,q)$ is a~{\it solution\/} (for the instance $p$).

Weihrauch reducibility $\leq_{W}$ and strong Weihrauch reducibility $\leq_{sW}$ allow  %\?us
to compare the computational strength of problems $F$ arising from the form~\Tag(1). The formal definitions of $\leq_{W}$ and $\leq_{sW}$ are given in \Sec*{Section~2}. For the known results on Weihrauch complexity, we refer to, e.g., the surveys~[9,\,10].

In this paper, we consider the Weihrauch complexity for model-theoretic problems. We illustrate our approach via the following example. The system $\operatorname{ACA}_0$ is often characterized via the iterations of the familiar problem $\lim$;
see Section~3 of~[10]. Here $\lim$ is the problem of finding the limit of a sequence in Baire space (see the formal definition in \Sec*{Section~2}). In particular, the following model-theoretic facts are known.

\Item (1) %\? есть \tag ссылок нет, по-моему
Over the system $\operatorname{RCA}_0$, $\operatorname{ACA}_0$ is equivalent to the following classical theorem: every countable atomic model $\Cal{M}$ is prime (i.e., $\Cal{M}$ is elementarily embeddable into any model $\Cal{N}$ that is elementarily equivalent to $\Cal{M}$); see Theorem~2.3 of~[3].

\Item (2)  %\? есть \tag ссылок нет, по-моему
This reverse-mathematical result has a natural counterpart in Weihrauch complexity. The problem of finding an elementary embedding $\theta$ from a given countable atomic model $\Cal{M}$ into a given countable model $\Cal{N} \equiv \Cal{M}$ is strongly Weihrauch equivalent to the problem $\lim$; see~[11].

Further known examples of Weihrauch degrees for model-theoretic problems can be found, e.g., in Section~7.3 of~[6].

The current paper continues investigations started in our previous work~[11]. For a given class of structures $\Cal{K}$, we consider the following problems:

	\Item (i)
$\operatorname{ElEm}_{\Cal{K}}(\text{prime},\text{any})$:

\Subitem $\smallbullet$ %\?--
Instance:  Complete diagrams of countable models $\Cal{M},\Cal{N}\in\Cal{K}$ such that $\Cal{M}$ and $\Cal{N}$ are elementarily equivalent, and $\Cal{M}$ is an atomic model.
		
		\Subitem $\smallbullet$ %\?--
Solution: An elementary embedding $\theta \colon \Cal{M} \to \Cal{N}$.
	
	\Item (ii)
$\operatorname{ElEm}_{\Cal{K}}(\text{any},\text{sat})$:

\Subitem $\smallbullet$ %\?--
Instance: Complete diagrams of countable models $\Cal{M},\Cal{N}\in\Cal{K}$ such that $\Cal{M}$ and $\Cal{N}$ are elementarily equivalent, and $\Cal{N}$ is a countable saturated model.
		
\Subitem $\smallbullet$ %\?--
 Solution: An elementary embedding $\theta \colon \Cal{M} \to \Cal{N}$.

In the previous work we have obtained the following result:

\proclaim{Theorem 1.1 \rm (Theorems~5 and~11 of~[11])}
{\rm(a)}
The class of all undirected graphs $\Bbb{UG}$ satisfies $\operatorname{ElEm}_{\Bbb{UG}}(\text{prime},\text{any}) \equiv_{sW} \lim$.
	
{\rm (b)}
The class of all equivalence structures $\Bbb{E}$ satisfies $\operatorname{ElEm}_{\Bbb{E}}(\text{any},\text{sat}) \equiv_{sW} \lim$.
\endproclaim

Here we focus on countable saturated models: we find the Weihrauch complexity of $\operatorname{ElEm}_{\Cal{K}}(\text{any},\text{sat})$ for various natural classes $\Cal{K}$. The paper is arranged as follows. \Sec*{Section~2} gives the necessary preliminaries.
In \Sec*{Section~3}  we isolate some natural subclasses $\Cal{K}$ of equivalence structures such that the Weihrauch degree $\bold{d}_{W,\Cal{K}}$ of $\operatorname{ElEm}_{\Cal{K}}(\text{any},\text{sat})$ is {\it strictly less\/} than the degree $\deg_{W}(\lim)$.
Namely, in  \Par{Theorem~3.3}{Theorems~3.3},  \Par{Theorem~3.7}{3.7},  and \Par{Theorem~3.10}{3.10}, %\?
we obtain the following realizable examples of $\bold{d}_{W,\Cal{K}}$:

	\Item $\smallbullet$
$\lim_{\Bbb{N}}$ (the limit problem on natural numbers),
	
	\Item $\smallbullet$
$\roman{LPO}$ %\? где \roman, было \mathsf
(limited principle of omniscience),

	\Item $\smallbullet$
$\roman{LLPO}$ (lesser limited principle of omniscience).

In \Sec*{Section~4} we prove that for the following classes $\Cal{K}$, the problem $\operatorname{ElEm}_{\Cal{K}}(\roman{any},\roman{sat})$ is strongly Weihrauch equivalent to $\lim$:

	\Item $\smallbullet$
linear orders,
	
	\Item $\smallbullet$
Boolean algebras,
	
	\Item $\smallbullet$
abelian groups.

\head
2. Preliminaries
\endhead

We consider only computable signatures $\sigma$. We identify first-order formulas $\psi(\bar x)$ with their G\"odel numbers. For the background on model theory, we refer to~[12]. For the preliminaries on computable model theory, we refer to the monograph~[13] and the survey~[14].

Preliminaries on computability theory can be found in~[15].
As usual, $(\varphi_e)_{e\in\omega}$ denotes the standard computable numbering of all unary partial computable functions. By $\langle \cdot, \cdot\rangle$ we denote the pairing function:
$$
	\langle x,y\rangle = \frac{(x+y)(x+y+1)}{2} + x.
$$
By $(D_k)_{k\in\omega}$ we denote the standard strongly computable numbering of all finite sets: that is, $D_0 = \emptyset$, and if $k = 2^{x_0} + 2^{x_1} + \dots + 2^{x_m}$, where $x_0 < x_1 < \dots <x_m$, then $D_k = \{ x_0, x_1, \dots, x_m\}$.

As usual, we use the following notations for familiar order types:

	\Item $\smallbullet$
$\omega$ is the order of natural numbers,
	
	\Item $\smallbullet$
$\zeta$ is the order of integers,
	
	\Item $\smallbullet$
$\eta$ is the order of rationals.

Here we give a definition of {\it Weihrauch reducibility\/} that is not equivalent to the general definition of Weihrauch reducibility (for problems $F: \subseteq X \rightrightarrows Y$ defined on arbitrary represented spaces $X$ and $Y$). Nevertheless, this definition is equivalent to the general definition in the case when $X$ and $Y$ are subspaces of Baire space $\omega^{\omega}$. We consider only such spaces (here we note that Cantor space $2^{\omega}$ and the countable discrete space $\omega$ can be viewed as subspaces of $\omega^{\omega}$). In particular, a given countable model $\Cal{M}$ (having domain $\omega$) is identified with the characteristic function $\chi_{FD(\Cal{M})} \in 2^{\omega}$ of its complete diagram.

The definition below follows Definition~1.5 from Appendix~A of~[16].

\demo{Definition 1}
Let $F, G : \subseteq \omega^\omega \rightrightarrows \omega^\omega$ be multivalued functions.

\Item (a)
$F$ is {\it Weihrauch reducible\/} to $G$ (denoted by $F \leq_W G$) if there exist Turing functionals $\Phi, \Psi : \subseteq \omega^\omega \to \omega^\omega$ such that:

		\Subitem $\smallbullet$ %-- %\?
$\Phi(p) \in \operatorname{dom}(G)$ for any $p \in \operatorname{dom}(F)$,
		
		\Subitem $\smallbullet$ %-- %\?
$\Psi(p\oplus q) \in F(p)$ for any $p \in \operatorname{dom}(F)$ and $q \in G(\Phi(p))$.

	Informally speaking, the ``preprocessing'' operator $\Phi$ transforms a given instance $p$ of the problem $F$ into an instance $p_G$ of the problem $G$. Given an arbitrary solution $q$ of the instance $p_G$,
the ``postprocessing'' operator $\Psi$ produces $\Psi(p\oplus q)$ that is a solution of the original instance $p$.

\Item (b)
$F$ is {\it strongly Weihrauch reducible\/} to $G$ (denoted by  $F \leq_{sW} G$) if there exist Turing functionals $\Phi, \Psi : \subseteq \omega^\omega \to \omega^\omega$ such that:

		\Subitem $\smallbullet$ %-- %\?
$\Phi(p) \in \operatorname{dom}(G)$ for any $p \in \operatorname{dom}(F)$,
		
		\Subitem $\smallbullet$ %-- %\?
$\Psi(q) \in F(p)$ for any $p \in \operatorname{dom}(F)$ and $q \in G(\Phi(p))$.
	
	Note that here the postprocessing operator $\Psi$ does not use the initial instance~$p$.
\enddemo

We give a list of the benchmark problems that will be used throughout the paper.

{\bf(1)}
For $p\in\omega^{\omega}$ and $i\in\omega$, $p^{[i]}$ denotes the $i$th column of $p$, that is, $p^{[i]}(x) = p(\langle i,x\rangle)$.

The {\it limit map\/} (on Baire space) %\?the
is the partial function $\lim :\!\subseteq  %\?
\omega^{\omega} \to \omega^\omega$ such that:

	\Subitem $\smallbullet$
$\lim(p) = \lim_{i\rightarrow\infty} p^{[i]}$, if there exists $\lim_{i\rightarrow\infty} p^{[i]}$,
	
	\Subitem $\smallbullet$
$\lim(p)$ is undefined, otherwise.

{\bf(2)}
The {\it Turing jump\/} is the function $\operatorname{J} \colon \omega^{\omega} \to \omega^\omega$ such that
$$
\operatorname{J}(p)(i) =
\cases
	1, & \text{if } F\varphi^p_i(0) {\downarrow},
\\
	0, & \text{otherwise},
\endcases
$$
for all $p\in\omega^\omega$ and $i\in\omega$.
The following result on the connection between $\lim$ and $\operatorname{J}$ is well known:

\proclaim{Theorem 2.1 \rm (see [9, Theorem~11.6.7])}
	The problem $\lim$ is strongly Weihrauch equivalent to $\operatorname{J}$.
\endproclaim

{\bf(3)}
The problem $\lim_{\Bbb{N}}$ is defined as follows:

	\Subitem $\smallbullet$
Instance: a function $p\in\omega^{\omega}$ such that there exists $\lim_s p(s)$.
	
	\Subitem $\smallbullet$
Solution: the number $\lim_s p(s)$ from $\omega$.

{\bf(4)}
The problem $\roman{LPO}$ (limited principle of omniscience) is defined as follows:

	\Subitem $\smallbullet$
Instance: a function $p\in\{0,1\}^{\omega}$.
	
	\Subitem $\smallbullet$
Solution:
	$$
		\cases
			1, & \text{if } \exists s (p(s) = 1),\\
			0, & \text{otherwise}.
		\endcases
	$$

{\bf(5)}
By $\widehat{0}$ we denote the infinite string $000\dots$. The problem $\roman{LLPO}$ (lesser limited principle of omniscience) is defined as follows:

	\Subitem $\smallbullet$
Instance: functions $p_0,p_1\in\{0,1\}^{\omega}$ such that $(p_0 = \widehat{0}\vee p_1=\widehat{0})$.
	
	\Subitem $\smallbullet$
Solution: an element of $\{i\in\{0,1\}: p_i=\widehat{0}\}$.

The following result about our benchmark problems is known:

\proclaim{Theorem 2.2}
	We have the following strict inequalities:

		\Item (a) %(1)
$\roman{LLPO} <_W \roman{LPO}$ {\rm([8];} see also Theorem~{\rm7.13} in~{\rm[17])}.
		
		\Item (b) %(2)
$\roman{LPO} <_{W} \lim_{\Bbb{N}}$ {\rm([8];} see also Proposition~{\rm11.7.17} and Theorem~{\rm11.7.13} in {\rm[9])}.
		
		\Item (c) %(3)
$\lim_{\Bbb{N}} <_{W} \lim$ {\rm(}Corollary~{\rm9.9} of~{\rm[18]}; see also Example~{\rm11.6.19} in~{\rm[9])}.
\endproclaim

For a signature $\sigma$, by $\Cal{K}_{\sigma}$ we denote the class of all $\sigma$-structures. We recall the following result from~[11].

\proclaim{Proposition 2.3 \rm (Propositions~6 and~12 of~[11])}
	We have $\operatorname{ElEm}_{\Cal{K}_{\sigma}}(\roman{prime},\roman{any}) \leq_{sW}\lim$ and $\operatorname{ElEm}_{\Cal{K}_{\sigma}}(\roman{any},\roman{sat}) \leq_{sW} \lim$. Consequently, any subclass $\Cal{K} \subseteq \Cal{K}_{\sigma}$ also satisfies $\operatorname{ElEm}_{\Cal{K}}(\roman{prime},\roman{any}) \leq_{sW} \lim$ and $\operatorname{ElEm}_{\Cal{K}}(\roman{any},\roman{sat}) \leq_{sW} \lim$.
\endproclaim

\head
3. Further Examples for Equivalence Structures
\endhead

An equivalence structure $\Cal{A} = (|\Cal{A}|, E^{\Cal{A}})$ consists of a set with an equivalence relation on this set.
If~$|\Cal{A}|$ is countable, then without loss of generality, we may assume that $|\Cal{A}| = \omega$. For an element $a\in |\Cal{A}|$, $[a]_{\Cal{A}}$ denotes the $E^{\Cal{A}}$-equivalence class of $a$.
The {\it character\/} of an equivalence structure $\Cal{A}$ is the set
$$
	\chi(\Cal{A}) = \bigl\{  (n,k)\,\colon n,k>0, \text{ and } \Cal{A} \text{ has at least } k \text{ equivalence classes of size } n\bigr\}.
$$
We say that the character $\chi(\Cal{A})$ is {\it bounded\/} if there exists a natural number $m_0$ such that the structure $\Cal{A}$ does not have finite equivalence classes of size greater than $m_0$.

We recall the following known result:

\proclaim{Proposition 3.1 \rm (folklore)}
	Let $\Cal{A}$ be a countable equivalence structure that has bounded character.
Then the theory $\operatorname{Th}(\Cal{A})$ is countably categorical.
\endproclaim

\demo{Proof}
	First, we introduce some ancillary formulas. For $n\geq 1$, we define:

		\Item $\smallbullet$
$\psi_{\geq n} (x) = \exists y_1 \exists y_2 \dots \exists y_n [ y_i$ are pairwise different and $(y_i\,E\,x)]$,
        \Item $\smallbullet$
the formula $\psi_{=n}(x) = \psi_{\geq n}(x) \,\&\, \neg \psi_{\geq n+1}(x)$ says that the class $[x]_E$ has size $n$.

\noindent
	Then the condition $(n,k)\in \chi(\Cal{A})$ holds if and only if $\Cal{A}$ contains pairwise nonequivalent elements $x_1,\dots, x_k$ satisfying $\psi_{=n}(x_i)$, $i\leq k$.

	Fix a number $m_0\in\omega$ such that for any finite $n > m_0$ the structure $\Cal{A}$ does not have classes of size~$n$. We construct a set of axioms $\Gamma$. Consider each nonzero $n \leq m_0$.  \Label{ad}

		\Item (a)
If $\Cal{A}$ has infinitely many equivalence classes of size $n$, then for each $k\geq 1$ we add to $\Gamma$ an axiom saying that $(n,k) \in \chi(\Cal{A})$.
		
		\Item (b)
If $\Cal{A}$ does not have classes of size $n$, then we add an axiom saying that $(n,1)\notin \chi(\Cal{A})$.
		
		\Item (c)
Suppose that $\Cal{A}$ has precisely $k'$-many classes of size $n$, where $1\leq k' <\omega$. Then we add an axiom saying that $(n,k')\in\chi(\Cal{A})$ and $(n,k'+1)\notin\chi(\Cal{A})$.
		
		\Item (d)
For every $m > m_0 +1$, we add the axiom $\forall x [ \psi_{\geq m_0+1}(x) \rightarrow \psi_{\geq m}(x)]$. This series of axioms implies that every equivalence class that has size at least $m_0+1$ must be infinite.
		
		\Item (e)
Similarly to %\?
Items~\Par{ad}{(a)}--\Par{ad}{(c)}, we also specify the number of infinite equivalence classes in the structure. For example, if $\Cal{A}$ contains precisely $k'$-many infinite classes, where $1\leq k' < \omega$, then we should say that there exist $k'$-many pairwise nonequivalent $x_i$ satisfying $\psi_{\geq m_0+1}(x_i)$, and one cannot find $(k'+1)$-many elements with this property.

	Note that $\Gamma \subseteq \operatorname{Th}(\Cal{A})$.
	
	We show that $\operatorname{Th}(\Cal{A})$ is countably categorical. Suppose that $\Cal{B}$ is a countable model of $\operatorname{Th}(\Cal{A})$. Since $\Cal{B} \models \Gamma$, we deduce the following:

		\Item $\smallbullet$
For each $n\leq m_0$, the structures $\Cal{B}$ and $\Cal{A}$ have the same number of classes of size~$n$.
		
		\Item $\smallbullet$
For every finite $n > m_0$, the structure $\Cal{B}$ does not have classes of size $n$.
		
		\Item $\smallbullet$
The structures $\Cal{B}$ and $\Cal{A}$ have the same number of countably infinite classes.

	These facts imply that $\Cal{B}$ is isomorphic to $\Cal{A}$. We conclude that $\operatorname{Th}(\Cal{A})$ is a countably categorical theory.
\qed\enddemo

Our proofs will also use the following fact:

\proclaim{Theorem 3.2 \rm (follows from Section 5 of~[19])}
	A computable equivalence structure $\Cal{A}$ is decidable if and only if the character $\chi(\Cal{A})$ is computable and the set
	$$
		K(\Cal{A}) := \bigl\{ (a,k)\in \omega^2:\roman{card}([a]_{\Cal{A}}) \geq k\bigr\}
\tag2
	$$
	is computable.
\endproclaim

We use the following ancillary problem:

\demo{Definition 2}
	Given a class of equivalence structures $\Cal{K}$, we define the problem $\operatorname{SizePrEmb}_{\Cal{K}}$ (the problem of ``size preserving'' embeddings) as follows:

		\Item $\smallbullet$
Instance: Complete diagrams of countable models $\Cal{A},\Cal{B}\in\Cal{K}$ such that $\Cal{A}$ is isomorphic to $\Cal{B}$.
		
		\Item $\smallbullet$
Solution: An isomorphic embedding $\theta \colon \Cal{A} \to \Cal{B}$ such that all $x\in\Cal{A}$ satisfy $\card([\theta(x)]_{\Cal{B}}) = \card([x]_{\Cal{A}})$.

	We note that Proposition~4 of~[11] implies that for $\Cal{A} \cong \Cal{B}$, any such embedding $\theta$ is an elementary embedding.
\enddemo

Our first result of this section isolates a class of equivalence structures
$\Cal{K}_{fin}$ %\?fin прямо
such that $\operatorname{ElEm}_{\Cal{K}_{fin}}(\roman{any},\roman{sat})$ is Weihrauch equivalent to
$\lim_{\Bbb{N}}$.

\proclaim{Theorem 3.3}
	Let $\Cal{K}_{fin}$ be the class of all countable equivalence structures $\Cal{E}$ such that $\Cal{E}$ has only finitely many finite equivalence classes. Then we have
	$$
		\operatorname{ElEm}_{\Cal{K}_{fin}}(\roman{prime},\roman{any}) = \operatorname{ElEm}_{\Cal{K}_{fin}}(\roman{any},\roman{sat}) \equiv_{W} \lim\nolimits_{\Bbb{N}}.
	$$
\endproclaim

\demo{Proof}
By \Par*{Proposition~3.1}, every structure $\Cal{E}$ from $\Cal{K}_{fin}$ has countably categorical theory. Hence, $\Cal{E}$ is both a prime model and a countable saturated model of $\operatorname{Th}(\Cal{E})$, and furthermore,
$$
	\operatorname{ElEm}_{\Cal{K}_{fin}}(\roman{prime},\roman{any}) = \operatorname{ElEm}_{\Cal{K}_{fin}}(\roman{any},\roman{sat}).
$$

Our further proof uses the following result:

\proclaim{Lemma 3.4}
	 $\operatorname{ElEm}_{\Cal{K}_{fin}}(\roman{any},\roman{sat})=\operatorname{SizePrEmb}_{\Cal{K}_{fin}}$.
\endproclaim

\demo{Proof}
	\Par*{Proposition~3.1} implies that for any structures $\Cal{A},\Cal{B}\in\Cal{K}_{fin}$, the structures $\Cal{A}$ and $\Cal{B}$ are elementarily equivalent if and only if $\Cal{A}$ and $\Cal{B}$ are isomorphic.
	
	Suppose that $\Cal{A}$ and $\Cal{B}$ are isomorphic structures belonging to $\Cal{K}_{fin}$. Every size preserving isomorphic embedding (in the sense of \Par*{Definition~2}) $\theta\colon \Cal{A} \to \Cal{B}$ is an elementary embedding. On the other hand, it is clear that every elementary embedding $\theta$ must be size preserving.
\qed\enddemo

Now we construct two Weihrauch reductions
(in \Par{Proposition 3.5}{Propositions~3.5} and~\Par{Proposition 3.6}{3.6} below).

\proclaim{Proposition 3.5}
	$\lim_{\Bbb{N}} \leq_{W} \operatorname{SizePrEmb}_{\Cal{K}_{fin}}$.
\endproclaim

\demo{Proof}
Fix a function $p\in\omega^\omega$ such that $\lim_s p(s)$ exists. For this $p$, we construct two equivalence structures $\Cal{A}$ and $\Cal{B}$.

The domain of the structure $\Cal{A}$ will be equal to $\{ w\} \cup \{ a_i : i\in\omega\} \cup \{ c_j : j\in\omega\}$.
The domain of~$\Cal{B}$ will be equal to $\{ b_i : i\in\omega\} \cup \{ d_j : j\in\omega\}$. We always assume that $w\notin [a_i]_{\Cal{A}}$, $[a_i]_{\Cal{A}} \neq [a_j]_{\Cal{A}}$, and $[b_i]_{\Cal{B}} \neq [b_j]_{\Cal{B}}$ for $i\neq j$. The equivalence class $[w]_{\Cal{A}}$ will be infinite.

At a stage $s$ of the construction we build finite equivalence structures $\Cal{A}_s$ and $\Cal{B}_s$. We also define an ancillary parameter $r(s) \in \omega$.

At stage $0$ we put $\Cal{A}_0 = \{ w\}$, $\Cal{B}_0 = \emptyset$, and $r(0) = 0$.

{\sc Stage $s+1$.}
First, we add to the class $[w]_{\Cal{A}_{s+1}}$ the least unused element $c_t$ (that is, $c_t$ having the least index $t$ such that $c_t$ has not been added to $\Cal{A}$ before). We also add the elements $a_s$ and $b_s$ to $\Cal{A}_{s+1}$ and $\Cal{B}_{s+1}$, respectively. We use the least unused elements $c_t$ and $d_t$, respectively, to make each of the current classes $[a_s]_{\Cal{A}_{s+1}}$ and $[b_s]_{\Cal{B}_{s+1}}$ have cardinality $\card(\Cal{A}_s) + 1$.

If $p(s) = p(s+1)$, then we set $r(s+1) = r(s)$. For each $i$ such that $r(s) < i \leq s$, we proceed as follows:

	\Item $\smallbullet$
we add to the class $[a_i]_{\Cal{A}_{s+1}}$ the least unused element $c_m$,
	
	\Item $\smallbullet$
we add to $[b_i]_{\Cal{B}_{s+1}}$ the least unused element $d_n$.

If $p(s) \neq p(s+1)$, then we put $r(s+1) = s$. We declare that for every $i\leq r(s+1)$, the classes $[a_i]_{\Cal{A}}$ and $[b_i]_{\Cal{A}}$ are {\it finished}: these classes will not grow at further stages.

Note that by the end of the stage $s+1$ we have $\card([b_i]_{\Cal{B}_{s+1}}) = \card([a_i]_{\Cal{A}_{s+1}}) < \card([a_j]_{\Cal{A}_{s+1}})$ for all $i<j \leq s$. We also note the following feature of the construction: if some $d_t$ is added into $[b_s]_{\Cal{B}}$, then we have $t \geq s$.

This concludes the description of the construction. We put $\Cal{A} = \bigcup_{s\in\omega} \Cal{A}_s$ and $\Cal{B} = \bigcup_{s\in\omega} \Cal{B}_s$. It is clear that the constructed structures are $p$-computable (uniformly in $p$).

We define the number
$$
	s^{\ast} = \cases
		\max \{ s\in\omega : p(s) \neq p(s+1)\}, 
& \text{if } \exists s (p(s) \neq p(s+1)),\\
		0, & \text{otherwise}.
	\endcases
\tag3
$$
The construction ensures that for all $s \geq s^{\ast}+1$ we have $r(s) = s^{\ast}$. Therefore, for every $j \geq s^{\ast}+1$, the classes $[a_j]_{\Cal{A}}$ and $[b_j]_{\Cal{B}}$ are infinite. Hence, both $\Cal{A}$ and $\Cal{B}$ have infinitely many infinite classes, and for $i\leq s^{\ast}$ we have
$$
	\card([a_i]_{\Cal{A}}) = \card([b_i]_{\Cal{B}}) < \omega.
$$
We deduce that the structures $\Cal{A}$ and $\Cal{B}$ are isomorphic, and $\Cal{A},\Cal{B} \in \Cal{K}_{fin}$.

Now we show that both $\Cal{A}$ and $\Cal{B}$ are $p$-decidable, uniformly in $p$.

(1)  %\?
Firstly, we note that for each finite $n\geq 1$, the structure $\Cal{A}$ has at most one equivalence class of size $n$. Indeed, if $s\geq n$, then $\card([a_s]_{\Cal{A}}) \geq n+1$. In addition, if $\card([a_i]_{\Cal{A}}) =n$, then for all $j< n$ such that $j\neq i$, we have $\card([a_j]_{\Cal{A}}) \neq n$. Therefore, $(n,k) \notin\chi(\Cal{A})$ for all $k\geq 2$.

We describe a procedure that determines whether $(n,1)$ belongs to $\chi(\Cal{A})$. We find the least stage~$s'$ such that by the end of the stage~$s'$, for each $i<n$ either the class $[a_i]_{\Cal{A}}$ is already finished, or $\card([a_i]_{\Cal{A}_{s'}}) \geq n+1$. Then we have $(n,1) \in \chi(\Cal{A})$ if and only if inside the structure $\Cal{A}_{s'}$ some finished class $[a_i]_{\Cal{A}_{s'}}$ has cardinality $n$.

We conclude that the character $\chi(\Cal{A})=\chi(\Cal{B})$ is $p$-computable, uniformly in $p$.

(2) %\?
Now given $x\in \Cal{A}$ and $k\geq 1$, we want to check whether $\card([x]_{\Cal{A}}) \geq k$ is true. If $x\in \{ c_j : j\in\omega\}$, then we can $p$-computably find an element $u\in \{ w\} \cup \{ a_i : i\in\omega\}$ such that $x\in [u]_{\Cal{A}}$. Since the class $[w]_{\Cal{A}}$ is infinite, in what follows we may assume that $x = a_i$ for some $i\in\omega$.

We find the least stage $s'$ such that by the end of the stage $s'$ either $[a_i]_{\Cal{A}}$ is finished, or $\card([a_i]_{\Cal{A}_{s'}}) \geq k$. If  $[a_i]_{\Cal{A}}$ is already finished, then clearly, $\card([a_i]_{\Cal{A}})$ is already ``finalized'' and is equal to $\card([a_i]_{\Cal{A}_{s'}})$.

We deduce that the set $K(\Cal{A})$ from equation \Tag(2) is $p$-computable, uniformly in $p$. A similar argument establishes the $p$-computability of $K(\Cal{B})$.

By a relativized version of \Par*{Theorem~3.2}, we conclude that the structures $\Cal{A}$ and $\Cal{B}$ are $p$-decidable, uniformly in $p$.

Finally, let $\theta$ be an arbitrary size preserving embedding from $\Cal{A}$ into $\Cal{B}$. Suppose that $\theta(w) \in [b_j]_{\Cal{B}}$ for some $j\in\omega$. Then the class $[b_j]_{\Cal{B}}$ is infinite, and hence, $[b_j]_{\Cal{B}}$ is never declared finished. Therefore, we have $j\geq s^{\ast} + 1$, where the parameter $s^{\ast}$ is taken from equation \Tag(3)). Hence, we have either $\theta( w) = b_j$ or $\theta(w) = d_t$, where $t \geq j$ (recall that every $d_t \in [b_j]_{\Cal{B}}$ must satisfy $t \geq j$).
We put
$$
	t^{\ast} = \cases
		j, & \text{if } \theta(w) = b_j,\\
		t, & \text{if } \theta(w) = d_t.
	\endcases
$$
It is clear that $t^{\ast} \geq s^{\ast} + 1$, and hence $p(t^{\ast}) = \lim_s p(s)$. Therefore, using $p$ and $\theta$, we can uniformly compute the limit $\lim_s p(s)$. We deduce that $\lim_{\Bbb{N}} \leq_{W} \operatorname{SizePrEmb}_{\Cal{K}_{fin}}$.
\qed\enddemo

\proclaim{Proposition 3.6}
$\operatorname{SizePrEmb}_{\Cal{K}_{fin}} \leq_{W} \lim_{\Bbb{N}}$.
\endproclaim

\demo{Proof}
Let $\Cal{A}$ and $\Cal{B}$ be isomorphic structures from $\Cal{K}_{fin}$. We construct an element $p = p_{(\Cal{A},\Cal{B})}\in\omega^\omega$ such that by using $\lim_s p(s)$ and the complete diagrams of $\Cal{A},\Cal{B}$, we can build (in a uniformly computable way) a size preserving embedding $\theta$ from $\Cal{A}$ into $\Cal{B}$.

Note that for making a uniform construction of an embedding $\theta$ from $\Cal{A}$ to $\Cal{B}$, it is sufficient to know how many finite classes are contained in $\Cal{A}$ and what their sizes are. We illustrate this via an example. Suppose that we know that $\Cal{A}$ contains one class of size~3 and one class of size~5, and all the other classes of $\Cal{A}$ are infinite. Then our construction of $\theta$ proceeds as follows:

	\Item $\smallbullet$
By searching through the complete diagrams of $\Cal{A}$ and $\Cal{B}$, we find elements $a,c\in\Cal{A}$ and $b,d\in\Cal{B}$ such that $\card([a]_{\Cal{A}}) = \card([b]_{\Cal{B}}) = 3$ and $\card([c]_{\Cal{A}}) = \card([d]_{\Cal{B}}) = 5$. The function $\theta_0$ maps $[a]_{\Cal{A}}$ onto $[b]_{\Cal{B}}$, and $[c]_{\Cal{A}}$ onto $[d]_{\Cal{B}}$.
	
	\Item $\smallbullet$
At a stage $s+1$, the finite map $\theta_{s+1} \supseteq \theta_s$ is defined as follows. Suppose that $s \notin [a]_{\Cal{A}} \cup [c]_{\Cal{A}}$. Then we have to define the value $\theta_{s+1}(s)$. We first check whether there exists $x<s$ such that $s\in [x]_{\Cal{A}}$. 	 
		\Subitem -- %\?
If there exists such $x$, then we find a fresh element $y\in [\theta(x)]_{\Cal{B}} \setminus \operatorname{range}(\theta_s)$, and we put $\theta_{s+1}(s) = y$. Such element $y$ exists, since $x\notin [a]_{\Cal{A}} \cup [c]_{\Cal{A}}$ and thus, the classes $[x]_{\Cal{A}}$ and $[\theta(x)]_{\Cal{B}}$ are infinite.
	
		\Subitem -- %\?
Otherwise, we find a fresh element $z$ such that $[z]_{\Cal{B}} \cap \operatorname{range}(\theta_s) = \emptyset$. Such $z$ exists, since $\Cal{A}$ and $\Cal{B}$ contain the same number of infinite equivalence classes. We put $\theta_{s+1}(x) = z$.

It is clear that the constructed isomorphic embedding $\theta$ is size preserving.

Recall that $(D_k)_{k\in\omega}$ is the standard effective numbering of all finite subsets of $\omega$. We define the function  $p = p_{(\Cal{A},\Cal{B})}\in\omega^\omega$ as follows.

At a stage $s\in\omega$, using the complete diagram of $\Cal{A}$, we compute the finite set
$$
	F^s = \{ a\leq s : \operatorname{card}([a]_{\Cal{A}}) \leq s+1, \text{ and } (\forall b < a) (b\notin [a]_{\Cal{A}})\}.
$$
We put $p(s) = k$, where the set $D_k$ is equal to $\{ \langle a, \operatorname{card}([a]_{\Cal{A}})\rangle : a \in F^s\}$.

Since $\Cal{A}$ contains only finitely many finite classes, there exists $s_0\in\omega$ such that $p(s) = p(s_0)$ for all $s\geq s_0$. Thus, using the limit $\lim_s p(s)$, we can recover how many finite classes are contained in $\Cal{A}$ and what their sizes are. Using this information and the complete diagrams of the structures $\Cal{A}$ and $\Cal{B}$, we construct a size preserving embedding $\theta$ from $\Cal{A}$ into $\Cal{B}$. Therefore, we have  $\operatorname{SizePrEmb}_{\Cal{K}_{fin}} \leq_{W}\lim_{\Bbb{N}}$.
\qed\enddemo

By \Par{Proposition 3.5}{Propositions~3.5} and~\Par{Proposition 3.6}{3.6}, we conclude that
$\operatorname{SizePrEmb}_{\Cal{K}_{fin}} \equiv_{W}\lim_{\Bbb{N}}$. \Par*{Theorem~3.3} is proved.
\qed\enddemo

Our second result of this section considers a subclass $\Cal{K}_{\leq 1} \subset \Cal{K}_{fin}$.

\proclaim{Theorem 3.7}
	Let $\Cal{K}_{\leq 1}$ be the class of all countable equivalence structures $\Cal{E}$ such that $\Cal{E}$ has at most one finite equivalence class. Then we have
	$$
		\operatorname{ElEm}_{\Cal{K}_{\leq 1}}(\roman{prime},\roman{any}) = \operatorname{ElEm}_{\Cal{K}_{\leq 1}}(\roman{any},\roman{sat}) \equiv_{W} \roman{LPO}.
	$$
\endproclaim

\demo{Proof}
The same argument as in the proof of \Par*{Theorem~3.3} implies that
$$
	\operatorname{SizePrEmb}_{\Cal{K}_{\leq 1}}=\operatorname{ElEm}_{\Cal{K}_{\leq 1}}(\roman{prime},\roman{any}) = \operatorname{ElEm}_{\Cal{K}_{\leq 1}}(\roman{any},\roman{sat}).
$$
\enddemo

 We show that $\operatorname{SizePrEmb}_{\Cal{K}_{\leq 1}} \equiv_{W} \roman{LPO}$ in
 \Par{Proposition 3.8}{Propositions~3.8} and \Par{Proposition 3.9}{3.9}.

\proclaim{Proposition 3.8}
$\roman{LPO}	\leq_{W} \operatorname{SizePrEmb}_{\Cal{K}_{\leq 1}}$.
\endproclaim

\demo{Proof}
Fix a function $p\in\{0,1\}^\omega$. For this $p$ we construct equivalence structures $\Cal{A}$ and $\Cal{B}$.

The domain of the structure $\Cal{A}$ will be equal to $\{ w\} \cup \{ a_{i,j} : i,j\in\omega\} \cup \{ c_k : k\in\omega\}$.
The domain of~$\Cal{B}$ will be equal to $\{ b_{i,j} : i,j\in\omega \}$. Beforehand, we declare the following:

	\Item $\smallbullet$
$[a_{i,0}]_{\Cal{A}} = \{ a_{i,j} : j\in\omega\}$,
	
	\Item $\smallbullet$
if $i_1\neq i_2$, then $b_{i_1,j_1} \notin [b_{i_2,j_2}]_{\Cal{B}}$.

At a stage $s$ of the construction we build equivalence structures $\Cal{A}_s$ and $\Cal{B}_s$. Along the construction, we could declare that the class $[w]_{\Cal{A}}$ becomes {\it finished}.

At stage $0$ we put $\operatorname{dom}(\Cal{A}_0) = \{w\} \cup \{ a_{i,j} : i,j\in\omega\}$ and $\Cal{B}_0 = \emptyset$.

{\sc Stage $s+1$.}
If the class $[w]_{\Cal{A}}$ is already finished, then we do nothing: i.e., we put $\Cal{A}_{s+1} = \Cal{A}_s$ and $\Cal{B}_{s+1} = \Cal{B}_s$.

Suppose that $[w]_{\Cal{A}}$ is not finished yet. Firstly, we add the least unused element $c_m$ into the class~$[w]_{\Cal{A}}$.

If $p(t) = 0$ for all $t\leq s$, then we declare that $[b_{s,0}]_{\Cal{B}} = \{ b_{s,j} : j\in\omega\}$, and we add $[b_{s,0}]_{\Cal{B}}$ into $\Cal{B}_{s+1}$.

If $s$ is the least number such that $p(s) = 1$, then we declare that the class $[w]_{\Cal{A}}$ is finished.
Note that in this case we have  $\card([w]_{\Cal{A}}) = s+2$.  Here we finalize the construction of $\Cal{A}_{s+1}$ and $\Cal{B}_{s+1}$ as follows. We find the least unused $c_n$, and set $[c_n]_{\Cal{A}} = \{ c_\ell : \ell \geq n\}$.  We put:

	\Item $\smallbullet$
$[b_{s,0}]_{\Cal{B}} = \{ b_{s,j} : j\leq s+1\}$,
	
	\Item $\smallbullet$
$[b_{s,s+2}]_{\Cal{B}} = \{ b_{s,j} : j\geq s+2\}$,
	
	\Item $\smallbullet$
$[b_{i,0}]_{\Cal{B}} = \{ b_{i,j} : j\in\omega\}$ for $i\geq s+1$.

This concludes the description of the construction. We define $\Cal{A} = \bigcup_{s\in\omega} \Cal{A}_s$ and $\Cal{B} = \bigcup_{s\in\omega} \Cal{B}_s$. Note that the constructed structures $\Cal{A}$ and $\Cal{B}$ are $p$-computable.

Note that each of the structures $\Cal{A}$ and $\Cal{B}$ has infinitely many infinite classes. If $p(s) = 0$ for all $s$, then all the classes of $\Cal{A}$ and $\Cal{B}$ are infinite. If $s^{\ast}$ is the least number such that $p(s^{\ast}) = 1$, then we have
$$
	\card([w]_{\Cal{A}}) = \card([b_{s^{\ast},0}]_{\Cal{B}}) = s^{\ast} + 2,
$$
and all the other equivalence classes are infinite. Therefore, $\Cal{A} \cong \Cal{B} \in \Cal{K}_{\leq 1}$.

We show that the structures $\Cal{A}$ and $\Cal{B}$ are $p$-decidable, uniformly in $p$. For all $n\geq 1$ and $k\geq 2$, we have $(n,k) \notin \chi(\Cal{A})$. A pair $(n,1)$, where $n\geq 1$, belongs to $\chi(\Cal{A})$ if and only if the class $[w]_{\Cal{A}}$ becomes finished by the end of stage $n$ and we have $\card([w]_{\Cal{A}_n}) = n$. Therefore, the character $\chi(\Cal{A}) =\chi(\Cal{B})$ is $p$-computable, uniformly in $p$.

Every class $[a_{i,j}]_{\Cal{A}}$ is infinite. We have $\card([w]_{\Cal{A}}) \geq k$ if and only if $\card([w]_{\Cal{A}_k}) \geq k$. Every element $c_t$ satisfies the following: either $c_t \in [w]_{\Cal{A}_{t+1}}$, or at the stage $t+1$ we have already declared that the class $[c_t]_{\Cal{A}}$ is infinite. Therefore, the set $K(\Cal{A})$ from equation \Tag(2)  is $p$-computable, uniformly in $p$. A similar argument shows that $K(\Cal{B})$ is also (uniformly) $p$-computable. By a relativized version of \Par*{Theorem~3.2}, we deduce that $\Cal{A}$ and $\Cal{B}$ are $p$-decidable, uniformly in $p$.

Finally, let $\theta$ be an arbitrary size preserving embedding from $\Cal{A}$ into $\Cal{B}$. We find the index $i_0$ such $\theta(w) = b_{i_0,j}$.

	\Item $\smallbullet$
If $\roman{LPO}(p) = 0$, then $p(s) = 0$ for all $s\in\omega$. In particular, we have $(\forall s\leq i_0)(p(s) = 0)$.
	
	\Item $\smallbullet$
If $\roman{LPO}(p) = 1$, then choose the least $s^{\ast}$ such that $p(s^{\ast}) = 1$. Then we have $\card([w]_{\Cal{A}}) = s^{\ast} +2$ and $b_{i_0,j} \in [b_{s^{\ast},0}]_{\Cal{B}}$. Consequently, we have $i_0 = s^{\ast}$ and $(\exists s\leq i_0)(p(s) = 1)$.

We obtain that %\?
$$
	\roman{LPO}(p) = 1 \ \Longleftrightarrow\ (\exists s \leq i_0) (p(s) = 1).
$$
Therefore, by using $\theta$ and $p$, we can uniformly compute $\roman{LPO}(p)$.
This shows that $\roman{LPO} \leq_{W} \operatorname{SizePrEmb}_{\Cal{K}_{\leq 1}}$.
\qed\enddemo

\proclaim{Proposition 3.9}
$\operatorname{SizePrEmb}_{\Cal{K}_{\leq 1}} \leq_{W}\roman{LPO}$.
\endproclaim

\demo{Proof}
Let $\Cal{A}$ and $\Cal{B}$ be isomorphic structures from $\Cal{K}_{\leq 1}$. We construct a function $p_{(\Cal{A},\Cal{B})}\in\{0,1\}^\omega$ such that by using $\roman{LPO} (p_{(\Cal{A},\Cal{B})})$ and complete diagrams of $\Cal{A},\Cal{B}$, we can build (in a uniformly computable way) a size preserving embedding $\theta$ from $\Cal{A}$ into $\Cal{B}$.
We describe the construction of $p = p_{(\Cal{A},\Cal{B})}$.

At a stage $s$, by using the complete diagram of $\Cal{A}$, we find the finite set
$$
	F^s = \{ a\leq s : \operatorname{card}([a]_{\Cal{A}}) \leq s+1 \}.
$$
If $F^s$ is empty, then put $p(s) = 0$. Otherwise, set $p(s) = 1$.

If $p(s)=0$ for all $s$, then $\Cal{A}$ and $\Cal{B}$ contain only infinite equivalence classes.
In this case, similarly to %\?
\Par*{Proposition~3.6}, we can map the equivalence classes of $\Cal{A}$ to the equivalence classes of $\Cal{B}$ in a uniform way.
If~$\exists s (p(s)=1)$, then $\Cal{A}$ contains only one finite class. In this case we can find the size of this finite class (by searching through the complete diagram of $\Cal{A}$).
Similarly to %\?
\Par*{Proposition~3.6}, we recover a size preserving embedding $\theta \colon \Cal{A} \to \Cal{B}$.

Hence, using $\roman{LPO} (p_{(\Cal{A},\Cal{B})})$ and the compete diagrams of $\Cal{A},\Cal{B}$, we can uniformly construct an elementary embedding from $\Cal{A}$ into $\Cal{B}$. Therefore, $\operatorname{SizePrEmb}_{\Cal{K}_{\leq 1}}\leq_W \roman{LPO}$.
\qed\enddemo

By \Par{Proposition 3.8}{Propositions~3.8} and \Par{Proposition 3.9}{3.9}, we have the following:
$$
	\operatorname{SizePrEmb}_{\Cal{K}_{\leq 1}} =\operatorname{ElEm}_{\Cal{K}_{\leq 1}}(\roman{prime},\roman{any}) = \operatorname{ElEm}_{\Cal{K}_{\leq 1}}(\roman{any},\roman{sat})\equiv_W\roman{LPO}.
$$
This concludes the proof of \Par*{Theorem~3.7}.
\qed\enddemo

The third result of this section considers another subclass $\Cal{K}_{=2} \subset \Cal{K}_{fin}$.

\proclaim{Theorem 3.10}
	Let $\Cal{K}_{=2}$ %\?
be the class of all countable equivalence structures $\Cal{E}$ such that $\Cal{E}$ has exactly two equivalence classes and at most one finite class. Then we have
	$$
		\operatorname{ElEm}_{\Cal{K}_{=2}}(\roman{prime},\roman{any}) = \operatorname{ElEm}_{\Cal{K}_{= 2}}(\roman{any},\roman{sat}) \equiv_{W} \roman{LLPO}.
	$$
\endproclaim

\demo{Proof}
The same argument as in the proof of \Par*{Theorem~3.3} implies that
$$
	 \operatorname{SizePrEmb}_{\Cal{K}_{=2}}=\operatorname{ElEm}_{\Cal{K}_{=2}}(\roman{prime},\roman{any}) = \operatorname{ElEm}_{\Cal{K}_{=2}}(\roman{any},\roman{sat}).
$$
\enddemo

 We show that $\operatorname{SizePrEmb}_{\Cal{K}_{=2}} \equiv_{W} \roman{LLPO}$ in
 \Par{Proposition 3.11}{Propositions~3.11} and~\Par{Proposition 3.12}{3.12}.

\proclaim{Proposition 3.11}
$\roman{LLPO} \leq_{W} \operatorname{SizePrEmb}_{\Cal{K}_{=2}}$.
\endproclaim

\demo{Proof}
Fix functions $p_0,p_1\in\{0,1\}^\omega$ such that $(p_0=\widehat{0}\vee p_1=\widehat{0})$.
For these $p_0$ and $p_1$ we construct equivalence structures $\Cal{A}$ and $\Cal{B}$.

The domain of the structure $\Cal{A}$ will be equal to $\{ a_{i} : i\in\omega\} \cup \{ c_j : j\in\omega\}$. The domain of $\Cal{B}$ will be equal to $\{ b_{i} : i\in\omega \}\cup\{ d_j : j\in\omega\}$. Beforehand, we declare that $a_0\notin [c_0]_{\Cal{A}}$ and $b_0 \notin [d_0]_{\Cal{B}}$.

At a stage $s$ of the construction we build equivalence structures $\Cal{A}_s$ and $\Cal{B}_s$. Along the construction, we could declare that the classes $[a_0]_{\Cal{A}}$, $[c_0]_{\Cal{A}}$, $[b_0]_{\Cal{B}}$, and $[d_0]_{\Cal{B}}$  become {\it finished}.

At stage $0$ we put $\Cal{A}_0 =\{a_0,c_0\}$ and $\Cal{B}_0 = \{b_0,d_0\}$.

{\sc Stage $s+1$.}
If one of the classes $[a_0]_{\Cal{A}}$, $[c_0]_{\Cal{A}}$, $[b_0]_{\Cal{B}}$, $[d_0]_{\Cal{B}}$ is already finished, then we do nothing: i.e., we put $\Cal{A}_{s+1} = \Cal{A}_s$ and $\Cal{B}_{s+1} = \Cal{B}_s$.

Suppose that none of the classes is finished. Firstly, we add $a_{s+1}$, $c_{s+1}$, $b_{s+1}$, and $d_{s+1}$ to the classes $[a_0]_{\Cal{A}}$, $[c_0]_{\Cal{A}}$, $[b_0]_{\Cal{B}}$, and $[d_0]_{\Cal{B}}$ respectively.

If $p_0(t)=p_1(t)=0$ for all $t\leq s$, then we do nothing: i.e., we put $\Cal{A}_{s+1} = \Cal{A}_s\cup\{a_{s+1},c_{s+1}\}$ and $\Cal{B}_{s+1} = \Cal{B}_s\cup\{b_{s+1},d_{s+1}\}$.

If $s$ is the least number such that $p_1(s)=1$, then we declare that the classes $[c_0]_{\Cal{A}}$ and $[d_0]_{\Cal{B}}$ are finished. In this case we have $\card([c_0]_{\Cal{A}}) = \card([d_0]_{\Cal{B}})=s+2$. Then we put:

\Item $\smallbullet$
$[a_0]_{\Cal{A}}=\{a_i: i\in\omega\}\cup\{c_j: j> s+1\}$,

\Item $\smallbullet$
$[b_0]_{\Cal{B}}=\{b_i: i\in\omega\}\cup\{d_j: j> s+1\}$.

If $s$ is the least number such that $p_0(s)=1$, then we declare that classes $[a_0]_{\Cal{A}}$ and $[d_0]_{\Cal{B}}$ are finished. In this case we have $\card([a_0]_{\Cal{A}}) = \card([d_0]_{\Cal{B}})=s+2$. Then we put:

\Item $\smallbullet$
$[c_0]_{\Cal{A}}=\{c_i: i\in\omega\}\cup\{a_j: j> s+1\}$,

\Item $\smallbullet$
$[b_0]_{\Cal{B}}=\{b_i: i\in\omega\}\cup\{d_j: j> s+1\}$.

This concludes the description of the construction. We define $\Cal{A} = \bigcup_{s\in\omega} \Cal{A}_s$ and $\Cal{B} = \bigcup_{s\in\omega} \Cal{B}_s$. Note that the constructed structures $\Cal{A}$ and $\Cal{B}$ are $p$-computable.

Note that each of the structures $\Cal{A}$ and $\Cal{B}$ has exactly two equivalence classes. Furthermore, $\Cal{A} \cong \Cal{B} \in \Cal{K}_{= 2}$.

We show that $\Cal{A}$ and $\Cal{B}$ are $p$-decidable, uniformly in $p$. For all $n\geq 1$ and $k\geq 2$ we have $(n,k)\notin\chi(\Cal{A})$. A pair $(n,1)$, where $n\geq 1$, belongs to $\chi(\Cal{A})$ if and only if one of the classes $[a_0]_{\Cal{A}}$ or $[c_0]_{\Cal{A}}$  becomes finished by the end of stage $n$, and we have $\card([a_0]_{\Cal{A}_n}) = n$ or $\card([c_0]_{\Cal{A}_n}) = n$ respectively. Therefore, the character $\chi(\Cal{A}) =\chi(\Cal{B})$ is $p$-computable, uniformly in $p$.

We have $\card([a_0]_{\Cal{A}}) \geq k$ if and only if $\card([a_0]_{\Cal{A}_k}) \geq k$. Every element $a_t$ satisfies the following: either $a_t \in [a_0]_{\Cal{A}_{t+1}}$, or at the stage $t+1$ we have already declared that the class $[a_t]_{\Cal{A}}$ is infinite. The same argument is true for $\card([c_0]_{\Cal{A}})$ and the elements from $\{c_j: j\in\omega\}$. Therefore, the set $K(\Cal{A})$ from equation \Tag(2)  is $p$-computable, uniformly in $p$. A similar argument shows that $K(\Cal{B})$ is also (uniformly) $p$-computable. By a relativized version of \Par*{Theorem~3.2}, we deduce that $\Cal{A}$ and $\Cal{B}$ are $p$-decidable, uniformly in $p$.

Finally, let $\theta$ be an arbitrary size preserving embedding from $\Cal{A}$ into $\Cal{B}$.

Note that the class $[b_0]_{\Cal{B}}$ is always infinite. The value $\theta(a_0)$ satisfies one of the following two cases:

{\sc Case~1.}
Suppose that $\theta(a_0) = b_j$ for some $j\in\omega$. Then $\theta(a_0) \in [b_0]_{\Cal{B}}$, and this implies that the class $[a_0]_{\Cal{A}}$ is infinite. Hence, $[a_0]_{\Cal{A}}$ is never declared finished, and $p_0 = \widehat{0}$. Thus, $0$ is a solution of $\roman{LLPO}(p_0,p_1)$.

{\sc Case~2.}
Otherwise, $\theta(a_0) = d_j$ for some $j\in\omega$. Then we check whether there exists $t\leq j$ such that $1\in \{p_0(t), p_1(t)\}$.

Assume that such $t$ exists. If $p_0(t) = 1$, then $p_1 = \widehat{0}$ and $1$ is a unique solution of $\roman{LLPO}(p_0,p_1)$. If $p_1(t) = 1$, then $0$ is a unique solution of $\roman{LLPO}(p_0,p_1)$.

If there is no such $t\leq j$, then the element $\theta(a_0) = d_j$ belongs to $[d_0]_{\Cal{B}}$. Then we have $\theta(c_0) \in [b_0]_{\Cal{B}}$, and thus, the class $[c_0]_{\Cal{A}}$ is infinite. Hence, $[c_0]_{\Cal{A}}$ is never declared finished, and $p_1 = \widehat{0}$. Therefore, $1$ is a~solution of $\roman{LLPO}(p_0,p_1)$.

We conclude that by using $\theta$, $p_0$, and $p_1$, we can uniformly compute a solution of $\roman{LLPO}(p_0,p_1)$.
This shows that $\roman{LLPO} \leq_{W} \operatorname{SizePrEmb}_{\Cal{K}_{= 2}}$.
\qed\enddemo

\proclaim{Proposition 3.12}
$ \operatorname{SizePrEmb}_{\Cal{K}_{=2}}\leq_{W}\roman{LLPO} $.
\endproclaim

\demo{Proof}
Let $\Cal{A}$ and $\Cal{B}$ be isomorphic structures from $\Cal{K}_{= 2}$. We construct functions $p_{0,(\Cal{A},\Cal{B})}\in\{0,1\}^\omega$ and $p_{1,(\Cal{A},\Cal{B})}\in\{0,1\}^\omega$ such that by using $\roman{LLPO} (p_{0,(\Cal{A},\Cal{B})},p_{1,(\Cal{A},\Cal{B})})$ and complete diagrams of $\Cal{A},\Cal{B}$, we can build (in a uniformly computable way) a size preserving embedding $\theta$ from $\Cal{A}$ into $\Cal{B}$. We describe the construction of $p_0 = p_{0,(\Cal{A},\Cal{B})}$ and $p_1 = p_{1,(\Cal{A},\Cal{B})}$.

First, by searching through the atomic diagrams of $\Cal{A}$ and $\Cal{B}$, we find elements $a_0,c_0\in\Cal{A}$ and $b_0,d_0\in\Cal{B}$ such that $[a_0]_{\Cal{A}} \neq [c_0]_{\Cal{A}}$ and $[b_0]_{\Cal{B}} \neq [d_0]_{\Cal{B}}$.

By using the complete diagrams of $\Cal{A}$ and $\Cal{B}$, we define the functions $p_0$ and $p_1$ as follows:
$$
\align
	p_0(s) &=  \cases
          1, \text{ if } \card([a_0]_{\Cal{A}})=s+1\text{ and }\card([b_0]_{\Cal{B}})>s+1,
           \\
           1,\text{ if }\card([a_0]_{\Cal{A}})>s+1\text{ and }\card([b_0]_{\Cal{B}})=s+1,
           \\
          0, %\?,
          \text{ otherwise}.
         \endcases
         \\
	p_1(s) &=  \cases
          1, \text{ if } \card([a_0]_{\Cal{A}})=\card([b_0]_{\Cal{B}})=s+1,
          \\
          1, \text{ if } \card([c_0]_{\Cal{A}})=\card([d_0]_{\Cal{B}})=s+1,
          \\
          0, %\?,
          \text{ otherwise}.
          \endcases
\endalign
$$
Note the following: if $p_1(s) = 1$ for some $s\in\omega$, then $\card([a_0]_{\Cal{A}}) = \card([b_0]_{\Cal{B}}) \in \{ s+1, \omega\}$. Therefore, if $p_1 \neq \widehat{0}$, then $p_0 = \widehat{0}$. We deduce that the pair $(p_0,p_1)$ belongs to $\operatorname{dom}(\roman{LLPO})$.

If $0$ is a solution of $\roman{LLPO}(p_0,p_1)$, then the following two cases are possible. In the first case, the classes $[a_0]_{\Cal{A}}$ and $[b_0]_{\Cal{B}}$ are both infinite. In the second case, $[a_0]_{\Cal{A}}$ and $[b_0]_{\Cal{B}}$ are both finite and have the same size. So, in any of these two cases, one can build a size preserving embedding $\theta \colon \Cal{A} \to \Cal{B}$ by mapping $[a_0]_{\Cal{A}}$ to $[b_0]_{\Cal{B}}$ and $[c_0]_{\Cal{A}}$ to $[d_0]_{\Cal{B}}$.

If $1$ is a solution of $\roman{LLPO}(p_0,p_1)$, then the cardinalities of the classes $[a_0]_{\Cal{A}}$ and $[d_0]_{\Cal{B}}$ are the same. We build a size preserving embedding $\theta \colon \Cal{A} \to \Cal{B}$ by mapping $[a_0]_{\Cal{A}}$ to $[d_0]_{\Cal{B}}$ and $[c_0]_{\Cal{A}}$ to $[b_0]_{\Cal{B}}$.

Hence, using $\roman{LLPO} (p_0,p_1)$ and the complete diagrams of $\Cal{A},\Cal{B}$, we can uniformly construct an elementary embedding from $\Cal{A}$ into $\Cal{B}$. Therefore, $\operatorname{SizePrEmb}_{\Cal{K}_{= 2}}\leq_W \roman{LLPO}$.
\qed\enddemo

By \Par{Proposition 3.11}{Propositions~3.11} and~\Par{Proposition 3.12}{3.12},
we have $\operatorname{SizePrEmb}_{\Cal{K}_{=2}} \equiv_W\roman{LLPO}$.
\Par*{Theorem~3.10} is proved.
\qed\enddemo

\head
4. The Problem $\lim$ and Familiar Classes
\endhead

\specialhead
4.1. Linear orders
\endspecialhead

We refer to the monograph~[20] and to the survey~[21] for the background on countable linear orders.

For a linear order $\Cal{L} = (L,\leq)$, the {\it adjacency relation\/} $\operatorname{Adj}$ is defined as follows: $\operatorname{Adj}(x,y)$ holds if and only if
$$
	x < y \ \&\ \neg \exists z (x < z < y).
$$

The {\it block relation\/} $\operatorname{B\ell}$ is defined as follows: $\operatorname{B\ell}(x,y)$ holds if and only if there are only finitely many $z\in\Cal{L}$ satisfying $\min_{\Cal{L}}(x,y) \leq z \leq \max_{\Cal{L}}(x,y)$. If $\operatorname{B\ell}(x,y)$ is true, then we say that $x$ and $y$ belong to the same block (inside $\Cal{L}$).


A linear order $\Cal{L}$ is {\it discrete\/} if every $a \in \Cal{L}$ satisfies the following properties:

	\Item $\smallbullet$
If $a$ is not a greatest element of $\Cal{L}$, then $a$ has an immediate successor $b$ (that is, $b$ satisfying $\operatorname{Adj}(a,b)$).
	
	\Item $\smallbullet$
If $a$ is not a least element, then $a$ has an immediate predecessor $c$ (i.e., $c$ satisfying $\operatorname{Adj}(c,a)$).

\proclaim{Proposition 4.1 \rm (Langford~[22]; see also Theorem~2.12 of~[21])}
	A discrete linear order $\Cal{L}$ is decidable if and only if $\Cal{L}$ is computable and its adjacency relation $\operatorname{Adj}^{\Cal{L}}$ is also computable.
\endproclaim

We obtain the following result:

\proclaim{Theorem 4.2}
	For the class $\Bbb{DL}$ of all discrete linear orders, we have $\operatorname{ElEm}_{\Bbb{DL}}(\roman{any},\roman{sat}) \equiv_{sW} \lim$.
\endproclaim

\demo{Proof}
	By \Par*{Proposition~2.3} and \Par*{Theorem~2.1}, it is sufficient to prove that the problem $\operatorname{J}$ is strongly Weihrauch reducible to $\operatorname{ElEm}_{\Bbb{DL}}(\roman{any},\roman{sat})$.
	
	Note that it is known that for an arbitrary linear order $\tau$, the discrete order $\omega + \zeta \cdot \tau$ is elementarily equivalent to $\omega$ (Corollary~6.12 of~[20]).
	In addition, the order $\omega + \zeta \cdot \eta$ is a countable saturated model of the theory $\operatorname{Th}(\omega)$ (see, e.g., Exercise~13.84 in~[20]).
	
	We choose a linear order $\Cal{B}$ as a decidable copy of the order $\omega + \zeta \cdot \eta$ such that the block relation $\operatorname{B\ell}^{\Cal{B}}$ is computable.
	
	Given an instance $p\in\omega^{\omega}$ of the jump $\operatorname{J}$, we build a $p$-decidable linear order $\Cal{A}_p = \omega + \Cal{L}_p$ (where $\omega$ is chosen as a decidable linear order). The order $\Cal{L}_p$ will have order type $\zeta \cdot \omega$.
	
	{\sc Stage $0$.}
For each $i\in\omega$, add the following points into $\Cal{L}_p$:
	$$
		 \dots <_{\Cal{L}_p} u_{i,-2} <_{\Cal{L}_p} u_{i,-1} <_{\Cal{L}_p} c_i\ \ %\?
<_{\Cal{L}_p}\ \  %\?
d_i <_{\Cal{L}_p} v_{i,1} <_{\Cal{L}_p} v_{i,2} <_{\Cal{L}_p} \cdots .
	$$
	Our adjacency relation $\operatorname{Adj}$ inside $\Cal{L}_p$ will satisfy the following: for a nonzero $k\in\omega$, we have $\operatorname{Adj}(u_{i,-k-1}, u_{i,-k})$ and $\operatorname{Adj}(v_{i,k}, v_{i,k+1})$. In addition, we have $\operatorname{Adj}(u_{i,-1}, c_i)$ and $\operatorname{Adj}(d_i, v_1)$.
	
	We declare that (at the current stage) the set $\{ c_i\} \cup \{ u_{i,-k} : k\geq 1\}$ is the {\it intended block of\/} $c_i$, and $\{ d_i\} \cup \{ v_{i,k} : k\geq 1\}$ is the {\it intended block of\/} $d_i$. Along the construction, we could declare that the blocks of $c_i$ and $d_i$ are {\it finished}.
	
	Here we always assume that every element from the intended block of $d_i$ is strictly less than any element from the intended block of $c_{i'}$ for $i' > i$.
	
	{\sc Stage $s+1$.}
If the blocks of $c_i$ and $d_i$ are not finished yet, we add a fresh element $w$ as a new greatest element inside the intended block of $c_i$. We also add a fresh $w'$ as a new least element inside the intended block of $d_i$.
	
	If $\varphi_{i,s}^p(0){\uparrow}$, then we (explicitly) declare that $w$ and $w'$ are {\it not adjacent\/} inside $\Cal{L}_p$.
	
	If $s$ is the least stage such that $\varphi_{i,s}^p(0){\downarrow}$, then we declare that $w$ and $w'$ are adjacent. We also declare that the intended blocks of $c_i$ and $d_i$ are finished.
	
	This concludes the description of the construction. It is clear that the constructed order $\Cal{L}_p$ is computable in $p$. In addition, we have $\operatorname{Adj}^{\Cal{L}_p}(x,y)$ if and only if some stage $s\in\omega$ satisfies $\operatorname{Adj}^{\Cal{L}_{p,s}}(x,y)$, and the elements $x$ and $y$ have not been explicitly declared nonadjacent at this stage. This implies that the set $\operatorname{Adj}^{\Cal{L}_p}$ is $p$-computable, uniformly in $p$. By applying a relativized version of
\Par*{Proposition~4.1}, we deduce that the order $\Cal{A}_p = \omega + \Cal{L}_p$ is $p$-decidable, uniformly in $p$.
	
	Note the following key property of the construction: for $i\in\omega$, $\varphi_{i}^p(0){\downarrow}$ if and only if the elements $c_i$ and $d_i$ belong to the same block inside $\Cal{A}_p$.
	
	Let $\theta$ be an arbitrary elementary embedding from $\Cal{A}_p$ into $\Cal{B}$.

		\Item $\smallbullet$
If $\varphi_{i}^p(0){\downarrow}$, then we have $\operatorname{B\ell}^{\Cal{A}_p}(c_i, d_i)$ and $\operatorname{B\ell}^{\Cal{B}}(\theta(c_i), \theta(d_i))$.

		\Item $\smallbullet$
If $\varphi_{i}^p(0){\uparrow}$, then $\neg \operatorname{B\ell}^{\Cal{A}_p}(c_i, d_i)$ and $\neg \operatorname{B\ell}^{\Cal{B}}(\theta(c_i), \theta(d_i))$.

	Hence, information about the embedding $\theta$ allows us to compute $\operatorname{J}(p)$. We deduce that $\operatorname{J} \leq_{sW} \operatorname{ElEm}_{\Bbb{DL}}(\roman{any},\roman{sat})$. \Par*{Theorem~4.2} is proved.
\qed\enddemo

\proclaim{Corollary 4.3}
	The class of all linear orders $\Bbb{LO}$ satisfies $\operatorname{ElEm}_{\Bbb{LO}}(\roman{any},\roman{sat}) \equiv_{sW} \lim$.
\endproclaim

\specialhead
4.2. Boolean algebras
\endspecialhead

For the background on countable Boolean algebras, we refer to the monograph~[23]. Boolean algebras are viewed as structures in the signature $\sigma_{BA} = \{ \vee, \wedge, \operatorname{C}, 0, 1\}$. For a Boolean algebra $\Cal{B}$, its ordering $\leq_{\Cal{B}}$ is defined in a standard way: $a \leq_{\Cal{B}} b$ if and only if $a\vee b = b$.
If $\Cal{L}$ is a linear order with a least element, then by $\operatorname{Intalg}(\Cal{L})$ we denote the induced
{\it interval Boolean algebra}. This algebra contains all finite unions of intervals of the form
$$
	[a,b) = \{ x : a\leq_{\Cal{L}} x <_{\Cal{L}} b\} \ \text{ or }\ [a,\infty) = \{ x : a\leq_{\Cal{L}} x \},
\tag4
$$
where $a <_{\Cal{L}} b$ (see Section~1.6 of~[23] for further formal details).

Let $\Cal{B}$ be a Boolean algebra. An element $a\in\Cal{B}$ is an {\it atom\/} if $a$ is a minimal nonzero element (i.e., $a\neq 0_{\Cal{B}}$ and there are no $b$ satisfying $0_{\Cal{B}} \neq b <_{\Cal{B}} a$). By $\operatorname{Atom}(\Cal{B})$ we denote the set of atoms of $\Cal{B}$. The {\it Fr{\'e}chet ideal\/} $\operatorname{F}(\Cal{B})$ of the algebra $\Cal{B}$ contains all finite sums of atoms of $\Cal{B}$.

A Boolean algebra $\Cal{B}$ is {\it atomic\/} if for any $b\neq 0_{\Cal{B}}$, there exists an atom $a \leq_{\Cal{B}} b$.

We will use the following known fact concerning Boolean algebras:

\proclaim{Proposition 4.4 \rm (Corollary~3.5.2 in~[23])}
 	An atomic Boolean algebra $\Cal{B}$ is decidable if and only if the algebra $\Cal{B}$ is computable and its set of atoms $\operatorname{Atom}(\Cal{B})$ is also computable.
\endproclaim

We obtain the following result:

\proclaim{Theorem 4.5}
	The class $\Bbb{AB}$ of all atomic Boolean algebras satisfies $\operatorname{ElEm}_{\Bbb{AB}}(\roman{any},\roman{sat}) \equiv_{sW} \lim$.
\endproclaim

\demo{Proof}
	It is known that all infinite atomic Boolean algebras are elementarily equivalent (see, e.g., Theorem~2.3.3 in~[23]). In addition, the atomic algebra $\operatorname{Intalg}(1+\omega\cdot \eta)$ is a countable saturated model (Proposition~2.3.3 of~[23]). 	
	
	Beforehand, we choose a Boolean algebra $\Cal{C}$ as a decidable copy of the algebra $\operatorname{Intalg}(1+\omega\cdot \eta)$ such that its Fr{\'e}chet ideal $\operatorname{F}(\Cal{C})$ is a computable set.
	
	It is sufficient to prove that $\roman{J} \leq_{sW} \operatorname{ElEm}_{\Bbb{AB}}(\roman{any},\roman{sat})$. Given an instance $p\in\omega^{\omega}$ of the problem $\roman{J}$, we build a $p$-decidable atomic Boolean algebra $\Cal{B}_p$. The algebra $\Cal{B}_p$ is defined as the interval algebra $\operatorname{Intalg}(\Cal{L}_p)$, where $\Cal{L}_p$ is a $p$-computable linear order. We describe the construction of $\Cal{L}_p$.
	
	Firstly, we define an ancillary computable linear order $\Cal{M}$. The domain of $\Cal{M}$ equals $\{ a_{i,j} : i,j \in\omega\}$, and we have $a_{i,j} \leq_{\Cal{M}} a_{k,\ell}$  if and only if either $i <_{\Bbb{N}} k$ or ($i = k$ and $j \leq_{\Bbb{N}} \ell$). Note that the order $\Cal{M}$ is isomorphic to the ordinal $\omega^2$.
	
	The desired order $\Cal{L}_p$ will be built as a suborder of $\Cal{M}$. Along the construction, we also define an ancillary $p$-c.e.\ set $V \subseteq \omega \times \omega$.
	
	{\sc Stage $0$.}
We add the elements $a_{i,0}$, $i\in\omega$, into $\operatorname{dom}(\Cal{L}_p)$.
	
	{\sc Stage $s+1$.}
For each $i\in\omega$ we proceed as follows.
	
	If $\varphi^p_{i,s}(0){\uparrow}$, then add the element $a_{i,s+1}$ into $\operatorname{dom}(\Cal{L}_p)$.
	
	If $s$ is the least stage such that $\varphi^p_{i,s}(0){\downarrow}$, then we add the pair $(a_{i,s}, a_{i+1,0})$ into the set~$V$.
	
	This concludes the description of the construction. As usual, by using a $p$-computable bijection acting from $\omega$ onto $\operatorname{dom}(\Cal{L}_p)$, without loss of generality we may assume that $\operatorname{dom}(\Cal{L}_p) = \omega$ and that the order $\Cal{L}_p$ is $p$-computable.
	
	By applying the standard effective construction of an interval Boolean algebra (see Proposition~3.2.1 of~[23]),
we obtain that %\?
the algebra $\Cal{B}_p = \operatorname{Intalg}(\Cal{L}_p)$ is $p$-computable, uniformly in $p$.
	
	An interval $[a_{i,s},a_{j,t})$ (recall equation \Tag(4)) is an atom of the algebra $\Cal{B}_p$ if and only if one of the following conditions is satisfied:

		\Item $\smallbullet$
$j = i$, $t = s+1$, and the element $a_{i,s+1}$ has been added to $\Cal{L}_p$ at the stage $s+1$,
		
		\Item $\smallbullet$
$j = i+1$, $t = 0$, and the pair $(a_{i,s},a_{i+1,0})$ has been enumerated into $V$ as the stage $s+1$.

	This observation implies that the set $\operatorname{Atom}(\Cal{B}_p)$ is $p$-computable, uniformly in $p$.	
	In addition, every nonzero element $x$ from the algebra $\Cal{B}_p$ has an atom $y$ such that $y \leq_{\Cal{B}_p} x$.
	Hence, the algebra $\Cal{B}_p$ is atomic. By a relativized version of \Par*{Proposition~4.4}, we deduce that the structure $\Cal{B}_p$ is $p$-decidable, uniformly in~$p$.
	
	Let $\theta$ be an arbitrary elementary embedding from $\Cal{B}_p$ into $\Cal{C}$. Since the set of atoms is first-order definable, we have the following: for an arbitrary $x\in\Cal{B}_p$,
	$$
		\card(\{ y \in \operatorname{Atom}(\Cal{B}_p) : y \leq_{\Cal{B}_p} x\}) = \card(\{ z \in \operatorname{Atom}(\Cal{C}) : z \leq_{\Cal{C}} \theta(x)\}).
	$$
	Therefore, $x$ belongs to the Fr{\'e}chet ideal $\operatorname{F}(\Cal{B}_p)$ if and only if $\theta(x) \in \operatorname{F}(\Cal{C})$. We obtain the following:

		\Item $\smallbullet$
If $\varphi^p_{i}(0){\uparrow}$, then the element $x_i := [a_{i,0},a_{i+1,0})$ does not belong to $\operatorname{F}(\Cal{B}_p)$, and hence $\theta(x_i)\notin  \operatorname{F}(\Cal{C})$.
		
		\Item $\smallbullet$
If $\varphi^p_{i}(0){\downarrow}$, then choose the least stage $s^{\ast}$ such that $\varphi^p_{i,s^{\ast}}(0){\downarrow}$. The element $x_i = [a_{i,0},a_{i+1,0})$ is a sum of $(s^{\ast}+1)$-many atoms, and hence $\theta(x_i) \in \operatorname{F}(\Cal{C})$.

	Recall that the set $\operatorname{F}(\Cal{C})$ is computable. Therefore, information about the embedding $\theta$ allows us to compute $\operatorname{J}(p)$. We conclude that $\operatorname{J} \leq_{sW} \operatorname{ElEm}_{\Bbb{AB}}(\roman{any},\roman{sat})$.
\Par*{Theorem~4.5} is proved.
\qed\enddemo

\proclaim{Corollary 4.6}
	The class of all Boolean algebras $\Bbb{BA}$ satisfies $\operatorname{ElEm}_{\Bbb{BA}}(\roman{any},\roman{sat}) \equiv_{sW} \lim$.
\endproclaim

\specialhead
4.3. Abelian groups
\endspecialhead

For the background on computable abelian groups, we refer to the surveys~[24] and~[25]. Abelian groups are viewed as structures in the signature $\sigma_{AG} = \{ +, 0\}$.
By $\Bbb{P}$ we denote the set of all prime numbers. Here $\Bbb{Q}$ denotes the abelian group of rationals.

Let $\Cal{A}$ be an abelian group. For a nonzero $N\in\omega$ and $x\in \Cal{A}$, we write $(N\mid x)$ iff
$$
	\Cal{A} \models \exists y (Ny = x).
$$
An abelian group $\Cal{A}$ is {\it divisible\/} if $(N\mid x)$ for all $x\in \Cal{A}$ and all $N\geq 1$. For example, the group of rationals $\Bbb{Q}$ is divisible.

Let $x$ be a nonzero element of $\Cal{A}$. The {\it order of\/} $x$, denoted by $\operatorname{ord}(x)$, is defined as follows. If there exists $n\in\omega\setminus\{ 0\}$ such that $nx=0$, then $\operatorname{ord}(x)$ is equal to the least such $n$. Otherwise, $\operatorname{ord}(x) = \infty$.

An abelian group $\Cal{A}$ is {\it torsion-free\/} if every nonzero element $x\in\Cal{A}$ has infinite order.

We will use the following known result (see, e.g., Proposition~1.1 in~[24] and Theorem~3.3 in~[25]).

\proclaim{Proposition 4.7 \rm [26]}
	Let $\Cal{A}$ be a computable abelian group. The group $\Cal{A}$ is decidable if and only if its theory $\operatorname{Th}(\Cal{A})$ is decidable and the unary predicates $(q^k \mid \cdot)$, where $q\in\Bbb{P}$ and $k\geq 1$, are uniformly computable.
\endproclaim

We also need the following folklore fact:

\proclaim{Lemma 4.8 \rm (folklore)}
	{\rm (a)}
The theory $\operatorname{Th}(\Bbb{Q})$ is decidable {\rm(}see, e.g., Corollary~{\rm1.2} of~{\rm[24])}.
	
	{\rm (b)}
For each nonzero $\beta \leq \omega$, the direct sum $\bigoplus_{i <\beta} \Bbb{Q}$ is elementarily equivalent to the group $\Bbb{Q}$.
{\rm(}This fact follows, e.g., from a direct analysis of the Szmielew invariants~{\rm[27]},
see Section~{\rm7.1} of~{\rm[24]} or Theorem~{\rm2.9} of~{\rm[28].)}
\endproclaim

We obtain the following theorem:

\proclaim{Theorem 4.9}
	The class $\Bbb{TF}$ of all torsion-free abelian groups satisfies $\operatorname{ElEm}_{\Bbb{TF}}(\roman{any},\roman{sat}) \equiv_{sW} \lim$.
\endproclaim

\demo{Proof}
	Consider the countable direct sum $\Cal{U} := \bigoplus_{i<\omega} \Bbb{Q}$. It is known that $\Cal{U}$ is a countable saturated model of the theory $\operatorname{Th}(\Bbb{Q})$ (see, e.g., Section~3 of~[28]).
	
	Suppose that $g_0,g_1,\dots,g_n$ are elements from $\Cal{U}$. As usual, we say that the elements $g_0,g_1,\dots,g_n$ are
{\it linearly independent\/} if for arbitrary $c_0,c_1,\dots,c_n \in\Bbb{Z}$, the equality $c_0g_0 + c_1 g_1 + \dots + c_n g_n = 0$ implies that $c_0 = c_1 = \dots = c_n = 0$.
	
	We say that a computable group $\Cal{A} \cong \Cal{U}$ has an {\it algorithm for linear independence\/} if given an arbitrary tuple $\bar{g} = g_0,g_1,\dots, g_n$ from $\Cal{A}$ one can computably check (uniformly in $\bar{g}$) whether $\bar{g}$ is linearly independent in $\Cal{A}$.
	
	Beforehand, we fix a decidable copy $\Cal{C}$ of $\Cal{U}$ that has an algorithm for linear independence.
		
	We prove that $\roman{J} \leq_{sW} \operatorname{ElEm}_{\Bbb{TF}}(\roman{any},\roman{sat})$. We fix an instance $p\in\omega^{\omega}$ of the problem $\roman{J}$.
	
	Since $\operatorname{Th}(\Bbb{Q})$ is decidable and the group $\Cal{U}$ is divisible, a relativized version of
\Par*{Proposition~4.7} implies that every $p$-computable copy of $\Cal{U}$ is also $p$-decidable. Thus, we describe a~uniform construction of a~$p$-computable group $\Cal{A}_p$ that is isomorphic to $\Cal{U}$.
	
	We fix two ancillary computable groups: $\Cal{G}^1$ that is isomorphic to $\Bbb{Q}$, and $\Cal{G}^2$ that is isomorphic to $\Bbb{Q} \oplus \Bbb{Q}$. We assume that $\operatorname{dom}(\Cal{G}^1) = \operatorname{dom}(\Cal{G}^2) = \omega$.
	
	 For $i\in\{ 1, 2\}$, we also fix a computable sequence of finite partial groups $(\Cal{G}^{i}_{s})_{s\in\omega}$ such that $\Cal{G}^{i}_{s} \subseteq \Cal{G}^{i}_{s+1}$ for all $s$, and $\bigcup_{s\in\omega} \Cal{G}^{i}_{s} = \Cal{G}^i$. Here the term ``partial group'' means the following: the operation $+_{\Cal{G}^{i}_{s}}$ is defined only on some subset of $\operatorname{dom}(\Cal{G}^{i}_{s}) \times \operatorname{dom}(\Cal{G}^{i}_{s})$.
	
	 We choose two elements $c$ and $d$ from $\Cal{G}^2$ such that $c,d$ are linearly independent. We may assume that $c,d \in \Cal{G}^{2}_{0}$.
	
	The desired group $\Cal{A}_p$ is built as a countable direct sum $\bigoplus_{i<\omega} \Cal{B}_i$. For each $i\in\omega$, the domain of $\Cal{B}_i$ will be equal to $\{i\} \times \omega = \{ (i,x) : x\in\omega\}$.
	
	{\sc Stage $0$.}
For each $i\in\omega$, we define the finite partial group $\Cal{B}_{i,0}$ as an isomorphic copy of $\Cal{G}^{2}_{0}$: that is, the map $x \mapsto ( i,x )$ induces an isomorphism from $\Cal{G}^{2}_{0}$ onto $\Cal{B}_{i,0}$.
	
	{\sc Stage $s+1$.}
For each $i\in\omega$ we proceed as follows.
	
	If $\varphi_{i,s}^p(0){\uparrow}$, then we extend $\Cal{B}_{i,s} \cong \Cal{G}^{2}_{s}$ to a finite structure $\Cal{B}_{i,s+1}$ that is isomorphic to $\Cal{G}^{2}_{s+1}$.
	
	Suppose that $s$ is the least stage such that $\varphi_{i,s}^p(0){\downarrow}$. Since the groups $\Cal{G}^2 \cong\Bbb{Q}\oplus \Bbb{Q}$ and $\Cal{G}^1 \cong\Bbb{Q}$ are elementarily equivalent (by \Par*{Lemma~4.8}\itm(b)), there exists a finite partial subgroup $\Cal{D} \subseteq \Cal{G}^1$ such that $\Cal{D}$ is isomorphic to $\Cal{B}_{i,s} \cong \Cal{G}^{2}_{s}$. Therefore, one can find (effectively in $p$) an isomorphic embedding $\psi \colon \Cal{B}_{i,s} \hookrightarrow \Cal{G}^1$. We declare that the group $\Cal{B}_i$ is finished and that $\Cal{B}_i$ is isomorphic to $\Cal{G}^1$. More formally, we extend the finite map $\psi$ to a bijection $\widehat{\psi}\supseteq \psi$ that maps $\{i \} \times \omega$ onto $\omega$, and for $x,y\in \Cal{B}_i$, we put
	$$
		x+_{\Cal{B}_i}y = \widehat{\psi}^{-1} (\widehat{\psi}(x) +_{\Cal{G}^1} \widehat{\psi}(y)).
	$$
	
	This concludes the description of the construction. Observe that the group $\Cal{A}_p = \bigoplus_{i<\omega} \Cal{B}_i$ is isomorphic to $\Cal{C} \cong \bigoplus_{i<\omega} \Bbb{Q}$. In addition, the construction of $\Cal{A}_p$ is $p$-computable, uniformly in $p$.
	
	Let $\theta$ be an arbitrary elementary embedding from $\Cal{A}_p$ into the decidable group $\Cal{C}$.

		\Item $\smallbullet$
If $\varphi_{i}^p(0){\uparrow}$, then the group $\Cal{B}_i$ is isomorphic to $\Cal{G}^2$, and the elements $(i,c)$ and $(i,d)$ from $\Cal{B}_i$ are linearly independent. Since the embedding $\theta$ is elementary, the elements $\theta(i,c)$ and $\theta(i,d)$ must be also linearly independent.
		
		\Item $\smallbullet$
If $\varphi_{i}^p(0){\downarrow}$, then $\Cal{B}_i \cong \Cal{G}^1$, and the elements $(i,c)$ and $(i,d)$ are linearly dependent. Then $\theta(i,c)$ and $\theta(i,d)$ are also linearly dependent.

	Recall that the group $\Cal{C}$ has an algorithm for linear independence. This implies that by using information about $\theta$, we can compute $\operatorname{J}(p)$. We conclude that  $\operatorname{J} \leq_{sW} \operatorname{ElEm}_{\Bbb{TF}}(\roman{any},\roman{sat})$.
	\Par*{Theorem~4.9} is proved.
\qed\enddemo

\proclaim{Corollary 4.10}
	The class of all abelian groups $\Bbb{AG}$ satisfies $\operatorname{ElEm}_{\Bbb{AG}}(\roman{any},\roman{sat}) \equiv_{sW} \lim$.
\endproclaim

\Refs

\ref\no 1
 \by                  Simpson S.G.
 \book                Subsystems of Second Order Arithmetic
 \bookinfo            Second edition
 \publ                Cambridge University
 \publaddr            Cambridge
 \yr                  2009
\finalinfo            Perspect. Log.
\endref

\ref\no 2
 \by                  Hirschfeldt D.R.
 \book                Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles
 \publ                World Sci.
 \publaddr            Hackensack
 \yr                  2015
\finalinfo            Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap.,~28
\endref

\ref\no 3
\by                   Hirschfeldt D.R., Shore R.A., and Slaman T.A.
\paper                The atomic model theorem and type omitting
\jour                 Trans. Amer. Math. Soc.
\yr                   2009
\vol                  361
\issue                11
\pages                5805--5837
\endref

\ref\no 4
\by                   Belanger D.R.
\paper                $WKL_0$ and induction principles in model theory
\jour                 Ann. Pure Appl. Logic
\yr                   2015
\vol                  166
\iftex
\issue                7--8
\else
\issue                7
\fi
\pages                767--799
\endref

\ref\no 5
\by                   Cholak P. and McCoy C.
\paper                Effective prime uniqueness
\jour                 Proc. Amer. Math. Soc.
\yr                   2017
\vol                  145
\issue                12
\pages                5363--5379
\endref

\ref\no 6
\by                   Hirschfeldt D.R., Lange K., and  Shore R.A.
\paper                Induction, bounding, weak combinatorial principles, and the homogeneous model theorem
\jour                 Mem. Amer. Math. Soc.
\yr                   2017
\vol                  1187
%\issue               -
\pages                1--114
\endref

\ref\no 7
 \by             Weihrauch K.
 \book           The Degrees of Discontinuity of Some Translators Between Representations of the Real Numbers
 \bookinfo       Technical Report, TR-92-050
 \publ           International Computer Science Institute
 \publaddr       Berkeley
  \yr            1992
\endref

\ref\no 8
 \by             Weihrauch K.
 \book           The TTE-Interpretation of Three Hierarchies of Omniscience Principles
 \bookinfo       Informatik Berichte 130
 \publ           FernUniversit{\"a}t Hagen
 \publaddr       Hagen
  \yr            1992
\endref

\ref\no 9
\by              Brattka V., Gherardi G., and Pauly~A.
\paper           Weihrauch complexity in computable analysis
\inbook          Handbook of Computability and Complexity in Analysis
\publaddr        Cham
\publ            Springer
\yr              2021
\pages           367--417
\finalinfo       Theory Appl. Comput.
\endref
%doi={10.1007/978-3-030-59234-9_11}

\ref\no 10
\by              Brattka V.
\paper           Weihrauch complexity and the Hagen school of computable analysis
\inbook          60 Jahre DVMLG
\publaddr        London
\publ            College Publications %\?
\yr              2022
\pages           13--44
\finalinfo       Tributes, 48 %\?
\endref

\ref\no 11
\by              Bazhenov~N.A., Marchuk M.I., and Fiori-Carones M.
\paper           Weihrauch degrees of elementary embeddings for prime and saturated models
\jour            Lobachevskii J. Math.
\yr              2025
\vol             46
\issue           12
\pages           6081--6093
\endref
%	doi = {10.1134/S1995080225613839}

\ref\no 12
 \by             Chang~C.C. and Keisler~H.J.
 \book           Model Theory
 \publ           North-Holland
 \publaddr       Amsterdam and London
 \yr             1973
\finalinfo       Stud. Logic Found. Math.,  73
\endref

\ref\no 13
\by                Ershov Yu.L. and Goncharov  S.S. %Goncharov~S.S. and   Ershov~Yu.L.
      \book        Constructive Models
      \publaddr    New York, etc.
      \publ        Kluwer Academic/Plenum
      \yr          2000
     \finalinfo    Siberian School of Algebra Logic
\endref

\ref\no 14
 \by               Harizanov V.S.
 \paper            Pure computable model theory
 \inbook             Handbook of Recursive Mathematics. Vol.~1
 \publ             North-Holland %Elsevier
 \publaddr         Amsterdam
 \yr               1998
 \pages            3--114
\finalinfo         Stud. Logic Found. Math., 138
\endref
%	Doi = {10.1016/S0049-237X(98)80002-5}

\ref\no 15
 \by               Odifreddi P.
 \book             Classical Recursion Theory
 \bookinfo         The Theory of Functions and Sets of Natural Numbers
 \publ             North-Holland %Elsevier
 \publaddr         Amsterdam
 \yr               1992
\finalinfo         Stud. Logic Found. Math., 125
\endref

\ref\no 16
\by                Dorais F.G., Dzhafarov D.D.,  Hirst J.L., Mileti J.R., and Shafer~P.
\paper             On uniform relationships between combinatorial problems
\jour              Trans. Amer. Math. Soc.
\yr                2016
\vol               368
\issue             2
\pages             1321--1359
\endref
%	doi = {10.1090/tran/6465},

\ref\no 17
\by                   Brattka V. and Gherardi G.
\paper                Weihrauch degrees, omniscience principles and weak computability
\jour                 J.~Symbolic Logic
\yr                   2011
\vol                  76
\issue                1
\pages                143--176
\endref

\ref\no 18
\by                   Brattka V., de Brecht M., and Pauly A.
\paper                Closed choice and a uniform low basis theorem
\jour                 Ann. Pure Appl. Logic
\yr                   2012
\vol                  163
\issue                8
\pages                986--1008
\endref

\ref\no 19
\by                Cenzer D.,  Harizanov V., and  Remmel J.B.
\paper             $\Sigma^0_1$ and $\Pi^0_1$ equivalence structures
\jour              Ann. Pure Appl. Logic
\yr                2011
\vol               162
\issue             7
\pages             490--503
\endref
%	doi = {10.1016/j.apal.2011.01.002}

\ref\no 20
\by           Rosenstein~J.G.
\book         Linear Orderings
\publ         Academic
\publaddr     New York and London
\yr           1982
\finalinfo    Pure Appl. Math., 98
\endref

\ref\no 21
\by               Downey R.G.
\paper            Computability theory and linear orderings
\inbook           Handbook of Recursive Mathematics. Vol.~2
\publaddr         Amsterdam
\publ             North-Holland %Elsevier
\yr               1998
\pages            823--976
\finalinfo        Stud. Logic Found. Math., 139
\endref

\ref\no 22
\by               Langford C.H.
\paper            Some theorems on deducibility
\jour             Ann. of Math. (2)
\iftex
\yr               1926, 1927
\else
\yr               1926
\fi
\vol              28
\iftex
\issue            1--4
\else
\issue            1
\fi
\pages            16--40
\endref
%	doi = {10.2307/1968352}

\ref\no 23
\by               Goncharov~S.S.
      \book       Countable Boolean Algebras and Decidability
      \publ       Consultants Bureau
      \publaddr   New York
     \yr          1997
     \finalinfo   Siberian School Algebra Logic
\endref

\ref\no 24
\by               Khisamiev~N.G.
\paper            Constructive abelian groups
\inbook           Handbook of Recursive Mathematics. Vol.~2
\publaddr         Amsterdam
\publ             North-Holland %Elsevier
\yr               1998
\pages            1177--1231
\finalinfo        Stud. Logic Found. Math., 139
\endref

\ref\no 25
\by                 Melnikov A.G.
\paper              Computable abelian groups
\jour               Bull. Symb. Log.
\yr                 2014
\vol                20
\issue              3
\pages              315--356
\endref
%	doi = {10.1017/bsl.2014.32}

\ref\no 26
 \by       Ershov~Yu.L.
 \book     Decision Problems and Constructive Models
 \publ     Nauka
 \publaddr Moscow
 \yr       1980
  \lang    Russian
\endref

\ref\no 27
\by               Szmielew~W.
\paper            Elementary properties of Abelian groups
\jour             Fund. Math.
\yr               1955
\vol              41
\issue            2
\pages            203--271
\endref

\ref\no 28
\by               Eklof P.C. and Fischer~E.R.
\paper            The elementary theory of abelian groups
\jour             Ann. Math. Logic
\yr               1972
\vol              4
\issue            2
\pages            115--171
\endref
%	doi = {10.1016/0003-4843(72)90013-7}
\endRefs

\enddocument