1. Introduction
This paper is concerned with the notion of completeness of numberings introduced by Mal’cev (Reference Mal’cev1963) and its relativizations. A numbering
$\nu$
of a set
$S$
(i.e., an arbitrary surjective mapping of the set of all non-negative integers
$\mathbb N$
onto
$S$
) is said to be complete with respect to
$X\in S$
if for every partial recursive function
$\psi$
there exists a recursive
$h$
such that
\begin{equation} \nu (h(x))= \begin{cases} \nu (\psi (x)), & \mbox{if}\ \psi (x)\downarrow ,\\ X, & \mbox{if}\ \psi (x)\uparrow , \end{cases} \end{equation}
for each
$x$
. If for every partial recursive function
$\psi$
there exists a recursive
$h$
satisfying (1) for each
$x$
, then
$X$
is called a special object of the numbering
$\nu$
. We say that a numbering is complete if it has a special object.
The proofs of Kleene’s recursion theorem, Rice’s theorem, the infinite padding property, and many other well-known results in recursion theory rely on the completeness with respect to
$\varnothing$
of the standard Gödel numberings
$x\mapsto W_x$
and
$x\mapsto \varphi _x$
of the families of all r.e. sets and partial recursive functions, respectively. Therefore, any complete numbering satisfies each of these theorems. In addition, complete numberings find applications in control structures theory (Jain and Nessel Reference Jain and Nessel2001), computable analysis (Selivanov Reference Selivanov, De Mol, Weiermann, Manea and Fernández-Duque2021a), and other areas of computability (cf., e.g., Ershov Reference Ershov1969a; Faizrahmanov Reference Faizrahmanov2023a; Terwijn Reference Terwijn2024), and they make it possible to combine important results in recursion theory due to Muchnik (Reference Muchnik1963), Myhill (Reference Myhill1955), Rogers (Reference Rogers1958), and Smullyan (Reference Smullyan1961), which previously seemed unrelated to each other.
A weaker property than the completeness of numberings is the property of their precompleteness introduced by Ershov (Reference Ershov1970, Reference Ershov1973). He called a numbering
$\nu$
precomplete if for every partial recursive function
$\psi$
there exists a recursive
$h$
such that
\begin{equation} \psi (x)\downarrow \Rightarrow \nu (h(x))=\nu (\psi (x)) \end{equation}
for each
$x$
. The precomplete numberings can be characterized by the following theorem.
Theorem 1 (Ershov’s recursion theorem (Ershov Reference Ershov1977)). A numbering
$\nu$
is precomplete if and only if for every binary partial recursive function
$\psi$
there exists a recursive function
$h$
such that
$\nu (\psi (x,h(x)))=\nu (h(x))$
for each
$x$
with
$\psi (x, h(x))\downarrow$
.
Even though not every precomplete numbering is complete, precomplete numberings still have many properties of complete numberings. Ershov’s recursion theorem implies that they satisfy Kleene’s recursion theorem. In addition, they have infinite padding (see Ershov (Reference Ershov1977)) and other properties common in recursion theory (cf., e.g., Selivanov (Reference Selivanov2021b)).
In this paper, we study the relativized properties of completeness and precompleteness of numberings from two perspectives. The first one is the full relativization of these two concepts.
Definition 1 (Badaev et al. Reference Badaev, Goncharov and Sorbi2003). Given an oracle
$A$
, a numbering
$\nu$
is said to be
$A$
-
$\textrm {precomplete}$
(
$A$
-
$\text{complete with respect to}$
$X\in \nu (\mathbb N)$
) if for any partial
$A$
-recursive function
$\psi$
there exists an
$A$
-recursive
$h$
satisfying condition (
2
) (condition (
1
), respectively) for each
$x$
.
The precompleteness property, relativized in this way, was also studied by Golov and Terwijn in their recent paper (Golov and Terwijn Reference Golov and Terwijn2022). There, the following question was raised (see Golov and Terwijn Reference Golov and Terwijn2022, Question 3.8).
Question 1.
Does there exist a set
$A$
and an
$A$
-precomplete numbering that is not precomplete?
A positive answer to this question is given by Theorem2 of this paper. It proves that there are even
$A$
-complete numberings that are not precomplete.
Another relativization of (pre)completeness was previously studied by Selivanov (Reference Selivanov1988, Reference Selivanov2021b). In his definition, Selivanov requires the totalization
$h$
of
$\psi$
to be absolutely recursive, rather than merely
$A$
-recursive.
Definition 2.
Given an oracle
$A$
, a numbering
$\nu$
is said to be
$\text{Selivanov}$
$A$
-
$\text{precomplete}$
(
$\text{Selivanov}$
$A$
-
$\text{complete with respect to}$
$X\in \nu (\mathbb N)$
) if for any partial
$A$
-recursive function
$\psi$
there exists a recursive
$h$
satisfying condition (
2
) (condition (
1
), respectively) for each
$x$
.
If a numbering
$\nu$
is
$A$
-complete or Selivanov
$A$
-complete with respect to
$X\in \nu (\mathbb N)$
, then the element
$X$
will also be called a special object of this numbering, and from the context it will always be clear what version of the completeness we are talking about.
Theorem5 and Corollary4 of this paper study Mal’cev’s problem (see Denisov and Lavrov Reference Denisov and Lavrov1970) of whether an arbitrary complete numbering determines its special object uniquely for
$A$
-complete and Selivanov
$A$
-complete numberings. From Corollary4, it follows that given an oracle
$A$
, for every nonempty at most countable set
$S$
and for any of its nonempty subsets
$S_0\subseteq S$
, there exists a numbering
$\nu$
of
$S$
that is both
$A$
-complete and Selivanov
$A$
-complete and whose set of special objects is
$S_0$
.
In the notation and terminology of recursion theory, we mainly follow Soare’s monograph (Soare Reference Soare2016). By
$\Phi ^A_e(x)$
, we denote the partial Turing functional with the Gödel number
$e$
. For a partial function
$\psi$
, we write
$\psi (x)\downarrow$
if the value of
$\psi$
on the argument
$x$
is defined, and
$\psi (x)\uparrow$
otherwise. We denote its domain and range by
$\mathrm{dom}\,\psi$
and
$\mathrm{ran}\,\psi$
, respectively. Let
$c(x, y)$
denotes the recursive pairing function
$2^x(2y+1)-1$
. Instead of
$c(x,c(y,z))$
we will simply write
$c(x,y,z)$
.
2. Preliminaries on numberings
For the main concepts and notions of the theory of numberings, we refer to the book by Ershov (Reference Ershov1977) and his paper Ershov (Reference Ershov and Griffor1999). Given numberings
$\mu$
and
$\nu$
with
$\mu (\mathbb N)\subseteq \nu (\mathbb N)$
, we say that
$\mu$
is reducible to
$\nu$
, abbreviated
$\mu \leqslant \nu$
, if there exists a recursive function
$f$
such that
\begin{equation*} \mu =\nu \circ f. \end{equation*}
Definition 3 (Goncharov and Sorbi (Reference Goncharov and Sorbi1997)). A numbering
$\nu$
of a family
$\mathscr{A}$
of
$\Sigma ^0_{n+1}$
-sets,
$n\in \mathbb N$
, is said to be
$\Sigma ^0_{n+1}$
-
$\text{computable}$
if the set of pairs
\begin{equation*} G_{\nu }=\big\{\big \langle x,y\big \rangle \in \mathbb N\times \mathbb N:y\in \nu (x)\big\} \end{equation*}
is a
$\Sigma ^0_{n+1}$
-set.
We say that
$\mathscr{A}$
is
$\Sigma ^0_{n+1}$
-computable if it has a
$\Sigma ^0_{n+1}$
-computable numbering. For
$n = 0$
,
$\Sigma ^0_{n+1}$
-computable numberings and families are called computable.
In the theory of numberings, the completeness property is often studied in
$\Sigma ^0_{n+2}$
-computable numberings,
$n\in \mathbb N$
, (see Badaev et al. Reference Badaev, Goncharov and Sorbi2003, Reference Badaev, Goncharov and Sorbi2008; Khisamiev Reference Khisamiev2006). This is because every
$\Sigma ^0_{n+2}$
-computable family has a complete
$\Sigma ^0_{n+2}$
-computable numbering, while a computable family has a complete computable numbering only if it contains a least element under inclusion (cf., e.g., Jain and Nessel Reference Jain and Nessel2001; Badaev et al. Reference Badaev, Goncharov and Sorbi2003). Moreover, every
$\Sigma ^0_{n+2}$
-computable principal numbering is complete with respect to each of its elements (see Badaev et al. Reference Badaev, Goncharov and Sorbi2003). Additionally, for all
$n$
, any
$\Sigma ^0_{n+2}$
-computable family has a Selivanov
$\varnothing ^{(n)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering. Indeed, the completion (with respect to
$X\in \alpha (\mathbb N)$
) of any
$\Sigma ^0_{n+2}$
-computable numbering
$\alpha$
(see Ershov Reference Ershov1970), relativized with respect to
$\varnothing ^{(n)}$
(see Badaev et al. Reference Badaev, Goncharov and Sorbi2003), that is, the numbering
\begin{equation*} \alpha ^{\textbf{0}^{(n)}}_X(c(e,x))= \begin{cases} \alpha (\Phi ^{\varnothing ^{(n)}}_e(x)), & \mbox{if}\ \Phi ^{\varnothing ^{(n)}}_e(x)\downarrow ,\\ X, & \mbox{if}\ \Phi ^{\varnothing ^{(n)}}_e(x)\uparrow , \end{cases} \end{equation*}
is obviously Selivanov
$\varnothing ^{(n)}$
-complete with respect to
$X\in \alpha (\mathbb N)$
and
$\Sigma ^0_{n+2}$
-computable. For these reasons, in this paper, we also limit ourselves to considering
$\Sigma ^0_{n+2}$
-computable numberings,
$n\in \mathbb N$
.
Definition 4.
We say that a
$\Sigma ^0_{n+1}$
-numbering
$\nu$
is
$\text{principal}$
if
$\mu \leqslant \nu$
for every
$\Sigma ^0_{n+1}$
-numbering
$\mu$
such that
$\mu (\mathbb N)\subseteq \nu (\mathbb N)$
.
If the family
$\mathscr{A}$
contains at least two sets, then we will call it non-trivial. We say that a numbering
$\nu$
is decidable if its numeration equivalence
\begin{equation*} \eta _{\nu }=\big\{\big \langle x,y\big \rangle \in \mathbb N\times \mathbb N:\nu (x)=\nu (y)\big\} \end{equation*}
is recursive.
If in the definition of the
$A$
-complete numbering
$\nu$
, we take as
$\psi$
the partial function
\begin{equation*} c(e,x)\mapsto \Phi ^A_e(x), \end{equation*}
then we obtain that there exists a binary
$A$
-recursive function
$f$
satisfying the condition
\begin{equation} \nu (f(e,x))= \begin{cases} \nu (\Phi ^{A}_e(x)), & \mbox{if}\ \Phi ^{A}_e(x)\downarrow ,\\ X, & \mbox{if}\ \Phi ^{A}_e(x)\uparrow , \end{cases} \end{equation}
for all
$e$
and
$x$
.
3. Relativized complete and precomplete numberings
The following theorem implies that there exists an oracle
$A$
and an
$A$
-complete numbering that is not precomplete. Thus, it solves Question1.
Theorem 2.
Every non-trivial
$\Sigma ^0_{n+2}$
-computable family
$\mathscr{A}$
with a least element under inclusion has an
$\varnothing ^{(n+1)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering that is not
$\varnothing ^{(m)}$
-precomplete for each
$m\leqslant n$
.
Proof.
Let
$\alpha$
be a
$\Sigma ^0_{n+2}$
-computable numbering of
$\mathscr{A}$
and let
$X$
be the least element of
$\mathscr{A}$
under inclusion. Fix
$Z\in \mathscr{A}$
such that
$Z\not =X$
. It was proved by Ershov (Reference Ershov1977) that every precomplete numbering
$\beta$
is cylindrical, that is, there exists a binary injective recursive function
$g$
such that
$\beta (x)=\beta (g(x,t))$
for all
$x$
and
$t$
. This result can be relativized to an arbitrary oracle. To prove the statement of the theorem, we are going to define an
$\varnothing ^{(n+1)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering
$\nu$
of
$\mathscr{A}$
that is not
$\varnothing ^{(n)}$
-cylindrical.
Let
$\{g_u\}_{u\in \mathbb N}$
be an
$\varnothing ^{(n+1)}$
-recursive sequence of all binary injective
$\varnothing ^{(n)}$
-recursive functions. Such a sequence can be obtained by an obvious modification of an
$\varnothing ^{(n+1)}$
-recursive sequence of all
$\varnothing ^{(n)}$
-recursive functions. Now, we choose
$\varnothing ^{(n+1)}$
-recursive sequences of integers
$\{s_u\}_{u\in \mathbb N}$
,
$\{t_u\}_{u\in \mathbb N}$
, and
$\{y_u\}_{u\in \mathbb N}$
such that
\begin{equation*} g_0(0,s_0)\lt g_0(0,t_0)\lt y_0 \lt y_0+1\lt g_1(1,s_1)\lt g_1(1,t_1)\lt y_1\lt \dots , \end{equation*}
and for every
$u$
, define
\begin{equation*} \nu (g_u(u,s_u))=X,\ \nu (g_u(u,t_u))=Z,\ \nu (y_u)=\alpha (u). \end{equation*}
Thus,
$\nu$
is not
$\varnothing ^{(n)}$
-cylindrical and
$\nu (\mathbb N)=\mathscr{A}$
. Further, we define the binary
$\varnothing ^{(n+1)}$
-recursive
$f$
by letting
\begin{equation*} f(e,x)=y_{c(e,x)}+1 \end{equation*}
for all
$e$
and
$x$
. For every
\begin{equation*} z\not \in \bigcup _u\{g_u(u,s_u), g_u(u,t_u), y_u\}\cup \mathrm{ran}\,f, \end{equation*}
we let
$\nu (z)=X$
.
Let us determine the values of
$\nu$
on
$f(e,x)$
,
$e,x\in \mathbb N$
, in such a way that condition (3), where
$A=\varnothing ^{(n+1)}$
, is met for all
$e$
and
$x$
. To do this, we define the relation
$\eta$
as the equivalence relation on
$\mathbb N$
generated by the binary relation
\begin{equation*} \big\{\big \langle \,f(e,x),\Phi ^{\varnothing ^{(n+1)}}_e(x)\big \rangle :e,x\in \mathbb N\,\&\,\Phi ^{\varnothing ^{(n+1)}}_e(x)\downarrow \big\}. \end{equation*}
Thus,
$\eta$
is
$\varnothing ^{(n+1)}$
-r.e. It is easy to check by direct verification that for any
$e$
and
$x$
there exists at most one
$z$
such that
\begin{equation} \big \langle\, f(e,x),z\big \rangle \in \eta \,\&\,z\not \in \mathrm{ran}\,f. \end{equation}
Hence, for any
$e$
and
$x$
, we can define
\begin{equation} \nu (f(e,x))= \begin{cases} \nu (z), & \mbox{if}\ \big \langle \,f(e,x),z\big \rangle \in \eta \,\&\,z\not \in \mathrm{ran}\,f,\\ X, & \mbox{otherwise}. \end{cases} \end{equation}
Since the function
$c(e,x)\mapsto f(e,x)$
is strictly increasing, the predicate “
$z\not \in \mathrm{ran}\,f$
” is
$\varnothing ^{(n+1)}$
-recursive. Since, besides this,
$X$
is the least element of
$\mathscr{A}$
under inclusion,
$\nu$
is
$\Sigma ^0_{n+2}$
-computable.
Let us show that condition (3), where
$A=\varnothing ^{(n+1)}$
, is met for all
$e$
and
$x$
. If
$\Phi ^{\varnothing ^{(n+1)}}_e(x)\uparrow$
, then, by the definition of
$\eta$
, there is no
$z$
satisfying (4). Therefore,
\begin{equation*} \nu (f(e,x))=X. \end{equation*}
Suppose
$\Phi ^{\varnothing ^{(n+1)}}_e(x)\downarrow$
. If there is
$z$
satisfying (4), then either
$\Phi ^{\varnothing ^{(n+1)}}_e(x)=z$
or
$\Phi ^{\varnothing ^{(n+1)}}_e(x)=f(j,w)$
for some
$j$
and
$w$
with
$\big \langle f(j,w),z\big \rangle \in \eta$
. Hence,
\begin{equation*} \nu (z)=\nu \left(\Phi ^{\varnothing ^{(n+1)}}_e(x)\right)=\nu (f(e,x)). \end{equation*}
If there is no
$z$
satisfying (4), then for every
$y$
such that
$ \big \langle f(e,x),y\big \rangle \in \eta ,$
we have
$\nu (y)=X$
. It follows that
$\nu (\Phi ^{\varnothing ^{(n+1)}}_e(x))=X=\nu (f(e,x))$
.
The following corollary follows from the proof of Theorem2.
Corollary 1.
Let
$\mathscr{A}$
be a non-trivial
$\Sigma ^0_{n+3}$
-computable family. Then for all
$k\leqslant n+1$
with
$k\gt 0$
and
$X\in \mathscr{A}$
, the family
$\mathscr{A}$
has a
$\Sigma ^0_{n+3}$
-computable numbering
$\varnothing ^{(k)}$
-complete with respect to
$X$
that is not
$\varnothing ^{(m)}$
-precomplete for each
$m\lt k$
.
Proof.
Let
$\nu$
be the non-
$\varnothing ^{(k-1)}$
-cylindrical numbering
$\varnothing ^{(k)}$
-complete with respect to
$X$
defined by (5) (where
$f$
and
$\eta$
are defined exactly as in the proof of Theorem2, and
$\{g_u\}_{u\in \mathbb N}$
is an
$\varnothing ^{(k)}$
-recursive sequence of all binary injective
$\varnothing ^{(k-1)}$
-recursive functions). Since
$\eta$
is
$\varnothing ^{(n+1)}$
-r.e., it is
$\varnothing ^{(n+2)}$
-recursive. Therefore,
$\nu$
is
$\Sigma ^0_{n+3}$
-computable. This completes the proof of the corollary.
Corollary 2.
For every
$n$
there exists an
$\varnothing ^{(n+1)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering that is not Selivanov
$\varnothing ^{(n+1)}$
-precomplete.
Proof.
Since any Selivanov
$\varnothing ^{(n+1)}$
-precomplete numbering is
$\varnothing ^{(m)}$
-precomplete for each
$m\leqslant n$
, the statement of the corollary follows immediately from Theorem2.
Now we will show that
$\Sigma ^0_{n+2}$
-computable families may not even have
$\varnothing ^{(n+1)}$
-precomplete
$\Sigma ^0_{n+2}$
-computable numberings.
Proposition 3.
Let
$\mathscr{A}$
be a non-trivial
$\Sigma ^0_{n+2}$
-computable family of (graphs of) total functions. Then
$\mathscr{A}$
has no
$\varnothing ^{(n+1)}$
-precomplete
$\Sigma ^0_{n+2}$
-computable numberings.
Proof.
Since
$\mathscr{A}$
is a non-trivial family of total functions, the numeration equivalence of any of its
$\Sigma ^0_{n+2}$
-computable numberings is co-
$\varnothing ^{(n+1)}$
-r.e. Hence, for every
$\Sigma ^0_{n+2}$
-computable numbering
$\alpha$
of
$\mathscr{A}$
there exists a function
$h\leqslant _T\varnothing ^{(n+1)}$
such that
$\alpha (x)\not =\alpha (h(x))$
for each
$x$
. But it was proved by Golov and Terwijn (see Golov and Terwijn (Reference Golov and Terwijn2022, Theorem 3.2) that for every set
$A$
, any
$A$
-recursive function has a fixed point in
$A$
-precomplete numberings. Therefore,
$\alpha$
is not
$\varnothing ^{(n+1)}$
-precomplete.
In Golov and Terwijn (Reference Golov and Terwijn2022), it was proved that there exists a set
$A$
and a numbering
$\nu$
such that
$\nu$
is precomplete, but not
$A$
-precomplete. It follows from the following theorem that even complete numberings may not be
$A$
-precomplete.
Theorem 3.
Let
$\mathscr{A}$
be a non-trivial
$\Sigma ^0_{n+2}$
-computable family that has an element
$X\in \mathscr{A}$
such that the family of all
$Y\in \mathscr{A}$
with
$Y\not =X$
is
$\Sigma ^0_{n+2}$
-computable. Then for all integers
$k\lt m\leqslant n+1$
, the family
$\mathscr{A}$
has a Selivanov
$\varnothing ^{(k)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering that is not
$\varnothing ^{(m)}$
-precomplete.
Proof.
Let
$X$
be an element of
$\mathscr{A}$
such that the family
$\mathscr{A}\setminus \{X\}$
is
$\Sigma ^0_{n+2}$
-computable and let
$\gamma$
be a
$\Sigma ^0_{n+2}$
-computable numbering of
$\mathscr{A}\setminus \{X\}$
. Fix arbitrary integers
$k$
and
$m$
with
$k\lt m\leqslant n+1$
.
In order to define an
$\varnothing ^{(k)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering
$\nu$
of
$\mathscr{A}$
that is not
$\varnothing ^{(m)}$
-precomplete, we need the
$\varnothing ^{(k)}$
-r.e. equivalence relation
$\eta$
generated by the binary relation
\begin{equation*} \big\{\big \langle c(e,x),\Phi ^{\varnothing ^{(k)}}_e(x)\big \rangle :e,x\in \mathbb N\,\&\,\Phi ^{\varnothing ^{(k)}}_e(x)\downarrow \big\}. \end{equation*}
Using the recursion theorem and its uniformity, we choose an injective recursive sequence of integers
$\{p_t\}_{t\in \mathbb N}$
such that
\begin{equation*} \Phi ^{\varnothing ^{(k)}}_{p_t}(0)=c(p_t,0),\ t\in \mathbb N. \end{equation*}
It is not hard to verify (for example, using the arguments from the proof of (Faizrahmanov Reference Faizrahmanov2023b, Theorem1)) that
\begin{equation} \big \langle c(\,p_t,0),c(p_u,0)\big \rangle \not \in \eta \end{equation}
for all distinct integers
$t$
and
$u$
and
\begin{equation} \big \langle c(\,p_t,0),c(e,x)\big \rangle \not \in \eta \end{equation}
for each
$t$
and all
$e$
,
$x$
with
$\Phi ^{\varnothing ^{(k)}}_e(x)\uparrow$
. Now, we define
\begin{equation*} \nu (y)= \begin{cases} \gamma (t), & \mbox{if}\ \big \langle c(p_t,0),y\big \rangle \in \eta ,\\ X, & \mbox{if}\ \forall t\,\big[\big \langle c(p_t,0),y\big \rangle \not \in \eta \big], \end{cases} \end{equation*}
for each
$y$
. Since
$k\lt n+1$
, this numbering is
$\Sigma ^0_{n+2}$
-computable. To show that it is Selivanov
$\varnothing ^{(k)}$
-complete, we are going to prove that
\begin{equation} \nu (c(e,x))= \begin{cases} \nu (\Phi ^{\varnothing ^{(k)}}_e(x)), & \mbox{if}\ \Phi ^{\varnothing ^{(k)}}_e(x)\downarrow ,\\ X, & \mbox{if}\ \Phi ^{\varnothing ^{(k)}}_e(x)\uparrow , \end{cases} \end{equation}
for all
$e$
and
$x$
. If
$\Phi ^{\varnothing ^{(k)}}_e(x)\uparrow$
, then, by (7),
\begin{equation*} \nu (c(e,x))=X. \end{equation*}
Suppose
$\Phi ^{\varnothing ^{(k)}}_e(x)\downarrow$
. If
\begin{equation*} \big \langle c(p_t,0),\Phi ^{\varnothing ^{(k)}}_e(x)\big \rangle \not \in \eta \end{equation*}
for each
$t$
, then since
$\big \langle c(e,x),\Phi ^{\varnothing ^{(k)}}_e(x)\big \rangle \in \eta$
, we have that
\begin{equation*} \big \langle c(p_t,0),c(e,x)\big \rangle \not \in \eta \end{equation*}
for each
$t$
as well. Therefore,
\begin{equation*} X=\nu (\Phi ^{\varnothing ^{(k)}}_e(x))=\nu (c(e,x)). \end{equation*}
Assume that there exists
$t$
such that
\begin{equation*} \big \langle c(p_t,0),\Phi ^{\varnothing ^{(k)}}_e(x)\big \rangle \in \eta . \end{equation*}
Then
\begin{equation*} \big \langle c(p_t,0),c(e,x)\big \rangle \in \eta \end{equation*}
as well. It follows that
\begin{equation*} \gamma (t)=\nu \Big(\Phi ^{\varnothing ^{(k)}}_e(x)\Big)=\nu (c(e,x)). \end{equation*}
Thus, (8) is met for all
$e$
,
$x$
and, hence,
$\nu$
is Selivanov
$\varnothing ^{(k)}$
-complete.
To prove that
$\nu$
is not
$\varnothing ^{(m)}$
-precomplete, we define a function
$h\leqslant _T\varnothing ^{(m)}$
such that
\begin{equation} \nu (h(y))\not =\nu (y) \end{equation}
for each
$y$
. Fix
$z$
with
$\nu (z)=X$
and for every
$y$
, define
\begin{equation*} h(y)= \begin{cases} z, & \mbox{if}\ \exists t\,\big[\big \langle c(p_t,0),y\big \rangle \in \eta \big],\\ c(p_0,0), & \mbox{otherwise}. \end{cases} \end{equation*}
By the definition of
$\eta$
, for every
$y$
, we have
\begin{equation*} \nu (y)=X\Leftrightarrow \forall t\,[\big \langle c(p_t,0),y\big \rangle \not \in \eta ]. \end{equation*}
Since
$\nu (c(p_t,0))=\gamma (t)\not =X$
for each
$t$
, (9) is met for each
$y$
.
Note that any non-trivial family
$\mathscr{A}$
with a decidable
$\Sigma ^0_{n+2}$
-computable numbering satisfies the statement of Theorem3. In particular, this statement is satisfied by the family of all
$\Sigma ^0_{n+2}$
-sets and by any non-trivial finite family of
$\Sigma ^0_{n+2}$
-sets.
It was proved in Badaev and Goncharov (Reference Badaev and Goncharov2014) by Badaev and Goncharov that for every
$n$
there exists a family without a least element under inclusion which has a
$\Sigma ^0_{n+2}$
-computable principal numbering. Since this family has no least element under inclusion, it has no
$\varnothing ^{(n+1)}$
-complete numberings (cf., e.g., Badaev et al. Reference Badaev, Goncharov and Sorbi2003). The following theorem shows that this family nevertheless has a Selivanov
$\varnothing ^{(n+1)}$
-precomplete
$\Sigma ^0_{n+2}$
-computable numbering. This theorem also proves that a Selivanov
$\varnothing ^{(n+1)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering may not be principal. Previously, Badaev, Goncharov, and Sorbi showed (Badaev et al. Reference Badaev, Goncharov and Sorbi2008) that there exists a family with the least element under inclusion that has a complete
$\Sigma ^0_{n+2}$
-computable non-principal numbering.
Theorem 4.
$1)$
Every
$\Sigma ^0_{n+2}$
-computable principal numbering is Selivanov
$\varnothing ^{(n+1)}$
-precomplete.
$2)$
For every
$n$
there exists a family
$\mathscr{A}$
with the least element under inclusion that has a Selivanov
$\varnothing ^{(n+1)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering, but has no
$\Sigma ^0_{n+2}$
-computable principal numbering.
Proof.
(1) Let
$\nu$
be a
$\Sigma ^0_{n+2}$
-computable principal numbering ant let
$\psi$
be an arbitrary partial
$\varnothing ^{(n+1)}$
-recursive function. To construct a recursive
$h$
that for each
$x$
satisfies (2), we fix an
$\varnothing '$
-recursive sequence
$\{h_m\}_{m\in \mathbb N}$
of all recursive functions and define the
$\Sigma ^0_{n+2}$
-computable numbering
$\mu$
of a subfamily of
$\nu (\mathbb N)$
by letting
\begin{equation*} \mu (c(m,x,s))=\begin{cases} \nu (\psi _s(x)), \mbox{if}\ \psi _s(x)\downarrow ,\\ \nu (h_m(c(m,x,s+1))),\ \mbox{if}\ \psi _s(x)\uparrow , \end{cases} \end{equation*}
for all
$m$
,
$x$
, and
$s$
. Since
$\nu$
is principal, we can fix an index
$e$
such that
$\mu =\nu \circ h_e$
. Further, we choose an arbitrary
$x$
. If
$\psi (x)\downarrow$
, then we fix the least
$t$
such that
$\psi _t(x)\downarrow$
. Then
\begin{equation*} \nu (h_e(c(e, x, s))) = \mu (c(e, x, s)) = \nu (h_e(c(e, x, s+1))) \end{equation*}
for each
$s \lt t$
and
\begin{equation*} \nu (\psi _t(x)) = \mu (c(e, x, t)) =\nu (h_e(c(e, x, t))). \end{equation*}
Thus, if
$\psi (x)\downarrow$
, then
$\nu (\psi (x))=\nu (h_e(c(e,x,0)))$
.
Therefore, the recursive function
\begin{equation*} h:x\mapsto h_e(c(e,x,0)) \end{equation*}
satisfies (2) for each
$x$
.
(2) Let
$\{X_m\}_{m\in \mathbb N}$
be an
$\varnothing ^{(n+1)}$
-r.e. sequence of sets such that
\begin{equation*} X_m\subseteq X_{m+1}\,\&\,X_m\not =\bigcup _kX_k \end{equation*}
for each
$m$
. Relativizing Lachlan’s result (see Lachlan Reference Lachlan1964; Badaev and Goncharov Reference Badaev and Goncharov2014), we obtain that if a family has a
$\Sigma ^0_{n+2}$
-computable principal numbering, then it is closed under unions of
$\varnothing ^{(n+1)}$
-r.e. sequences of elements non-decreasing under inclusion. Hence, the
$\Sigma ^0_{n+2}$
-computable family
\begin{equation*} \mathscr{A}=\{X_m:m\in \mathbb N\} \end{equation*}
has no
$\Sigma ^0_{n+2}$
-computable principal numberings.
To show that
$\mathscr{A}$
has a Selivanov
$\varnothing ^{(n+1)}$
-complete
$\Sigma ^0_{n+2}$
-computable numbering, we define an
$\varnothing ^{(n+1)}$
-r.e. equivalence relation
$\eta$
as the equivalence generated by the binary relation
\begin{equation*} \big\{\big \langle c(e,x),\Phi ^{\varnothing ^{(n+1)}}_e(x)\big \rangle :e,x\in \mathbb N\,\&\,\Phi ^{\varnothing ^{(n+1)}}_e(x)\downarrow \big\}. \end{equation*}
By the recursion theorem, there exists a recursive sequence of integers
$\{p_t\}_{t\in \mathbb N}$
such that
\begin{equation*} \Phi ^{\varnothing ^{(n+1)}}_{p_t}(0)=c(p_t,0) \end{equation*}
for each
$t$
. In the same way as in the proof of Theorem3, we have that (6) is met for all distinct integers
$t$
and
$u$
and (7) is met for each
$t$
and all
$e$
,
$x$
with
$\Phi ^{\varnothing ^{(n+1)}}_e(x)\uparrow$
, and also that the
$\Sigma ^0_{n+2}$
-computable numbering
$\nu$
of
$\mathscr{A}$
defined by
\begin{equation*} \nu (y)= \begin{cases} X_t, & \mbox{if}\ \big \langle c(p_t,0),y\big \rangle \in \eta ,\\ X_0, & \mbox{if}\ \forall t\,[\big \langle c(p_t,0),y\big \rangle \not \in \eta ],\ y\in \mathbb N, \end{cases} \end{equation*}
is Selivanov
$\varnothing ^{(n+1)}$
-complete with respect to
$X_0$
.
4. Families of special objects
As mentioned earlier, a computable numbering of a family
$\mathscr{A}$
is complete with respect to
$X\in \mathscr{A}$
if and only if
$X$
is the least element of
$\mathscr{A}$
under inclusion. It was proved by Ershov (Reference Ershov1968) that this is no longer true for non-computable numberings. Namely, he showed that for every
$n$
there exists a numbering having exactly
$n$
special objects. Later, Denisov and Lavrov proved (Denisov and Lavrov Reference Denisov and Lavrov1970) that complete numberings can have infinitely many special objects (the question of the existence of such numberings was raised by Ershov (Reference Ershov1969b). A joint generalization of the results by Ershov, Denisov, and Lavrov was obtained by (Reference Khisamiev2006), who proved that any subset of a given at most countable nonempty set
$S$
is the set of special objects of some complete numbering of
$S$
. Moreover, he showed that for all
$\Sigma ^0_{n+2}$
-computable families
$\mathcal{C}$
and
$\mathcal{D}$
with
$(\mathcal{C}\cup \{\varnothing \})\setminus \mathcal{D}\not =\varnothing$
there exists a
$\Sigma ^0_{n+2}$
-computable numbering of the family
$\mathcal{C}\cup \mathcal{D}\cup \{\varnothing \}$
whose family of special objects is
$\mathcal{C}\cup \{\varnothing \}$
. The following theorem generalizes Khisamiev’s result and implies that given an oracle
$A$
, every subset of a nonempty at most countable set
$S$
is the set of special objects of some (Selivanov)
$A$
-complete numbering of
$S$
.
Theorem 5.
Let
$\mathscr{A}$
and
$\mathcal{B}\subseteq \mathscr{A}$
be nonempty
$\Sigma ^0_{n+2}$
-computable families. Then for every
$m\leqslant n$
, the family
$\mathscr{A}$
has a
$\Sigma ^0_{n+2}$
-computable numbering
$\nu$
that for any
$X\in \mathcal{B}$
is Selivanov
$\varnothing ^{(n)}$
-complete with respect to
$X$
and for no
$Y\in \mathscr{A}\setminus \mathcal{B}$
is
$\varnothing ^{(m)}$
-complete with respect to
$Y$
.
Proof.
Let
$\alpha$
and
$\beta$
be
$\Sigma ^0_{n+2}$
-computable numberings of the families
$\mathscr{A}$
and
$\mathcal{B}$
, respectively. Since the statement of the theorem is obvious for
$|\mathscr{A}|=1$
, we will assume that
$|\mathscr{A}|\gt 1$
, and also, without loss of generality, that
\begin{equation*} \alpha (0)\not =\alpha (1). \end{equation*}
Fix an arbitrary integer
$m\leqslant n$
. To define the numbering
$\nu$
satisfying the statement of the theorem, we construct a sequence
$\{\nu _s\}_{s\in \mathbb N}$
of partial mappings of
$\mathbb N$
to
$\mathscr{A}$
such that
$\nu _s\subseteq \nu _{s+1}$
for each
$s$
and
$\bigcup _s\nu _s$
is a
$\Sigma ^0_{n+2}$
-computable numbering of
$\mathscr{A}$
, satisfying the statement of the theorem. After that, we let
$\nu =\bigcup _s\nu _s$
.
In the construction of
$\nu$
, for all
$z$
, we will satisfy the following requirements:
\begin{gather*} N_z:\ (\mbox{There is a binary recursive}\ f\ \text{satisfying (3) for all}\ x\ \mbox{and}\ e,\\ \mbox{where}\ A=\varnothing ^{(n)}\ \mbox{and}\ X=\beta (z)), \end{gather*}
\begin{equation*} P_z:\ \exists x\,[\nu (x)=\alpha (z)], \end{equation*}
\begin{gather*} R_z:\ (\Phi ^{\varnothing ^{(m)}}_z\ \mbox{is total}\Rightarrow \mbox{there exist}\ e\ \mbox{and}\ x\ \mbox{such that for every}\ X\in \mathscr{A}\setminus \mathcal{B},\\ \text{condition (3) does not hold, where}\ f=\Phi ^{\varnothing ^{(m)}}_z\ \mbox{and}\ A=\varnothing ^{(m)}). \end{gather*}
Obviously, having met all these requirements, we obtain that
$\nu$
satisfies the statement of the theorem.
Construction
Stage
$0$
. We set
$\nu _0$
equal to the partial mapping of
$\mathbb N$
to
$\mathscr{A}$
with empty domain. At each stage
$s+1$
of the construction, we will also define some
$\varnothing ^{(n)}$
-r.e. equivalence
$\eta _{s+1}$
and a strictly increasing recursive sequence of integers
$\{a^{s+1}_i\}_{i\in \mathbb N}$
. Let
$\eta _{0}$
be the equality relation on
$\mathbb N$
and let
$a^0_i=i$
for each
$i$
.
Stage
$s+1$
. Assume by induction that for
$u=s$
the following conditions are met:
-
(i)
$\nu _v\subseteq \nu _u$
for each
$v\lt u$
, -
(ii) the sequence
$\{a^{u}_i\}_{i\in \mathbb N}$
is strictly increasing and recursive, -
(iii)
$\big \langle a^u_i,a^u_j\big \rangle \not \in \eta _u$
for all distinct integers
$i$
and
$j$
, -
(iv)
$\mathrm{dom}\,\nu _u=\mathbb N\setminus (\bigcup _i[a^u_i]_{\eta _u})$
, where
$[a^u_i]_{\eta _u}$
is the
$\eta _u$
-equivalence class of
$a^u_i$
, -
(v) for all
$x,y\in \mathrm{dom}\,\nu _u$
, if
$\big \langle x,y\big \rangle \in \eta _u$
, then
$\nu _u(x)=\nu _u(y)$
.
It is not hard to see that when
$u=0$
conditions (i)–(v) are met. Now, let us consider three cases.
1.
$s=3z$
for some
$z$
. In this case, we satisfy the requirement
$N_z$
. We define the relation
$\eta _{s+1}$
as the
$\varnothing ^{(n)}$
-r.e. equivalence relation generated by the binary relation
\begin{equation*} \eta _s\cup \big\{\big \langle a^s_{c(e,x)},\Phi ^{\varnothing ^{(n)}}_e(x)\big \rangle : e,x\in \mathbb N\,\&\,\Phi ^{\varnothing ^{(n)}}_e(x)\downarrow \big\}. \end{equation*}
Using the recursion theorem and its uniformity, effectively in
$s$
, we choose a strictly increasing recursive sequence
$\{e_i\}_{i\in \mathbb N}$
such that
\begin{equation} \Phi ^{\varnothing ^{(n)}}_{e_i}(0)=a^s_{c(e_i,0)} \end{equation}
for each
$i$
. Then for all
$i$
, we let
\begin{equation} a^{s+1}_i=a^s_{c(e_i,0)}. \end{equation}
Thus, condition (ii) is met for
$u=s+1$
. Since condition (iii) is met for
$u=s$
and condition (10) is met for each
$i$
, condition (iii) is met for
$u=s+1$
as well. Next, we define
\begin{equation*} \nu _{s+1}(x)=\nu _s(x) \end{equation*}
for each
$x\in \mathrm{dom}\,\nu _s$
. Hence, condition (i) is met for
$u=s+1$
. Further, for every
$x\not \in \mathrm{dom}\,\nu _s$
, we define
\begin{equation*} \nu _{s+1}(x)= \begin{cases} \nu _s(\Phi ^{\varnothing ^{(n)}}_e(y)), & \mbox{if}\ \big \langle x, a^s_{c(e,y)}\big \rangle \in \eta _{s+1}\,\&\,\Phi ^{\varnothing ^{(n)}}_e(y)\downarrow \in \mathrm{dom}\,\nu _s,\\ \uparrow , & \mbox{if}\ \exists i\,\big[\big \langle x,a^{s+1}_i\big \rangle \in \eta _{s+1}\big],\\ \beta (z), & \mbox{in other cases}. \end{cases} \end{equation*}
Let us show that this definition is correct. Let
$e$
,
$j$
,
$v$
, and
$w$
be arbitrary integers such that
\begin{equation*} \Phi ^{\varnothing ^{(n)}}_e(v)\downarrow \in \mathrm{dom}\,\nu _s\,\&\,\Phi ^{\varnothing ^{(n)}}_j(w)\downarrow \in \mathrm{dom}\,\nu _s\,\&\,\big \langle x, a^s_{c(e,y)}\big \rangle \in \eta _{s+1}\,\&\,\big \langle x, a^s_{c(j,w)}\big \rangle \in \eta _{s+1}. \end{equation*}
Thus,
$\big \langle a^s_{c(e,v)}, a^s_{c(j,w)}\big \rangle \in \eta _{s+1}$
. Assume that
$\nu _s(\Phi ^{\varnothing ^{(n)}}_e(v))\not =\nu _s(\Phi ^{\varnothing ^{(n)}}_j(w))$
. Then
\begin{equation*} \big \langle \Phi ^{\varnothing ^{(n)}}_e(v), \Phi ^{\varnothing ^{(n)}}_j(w)\big \rangle \not \in \eta _{s}. \end{equation*}
By the definition of equivalence
$\eta _{s+1}$
, we have that
$\big \langle a^s_{c(e,v)}, a^s_{c(j,w)}\big \rangle \not \in \eta _{s+1}$
. It follows from this contradiction that the values of
$\nu _{s+1}$
on elements
$x\not \in \mathrm{dom}\,\nu _s$
are defined correctly. Now, it is not hard to see that conditions (iv) and (v) are met for
$u=s+1$
.
By the definition of
$\nu _{s+1}$
, for all
$e$
and
$x$
with
$a^s_{c(e,x)}\in \mathrm{dom}\,\nu _{s+1}$
, we have
\begin{equation*} \nu _{s+1}\Big (a^s_{c(e,x)}\Big )= \begin{cases} \nu _{s+1}(\Phi ^{\varnothing ^{(n)}}_e(x)), & \mbox{if}\ \Phi ^{\varnothing ^{(n)}}_e(x)\downarrow , \\ \beta (z), & \mbox{if}\ \Phi ^{\varnothing ^{(n)}}_e(x)\uparrow . \end{cases} \end{equation*}
In addition, since for every
$i$
, conditions (10) and (11) are met, having met condition (v) for each
$u$
, we obtain that
\begin{equation*} \nu \Big (a^s_{c(e,x)}\Big )= \begin{cases} \nu (\Phi ^{\varnothing ^{(n)}}_e(x)), & \mbox{if}\ \Phi ^{\varnothing ^{(n)}}_e(x)\downarrow , \\ \beta (z), & \mbox{if}\ \Phi ^{\varnothing ^{(n)}}_e(x)\uparrow , \end{cases} \end{equation*}
for all
$e$
and
$x$
. Hence,
$N_z$
will be met with the recursive
$f:\big \langle e,x\big \rangle \mapsto a^s_{c(e,x)}$
.
2.
$s=3z+1$
for some
$z$
. In this case, we satisfy the requirement
$P_z$
. Let
$y$
be the least element of the set
$\bigcup _i[a^s_i]_{\eta _s}$
. Fix
$j$
such that
$y\in [a^s_j]_{\eta _s}$
and define
\begin{equation} \nu _{s+1}(x)=\alpha (z) \end{equation}
for each
$x\in \bigcup _{k\leqslant j}[a^s_k]_{\eta _s}$
. For every
$x\in \mathrm{dom}\,\nu _s$
, we define
$\nu _{s+1}(x)=\nu _s(x)$
. Let
$\eta _{s+1}$
be the
$\varnothing ^{(n)}$
-r.e. equivalence relation, generated by the binary relation
\begin{equation} \eta _s\cup \big\{\big \langle x,y\big \rangle \in \mathbb N\times \mathbb N: x,y\in \mathrm{dom}\,\nu _{s+1}\setminus \mathrm{dom}\,\nu _{s}\big\}. \end{equation}
Now, for every
$i$
, we let
\begin{equation*} a^{s+1}_i=a^s_{i+j+1}. \end{equation*}
It is not hard to see that in this case, conditions (i)–(v) are met for
$u=s+1$
and
$P_z$
is met as well.
3.
$s=3z+2$
for some
$z$
. In this case, we satisfy the requirement
$R_z$
. Let
$F_0,\dots , F_k$
be all
$\eta _s$
-equivalence classes such that for all
$i\leqslant k$
and
$x\in F_i$
, at least one of the assignments (12), (14) (see below) has been performed at one of the previous stages (the construction will guarantee that the tuple of such classes is always finite).
Now, we define some Turing functional
$\Psi$
assuming, by the recursion theorem, that an index
$r$
for which
\begin{equation*} \Psi =\Phi _r \end{equation*}
is given. If
$\Phi ^{\varnothing ^{(m)}}_z(r,l)\downarrow$
for each
$l\leqslant k+1$
and there exist
$p\lt q\leqslant k+1$
such that
\begin{equation*} \left \langle \Phi ^{\varnothing ^{(m)}}_z(r,p),\Phi ^{\varnothing ^{(m)}}_z(r,q)\right \rangle \in \eta _s, \end{equation*}
then we define
\begin{equation*} \Psi ^{\varnothing ^{(m)}}(p)=a^s_0,\ \Psi ^{\varnothing ^{(m)}}(q)=a^s_1, \end{equation*}
\begin{equation} \nu _{s+1}(x)=\alpha (t) \end{equation}
for all
$t=0,1$
and
$x\in [a^s_t]_{\eta _s}$
. Thus, we will have that
\begin{equation*} \nu \left(\Phi ^{\varnothing ^{(m)}}_z(r,p)\right)=\nu (\Phi ^{\varnothing ^{(m)}}_z(r,q)), \end{equation*}
but
\begin{equation*} \nu \left(\Psi ^{\varnothing ^{(m)}}(p)\right)=\alpha (0)\not =\alpha (1)=\nu \left(\Psi ^{\varnothing ^{(m)}}(q)\right). \end{equation*}
Hence,
$R_z$
will be met. For every
$i$
, we let
\begin{equation*} a^{s+1}_i=a^s_{i+2}. \end{equation*}
Now, we suppose that
$\Phi ^{\varnothing ^{(m)}}_z(r,l)\downarrow$
for each
$l\leqslant k+1$
and
\begin{equation*} \left \langle \Phi ^{\varnothing ^{(m)}}_z(r,p),\Phi ^{\varnothing ^{(m)}}_z(r,q)\right \rangle \not \in \eta _s \end{equation*}
for all
$p\lt q\leqslant k+1$
. Let
$d\leqslant k+1$
be the least integer such that
\begin{equation*} \Phi ^{\varnothing ^{(m)}}_z(r,d)\not \in \bigcup _{b\leqslant k} F_b. \end{equation*}
If
$\Phi ^{\varnothing ^{(m)}}_z(r,d)\not \in \mathrm{dom}\,\nu _s$
, then we fix
$j$
with
$\Phi ^{\varnothing ^{(m)}}_z(r,d)\in [a^s_j]_{\eta _s}$
and define
\begin{equation*} \nu _{s+1}(x)=\beta (0) \end{equation*}
for each
$x\in \bigcup _{i\leqslant j}[a^s_i]_{\eta _s}$
. For every
$i$
, we let
\begin{equation*} a^{s+1}_i=a^s_{i+j+1}. \end{equation*}
Note that if
$\Phi ^{\varnothing ^{(m)}}_z(r,d)\in \mathrm{dom}\,\nu _s$
, then since
$\Phi ^{\varnothing ^{(m)}}_z(r,d)\not \in \bigcup _{b\leqslant k} F_b$
, we have
\begin{equation*} \nu _s\left(\Phi ^{\varnothing ^{(m)}}_z(r,d)\right)\in \mathcal{B}. \end{equation*}
Thus,
$\Psi ^{\varnothing ^{(m)}}(d)\uparrow$
and
$\nu _{s+1}(\Phi ^{\varnothing ^{(m)}}_z(r,d))\not \in \mathscr{A}\setminus \mathcal{B}$
. Therefore, the requirement
$R_z$
will be met. Further, we define
$\eta _{s+1}$
by (13) and
$\nu _{s+1}(x)=\nu _s(x)$
for each
$x\in \mathrm{dom}\,\nu _s$
. It is not hard to see that in this case, conditions (i)–(v) are met for
$u=s+1$
.
This completes the description of the construction and the proof of the theorem.
Corollary 4.
Let
$A$
be an arbitrary oracle and let
$S$
be a nonempty at most countable set. Then for every nonempty subset
$S_0$
of
$S$
there exists a numbering
$\nu$
of
$S$
that for any
$w\in S_0$
is Selivanov
$A$
-complete with respect to
$w$
and for no
$z\in S\setminus S_0$
is
$A$
-complete with respect to
$z$
.
Proof.
Let us consider the computable family
$\mathscr{A}$
defined as follows:
\begin{equation*} \mathscr{A}=\big \{\{y\}:y\in \mathbb N\,\&\,y\lt |S|\big \}. \end{equation*}
Let
$\mathcal{B}$
be a computable subfamily of
$\mathscr{A}$
such that
$|\mathcal{B}|=|S_0|$
and
$|\mathscr{A}\setminus \mathcal{B}|=|S\setminus S_0|$
. By the relativization of Theorem5, there exists an
$A'$
-computable numbering
$\mu$
of
$\mathscr{A}$
that for any
$X\in \mathcal{B}$
is Selivanov
$A$
-complete with respect to
$X$
and for no
$Y\in \mathscr{A}\setminus \mathcal{B}$
is
$A$
-complete with respect to
$Y$
.
Now, we choose an injective sequence
$\{a_y\}_{y\lt |S|}$
of elements of
$S$
such that
\begin{equation*} S=\{a_y:y\lt |S|\},\ S_0=\{a_y:\{y\}\in \mathcal{B}\}. \end{equation*}
Then the numbering
$\nu$
is defined by
\begin{equation*} \nu (x)=a_y\Leftrightarrow \mu (x)=\{y\},\ x,y\in \mathbb N, \end{equation*}
satisfies the statement of the corollary.
Acknowledgements
This work was supported by the Russian Science Foundation (grant no. 24-11-00227).
Competing interests
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Data availability
No data was used for the research described in the article.
