2. Preliminaries

Given a total function $f\colon \omega \to \omega$ and a nonzero natural number m, by $f| m$ we denote the following tuple:

\begin{align*} f| m := (f(0),f(1),\dots,f(m-1)).\end{align*}

For a set $A\subseteq \omega$ , by $\chi_A$ we denote the characteristic function of A. For a pair of natural numbers $(k ,\ell)$ , the value $\langle k,\ell\rangle$ is its standard Cantor index, that is,

\begin{align*} \langle k,\ell\rangle = \frac{(k+\ell)(k+\ell+1)}{2} + k.\end{align*}

2.1 Theory of numberings

Let $\nu$ be a numbering of a family $\mathcal{S}_0$ and $\mu$ be a numbering of a family $\mathcal{S}_1$ . It is easy to see that the condition $\nu \leq \mu$ implies that $\mathcal{S}_0$ is a subfamily of $\mathcal{S}_1$ . Clearly, if $\nu\leq_{pr} \mu$ , then $\nu\leq \mu$ .

Numberings $\nu$ and $\mu$ are equivalent, denoted by $\nu\equiv \mu$ , if $\nu\leq \mu$ and $\mu \leq \nu$ . The punctual equivalence $\equiv_{pr}$ is defined in a similar way. The numbering $\nu\oplus\mu$ of the family $\mathcal{S}_0\cup\mathcal{S}_1$ is defined as follows:

\begin{align*} (\nu \oplus \mu)(2x) = \nu(x), \quad (\nu \oplus \mu)(2x+1) = \mu(x).\end{align*}

It is not difficult to obtain the following fact (see, e.g., Proposition 3 in Ershov Reference Ershov1977, p. 36). If $\unlhd \in \{\leq,\leq_{pr}\}$ and $\xi$ is an arbitrary numbering, then

\begin{align*} (\nu \unlhd \xi \ \&\ \mu\unlhd \xi) \ \Leftrightarrow\ (\nu\oplus \mu \unlhd \xi).\end{align*}

Let $\mathcal{S}$ be a punctual family of functions. By $Com_{pr}(\mathcal{S})$ , we denote the set of all punctual numberings of $\mathcal{S}$ . Since the relation $\equiv_{pr}$ is a congruence on the structure $(Com_{pr}(\mathcal{S}); \leq_{pr}, \oplus)$ , we use the same symbols $\leq_{pr}$ and $\oplus$ on numberings of $\mathcal{S}$ and on $\equiv_{pr}$ -equivalence classes of the numberings.

The quotient structure $\mathcal{R}_{pr}(\mathcal{S}) := (Com_{pr}(\mathcal{S}) /_{\displaystyle{\equiv_{pr}}}; \leq_{pr}, \oplus)$ is an upper semilattice. We call the structure $\mathcal{R}_{pr}(\mathcal{S})$ the Rogers pr-semilattice of the punctual family $\mathcal{S}$ .

Let $\mathcal{T}$ be a family of total (Turing) computable functions acting from $\omega$ to $\omega$ . A numbering $\nu$ of the family $\mathcal{T}$ is computable if the function $g_{\nu}$ from Definition 1 is computable. Note that this definition is consistent with the notion of computable numbering discussed in the introduction: if we identify functions from $\mathcal{T}$ with their graphs, then we will get precisely the same notions.

We say that a family $\mathcal{T}$ is Turing computable if it has a computable numbering. The definition of Rogers semilattice $\mathcal{R}_{c}(\mathcal{T})$ is obtained in a similar way to the semilattice $\mathcal{R}_{pr}(\mathcal{S})$ , modulo the following modification: one needs to consider all computable numberings of $\mathcal{T}$ and the standard reducibility $\leq$ between them.

Another way to look at things is the following. Suppose that $\mathcal{T}$ is still a Turing computable family of total functions, but our reducibility is punctual. This gives rise to another Rogers semilattice $\mathcal{R}^{(c,pr)}(\mathcal{T})$ . In this setting, the semilattices $\mathcal{R}_{pr}(\mathcal{S})$ constitute a special case of $\mathcal{R}^{(c,pr)}(\mathcal{T})$ . Throughout the paper, we give several comments on how our results on $\mathcal{R}_{pr}(\mathcal{S})$ could be extended to a more general case of $\mathcal{R}^{(c,pr)}(\mathcal{T})$ .

2.2 The punctuality paradigm

Kalimullin et al. (Reference Kalimullin, Melnikov and Ng2017) noted that many known proofs from polynomial time structure theory (see, e.g., the survey Cenzer and Remmel Reference Cenzer and Remmel1998) are focused on making the operations and relations on a given algebraic structure $\mathcal{S}$ primitive recursive, and then observing that the obtained presentation of $\mathcal{S}$ is in fact computable in polynomial time.

Kalimullin et al. (Reference Kalimullin, Melnikov and Ng2017) proposed that a reasonable “online” presentation of a structure must minimally satisfy the following: a countably infinite structure is punctual if its domain equals $\omega$ and the operations and predicates of the structure are (uniformly) primitive recursive. Roughly speaking, the intuition behind this notion is the following: punctual presentations do not allow any delays – or in other words, there are no instances of truly unbounded search.

Nowadays, the theory of punctual structures is a flourishing research direction. Its intricate constructions have provided a deep insight into the algorithmic complexity of isomorphisms (Downey et al. Reference Downey, Greenberg, Melnikov, Ng and Turetsky2020a,b; Melnikov and Ng Reference Melnikov and Ng2019). The developed techniques found applications in the theory of automatic structures (Bazhenov et al. Reference Bazhenov, Harrison-Trainor, Kalimullin, Melnikov and Ng2019b). For further results on punctual structures, the reader is referred to the surveys (Bazhenov et al. Reference Bazhenov, Downey, Kalimullin and Melnikov2019a; Downey et al. Reference Downey, Melnikov and Ng2021; Melnikov Reference Melnikov2017).

The restricted Church–Turing thesis for primitive recursive functions says the following: A function is primitive recursive if and only if it can be described by an algorithm that uses only bounded loops. Informally speaking, one needs to eliminate all instances of while do, repeat until, and goto in a Pascal-like programming language.

Our proofs will exploit the restricted Church–Turing thesis without an explicit reference.

Let k be a nonzero natural number. We fix a computable list $(p^{(k)}_e)_{e\in\omega}$ of all k-ary primitive recursive functions. We emphasize that the list is computable, but it cannot be primitive recursive. Nevertheless, the following function can be treated as a punctual object:

\begin{align*} p^{(k)}_e[t](\bar x) := \begin{cases} p^{(k)}_e (\bar x), & \text{if the value } p^{(k)}_e(\bar x) \text{ is computed in}\\ & \text{at most } t \text{ computational steps},\\ \text{undefined}, & \text{otherwise}. \end{cases}\end{align*}

Without loss of generality, one may also assume the following: if $p^{(k)}_e(\bar x)$ is equal to N, then for any $t\leq \max(e,\bar x,N)$ , the value $p^{(k)}_e[t](\bar x)$ is undefined. The formal details can be recovered from Bazhenov et al. (Reference Bazhenov, Downey, Kalimullin and Melnikov2019a, Section 10).

If $k=1$ , then we omit the superscript – we write $p_e$ in place of $p^{(1)}_e$ . For $e\in\omega$ , we define a numbering $\rho_e$ :

\begin{align*} (\rho_e(k))(x) := p^{(2)}_e(k,x).\end{align*}

It is clear that $(\rho_e)_{e\in\omega}$ is a computable list of all punctual numberings.

3. Strongly Punctually Decidable Numberings

In this section, we introduce the notion of a strongly punctually decidable numbering and discuss its properties. This notion will play a key role in most of our further constructions.

The background behind the notion comes from some classical results of the theory of numberings. An arbitrary numbering $\nu$ is traditionally associated with an equivalence relation $\eta_{\nu}$ on $\omega$ – the relation $\eta_{\nu}$ is defined as follows:

\begin{align*} m ~\eta_{\nu}~ n \ \Leftrightarrow\ \nu(m) = \nu(n).\end{align*}

Sometimes, the relation $\eta_{\nu}$ is called the numeration equivalence of $\nu$ .

A numbering $\nu$ is called negative if the relation $\eta_{\nu}$ is co-c.e., that is, $\eta_{\nu}$ is the complement of a c.e. set. A numbering $\nu$ is decidable if the relation $\eta_{\nu}$ is (Turing) computable. A numbering $\nu$ is Friedberg if $\eta_{\nu}$ is the identity relation.

Let $\mathcal{T}$ be an infinite, Turing computable family of functions. Mal’cev (Reference Mal’cev1965) showed that every computable numbering of $\mathcal{T}$ is negative. Ershov (Reference Ershov1967) proved that for any computable numbering $\nu$ of $\mathcal{T}$ , there is a computable Friedberg numbering $\mu$ of $\mathcal{T}$ such that $\mu \leq \nu$ .

The notion of a strongly punctually decidable numbering comes from a “punctual version” of the results of Mal’cev and Ershov. First, we note the following:

Observation 4. If $\nu$ is a punctual numbering, then $\nu$ is negative.

