Proof. First, we show that the family

$$ \begin{align*}\mathcal{A}_1=\{\theta\in\mathcal{P}_1:\theta\ \text{ is infinite or }\ |\theta|=4m\ \text{for some}\ m\}\end{align*} $$

has a computable numbering. Let us fix a strongly computable double sequence of partial functions $\{\psi _{x,s}\}_{x,s\in \mathbb N}$ such that

$$ \begin{align*}\bigcup_s\psi_{x,s}=\varphi_x\,\&\,|\psi_{x,t+1}\setminus\psi_{x,t}|\leqslant 1\end{align*} $$

for all x and t. By the s-m-n theorem, there exists a recursive function f such that for all x and y, each of the following conditions is met:

• • $\varphi _{f(x)}(y)\downarrow $ if and only if there exist $m,s\in \mathbb N$ with $|\psi _{x,s}|=4m$ and $\psi _{x,s}(y)\downarrow $ ;

• • $\varphi _{f(x)}(z)=\psi _{x}(z)$ for each $z\in \mathrm {dom}\,\varphi _{f(x)}$ .

It is not hard to see that the binary p.r. function

$$ \begin{align*}\big\langle x,y\big\rangle\mapsto\varphi_{f(x)}(y)\end{align*} $$

is a computable numbering of $\mathcal {A}_1$ .

Let $\mathcal {A}_0$ be the family of all finite partial functions $\theta \in \mathcal {A}$ such that $|\theta |=4m+2$ for some $m\in \mathbb N$ . It is clear that $\mathcal {A}_0$ has a computable Friedberg numbering. Thus, the families $\mathcal {A}$ , $\mathcal {A}_0$ , and $\mathcal {A}_1$ satisfy the condition of Theorem 3.2. Therefore, $\mathcal {A}$ has a computable Friedberg numbering.

Proof of Theorem 3.1.

We are going to construct a uniformly positive computable sequence of pairwise non-equivalent universal numberings $\{\psi ^n\}_{n\in \mathbb N}$ such that $\varphi \preceq \bigoplus _n\psi ^n$ . Thus, we will obtain that the numbering $\bigoplus _n\psi ^n$ is acceptable and, hence, the Gödel one.

Since by Lemma 3.3 the family $\mathcal {A}$ of all p.r. functions $\theta $ such that either $\theta $ is infinite or $|\theta |$ is even has a computable Friedberg numbering, the family

$$ \begin{align*}\{\theta\in\mathcal{A}: |\theta|>2\}\end{align*} $$

has a computable Friedberg numbering, say $\xi $ , as well. Fix a strongly computable double sequence of partial functions $\{\xi _{x,s}\}_{x,s\in \mathbb N}$ such that $|\xi _{x,s}|>2$ , $\xi _{x,s}\subseteq \xi _{x,s+1}$ and $\bigcup _t\xi _{x,t}=\xi _x$ for all x and s.

In order for any numbering $\psi ^n$ , $n\in \mathbb N$ , to be universal, we will meet the following requirements in its construction:

1. (a) $\psi ^n_0=\varphi _n$ ;

2. (b) $\forall u\,[\xi _u\not =\varphi _n\Rightarrow \exists x\in 2\mathbb N\,[x>0\,\&\,\psi ^n_x=\xi _u]]$ ;

3. (c) for any finite partial function $\pi $ such that $|\pi |$ is odd, $|\pi |>2$ , and $\pi \not =\varphi _n$ there exists $y\in 4\mathbb N+1$ with $\psi ^n_y=\pi $ ;

4. (d) for any finite partial function $\delta $ such that $|\delta |\leqslant 2$ and $\delta \not =\varphi _n$ there exists $y\in 4\mathbb N+3$ with $\psi ^n_y=\delta $ .

Satisfying requirement (a) for each n will also ensure that $\varphi \preceq \bigoplus _n\psi ^n$ .

In order for each of the numberings $\psi ^n$ to be positive uniformly with respect to n, we also construct uniformly with respect to n a p.r. function $\gamma $ such that the numeration equivalence $\eta _{\psi ^n}$ coincides with the r.e. equivalence generated by the binary relation

(1) $$ \begin{align} \{\big\langle y,\gamma(y)\big\rangle:y\in\mathrm{dom}\,\gamma\}. \end{align} $$

We ensure this property by enforcing the following recursive conditions:

• • for every $y\in (2\mathbb N+1)$ ,

  $$ \begin{align*}\gamma(y)\downarrow\Leftrightarrow\gamma(y)\downarrow=0\Leftrightarrow\psi^n_y=\psi^n_0,\end{align*} $$

• • for every positive $x\in 2\mathbb N$ ,

  $$ \begin{align*}\gamma(x)\downarrow\Leftrightarrow\gamma(x)\downarrow\in (4\mathbb N+1),\end{align*} $$

• • for every $y\in (2\mathbb N+1)$ ,

  $$ \begin{align*}\exists z\in (2\mathbb N+1)\,[y\not=z\,\&\,\psi^n_y=\psi^n_z]\Leftrightarrow\gamma(y)\downarrow,\end{align*} $$

• • for every positive $x\in 2\mathbb N$ ,

  $$ \begin{align*}\exists z\in 2\mathbb N\,[x\not=z\,\&\,\psi^n_x=\psi^n_z]\Leftrightarrow\gamma(x)\downarrow\,\&\,\gamma(\gamma(x))\downarrow=0\Leftrightarrow\psi^n_x=\psi^n_0,\end{align*} $$

• • for every positive $x\in 2\mathbb N$ and every $y\in (2\mathbb N+1)$ ,

  $$ \begin{align*}\psi^n_x=\psi^n_y\Leftrightarrow\gamma(x)\downarrow\,\&\,[\gamma(x)=y\,\vee\,\gamma(\gamma(x))\downarrow\,\&\,\gamma(y)\downarrow].\end{align*} $$

Once $\psi ^n$ has been constructed, we will show based on these conditions that its numbering equivalence is generated by relation (1). Additionally, we will provide that for all $n\in \mathbb N$ and $y\in (2\mathbb N+1)$ , $\psi ^n_y$ is finite whenever $\psi ^n_y\not =\varphi _n$ .

