A Family with a Single Minimal but Not Least Numbering

Abstract

We prove the existence of a family of computably enumerable sets that, up to equivalence, has a unique computable minimal but not least numbering.

1. Introduction

One of the main problems of the theory of numberings is the algebraic classification of semilattices of computable numberings of computably enumerable (c.e.) sets. Closely related is Ershov’s problem, classical and still open, on the possible numbers (up to equivalence) of minimal computable numberings of c.e. sets. The problem was posed at the end of the 1960s (see [1, 2]) and its formulation has been intensively studied by many authors since then. This in particular led to the results in their own right for the theory of numberings (see [3,4,5,6,7]) and applications in other areas of mathematical logic (see [8, 9]).

The problem under study was solved by Marchenkov for the families of (graphs of) computable functions:

Theorem 1 [3]

A computable family of total functions has either a least numbering or infinitely many minimal computable numberings.

Both alternatives in the statement of Theorem 1 are realizable. For instance, each finite family of c.e. sets has a least computable numbering; see [10] (therefore, the problem of the number of minimal computable numberings is studied only for infinite families). Ershov found some families of total functions possessing infinitely many minimal numberings:

Theorem 2 [11]

The family of all primitively recursive functions has infinitely many minimal computable numberings.

Single-valued and positive numberings form important classes of minimal numberings. Goncharov solved Ershov’s problem for the class which also led to numerous important statements in the theory of computable models (see, for example, [8, 9, 12]).

Theorem 3 [4, 5]

For each $n\in{𝕅}$, there exists a family of c.e. sets having exactly $n$ single-valued (positive) computable numberings.

For $n=1$, Goncharov proved that a unique single-valued (positive) numbering may fail to be the least (see [6, 7]).

Advances in solving the problem in its general statement were made by Badaev [13, 14] and V’yugin [15], as well as Goncharov, A. Yakhnis, and V. Yakhnis [16], et al. Among other things, some computable families not admitting minimal computable numberings were constructed in [13, 15].

Ershov’s problem was also studied for generalized computable families [17] both with respect to the classical reducibility (see [18,19,20,21,22]) and more general positive reducibilities (see [23, 24]). For example, Badaev and Goncharov proved that every infinite $\Sigma^{0}_{n}$-computable family ($n>1$) has infinitely many minimal $\Sigma^{0}_{n}$-computable numberings in [18]. It was proved in [20,21,22] that this also holds for all $A$-computable families where the Turing degree of the oracle $A$ is high or bounds a nonzero c.e. degree.

In the twenty first century, Badaev and Lempp were closest to solving this problem. The main result of their article [19] implies the existence of a $\Sigma^{-1}_{2}$-computable family having exactly two minimal $\Sigma^{-1}_{2}$-computable numberings:

Theorem 4 [19]

There exists a family of $2$-c.e. sets $\mathcal{F}$ having two single-valued $\Sigma^{-1}_{2}$-computable numberings $\mu$ and $\nu$ such that for each $\Sigma^{-1}_{2}$-computable numbering $\pi$ of $\mathcal{F}$, either $\mu\leq\pi$ or $\pi\leq\nu$.

In the present article, we continue these studies and answer one question posed by Goncharov in the mid-1980s: Is a unique minimal computable numbering the least? The main result, Theorem 5, enables us to answer this question in the negative.

Theorem 5

There exists a discrete family $\mathcal{A}$ having a minimal computable numbering $\mu$ such that $\mu\leq\alpha$ for every minimal computable numbering $\alpha\in H(\mathcal{A})$ and $\mu\not\leq\beta$ for some computable numbering $\beta\in H(\mathcal{A})$.

Note that the semilattice of computable numberings of such family $\mathcal{A}$ may be regarded as an example of a degree structure with a nontrivial definable singleton.

2. Preliminaries

We will stick to the notation and terminology of [10] as well as [25,26,27]. Given an at most countable set $S$, every surjective mapping $\alpha:{𝕅}\to S$ is called a numbering of $S$. The set of all numberings of $S$ will be denoted by $H(S)$. If $\alpha,\beta\in H(S)$ then we say that $\alpha$ is reducible to $\beta$ (and use the notation $\alpha\leq\beta$) if there exists a computable function $f$ such that $\alpha(x)=\beta(f(x))$ for all $x$. If $\alpha\leq\beta$ and $\beta\leq\alpha$ then the numberings $\alpha$ and $\beta$ are equivalent (in this case, we use the notation $\alpha\equiv\beta$). Call a numbering $\alpha$ positive if its numeration equivalence

$$ \eta_{\alpha}=\{\langle{}x,y\rangle{}\in{𝕅}\times{𝕅}:\alpha(x)=\alpha(y)\} $$

is c.e.; $\alpha$ is called single-valued if $\eta_{\alpha}$ coincides with the equality. A numbering $\mu$ of $S$ is minimal if $\mu\leq\alpha$ for every numbering $\alpha\leq\mu$ of $S$.

A numbering $\alpha$ of a family of c.e. sets $\mathcal{A}$ is computable if the set of the pairs

$$ G_{\alpha}=\{\langle{}x,y\rangle{}\in{𝕅}\times{𝕅}:y\in\alpha(x)\} $$

is c.e. We will refer to families admitting computable numberings also as computable.

By $\varphi_{e}$ and $W_{e}$ we denote the p.c. function and the c.e. set with Gödel number $e$. Given $e$, denote by $\alpha_{e}$ the computable numbering for which

$$ G_{\alpha_{e}}=W_{e}. $$

Fix a triple strongly computable sequence of finite sets $\{\alpha_{e,s}(x)\}_{e,s,x\in{𝕅}}$ such that for all $e$, $s$, and $x$ we have

