Fixpoints and relative precompleteness

Abstract

We study relative precompleteness in the context of the theory of numberings, and relate this to a notion of lowness. We introduce a notion of divisibility for numberings, and use it to show that for the class of divisible numberings, lowness and relative precompleteness coincide with being computable.

We also study the complexity of Skolem functions arising from Arslanov’s completeness criterion with parameters. We show that for suitably divisible numberings, these Skolem functions have the maximal possible Turing degree. In particular this holds for the standard numberings of the partial computable functions and the c.e. sets.

Keywords

Computability theory numberings

1. Introduction

A numbering is a surjective function $γ : ω \to S$ to a given set of objects S. The computability theoretic study of numberings was initiated by Ershov [8] in a series of papers. For a given numbering γ, we can consider two functions to be equivalent if their values are mapped by γ to the same objects in S. A key notion in the theory is the notion of precompleteness, which says that every partial computable (p.c.) function has a total extension modulo the numbering. Among other things, Ershov showed that Kleene’s recursion theorem [11] holds for any precomplete numbering. The recursion theorem is then the special case for the numbering of the p.c. functions. The recursion theorem has been generalized in several other ways. For example, Arslanov [5] generalized the recursion theorem from the computable functions to the class of functions computable from a Turing incomplete c.e. set. This gives a completeness criterion for c.e. sets: A c.e. set is Turing complete if and only if it can compute a fixed point free function. Selivanov [15] proved that Arslanov’s theorem also holds for any precomplete numbering. (This result was also discussed in Barendregt and Terwijn [6], who considered fixed point theorems in the more general setting of partial combinatory algebras.) Another generalization of the recursion theorem, simultaneously generalizing Arslanov’s theorem and a theorem of Visser [21], was given in Terwijn [19]. This is a result about the standard numbering of the computably enumerable (c.e.) sets, and it is currently open whether this also holds for every precomplete numbering. Variations of Arslanov’s completeness criterion that arise by considering different kinds of fixpoints were studied in Jockusch et al. [10].

In this paper, we study relative precompleteness, that is, for a given oracle A we consider which numberings γ have the property that every A-p.c. function has a total A-computable extension modulo γ. We introduce a notion of lowness (Definition 2.3), and show that for a certain class of divisible numberings that includes the standard numberings of the p.c. functions and the c.e. sets, lowness and A-precompleteness are equivalent to A being computable (Theorem 3.6).

We then proceed to study the complexity of Skolem functions that arise from Arslanov completeness criterion with parameters. It was shown in Terwijn [20] that these Skolem functions in general cannot be computable. Here we use the notions of lowness and divisibility from the first part of the paper to show that they have the maximal possible Turing degree (Corollary 4.5).

Our notation from computability theory is mostly standard. In the following, $φ_{n}$ denotes the n-th partial computable (p.c.) function, in some standard numbering of the p.c. functions. Similarly, $W_{n}$ denotes the n-th computably enumerable (c.e.) set, in some standard numbering of the c.e. sets. We denote these numberings as $φ_{(-)}$ and $W_{(-)}$ respectively. Partial computable functions are denoted by lower case Greek letters and (total) computable functions by lower case Roman letters. ω denotes the natural numbers. We write $φ_{e} (n) ↓$ if this computation is defined and $φ_{e} (n) ↑$ otherwise. We let $⟨ e, n ⟩$ denote a computable pairing function. For unexplained notation we refer to Odifreddi [14] and Soare [18].

2. Turing degrees, up to a numbering

The theory of numberings originates from Ershov [8].

Definition 2.1.
A numbering of a set S is a surjection $γ : ω \to S$ .

For every numbering γ there is an associated equivalence relation $\sim_{γ}$ on ω defined by $n \sim_{γ} m$ iff $γ (n) = γ (m)$ . Thus, as noted in Bernardi and Sorbi [7], the study of numberings is essentially equivalent to the study of countable equivalence relations.

Of particular interest are so-called precomplete numberings. The notion of a precomplete numbering was introduced by Ershov [8]. We will work with the following relativized version of precompleteness. Definition 2.2.
Given an oracle A, a numbering γ is A-precomplete if for every partial A-computable function ψ there is a total A-computable function f such that $\begin{matrix} ψ (n) ↓ ⟹ ψ (n) \sim_{γ} f (n) . \end{matrix}$ for every n. We call f a totalization of ψ modulo γ. Note that ∅-precomplete is the same as Ershov’s notion of precompleteness.
Remark.
A relativized notion of precompleteness was already studied by Selivanov [15,17]. In his definition, Selivanov requires the totalization f to be absolutely computable, rather than merely A-computable. Thus Selivanov’s notion is a combination of relativization and a lowness notion. We introduce a lowness notion for numberings in Definition 2.3 below.

2.1. Lowness

While our aim is to characterize the Turing degrees of particular functions, in the context of numberings it is more natural to show results about the following relation, which expresses a lowness property.