We will ensure pairwise incomparability of the numberings $\psi ^n$ , $n\in \mathbb N$ , by the standard diagonalization procedure.

Now we proceed to the simultaneous construction of all the numberings $\psi ^n$ , $n\in \mathbb N$ .

Construction of $\psi ^n$

Stage $0$ . We define $\psi ^n_{0,0}=\varphi _n$ , $\psi ^n_{x,0}=\varnothing $ for each $x>0$ and $\gamma _0=\varnothing $ . Let

$$ \begin{align*}b(x,0)\,{=}\,-1\end{align*} $$

for all $x\in \mathbb N$ . In the construction, we ensure that for every x, if $\lim _sb(x,s)$ exists and $\lim _sb(x,s)\not =\,-1$ , then $\lim _sb(x,s)<\infty $ and $\psi ^n_x=\xi _{\lim _sb(x,s)}$ , and also that for every u with $\xi ^n_u\not =\varphi _n$ there exists x such that $\lim _sb(x,s)=u$ . For all x and s, we assume that $\psi ^n_{x,s+1}=\psi ^n_{x,s}$ , $\gamma _{s+1}(x)=\gamma _s(x)$ , and $b(x,s+1)=b(x,s)$ , unless explicitly stated otherwise.

Stage $s+1$ . 1) At these substages, we provide the positiveness of $\psi ^n$ . If there exists a positive $x\in 2\mathbb N\setminus \mathrm {dom}\,\gamma _s$ such that $\psi ^n_{x,s}\not =\varnothing $ and

(2) $$ \begin{align} \begin{gathered} \max\{k\leqslant s:\psi^n_{x,s}\upharpoonright k = \varphi_{n,s}\upharpoonright k\}>\\ >\max\{k\leqslant s:\exists t<s\,[\psi^n_{x,t}\upharpoonright k = \varphi_{n,t}\upharpoonright k]\} \end{gathered} \end{align} $$

(in this case, we predict that the partial function with the $\psi ^n$ -number x is equal to $\varphi _n$ ), then we choose the least such x (and denote it by $x_0$ ) and some finite partial function $\rho $ of odd cardinality for which $|\rho |>2$ , $\psi _{x_0,s}\subseteq \rho $ , and

(3) $$ \begin{align} \forall z\,[\rho\not=\psi^n_{z,s}], \end{align} $$

and then we define

(4) $$ \begin{align} \psi^n_{x_0,s+1}&=\rho, \end{align} $$

(5) $$ \begin{align} \gamma_{s+1}(x_0)&=y, \end{align} $$

$$ \begin{align*}\psi^n_{y,s+1}=\rho,\ b(x_0,s+1)=\,-1,\end{align*} $$

where y is the least integer with $y\in (4\mathbb N+1)$ and $\psi ^n_{y,s}=\varnothing $ .

For all $y\in (2\mathbb N+1)$ such that $\gamma _s(y)\uparrow $ , $\psi ^n_{y,s}\not =\varnothing $ , and

(6) $$ \begin{align} \psi^n_{y,s}=\varphi_{n,s} \end{align} $$

(it will follow directly from the construction that y is unique), we define

(7) $$ \begin{align} \gamma_{s+1}(y)=0, \end{align} $$

and for all $u\in \mathbb N$ with $\gamma _s(u)\downarrow $ , we set

(8) $$ \begin{align} \psi^n_{u,s+1}=\psi^n_{\gamma(u),s} \end{align} $$

(it will follow directly from the construction that $\psi ^n_{u,s}\subseteq \psi ^n_{\gamma (u),s}$ ).

2) At these substages, we meet requirement $(b)$ . If

(9) $$ \begin{align} l(s)\not\in\{b(x,s):x,s\in\mathbb N\}, \end{align} $$

then we choose the least positive integer $x\in 2\mathbb N$ such that

$$ \begin{align*}\psi^n_{x,s}=\varnothing\,\&\,b(x,s)=\,-1\,\&\,\gamma_s(x)\uparrow,\end{align*} $$

and if in addition $x_0$ is defined, then $x\not =x_0$ , and define

$$ \begin{align*}b(x,s+1)=l(s).\end{align*} $$

For every $x\in 2\mathbb N$ such that $b(x,s+1)\not =\,-1$ , we set

(10) $$ \begin{align} \psi^n_{x,s+1}=\xi_{b(x,s),s+1} \end{align} $$

(it will follow directly from the construction that $\psi ^n_{x,s}\subseteq \xi _{b(x,s),s}$ ).

3) At these substages, we meet requirement $(c)$ . Let $\{\pi _d\}_{d\in \mathbb N}$ be a strongly computable sequence of all partial functions $\pi $ such that $|\pi |$ is odd and $|\pi |>2$ . We choose the least integer d such that

(11) $$ \begin{align} \forall z\,[\psi^n_{z,s}\not=\pi_d] \end{align} $$

and if in addition $x_0$ is defined, then $\pi _d\not =\psi ^n_{x_0,s+1}$ , and the least $y\in (4\mathbb N+1)$ with $\psi ^n_{y,s}=\varnothing $ . Then we define

(12) $$ \begin{align} \psi^n_{y,s+1}=\pi_d. \end{align} $$

4) At these substages, we meet requirement $(d)$ . Let $\{\delta _d\}_{d\in \mathbb N}$ be a strongly computable sequence of all partial functions $\delta $ with $|\delta |\leqslant 2$ . We choose the least $y\in (4\mathbb N+3)$ satisfying the condition

(13) $$ \begin{align} \psi^n_{y,s}=\varnothing\,\&\,[\varphi_{n,s}\not=\varnothing\Rightarrow\exists z<y\,[z\in(4\mathbb N+3)\,\&\,\psi^n_{z,s}=\varnothing]], \end{align} $$

and the least d such that $\delta _d\not =\varnothing $ and

(14) $$ \begin{align} \forall z\,[\delta_d\not=\psi^n_{z,s}], \end{align} $$

and then we define

(15) $$ \begin{align} \psi^n_{y,s+1}=\delta_d. \end{align} $$