$\bullet$ $\alpha_{e,s}(x)\subseteq\alpha_{e,s+1}(x)$;

$\bullet$ $\alpha_{e,s}(x)=\varnothing$ if $e>s$;

$\bullet$ $\alpha_{e}(x)=\bigcup\nolimits_{t}\alpha_{e,t}(x)$.

Given a partial function $\psi$, the domain of definition of $\psi$ is denoted by $\operatorname{dom}\psi$. We use the notation $\psi(x){\downarrow}$ if $x\in\operatorname{dom}\psi$ and $\psi(x){\uparrow}$ otherwise. The range of $\psi$ will be denoted by $\operatorname{ran}\psi$. Denote the computable bijection $\langle{}x,y\rangle{}\mapsto 2^{x}(2y+1)-1$ from ${𝕅}\times{𝕅}$ onto ${𝕅}$ by $c(x,y)$.

For two strings $\sigma,\tau\in 2^{<{𝕅}}$, we use the notation $\sigma\preceq\tau$ if $\sigma$ is a prefix of $\tau$ and $\sigma\prec\tau$ if $\sigma\preceq\tau$ and $\sigma\not=\tau$. If there exists $i$ that is less than the length of the strings $\sigma$ and $\tau$ for which $\sigma(i)=0$ and $\tau(i)=1$ and also $\sigma(j)=\tau(j)$ for all $j<i$ then we write $\sigma<_{L}\tau$. The length of a string $\sigma$ is denoted by $\operatorname{lh}(\sigma)$.

3. Proof of Theorem 5

For proving the theorem, it suffices to define the discrete family of c.e. sets $\mathcal{A}$ by constructing some computable numberings $\mu$ and $\beta$ of $\mathcal{A}$ satisfying the following requirements for all $n\in{𝕅}$:

$R_{n}$: $\alpha_{n}\in H(\mathcal{A})\text{ is minimal}\Rightarrow\mu\leq\alpha_{n}$,

$M_{n}$: $\varphi_{n}\ \text{is total }\&\,(\mu\circ\varphi_{n})\in H(\mathcal{A})\Rightarrow\mu\leq(\mu\circ\varphi_{n})$,

$P_{n}$: $\varphi_{n}\ \text{is total }\Rightarrow\mu\not=(\beta\circ\varphi_{n})$.

To satisfy $P_{n}$, fix $w_{0}$ and $a_{0}$ and put

$$ \mu(w_{0})=\beta(w_{0})=\{a_{0}\}. $$

If at some stage $\varphi_{n}(w_{0})=w_{0}$ then we put

$$ \mu(w_{0})=\{a_{0}<a_{1}<a_{2}\},\quad\mu(w)=\{a_{0}<a^{\prime}_{1}<a^{\prime}_{2}\}, $$

$$ \beta(w_{0})=\{a_{0}<a^{\prime}_{1}<a^{\prime}_{2}\},\quad\beta(w)=\{a_{0}<a_{1}<a_{2}\} $$

for some new pairwise distinct numbers $a_{1},a_{2},a^{\prime}_{1},a^{\prime}_{2}$ and $w$.

To satisfy $M_{n}$, in the construction of $\mu$, we guarantee that for each $x$, it is possible to effectively find $z$ such that $\mu(x)=\mu(\varphi_{n}(z))$ if $\mu(\varphi_{n}({𝕅}))=\mathcal{A}$.

For meeting $R_{n}$ in the construction, we will define some computable functions $g_{n}(x)$, $f_{n}(x)$, and $d(n,s)$ such that we have the limit $\lim\nolimits_{s}d(n,s)$, and if $\alpha_{n}\in H(\mathcal{A})$ then

$\bullet$ $\alpha_{n}(g_{n}({𝕅}))=\mathcal{A}$;

$\bullet$ $\alpha_{n}\not=\alpha_{n}\circ g_{n}\circ\varphi_{i}$ for all $i<\lim\nolimits_{s}d(n,s)$; in particular, if $\lim\nolimits_{s}d(n,s)=\infty$ then $\alpha_{n}\not\leq\alpha\circ g_{n}$, and hence $\alpha_{n}$ is not minimal;

$\bullet$ $\mu=\alpha_{n}\circ f_{n}$ if $\alpha_{n}$ is minimal.

The main obstacle to meeting this requirement is that at some stage $s$ of the construction, it can happen that

$$ \mu(w_{0})=\{a_{0}<a_{1}<a_{2}\}\not=\alpha_{n}(f_{n}(w_{0})). $$

In this case, fix $i=d(n,s)$ and put $d(n,s+1)=d(n,s)+1$. We will achieve the fulfillment of the conditions $\alpha_{n}(g_{n}({𝕅}))=\mathcal{A}$ and $\alpha_{n}\not=\alpha_{n}\circ g_{n}\circ\varphi_{i}$. For this choose $r_{n}$ such that

$$ \alpha_{n}(r_{n})\not\in\alpha_{n}(g_{n}({𝕅})) $$

and $\alpha_{n}(r_{n})=\mu(w_{0})$ at some of the subsequent stages (the existence of $r_{n}$ will be guaranteed while constructing) and also the new numbers $x_{n}$ and $x^{\prime}_{0}$ at which we define

$$ \mu(x_{n})=\{b^{n}_{0}<b^{n}_{1}\},\quad\mu(x^{\prime}_{0})=\{b_{0}<b_{1}\} $$

for some new pairwise distinct numbers $b^{n}_{0}$, $b^{n}_{1}$, $b_{0}$, and $b_{1}$. Then choose $y^{n}$ for which at some of the subsequent stages, we will have