Definition 2.3.
Given a numbering γ and oracles A and B, we say that A is $(γ, B)$ -low if for every A-computable function f there is a B-computable function g such that for all n, $\begin{matrix} (1) & f (n) \sim_{γ} g (n) . \end{matrix}$

We will denote this by $A ⩽_{γ} B$ . We will say that A is γ-low if $A ⩽_{γ} \emptyset$ . A function g satisfying (1) will be called a γ-lift of f to B.

Let us now look at some basic properties and some simple examples of lowness results.
Theorem 2.4.
For every γ, the relation $⩽_{γ}$ is a preorder.
Proof.
Reflexivity is trivial. For transitivity, suppose $A ⩽_{γ} B ⩽_{γ} C$ and let f be an A-computable function. Since $A ⩽_{γ} B$ , f has a γ-lift g to B, and since $B ⩽_{γ} C$ , g has a γ-lift h to C. Since these are γ-lifts, for every n we have that $\begin{matrix} f (n) \sim_{γ} g (n) \sim_{γ} h (n) . \end{matrix}$ □

The following result shows that the lowness relation $⩽_{γ}$ is coarser than Turing reducibility.
Proposition 2.5.
For every numbering γ and all A and B, if $A ⩽_{T} B$ then $A ⩽_{γ} B$ .
Proof.
Since by assumption every A-computable function is B-computable, for any A-computable f we can take f itself as its γ-lift to B. □

The converse of Proposition 2.5 does not hold by Example 2.8, since for the numbering there $A ⩽_{γ} \emptyset$ for every A, but not every A is computable. In Theorem 2.13 we prove a partial converse of Proposition 2.5.
Corollary 2.6.
A set A is γ-low iff it is minimal with respect to the $⩽_{γ}$ ordering.
Proof.
A is γ-low if $A ⩽_{γ} \emptyset$ . Since $\emptyset ⩽_{T} B$ for all B, it follows from Proposition 2.5 that $A ⩽_{γ} B$ for all B. □

For numberings $γ_{1}$ and $γ_{2}$ , we say that $γ_{2}$ is a quotient of $γ_{1}$ if $n \sim_{γ_{1}} m$ implies that $n \sim_{γ_{2}} m$ for all n and m. Proposition 2.7.
Let $γ_{1}$ and $γ_{2}$ be numberings and let $γ_{2}$ be a quotient of $γ_{1}$ . If $A ⩽_{γ_{1}} B$ then $A ⩽_{γ_{2}} B$ .
Proof.
Let f be A-computable and let g be its $γ_{1}$ -lift to B. For every n, $f (n) \sim_{γ_{1}} g (n)$ . Since $γ_{2}$ is a quotient of $γ_{1}$ , it follows that $f (n) \sim_{γ_{2}} g (n)$ . □
Example 2.8.
Let A be an arbitrary oracle. Recall that $φ_{(-)}^{A}$ is the standard numbering of partial A-computable functions. By the S-m-n-theorem, for every A-computable function f there exists a primitive recursive function g such that for all n, $\begin{matrix} φ_{f (n)}^{A} = φ_{g (n)}^{A} \end{matrix}$ and hence A is $φ_{(-)}^{A}$ -low.

Since the numbering of A-c.e. sets $W_{(-)}^{A}$ is a quotient of $φ_{(-)}^{A}$ , every A is $W_{(-)}^{A}$ -low by Proposition 2.7.

2.2. Divisibility

In order to turn results about lowness into results about Turing reducibility, we will make use of the following notion of divisibility.1

¹
The notion of divisibility is very similar to the notion of an A-wide numbering from Selivanov [16]. A numbering γ is A-wide if there exists an A-c.e. sequence of γ-index sets ${(S_{n})}_{n \in ω}$ and an A-computable function u such that for all n, $u (n) \in S_{n} - ⋃_{k \neq n} S_{k}$ . Every A-wide numbering is $(ω, A)$ -divisible, but it is not clear whether the converse holds.

For

x \in ω

, we let

{[x]}_{\sim_{γ}}

denote the equivalence class of x under

\sim_{γ}

Definition 2.9.

Let $n ⩽ ω$ . A numbering γ is said to be $(n, A)$ -divisible if there exist A-computable sequences ${(x_{i})}_{i < n}$ and ${(e_{i})}_{i < n}$ such that:

For all $i < n$ , ${[x_{i}]}_{\sim_{γ}} \subseteq W_{e_{i}}^{A}$ .

For all distinct $i, j < n$ , ${[x_{i}]}_{\sim_{γ}} \cap W_{e_{j}}^{A} = \emptyset$ .

We say that the points

x_{i}

and the sets

W_{e_{i}}^{A}

witness the divisibility of γ. We use n-divisible to mean

(n, \emptyset)

-divisible.2

For a c.e. equivalence relation (or ceer, cf. Section 2.4 below) that is ω-divisible, since the equivalence classes ${[x_{i}]}_{\sim}$ are c.e., we can simply take $W_{e_{i}} = {[x_{i}]}_{\sim}$ in Definition 2.9. In Andrews and Sorbi [4], a ceer was called light if it has an effectively enumerable antichain. So for ceers, ω-divisible is exactly the same as light.