5) At these substages, we ensure that the condition $\psi ^n\not \preceq \psi ^m$ holds for all $m>n$ . For all $m>n$ , e and i for which there exist y and z satisfying the conditions

(16) $$ \begin{align} \begin{gathered} \psi^n_{y,s}=\psi^m_{z,s}=\{\big\langle 0,c(n,m,e,i)\big\rangle\}\not=\varphi_{n,s}\,\&\,\varphi_{e,s}(y)=z,\\ \forall y'[y'\not=y\Rightarrow\varphi_{e,s}(y')\not=z], \end{gathered} \end{align} $$

we choose some d with

(17) $$ \begin{align} |\delta_d|=2\,\&\,\forall x\,[\delta_d\not=\psi^n_{x,s}]\,\&\,\delta_d(0)=c(n,m,e,i) \end{align} $$

and define

(18) $$ \begin{align} \psi^n_{y,s+1}=\delta_d. \end{align} $$

End of construction

At the end of the construction we define $\psi ^n_x=\bigcup _s\psi ^n_{x,s}$ for each x and $\gamma =\bigcup _s\gamma _s$ . It follows directly from the construction that for all x, $\psi ^n_x$ is a partial function.

Let us fix an arbitrary n and show that the constructed numbering $\psi ^n$ is the required one.

Proof. Since at the beginning of the construction we define

$$ \begin{align*}\psi^n_{0,0}=\varphi_n,\end{align*} $$

requirement $(a)$ is met.

Now we show that requirement $(b)$ is met as well. Let us choose an arbitrary u with $\xi _u\not =\varphi _n$ . Thus, there exist only finitely many s satisfying the inequality

$$ \begin{align*}\max\{k\leqslant s:\xi_{u,s}\upharpoonright k = \varphi_{n,s}\upharpoonright k\}> \max\{k\leqslant s:\exists t<s\,[\xi_{u,t}\upharpoonright k = \varphi_{n,t}\upharpoonright k]\}.\end{align*} $$

It follows that there exists s satisfying (9) such that $l(s)=u$ and at no stage greater than $s+1$ does inequality (2) hold, where $x\in 2\mathbb N$ is an integer with $b(x,s+1)=l(s)$ . Thus, assignments (10) of the construction ensure that

$$ \begin{align*}\psi^n_x=\xi_u.\end{align*} $$

Further, let $\pi $ be a finite partial function such that $|\pi |$ is odd, $|\pi |>2$ , and $\pi \not =\varphi _n$ . Since $\pi \not =\varphi _n$ , there exist only finitely many s with

$$ \begin{align*}\pi=\varphi_{n,s}.\end{align*} $$

Thus, assignments (12) of the construction ensure that there are integers s and $y\in (4\mathbb N+1)$ such that

$$ \begin{align*}\psi^n_{y,s+1}=\pi\end{align*} $$

and at no stage greater than $s+1$ is condition (6) met with this y. Therefore, $\psi ^n_y=\pi $ . Hence, requirement (c) is satisfied.

Finally, checks (13), (14) and assignments (15) of the construction provide that requirement (d) is also satisfied (it is easy to see that substages $5$ of the construction do not affect the satisfaction of requirement (d)).

Proof. The assignments (5), (7), and (8) guarantee that $\eta \subseteq \eta _{\psi ^n}$ , where $\eta $ is the r.e. equivalence on $\mathbb N$ generated by the binary relation (1).

Let us show that the reverse inclusion also holds. To do this, we choose an arbitrary pair of different integers $z_0$ and $z_1$ with $\psi ^n_{z_0}=\psi ^n_{z_1}$ and consider the following four cases.

i) $z_0$ and $z_1$ are both odd. In this case, checks (3), (11), (14), and (6) as well as assignment (7) ensure that if $\psi ^n_{z_0}=\psi ^n_{z_1}$ , then $\big \langle z_0,0\big \rangle \in \eta $ and $\big \langle z_1,0\big \rangle \in \eta $ . Therefore, $\big \langle z_0,z_1\big \rangle \in \eta $ .

ii) $z_0$ and $z_1$ are both positive and even. Since $\xi $ is a Friedberg numbering, the equality $\psi ^n_{z_0}=\psi ^n_{z_1}$ can only be forced by assignments (4) and (5) of the construction. Since $z_0\not =z_1$ and $\psi ^n_{z_0}=\psi ^n_{z_1}$ , checks (6) and assignments (7) ensure that $\gamma (z_j)\downarrow $ and $\gamma (\gamma (z_j))\downarrow =0$ , $j=0,1$ . Therefore, $\big \langle z_0,z_1\big \rangle \in \eta $ .

iii) $z_0$ is odd and $z_1$ is positive and even. Let us show that for any even integer $x>0$ with $\gamma (x)\uparrow $ there exists y such that

$$ \begin{align*}\psi^n_x=\xi_y\not=\varphi_n.\end{align*} $$

Indeed, if $\gamma (x)\uparrow $ , then at no stage of the construction does assignment (5) hold, where $x_0=x$ . Hence, at no stage of the construction does inequality (2) hold. Thus, $\psi ^n_x\not =\varphi _n$ . In addition, the second substages of the construction stages ensure that the limit $\lim _xb(x,s)$ exists and is finite, and that $\psi ^n_x=\xi _{\lim _xb(x,s)}$ . Hence,

$$ \begin{align*}\xi_{\lim_xb(x,s)}=\psi^n_x\not=\psi^n_{z_0}.\end{align*} $$

Therefore, $\gamma (z_1)\downarrow $ . If $\gamma (z_1)=z_0$ , then obviously $\big \langle z_0,z_1\big \rangle \in \eta $ . Suppose that $\gamma (z_1)\not =z_0$ . Then there exists $y\in (4\mathbb N+1)$ such that $\gamma (z_1)=y$ . Since

$$ \begin{align*}\psi^n_y=\psi^n_{z_1}=\psi^n_{z_0},\end{align*} $$

we have $\big \langle y,0\big \rangle \in \eta $ and $\big \langle z_0,0\big \rangle \in \eta $ (see case i). Since $\gamma (z_1)=y$ , we have $\big \langle z_0,z_1\big \rangle \in \eta $ .