Indeed, this fact easily follows from the result of Mal’cev (Reference Mal’cev1965). After that, we introduce our new notions:

A punctually decidable numbering $\nu$ is strongly punctually decidable (or spd for short) if every $\eta_{\nu}$ -equivalence class C satisfies the following: either C contains only one element, or $C = [0]_{\eta_{\nu}}$ .

Roughly speaking, the intuition behind the notion of an spd numbering is as follows. When one builds a punctual algebraic structure $\mathcal{P}$ , one of the basic strategies is “time-filling”: while we wait for some Turing computable (not necessarily primitive recursive) process to finish its computations, we still have to promptly construct larger and large finite pieces of $\mathcal{P}$ . Typically, this is achieved via copying some (relatively) simple parts of a given punctual structure $\mathcal{A}$ . For example, if $\mathcal{A} = (\omega, s, 0)$ , where s is the successor function, then one could promptly take fresh numbers and declare that inside our $\mathcal{P}$ , they are equal to $0_{\mathcal{P}}$ , $s_{\mathcal{P}}(0_{\mathcal{P}})$ , $s_{\mathcal{P}}(s_{\mathcal{P}}(0_{\mathcal{P}}))$ ,…, $s^{(n)}_{\mathcal{P}}(0_{\mathcal{P}})$ ,….

The notion of an spd numbering mirrors the time-filling strategy. In general, the construction of a punctual Friedberg numbering for a given punctual family $\mathcal{S}$ could be impossible (see Proposition 38 in the last section). Nevertheless, “stalling” the construction process by defining

\begin{align*} \nu(1) := \nu(0),\ \ \nu(2) := \nu(0), \ \ \dots,\ \ \nu(n) := \nu(0), \ \ \dots, \end{align*}

allows to build an spd numbering for $\mathcal{S}$ .

We prove the following general result about numberings:

Since the numbering $\nu$ is negative, the set

\begin{align*} I_{\nu}:= \{ n\in\omega \,\colon (\forall i < n)( \nu(i) \neq \nu(n)) \} \end{align*}

is computably enumerable. Choose a primitive recursive function h(x) such that $\mathrm{range}(h) = I_{\nu}$ . Then it is not hard to show that the numbering $\mu:= \nu\circ h$ is punctually decidable. Hence, $\mu$ has the desired properties.

The following consequence of Proposition 6 will play a crucial part in our constructions:

3.1 Punctual families with spd numberings

After Proposition 6 and Corollary 7 are obtained, it is natural to consider the following problem:

Problem 8. We say that a punctual family $\mathcal{S}$ is persistently decidable if every punctual numbering of $\mathcal{S}$ is punctually decidable. Characterize persistently decidable families.

First, we observe the following easy sufficient condition for being persistently decidable.

Definition 9. We say that a punctual family $\mathcal{S}$ is strongly finitely discrete (or sf-discrete for short) if there exists a natural number N such that for any functions $f,g\in\mathcal{S}$ , the following conditions are equivalent:

\begin{align*} f = g\ \Leftrightarrow\ f| N = g| N. \end{align*}

Lemma 10. Every sf-discrete punctual family $\mathcal{S}$ is persistently decidable.

Proof. Let $\nu$ be an arbitrary punctual numbering of $\mathcal{S}$ . It is clear that we have

\begin{align*} (k ~\eta_{\nu}~ \ell)\ \Leftrightarrow\ \nu(k)| N = \nu(\ell) | N, \end{align*}

and this condition is primitive recursive.

Note that every finite punctual family is sf-discrete.

Example 11. A simple example of an infinite sf-discrete family is the family containing the following functions: for $i\in\omega$ ,

\begin{align*} g_i(x) = i, \text{ for all } x. \end{align*}

Second, we obtain a sufficient condition for being not persistently decidable.

Definition 12. Let $\nu$ be a punctual numbering of a family $\mathcal{S}$ . We say that a primitive recursive function f is a quickly spoiling limit point for $\nu$ if it satisfies the following: there is a primitive recursive function sp(n,t) such that for any n,

\begin{align*} \nu(sp(n,0)) | n = \nu(sp(n,1)) | n = f| n \text{ and } \nu(sp(n,0)) \neq \nu(sp(n,1)). \end{align*}

The intuition behind the definition is as follows. Consider a construction, which promptly defines a function g(x) bit by bit. A default action of this construction is copying the function f – we put $g(0) := f(0)$ , $g(1) := f(1)$ , $g(2) := f(2)$ ,. Then the function sp(n,t) always provides two different opportunities for a quick “diagonalization”: at any stage s, one can abandon copying f and set either $g := \nu(sp(s,0))$ or $g := \nu(sp(s,1))$ .

Observation 13. Let $\nu$ be a punctual numbering of a family $\mathcal{S}$ , and let $\mu$ be a punctual numbering of a family $\mathcal{T}$ . If f is a quickly spoiling limit point for $\nu$ , then f is also quickly spoiling for $\nu\oplus \mu$ .

Example 14. A simple example for Definition 12 can be recovered as follows. Consider a punctual Friedberg numbering:

\begin{align*} \nu(k) := \chi_{ \{ k\}}. \end{align*}

Then the function $f := \chi_{\emptyset}$ is a quickly spoiling limit point for $\nu$ . This is witnessed by a function sp satisfying $sp(n,0) := n+1$ and $sp(n,1) := n+2$ . Note that in this example, f is the unique limit point of $\mathcal{S}$ in the Cantor space $2^{\omega}$ .

Proposition 15. Suppose that $\nu$ is a punctual numbering of a family $\mathcal{S}$ , and f is a quickly spoiling limit point for $\nu$ . Then the family $\mathcal{S}$ is not persistently decidable.

Proof. Choose a primitive recursive function sp(n,t), which witnesses the spoiledness of f. Let A be a computable set which is not primitive recursive. Fix two primitive recursive functions p(x) and q(x) such that $A = \mathrm{range}(p)$ and $\overline{A} = \mathrm{range}(q)$ .

We define a punctual numbering $\mu$ of some subfamily $\mathcal{S}_0 \subseteq \mathcal{S}$ . An informal idea of the construction is as follows. Consider a number $k\in\omega$ . We look at two quick listings $A = \left\{{}p(0), p(1), p(2), \dots\right\}$ and $\overline{A} = \{ q(0), q(1), q(2), \dots\}$ , and we wait for the first stage $s_0$ , at which we see that k appeared on one of the two lists. At every stage $s< s_0$ , the functions $\mu(2k)$ and $\mu(2k+1)$ just copy (the initial segments of) the limit point f. At the stage $s_0$ , we consider two cases:

1. (1). If $k \in A$ , then we put $\mu(2k) = \mu(2k+1) := \nu( sp(s_0,0))$ .

2. (2). If $k\not\in A$ , then we set $\mu(2k) := \nu (sp(s_0,0))$ and $\mu(2k+1) := \nu (sp(s_0,0))$ .

The properties of the function sp(n,t) ensure that the described construction builds a punctual numbering, and every function $\mu(\ell)$ belongs to $\mathcal{S}$ . Moreover, we deduce that

\begin{align*} k\in A\ \Leftrightarrow\ \mu(2k) = \mu(2k+1). \end{align*}

Since the set A is not primitive recursive, the numbering $\mu$ cannot be punctually decidable.

For the sake of completeness, we provide a more formal description of the construction. We build the numbering $\mu$ and auxiliary prompt functions u(k,s) and w(k,s). We put $\mu(k)(0) = f(0)$ and $u(k,0) = w(k,0) = -1$ for all $k\in\omega$ .

At a stage $s+1$ , for each k we proceed as follows:

1. (1). If $u(k,s) \geq 0$ , then we put $u(k,s+1) := u(k,s)$ and $w(k,s+1) := w(k,s)$ . Otherwise, we check the following conditions:

   1. – If $k\in \{ p(0), p(1),\dots,p(s+1)\}$ , then set $u(k,s+1) = w(k,s+1) := sp(s+1, 0)$ .

   2. – If $k \in \{ q(0), q(1), \dots, q(s+1)\}$ , then define $u(k,s+1) := sp(s+1,0)$ and $w(k,s+1) := sp(s+1,1)$ .

   3. – Otherwise, do not change the values of u and v.

2. (2). Define

   \begin{gather*} \mu(2k) (s+1) := \begin{cases} \nu(u(k,s+1)) (s+1), & \text{if } u(k,s+1) \geq 0,\\ f (s+1), & \text{if } u(k,s+1) = -1; \end{cases}\\ \mu(2k+1) (s+1) := \begin{cases} \nu(w(k,s+1)) (s+1), & \text{if } w(k,s+1) \geq 0,\\ f (s+1), & \text{if } w(k,s+1) = -1. \end{cases} \end{gather*}

This concludes the description of the construction. The argument given before the description shows that $\mu$ promptly indexes some subfamily $\mathcal{S}_0$ of $\mathcal{S}$ , and the numbering $\mu$ is not punctually decidable. Therefore, the numbering $\mu_1 := \nu \oplus \mu$ belongs to $Com_{pr}(\mathcal{S})$ , and $\mu_1$ is not punctually decidable. Hence, the family $\mathcal{S}$ is not persistently decidable.