$$ \alpha_{n}(y^{n})=\mu(x_{n}), $$

and put $g_{n}(w)=y_{n}$ for the first number $w$ at which the value $g_{n}(w)$ is undefined at the previous stage. After that, we consecutively begin adding elements into $\mu(x^{\prime}_{0})$, $\mu(x_{n})$, and $\mu(w_{0})$; so as before adding each of the subsequent elements, expecting the fulfillment at some stage of the equalities

$$ \alpha_{n}(y^{n})=\mu(x_{n}),\quad\alpha_{n}(r_{n})=\mu(w_{0}). $$

We organize the process so that at each stage, $\mu(x^{\prime}_{0})$, $\mu(x_{n})$, and $\mu(w_{0})$ are pairwise incomparable with respect to inclusion, but the greatest number $k$ for which

$$ \mu(x^{\prime}_{0})\upharpoonright k=\mu(x_{n})\upharpoonright k=\mu(w_{0})\upharpoonright k $$

grows in the process. If $\varphi_{i,t}(r_{n}){\downarrow}\in\operatorname{dom}g_{n}$ at one of the subsequent stages $t$ then we stop adding elements to $\mu(w_{0})$ but continue adding them to $\mu(x^{\prime}_{0})$ and $\mu(x_{n})$ so that at each stage, $\mu(x^{\prime}_{0})$ and $\mu(x_{n})$ are pairwise incomparable with respect to inclusion but the greatest $k$ for which

$$ \mu(x^{\prime}_{0})\upharpoonright k=\mu(x_{n})\upharpoonright k $$

grows in the process. Since, at stage $t$, we have

$$ \alpha_{n}(r_{n})\not\in\alpha_{n}(g_{n}({𝕅}))\,\&\,\varphi_{i}(r_{n}){\downarrow}\in\operatorname{dom}g_{n}, $$

we infer

$$ \alpha_{n}(r_{n})\not=\alpha(g_{n}(\varphi_{i}(r_{n}))). $$

Hence, the numbering $\alpha_{n}$ is not reducible to the numbering $\alpha_{n}\circ g_{n}$ via $\varphi_{i}$. Then we put $g_{n}(w)=r_{n}$ for the least $w$ at which $g(w)$ is undefined at stage $t$. If $\varphi_{i,t}(r_{n}){\uparrow}$ at all stages $t$; then, trivially, $\alpha_{n}$ is not reducible to $\alpha_{n}\circ g_{n}$ via $\varphi_{i}$. Moreover, we finally have

$$ \mu(x^{\prime}_{0})=\mu(x_{n})=\mu(w_{0}). $$

Therefore,

$$ \mu(w_{0})=\mu(x_{n})=\alpha_{n}(y^{n})\in\alpha_{n}(g_{n}({𝕅})). $$

In construction, we will make sure that the numbering $\mu$ satisfies the condition

$$ \forall X\in\mathcal{A}\,[\mu^{-1}(X)\ \text{is finite}]. $$

(1)

At each of the stages of the construction, as it is often done in such constructions (see, for example, [26, Chapter VII, Theorem 3.1]), we will also define the auxiliary binary computable length functions $l$ and $m$. Given $n$ and $s$, we will put $l(n,s)$ to be equal to the greatest $r\leq s$ such that

$$ \forall x\leq r\exists y\leq s\,[\mu_{s}(y)\not=\varnothing\,\&\,\alpha_{n,s}(x)\upharpoonright r=\mu_{s}(y)\upharpoonright r], $$

$$ \forall y\leq r\exists x\leq s\,[\mu_{s}(y)\upharpoonright r=\alpha_{n,s}(x)\upharpoonright r]. $$

If $\mathcal{A}$ is a discrete family and $\mu$ is its computable numbering satisfying (1) then for each $n$ we have

$$ \begin{gathered}\displaystyle\limsup_{s}l(n,s)=\infty\Rightarrow\alpha_{n}({𝕅})\subseteq\mu({𝕅})\ \text{by (1) and}\ \mu({𝕅})\subseteq\alpha_{n}({𝕅})\\ \displaystyle\text{by the discreteness of}\ \mathcal{A}\Rightarrow\alpha_{n}({𝕅})=\mathcal{A}\Rightarrow\lim\limits_{s}l(n,s)=\infty.\end{gathered} $$

The value $m(n,s)$ will be put to be equal to the greatest $r\leq s$ such that

$$ \forall x\leq r\exists y\leq s\,[\varphi_{n,s}(x){\downarrow}\,\&\,\varphi_{n,s}(y){\downarrow}\,\&\,\mu_{s}(x)\upharpoonright r=\mu_{s}(\varphi_{n}(y))\upharpoonright r]. $$

If $\mathcal{A}$ is a discrete family and $\mu$ is its computable numbering then for all $n$ we have

$$ \limsup_{s}m(n,s)=\infty\Rightarrow(\varphi_{n}\ \text{is total }\&\mathcal{A}=\mu(\varphi_{n}({𝕅})))\Rightarrow\lim\limits_{s}m(n,s)=\infty. $$