iv) $z_0=0$ and $z_1>0$ . Then checks (6) and assignments (7) ensure that $\big \langle z_0,z_1\big \rangle \in \eta $ .

Thus, $\eta _{\psi ^n}=\eta $ . Since $\eta $ is r.e. uniformly with respect to n, $\psi ^n$ is positive uniformly with respect to n.

Finally, checks (16), (17) and assignments (18) ensure that $\psi ^n\not \preceq \psi ^m$ for each $m>n$ . Since $\psi ^n$ is minimal, it is not comparable to any numbering $\psi ^m$ , where $m>n$ . This completes the proof of the theorem.

Proof. Since the degree of A is hyperimmune, there exists a function $h\leqslant _T A$ that is not dominated by any recursive function (cf. Miller and Martin [Reference Miller and Martin18]).

Fix an arbitrary n. To define an A-computable Friedberg numbering of the family $\mathcal {A}=\mathcal {I}\setminus \{\varphi _n\}$ , we construct uniformly with respect to n an A-computable Friedberg numbering of the family

$$ \begin{align*}\mathcal{A}_0=\{\theta\in\mathcal{I}:|\theta|\ \text{even}\}\setminus\{\varphi_n\}\end{align*} $$

and an A-computable numbering of the family

$$ \begin{align*}\mathcal{A}_1=\{\theta\in\mathcal{I}:\theta\ \text{infinite or}\ |\theta|\ \text{odd}\}\setminus\{\varphi_n\},\end{align*} $$

and then apply (the relativized) Theorem 3.2.

To define an A-computable Friedberg numbering of $\mathcal {A}_0$ , we choose a strongly computable injective sequence $\{g_i\}_{i\in \mathbb N}$ of all finite partial functions $g\in \mathcal {I}$ such that either $g=\varnothing $ or $g(|g|-1)\not =0$ . Let us fix an arbitrary i and show that the family $\mathcal {B}_i$ of all partial functions $\theta \in \mathcal {A}_0$ satisfying the condition

(19) $$ \begin{align} g_i\subseteq\theta\,\&\,\forall x\in\mathrm{dom}\,\theta\,[x\geqslant |g_i|\Rightarrow\theta(x)=0] \end{align} $$

has an A-computable Friedberg numbering. To this end, first construct its computable (not necessarily Friedberg one) numbering $\xi ^i$ . In this construction, we will use Kalimullin’, Khoussainov’, and Melnikov’s technique [Reference Kalimullin, Khoussainov and Melnikov9] of constructing a non-limitwise monotonic sequence of sets that is limitwise monotonic in each hyperimmune degree. Let $\{f_x\}_{x\in \mathbb N}$ be a strongly computable sequence of all finite partial functions $f\in \mathcal {I}$ such that $g_i\subseteq f$ , $|f|$ is even, and $f(y)=0$ for each y with $|g_i|\leqslant y<|f|$ . For arbitrary $x,u\in \mathbb N$ and $y<|f_x|$ , we define

$$ \begin{align*}\xi^i(c(x,u),y)=f_x(y). \end{align*} $$

Now given an integer x and an even integer $z\geqslant |f_x|$ , assume by induction that $\xi ^i(c(x,u),y)\downarrow $ for all $y<z$ . If there exists $s\geqslant u$ such that

(20) $$ \begin{align} \xi^i_{c(x,u)}\upharpoonright z=\varphi_{n,s}, \end{align} $$

then we fix the least s satisfying (20) and if

(21) $$ \begin{align} \varphi_{n,h(z/2)}\subseteq\varphi_{n,s}, \end{align} $$

then we define

$$ \begin{align*}\xi^i(c(x,u),z+j)=0,\ j=0,1. \end{align*} $$

Otherwise, we put $\xi ^i(c(x,u),y)\uparrow $ for each $y\geqslant z$ .

Let us show that $\xi ^i$ is a numbering of $\mathcal {B}_i$ . If $\theta \in \mathcal {B}_i$ , then there exist x and u such that $\theta =f_x$ and $f_x\not =\varphi _{n,s}$ for each $s\geqslant u$ . Therefore, $\xi ^i_{c(x,u)}=\theta $ . Now we take arbitrary integers x and u and show that $\xi ^i_{c(x,u)}\in \mathcal {B}_i$ . It follows directly from the definition of the numbering $\xi ^i$ that if the partial function $\xi ^i_{c(x,u)}$ is finite, then $\xi ^i_{c(x,u)}\in \mathcal {B}_i$ . Suppose, for the sake of a contradiction, that $\xi ^i_{c(x,u)}$ is infinite. Hence, for every even integer $z\geqslant |f_x|$ there exists $s\geqslant u$ satisfying (20) and the least $s\geqslant u$ satisfying (20) satisfies (21) as well. Therefore, $h(z/2)$ is less than the least t with

(22) $$ \begin{align} \varphi_{n,t}\not\subseteq\varphi_{n,s}. \end{align} $$

(Since $\xi ^i_{c(x,u)}$ is infinite, for every even integer $z\geqslant |f_x|$ there exists s satisfying (20). Hence, $\varphi _n$ is infinite as well. Therefore, for every s there exists t satisfying (22).) Thus, h is dominated by a recursive function. That is a contradiction. To show that $\mathcal {B}_i$ has an A-computable Friedberg numbering, we define an A-limitwise monotonic function F by letting

$$ \begin{align*}F(w)=|\xi_w|-|g_i| \end{align*} $$

for each w. Using Theorem 4.2 we take an injective A-limitwise monotonic function G such that $\mathrm {ran}\,G=\mathrm {ran}\,F$ . Now we define an A-computable numbering $\psi ^i$ of the family $\mathcal {B}_i$ as follows:

$$ \begin{align*}\psi^i(w,y)= \begin{cases} g_i(y), & \text{if}\ y<|g_i|,\\ 0, & \text{if}\ |g_i|\leqslant y\leqslant G(w) \end{cases} \end{align*} $$

for all w and y. Since G is injective, $\psi ^i$ is a Friedberg numbering.