In general, it seems that Problem 8 is pretty hard to solve. After the reader familiarizes themselves with further punctual constructions, in Section 9, we will build an infinite, persistently decidable family $\mathcal{S}$ such that:

• For every function $f\in\mathcal{S}$ , $\textrm{range}(f) \subseteq \{ 0,1\}$ . This implies that $\mathcal{S}$ is not sf-discrete.

• The family $\mathcal{S}$ has a unique limit point f in the Cantor space, and this f is primitive recursive. By Proposition 15, f cannot be quickly spoiling for any punctual numbering $\nu$ of $\mathcal{S}$ .

4. Warming Up: Absence of Minimal Elements

The section contains an introduction to punctual priority constructions: we give a detailed proof of the result below, which serves as a good starting point.

Our construction will satisfy the following series of requirements:

1. $P_e$ : The function $p_e$ does not punctually reduce $\nu$ to $\mu$ .

The key difference between our construction and a typical priority argument (of recursion theory) is the following: our requirements do not injure each other, and we will satisfy only one requirement $P_e$ at a time.

Strategy for $P_e$ . Suppose that the $P_e$ -strategy starts working at a stage $s^e$ of the construction, and $N^e$ is the least index such that the object $\mu(N^e)$ is still undefined at the beginning of the stage $s^e$ .

We wait until the first stage $t>s^e$ with the following properties:

1. (a) There is a (least) number $w^e\leq t$ such that $w^e \geq e$ , $\nu(w^e) \neq \nu(0)$ , and we have not used the object $\nu(w^e)$ in our definition of $\mu$ before.

2. (b) For this particular $w^e$ , the value $p_e[t](w^e)$ is already defined.

Note that checking whether $\nu(w^e)$ is equal to $\nu(0)$ is a punctual procedure, since the numbering $\nu$ is spd.

While waiting for this t to appear, we should not delay the definition of the numbering $\mu$ , so, one by one, we put

\begin{align*} \mu(N^e) := \nu(0),\ \mu(N^e+1) := \nu(0),\ \mu(N^e+2) := \nu(0), \dots. \end{align*}

When the desired stage t is achieved, we proceed as follows:

1. 1. For each $k\leq p_e(w^e)$ , if the object $\mu(k)$ is still undefined, then put $\mu(k) := \nu(0)$ .

2. 2. Let m be the least index such that at this moment, $\mu(m)$ is still undefined. Set $\mu(m + \ell) := \nu(\ell)$ , for every $\ell \leq w^e$ .

It is clear that the described actions ensure that the requirement $P_e$ is forever satisfied: our choice of the witness $w^e$ guarantees that we have $\nu(w^e)\neq \mu(p_e(w^e))$ .

The construction is arranged as follows: we start the $P_0$ -strategy and wait until it is satisfied. When $P_0$ is satisfied, we immediately start the $P_1$ -strategy. After $P_1$ is satisfied, we start $P_2$ , etc.

Verification. Since the family $\mathcal{S}$ is infinite, each strategy $P_e$ will eventually find its witness $w^e$ , and after that, $P_e$ will eventually become satisfied. Therefore, we deduce $\nu\not\leq_{pr} \mu$ .

The constructed numbering $\mu$ is punctual: indeed, for an index $k\in\omega$ , one can just look at the stage $k+1$ of the described construction. At this stage $k+1$ , we can promptly find an index r(k) such that $\mu(k)$ is equal to $\nu(r(k))$ . This shows the punctuality of $\mu$ , and furthermore, the function r punctually reduces $\mu$ to $\nu$ .

Informally speaking, the punctuality of $\mu$ is ensured by elimination of unbounded searches: Surely, the $P_e$ -strategy wants to “catch” a particularly good stage t, but this quest for t does not delay the construction at all – while doing the t-search, our definition of $\mu$ just executes a straightforward filler action (copying $\nu(0)$ for appropriate $\mu$ -indices).

Now it is enough to show that the numbering $\mu$ has an index for every element of $\mathcal{S}$ . This is ensured by the assignment $\mu(m + \ell) := \nu(\ell)$ given above – after satisfying $P_e$ , $\mu$ copies the long initial segment $\nu(0),\nu(1),\dots,\nu(w^e)$ .

The classical result of Khutoretskii (Reference Khutoretskii1971) shows that for any computable family $\mathcal{T}$ , its semilattice $\mathcal{R}_c(\mathcal{T})$ is either one element or infinite. Proposition 3 and Theorem 16 together imply that the punctual setting exhibits a similar behavior:

For a Turing computable family of total functions $\mathcal{T}$ , we consider the semilattice $\mathcal{R}^{(c,pr)}(\mathcal{T})$ defined in Section 2.1. A simple analysis of the proof of Theorem 16 shows the following:

Proof Sketch. In the construction of Theorem 16, one builds a new numbering $\mu$ only by looking at the $\nu$ -indices, that is, we always declare that $\mu(k) := \nu(\ell_k)$ for some $\ell_k\in\omega$ , and we never really work with the “internal content” of our functions $\nu(\ell_k)$ . By working with the internal content, here we mean the following: say, one can choose to define

\begin{align*} \mu(0)(0) = \nu(\ell_0)(m_0), \ \ \mu(0)(1) = \nu(\ell_1)(m_1),\ \ \mu(0)(2) = \nu(\ell_2)(m_2),\ \dots, \end{align*}

that is, to copy different finite pieces from different functions $\nu(\ell_t)$ , $t\in\omega$ .

This observation implies that the constructed new numbering $\mu$ is a Turing computable numbering of our family $\mathcal{T}$ such that $\mu\leq_{pr} \nu$ and $\nu\not\leq_{pr} \mu$ .

5. Antichains

In this section, we establish that any non-greatest element of a Rogers pr-semilattice is a part of an infinite antichain. First, we prove the following.

We satisfy the following series of requirements:

1. $P_e$ : $p_e\colon \tilde\mu \not\leq_{pr}\nu$ , that is, $p_e$ does not punctually reduce $\tilde\mu$ to $\nu$ .

2. $Q_i$ : $p_i\colon \nu \not\leq_{pr} \mu$ .

The $P_e$ -requirements ensure that $\tilde\mu \not\leq_{pr} \nu$ . Since $\tilde{\mu} \leq_{pr} \mu$ , this implies $\mu \not\leq_{pr} \nu$ .

We also have a global requirement

1. R: $\nu$ is punctually reducible to $\alpha$ .

Informally, this will be satisfied via the following action: at a stage s, we promptly define the value $f_{\nu}(s)$ such that $\nu(s) = \alpha(f_{\nu}(s))$ .

We fix a (punctual) ordering of requirements: $P_0 < Q_0 < P_1 < Q_1 < \dots$ . This means that we will satisfy $P_0$ , then $Q_0$ , then $P_1$ , etc.

The $P_e$ -strategy. By the background action of the $P_e$ -strategy, we mean the following: whenever we are waiting for some object to be found, we do not delay our construction, and we just put

\begin{align*} \nu(N) := \tilde\mu(0),\ \nu(N+1) := \tilde\mu(0),\ \nu(N+2) := \tilde\mu(0)\ \dots, \end{align*}

starting with an appropriate index N. This N is typically clear from the context (recall the $N^e$ from Theorem 16).

The strategy $P_e$ waits until the first (large enough) stage t with the following properties:

1. (a) There are $N+1$ indices $a_0,a_1,\dots,a_{N}$ such that $a_i \leq t$ and the objects $\tilde\mu(a_i)$ are pairwise different. Recall that the relation $\eta_{\tilde\mu}$ is primitive recursive, so this condition can be verified in a prompt way.

2. (b) For each $i\leq N$ , the value $p_e(a_i)[t]$ is defined.

When this t is found, we compute $M := \max(p_e(a_0),p_e(a_1),\dots,p_e(a_N))$ . For every $k\leq M$ , if $\nu(k)$ is still undefined, then we put $\nu(k) := \tilde{\mu}(0)$ .

Consider the finite set $F := \{ j\,\colon j\leq M\}$ . On one hand, it is clear that the family $ \{ \nu(j)\,\colon j\in F\} $ contains at most N different objects. On the other hand, there are $(N+1)$ different functions $\tilde{\mu}(a_i)$ , $i\leq N$ , and $p_e(a_i) \in F$ for all i.

Therefore, we deduce that $p_e$ cannot punctually reduce $\tilde\mu$ to our $\nu$ , and the $P_e$ -requirement is satisfied.

The $Q_i$ -strategy. Suppose that the strategy starts working at a stage $s_0$ of the construction. Let $M_0$ be the least index such that $\nu(M_0)$ is still undefined. We put

\begin{align*} \nu(M_0 + k) := \alpha(k) \text{ for every } k\leq s_0. \end{align*}

This action ensures that every object from the family $\mathcal{S}$ eventually obtains a $\nu$ -index.

Put $N:=M_0+s_0+1$ . The background action of the $Q_i$ -strategy is as follows – it defines

\begin{align*} \nu(N) := \alpha(0),\ \nu(N+1) := \alpha(1),\ \nu(N+2) := \alpha(2),\ \dots. \end{align*}