Furthermore, define the notion of $\sigma$-stage for every string $\sigma\in 2^{<{𝕅}}$. As this is characteristic for $\mathbf{0}^{\prime\prime}$-priority constructions, all requirements for the family $\mathcal{A}$ and its numbering $\mu$ will be satisfied at $\sigma$-stages such that $\sigma$ is the least string with respect to the lexicographic order among all strings of length $\operatorname{lh}(\sigma)$ for which the set of $\sigma$-stages is infinite. Moreover, if this property is possessed by another string $\tau$, $\operatorname{lh}(\tau)>\operatorname{lh}(\sigma)$, then, by the definition below, we will have $\sigma\prec\tau$. In the limit, all strings with this property together $\sigma_{0}\prec\sigma_{1}\prec\sigma_{2}\prec\cdots$ form $T\in 2^{{𝕅}}$ which is usually called the true path of the construction (see [26, Chapter XIV, § 2]), constructing along which guarantees the meeting of all requirements for $\mathcal{A}$ and $\mu$. The set of all $\sigma$-stages will be denoted by $S_{\sigma}$. For the empty string $\lambda$, every $s\in{𝕅}$ will be called a $\lambda$-stage. Suppose by induction that for a string $\sigma$, the notion of a $\sigma$-stage is defined. Let $\operatorname{lh}(\sigma)=2n$ ($\operatorname{lh}(\sigma)=2n+1$). Then a $\sigma$-stage $s$ is called a $\sigma 0$-stage if

$$ \forall t<s\,\big{[}t\in S_{\sigma}\Rightarrow l(n,s)>l(n,t)\ (m(n,s)>m(n,t))\big{]}, $$

and a $\sigma 1$-stage otherwise.

Simultaneously with constructing the numberings $\mu$ and $\beta$, for each $n$, we will construct partially computable functions $f_{n}$ and $g_{n}$ such that

(a) if the numbering $\alpha_{n}\in H(\mathcal{A})$ is minimal then for all $x$ (excluding finitely many), we have $f_{n}(x){\downarrow}$ and $\mu(x)=\alpha_{n}(f(x))$;

(b) if $\alpha_{n}\in H(\mathcal{A})$ then $g_{n}$ is total and the family $\mathcal{A}\setminus\alpha_{n}(g_{n}({𝕅}))$ is finite.

Also for every string $\sigma$ of length $2n+2$, we will construct a binary partially computable function $d_{\sigma}$ with the help of which we will control the minimality of the numberings $\alpha_{e}$, $e\leq n$ (as it was done in the informal description of the construction with the use of the function $d$). Additionally, in construction we guarantee the meeting of $|X\setminus Y|\geq 2$ for all distinct $X,Y\in\mathcal{A}$.

At the prefix of the construction, we put $\mu_{0}(x)=\beta_{0}(x)=\varnothing$ for all $x\in{𝕅}$, the functions $f_{n,0}$ and $g_{n,0}$ to be nowhere defined, and $d_{\sigma}(n,0)=0$ for all $\sigma\in 2^{<{𝕅}}$ and $n\in{𝕅}$. At each stage $s+1$ of the construction, for all $x,n\in{𝕅}$ and $\sigma\in 2^{<{𝕅}}$, unless otherwise specified, we assume that $\mu_{s+1}(x)=\mu_{s}(x)$, $\beta_{s+1}(x)=\beta_{s}(x)$, $f_{n,s+1}(x)=f_{n,s}(x)$, $g_{n,s+1}(x)=g_{n,s}(x)$, and $d_{\sigma}(n,s+1)=d_{\sigma}(n,s)$.

Also, at each stage $s$, for all $x$, we will assume that the value $\beta_{s}(x)$ is defined to be equal to $\mu_{s}(x)$ unless another definition of $\beta_{s}(x)$ is explicitly given. Moreover, we guarantee in construction that $\mu_{s}(x)\not=\varnothing$ if and only if $\beta_{s}(x)\not=\varnothing$.

The construction is carried out by the simultaneous implementation of the procedures $P(\sigma)$ for all strings $\sigma$ of even length. Each procedure $P(\sigma)$, $\operatorname{lh}(\sigma)=2n+2$, aims at satisfying $R_{e}$ and $M_{e}$, with $e\leq n$, and $P_{n}$ if $\sigma$ is an initial segment of the true path. Without specifying this in what follows, we assume that all numbers defined therein belong to elements of the family $\mathcal{A}$ are of the form $c(x,\sigma)$, where $x\in{𝕅}$ and $\sigma$ is identified with the number whose binary representation it is. In each $P(\sigma)$, we will define the values of $\mu(x)$, where $x$ belongs to some set $N_{\sigma}$. For different strings $\sigma$ and $\tau$, the sets $N_{\sigma}$ and $N_{\tau}$ have empty intersection. Moreover,

$$ \bigcup\limits_{\sigma\in 2^{<{𝕅}}}N_{\sigma}={𝕅}. $$

Thus, the fragments of the construction carried out by some different procedures $P(\sigma)$ do not violate each other, and during their simultaneous work, a desired numbering $\mu$ will be constructed.

Description of $P(\sigma)$ with $\operatorname{lh}(\sigma)=2n+2$. The procedure works stepwise at all stages

$$ s=c(0,\sigma),c(1,\sigma),c(2,\sigma),\ldots. $$

Let $c(u,\sigma)$ be the last stage at which $P(\sigma)$ was interrupted and $u=0$ if it is launched for the first time. For each stage

$$ s=c(u+1,\sigma),c(u+2,\sigma),\dots, $$

we check whether there exists a $\sigma$-stage $t$ such that $c(u,\sigma)<t\leq s$ (i.e., we wait for the first $\sigma$-stage not exceeding $s$ and greater than $c(u,\sigma)$) and denote the first such stage $s$ by $v$ if it exists (otherwise, no actions are performed in the procedure before it is interrupted). Then choose a new number $a_{0}$ (greater that all numbers previously used in the construction and belonging to $\bigcup\nolimits_{e,x}\alpha_{e,v}(x)$) and define

$$ \mu_{v+1}(w_{0})=\beta_{v+1}(w_{0})=\{a_{0}\}, $$

where $w_{0}$ is the least number such that $\mu(w_{0})$ (and hence $\beta(w_{0})$) is empty at stage $v$. Let

