Numberings,c.e. oracles,and fixed points

Abstract

The Arslanov completeness criterion says that a c.e. set A is Turing complete if and only there exists an A-computable function f without fixed points, i.e. a function f such that $W_{f (x)} \neq W_{x}$ for each integer x. Recently, Barendregt and Terwijn proved that the completeness criterion remains true if we replace the Gödel numbering $x \mapsto W_{x}$ with an arbitrary precomplete computable numbering. In this paper, we prove criteria for noncomputability and highness of c.e. sets in terms of (pre)complete computable numberings and fixed point properties. We also find some precomplete and weakly precomplete numberings of arbitrary families computable relative to Turing complete and non-computable c.e. oracles respectively.

Keywords

Arslanov completeness criterion fixed point complete numbering precomplete numbering weakly precomplete numbering computable numbering minimal numbering high set

1. Introduction

As is known, Kleene’s recursion theorem and Rice’s theorem hold for the Gödel numbering of the family of all c.e. sets, and these theorems play an important role in the development of computability theory. The notion of complete numbering, introduced by Mal’tsev [18,19], is independent of the nature of the elements of the enumerable family, and it became a very productive notion, closely related to both Kleene’s and Rice’s theorems. Recently Barendregt and Terwijn proved [7] that Arslanov’s completeness criterion [3,4] holds if one uses complete, or even precomplete, numberings, instead of the Gödel numbering $x \mapsto W_{x}$ . In this paper, we prove criteria for noncomputability and highness of c.e. sets using (pre)complete computable numberings, which also generalize the Recursion Theorem. Also, for all families computable relative to Turing complete (non-computable) c.e. oracles, we provide their (weakly) precomplete numberings. These results allow us to solve the question posed by Barendregt and Terwijn [7] about the existence of numberings that are not precomplete, but nevertheless satisfy the Recursion Theorem with Parameters.

The general theory of numberings was initiated in the mid-1950s by Kolmogorov [16,25]. Later, Uspensky carried out a systematic study of computable numberings of partial computable functions and applied them to the theory of algorithms [24]. Independently, a study of computable numberings of the family of all unary partial computable functions was initiated by Rogers [21]. The further development of the theory of numberings was undertaken by Ershov, Lavrov, Lachlan, Khutoretsky, V’jugin, Selivanov, Denisov, Goncharov, Badaev, Kummer and others (cf. the book by Ershov [9]).

The results of the theory of numberings are mostly applied in recursive mathematics. One of the powerful method for constructing families of c.e. sets with a finite number of computable single-valued numberings suggested by Goncharov [11] is the starting-point of the research on the algorithmic dimension of computable models. Applications of the theory of numberings to classical computability theory are also significant. For instance, using a theorem of Goncharov [11] on the number of computable single-valued numberings of families of c.e. sets, Kummer [17] solved a famous problem on the recursive isomorphism types of partial computable functions. Namely, he proved that for each integer k there exists a computable function having exactly k recursive isomorphism types.

An interesting version of the theory of precomplete numberings was developed by Weihrauch [26,27], who extended this theory from numberings to representations of topological spaces playing an important role in computable analysis and topology. Besides, we might mention application of the results on numberings in c.e. equivalences [2], in proof theory [13], in learning theory [1], etc.

2. Background

In this section, we give some required background results and definitions. For terminology and notations relative to computability theory, our main references are the textbooks by Soare [22,23]. For the main concepts and notions of the theory of numberings we refer to the book by Ershov [9] (see also [10]).

A surjective mapping α of the set $N$ of nonnegative integers onto a nonempty set S is called a numbering of S.