We wait until the first stage t such that there are an index $w_0 \leq t$ and a number $L \leq t$ with the following properties:

• The value $p_i(w_0)[t]$ is defined.

• The object $\nu(w_0)$ is defined.

• We have $\nu(w_0) | L \neq \mu(p_i(w_0)) | L$ .

If these $w_0$ and L are found, then $\nu(w_0) \neq \mu(p_i(w_0))$ . This shows that $p_i$ does not reduce $\nu$ to $\mu$ , and the $Q_i$ -strategy is satisfied.

Now we only need to show that the desired stage t will be eventually reached. Toward a contradiction, assume that there is no such stage t. Then for every w and L, we have $\nu(w) | L = \mu(p_i(w)) | L$ . In other words, the function $p_i$ punctually reduces $\nu$ to $\mu$ . Then our background actions imply that

\begin{align*} \alpha(x) = \nu(N+x) = \mu(p_i(N+x)) \text{ for all } x\in\omega; \end{align*}

hence $\alpha \leq_{pr} \mu$ , which contradicts the conditions of the theorem.

The construction is arranged similarly to Theorem 16: our requirements are satisified one by one, according to their priority ordering.

Verification. We have already shown that every requirement will be eventually satisfied; hence, the numberings $\nu$ and $\mu$ are $\leq_{pr}$ -incomparable. Moreover, our description of a $Q_i$ -strategy guarantees that $\nu$ provides an index for every element from $\mathcal{S}$ .

Note that there is a primitive recursive function $f_{\nu}(x)$ such that $\nu = \alpha \circ f_{\nu}$ . This is ensured by the background actions: at each stage, we promptly set either $\nu(x) := \tilde{\mu}(0) = \alpha(f_{\tilde\mu}(0))$ or $\nu(x) := \alpha(\ell_x)$ for appropriately chosen index $\ell_x$ . Therefore, the numbering $\nu$ has desired properties.

A not too difficult modification of Theorem 19 provides the following result:

1. (a) for every k, $\nu_k \leq_{pr} \alpha$ and $\nu_k$ is $\leq_{pr}$ -incomparable with $\mu$ ;

2. (b) the numberings $\nu_k$ are pairwise $\leq_{pr}$ -incomparable.

Proof of Theorem 20. Here we discuss a construction, which builds only two $\leq_{pr}$ -incomparable punctual numberings $\nu_0$ and $\nu_1$ . This construction admits a straightforward generalization to the case of countably many incomparable elements. We use the same notation as in Theorem 19.

For $\varepsilon \in\{ 0,1\}$ , we need to satisfy the following requirements:

1. $R^{\varepsilon}$ : $\nu_{\varepsilon}$ is punctually reducible to $\alpha$ .

2. $P^{\varepsilon}_e$ : $p_e\colon \tilde\mu \not\leq_{pr}\nu_{\varepsilon}$ .

3. $Q^{\varepsilon}_i$ : $p_i\colon \nu_{\varepsilon} \not\leq_{pr} \mu$ .

4. $N^0_j$ : $p_j\colon \nu_0 \not\leq_{pr} \nu_1$ .

5. $N^1_j$ : $p_j\colon \nu_1 \not\leq_{pr} \nu_0$ .

The strategies for the requirements $R^{\varepsilon}$ , $P^{\varepsilon}_e$ , and $Q^{\varepsilon}_j$ are essentially the same as those in the proof of Theorem 19. Since $N^1$ -requirements are similar to $N^0$ -requirements, it is sufficient to discuss only a $N^0_j$ -strategy.

The $N^0_j$ -strategy. The background action of the strategy is the following: we put

\begin{gather*} \nu_0(N) := \tilde{\mu}(0),\ \nu_0(N+1) := \tilde{\mu}(1),\ \nu_0(N+2) := \tilde{\mu}(2),\ \dots\\ \nu_1(N) := \tilde{\mu}(0),\ \nu_1(N+1) := \tilde{\mu}(0),\ \nu_1(N+2) := \tilde{\mu}(0),\ \dots \end{gather*}

Our strategy waits until the first stage t with the following properties:

1. (a) There are $N+1$ indices $b_0,b_1,\dots,b_{N}$ such that $N\leq b_i \leq t$ and the objects $\nu_0(b_i)$ are pairwise different. Since the numbering $\tilde{\mu}$ is spd and (in the background) $\nu_0(N+x) = \tilde{\mu}(x)$ , these indices will eventually appear.

2. (b) For each $i\leq N$ , the value $p_j(b_i)[t]$ is defined.

When the number t is found, we set $M:= \max\{ p_j(b_i)\,\colon i\leq N\}$ . For each $k\leq M$ , if the value $\nu_0(k)$ is still undefined, then put $\nu_0(k) := \tilde{\mu}(0)$ . We work with $\nu_1(k)$ , $k\leq M$ , in a similar way.

An argument similar to the one given in the description of the $P_e$ -strategy (Theorem 19) shows that $p_j$ does not punctually reduce $\nu_0$ to $\nu_1$ .

As usual, our construction fixes some punctual ordering of all requirements (except $R^0$ and $R^1$ ) and satisfies these requirements one by one. The requirements $R^0$ and $R^1$ are satisfied via “global” actions. The verification proceeds similarly to Theorem 19. This concludes the proof of Theorem 20.

Similarly to Corollary 18, the proof of Theorem 20 implies the following:

6. Density

In this section, we consider intervals inside a Rogers pr-semilattice $\mathcal{R}_{pr}(\mathcal{S})$ . First, we prove that the poset $\mathcal{R}_{pr}(\mathcal{S})$ is dense:

1. R: $\alpha$ is punctually reducible to $\mu$ .

2. $P_e$ : $p_e\colon \alpha \not\leq_{pr} \nu$ .

3. $Q_i$ : $p_i\colon \mu\not\leq_{pr} \alpha \oplus \nu$ .

These requirements are enough for our goals: indeed, assume that all requirements are satisfied and consider the punctual numbering $\xi:=\alpha \oplus \nu$ of the whole family $\mathcal{S}$ . Then clearly, we have $\nu \leq_{pr} \xi \leq_{pr} \mu$ . The $P_e$ -requirements guarantee that $\xi \not\leq_{pr} \nu$ . The $Q_i$ -requirements ensure $\mu \not\leq_{pr} \xi$ .

As in Theorem 19, the R-strategy acts globally: at a stage s, we promptly define the value $g_{\alpha}(s)$ with $\alpha(s) = \mu(g_{\alpha}(s))$ .

The $P_e$ -strategy. Suppose that the strategy starts working at a stage $s_0$ , and N is the least index with $\alpha(N)$ still being undefined.

The background action of the $P_e$ -strategy is as follows. We propagate

\begin{align*} \alpha(N) := \mu(0), \ \alpha(N+1) := \mu(1),\ \alpha(N+2) := \mu(2),\ \dots. \end{align*}

We wait for the least stage $s_1 > s_0$ such that there is a number $w\leq s_1$ with the following properties:

• The object $\alpha(w)$ is already defined, and $\alpha(w) = \mu(g_{\alpha}(w))$ . The verification will demonstrate that given w, the desired $\mu$ -index $g_{\alpha}(w)$ can be calculated in a prompt way.

• The value $p_e[s_1](w)$ is defined.

• By the stage $s_1$ , we have already witnessed that $\mu(g_{\alpha}(w)) \neq \mu f(p_e(w))$ .

The last item requires a little bit of clarification: How does one check such a condition?

Recall that by Observation 4, the numbering $\mu$ is negative. In other words, the set $ \left\{ (k,\ell)\,\colon \mu(k) \neq \mu(\ell) \right\} $ is c.e., and hence, it can be enumerated by a punctual function. Thus, if our $g_{\alpha}(w)$ and $f(p_e(w)) $ are $\mu$ -indices of different objects, then we will eventually witness this fact.

We emphasize the following: If the desired stage $s_1$ is found, then the requirement $P_e$ will be forever satisfied. Indeed, we know that $\alpha(w) = \mu(g_{\alpha}(w)) \neq \mu f(p_e(w)) = \nu(p_e(w))$ , and hence, $p_e$ cannot punctually reduce $\alpha$ to $\nu$ . Thus, after the stage $s_1$ , one can proceed to working with other requirements.

The $Q_i$ -strategy. Again, we assume that the strategy starts working at a stage $s_0$ , and N is the least index with $\alpha(N)$ still undefined.

The background action of $Q_i$ is propagating the following:

\begin{align*} \alpha(N) := \nu(0) = \mu(f(0)), \ \alpha(N+1) := \nu(1) = \mu(f(1)),\ \dots. \end{align*}

Wait for the least stage $s_1 > s_0$ such that there is a number $w\leq s_1$ satisfying:

• The value $p_i[s_1](w)$ is defined.

• If the value $p_i(w)$ is even, then the object $\alpha(p_i(w)/2)$ is already defined. Set

  \begin{align*} \ell(w) := \begin{cases} f(\lfloor{}p_i(w)/2 \rfloor), & \text{if } p_i(w) \text{ is odd},\\ g_{\alpha}(p_i(w)/2), & \text{if } p_i(w) \text{ is even}. \end{cases} \end{align*}
  Here, again, we assume that $\alpha(k) = \mu(g_{\alpha}(k))$ .