Proposition 2.10.

Let $γ_{1}$ and $γ_{2}$ be numberings and let $γ_{2}$ be a quotient of $γ_{1}$ . If $γ_{2}$ is $(n, A)$ -divisible then so is $γ_{1}$ .

Proof.

The same witnesses can be used and the requirements are easily verified. □

Example 2.11.

For an arbitrary oracle A, the numbering $W_{(-)}^{A}$ is $(ω, A)$ -divisible since we can take the enumerations $W_{x_{i}}^{A} = {i}$ and $\begin{matrix} W_{e_{i}}^{A} = {d \in ω : i \in W_{d}^{A}} . \end{matrix}$

It is then easily verified that the conditions from Definition 2.9 are met, because when $i \neq j$ then $j \notin W_{x_{i}}^{A}$ . Using the fact that $W_{(-)}^{A}$ is a quotient of $φ_{(-)}^{A}$ , we also see that $φ_{(-)}^{A}$ is $(ω, A)$ -divisible by Proposition 2.10.

Proposition 2.12.

For any oracles $A ⩽_{T} B$ and any numbering γ, if γ is $(n, A)$ -divisible then it is also $(n, B)$ -divisible.

Proof.

Trivial, since the same witnesses can be used. □

The following result is a partial converse of Proposition 2.5. Theorem 2.13.

Let γ be a numbering and let $A ⩽_{γ} B$ . If γ is $(2, B)$ -divisible then $A ⩽_{T} B$ .

Proof.