Definition 1.
A numbering α of a nonempty set S is called complete with respect to $a \in S$ if for every partial computable function ψ there exists a computable function h such that, for every x, $\begin{matrix} α (h (x)) = \{\begin{matrix} α (ψ (x)), & if ψ (x) ↓, \\ a, & if ψ (x) ↑ . \end{matrix} \end{matrix}$

For instance the numbering $x \mapsto W_{x}$ is complete with respect to ∅. For a thorough investigation of complete numberings, see [6,8]. The following definition is a bit less demanding, [8]:
Definition 2.
A numbering α is precomplete if for every partial computable function ψ there is a computable function h such that, for every x, if $ψ (x) ↓$ , then $α (ψ (x)) = α (f (x))$ .

It is immediate to see that every complete numbering is precomplete. The following theorem provides an equivalent definition of precomplete numbering.
Theorem 1 (Ershov’s Recursion Theorem with Parameters [9]).

A numbering α is precomplete if and only if for every binary partial computable function ψ there exists a computable function h such that for every integer x we have $α (ψ (x, h (x))) = α (h (x))$ whenever $ψ (x, h (x)) ↓$ .

Suppose that A is a subset of $N$ and $F$ is a nonempty family of A-c.e. sets.

Definition 3.
A numbering α of $F$ is said to be A-computable [12] if there exists a computable function f such that $α (x) = W_{f (x)}^{A}$ for each $x \in N$ .

If we skip the oracle A in this definition, we arrive at the classical notion of computable numbering [9]. We say that a family $F$ is A-computable if it has an A-computable numbering. Families containing more than one element are said to be non-trivial.

Our notation from computability theory is mostly standard. In the following, $φ_{e}$ denotes the partial computable function with the Gödel number e. We write $φ_{e} (x) ↓$ if this computation converges, and $φ_{e} (x) ↑$ otherwise. Without loss of generality we assume that if $φ_{e} (x)$ is defined at a stage s, then $φ_{e} (x) < s$ . We let $⟨ x, y ⟩$ denote the computable pairing function $(x, y) \mapsto 2^{x} (2 y + 1) - 1$ . A double sequence ${F_{x, s}}_{x, s \in N}$ of finite sets is said to be strongly computable if there exists a binary computable function f such that, for all x, s, the canonical index of $F_{x, s}$ equals to $f (x, s)$ .

It is not hard to show that, for a Turing incomplete set A, if an A-computable numbering α is complete with respect to some set $B \in α (N)$ , then B is the least element of $α (N)$ under inclusion. Indeed, assume that, for a Turing incomplete set A, there exists an A-computable numbering α complete with respect to a set $B \in α (N)$ such that $B ⊈ α (x_{0})$ for some $x_{0}$ . Let $a \in B ∖ α (x_{0})$ . Now we define a partial computable function ψ by $\begin{matrix} ψ (x) = \{\begin{matrix} x_{0}, & if x \in \emptyset^{'}, \\ undefined, & if x \notin \emptyset^{'} . \end{matrix} \end{matrix}$ Let h be a computable function given by the completeness of α: $\begin{matrix} α (h (x)) = \{\begin{matrix} α (ψ (x)), & if ψ (x) ↓, \\ B, & if ψ (x) ↑ . \end{matrix} \end{matrix}$ Then, for every x, we have $x \notin \emptyset^{'}$ if and only if $a \in α (h (x))$ . Hence, $\emptyset^{'} ⩽_{T} A$ . This is a contradiction.
Definition 4.
A numbering α is said to be cylindric if there exists a binary computable function f such that $α (f (x, t)) = α (x)$ for all x, t and $f (x, t_{0}) \neq f (x, t_{1})$ for all x and all different $t_{0}$ , $t_{1}$ .

It is known [9] that every precomplete numbering is cylindric. Let α and β be numberings of a set S.
Definition 5.
We say that α is reducible to β (in symbols, $α ⩽ β$ ) if $α = β \circ f$ for some computable function f.

A numbering μ of a set S is said to be minimal if $μ ⩽ α$ for every numbering α of S with $α ⩽ μ$ .
3. Criteria for noncomputability and highness

In this section, we provide criteria for noncomputability and highness of c.e. sets using (pre)complete computable numberings. Let us first prove the first one.

Theorem 2.
Let A be a c.e. set. Then the following statements are equivalent:
A is noncomputable;

for any computable numbering α of a non-trivial family there exists a function $f ⩽_{T} A$ such that for every infinite c.e. set W there is an $x \in W$ with $α (f (x)) \neq α (x)$ ,

there exist a precomplete numbering α and a function $f ⩽_{T} A$ such that for every infinite c.e. set W there is an $x \in W$ with $α (f (x)) \neq α (x)$ .

Proof.
Let A be a noncomputable c.e. set. Since every noncomputable c.e. degree is hyperimmune (see, e.g., [22, V Theorem 2.5]) and every hyperimmune degree is bi-immune [14], we can fix a bi-immune set $A_{0}$ such that $A_{0} \equiv_{T} A$ . To prove the implication (1) ⇒ (2), for a given computable numbering α of a non-trivial family, we fix integers $x_{0}$ , $x_{1}$ such that $α (x_{0}) ⊈ α (x_{1})$ and define a function $f ⩽_{T} A$ by $\begin{matrix} f (x) = \{\begin{matrix} x_{0}, & if x \notin A_{0}, \\ x_{1}, & if x \in A_{0} . \end{matrix} \end{matrix}$ Let $a \in α (x_{0}) ∖ α (x_{1})$ and let W be an infinite c.e. set. If there are infinitely many $y \in W$ with $a \in α (y)$ , then there exists an $x \in W \cap A_{0}$ such that $a \in α (x)$ . Therefore, $a \in α (x) ∖ α (x_{1}) = α (f (x))$ . If there is a z such that $a \notin α (y)$ for each $y \in W$ , $y ⩾ z$ , then there is an $x \in W ∖ A_{0}$ with $a \notin α (x)$ . Therefore, $a \in α (x_{0}) = α (f (x)) ∖ α (x)$ . Hence, there is an $x \in W$ with $α (f (x)) \neq α (x)$ .

The implication (2) ⇒ (3) is clear. To prove the implication (3) ⇒ (1) it suffices to show that for every computable function f there exists an infinite c.e. set W such that $α (f (x)) = α (x)$ for each $x \in W$ . Using [2, Theorem 2.4], we can fix an injective computable function g such that $α (f (g (x))) = α (g (x))$ for each x. Then we can define $W = rng g$ . □

We now turn to the proof of the highness criterion. We need the following two lemmas.
Lemma 1.
Let A be a high set and let α be a computable numbering of a non-trivial family containing a computable set B. Then there exists a function $f ⩽_{T} A$ satisfying the following conditions:
for each z either $α (z) \neq B$ or $α (f (z)) \neq B$ ,

for every computable set C such that $\begin{matrix} (1) & \forall y \in C [α (y) ⊈ B] \end{matrix}$ the set ${x \in C : α (f (x)) = α (x)}$ is finite.

Proof.
If $α (x) \subseteq B$ for each x, we take a b such that $α (b) \neq B$ and define f to be the constant function $f \equiv b$ .

Otherwise, we fix integers $x_{0}$ , $x_{1}$ such that $α (x_{0}) = B$ and $α (x_{1}) ⊈ B$ . Since A is high, by Jockusch’s Theorem [15], [22, XII Theorem 3.4] the family of all computable sets is A-computable. Hence, there is an A-computable sequence ${g_{n}}_{n \in N}$ of all strictly increasing computable functions. By Martin’s criterion [20], [22, XI Theorem 1.3], there also exists a function $h ⩽_{T} A$ that dominates every computable function (i.e. for every computable function d there is an integer N such that $d (n) ⩽ h (n)$ for each $n ⩾ N$ ).

Let ${α_{s} (x)}_{x, s \in N}$ be a strongly computable double sequence of finite sets such that $α (x) = ⋃_{s} α_{s} (x)$ and $α_{t} (x) \subseteq α_{t + 1} (x)$ for all x, t. Now we define a function f by $\begin{matrix} f (z) = \{\begin{matrix} x_{0}, & if \exists n ⩽ z \exists y [z = g_{n} (y) & α_{h (y)} (g_{n} (y)) ⊈ B], \\ x_{1}, & otherwise . \end{matrix} \end{matrix}$ Since $g_{n}$ is strictly increasing for each n, we have $f ⩽_{T} A$ . It is easy to see that either $α (z) \neq B$ or $α (f (z)) \neq B$ for each z. Now let us prove statement (b). For an infinite computable set C satisfying (1), we fix an integer n such that $C = rng g_{n}$ . Since h dominates the computable function $\begin{matrix} y \mapsto min {s : α_{s} (g_{n} (y)) ⊈ B}, \end{matrix}$ there exists an integer $y_{0}$ such that $f (g_{n} (y)) = x_{0}$ and hence $α (g_{n} (y)) ⊈ B = α (f (g_{n} (y)))$ for each $y ⩾ y_{0}$ . Therefore, the set ${x \in C : α (f (x)) = α (x)}$ is finite. □

The corollary of the following lemma will be useful in the proof of Theorem 3.
Lemma 2.
Let α be a numbering complete with respect to $B \in α (N)$ . Then for any partial computable function ψ there is a strictly increasing computable function r such that $\begin{matrix} (2) & α (r (x)) = \{\begin{matrix} α (ψ (x)), & if ψ (x) ↓, \\ B, & if ψ (x) ↑, \end{matrix} \end{matrix}$ for each x.
Proof.
Let f be a computable function such that $\begin{matrix} α (f (x)) = \{\begin{matrix} α (ψ (x)), & if ψ (x) ↓, \\ B, & if ψ (x) ↑, \end{matrix} \end{matrix}$ for each x. Since α is cylindric, there is a binary computable function g such that $α (g (x, t)) = α (x)$ for all x, t and $g (x, t_{1}) \neq g (x, t_{2})$ for all x and all $t_{1}$ , $t_{2}$ with $t_{1} \neq t_{2}$ . Therefore, there is a computable sequence ${t_{x}}_{x \in N}$ such that $\begin{matrix} g (f (x), t_{x}) < g (f (x + 1), t_{x + 1}) \end{matrix}$ for all x. Hence, we can define $r (x) = g (f (x), t_{x})$ for each x. □
Corollary 1.
Let α be a numbering complete with respect to $B \in α (N)$ . Then there is a computable sequence of strictly increasing computable functions ${r_{e}}_{e \in N}$ such that $\begin{matrix} α (r_{e} (x)) = \{\begin{matrix} α (φ_{e} (x)), & if φ_{e} (x) ↓, \\ B, & if φ_{e} (x) ↑, \end{matrix} \end{matrix}$ for all e, x.
Proof.
Let $ψ ⟨ e, x ⟩ = φ_{e} (x)$ for all e, x. Then we can define $r_{e} (x) = r ⟨ e, x ⟩$ , where r is a strictly increasing computable function, satisfying (2). □

The following theorem provides the highness criterion for the c.e. sets.
Theorem 3.
Let A be a c.e. set. Then the following statements are equivalent:
A is high,

for any computable numbering α of a non-trivial family containing a computable set B there exists a function $f ⩽_{T} A$ satisfying the following conditions:

for each z either $α (z) \neq B$ or $α (f (z)) \neq B$ ,

for every computable set C such that $\begin{matrix} \forall y \in C [α (y) ⊈ B] \end{matrix}$ the set ${x \in C : α (f (x)) = α (x)}$ is finite,

there exist a computable numbering α complete with respect to a computable set $B \in α (N)$ and a function $f ⩽_{T} A$ , satisfying items (a) and (b) of the previous statement.

Proof.
The implication (1) ⇒ (2) follows directly from Lemma 1. The implication (2) ⇒ (3) is clear.

Let us prove the implication (3) ⇒ (1). Let α be a computable numbering complete with respect to a computable set $B \in α (N)$ such that there exists a function $f ⩽_{T} A$ satisfying items (a) and (b) of statement (2). By the Modulus Lemma (see [22, III Lemma 3.2]) there exist a binary computable function $\hat{f}$ and an A-computable function m such that $f (x) = {lim}_{s} \hat{f} (x, s)$ and $\hat{f} (x, t) = f (x)$ for all $x \in N$ and $t ⩾ m (x)$ . Recall that any such function m is called a modulus of convergence for the function $\hat{f}$ . Let ${α_{s} (x)}_{x, s \in N}$ be a strongly computable double sequence of finite sets such that $α (x) = ⋃_{s} α_{s} (x)$ and $α_{t} (x) \subseteq α_{t + 1} (x)$ for all x, t.

Using Corollary 1, we can choose a computable sequence of strictly increasing computable functions ${r_{e}}_{e \in N}$ such that $\begin{matrix} α (r_{e} (x)) = \{\begin{matrix} α (φ_{e} (x)), & if φ_{e} (x) ↓, \\ B, & if φ_{e} (x) ↑, \end{matrix} \end{matrix}$ for all e, x. Now we define a computable function d by $\begin{matrix} φ_{d (n)} ⟨ e, x ⟩ = \{\begin{matrix} undefined, & if, for every s, either φ_{e, s} (x) ↑ or, \\ α_{s} (\hat{f} (r_{n} ⟨ e, x ⟩, s)) \subseteq B, \\ \hat{f} (r_{n} ⟨ e, x ⟩, s), & otherwise, where s is the least integer \\ such that φ_{e, s} (x) ↓ and \\ α_{s} (\hat{f} (r_{n} ⟨ e, x ⟩, s)) ⊈ B . \end{matrix} \end{matrix}$ By the Recursion Theorem we can choose an integer k such that $φ_{d (k)} = φ_{k}$ . Now we show that the A-computable function $\begin{matrix} h (x) = \sum_{e = 0}^{x} m (r_{k} ⟨ e, x ⟩) \end{matrix}$ dominates every computable function. Let $φ_{e}$ be total. Then $φ_{k} ⟨ e, x ⟩ ↓$ for each x, because if $φ_{k} ⟨ e, x ⟩ ↑$ for some x, we would have both $α (f (r_{k} ⟨ e, x ⟩)) = B$ (since $α (f (r_{k} ⟨ e, x ⟩)) \subseteq B$ and B is the least set under inclusion in $α (N)$ ), and $α (r_{k} ⟨ e, x ⟩) = B$ , which contradicts item (a). Therefore, for every x there is an s such that $\begin{matrix} α (r_{k} ⟨ e, x ⟩) = α (φ_{k} ⟨ e, x ⟩) = α (\hat{f} (r_{k} ⟨ e, x ⟩, s)) ⊈ B . \end{matrix}$ Let $C = {r_{k} ⟨ e, x ⟩ : x \in N}$ . Since $r_{k}$ is strictly increasing, C is computable. By item (b) there exists an $x_{0}$ such that $\begin{matrix} α (φ_{k} ⟨ e, x ⟩) = α (r_{k} ⟨ e, x ⟩) \neq α (f (r_{k} ⟨ e, x ⟩)) \end{matrix}$ for each $x ⩾ x_{0}$ . If $φ_{e, m (r_{k} ⟨ e, x ⟩)} (x) ↑$ for some $x ⩾ x_{0}$ , then there is an $s > m (r_{k} ⟨ e, x ⟩)$ such that $\begin{matrix} φ_{k} ⟨ e, x ⟩ = \hat{f} (r_{k} ⟨ e, x ⟩, s) = f (r_{k} ⟨ e, x ⟩) . \end{matrix}$ Therefore, $\begin{matrix} α (r_{k} ⟨ e, x ⟩) = α (φ_{k} ⟨ e, x ⟩) = α (f (r_{k} ⟨ e, x ⟩)) \end{matrix}$ for some $x ⩾ x_{0}$ . This is a contradiction. Hence, $\begin{matrix} φ_{e, m (r_{k} ⟨ e, x ⟩)} (x) ↓ < m (r_{k} ⟨ e, x ⟩) ⩽ h (x) \end{matrix}$ for each $x ⩾ max {x_{0}, e}$ . This completes the proof of the theorem. □

Since the Gödel numbering of all c.e. sets is complete with respect to ∅, the following corollary holds.
Corollary 2.
Let A be a c.e. set. Then A is non-high if and only if for every function $f ⩽_{T} A$ either there is an integer n with $W_{n} = W_{f (n)} = \emptyset$ , or there is a computable set $C \subseteq K_{1}$ such that $W_{f (n)} = W_{n}$ for infinitely many $n \in C$ .

Here, we let $K_{1}$ denote the index set of all nonempty c.e. sets.
4. Turing complete oracles and complete numberings

In this section, we show that, for a c.e. oracle A, its Turing completeness is equivalent to the existence of a precomplete and even a complete relative to any element A-computable numbering of every A-computable family.

Theorem 4.
Let $A <_{T} \emptyset^{'}$ be a Turing incomplete c.e. set and let $R$ be a finite nonempty family of A-c.e. sets without the least element under inclusion. Then $R$ has no precomplete A-computable numberings.
Proof.
Let α be an A-computable numbering of $R$ . Let $B_{0}, \dots, B_{n}$ be all elements of $R$ that are minimal under inclusion ( $n > 0$ ). In the same way as in the proof of Proposition 4 [9, I §2] we can choose finite sets $F_{0}, \dots, F_{n}$ such that $\begin{matrix} F_{i} \subseteq B_{j} \Leftrightarrow i = j \end{matrix}$ for all $i, j ⩽ n$ . Fix integers $x_{0}$ , $x_{1}$ such that $α (x_{0}) = B_{0}$ and $α (x_{1}) = B_{1}$ .

For contradiction, suppose there exists a binary computable function f such that $α (f (e, x)) = α (φ_{e} (x))$ whenever $φ_{e} (x) ↓$ . Let ${α_{s} (x)}_{s, x \in N}$ be a strongly A-computable double sequence of finite sets such that $α (x) = ⋃_{s} α_{s} (x)$ and $α_{t} (x) \subseteq α_{t + 1} (x)$ for all x, t. Now we define A-computable functions r and h by $\begin{array}{l} r (y) = min {s : \exists i ⩽ n [F_{i} \subseteq α_{s} (y)]}, \\ h (y) = min {i ⩽ n : F_{i} \subseteq α_{r (y)} (y)} \end{array}$ for each y. By the Modulus Lemma there exist a binary computable function $\hat{h}$ and an A-computable function m such that $h (x) = {lim}_{s} \hat{h} (x, s)$ and $\hat{h} (x, t) = h (x)$ for all $x \in N$ and $t > m (x)$ .

By the s-m-n Theorem there is a computable function d such that $\begin{matrix} φ_{d (e)} (x) = \{\begin{matrix} x_{0}, & if x \in \emptyset^{'} & \hat{h} (f (e, x), s) > 0, \\ where s = min {t : x \in \emptyset_{t}^{'}}, \\ x_{1}, & if x \in \emptyset^{'} & \hat{h} (f (e, x), s) = 0, \\ where s = min {t : x \in \emptyset_{t}^{'}}, \\ undefined, & otherwise . \end{matrix} \end{matrix}$ Using the Recursion Theorem we can fix an integer n such that $φ_{d (n)} = φ_{n}$ . Now we have $\begin{matrix} x \in \emptyset^{'} \Leftrightarrow x \in \emptyset_{m (f (n, x))}^{'} \end{matrix}$ for each x. Indeed, if $x \notin \emptyset^{'}$ , then $x \notin \emptyset_{m (f (n, x))}^{'}$ . Let $x \in \emptyset^{'}$ . Assume that $x \notin \emptyset_{m (f (n, x))}^{'}$ . Fix the least s such that $x \in \emptyset_{s}^{'}$ . Since $s > m (f (n, x))$ , either $F_{0} \subseteq α (f (n, x))$ and $φ_{n} (x) = x_{1}$ , or $\begin{matrix} \exists i ⩽ n [0 < i & F_{i} \subseteq α (f (n, x))] \end{matrix}$ and $φ_{n} (x) = x_{0}$ . Therefore, $\begin{matrix} α (f (n, x)) \neq α (φ_{n} (x)) = α (f (n, x)) . \end{matrix}$ Hence, $x \in \emptyset_{m (f (n, x))}^{'}$ . Thus we obtain that $\emptyset^{'} ⩽_{T} A$ . This is a contradiction with the incompleteness of A. □
Corollary 3.
For a c.e. set A the following statements are equivalent:
$\emptyset^{'} ⩽_{T} A$ ,

for every A-computable family $F$ and for every set $B \in F$ there exists an A-computable numbering of $F$ complete with respect to B,

every A-computable family has a precomplete A-computable numbering.

Proof.
If $\emptyset^{'} ⩽_{T} A$ , then for every A-computable numbering $α : N \to F$ and for every $B \in F$ the completion [6,8] $\begin{matrix} α_{B} ⟨ e, x ⟩ = \{\begin{matrix} α (φ_{e} (x)), & if φ_{e} (x) ↓, \\ B, & if φ_{e} (x) ↑ \end{matrix} \end{matrix}$ of α is A-computable as well and complete with respect to B. Hence we proved the implication (1) ⇒ (2).

The implication (2) ⇒ (3) is clear. The implication (3) ⇒ (1) follows immediately from Theorem 4. □

Note that for any numbering α of a set S and any element $b \in S$ the completion $α_{b}$ of α is reducible to α via some $\emptyset^{'}$ -computable function. Now we will show how to construct a complete minimal numbering μ, which reduces to a given numbering α of an infinite set via some $\emptyset^{″}$ -computable function. This will answer one of the questions in [6]. Theorem 5.
For every numbering α of an infinite set S and for every element $b \in S$ there exists a minimal numbering μ of S complete with respect to b such that $μ = α \circ f$ for some function $f ⩽_{T} \emptyset^{″}$ .
Proof.
We define the minimal numbering μ by induction. To make μ complete we will provide that $\begin{matrix} (3) & μ ⟨ e, x ⟩ = \{\begin{matrix} μ (φ_{e} (x)), & if φ_{e} (x) ↓, \\ b, & if φ_{e} (x) ↑, \end{matrix} \end{matrix}$ for all integers e, x. Let $E_{0}$ be the equivalence relation generated by the binary relation $\begin{matrix} {(⟨ e, x ⟩, φ_{e} (x)) : x, e \in N, φ_{e} (x) ↓} . \end{matrix}$ By the Recursion Theorem, we can choose an infinite computable set $\begin{matrix} {n_{0} < n_{1} < n_{2} < \dots} \end{matrix}$ such that $φ_{n_{i}} (0) = ⟨ n_{i}, 0 ⟩$ for each i. Let $z_{i}^{0} = ⟨ n_{i}, 0 ⟩$ , $i \in N$ . Now we define $\begin{matrix} μ_{0} (x) = b for each x \in N ∖ (⋃_{i} {[z_{i}^{0}]}_{E_{0}}), \end{matrix}$ where ${[z]}_{E_{0}}$ means the $E_{0}$ -equivalence class of z. Assume by induction that we have defined a partial mapping $μ_{s} : N \to S$ , a c.e. equivalence relation $E_{s}$ and a computable sequence $\begin{matrix} {z_{0}^{s} < z_{1}^{s} < z_{2}^{s} < \dots} \end{matrix}$ which satisfy the following conditions:
$μ_{t} \subseteq μ_{s}$ and $E_{t} \subseteq E_{s}$ for each $t < s$ ,

$μ_{s} (x) = μ_{s} (y)$ for all $y \in dom μ_{s}$ and $x \in {[y]}_{E_{s}}$ ,

$\neg (z_{i}^{s} E_{s} z_{j}^{s})$ for all different i and j,

$dom μ_{s} = N ∖ (⋃_{i} {[z_{i}^{s}]}_{E_{s}})$ ,

$rng μ_{s}$ is finite.
Let y be the least element of $⋃_{i} {[z_{i}^{s}]}_{E_{s}}$ . Fix an integer k such that $(z_{k}^{s} E_{s} y)$ . Using the oracle $\emptyset^{″}$ , we can check the following condition $\begin{matrix} (4) & \exists^{\infty} j \exists y [φ_{s} (y) ↓ & (φ_{s} (y) E_{s} z_{j}^{s})] . \end{matrix}$ If (4) is false we, for every x, define $\begin{matrix} μ_{s + 1} (x) = \{\begin{matrix} μ_{s} (x), & if x \in dom μ_{s}, \\ α (s), & if \exists i ⩽ k (x E_{s} z_{i}^{s}), \\ undefined, & otherwise, \end{matrix} \end{matrix}$ and $z_{i}^{s + 1} = z_{k + i + 1}^{s}$ , $E_{s + 1} = E_{s}$ . Otherwise, we can choose a strictly increasing computable function h such that, for every j, $\begin{matrix} h (j) > k & \exists y (φ_{s} (y) E_{s} z_{h (j)}^{s}) . \end{matrix}$ By the Recursion Theorem, there exists an infinite computable set $\begin{matrix} {m_{0} < m_{1} < m_{2} < \dots} \end{matrix}$ such that $φ_{m_{i}} (0) = z_{h ⟨ m_{i}, 0 ⟩}^{s}$ for each i. Note that, for every i, $\begin{matrix} ⟨ m_{i}, 0 ⟩ E_{0} φ_{m_{i}} (0) = z_{h ⟨ m_{i}, 0 ⟩}^{s} . \end{matrix}$ Now we define $z_{i}^{s + 1} = z_{h ⟨ m_{i}, 0 ⟩}^{s}$ for each i, $E_{s + 1}$ to be the equivalence relation generated by the binary relation $E_{s} \cup {(i, z_{h (i)}^{s}) : i \in N}$ , and $\begin{matrix} μ_{s + 1} (x) = \{\begin{matrix} μ_{s} (y), & if y \in dom μ_{s} & (y E_{s + 1} x), \\ α (s), & if \exists i ⩽ k (x E_{s + 1} z_{i}^{s}), \\ undefined, & if \exists i [(x E_{s + 1} z_{i}^{s + 1})], \\ b, & otherwise \end{matrix} \end{matrix}$ for each x. Note that, by the definition of the equivalence $E_{s + 1}$ , if $y, z \in dom μ_{s}$ and $(x E_{s + 1} y E_{s + 1} z)$ , then $(y E_{s + 1} z)$ . Therefore, the definition of $μ_{s + 1}$ is correct. It is not hard to see that conditions (a)–(e) are satisfied at stage $s + 1$ too. This completes the definition of $μ = ⋃_{s} μ_{s}$ .

Since $μ_{s + 1} (y) = α (s)$ for each s, where y is the least element of $N ∖ dom μ_{s}$ , we have $dom μ = N$ and $rng μ = S$ . By the definition, μ satisfies (3) and μ is reducible to α via some $\emptyset^{″}$ -computable function. It remains to show that μ is minimal. Let $φ_{s}$ be total. If the set $\begin{matrix} {i : \exists y (z_{i}^{s} E_{s} φ_{s} (y))} \end{matrix}$ is finite, then, since $rng μ_{s}$ is finite, the numbering $μ \circ φ_{s}$ enumerates a finite set. Suppose that it is infinite. Then by the definition of μ we have $(i E_{s + 1} z_{h (i)}^{s})$ for each i. Therefore, for every i we can find a y such that $(φ_{s} (y) E_{s + 1} z_{h (i)}^{s} E_{s + 1} i)$ and, hence, $\begin{matrix} μ (i) = μ (φ_{s} (y)) . \end{matrix}$ This completes the proof. □
Corollary 4.
Let $\emptyset^{″} ⩽_{T} A$ and $F$ be an infinite A-computable family. Then for every set $B \in F$ there exists a minimal A-computable numbering of $F$ complete with respect to B.

5. Noncomputable c.e. oracles and weak precompleteness

Recall [5] that an equivalence relation η on $N$ is weakly precomplete if there exists a partial computable function ψ such that for every e $\begin{matrix} ψ (e) ↓ & (ψ (e) η φ_{e} (ψ (e))) \end{matrix}$ whenever $φ_{e}$ is total. A numbering α is called weakly precomplete if its numeration equivalence $\begin{matrix} η_{α} = {(x, y) : α (x) = α (y)} \end{matrix}$ is weakly precomplete. It is not hard to see that every weakly precomplete numbering α satisfies the Recursion Theorem with Parameters, i.e. for every binary computable function f there exists a computable function h such that $\begin{matrix} α (f (x, h (x)) = α (h (x)) \end{matrix}$ for each x.

Theorem 6.

Let A be a noncomputable c.e. set. Then for any numbering α of a set S there exists a weakly precomplete numbering ν of S reducible to α via some A-computable function.

Proof.

To define a weakly precomplete numbering ν reducible to α via some A-computable function, we will construct a Turing functional Γ such that $dom Γ^{A} = N$ and $ν = α \circ Γ^{A}$ , and a partial computable function ψ such that $ψ (e) ↓$ and $\begin{matrix} Γ^{A} (φ_{e} (ψ (e))) = Γ^{A} (ψ (e)) \end{matrix}$ whenever $φ_{e}$ is total. Let γ be the use-function of Γ.

We define $Γ^{A_{s}} (2 x + 1) = x$ and $γ^{A_{s}} (2 x + 1) = 0$ for all s, x. At stage 0 we let $ψ_{0} = \emptyset$ and $Γ^{A_{0}} (2 x) = 0$ , $γ^{A_{0}} (2 x) = x$ for each x. At stage $s + 1$ we choose the least $e ⩽ s$ such that $ψ_{s} (e) ↑$ , $\begin{array}{rcl} (5) & \begin{matrix} \exists y ⩽ s [φ_{e, s} (2 ⟨ e, y ⟩) ↓], \\ A_{s + 1} ↾ M \neq A_{s} ↾ M, \end{matrix} \end{array}$ where $\begin{matrix} M = max {γ^{A_{s}} (φ_{e} (2 ⟨ e, y ⟩), γ^{A_{s}} (2 ⟨ e, y) ⟩}, \end{matrix}$ and, for every z, define $\begin{array}{l} Γ^{A_{s + 1}} (z) = \{\begin{matrix} (φ_{e} (2 ⟨ e, y ⟩) - 1) / 2, & if γ^{A_{s}} (z) = M and φ_{e} (2 ⟨ e, y ⟩) is odd, \\ Γ^{A_{s}} (z), & otherwise, \end{matrix} \\ γ^{A_{s + 1}} (z) = \{\begin{matrix} m, & if γ^{A_{s}} (z) = M, \\ γ^{A_{s}} (z), & otherwise, \end{matrix} \end{array}$ where $\begin{matrix} m = min {γ^{A_{s}} (φ_{e} (2 ⟨ e, y ⟩), γ^{A_{s}} (2 ⟨ e, y ⟩)} . \end{matrix}$ Note that $m = 0$ if $φ_{e} (2 ⟨ e, y ⟩)$ is odd. Let $ψ_{s + 1} (e) = 2 ⟨ e, y ⟩$ . If there is no e satisfying (5), we go the next stage.

It is not hard to show that ν is weakly precomplete. Indeed let $φ_{e}$ be total. The standard permitting argument shows that there are s and y satisfying (5) such that $ψ_{s} (e) ↑$ and $ψ_{s + 1} (e) = 2 ⟨ e, y ⟩$ . It follows directly from the construction that $\begin{array}{l} Γ^{A_{s + 1}} (ψ (e)) = Γ^{A_{s + 1}} (φ_{e} (ψ (e))), \\ γ^{A_{s + 1}} (ψ (e)) = γ^{A_{s + 1}} (φ_{e} (ψ (e))), \end{array}$ and $Γ^{A} (z) = Γ^{A} (ψ (e))$ for every z with $γ^{A_{s + 1}} (z) = m$ . This completes the proof of the theorem. □

Corollary 5.

Let A be a c.e. set. Then the following statements are equivalent:

A is noncomputable,

every A-computable family has a weakly precomplete A-computable numbering,

every A-computable family has an A-computable numbering α such that for any binary computable function f there exists a computable function h with $α (f (x, h (x))) = α (h (x))$ for each x,

every A-computable family has an A-computable numbering α such that for any binary function f there exists an integer n with $α (f (n)) = α (n)$ .

Proof.

The implications (1) ⇒ (2) ⇒ (3) ⇒ (4) are clear. To prove the implication (4) ⇒ (1) we show that for any computable numbering α of every non-trivial finite family $R$ of c.e. sets without the least element under inclusion there exists a computable function f such that $α (f (x)) \neq α (x)$ for each integer x. Let $B_{0}, \dots, B_{n}$ be all elements of $R$ that are minimal under inclusion. We fix finite sets $F_{0}, \dots, F_{n}$ such that $\begin{matrix} F_{i} \subseteq B_{j} \Leftrightarrow i = j \end{matrix}$ for all $i, j ⩽ n$ . Fix integers $x_{0}$ , $x_{1}$ such that $α (x_{0}) = B_{0}$ and $α (x_{1}) = B_{1}$ . Now we define a computable function g as follows. For every x we choose the least t such that $\begin{matrix} \exists i ⩽ n [F_{i} \subseteq α_{t} (x)] . \end{matrix}$ Let $g (x) = min {i ⩽ n : F_{i} \subseteq α_{t} (x)}$ and $\begin{matrix} f (x) = \{\begin{matrix} x_{0}, & if g (x) > 0, \\ x_{1}, & if g (x) = 0 . \end{matrix} \end{matrix}$ It is easy to see that $α (f (x)) \neq α (x)$ for any x. □

Corollaries 3 and 5 allows to answer the question posed by Barendregt and Terwijn [7] about the existence of a numbering which, although not precomplete, satisfies the Recursion Theorem with Parameters. Indeed, fix an arbitrary c.e. noncomputable set $A <_{T} \emptyset^{'}$ . By Corollary 3 there exists an A-computable family $F$ without precomplete A-computable numberings. Using Corollary 5, $F$ has a weakly precomplete A-computable numbering which, in particular, satisfies the Recursion Theorem with Parameters.

Footnotes

Acknowledgements

The author is extremely grateful to the referees for their careful reading of the manuscript, and for the comments, remarks and detailed suggestions for improving the paper.

The work is performed under the development program of Volga Region Mathematical Center (agreement No. 075-02-2023-944).

References

Ambos-Spies,

Badaev and

Goncharov, Inductive inference and computable numberings, Theoretical Comp. Sci. 412 (2011), 1652–1668. doi:10.1016/j.tcs.2010.12.041.

Andrews,

Badaev and

Sorbi, A survey on universal computably enumerable equivalence relations, in: Computability and Complexity. Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Springer, 2017, pp. 418–451. doi:10.1007/978-3-319-50062-1_25.

M.M.

Arslanov, On some generalizations of the fixed point theorem, Sov. Math. (Iz. VUZ) 25 (1981), 1–10.

M.M.

Arslanov,

R.F.

Nadirov and

V.D.

Solov’ev, Completeness criteria for recursively enumerable sets and some general theorems on fixed points, Sov. Math. (Iz. VUZ) 21 (1977), 1–4.

S.A.

Badaev, On weakly pre-complete positive equivalences, Sib. Math. J. 32 (1991), 321–323. doi:10.1007/BF00972779.

S.A.

Badaev,

S.S.

Goncharov and

Sorbi, Completeness and universality of arithmetical numberings, in: Computability and Models, The University Series in Mathematics, Springer, Boston, MA, 2003. doi:10.1007/978-1-4615-0755-0_2.

Barendregt and

S.A.

Terwijn, Fixed point theorems for precomplete numberings, Ann. Pure App. Log. 170 (2019), 1151–1161. doi:10.1016/j.apal.2019.04.013.

Y.L.

Ershov, On inseparable pairs, Algebra Log. 9 (1970), 396–399. doi:10.1007/BF02219043.

Y.L.

Ershov, Theory of Numberings, Nauka, Moscow, 1977, Russian.

10.

Y.L.

Ershov, Theory of numberings, in: Handbook of Computability Theory,

E.R.

Griffor, ed., Studies in Logic and the Foundations of Mathematics, Vol. 140, Elsevier Science, Amsterdam, 1999, pp. 473–506. doi:10.1016/S0049-237X(99)80030-5.

11.

S.S.

Goncharov, Computable single-valued numerations, Algebra Log. 19 (1980), 325–356. doi:10.1007/BF01669607.

12.

S.S.

Goncharov and

Sorbi, Generalized computable numerations and non-trivial Rogers semilattices, Algebra Log. 36 (1997), 359–369. doi:10.1007/BF02671553.

13.

Grabmayr, On the invariance of Gödel’s second theorem with regard to numberings, Review Symb. Log. 14 (2021), 51–84. doi:10.1017/S1755020320000192.

14.

C.G.

JockuschJr., The degrees of bi-immune sets, Z. Math. Logik Grundlagen Math. 15 (1969), 135–140. doi:10.1002/malq.19690150707.

15.

C.G.

JockuschJr., Degrees in which the recursive sets are uniformly recursive, Canad. J. Math. 24 (1972), 1092–1099. doi:10.4153/CJM-1972-113-9.

16.

A.N.

Kolmogorov and

V.A.

Uspensky, On the definition of an algorithm, Usp. Mat. Nauk. 13 (1958), 3–28.

17.

Kummer, Some applications of computable one–one numberings, Arch. Math. Logic. 30 (1990), 219–230. doi:10.1007/BF01792984.

18.

A.I.

Mal’tsev, Constructive algebras I, Russ. Math. Surv. 16 (1961), 77–129. doi:10.1070/RM1961v016n03ABEH001120.

19.

A.I.

Mal’tsev, The Metamathematics of Algebraic Systems, North-Holland, Amsterdam, 1971.

20.

D.A.

Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math. 12 (1966), 295–310. doi:10.1002/malq.19660120125.

21.

Rogers, Gödel numberings of partial computable functions, J. Symb. Logic. 23 (1958), 49–57. doi:10.2307/2964292.

22.

R.I.

Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, Heidelberg, New York, 1987.

23.

R.I.

Soare, Turing Computability, Theory and Applications of Computability, Springer-Verlag, Berlin, Heidelberg, 2016.

24.

V.A.

Uspensky, Some remarks on enumerable sets, Z. Math. Logik Grundlagen Math. 3 (1957), 157–170. doi:10.1002/malq.19570031202.

25.

V.A.

Uspensky and

A.L.

Semenov, Algorithms: Main Ideas and Applications, Kluwer Academic Publishers, Dordrecht, 1993.

26.

Weihrauch, Computability, Springer, Berlin, 1987.

27.

Weihrauch, Computable Analysis, Springer, Berlin, 2000.