Since the sequence $\{g_i\}_{i\in \mathbb N}$ is injective, the direct sum $\bigoplus _i\psi ^i$ is an A-computable Friedberg numbering of the family $\mathcal {A}_0$ . It is similarly proved that for any i, the family of all finite functions $\theta \in \mathcal {A}_1$ satisfying (19) also has an A-computable numbering, say, $\tau ^i$ .

Next, for a given i, let $f_i$ be a total function satisfying the condition

$$ \begin{align*}g_i\subseteq f_i\,\&\,\forall y\geqslant |g_i|\,[f_i(y)=0].\end{align*} $$

It is straightforward to prove that there exists a binary partial A-recursive function $\upsilon ^i$ such that for every x,

$$ \begin{align*}\upsilon^i_{2x+1}=\tau^i_x,\end{align*} $$

$$ \begin{align*}\upsilon^i_{2x}=f_i,\ \text{if}\ \forall s\,[\varphi_{n,s}\upharpoonright x\not=f_i\upharpoonright x],\end{align*} $$

$$ \begin{align*}\upsilon^i_{2x}=\upsilon^i_{2z+1}\ \text{for some}\ z,\ \text{if}\ \exists s\,[\varphi_{n,s}\upharpoonright x=f_i\upharpoonright x].\end{align*} $$

It is clear that $\upsilon ^i$ is an A-computable numbering of the family of all partial functions $\theta \in \mathcal {A}_1$ satisfying (19).

Thus, the direct sum $\bigoplus _i\upsilon ^i$ is an A-computable numbering of the family $\mathcal {A}_1$ . Since the sequence $\{g_i\}_{i\in \mathbb N}$ is injective, $\bigoplus _i\psi ^i$ is an A-computable Friedberg numbering of the family $\mathcal {A}_0$ . Hence, by (the relativized) Theorem 3.2, the family $\mathcal {A}$ has an A-computable Friedberg numbering.

Taking into account the uniformity of Kummer’s and Harris’ theorems as well as the uniformity of all constructions performed in this proof we obtain that the required numbering of the family $\mathcal {A}$ can be constructed uniformly with respect to n.

Proof. First we show that the family $\mathcal {P}_1\setminus \mathcal {I}$ has a computable numbering. Note that

$$ \begin{align*}\mathcal{P}_1\setminus\mathcal{I}=\{\theta\in\mathcal{P}_1:\exists y\in\mathrm{dom}\,\theta\exists z<y\,[\theta(z)\uparrow]\,\vee\,\exists^{\infty}y\,[\theta(y)\downarrow\not=0]\}.\end{align*} $$

Since the set

$$ \begin{align*}\{e:\exists y>0\,[\varphi_e(y)\downarrow]\}\end{align*} $$

is r.e., the family

$$ \begin{align*}\{\theta\in\mathcal{P}_1:\exists y>0\,[\theta(y)\downarrow]\}\end{align*} $$

has a computable numbering, say, $\xi $ . Therefore, there exists a strongly computable double sequence of partial functions $\{\xi _{x,s}\}_{x,s\in \mathbb N}$ such that

$$ \begin{align*}\xi_{x,s}\subseteq\xi_{x,s+1}\,\&\,\xi_x=\bigcup_t\xi_{x,t},\end{align*} $$

(23) $$ \begin{align} \exists y\in\mathrm{dom}\,\xi_{x,s}\exists z<y\,[\xi_{x,s}(z)\uparrow] \end{align} $$

for all x and s. Thus, $\xi _{x,s}\in \mathcal {P}_1\setminus \mathcal {I}$ for all x and s.

Now we construct a computable numbering $\psi $ of the family $\mathcal {P}_1\setminus \mathcal {I}$ . Let $\gamma $ be a computable numbering of the family of all finite partial functions belonging to $\mathcal {P}_1\setminus \mathcal {I}$ . For all x and y we define

$$ \begin{align*}\psi(2x+1,y)=\gamma_x(y).\end{align*} $$

Next, for every x, we define the r.e. set

$$ \begin{align*}B_x=\{s>0:\exists y\in\mathrm{dom}\,\xi_s\setminus\xi_{s-1}\,[\xi_{x,s}(y)\not=0]\}\end{align*} $$

and put

$$ \begin{align*}\psi_{2x}=\bigcup_{s\in B_x}\xi_{x,s}.\end{align*} $$

It is clear that for every x, the set $B_x$ is infinite if and only if $\xi _x$ is infinite and $\xi _x\not \in \mathcal {I}$ . In addition, given the condition (23), we have that for every x, if $\psi _{2x}$ is finite, then $\psi _{2x}\not \in \mathcal {I}$ as well. Thus, since $\psi _{2x+1}=\gamma _x$ for each x, $\psi $ is a computable numbering of the family $\mathcal {P}_1\setminus \mathcal {I}$ .

Now we define an A-computable numbering $\upsilon $ of the family

$$ \begin{align*}\mathcal{A}=\mathcal{P}_1\setminus(\mathcal{I}\cup\{\varphi_n\}).\end{align*} $$

To this end, for all x and u, we define by induction a sequence of p.r. functions $\{\upsilon _{c(x,u),s}\}_{s\in \mathbb N}$ by letting

$$ \begin{align*}\upsilon_{c(x,u),s}(y)= \begin{cases} \psi_x(y), & \text{if}\ \forall t<s\,[u\leqslant t\Rightarrow\varphi_{n,t}\upharpoonright u\not=\upsilon_{c(x,u),t}\upharpoonright u],\\ \chi_A(y/2), & \text{if}\ \exists t<s\,[u\leqslant t\,\&\,\varphi_{n,t}\upharpoonright u=\upsilon_{c(x,u),t}\upharpoonright u]\,\&\\ & \&\,\bigcup_{t<s}\upsilon_{c(x,u),t}=\varphi_{n,s}\,\&\\ & \&\, y\in 2\mathbb N\,\&\,y>|\bigcup_{t<s}\upsilon_{c(x,u),t}|,\\ 0, & \text{if neither of the previous two cases is true},\\ & \mathrm{dom}\,\Big(\bigcup_{t<s}\upsilon_{c(x,u),t}\Big)\ \text{is an initial segment of}\ \mathbb N,\ \text{and}\\ & y>|\bigcup_{t<s}\upsilon_{c(x,u),t}|,\\ \uparrow, & \text{otherwise}, \end{cases} \end{align*} $$