• By the stage $s_1$ , we have already witnessed that $\mu(w) \neq \mu(\ell(w))$ .

If such a stage $s_1$ is found, then the requirement $Q_i$ will be satisfied. Indeed, we witness that

\begin{align*} \mu(w) \neq \mu(\ell(w)) &= \left\{ \begin{array}{ll} \mu f(\lfloor p_i(w)/2 \rfloor), & \text{if } p_i(w) \text{ is odd},\\ \mu g_{\alpha}(p_i(w)/2), & \text{if } p_i(w) \text{ is even} \end{array} \right\} \\ &= \left\{ \begin{array}{ll} \nu(\lfloor p_i(w)/2 \rfloor), & \text{if } p_i(w) \text{ is odd},\\ \alpha(p_i(w)/2), & \text{if } p_i(w) \text{ is even} \end{array} \right\} = (\alpha \oplus \nu) (p_i(w)). \end{align*}

The construction is arranged as follows. We fix the ordering of our requirements $P_0 < Q_0 < P_1 < Q_1 < \dots$ , and satisfy them one by one.

Verification. It is clear that $\alpha(x) = \mu(g_{\alpha}(x))$ , where $g_{\alpha}$ is a primitive recursive function. This is ensured by our background actions: we always promptly set either $\alpha(N) := \mu(\ell_N)$ or $\alpha(N):= \nu(\ell_N) = \mu(f(\ell_N))$ for appropriately chosen index $\ell_N$ . Hence, $\alpha \leq_{pr} \mu$ , and the strategy descriptions above are well defined.

In order to finish the proof, we need to establish the following fact: every requirement is eventually satisfied.

Toward a contradiction, assume that there is the least requirement T, which is never satisfied. There are two possible cases.

Case 1. Assume that $T = P_e$ for some $e\in\omega$ . This implies that the desired stage $s_1$ of the $P_e$ -strategy is never found. Therefore, for each index w, we have $\alpha(w) = \mu(g_{\alpha}(w)) = \mu f(p_e(w)) = \nu(p_e(w))$ .

Since the $P_e$ -strategy works forever, for some fixed index N, we have $\alpha(N+\ell) = \mu(\ell)$ , for all $\ell \in \omega$ . Therefore,

\begin{align*} \mu(\ell) = \alpha(N + \ell) = \nu(p_e(N + \ell)). \end{align*}

This means that $\mu \leq_{pr} \nu$ , which gives a contradiction.

Case 2. Suppose that $T = Q_i$ . The desired $s_1$ of the $Q_i$ -strategy cannot be found, and this implies that for every index w, we have $\mu(w) = \mu(\ell(w)) = (\alpha\oplus \nu)(p_i(w))$ .

The background actions of the $Q_i$ -strategy ensure that there is N such that $\alpha(N + m) = \nu(m)$ , for all $m\in \omega$ . This shows that $\alpha \leq_{pr} \nu$ , since for each $k<N$ , one can nonuniformly find a $\nu$ -index of the object $\alpha(k)$ . Hence, we have

\begin{align*} \mu \leq_{pr} \alpha \oplus \nu \leq_{pr} \nu, \end{align*}

which contradicts the conditions of the theorem.

Therefore, we deduce that every requirement is satisfied. This concludes the proof of Theorem 23.

With a little bit more work, we obtain the following result.

1. (a) $\xi_i \in Com_{pr}(\mathcal{S})$ and $\nu <_{pr} \xi_i <_{pr} \mu$ .

2. (b) For any non-empty finite sets F and G, we have

   \begin{align*} \bigoplus_{i\in F} \xi_i \leq_{pr} \bigoplus_{j\in G} \xi_j\ \Leftrightarrow\ F\subseteq G. \end{align*}

We use the same notation as in Theorem 23. We build punctual numberings $\alpha_0 \in Com_{pr}(\mathcal{S}_0)$ and $\alpha_1 \in Com_{pr}(\mathcal{S}_1)$ for some subfamilies $\mathcal{S}_0$ and $\mathcal{S}_1$ of the family $\mathcal{S}$ . We satisfy the following requirements:

1. $R^0$ : $\alpha_0 \leq_{pr} \mu$ via a function $g_{\alpha_0}$ .

2. $R^1$ : $\alpha_1 \leq_{pr} \mu$ via a function $g_{\alpha_1}$ .

3. $N^0_e$ : $p_e\colon \alpha_0\oplus \nu \not\leq_{pr} \alpha_1 \oplus\nu$ .

4. $N^1_i$ : $p_i\colon \alpha_1 \oplus \nu \not\leq_{pr} \alpha_0 \oplus \nu$ .

Then the numberings $\xi_0 := \alpha_0 \oplus \nu$ and $\xi_1:= \alpha_1 \oplus \nu$ have all the desired properties. Indeed, $R^0$ ensures that $\xi_0 \leq_{pr}\mu$ . It is obvious that $\nu \leq_{pr} \xi_0$ . The $N^0_e$ - and $N^1_i$ -requirements guarantee that $\xi_0$ and $\xi_1$ are $\leq_{pr}$ -incomparable. Hence, it is clear that $\nu <_{pr} \xi_j <_{pr} \mu$ for $j\in\{ 0,1\}$ .

It is sufficient to discuss only an $N^0_e$ -strategy: The $R^{j}$ -satisfaction is similar to Theorem 23, and an $N^1_i$ -strategy is essentially the same as that for $N^0_e$ .

The $N^0_e$ -strategy. Suppose that the strategy starts working at a stage $s_0$ , and M is the least index with both $\alpha_0(M)$ and $\alpha_1(M)$ undefined.

Our background action defines

\begin{gather*} \alpha_0(M) := \mu(0), \ \alpha_0(M+1) := \mu(1),\ \alpha_0(M+2) := \mu(2),\ \dots;\\ \alpha_1(M) := \nu(0) = \mu f(0), \ \alpha_1(M+1) := \nu(1) = \mu f(1),\ \alpha_1(M+2) := \nu(2) = \mu f(2),\ \dots \end{gather*}

We wait for a stage $s_1 > s_0$ such that there is $w\leq s_1$ with the following properties:

• The object $\alpha_0(w) = \mu (g_{\alpha_0}(w))$ is already defined.

• The value $p_e[s_1](2w)$ is defined.

• By the stage $s_1$ , we have already witnessed that

  \begin{gather*} \mu g_{\alpha_0}(w) \neq \left\{ \begin{array}{ll} \mu g_{\alpha_1} (p_e(2w) / 2), & \text{if } p_e(2w) \text{ is even},\\ \mu f (\lfloor p_e(2w) / 2 \rfloor), & \text{if } p_e(2w) \text{ is odd} \end{array} \right\} = (\alpha_1 \oplus \nu) (p_e(2w)). \end{gather*}

If this stage $s_1$ is found, then the $N^0_e$ -requirement is satisfied: indeed, we have

\begin{align*} (\alpha_0\oplus \nu)(2w) = \alpha_0(w) = \mu g_{\alpha_0}(w) \neq (\alpha_1\oplus \nu) (p_e(2w)). \end{align*}

We show that $s_1$ will be eventually reached. Toward a contradiction, assume that there is no such $s_1$ . Then we deduce the following:

1. 1. $\mu(x) = \alpha_0(M+x)$ for all $x\in\omega$ .

2. 2. The function $q(k) := p_e(2k)$ provides a punctual reduction from $\alpha_0$ to $(\alpha_1\oplus\nu)$ .

3. 3. $\nu(x) = \alpha_1(M+x)$ for all x. By nonuniformly choosing a finite set of $\nu$ -indices, one can construct a punctual reduction from $\alpha_1$ to $\nu$ .

These facts together imply that $\mu \leq_{pr} \alpha_0 \leq_{pr} \alpha_1 \oplus \nu \leq_{pr} \nu$ . Thus, $\mu$ is punctually reducible to $\nu$ , which gives a contradiction.

The construction is arranged in a straightforward way. It is not hard to prove that the requirements $R^0$ and $R^1$ are satisfied. We showed above that every $N^{\varepsilon}_e$ , where $\varepsilon \in \{ 0,1\}$ , will be eventually satisfied. This concludes the discussion for the case of two incomparable numberings $\xi_0$ and $\xi_1$ .

The general case is obtained as follows. Here, for every $k\in\omega$ and every non-empty finite set $F\subset \omega$ , we need to satisfy the requirements:

1. $R^k$ : $\alpha_k \leq_{pr} \mu$ via a function $g_{\alpha_k}$ .

2. $N^{k,F}_e$ : If $k\not\in F$ , then $p_e\colon \alpha_k\oplus \nu \not\leq_{pr} (\bigoplus_{j\in F} \alpha_j) \oplus\nu$

Then one can show that the numberings $\xi_k := \alpha_k \oplus \nu$ satisfy the theorem.