Let γ be such a numbering and let the points x, y and the c.e. sets X, Y witness the divisibility of γ. Define A-computable f by $\begin{matrix} f (n) = \{\begin{matrix} x & if n \notin A \\ y & if n \in A . \end{matrix} \end{matrix}$

Let g be a γ-lift of f to B. Note that by property (i) above, $g (n) \in X \cup Y$ , and by property (ii), if $g (n) \sim_{γ} x$ then $g (n) \notin Y$ and vice-versa. Define h as follows: $\begin{matrix} h (n) = \{\begin{matrix} 0 & if g (n) \in X \\ 1 & if g (n) \in Y . \end{matrix} \end{matrix}$

Since h is B-computable and $h = χ_{A}$ , A is B-computable. □

2.3. Partial computable functions and c.e. sets

Before we continue, let us consider a few more examples and investigate the consequences of Theorem 2.13 for the standard numberings $φ_{(-)}^{A}$ and $W_{(-)}^{A}$ . The contrapositive of Theorem 2.13 gives us some examples of non-divisible numberings.

Corollary 2.14.
For noncomputable A, the numberings $W_{(-)}^{A}$ and $φ_{(-)}^{A}$ are not 2-divisible.
Proof.
Immediate by the theorem together with Example 2.8. □

The following propositions will serve to characterize the behavior of $⩽_{γ}$ for the numbering of the A-c.e. sets for any A.
Proposition 2.15.
If A is γ-low and $B ⩽_{T} A$ , then B is γ-low as well.
Proof.
Since $B ⩽_{T} A$ implies $B ⩽_{γ} A$ by Proposition 2.5, we have $B ⩽_{γ} A ⩽_{γ} \emptyset$ . □
Proposition 2.16.
Suppose γ is $(2, A)$ -divisible and $A ⩽_{T} B$ . If $C ⩽_{γ} B$ , then $C ⩽_{T} B$ .
Proof.
Since $A ⩽_{T} B$ , γ is also $(2, B)$ -divisible by Proposition 2.12. It now follows from Theorem 2.13 that $C ⩽_{T} B$ . □

For the numbering γ of the A-c.e. sets, we can now characterize the relation $⩽_{γ}$ on the upper and lower cone of A as follows: Theorem 2.17.
Fix A, and let γ be one of $W_{(-)}^{A}$ and $φ_{(-)}^{A}$ . Then
every $B ⩽_{T} A$ is γ-low,

for all $B, C ⩾_{T} A$ , we have $B ⩽_{γ} C$ if and only if $B ⩽_{T} C$ .

Proof.
By Example 2.8, A is γ-low, so item (i) immediately follows from Proposition 2.15.

For item (ii), as we have seen in Example 2.11, γ is $(ω, A)$ -divisible, hence certainly $(2, A)$ -divisible. Suppose that $B, C ⩾_{T} A$ . If $B ⩽_{γ} C$ then $B ⩽_{T} C$ by Proposition 2.16. The converse always holds by Proposition 2.5. □

2.4. Ceers and c.e. numberings

Every numbering γ gives rise to the equivalence relation $\sim_{γ}$ . A particularly interesting class of numberings are those for which $\sim_{γ}$ is a computably enumerable equivalence relation, typically called a ceer. These were already studied by Ershov [8], who called them positive numberings. Every ceer, in turn, gives rise to a c.e. numbering by sending $n \in ω$ to its equivalence class. Ceers have been studied extensively in recent years, see for example Andrews, Badaev, and Sorbi [1], Andrews et al. [2], Andrews and Sorbi [3,4], and the references mentioned in these papers.

Definition 2.18.
A numbering γ is c.e. if the set $\begin{matrix} {⟨ x, y ⟩ : x, y \in ω, x \sim_{γ} y} \end{matrix}$ is computably enumerable.

Since each equivalence class of a c.e. numbering is c.e., the notion of n-divisibility is trivial for finite n provided that there are sufficiently many equivalence classes. However, this does not extend to the infinitary case, since it may not be possible to enumerate an infinite subset of the equivalence classes without repetition.
Proposition 2.19.
If γ is a c.e. numbering with at least $n \in ω$ equivalence classes then γ is n-divisible.
Proof.
Select n non-γ-equivalent elements $x_{i}$ and note that for all $0 ⩽ i < n$ , the set $\begin{matrix} {y \in ω : x_{i} \sim_{γ} y} \end{matrix}$ is computably enumerable. □
Corollary 2.20.
For every c.e. numbering γ with at least two equivalence classes, the notions $A ⩽_{T} B$ and $A ⩽_{γ} B$ are equivalent.
Proof.
This follows immediately from Proposition 2.5 and 2.13. □
Theorem 2.21.
There exists a c.e. numbering γ with ω equivalence classes that is not ω-divisible. 3
³
Note added in proof: in the terminology of Andrews and Sorbi [4], this says that there exists a ceer that is not light. This theorem is thus also a corollary of Theorem 3.3 from [4].

In Proposition 2.24 we will see that such a γ cannot be precomplete. In the terminology of Andrews and Sorbi [4],
Proof.
We construct a c.e. set of pairs A and let $\sim_{γ}$ be the least equivalence relation containing A. The numbering γ then arises by sending every $n \in ω$ to its $\sim_{γ}$ -equivalence class.

To guarantee that γ is not ω-divisible, we ensure that for every total computable function f there is some equivalence class of γ that appears in the output of f at least twice, and thus that taking $x_{i} = f (i)$ does not satisfy requirement (ii) in Definition 2.9. We do this by ensuring the following requirements are satisfied: $\begin{matrix} R_{e} : f = φ_{e} total and injective ⟹ \exists i, j . ⟨ f (i), f (j) ⟩ \in A . \end{matrix}$

Let $A_{s}$ be the set of pairs enumerated up to stage s. Throughout the construction, we keep track of a function $g_{s}$ that maps n to the least requirement e that has contributed a value to the equivalence class of n in $A_{s}$ , or ∞ if there is no such requirement. We also track which requirements have acted.

At stage $s = 0$ , set $A_{0}$ to be empty.

At stage $s + 1$ , we say that a requirement $R_{e}$ needs attention if it has not acted previously and there exist i, j such that $x = φ_{e, s} (i) ↓$ and $y = φ_{e, s} (j) ↓$ and $g_{s} (x), g_{s} (y) > e$ .

If no requirement $R_{e}$ , with $e < s$ , requires attention, do nothing for this stage. Otherwise, let $e < s$ be least such that $R_{e}$ requires attention, enumerate $⟨ x, y ⟩$ into A, and mark $R_{e}$ as having acted. This completes the construction.

To see that the requirements are satisfied, it suffices to show that if $f = φ_{e}$ is total and injective, then $R_{e}$ eventually acts, since any requirement that acts is clearly satisfied. Suppose the antecedent of $R_{e}$ is satisfied. By induction, there is some stage s after which no requirement $d < e$ acts and thus $g_{s}^{- 1} ({0, \dots, e - 1})$ is fixed. Since f is total and injective it is also unbounded, and thus there exist i, j such that $g_{s} (f (i)), g_{s} (f (j)) > e$ and $R_{e}$ will thus eventually act.

It remains to show that A induces infinitely many equivalence classes in γ, which we will do by showing every equivalence class is finite. Let $x \in ω$ . If the equivalence class of x is a singleton, then it is clearly finite. Otherwise, there is some requirement $R_{e}$ that first extended the equivalence class of x. By construction, every next extension was by some requirement $R_{d}$ with $d < e$ , and since there are only finitely many such requirements, the equivalence class of x was only extended finitely often and is thus finite.

It follows that every equivalence class is finite, and thus that $\sim_{γ}$ has infinitely many equivalence classes. However, since every computable function is non-injective modulo γ, it follows that γ is not ω-divisible. □

In practice, many ceers from the literature are in fact ω-divisible. In particular, we will see in Proposition 2.24 that all precomplete ceers are ω-divisible. First, let us consider two examples from Visser [21].
Example 2.22.
Let $M_{λ β}$ be the set of λ-calculus terms modulo β-equivalence and let $γ_{λ}$ be the numbering given by some effective coding of terms.

Since β-equivalence is a c.e. relation, $γ_{λ}$ is c.e. To see that $γ_{λ}$ is ω-divisible, note that by strong normalization and the diamond property, it suffices to enumerate any infinite set of non-equal terms in normal form. This can be done, for example, by taking the Church numerals $λ f . λ x . f^{n} (x)$ .
Example 2.23.
Let A be an arithmetical set and let γ be the numbering induced by the equivalence relation $\begin{matrix} n \sim_{γ} m ⟺ PA ⊢ \forall x . φ_{n}^{A} (x) ≃ φ_{m}^{A} (x) . \end{matrix}$

Since we can enumerate proofs in PA, γ is a c.e. numbering. To see that γ is ω-divisible we can take $φ_{f (n)}^{A} = n$ , which gives us an enumeration f of codes of distinct functions. Since PA is sound, these codes are not identified by γ.

Note that by Theorem 2.13, it follows that if A noncomputable then A is not γ-low. This is in contrast with the numbering $φ_{(-)}^{A}$ , where A is always $φ_{(-)}^{A}$ -low.

An analogue of the following result for wide numberings was already mentioned by Selivanov [17]. Proposition 2.24.
Every precomplete c.e. numbering is ω-divisible. 4
⁴
An alternative way to phrase this is to say that every precomplete ceer is light, cf. footnote 2. This is also easy to see using the result of Bernardi and Sorbi [7] that every precomplete ceer is universal, so that in particular the identity relation reduces to it. The latter property is equivalent to being light.

Proof.
This follows from a theorem due to Lachlan [12], stating that every two precomplete c.e. numberings are recursively isomorphic. Let γ be a precomplete c.e. numbering. By Lachlan’s theorem γ is recursively isomorphic to $γ_{λ}$ from Example 2.22 above. There thus exists a recursive permutation h such that $γ_{λ} (n) = γ_{λ} (m)$ iff $γ (n) = γ (m)$ . Taking ${(x_{n})}_{n \in ω}$ to be the enumeration of Church numerals, ${(h (x_{n}))}_{n \in ω}$ witnesses that γ is ω-divisible as well. □

3. Relative precompleteness

The following is Ershov’s version of the recursion theorem for precomplete numberings [9]. In relativized form it reads as follows:

Theorem 3.1 (Recursion theorem for precomplete numberings).

If γ is an A-precomplete numbering then every A-computable function f has a fixpoint modulo γ; that is, for every A-computable f there is an $n \in ω$ such that $f (n) \sim_{γ} n$ .

Kleene’s second recursion theorem (cf. Moschovakis [13] for the rich history of this result) is a uniform, parameterized version of the first recursion theorem. It also holds for precomplete numberings (with the same proof), and reads as follows:

Theorem 3.2 (Recursion theorem with parameters).

If γ is an A-precomplete numbering then for every binary A-computable function h there is a unary A-computable function f such that for all $n \in ω$ , $\begin{matrix} h (n, f (n)) \sim_{γ} f (n) . \end{matrix}$

Arslanov [5] generalized the recursion theorem from computable functions to the class of functions that are computable from an incomplete c.e. set. Phrased differently: A c.e. set is Turing complete if and only if it can compute a fixpoint free function. This is Arslanov’s completeness criterion. Selivanov [15] (see also [6]) proved that Arslanov’s theorem also holds for any precomplete numbering:

Theorem 3.3 (Arslanov’s completeness criterion for precomplete numberings).

If A is Turing incomplete and c.e. and γ is a precomplete numbering, then every A-computable function f has a fixpoint modulo γ.

At first glance, we may hope to prove Arslanov’s completeness criterion by showing that that if A is incomplete and c.e. and γ is precomplete, then γ is also A-precomplete. In the remainder of this section we show that this is not the case for precomplete ω-divisible numberings. As we have seen in the previous section, this includes the numberings $W_{(-)}$ and $φ_{(-)}$ .

Lemma 3.4.
If an A-precomplete numbering γ is 2-divisible and the totalization u of the universal function modulo γ is computable, then A is γ-low and therefore computable.
Proof.
Let γ be such a numbering and let u be the totalization of the universal function. Suppose u is computable. Let $f = φ_{e}^{A}$ be a total A-computable function. Define a computable function g by $\begin{matrix} g (n) = u (e, n) . \end{matrix}$

Now for all n, $\begin{matrix} g (n) = u (e, n) \sim_{γ} φ_{e}^{A} (n) = f (n) \end{matrix}$ and thus A is γ-low. By Theorem 2.13, A is computable. □
Theorem 3.5.
Let $A ⩽_{T} B$ . If a numbering γ is $(ω, A)$ -divisible and γ is B-precomplete, then $A \equiv_{T} B$ .
Proof.
Let $A ⩽_{T} B$ and let u be the totalization of a partial B-computable universal function modulo γ. Let ${(x_{i})}_{i \in ω}$ and ${(X_{i})}_{i \in ω}$ witness that γ is $(ω, A)$ -divisible.

Let $U (e, x)$ be the use of $u (e, x)$ and define a B-computable function f by $\begin{matrix} f (n) = max_{\begin{array}{c} i ⩽ n \\ j ⩽ n \end{array}} U (i, j) . \end{matrix}$

If ${lim}_{n \to \infty} f (n)$ is finite then u is computable and thus B is γ-low by Lemma 3.4 and is thus computable by Theorem 2.13. It follows that $A \equiv_{T} B \equiv_{T} \emptyset$ .

Suppose, then, that ${lim}_{n \to \infty} f (n)$ diverges. Let $D_{(-)}$ be the canonical numbering of finite sets. Since f is B-computable, there is a B-computable function g such that $\begin{matrix} D_{g (n)} = {b \in B : b ⩽ f (n + 1)} . \end{matrix}$

Let $u^{'} (e, n, m)$ be the computable function that acts like $u (e, n)$ but with queries to the oracle B replaced by reads from $D_{m}$ .

Now fix e to be a code of $n \mapsto x_{g (n)}$ . Note that this function is B-computable, since g is B-computable, the sequence $x_{i}$ is A-computable, and $A ⩽_{T} B$ . Note that we have $\begin{matrix} (2) & u (e, n) \sim_{γ} φ_{e}^{B} (n) = x_{g (n)} . \end{matrix}$ Define the partial A-computable function δ by $\begin{matrix} δ (n, m) = least i such that u^{'} (e, n, m) \in X_{i} . \end{matrix}$

For any $n, m \in ω$ with $n ⩾ e$ , if $D_{m}$ agrees with B on the first $f (n)$ bits, then $δ (n, m)$ terminates after using at most the first $f (n)$ bits of $D_{m}$ and $D_{δ (n, m)}$ agrees with B on the first $f (n + 1)$ bits. Namely, $u^{'} (e, n, m) = u (e, n)$ since by assumption $D_{m}$ gives the correct answers to the oracle queries below $f (n)$ , which includes the use of $u (e, n)$ , and because by (2) we have $u (e, n) \sim_{γ} x_{g (n)}$ it follows that $u^{'} (e, n, m) \in X_{g (n)}$ by the properties of the dividing sets $X_{i}$ . Hence $δ (n, m) ↓ = g (n)$ .

Let $D_{c}$ be the code of the first $f (e)$ bits of the oracle B. By recursion, we can define $\begin{array}{l} b (0) = D_{c} \\ b (k + 1) = δ (k, b (k)) . \end{array}$

Now b is an A-computable sequence of canonical codes of increasing initial segments of B, where $D_{b (n)}$ contains at least $f (n)$ bits if $n ⩾ e$ . Since ${lim}_{n \to \infty} f (n) = \infty$ , eventually we can compute all of B this way. Since δ is A-p.c., it follows that $B ⩽_{T} A$ . □

Putting this together with earlier results, we obtain the following equivalence.
Theorem 3.6.
For any precomplete ω-divisible numbering γ, the following are equivalent:
A is computable.

A is γ-low.

γ is A-precomplete.
In particular, this is the case for γ one of $W_{(-)}$ and $φ_{(-)}$ ,
Proof.
If A is computable, by Proposition 2.5 it is γ-low. Since γ is already precomplete, it is also A-precomplete.

If A is γ-low, then by Theorem 2.13 it is in fact computable.

If γ is A-precomplete, Theorem 3.5 applies and again A is computable.

As we have seen $W_{(-)}$ and $φ_{(-)}$ are precomplete and ω-divisible and thus satisfy the requirements of the theorem. □

Taking A noncomputable, and considering the numbering $W_{(-)}$ , we see from Theorem 3.6 that this numbering is precomplete, but not A-precomplete. If moreover A is c.e. and incomplete, then by Arslanov’s completeness criterion (Theorem 3.3) we know that every A-computable function has a fixpoint for this numbering. So we see that the existence of fixpoints of A-computable functions does not, in general, give us A-precompleteness, even for a precomplete numbering.
Corollary 3.7.
There exists a set A and a numbering γ such that γ is precomplete but not A-precomplete.

We currently do not know if the converse implication also does not hold, so we ask:
Question 3.8.
Does there exists a set A and a numbering γ such that γ is A-precomplete but not precomplete?
4. Skolem functions

Just as the recursion theorem has a version with parameters (Theorem 3.2), we can formulate in the same way a parameterized version of Arslanov’s completeness criterion (Theorem 3.3). Again we can formulate this for arbitrary precomplete numberings, and in relativized form, as follows:

Theorem 4.1 (Arslanov’s completeness criterion with parameters, for precomplete numberings).

If A is a incomplete c.e. set and γ is a precomplete numbering then for every A-computable binary function h there is an A-computable function f such that $\begin{matrix} (3) & h (n, f (n)) \sim_{γ} f (n) . \end{matrix}$

4.1. Complexity of Skolem functions

It was already stated in Arslanov [5] that this form of Arslanov’s completeness criterion holds for the standard numbering of c.e. sets $W_{(-)}$ . Following the notation in [20], we refer to f as in (3) as the Skolem function, since it is the Skolemization of $\begin{matrix} \forall n \exists x . h (n, x) \sim_{γ} x, \end{matrix}$ which holds by Theorem 3.3.

Definition 4.2.
For a given numbering γ, we say that there exist B-computable Skolem functions for A-computable functions if f as in (3) can be chosen to be B-computable. If this is the case we write $Skolem (A, B, γ)$ .

Note that Theorem 4.1 says that $Skolem (A, A, γ)$ for every incomplete c.e. A and precomplete γ. This can be proved by analyzing the original proof of Arslanov. For completeness we include a proof here.
Proof of Theorem 4.1.
Let A be a incomplete, c.e. set and let γ be a precomplete numbering. Let $\hat{h}$ be a computable approximation of h and let m be its A-computable modulus. By the properties of a modulus we have that for all $n, x \in ω$ and all $s ⩾ m (n, x)$ , $\hat{h} (n, x, s) = h (n, x)$ .

Define $\begin{matrix} ψ (n, x, k) = \{\begin{matrix} \hat{h} (n, x, s_{k}) & if k \in \emptyset^{'} and s_{k} is minimal such that k \in \emptyset_{s}^{'} \\ ↑ & if k \notin \emptyset^{'} . \end{matrix} \end{matrix}$

Let g be a totalization of ψ modulo γ. By the recursion theorem with parameters there is a computable $\hat{f} (n, k)$ such that for all $n, k \in ω$ , $\begin{matrix} \hat{f} (n, k) \sim_{γ} g (n, \hat{f} (n, k), k) . \end{matrix}$

Define $\begin{matrix} r (n) = k where ⟨ s, k ⟩ = μ ⟨ s, k ⟩ [m (n, \hat{f} (n, k)) ⩽ s \land k \in \emptyset_{s}^{'}] . \end{matrix}$

We claim r is total. Note that by minimality, $s = s_{k}$ from above. Suppose there exists n such that no such s and k exist. Then for all $k \in \emptyset^{'}$ , $m (n, \hat{f} (n, k)) > s_{k}$ and thus $k \in \emptyset_{m (n, \hat{f} (n, k))}^{'}$ . It follows that $\emptyset^{'} ⩽_{T} A$ , contradicting our assumption that A is incomplete.

Since $r (n)$ is total and $m (n, \hat{f} (n, r (n))) ⩽ s_{r (n)}$ it follows that $\begin{matrix} h (n, \hat{f} (n, r (n)) = \hat{h} (n, \hat{f} (n, r (n)), s_{r (n)}) \end{matrix}$ and thus since $r (n) \in \emptyset^{'}$ $\begin{array}{l} h (n, \hat{f} (n, r (n)) & = \hat{h} (n, \hat{f} (n, r (n)), s_{r (n)}) \\ \sim_{γ} g (n, \hat{f} (n, r (n)), r (n)) \\ \sim_{γ} \hat{f} (n, r (n)) . \end{array}$

Therefore, $f (n) = \hat{f} (n, r (n))$ is a fixpoint of h modulo γ. □

This shows that the Skolem functions have degree at most A. In Terwijn [20, Theorem 3.1] it was shown that, for the numbering $W_{(-)}$ , the Skolem functions in general cannot be computable. We will now show that the degree of the Skolem functions for an incomplete c.e. set A is in fact equal to A.
Theorem 4.3.
For every A, B and every numbering γ, if $Skolem (A, B, γ)$ then $A ⩽_{γ} B$ .
Proof.
Suppose that for every A-computable h there exists such a B-computable f. Let g be an A-computable function and define $h (n, x) = g (n)$ . Take f B-computable such that $h (n, f (n)) \sim_{γ} f (n)$ for all n. It now follows that $\begin{matrix} g (n) = h (n, f (n)) \sim_{γ} f (n) . \end{matrix}$ □
Corollary 4.4.
Let A and B be oracles, and let γ be a $(2, B)$ -divisible numbering. If $Skolem (A, B, γ)$ then $A ⩽_{T} B$ .
Proof.
It follows from Theorem 4.3 that $A ⩽_{γ} B$ , and thus $A ⩽_{T} B$ by Theorem 2.13 □
Corollary 4.5.
Suppose that A is an incomplete c.e. set, and let γ be one of the numberings $W_{(-)}$ or $φ_{(-)}$ . Then $Skolem (A, B, γ)$ if and only if $A ⩽_{T} B$ .
Proof.
By Example 2.11 the numberings $W_{(-)}$ and $φ_{(-)}$ are ω-divisible, hence 2-divisible, so if $Skolem (A, B, γ)$ then $A ⩽_{T} B$ by Corollary 4.4. Conversely, if $A ⩽_{T} B$ then $Skolem (A, B, γ)$ by Theorem 4.1. □

In Barendregt and Terwijn [6, Question 3.4] the question was posed whether the uniformly computable existence of fixpoints for a numbering implies that the numbering is precomplete. This question remains open, but we note here that in general the answer is negative for the relativized version of this question. Namely, we see from Theorem 4.1, together with Theorem 3.6, that even if every A-computable family of A-computable functions has a fixpoint modulo γ, computable uniformly in A, this does not guarantee that γ is A-precomplete.
4.2. Comparison of results

After putting this paper on the arXiv, M. M. Arslanov was kind enough to send us a yet unpublished but submitted paper (Fixed-point selection functions) that also contains results about the complexity of computing fixpoints, some of which are related to the results of this paper.

The two papers use slightly different terminology. Since we are only concerned with the behaviour of total (A-)computable functions, we have no equivalent of Arslanov’s notion of the existence of a fixed point selection function for a set A, which is phrased in terms of a universal function relative to A. Our notion $Skolem (A, B, γ)$ corresponds to the existence of a B-computable fixed point selection function modulo γ for every A-computable function.

The most notable relation between our results is that our Corollary 4.5 generalizes Arslanov’s Theorem 7 to the case when B is not comparable to A. The negation of $Skolem (A, B, γ)$ is equivalent to the existence of a function $h ⩽_{T} A$ that has no B-computable fixed point selection function. Arslanov’s result that h can be taken of degree A can be obtained by encoding A into h.

Footnotes

Acknowledgement

We thank Andrea Sorbi for several helpful remarks about ceers.

References

Andrews,

Badaev and

Sorbi, A survey on universal computably enumerable equivalence relations, in: Computability and Complexity,

Day et al., eds, Springer, 2017, pp. 418–451. doi:10.1007/978-3-319-50062-1_25.

Andrews,

Lempp,

J.S.

Miller,

K.M.

Ng,

San Mauro and

Sorbi, Universal computably enumerable equivalence relations, Journal of Symbolic Logic 79 (2014), 60–88. doi:10.1017/jsl.2013.8.

Andrews and

Sorbi, Jumps of computably enumerable equivalence relations, Annals of Pure and Applied Logic 169 (2018), 243–259. doi:10.1016/j.apal.2017.12.001.

Andrews and

Sorbi, Joins and meets in the structure of ceers, Computability 8 (2019), 193–241. doi:10.3233/COM-180098.

M.M.

Arslanov, On some generalizations of the fixed point theorem, Soviet Mathematics (Izvestiya VUZ. Matematika) 25(5) (1981), 1–10, (English translation).

H.P.

Barendregt and

S.A.

Terwijn, Fixed point theorems for precomplete numberings, Annals of Pure and Applied Logic 170 (2019), 1151–1161. doi:10.1016/j.apal.2019.04.013.

Bernardi and

Sorbi, Classifying positive equivalence relations, Journal of Symbolic Logic 48(3) (1983), 529–538. doi:10.2307/2273443.

Y.L.

Ershov, Theorie der Numerierungen I, Zeitschrift für mathematische Logik und Grundlagen der Mathematik 19 (1973), 289–388. doi:10.1002/malq.19730191901.

Y.L.

Ershov, Theorie der Numerierungen II, Zeitschrift für mathematische Logik und Grundlagen der Mathematik 21 (1975), 473–584. doi:10.1002/malq.19750210164.

10.

C.G.

JockuschJr.,

Lerman,

R.I.

Soare and

R.M.

Solovay, Recursively enumerable sets modulo iterated jumps and extensions of Arslanov’s completeness criterion, Journal of Symbolic Logic 54(4) (1989), 1288–1323. doi:10.1017/S0022481200041104.

11.

S.C.

Kleene, On notation for ordinal numbers, Journal of Symbolic Logic 3 (1938), 150–155. doi:10.2307/2267778.

12.

A.H.

Lachlan, A note on positive equivalence relations, Mathematical Logic Quarterly 33(1) (1987), 43–46. doi:10.1002/malq.19870330106.

13.

Y.N.

Moschovakis, Kleene’s amazing second recursion theorem, Bulletin of Symbolic Logic 16(2) (2010), 189–239. doi:10.2178/bsl/1286889124.

14.

Odifreddi, Classical Recursion Theory, Vol. 1, Studies in Logic and the Foundations of Mathematics, Vol. 125, North-Holland, Amsterdam, 1989.

15.

V.L.

Selivanov, Index sets of quotient objects of the post numeration, Algebra i Logika 27(3) (1988), 343–358, (English translation 1989).

16.

V.L.

Selivanov, Precomplete numberings and functions without fixed points, Matematicheskie Zametki 51(1) (1992), 149–155, (English translation 1992).

17.

V.L.

Selivanov, in: Precomplete Numberings, Itogi Nauki i Tekhniki, Sovremennaya Matematika i ee Prilozheniya, Tematicheskie Obzory, Vol. 157, 2018, pp. 106–134.

18.

R.I.

Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.

19.

S.A.

Terwijn, Generalizations of the recursion theorem, Journal of Symbolic Logic 83(4) (2018), 1683–1690. doi:10.1017/jsl.2018.52.

20.

S.A.

Terwijn, The noneffectivity of Arslanov’s completeness criterion and related theorems, Archive for Mathematical Logic 59(5) (2020), 703–713. doi:10.1007/s00153-020-00712-z.

21.

Visser, Numerations, λ-calculus, and arithmetic, in: To H.B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism,

J.P.

Seldin and

J.R.

Hindley, eds, Academic Press, 1980, pp. 259–284.