$$ R=\{e\leq n:\sigma(2e)=0\},\quad M=\{e\leq n:\sigma(2e+1)=0\}. $$

To guarantee the minimality of $\mu$, for each $e\in M$, with $e>0$, we wait for a stage at which there exists $z$ such that

$$ \varphi_{e-1}(z)=w_{0}. $$

(2)

Then, for each $e\in R$, we wait for a stage at which for some $u_{e}$ we have

$$ \alpha_{e}(u_{e})=\{a_{0}\}, $$

and if such stage exists then we put

$$ f_{e}(w_{0})=g_{e}(w)=u_{e}, $$

where $w$ is the least number at which the value $g_{e}(w)$ is undefined at the previous stage. Given $e\leq n$, choose some new numbers $b^{e}_{0}<b^{e}_{1}$ and put

$$ \mu(x_{e})=\{b^{e}_{0},b^{e}_{1}\}, $$

where $x_{0}$ is the first number at which the value $\mu(x_{0})$ is undefined at the previous stage and $x_{e}=x_{0}+e$ for all $e\leq n$. Furthermore, choose the least $x^{\prime}_{0}$ at which the value $\mu(x^{\prime}_{0})$ is undefined, new numbers $b_{0}<b_{1}$, and put

$$ \mu(x^{\prime}_{0})=\{b_{0},b_{1}\}. $$

After that, for each $e\leq n$, we begin the simultaneous implementation of processes $1$ and $2$. Describe their work for every arbitrarily chosen $e\leq n$.

Process 1. If $e>0$; then, to guarantee the minimality of $\mu$, we wait for a stage at which there exist numbers $z^{e-1}_{e-1},\dots,z^{e-1}_{n}$ such that

$$ (e-1)\in M\Rightarrow\varphi_{e-1}\bigl{(}z^{e-1}_{e-1}\bigr{)}\in\{x^{\prime}_{0},x_{0},\dots,x_{e-1}\}\,\&\,\varphi_{e-1}\bigl{(}z^{e-1}_{i}\bigr{)}=x_{i} $$

(3)

for all $i=e,\dots,n$. Furthermore, if $e=0$ or the desired numbers $z^{e-1}_{e-1},\dots,z^{e-1}_{n}$ are found; then we wait for some stage and numbers $y^{e}_{e},\dots,y^{e}_{n}$ such that, at this stage, we have

$$ e\in R\Rightarrow\alpha_{e}(y^{e}_{i})=\{b^{i}_{0},b^{i}_{1}\}=\mu(x_{i}) $$

for all $i=e,\dots,n$. If $e\in R$ and the desired numbers $y^{e}_{e},\dots,y^{e}_{n}$ are found; then, for the same $i=e,\dots,n$ and all $j<e$, we put

$$ f_{e}(x_{i})=y^{e}_{i},\ f_{e}(x_{j})=y^{e}_{e},\quad g_{e}(w^{\prime}_{i})=y^{e}_{i}, $$

where $w^{\prime}_{0}$ is the least number at which the value $g_{e}(w^{\prime}_{0})$ is undefined at the previous stage and $w^{\prime}_{i}=w^{\prime}_{0}+i$. Define also

$$ f_{e}(x^{\prime}_{0})=y^{e}_{e}. $$

Then wait for a stage $s$, some sets $B_{0}$ and $B$, and pairwise distinct numbers $p_{0}<p_{1}$ and $q_{0}<q_{1}$, for which at stage $s$ we have the conditions

$$ \mu(x^{\prime}_{0})=B_{0}\cup\{p_{0},p_{1}\},\quad\mu(x_{e})=B\cup\{q_{0},q_{1}\}, $$

(4)

$$ \forall k\leq e\,\bigl{[}k\in R\Rightarrow\alpha_{k}\bigl{(}y^{k}_{e}\bigr{)}=\mu(x_{e})\bigr{]}, $$

(5)

$$ \forall b\in B_{0}\,[b<p_{0}]\,\&\,\forall b\in B\,[b<q_{0}], $$

(6)

and then for the new numbers $c_{0}>p_{1}$ and $c_{1}>q_{1}$, we put

$$ \mu_{s+1}(x^{\prime}_{0})=\mu_{s}(x^{\prime}_{0})\cup\{\min(\mu_{s}(x_{e})\setminus\mu_{s}(x^{\prime}_{0}))\}\cup\{c_{0}\}, $$

(7)

$$ \mu_{s+1}(x_{e})=\mu_{s}(x_{e})\cup\{\min(\mu_{s}(x^{\prime}_{0})\setminus\mu_{s}(x_{e}))\}\cup\{c_{1}\}. $$

(8)

For $e$ chosen, we continue the search for a new stage $s$, some new sets $B_{0}$ and $B$, and pairwise distinct numbers $p_{0}<p_{1}$ and $q_{0}<q_{1}$ satisfying (4)–(6), and if they appear, perform actions (7), (8) for new numbers $c_{0}>p_{1}$ and $c_{1}>q_{1}$. Observe that the continuous implementation of these cyclic actions leads to the equality $\mu(x_{e})=\mu(x^{\prime}_{0})$. This finishes the description of process 1.

If, during the action of the procedure, we encounter a $\tau$-stage $t>0$ for which $\tau<_{L}\sigma$ then we initialize it by performing the following:

(1) interrupt its work;