The $N^{k,F}_e$ -strategy is similar to the $N^0_e$ -strategy described above, modulo its background actions. For all $j\in F$ and $\ell\not\in F\cup\{ k\}$ , here we put

\begin{align*} \alpha_k(M) := \mu(0), \ \alpha_k(M+1) := \mu(1),\ \alpha_k(M+2) := \mu(2),\ \dots;\\ \alpha_j(M) := \nu(0), \ \alpha_j(M+1) := \nu(1),\ \alpha_j(M+2) := \nu(2),\ \dots;\\ \alpha_{\ell}(M) := \mu(0),\ \alpha_{\ell}(M+1) := \mu(0), \ \alpha_{\ell}(M+2) := \mu(0),\ \dots. \end{align*}

All other modifications are pretty straightforward. This concludes the proof of Theorem 24.

As a consequence, we obtain the following:

Proof Sketch. It is sufficient to show that every finite Boolean algebra (treated as an upper semilattice) can be isomorphically embedded into the interval $[\!\deg_{pr}\!(\nu); \deg_{pr}\!(\mu)]$ .

Let B be a finite Boolean algebra with precisely $n+1$ atoms. Consider the sequence $(\xi_i)_{i\in\omega}$ constructed in Theorem 24. Then it is not hard to prove that the subsemilattice of $\mathcal{R}_{pr}(\mathcal{S})$ with domain

\begin{align*} \left\{ \deg_{pr}\!(\nu) \right\} \cup \big\{\!\deg_{pr} \big(\bigoplus\!_{j\in F} \xi_j \big) \,\colon F\neq \emptyset,\ F \subseteq \{ 0,1,\dots,n\} \big\} \end{align*}

is isomorphic to B.

Proof Sketch. We follow the proof of Theorem 24. The only nontrivial detail is the following: recall that in Theorem 23, we use the fact that the numbering $\mu$ is negative. In this corollary, our $\mu$ is a Turing computable numbering, and it is also negative.

7. Lattices

Note that Corollary 25 implies that for arbitrary infinite punctual families $\mathcal{S}_0$ and $\mathcal{S}_1$ , the $\Sigma_1$ -fragments of the theories $Th(\mathcal{R}_{pr}(\mathcal{S}_0))$ and $Th(\mathcal{R}_{pr}(\mathcal{S}_1))$ are the same. In this section, we witness that this is not the case already for the $\Sigma_2$ -fragments. On the one hand, we show that some Rogers pr-semilattices are lattices (Theorem 27). On the other hand, some semilattices contain minimal pairs (Proposition 29).

Selivanov (Reference Selivanov1976) obtained the following classical result: for any computable family $\mathcal{T}$ , if the semilattice $\mathcal{R}_c(\mathcal{T})$ is infinite, then it cannot be a lattice. This section illustrates that the result of Selivanov cannot be transferred to the punctual setting.

Our first theorem shows that persistently decidable families $\mathcal{S}$ (see Problem 2) exhibit a pretty tame behavior. ^{Footnote 1}

First, notice the following: since the family $\mathcal{S}$ is persistently decidable, the equivalence relation $\eta_{\nu\oplus \mu}$ is primitive recursive. Therefore, given $k,\ell\in\omega$ , one can promptly compute whether the equality $\nu(k) = \mu(\ell)$ is true: indeed, $\nu(k) = \mu(\ell)$ if and only if $(2k,2\ell+1) \in \eta_{\nu\oplus \mu}$ .

For each $s\in\omega$ , at the stage s, we will promptly define an index $w_s$ such that $\alpha(s) = \nu(w_s)$ .

At a stage s of the construction, we find a finite subset of $\omega$ :

\begin{align*} I[s] := \left\{ k \leq s \,\colon (\exists \ell \leq s)[ \nu(k) = \mu(\ell) ] \ \&\ (\forall k' < k)[\nu(k') \neq \nu(k)] \right\}. \end{align*}

It is not hard to show that the procedure of finding I[s] is punctual.

We (punctually) search for the least number $z\in I[s]$ such that $z\not\in \{ w_t\,\colon t<s\}$ . If such a number z exists, then put $w_s:=z$ and $\alpha(s) := \nu(z)$ . Otherwise, set $w_s:=0$ and $\alpha(s) := \nu(0)$ .

The construction of $\alpha$ is described. It is not difficult to prove that the numbering $\alpha$ is punctual. Moreover, since we have

\begin{align*} \bigcup_{s} I[s] = \{ k\,\colon (\forall k' < k)[\nu(k') \neq \nu(k)]\}, \end{align*}

$\alpha$ indexes the whole family $\mathcal{S}$ . In addition, the function $s\mapsto w_s$ provides a punctual reduction from $\alpha$ to $\nu$ .

We prove that $\alpha \leq_{pr} \mu$ . Fix a number $a_0$ with $\mu(a_0) = \nu(0)$ . A punctual reduction g from $\alpha$ to $\mu$ is defined as follows:

• If $w_x = 0$ , then put $g(x) := a_0$ .

• If $w_x \neq 0$ , then notice that $w_x \in I[x]$ , and hence, one can promptly find an index $\ell\leq x$ with $\mu(\ell) = \nu(w_x)$ . We set $h(x) := \ell$ .

In order to finish the proof, we need to establish the following fact: suppose that $\beta \leq_{pr} \nu$ via a function $g_0$ , and $\beta \leq_{pr} \mu$ via a function $g_1$ . Then $\beta$ is punctually reducible to $\alpha$ .

Since the numbering $\beta\oplus\nu$ is punctually decidable, we deduce that for $k,\ell\in\omega$ , one can quickly compute whether $\beta(k) = \nu(\ell)$ holds.

Let $x\in\omega$ . If $\beta(x) = \nu(0)$ , then one can nonuniformly choose an $\alpha$ -index for $\nu(0)$ , and this is enough for us. Assume that $\beta(x) \neq \nu(0)$ . It is clear that there exists k such that $k\in \widehat{I}_x := I[\max(g_0(x),g_1(x))]$ and $\beta(x) = \nu(k)$ . Let M be the greatest element of $\widehat{I}_x$ . One can show that there is (the least) index $\ell$ such that $\alpha(\ell) = \nu(k)$ , and

\begin{align*} \ell \leq \max(g_0(x),g_1(x)) + M + 1.\end{align*}

Thus, this $\ell$ can be found in a prompt way, and one can construct a punctual reduction from $\beta$ to $\alpha$ .

Indeed, let $\mu$ be some fixed computable numbering of the family $\mathcal{T}$ such that $\mu(0) \neq \mu(1)$ . Then for an arbitrary computable, not primitive recursive set $X\subseteq\omega$ , we define

\begin{align*} \nu_X(2k+1) = \mu(k),\quad \nu_X(2k) = \begin{cases} \mu(0), & \text{if } k\not\in X,\\ \mu(1), & \text{if } k\in X. \end{cases} \end{align*}

The numbering $\nu_X$ is computable, and $\eta_{\nu_X}$ is not primitive recursive.

Our second result gives an example of a Rogers pr-semilattice, which is not a lattice:

The degree of the numbering $\nu$ will be one of the components of the minimal pair. Now we build the other component: it will be induced by a Friedberg numbering $\mu$ .

Fix a non-computable c.e. set W, and a primitive recursive function q with $\mathrm{range}(q) = W$ .

For each number $k\in\omega$ , the construction of the “k-th layer” $\mu \langle k,\cdot\rangle$ proceeds as follows. Beforehand, set the values:

\begin{align*} \mu \langle k, 0\rangle (2k) := 1 \text{ and } \mu \langle k, 0\rangle (2m) := 0 \end{align*}

for all $m\neq k$ .

Consider a stage s of the construction. If $k\not \in \{ q(0),q(1),\dots,q(s)\}$ , then put

\begin{align*} \mu \langle k, 0\rangle (2s+1) := 0 \text{ and } \mu \langle k, s+1\rangle := \chi_{\{ 2k, 2s+1\}}. \end{align*}

Suppose that $s_0$ is the least stage with $k \in \{ q(0),q(1),\dots,q(s_0)\}$ . Then we set

\begin{align*} \mu \langle k, 0\rangle := \chi_{ \{ 2k,2s_0+1\} },\ \mu \langle k,s_0+1\rangle := \chi_{\{ 2k\}},\ \mu \langle k,t+2\rangle := \chi_{\{ 2k, 2t+3\}}, \end{align*}

for all $t\geq s_0$ . After the stage $s_0$ , we stop the construction of this particular k-th layer.

It is not hard to show that the constructed $\mu$ belongs to $Com_{pr}(\mathcal{S})$ , and $\mu$ is Friedberg. We need to prove that the degrees of $\nu$ and $\mu$ form a minimal pair inside $\mathcal{R}_{pr}(\mathcal{S})$ .

Toward a contradiction, assume that there is a punctual numbering $\alpha$ of $\mathcal{S}$ with punctual reductions $f\colon \alpha \leq_{pr} \nu$ and $h\colon \alpha \leq_{pr} \mu$ . Consider a c.e. set

\begin{align*} V := \{ k\in\omega\,\colon \exists x( f(x) = h(x) = \langle k,0\rangle )\}. \end{align*}