for all s and $y\leqslant s$ , where $\{\psi _{x,s}\}_{x,s\in \mathbb N}$ is a non-decreasing (under inclusion) in s strongly computable double sequence of partial functions such that $\bigcup _s\psi _{x,s}=\psi _x$ for each x. Next, for all x and y, we define

$$ \begin{align*}\upsilon(x,y)=\big(\bigcup_s\upsilon_{x,s}\big)(y).\end{align*} $$

It is clear that for every x with $\varphi _n\not =\psi _x$ there exists u such that $\upsilon _{c(x,u)}=\psi _x$ . Let us show that $\upsilon _{c(x,u)}\in \mathcal {A}$ for all x and u. If for every s we have

$$ \begin{align*}\forall t<s\,[u\leqslant t\Rightarrow\varphi_{n,t}\upharpoonright u\not=\upsilon_{c(x,u),t}\upharpoonright u],\end{align*} $$

then $\varphi _n\not =\psi _x=\upsilon _{c(x,u)}\in \mathcal {A}$ . Otherwise, since A is not recursive, $\upsilon _{c(x,u)}$ is finite and $\upsilon _{c(x,u)}\not =\varphi _n$ . By the definition of $\upsilon _{c(x,u)}$ , we also have that $\upsilon _{c(x,u)}\not \in \mathcal {I}$ . Thus, in this case as in the previous one we also have $\upsilon _{c(x,u)}\in \mathcal {A}$ .

Taking into account the uniformity of all constructions performed in the proof we obtain that the required numbering of the family $\mathcal {A}$ can be constructed uniformly with respect to n.

Proof of Theorem 4.1.

Suppose A is a set of hyperimmune degree. By Lemmas 4.3 and 4.4, for every n, we can construct uniformly with respect to n an A-computable Friedberg numbering $\lambda ^n$ of the family

$$ \begin{align*}\mathcal{A}^n_0=\mathcal{I}\setminus\{\varphi_n\}\end{align*} $$

and an A-computable numbering $\mu ^n$ of

$$ \begin{align*}\mathcal{A}^n_1=\mathcal{P}_1\setminus(\mathcal{I}\cup\{\varphi_n\}).\end{align*} $$

Since $\mathcal {A}^n_0\cap \mathcal {A}^n_1=\varnothing $ and

$$ \begin{align*}\mathcal{P}_1\setminus\{\varphi_n\}=\mathcal{A}^n_0\cup\mathcal{A}^n_1,\end{align*} $$

by Theorem 3.2, uniformly with respect to $\lambda ^n$ and $\mu ^n$ one can construct an A-computable Friedberg numbering $\xi ^n$ of the family $\mathcal {P}_1\setminus \{\varphi _n\}$ . Hence, for every n, the binary partial function

$$ \begin{align*}\upsilon^n(x,y)= \begin{cases} \xi^n(x-1,y), & \text{if}\ x>0,\\ \varphi_n(y), & \text{if}\ x=0,\ x,y\in\mathbb N, \end{cases} \end{align*} $$

is a universal A-computable (uniformly with respect to n) Friedberg numbering. Since $\upsilon ^n_0=\varphi _n$ for each n, the direct sum $\bigoplus _n\upsilon ^n$ is a programmable numbering.

Now based on the sequence $\{\upsilon ^n\}_{n\in \mathbb N}$ we construct an A-computable sequence of universal Friedberg numberings $\{\psi ^n\}_{n\in \mathbb N}$ such that $\psi ^n_0=\varphi _n$ for each n which for all n, m, and e, satisfies the following requirement:

$$ \begin{align*}P_{c(n,m,e)}:n<m\,\&\,(\varphi_e\ \text{is total})\Rightarrow\psi^n\ \text{is not reducible to}\ \psi^m\ \text{via}\ \varphi_e.\end{align*} $$

Thus, we obtain that for $n\not =m$ , the numberings $\psi ^n$ and $\psi ^m$ are not comparable.

To guarantee the universality and Friedbergness of the numberings $\psi ^n$ , $n\in \mathbb N$ , in the construction, we will define a recursive function a such that for all n and x there exists a finite limit $\widehat {a}(n,x)=\lim _sa(n,x,s)$ and

$$ \begin{align*}\psi^n_x=\upsilon^n_{\widehat{a}(n,x)}.\end{align*} $$

We will also ensure in the construction that for every n, the function $x\mapsto \widehat {a}(n,x)$ will be bijective.

We will also define a standard for finite injury priority constructions recursive restraint function r.

Now we fix a non-decreasing in s strongly A-computable double sequence of partial functions $\{\upsilon _{x,s}\}_{x,s\in \mathbb N}$ such that $\bigcup _t\upsilon _{x,t}=\upsilon _x$ and $\upsilon _{x,s}=\varnothing $ for all x and $s\leqslant x$ , and proceed to the construction.

Construction of $\{\psi ^n\}_{n\in \mathbb N}$

Stage $0$ . For all $x>0$ and $n,m,e\in \mathbb N$ , we define $\psi ^n_{0,0}=\varphi _n$ , $\psi ^n_{x,0}=\varnothing $ , $r(n,m,e,s)=0$ , and $a(n,x,0)=x$ . For all n, m, e, x, and s, we denote by $R(n,m,e,s)$ the greatest element of the set

$$ \begin{align*}\{r(l,k,d,s):c(l,k,d,s)<c(n,m,e,s)\}\end{align*} $$

(we set $R(n,m,e,s) = 0$ if this set is empty). For all n, m, e, x, and s, we assume that $\psi ^n_{x,s+1}=\psi ^n_{x,s}$ , $r(n,m,e,s+1)=r(n,m,e,s)$ , and $a(n,x,s+1)=a(n,x,s)$ unless explicitly stated otherwise.

Stage $s+1=2c(n,m,e,i)+1$ . At these stages, we meet the requirement $P_{c(n,m,e)}$ . If $m\leqslant n$ , then we immediately proceed to the next stage. Suppose that $n<m$ and $r(n,m,e,s)=0$ . If there exists x such that