(2) for each $x$ used as an argument for $\mu$ during the action of the procedure, define the value $\mu_{t}(x)$ to be equal to the union of all values $\mu_{t-1}(y)$, where $y$ also was used as an argument for $\mu$ during its action; if the value $a_{0}$ was defined in the procedure, then for each $e\leq n$ after the appearance of a stage at which $a_{0}\in\alpha_{e}(z)$ for some $z$, define $f_{e}(x)=z$ if at the previous stage the value $f_{e}(x)$ is undefined and $g_{e}(w)=z$, where $w$ is the least number at which the value of $g_{e}$ is undefined at the previous stage;

(3) for all $e$, we put

$$ d_{\sigma}(e,t)=\max(\{d_{\rho}(e,t-1):\rho<_{L}\sigma\,\&\,\operatorname{lh}(\rho)=\operatorname{lh}(\sigma)\}\cup\{d_{\rho}(e,t):\rho\prec\sigma\}). $$

This finishes the description of the initialization.

Furthermore, if at some stage we have

$$ \varphi_{n}(w_{0})=w_{0}; $$

(9)

then we initialize the procedures $P(\tau)$ for all such strings $\tau$ of even length such that either $\sigma\prec\tau$ or $\sigma<_{L}\tau$ and put

$$ \mu(w_{0})=\{a_{0}<a_{1}<a_{2}\},\quad\mu(w)=\{a_{0}<a^{\prime}_{1}<a^{\prime}_{2}\}, $$

(10)

$$ \beta(w_{0})=\{a_{0}<a^{\prime}_{1}<a^{\prime}_{2}\},\quad\beta(w)=\{a_{0}<a_{1}<a_{2}\} $$

(11)

for new pairwise distinct numbers $a_{1},a_{2},a^{\prime}_{1},a^{\prime}_{2}$ and the first $w$ for which the value of $\mu(w)$ is undefined at the previous stage. Performing these actions in the construction guarantees the validity of the inequality $\mu\not=(\beta\circ\varphi_{n})$. For each $e\in R$, if, at some stage (of any of the procedures), there appears $x$ such that

$$ \alpha_{e}(x)=\{a_{0}<a^{\prime}_{1}<a^{\prime}_{2}\}; $$

then we put

$$ f_{e}(w)=x,\quad g_{e}(w^{\prime})=x, $$

(12)

where $w^{\prime}$ is the least number at which the value $g_{e}$ is undefined at the previous stage.

Process 2. The actions of the process aim to fulfill the condition

$$ \exists r_{e}\,[\alpha_{e}(r_{e})\in\alpha_{e}(g_{e}({𝕅}))\,\&\,\alpha_{e}(r_{e})\not=\alpha_{e}(g_{e}(\varphi_{d_{\sigma}(e,v)}(r_{e})))] $$

if $e\in R$ is the least element in $R$ such that $\alpha_{e}(u_{e})\not=\mu(w_{0})$ and (14) holds, which in turn aims to satisfy the condition that the numbering $\alpha_{e}$ is not minimal provided that it numerates $\mathcal{A}$ and $\mu\not\leq\alpha_{e}$. If $e\in R$ then we wait for a stage $s\geq v$ at which for all $e^{\prime}\leq e$, if $e^{\prime}\in R$ then the elements $y^{e^{\prime}}_{e^{\prime}},\dots,y^{e^{\prime}}_{n}$ are defined, and if $e^{\prime}>0$ and $(e^{\prime}-1)\in M$ then the elements $z^{e^{\prime}-1}_{e^{\prime}-1},\dots,z^{e^{\prime}-1}_{n}$ are defined and

$$ |\alpha_{e}(u_{e})\setminus\mu(w_{0})|\geq 2. $$

(13)

If such stage $s$ is found then consider the two cases:

(1) The number $e$ is not the least element of $R$ satisfying at some stage $s^{\prime}=v,\dots,s$ condition (13) and the condition

$$ \min D=c(e,d_{\sigma}(e,v)),\ \text{where}\ D=\{c(k,d_{\sigma}(k,v)):k\in R\}. $$

(14)

Then for each $r$ satisfying the condition

$$ \alpha_{e}(r)=\mu(w_{0}) $$

at some of the subsequent stages, we define

$$ g_{e}(w)=r, $$

(15)

where $w$ is the least number at which $g_{e}(w)$ is undefined at the previous stage.

(2) The number $e$ is the least element of $R$ satisfying (13) and (14) at some stage $s^{\prime}=v,\dots,s$. Then, for all remaining $e^{\prime}\in R$ satisfying (13) at one of the stages $s^{\prime}=v,\dots,s$ (with $e^{\prime}$ instead of $e$), we put

$$ d_{\sigma}(e^{\prime},s+1)=d_{\sigma}(e^{\prime},v). $$

(16)

For each $r$ satisfying the condition

$$ \alpha_{e^{\prime}}(r)=\mu(w_{0}) $$

at one of the subsequent stages, we define

$$ g_{e^{\prime}}(w)=r, $$

(17)

where $w$ is the least number at which the value $g_{e^{\prime}}(w)$ is undefined at the previous stage. The implementation of all subsequent actions of process 2 for $e^{\prime}$ is interrupted. Now, define

$$ d_{\sigma}(e,s+1)=d_{\sigma}(e,v)+1 $$

(18)

and initialize the procedures $P(\tau)$ for all strings of even length $\tau$ such that either $\sigma\prec\tau$ or $\sigma<_{L}\tau$. Then we wait for a stage $t$ and, if it has not appeared before, for a number $r_{e}$ for which

$$ \alpha_{e}(r_{e})=\mu(w_{0}) $$

(19)

at this stage. Let $i=d_{\sigma}(e,v)$. If $\varphi_{i,t}(r_{e}){\uparrow}$ and also there exist sets $B_{0}$ and $B$ and pairwise distinct numbers $p_{0}<p_{1}$ and $q_{0}<q_{1}$ such that, at stage $t$, the conditions