Clearly, for a number $k\in V$ and the corresponding x, we have $\nu(f(x)) = \mu(h(x)) = \chi_{\{ 2k\}}$ . Since $\mu$ is a Friedberg numbering, the function $\chi_{\{2k\}}$ has a unique $\mu$ -index $e_k$ .

Note that the construction ensures the following:

• If $k\in V$ , then $e_k = \langle k,0\rangle$ and $k\not\in \mathrm{range}(q) = W$ .

• If $k\not\in V$ , then for every $x\in\omega$ , the condition $\alpha(x) = \chi_{\{2k\}}$ implies $f(x) = \langle k,0\rangle$ and $h(x) \neq \langle k,0\rangle$ . Hence, $e_k = \langle k,s_0+1\rangle$ for some $s_0\in \omega$ , and $k\in W$ .

Thus, we deduce that $V = \overline{W}$ , which contradicts the choice of W.

1. (a) The function $\chi_{\emptyset}\not\in\mathcal{S}$ is quickly spoiling – this is witnessed by the function sp(n,t) with $sp(n,0) = \langle n+1,0\rangle$ and $sp(n,1) = \langle n+2, 0\rangle$ .

2. (b) For $k\in\omega$ , the function $\chi_{ \{2k \} }$ is quickly spoiling. The witness can be defined as follows: $sp(n,0) = \langle k, n+2\rangle$ and $sp(n,1) = \langle k, n+3\rangle$ .

Therefore, the family $\mathcal{S}$ is not persistently decidable.

8. Existence of the Greatest Element

In this section, we provide examples of Rogers pr-semilattices with greatest element and without greatest element. This gives another difference in the $\Sigma_2$ -fragments of the first-order theories.

Let $\mu$ be an arbitrary punctual numbering of the family $\mathcal{S}$ . In order to prove the theorem, we build a punctual numbering $\alpha$ of some subfamily $\mathcal{S}_0 \subseteq \mathcal{S}$ such that $\alpha \not\leq_{pr} \mu$ . Indeed, the existence of such $\alpha$ is sufficient for us, since this implies that $\mu \leq_{pr} \mu \oplus \alpha$ and $\mu \oplus \alpha \not\leq_{pr} \mu$ .

We satisfy the series of requirements:

$P_e$ : $p_e \colon \alpha \not\leq_{pr} \mu$ .

The $P_e$ -strategy. Choose the least w such that we have not talked about the object $\alpha(w)$ before. Wait for the least stage s such that:

• the value $p_e[s](w)$ is defined, and

• our computations have already provided a number $N\leq s$ with $\mu(p_e(w)) | N \neq f | N$ .

Since f does not belong to the family $\mathcal{S}$ , such a stage s will be eventually reached.

While waiting for this s, just propagate

\begin{align*} \alpha(w)(0) := f(0),\ \alpha(w)(1) := f(1),\ \alpha(w)(2) := f(2),\ \dots. \end{align*}

When the stage s and the corresponding N are found, define M as the least number such that $M\geq N$ and the value $\alpha(w)(M)$ is still undefined. Using the spoiledness of f, we promptly set $\alpha(w) := \nu(sp(M,0))$ .

This procedure is well defined, and it satisfies the $P_e$ -requirement: indeed, we have

\begin{align*} \mu(p_e(w)) | M \neq f | M = \nu(sp(M,0)) | M = \alpha(w) | M. \end{align*}

The construction is arranged in a straightforward manner. We note that in order to ensure the punctuality of $\alpha$ , the $P_e$ -strategy also has to implement some simple background actions – for example, one by one, we set $\alpha(w+1) := \nu(0)$ , $\alpha(w+2) := \nu(0)$ .

Clearly, $\alpha$ indexes a subfamily of $\mathcal{S}$ . Since every $P_e$ is eventually satisfied, we have $\alpha \not\leq_{pr} \mu$ .

We give an example of an infinite punctual family such that its Rogers pr-semilattice has the greatest element.

Lemma 33. Consider the family $\mathcal{S}$ from Example 11 – it can be defined via its punctual Friedberg numbering: for $i\in\omega$ ,

\begin{align*} \nu(i)(x) = i \text{ for all } x\in\omega. \end{align*}

Any punctual numbering $\mu\in Com_{pr}(\mathcal{S})$ is punctually reducible to $\nu$ .

We leave the following question open:

9. Persistently Decidable Families Revisited

Here we prove the result, which was announced at the end of Subsection 3.1:

The desired family $\mathcal{S}$ is constructed via its punctual numbering $\nu$ . Beforehand, we put $\nu(0) := \chi_{ \{0\} }$ .

We satisfy the following series of requirements:

$R_e$ : If $\rho_e$ is a numbering of $\mathcal{S}$ , then $\eta_{\rho_e}$ is primitive recursive.

We fix an ordering of the requirements: $R_0 < R_1 < R_2 < \dots$ .

At a stage s, the $R_e$ -readiness level is the maximal number $t\leq s$ such that for every $x\leq t$ and every $z\leq t+2$ , the value $\rho_e(x)(z)[s]$ is defined. Note that the $R_e$ -readiness level tends to infinity.

At a stage s, we define the construction readiness level $\mathrm{cr}[s] \in \omega$ . We put $\mathrm{cr}[0] := 1$ . The intuition behind this parameter is as follows. We want to add a fresh element g to the family $\mathcal{S}$ . This g will be always chosen as either $\chi_{ \{\mathrm{cr}[s]\} }$ or $\chi_{ \{ \mathrm{cr}[s]+1\}}$ . The choice of the g is motivated by the following: we want to diagonalize against a requirement $R_e$ with the highest priority – this is done via ensuring that $\rho_e$ does not index the family $\mathcal{S}$ (to be elaborated below).

The construction. Consider stage $s+1$ . We work with the requirements $R_0,R_1,\dots,R_{\mathrm{cr}[s]}$ . For $e\leq \mathrm{cr}[s]$ , let $\mathrm{rl}(e)$ be the $R_e$ -readiness level at the stage $s+1$ .

If there is $x\leq \mathrm{rl}(e)$ such that the string $\rho_e(x)| \mathrm{rl}(e)$ contains at least two ones, then the $R_e$ -requirement is declared inactive. If $R_e$ is inactive, then it is forever satisfied: indeed, we have already witnessed that the function $\rho_e(x)$ cannot be the characteristic function of a one-element set.

We compute the parameter:

\begin{align*} r := \min \{ \mathrm{rl}(e)\,\colon e\leq \mathrm{cr}[s], \text{ and } R_e \text{ is still active}\}. \end{align*}

If $r<\mathrm{cr}[s]$ , then put $\nu(s+1) := \nu(0)$ and proceed to the next stage.

Suppose that $r\geq \mathrm{cr}[s]$ . Then, we define $\mathrm{cr}[s+1] := \mathrm{cr}[s]+2$ . We search for the least $e\leq \mathrm{cr}[s]$ such that there is $x \leq \mathrm{cr}[s]$ with

\begin{align*} \rho_e(x) | (\mathrm{cr}[s]+2) = \chi_{\{\mathrm{cr}[s]\}} | (\mathrm{cr}[s]+2)\text{ or } \rho_e(x) | (\mathrm{cr}[s]+2) = \chi_{\{\mathrm{cr}[s]+1\}} | (\mathrm{cr}[s]+2). \end{align*}

If these e and x exist, we put

\begin{align*} \nu(s+1) := \begin{cases} \chi_{ \{ \mathrm{cr}[s]+1 \} }, & \text{if } \rho_e(x) | (\mathrm{cr}[s]+2) = \chi_{\{\mathrm{cr}[s]\}} | (\mathrm{cr}[s]+2),\\ \chi_{ \{ \mathrm{cr}[s] \} }, & \text{otherwise}. \end{cases} \end{align*}

In this case, we say that $R_e$ is successfully defeated. The requirement $R_e$ is declared forever inactive, and $R_e$ is satisfied – our construction ensures that $\rho_e(x)$ does not belong to $\mathcal{S}$ .

If there are no such e and x, then $\nu(s+1) := \chi_{\{\mathrm{cr}[s]\}}$ . This concludes the description of the construction.

Verification. It is not hard to show that $\nu$ is a punctual numbering. The construction ensures that for any $x\in\omega$ , there is a number k such that $\nu(x) = \chi_{ \{k\} }$ .

Since for each e, the $R_e$ -readiness level tends to infinity, we have $\mathrm{cr}[s] \xrightarrow[s\to\infty]{} \infty$ . This implies that the numbering $\nu$ indexes an infinite family $\mathcal{S}$ . Now it is sufficient to establish the following fact.

1. (a) $\mathrm{cr}[s_0] \geq e$ .

2. (b) If a requirement $R_i$ , where $i < e$ , is declared inactive at some stage $s^{\ast}$ , then this $s^{\ast}$ is strictly less than $s_0$ .

Given numbers $x < y$ , we describe a prompt procedure, which checks whether $\rho_e(x) = \rho_e(y)$ . If $y\leq s_0$ , then this checking is realized nonuniformly.