$$ \begin{align*}x>R(n,m,e,s)\,\&\,\varphi_{e,s}(x)\downarrow>R(n,m,e,s), \end{align*} $$

then we fix the least x satisfying these inequalities and choose some $u>x$ and $v>\varphi _e(x)$ for which

$$ \begin{align*}\psi^n_{u,s}=\psi^m_{v,s}=\varnothing\end{align*} $$

and there exist t and y with

(24) $$ \begin{align} \psi^n_{x,s}\subseteq\upsilon^n_{a(n,u,s),t}\,\&\,\psi^m_{\varphi_e(x),s}\subseteq\upsilon^m_{a(m,v,s),t}, \end{align} $$

$$ \begin{align*}\upsilon^n_{a(n,u,s),t}(y)\downarrow\not=\upsilon^m_{a(m,v,s),t}(y)\downarrow,\end{align*} $$

and then define

$$ \begin{align*}\psi^n_{x,s+1}=\upsilon^n_{a(n,u,s),t},\end{align*} $$

$$ \begin{align*}a(n,x,s+1)=a(n,u,s),\ a(n,u,s+1)=a(n,x,s),\end{align*} $$

$$ \begin{align*}\psi^m_{\varphi_e(x),s+1}=\upsilon^n_{a(n,v,s),t},\end{align*} $$

$$ \begin{align*}a(n,\varphi_e(x),s+1)=a(n,v,s),\ a(n,v,s+1)=a(n,\varphi_e(x),s).\end{align*} $$

Thus, $\psi ^n_{x,s+1}(y)\downarrow \not =\psi ^m_{\varphi _e(x),s+1}(y)\downarrow $ . Set

(25) $$ \begin{align} r(m,n,e,s+1)=\max\{u,v\}. \end{align} $$

Stage $s+1=2c(n,x,i)+2$ . At these stages, we provide that $\psi ^n_x=\upsilon ^n_{\widehat {a}(n,x)}$ . We define $\psi ^n_{x,s+1}=\psi ^n_{x,s}\cup \upsilon ^n_{a(n,x,s),s+1}$ (note that checks (24) guarantee that $\psi ^n_{x,s}\cup \upsilon ^n_{a(n,x,s),s+1}$ is a partial function).

End of construction

By a standard finite injury priority argument, we obtain that for all n, m, and e there exists a finite limit $\lim _sr(n,m,e,s)=\widehat {r}(n,m,e)$ . It follows that for all n, m, and e there also exists a finite limit $\lim _sR(n,m,e,s)=\widehat {R}(n,m,e)$ .

Assignments (25) ensure that for all n and x there exists a finite limit

$$ \begin{align*}\lim_sa(n,x,s)=\widehat{a}(n,x).\end{align*} $$

It follows directly from the construction that for every n, the function $x\mapsto \widehat {b}(n,x)$ is bijective and that for all n and x, the equalities $\psi ^n_x=\upsilon ^n_{\widehat {b}(n,x)}$ and $\widehat {b}(n,0)=0$ hold. Therefore, the direct sum $\bigoplus _n\psi _n$ is programmable and for every n, $\psi ^n$ is a universal Friedberg numbering.

Let us show that for all m, n, and e, the requirement $P_{c(n,m,e)}$ is met. Indeed, if $n<m$ , $\varphi _e$ is total, and $\psi ^n\preceq \psi ^m$ via $\varphi _e$ , then since $\psi ^n$ is universal, there exists x with

$$ \begin{align*}x>\widehat{R}(n,m,e)\,\&\,\varphi_{e}(x)\downarrow>\widehat{R}(n,m,e).\end{align*} $$

Thus, stages $s+1=2c(n,m,e,i)$ , $i\in \mathbb N$ , of the construction provide that $\psi ^n_{x}(y)\downarrow \not =\psi ^m_{\varphi _e(x)}(y)\downarrow $ for some y. Therefore, $P_{c(n,m,e)}$ is met.

Proof. Let $\{\xi ^n\}_{n\in \mathbb N}$ be an arbitrary computable sequence of Friedberg numberings of the family $\mathcal {A}$ and let $\tau $ and $\upsilon $ be its computable numberings with $\tau \not \preceq \upsilon $ . To prove that the direct sum $\bigoplus _n\xi ^n$ is not $\mathcal {A}$ -acceptable, we define a numbering $\psi $ of some subfamily $\mathcal {A}$ such that $\psi \not \preceq \bigoplus _n\xi ^n$ . Then we will obtain that $\tau \oplus \psi \not \preceq \bigoplus _n\xi ^n$ . Since $\tau \oplus \psi $ is a numbering of the entire family $\mathcal {A}$ , it will be proved that $\bigoplus _n\xi ^n$ is not $\mathcal {A}$ -acceptable.

Fix strongly computable non-decreasing in s sequences of partial functions $\{\xi ^n_{x,s}\}_{n,x,s\in \mathbb N}$ , $\{\tau _{x,s}\}_{x,s\in \mathbb N}$ , and $\{\upsilon _{x,s}\}_{x,s\in \mathbb N}$ such that

$$ \begin{align*}\xi^n_x=\bigcup_t\xi^n_{x,s}\,\&\,\tau_x=\bigcup_t\tau_{x,s}\,\&\,\upsilon_x=\bigcup_t\upsilon_{x,s}\end{align*} $$

for all n, x, and s.

Now we choose arbitrary integers e, x and define a partial function $\psi _{c(e,x)}$ . To do this, we construct a non-decreasing in s strongly computable sequence of partial functions $\{\psi _{c(e,x),s}\}_{s\in \mathbb N}$ and then define $\psi _{c(e,x)}=\bigcup _s\psi _{c(e,x),s}$ .

Given s, consider the following three cases:

i) $\varphi _{e,s}(c(e,x))\uparrow $ . In this case, we define $\psi _{c(e,x),s}=\tau _{x,s}$ .