$$ \mu(x^{\prime}_{0})=B_{0}\cup\{p_{0},p_{1}\}, $$

(20)

$$ \mu(w_{0})=B\cup\{q_{0},q_{1}\}, $$

(21)

$$ \forall b\in B_{0}\,[b<p_{0}]\,\&\,\forall b\in B\,[b<q_{0}] $$

(22)

are fulfilled then, for new numbers $c_{0}>p_{1}$ and $c_{1}>q_{1}$, we put

$$ \mu_{t+1}(x^{\prime}_{0})=\mu_{t}(x^{\prime}_{0})\cup\{\min\big{(}\mu_{t}(w_{0})\setminus\mu_{t}(x^{\prime}_{0})\big{)}\}\cup\{c_{0}\}, $$

(23)

$$ \mu_{t+1}(w_{0})=\mu_{t}(w_{0})\cup\{\min(\mu_{t}(x^{\prime}_{0})\setminus\mu_{t}(w_{0}))\}\cup\{c_{1}\}. $$

(24)

If $\varphi_{i,t}(r_{e}){\downarrow}\in\operatorname{dom}g_{e}$ then we interrupt the implementation of the actions of the process related to $e$ and put

$$ g_{e}(w)=r_{e}, $$

(25)

where $w$ is the least number at which the value $g_{e}(w)$ is undefined at the previous stage. Otherwise, we return to waiting for a stage $t$ at which (19) holds, and if it appears then we implement the same sequence of actions already for the new $t$. Observe that if $\varphi_{i}(r_{e}){\downarrow}$ and the process is not interrupted then $\alpha_{e}(r_{e})=\mu(w_{0})$. This finishes the description of the work of process 2 and the procedure $P(\sigma)$.

It is immediate from the construction that every two distinct elements in $\mathcal{A}$ are incomparable with respect to inclusion and its every two distinct infinite elements are disjoint and also for every $X\in\mathcal{A}$ there exist only finitely many elements of $\mathcal{A}$ having nonempty intersection with $X$. It follows that $\mathcal{A}$ is discrete. The construction also implies that, in each of the procedures $P(\sigma)$, only finitely many values of the numbering $\mu$ are found and the values found in different procedures do not intersect. Hence, we have condition (1).

Let us show that for each $n$, the requirements $R_{n}$, $M_{n}$, and $P_{n}$ are met. We will need the following assertion:

Lemma 1

For each $n$, if $\alpha_{n}\in H(\mathcal{A})$ then the difference $\mathcal{A}\setminus\alpha_{n}(g_{n}({𝕅}))$ is finite.

Proof

Let $\alpha_{n}\in H(\mathcal{A})$ and $T$ be the true path of the construction. By construction, $g_{n}$ is total. Show that the family $\mathcal{A}\setminus\alpha_{n}(g_{n}({𝕅}))$ is finite. Choose an arbitrary number $m\geq n$ and a string $\sigma$ of length $2m+2$ for which $T\upharpoonright(2n+2)\preceq\sigma$. Consider the implementation of $P(\sigma)$ starting from the least stage $u$ after which it no longer initializes. If there is no such stage then, by item (2) of its initialization, each of the set families $\mathcal{A}$ constructed in its implementation has an $\alpha_{n}$-number belonging to $\operatorname{ran}g_{n}$. Otherwise, the value $u_{n}$ is defined and $u_{n}\in\operatorname{ran}g_{n}$. Also in process $1$, it is guaranteed that

$$ y^{n}_{n},\dots,y^{n}_{m}\in\operatorname{ran}g_{n}. $$

Continuous cyclic checks (4)–(6) and actions (7), (8) implemented in process $1$ lead to the equalities

$$ \alpha(y^{n}_{n})=\mu(x_{e}) $$

for all $e\leq n$ and

$$ \alpha(y^{n}_{n+1})=\mu(x_{n+1}),\dots,\alpha(y^{n}_{m})=\mu(x_{m}). $$

If in the subsequent work of the procedure, equalities (10) are defined then actions (12) guarantee the existence of an $\alpha_{n}$-number of the set $\mu(w)$ belonging to $\operatorname{ran}g_{n}$. Suppose that $\alpha_{n}(u_{n})\not=\mu(w_{0})$. By construction, this is equivalent to the condition $|\alpha_{e}(u_{n})\setminus\mu(w_{0})|\geq 2$. Then, in process $2$, it is guaranteed that either, by actions (15), (17), and (25), there exists an $\alpha_{n}$-number of $\mu(w_{0})$ or, by the continuous cyclic implementation of checks (20)–(22) and actions (23), (24), we have

$$ \alpha_{n}(y^{n}_{n})=\mu(w_{0}). $$

Thus, each of the sets of $\mathcal{A}$ constructed in implementing $P(\sigma)$, where $T\upharpoonright(2n+2)\preceq\sigma$, also belong to the family $\alpha_{n}(g_{n}({𝕅}))$. The difference $\mathcal{A}\setminus\alpha_{n}(g_{n}({𝕅}))$ contains only finitely many sets defined in implementing $P(\tau)$, where $\tau<_{L}T\upharpoonright(2n+2)$. This finishes the proof of the lemma.

Lemma 2

For each $n$, if $\alpha_{n}\in H(\mathcal{A})$ and $\alpha_{n}$ is minimal then $\mu\leq\alpha_{n}$.

Proof

Let $\mathcal{A}\setminus\alpha_{n}(g_{n}({𝕅}))=\{Y_{0},\dots,Y_{k}\}$. Define the numbering $\gamma$ reducible to $\alpha_{n}$, putting for each $x$