Suppose that $y>s_0$ . Compute the strings $\sigma := \rho_e(x) | y$ and $\tau := \rho_e(y) | y$ . There are two cases:

Case 1. If one of the strings $\sigma$ or $\tau$ contains 1, then it is clear that

\begin{align*} \rho_e(x) = \rho_e(y)\ \Leftrightarrow\ \sigma = \tau. \end{align*}

Case 2. Otherwise, we have $\sigma = \tau = \chi_{\emptyset} | y$ . We argue that in this case, our construction ensures that $\rho_e(x) = \rho_e(y)$ .

Toward a contradiction, assume that $\rho_e(x) \neq \rho_e(y)$ . Since $\rho_e$ indexes the family $\mathcal{S}$ , there are numbers $k,\ell \geq y$ such that $k\neq \ell$ , $\rho_e(x) = \chi_{ \{k\} }$ , and $\rho_e(y) = \chi_{ \{\ell\}}$ . Without loss of generality, one may assume that $k<\ell$ .

It is not hard to show that there is a unique $\nu$ -index $s^{\ast}>0$ such that $\nu(s^{\ast}) = \chi_{ \{\ell\} }$ . Using the description of the construction, we deduce the following properties (at the stage $s^{\ast}$ ):

• $\ell \in \{ \mathrm{cr}[s^{\ast}-1], \mathrm{cr}[s^{\ast}-1]+1\}$ .

• $s^{\ast} \geq \mathrm{rl}(e) \geq r \geq \mathrm{cr}[s^{\ast}-1] \in \{ \ell, \ell-1\}$ ; hence $s^{\ast}\geq \ell-1\geq k \geq y >s_0$ .

• Since $s^{\ast} - 1 \geq s_0$ , we have $\mathrm{cr}[s^{\ast}-1] \geq \mathrm{cr}[s_0] \geq e$ .

• $\mathrm{cr}[s^{\ast}-1] \geq y$ .

Summarizing, at the stage $s^{\ast} > s_0$ , we have $e \leq \mathrm{cr}[s^{\ast}-1]$ and $y\leq \mathrm{cr}[s^{\ast} - 1]$ such that

\begin{align*} \rho_e(y) = \chi_{ \{ \mathrm{cr}[s^{\ast}-1] \} } \text{ or } \rho_e(y) = \chi_{ \{ \mathrm{cr}[s^{\ast}-1] +1\} }. \end{align*}

Recall that after stage $s_0$ , no additional requirement $R_i$ with $i<e$ can become inactive. Therefore, at the stage $s^{\ast}$ , we successfully defeat $R_e$ , and $\rho_e$ does not index $\mathcal{S}$ . This contradicts the choice of $\rho_e$ . Therefore, we deduce that the equality $\sigma = \tau = \chi_{\emptyset} | y$ implies $\rho_e(x) = \rho_e(y)$ .

So, we established that the two discussed cases provide a prompt procedure for checking if $(x,y) \in \eta_{\rho_e}$ . Therefore, the numbering $\rho_e$ is punctually decidable.

Claim 1 shows that our family $\mathcal{S}$ is persistently decidable. This concludes the proof of Theorem 35.

After the first version of the paper was submitted, Sergey Goncharov introduced the following simple example of a persistently decidable family which is not sf-discrete.

Example 36 (Goncharov) The family $\mathcal{S}$ contains the following functions: for each $k\in\omega$ ,

\begin{align*} \begin{array}{l} g^0_{k}(0) = k+1,\ \ g^0_{k}(x+1) = 0 \text{ for all } x;\\ g^1_{k}(0) = k+1, \ \ g^1_{k}(k+1) = 1,\ \ g^1_{k}(x) = 0 \text{ for } x\not\in\{0,k+1\}. \end{array} \end{align*}

Since $g^0_k(k+1) \neq g^1_k(k+1)$ for all k, it is clear that the family $\mathcal{S}$ is not sf-discrete.

On the other hand, let f and h be arbitrary functions from the family $\mathcal{S}$ . Then $f = h$ if and only if $f(0) = h(0)$ and $f(f(0)) = h(h(0))$ . This implies that every punctual numbering of $\mathcal{S}$ is punctually decidable; hence, the family $\mathcal{S}$ is persistently decidable.

10. Friedberg Numberings

Recall that a numbering $\nu$ is Friedberg if $\eta_{\nu}$ equals to the identity relation. Friedberg numberings consitute an important classical object of study. One of the reasons behind this is the following fact: one can show that for any computable family $\mathcal{T}$ , an arbitrary computable Friedberg numbering of $\mathcal{T}$ induces a minimal element inside the semilattice $\mathcal{R}_c(\mathcal{T})$ .

We have already seen that this fact fails in the punctual setting: recall that an infinite $\mathcal{R}_{pr}(\mathcal{S})$ is downward dense (Theorem 16). Essentially, the reason behind this is the following fact: the inverse of a primitive recursive function is not necessarily primitive recursive. Furthermore, one can obtain the following:

1. (a) An infinite descending chain of degrees, such that each of them is induced by a Friedberg numbering.

2. (b) An infinite antichain of degrees, such that each of them is induced by a Friedberg numbering.

Proof Sketch. First, we observe the following simple fact: If $\nu$ and $\mu$ are Friedberg numberings of $\mathcal{S}$ , and a function f provides a punctual reduction from $\nu$ to $\mu$ , then f is a primitive recursive permutation of $\omega$ .

Let $\alpha$ be a punctual Friedberg numbering of $\mathcal{S}$ .

1. (a) It is known that there is a primitive recursive permutation f of $\omega$ such that its inverse $f^{-1}$ is not primitive recursive (Kuznecov Reference Kuznecov1950, a proof sketch in English can be found, for example, in Paolini et al. Reference Paolini, Piccolo and Roversi2016). This implies that the sequence:

   \begin{align*} \mu_0 := \alpha\circ f,\ \mu_1 := \mu_0 \circ f,\ \dots,\ \mu_{k+1} := \mu_k \circ f,\ \dots \end{align*}
   induces a strictly $\leq_{pr}$ -descending chain below $\alpha$ .

2. (b) Informally speaking, here one needs to modify the proof of Theorem 20. In the notations of the theorem, we need to build two Friedberg numberings $\nu_0$ and $\nu_1$ , while satisfying the requirements $R^{\varepsilon}$ , $N^0_j$ , and $N^1_j$ .

The numberings $\nu_i$ , which are being constructed, copy different pieces of the given Friedberg numbering $\alpha$ . We modify the $N^0_j$ -strategy appropriately.

The new $N^0_j$ -strategy. Let M be the least index such that the object $\alpha(M)$ has not been used in the construction yet. The background action is the following: we put

\begin{gather*} \nu_0(N) := \alpha(M),\ \nu_0(N+1) := \alpha(M+1),\ \nu_0(N+2) := \alpha(M+2),\ \dots\\ \nu_1(N) := \alpha(M+1),\ \nu_1(N+1) := \alpha(M+2),\ \nu_1(N+2) := \alpha(M+3),\ \dots \end{gather*}

Our strategy waits until the first stage t with the following properties: The value $p_j(N)[t]$ is defined, and the object $\nu_1(p_j(N))$ is also defined.

When the number t is found, it is clear that the $N^0_j$ -requirement is satisfied: we have

\begin{align*} \nu_0(N) = \alpha(M) \neq \alpha(\ell) = \nu_1(p_j(N)), \end{align*}

where $\ell \in \omega\setminus\{ M\}$ .

Note that we have a little technical problem here: since we require $\nu_1\in Com_{pr}(\mathcal{S})$ , we need to provide a unique $\nu_1$ -index k such that $\nu_1(k) = \alpha(M)$ . Surely, this should be done after the $N^0_j$ -requirement is satisfied. It is not difficult to resolve this problem via a careful arrangement of the construction. Proposition 37 is proved.

Recall that below any (Turing) computable negative numbering of an infinite family, one can always find a computable Friedberg numbering (see Section 3). This fact fails in the punctual setting:

The desired set W is built in stages. Note that these stages have to be arranged in a non-punctual way. At a stage e, we define finite sets W[e] and V[e].

Stage $e+1$ . Find the least index k such that:

• either the string $p_e | k$ witnesses that $p_e$ is not injective,

• or there are two indices $\ell$ and m with $\ell,m\leq k$ and $\{ p_e(\ell) \neq p_e(m) \} \subseteq \omega \setminus (W[e] \cup V[e])$ .

If these indices are found, then put $p_e(\ell)$ into W and $p_e(m)$ into V.

It is not hard to show that both W and V are infinite, $W\cap V = \emptyset$ , and for any injective $p_e$ , we have $range(p_e) \neq W$ . This concludes the construction of W.

Choose a primitive recursive (non-injective) function h with $\mathrm{range}(h) = W$ . The desired family $\mathcal{S}$ is defined via its punctual numbering: for $i,x\in\omega$ , set $(\nu(i))(x) := h(i)$ .

Assume that $\mu$ is a punctual Friedberg numbering of $\mathcal{S}$ . Then the primitive recursive injection $\psi(i) := (\mu(i))(0)$ satisfies $\mathrm{range}(\psi) = W$ , which contradicts the choice of the set W.