ii) $\varphi _{e,s}(c(e,x))\downarrow \,\&\,\forall w<s\,[\varphi _{e,w}(c(e,x))\uparrow ]$ . In this case, we also define $\psi _{c(e,x),s}=\tau _{x,s}$ and (uniformly with respect to x and s) fix integers u and $t>s$ such that $\tau _{x,s}\subseteq \upsilon _{u,t}$ .

iii) The previous two cases do not hold (note that then $s>0$ ). In this case, we choose the least $p>\max \{s,t\}$ satisfying one of the following conditions:

1. 1) $\tau _{x,p}\upharpoonright s=\upsilon _{u,p}\upharpoonright s$ ;

2. 2) there exists $v\leqslant p$ such that $v\not =r(\varphi _e(c(e,x)))$ and $\psi _{c(e,x),s-1}\subseteq \xi ^n_{v,p}$ , where $n=l (\varphi _e(c(e,x)))$ .

(Below we will show that such p always exists.) If p satisfies the first condition, then we define

$$ \begin{align*}\psi_{c(e,x),s}=\tau_{x,s}\upharpoonright s.\end{align*} $$

Otherwise, for every $q\geqslant s$ we define

$$ \begin{align*}\psi_{c(e,x),q}=\xi^n_{v,\max\{p,q\}}\end{align*} $$

and complete the construction of the sequence $\{\psi _{c(e,x),q}\}_{q\in \mathbb N}$ .

Now we show that for all e, x, and s satisfying the condition of case iii, there necessarily exists $p>\max \{s,t\}$ satisfying one of conditions $1$ and $2$ . If $\tau _x=\upsilon _u$ , then when considering case iii there always exists an arbitrarily large integer p satisfying condition 1. Next, suppose that there are integers e, x, and s satisfying the condition of case iii for which the desired p does not exist. For given e and x, we fix the least such s. It follows directly from the definition of the partial function $\psi _{c(e,x)}$ that

$$ \begin{align*}\psi_{c(e,x),s-1}=\tau_{x,s-1}\upharpoonright (s-1)\subseteq\upsilon_u.\end{align*} $$

Since given our assumption, $\tau _x\not =\upsilon _u$ and each of the numberings $\xi ^m$ , $m\in \mathbb N$ , is universal, there exist distinct v and $v'$ such that

$$ \begin{align*}\psi_{c(e,x),s-1}\subseteq\xi^n_v\,\&\,\psi_{c(e,x),s-1}\subseteq\xi^n_{v'}.\end{align*} $$

Therefore, for some $p>\max \{s,t\}$ , condition 2 is satisfied. That is a contradiction.

It follows directly from the definition of the numbering $\psi $ that for all e and x, either $\psi _{c(e,x)}=\tau _x$ or $\psi _{c(e,x)}=\xi ^n_v$ for some n and v. Thus, $\psi $ numerates a subfamily of $\mathcal {A}$ .

Now we choose an arbitrary e such that $\varphi _e$ is total and show that $\psi $ is not reducible to $\bigoplus _n\xi ^n$ via $\varphi _e$ . Note that for all x and s satisfying the condition of case ii, the integers u and t corresponding to these x and s in the construction of the sequence $\{\psi _{c(e,x),q}\}_{q\in \mathbb N}$ are chosen uniformly with respect to x and s. Since $\tau \not \preceq \upsilon $ , there are integers x and s such that the corresponding u satisfies the condition

$$ \begin{align*}\tau_x\not=\upsilon_u.\end{align*} $$

Therefore, there exist x and s such that the corresponding p satisfies condition 2. Hence, there exists v with

$$ \begin{align*}v\not=w\,\&\,\psi_{c(e,x)}=\xi^n_v,\end{align*} $$

where $\varphi _e(c(e,x))=c(n,w)$ . Since the numbering $\xi ^n$ is Friedberg, we have

$$ \begin{align*}\psi_{c(e,x)}=\xi^n_v\not=\xi^n_w.\end{align*} $$

Therefore, $\psi $ is not reducible to $\bigoplus _m\xi ^m$ via $\varphi _e$ . Since the choice of e is arbitrary, the proof is complete.

Proof. Let $\tau $ be an arbitrary computable numbering of $\mathcal {A}$ . It follows from the conditions of the theorem that $\mathcal {A}$ is infinite. It is not hard to see that for every n, the set

$$ \begin{align*}\{y\in\mathbb N:\tau_y\not=\tau_n\}\end{align*} $$

is r.e. uniformly with respect to n. Therefore, uniformly with respect to n one can construct a computable numbering $\sigma ^n$ of the family $\mathcal {A}\setminus \{\tau _n\}$ . It is clear that for every n, the numbering $\sigma ^n$ is negative. It was proved by Ershov [Reference Ershov4] that for every negative numbering $\sigma $ of an infinite family $\mathcal {B}$ there exists a Friedberg numbering $\xi $ of $\mathcal {B}$ that is reducible to $\sigma $ . Moreover, the recursive function that reduces $\xi $ to $\sigma $ can be found uniformly with respect to an r.e. index of the relation $(\mathbb N\times \mathbb N)\setminus \eta _{\sigma }$ . Hence, there exists a computable sequence of Friedberg numberings $\{\xi ^n\}_{n\in \mathbb N}$ such that $\xi ^n$ numerates $\mathcal {A}\setminus \{\tau _n\}$ for each n. Thus, the sequence of numberings $\{\upsilon ^n\}_{n\in \mathbb N}$ of $\mathcal {A}$ , where

$$ \begin{align*}\upsilon^n(x,y)= \begin{cases} \xi^n(x-1,y), & \text{if}\ x>0,\\ \tau_n(y), & \text{if}\ x=0,\ x,y\in\mathbb N, \end{cases} \end{align*} $$

is a computable sequence of Friedberg numberings of $\mathcal {A}$ . Based on this sequence, as in the proof of Theorem 4.1 one can construct a computable sequence $\{\psi ^n\}_{n\in \mathbb N}$ of pairwise incomparable Firedberg numberings of $\mathcal {A}$ such that $\psi ^n_0=\tau _n$ for each n. Therefore, $\tau \preceq \bigoplus _n\psi ^n$ . Since the choice of $\tau $ is arbitrary, the proof is complete.