$$ \gamma(x)=\begin{cases}Y_{x}&\text{if}\ x\leq k,\cr\alpha_{n}(g_{n}(x-k-1))&\text{if}\ x>k.\end{cases} $$

The construction implies that for all strings $\sigma$ and $\tau$ of even length, there exists a finite limit $\widehat{d}_{\sigma}(e)=\lim\nolimits_{s}d_{\sigma}(e,s)$ and $\widehat{d}_{\sigma}(e)\leq\widehat{d}_{\tau}(e)$ for $\sigma\preceq\tau$. By definitions (16) and (18) of process $2$ for each of the Procedures $P(\sigma)$, if for some $e^{\prime}$, at some stage $s$, we have $d_{\sigma}(e^{\prime},s+1)<d_{\sigma}(e^{\prime},s)$ then there exists $e$ for which

$$ c(e,d_{\sigma}(e,v))\leq c(e^{\prime},d_{\sigma}(e^{\prime},v)),\ d_{\sigma}(e,v)<d_{\sigma}(e,s+1). $$

This and item 3 of the initialization of $P(\sigma)$ imply that for each $e$ we have the limit $\lim\nolimits_{m}\widehat{d}_{T\upharpoonright(2m+2)}(e)$. If $\alpha_{e}({𝕅})=\mathcal{A}$ and this limit is infinite then for any total function $\varphi_{i}$, with account taken of checks (19)–(22) and actions (23), (24), there exists a number $r_{e}$ for which

$$ \gamma(\varphi_{i}(r_{e}))\not=\alpha_{e}(r_{e}) $$

since $\alpha_{e}(r_{e})$ acquires a $\gamma$-number only in action (25). Therefore, $\alpha_{e}\not\leq\gamma$, and hence the numbering $\alpha_{e}$ is not minimal. Let $\alpha_{n}({𝕅})=\mathcal{A}$ and

$$ \lim\limits_{m}\widehat{d}_{T\upharpoonright(2m+2)}(n)=i<\infty. $$

The construction implies that $f_{n}(x)$ is defined for all (but finitely many) $x$. If there exist infinitely many $x\in\operatorname{dom}f_{n}$ for which

$$ \mu(x)\not=\alpha_{n}(f_{n}(x)) $$

then for infinitely many $m$, in the procedure $P(T\upharpoonright(2m+2))$, we have $\mu(w_{0})\not=\alpha_{n}(u_{n})$. Consequently, the fulfillment of actions (18) in the implementation of the second processes of these procedures leads to the inequality

$$ \lim\limits_{m}\widehat{d}_{T\upharpoonright(2m+2)}(n)>i. $$

The so-obtained contradiction finishes the proof of the lemma.

Thus, $R_{n}$ is satisfied for each $n$.

Lemma 3

The numbering $\mu$ is minimal.

Proof

Choose an arbitrary $e>0$ for which $\varphi_{e-1}$ is total and $\mu(\varphi_{e-1}({𝕅}))=\mathcal{A}$. Let

$$ \sigma=T\upharpoonright(2e+2). $$

Then

$$ \bigcup\limits_{\tau<_{L}\sigma}N_{\tau}\quad\text{and}\quad\bigcup\limits_{\tau\prec\sigma}N_{\tau} $$

are finite by the definition of $T$. For every string $\tau$, if the number $x$ is chosen in implementing $P(\tau)$ and after that it initializes at some stage; then, by the first part of item 2 of the initialization, from this $x$, we can effectively point to a finite set consisting of all $y$ with $\mu(y)=\mu(x)$. Since

$$ \mu(\varphi_{e-1}({𝕅}))=\mathcal{A}, $$

for one of such $y$, we have $y\in\operatorname{ran}\varphi_{e-1}$. Note that for each set in $\mathcal{A}$ of the form $\{a_{0}<a^{\prime}_{1}<a^{\prime}_{2}\}$, there exists $z$ for which

$$ \mu(\varphi_{e-1}(z))=\{a_{0}<a^{\prime}_{1}<a^{\prime}_{2}\}. $$

Given $n\geq e$, consider the implementation of the procedure $P(T\upharpoonright(2n+2))$ starting from the stage after which it does not initialize. Now, the reducibility $\mu\leq\mu\circ\varphi_{e-1}$ stems from checks (2), (3), and the equalities

$$ \mu(x_{0})=\dots=\mu(x_{e-1})=\mu(x_{0}^{\prime}), $$

which in turn follows from checks (4)–(6) and actions (7), (8). By the arbitrariness of the choice of $e$, the numbering $\mu$ is minimal. This finishes the proof of the lemma.

Finally, for finishing the proof of the theorem, it remains to notice that due to the implementation of checks (9) and actions (10), (11), $P_{n}$ is satisfied for each $n$.

4. Conclusion

In [2], among other things, the question was formulated of the existence of a family with a unique minimal computable numbering that is neither the least nor positive. To guarantee the nonpositivity of the numbering $\mu$ in the proof of the last theorem, into its construction, it is not hard to integrate a process for meeting the requirements

$$ N_{n}:\eta_{\mu}\not=W_{n},\quad n\in{𝕅}, $$

based on the following strategy: Fixing distinct numbers $x$ and $y$, we begin to consecutively add elements to the sets $\mu(x)$ and $\mu(y)$ so that, at each stage, $\mu(x)$ and $\mu(y)$ are incomparable with respect to inclusion but the greatest $k$ for which $\mu(x)\upharpoonright k=\mu(y)\upharpoonright k$ grows. If in implementing this process, the pair $\langle{}x,y\rangle{}$ is enumerated in $W_{n}$ then we interrupt this work, which leads to the inequality $\mu(x)\not=\mu(y)$.