Effectively infinite classes of numberings and computable families of reals

Abstract

We prove various sufficient conditions for the effective infinity of classes of computable numberings. Then we apply them to show that for every computable family of left-c.e. reals without the greatest element the class of its Friedberg computable numberings is effectively infinite. In particular, this result covers the families of all left-c.e. and all Martin-Löf random left-c.e. reals whose Friedberg computable numberings have been constructed by Broadhead and Kjos-Hanssen in their paper (In Mathematical Theory and Computational Practice, CiE 2009 (2009) 49–58 Springer). In addition, for every infinite computable family of left-c.e. reals we prove that the classes of all its computable, positive and minimal numberings are effectively infinite.

Keywords

Computable numbering Friedberg numbering positive numbering effective infinity left-c.e. real

1. Introduction

One of the most intensively studied questions in the theory of numberings has been formulated by Yu.L. Ershov in the mid-1960s: how many minimal and, in particular, Friedberg and positive computable numberings families of c.e. sets can have (see [2,3]). If two classes of numberings are infinite, then the theory of numberings also considers the question of which of them is «greater» (see [4,16]). In the paper [16] by S.S. Goncharov, A. Yakhnis and V. Yakhnis, it was noted that classes of computable numberings of a family may have different degrees of infinity. We may first show that a class is not finite. This is the classical version of infinity. Another possibility is to construct an infinite computable sequence without repetitions consisting of all (up to equivalence) numberings from the class. This yields more information than the classical version and it is more constructive. A still stronger way to prove infinity is to show that a class is effectively infinite. This concept was introduced and first studied also in [16]. The authors called a class of computable numberings of some family $S$ is effectively infinite if, given any of its computable subclasses, we can effectively construct a computable numbering belonging to that class that is not equivalent to any numbering from this computable subclass. Thus, the notion of effective infinity extends the notion of productiveness for subsets of $N$ to classes of numberings. In the same paper [16], sufficient conditions were obtained for the effective infinity of various classes of numberings, which were then applied to the classes of Friedberg, positive, negative, and minimal numberings of the family $E$ of all c.e. subsets of $N$ . In this paper, we obtain other sufficient conditions for the effective infinity of classes of numberings. We apply these conditions to show that for every computable family of left-c.e. reals without greatest element the class of its Friedberg computable numberings is effectively infinite. In addition, for every infinite computable family of left-c.e. reals we prove that the classes of all its computable, positive and minimal numberings are effectively infinite. Some of these results were announced in [12].

The general theory of numberings was initiated in the mid-1950s by A.N. Kolmogorov, and continued by V.A. Uspenskii, A.I. Mal’tsev, Yu.L. Ershov [7,19,24]. The reader can find the necessary information on the theory of numberings in Ershov’s monograph [8] and in his paper [9]. The necessary information on computability theory can be found in Soare’s monographs [22,23]. We present the most important of them below. A numbering of an at most countable set S is a surjective map $α : N \to S$ . The set of all numberings of S will be denoted as usual by $H (S)$ . A numbering $α \in H (S)$ is said to be reducible to a numbering $β \in H (S)$ ( $α ⩽ β$ ) if there exists a computable function f such that $α (x) = β (f (x))$ for each x. Two numberings α and β are called equivalent ( $α \equiv β$ ) if $α ⩽ β$ and $β ⩽ α$ .

In one of the earliest results, R. Friedberg [14] constructed an injective numbering α of the family of all c.e. sets such that the relation « $y \in α (x)$ » is itself c.e. In view of this, if numbering is injective, then it is called Friedberg numbering. We say that a numbering α is decidable (positive, negative) if its numbering equivalence $\begin{matrix} η_{α} = {⟨ x, y ⟩ \in N \times N : α (x) = α (y)} \end{matrix}$ is computable (c.e., co-c.e.). A numbering $α \in H (S)$ is said to be minimal if $α ⩽ β$ for every numbering $β \in H (S)$ with $β ⩽ α$ .

Let us now give some information about the computability of numberings. A numbering α of a family $S$ of c.e. sets is said to be computable if the set $\begin{matrix} G_{α} = {⟨ x, y ⟩ \in N \times N : y \in α (x)} \end{matrix}$ is c.e. If $G_{α} = W_{e}$ , then the numbering α will be denoted by $α_{e}$ . If a family has a computable numbering, then it is also called computable. With each computable numbering β we will associate a double strongly computable sequence of finite sets ${β_{s} (x)}_{s, x \in N}$ such that $\begin{array}{c} β_{s} (x) \subseteq β_{s + 1} (x), β (x) = ⋃_{t} β_{t} (x), \\ s ⩽ x \Rightarrow β_{s} (x) = \emptyset \end{array}$ for all s and x.

For a partial function ψ, we write $ψ (x) ↓$ if its value is defined on the argument x, and $ψ (x) ↑$ otherwise. We let $c (x, y)$ denote a computable pairing function. The symbol «⇋» will replace the phrase «which is equal to».

2. The effective infinity of classes of numberings and numberings of families of reals

A class K of computable numberings of a family $S$ is said to be computable [16] if there exists a c.e. set H such that $\begin{matrix} K = {α_{e} : e \in H} . \end{matrix}$ If $H = W_{x}$ , then the class K will be denoted by $C_{x}$ . It is not hard to see that a nonempty class $K \subseteq H (S)$ is computable if and only if there exists a computable function d such that $\begin{matrix} K = {α_{d (x)} : x \in N} . \end{matrix}$

Definition 1 (S.S. Goncharov, A. Yakhnis and V. Yakhnis [16]).

A class K of numberings of a family $S$ is said to be effectively infinite is there exists a partial computable function ψ such that for every x, if $C_{x} \subseteq K$ , then $ψ (x) ↓$ , $α_{ψ (x)} \in K$ , and $α_{ψ (x)} ≢ ξ$ for each $ξ \in C_{x}$ .

We now give information about the enumerability of reals. We say that a real ζ is left-c.e. is the set $\begin{matrix} L (ζ) = {q \in Q : q < ζ} \end{matrix}$ is c.e. Let $L$ be the family of all letft-c.e. reals. A numbering α of a family $A \subseteq L$ is said to be computable [5] if the numbering $β : x \mapsto L (α (x))$ of the family $\begin{matrix} D (A) = {L (ζ) : ζ \in A} \end{matrix}$ (identified with a family of subsets of $N$ ) is computable (see [10,11,13] for another approach to the notion of computability of such numberings in terms of limitwise monotonicity). This definition corresponds to the general approach to the concept of computable numbering of a family of sets of constructive objects proposed in the paper by S.S. Goncharov and A. Sorbi [15].

For a family $S \subseteq E$ ( $S \subseteq L$ ) let $K_{all} (S)$ be the class of all its computable numberings. The classes of all its Friedberg, decidable, positive, minimal and negative computable numberings will be denoted by $K_{dec} (S)$ , $K_{pos} (S)$ , $K_{min} (S)$ , $K_{neg} (S)$ respectively. It is known from [8] that $K_{Fr} (S) \subseteq K_{dec} (S) \subseteq K_{pos} (S) \subseteq K_{min} (S)$ and for every negative numbering of a set S there exists a Friedberg numbering of S that is reducible to it.

3. Sufficient conditions for the effective infinity

To prove that a subset of $N$ is productive, it suffices to show that $\overline{\emptyset^{'}}$ is m-reducible to it [20,22]. In the following theorem we prove a similar result for the effective infinity of classes of numberings.

Theorem 1.
Let K be a class of numberings of a family $S \subseteq E$ . If there exists a computable function f such that $α_{f (e)} \in K$ for each $e \notin \emptyset^{(3)}$ and $\forall β \in K [β ≢ α_{f (e)}]$ for each $e \in \emptyset^{(3)}$ , then K is effectively infinite.
Proof.
It is not hard to see that $\begin{matrix} {⟨ i, k ⟩ : α_{i} \equiv α_{k}} \in Σ_{3}^{0} . \end{matrix}$ Therefore, there exists a computable function h satisfying $\begin{matrix} W_{h (x)}^{\emptyset^{″}} = {i : \exists k \in W_{x} [α_{i} \equiv α_{k}]} \end{matrix}$ for each x. Since $\begin{matrix} \overline{\emptyset^{(3)}} \equiv_{m} {x : W_{x}^{\emptyset^{″}} = \emptyset}, \end{matrix}$ there exists a computable function f such that $\begin{array}{c} W_{e}^{\emptyset^{″}} = \emptyset \Rightarrow α_{f (e)} \in K, \\ W_{e}^{\emptyset^{″}} \neq \emptyset \Rightarrow \forall β \in K [α_{f (e)} ≢ β] \end{array}$ for each e. Let us define a binary computable function g by letting $\begin{matrix} W_{g (x, y)}^{\emptyset^{″}} = \{\begin{array}{ll} {0}, & if f (y) \in W_{h (x)}^{\emptyset^{″}}, \\ \emptyset, & otherwise \end{array} \end{matrix}$ for all x, y. By the recursion theorem with parameters, one can define a computable function n such that $\begin{matrix} W_{g (x, n (x))}^{\emptyset^{″}} = W_{n (x)}^{\emptyset^{″}} \end{matrix}$ for each x. Now we show that K is effectively infinite via the function $p = f \circ n$ . For every x, if $\begin{matrix} \emptyset \neq W_{n (x)}^{\emptyset^{″}} = {0}, \end{matrix}$ then $p (x) \in W_{h (x)}^{\emptyset^{″}}$ . Hence, $α_{p (x)} \equiv ξ$ for some numbering $ξ \in C_{x}$ . On the other hand, $α_{p (x)} ≢ β$ for each $β \in K$ . Thus we have that $ξ \in C_{x} ∖ K$ . If $\begin{matrix} W_{n (x)}^{\emptyset^{″}} = \emptyset, \end{matrix}$ then $α_{p (x)} \in K$ and $p (x) \notin W_{h (x)}^{\emptyset^{″}}$ . To complete the proof it remains to note that since $p (x) \notin W_{h (x)}^{\emptyset^{″}}$ , then $α_{p (x)} ≢ β$ for each $β \in C_{x}$ . □

Using Theorem 1, we are going to prove sufficient conditions for the effective infinity of classes of the form $K_{Fr} (S)$ and $K_{pos} (S)$ .
Theorem 2.
Let μ be a Friedberg computable numbering of a family $S \subseteq E$ and $h ⩽_{T} \emptyset^{'}$ be a function unbounded from above such that for every x the family of all supersets of the set $μ (h (x))$ belonging to $S$ is infinite. Then every class $K \subseteq H (S)$ for which $K_{Fr} (S) \subseteq K$ is effectively infinite.
Proof.
To prove the effective infinity of the class K, we will define uniformly in each e a computable numbering $β_{e}$ which satisfies the following conditions: $\begin{array}{c} e \notin Cof ⇋ {x : {\overline{W}}_{x} is finite} \Rightarrow β_{e} \in K_{Fr} (S) \subseteq K, \\ e \in Cof \Rightarrow β_{e} \notin H (S) . \end{array}$ Since $Cof \equiv_{m} \emptyset^{(3)}$ and $β_{e} = α_{f (e)}$ , $e \in N$ , for some computable function f, Theorem 1 will imply the effective infinity of the class K.

Fix an arbitrary e. To define the numbering $β_{e}$ , we will construct some binary partially computable function ψ such that for each x the set $\begin{matrix} P_{x} = {v > 0 : ψ (x, v) ↓} \end{matrix}$ will be non-empty and finite, and the mapping $\begin{matrix} (1) & x \mapsto (⋃ {μ_{s} (ψ (x, v_{n}^{x})) : s ⩾ v_{n}^{x}}) \cup μ_{v_{0}^{x}} (ψ (x, v_{0}^{x})) \cup μ_{v_{1}^{x}} ψ (x, v_{1}^{x})) \cup \dots \cup μ_{v_{n}^{x}} (ψ (x, v_{n}^{x})), \end{matrix}$ where $P_{x} = {v_{0}^{x} < v_{1}^{x} < v_{2}^{x} < \dots < v_{n}^{x}}$ , will be a computable numbering of some subfamily of $S$ . At the end of the construction, we will define $β_{e}$ to be equal to this numbering.

Without loss of generality, we assume that the function $h ⩽_{T} \emptyset^{'}$ is strictly increasing. Fix a computable sequence of functions ${h_{s}}_{s \in N}$ such that $\begin{matrix} h (x) = lim_{s} h_{s} (x) & h_{t} (x) < h_{t} (x + 1) \end{matrix}$ for all x and t.

Construction of ψ. Stage 0. Define $ψ_{0} = \emptyset$ . For all x and s, we denote by $t_{x, s}$ the following value: $\begin{matrix} t_{x, s} = \{\begin{array}{ll} 0, & if there is no t such that 0 < t ⩽ s and ψ_{s} (x, t) ↓, \\ max {t : 0 < t ⩽ s & ψ_{s} (x, t) ↓} & otherwise . \end{array} \end{matrix}$ In addition to ψ, we will construct a binary computable function r, which we will then use to prove the following equivalence: $\begin{matrix} e \notin Cof \Leftrightarrow β_{e} (N) = S . \end{matrix}$ For all y we define $r (y, 0) = 0$ . At each subsequent stage $(s + 1)$ , we will assume that $ψ_{s + 1} = ψ_{s}$ and $r (y, s + 1) = r (y, s)$ , unless explicitly stated otherwise.

Stage $s + 1 = 2 c (y, u) + 1$ . At these stages, we ensure $\begin{matrix} e \notin Cof \Rightarrow μ (y) \in β_{e} (N) . \end{matrix}$ If there exists an $x ⩽ r (y, s)$ such that $ψ_{s} (x, t_{x, s}) = y$ , then we go to the next stage. If there exists an $\begin{matrix} (2) & x > r (y, s) \end{matrix}$ such that $\begin{matrix} (3) & ψ_{s} (x, t_{x, s}) = y, \end{matrix}$ then we define $\begin{matrix} (4) & r (b, s + 1) = max {x, r (b, s)} \end{matrix}$ for each $b ⩾ y$ . Otherwise, we choose the least x with $t_{x, s} = 0$ and define $\begin{matrix} (5) & ψ_{s + 1} (x, s + 1) = y, r (b, s + 1) = max {x, r (b, s)} \end{matrix}$ for each $b ⩾ y$ .

Stage $s + 1 = 2 c (y, u) + 2$ . At these stages, we ensure $\begin{matrix} N \cap [y, \infty) \subseteq W_{e} \Rightarrow \exists z [μ (h (z)) \notin β_{e} (N)] . \end{matrix}$ If there is no $a \in N$ such that $\begin{matrix} (6) & N \cap [y, a] ⊈ W_{e, u} & N \cap [y, a] \subseteq W_{e, u + 1} \end{matrix}$ or there is no z with $\begin{matrix} (7) & h_{s} (z) > max {ψ_{s} (n, t_{n, s}) : n ⩽ r (y, s) & ψ_{s} (n, t_{n, s}) ↓}, \end{matrix}$ then we go to the next stage. Otherwise, we choose the least z satisfying (7). If for some x (the construction will guarantee that this x is the unique) we have $\begin{matrix} (8) & ψ_{s} (x, t_{x, s}) = h_{s} (z), \end{matrix}$ then choose the least $v > t_{x, s}$ such that either there exists a $w ⩽ v$ satisfying $\begin{array}{c} (9) & w \notin {ψ_{s} (n, t_{n, s}) : n \in N & ψ_{s} (n, t_{n, s}) ↓}, \\ (10) & μ_{s + t_{x, s}} (h_{s} (z)) \subseteq μ_{v} (w), \end{array}$ or for each $w ⩽ v$ one of the conditions (9) and (10) is not satisfied, but $\begin{matrix} h_{s} (z) \neq h_{v} (z) . \end{matrix}$ The required v exists because for each d the family of all supersets of the set $μ (h (d))$ belonging to $S$ is infinite. If there exists a $w ⩽ v$ satisfying (9) and (10), then we define $\begin{array}{c} (11) & ψ_{s + 1} (x, v) = w, \\ (12) & r (b, s + 1) = max {x, r (b, s)} \end{array}$ for the least w satisfying (9) and (10) and for each $b > y$ . Otherwise, we go to the next stage.

At the end of the construction, we define $ψ = ⋃_{s} ψ_{s}$ . It is not hard to see that the construction at its odd stages ensures that for each x there exists a $t > 0$ such that $ψ (x, t) ↓$ .

Since in the construction we check condition (7) and for all x and s after the assignment (11) we perform the assignment (12), we obtain that $P_{x}$ is finite for each x. And since for each assignment (11) we choose u and v satisfying (10), the numbering (1) is computable and its range is contained in $S$ . In addition, it follows directly from the construction that for each s and for any distinct $x_{0}$ and $x_{1}$ we have $\begin{matrix} t_{x_{0}, s} > 0 & t_{x_{1}, s} > 0 \Rightarrow ψ (x_{0}, t_{x_{0}, s}) \neq ψ (x_{1}, t_{x_{1}, s}) . \end{matrix}$ Therefore, the numbering $β_{e}$ is Friedberg. Lemma 1.
For every e, we have $e \notin Cof$ if and only if $β_{e} (N) = S$ .
Proof.
If $e \notin Cof$ , then for each y there are only finitely many numbers u satisfying (6) for some a. Hence, for every y there is a finite limit ${lim}_{t} r (y, t)$ . For an arbitrary y we choose the least u such that $\begin{matrix} \forall y_{0} < y [lim_{t} r (y_{0}, t) = r (y_{0}, 2 c (y, u))] . \end{matrix}$ It follows from the construction that there exists an x such that $ψ_{s + 1} (x, t_{x, s + 1}) = y$ , where $s = 2 c (y, u)$ . Since r is monotonic in the second argument, given the checks (2), (3) and (7), as well as the assignments (4) and (5) in the construction, we obtain that $t_{x, s + 1} = t_{x, v}$ for every $v > s$ . Hence, $μ (y) \in β_{e} (N)$ . Since the choice of y is arbitrary, we get $β_{e} (N) = S$ .

Let $e \in Cof$ . Let us choose the least y with $N \cap [y, \infty) \subseteq W_{e}$ . Fix an s such that $\begin{array}{c} \forall y_{0} ⩽ y [lim_{t} r (y_{0}, t) = r (y_{0}, s)], \\ \forall n ⩽ r (y, s) \forall v ⩾ s [t_{n, s} = t_{n, v}], \\ \forall z_{0} ⩽ z [h_{s} (z_{0}) = lim_{t} h_{t} (z_{0})] \end{array}$ for the least z satisfying (7). Since the conditions (8) and (9) are checked and the assignments (11) are performed in the construction, we have $h (z) \notin ran ψ$ . Therefore, $μ (h (z)) \notin β_{e} (N)$ . □

This completes the proof of the theorem. □

Theorem 2 provides one more proof of one of the theorems of the paper [16].
Theorem 3 (S.S. Goncharov, A. Yakhnis, V. Yakhnis [16]).

Assume that $S \subseteq E$ satisfies the following three properties:

there are infinitely many finite sets in $S$ ;

for any finite set $A \in S$ there are infinitely many distinct (not necessarily finite) sets $B \in S$ such that $A \subseteq B$ ;

there exists a Friedberg computable numbering of S.

Then any class

K \subseteq H (S)

such that

K_{Fr} (S) \subseteq K

is effectively infinite.

Proof.
Let μ be a Friedberg computable numbering of S. Since $\begin{matrix} D ⇋ {x : μ (x) is finite} \in Σ_{2}^{0}, \end{matrix}$ there exists a function $h ⩽_{T} \emptyset^{'}$ such that $D = ran h$ . Now, using Theorem 2, we obtain the effective infinity of K. □

S.A. Badaev has proved in his paper [1] that any infinite computable family $S$ with the greatest element under inclusion has an infinite number of pairwise nonequivalent positive computable numberings. The following theorem proves that for any family $S$ with this property the class $K_{pos} (S)$ is even effectively infinite. Theorem 4.
If an infinite computable family $S \subseteq E$ has the greatest element under inclusion, then any class $K \subseteq H (S)$ such that $K_{pos} (S) \subseteq K$ is effectively infinite.
Proof.
Since the family $S$ is infinite and has the greatest element under inclusion, it follows from [1] that it has a positive computable numbering ν in which every element except the greatest one has a unique number. Without loss of generality, we assume that $ν (0)$ is the greatest element of $S$ under inclusion. To show the effective infinity of the class K, by Theorem 1 it suffices to define uniformly in each e a computable numbering $β_{e}$ for which the conditions $\begin{array}{c} e \notin Cof \Rightarrow β_{e} \in K_{pos} (S), \\ e \in Cof \Rightarrow β_{e} \notin H (S) \end{array}$ will be satisfied. In order to do this, we will construct a computable numbering $γ_{e}$ of some subfamily of the family $\begin{matrix} B = {{y} : ν (y) \neq ν (0)} \cup {N} \end{matrix}$ satisfying the same two conditions as $β_{e}$ and $S$ . Then we will define $\begin{matrix} β_{e} (x) = \{\begin{array}{ll} ν (y), & if γ_{e} (x) = {y}, \\ ν (0), & if γ_{e} (x) = N \end{array} \end{matrix}$ for each x. Fix an arbitrary e. The numbering $β_{e}$ will be computable because we will have $\begin{matrix} z \in β_{e} (x) \Leftrightarrow \exists y [y \in γ_{e} (x) & z \in ν (y)] \end{matrix}$ for all x and z. Note that any computable numbering μ of a subfamily of $B$ in which every element other than $N$ has a unique number is positive. Indeed, for all x and y we have $μ (x) = μ (y)$ if and only if $| μ (x) | > 1$ and $| μ (y) | > 1$ . In the construction, we will ensure that the numbering $γ_{e}$ will satisfy the same condition. Then, since $η_{β_{e}} = η_{γ_{e}}$ , the numbering $β_{e}$ will be positive.

Construction of $γ_{e}$ . Stage 0. Define $γ_{e, 0} (0) = N$ and $γ_{e, 0} (x) = \emptyset$ for each $x > 0$ .

Stage $s + 1 = 2 c (y, u) + 1$ . At these stages, we ensure $\begin{array}{c} e \notin Cof \Rightarrow γ_{e} (N) = B, \\ | γ_{e}^{- 1} ({y}) | ⩽ 1 . \end{array}$ If $\begin{matrix} ⟨ y, 0 ⟩ \notin η_{ν_{s}} & {y} \notin γ_{e, s} (N), \end{matrix}$ then we choose the least x such that $γ_{e, s} (x) = \emptyset$ and define $\begin{matrix} γ_{e, s + 1} (x) = {y} . \end{matrix}$ For every x, if $⟨ x, 0 ⟩ \in η_{ν_{s}}$ , then we define $\begin{matrix} γ_{e, s + 1} (z) = N \end{matrix}$ for each z with $x \in γ_{e, s} (z)$ .

Stage $s + 1 = 2 c (y, u) + 2$ . At these stages, we ensure $\begin{matrix} e \in Cof \Rightarrow γ_{e} (N) \neq B . \end{matrix}$ If either there is no $a \in N$ such that $\begin{matrix} (13) & N \cap [y, a] ⊈ W_{e, u} & N \cap [y, a] \subseteq W_{e, u + 1} \end{matrix}$ or there is no $z > y$ with $⟨ z, 0 ⟩ \notin η_{ν_{s}}$ and ${z} \in γ_{e, s} (N)$ , then we go to the next stage. Otherwise, we choose the least such z and define $\begin{matrix} (14) & γ_{e, s + 1} (x) = N \end{matrix}$ for the least (and the unique) x such that $γ_{e, s} (x) = {z}$ .

At the end of the construction, we define $γ_{e} = ⋃_{s} γ_{e, s}$ . The construction at its odd stages ensures that ${x} \notin γ_{e} (N)$ for each x with $⟨ x, 0 ⟩ \in η_{ν}$ .

If $e \notin Cof$ , then for every $y_{0}$ we can choose a u such that there are no $y ⩽ y_{0}$ and a satisfying (13). It follows that if $⟨ y_{0}, 0 ⟩ \notin η_{ν}$ , then ${y_{0}} \in γ_{e, s + 1} (N)$ for each $s ⩾ 2 c (y_{0}, u)$ . Hence, $γ_{e} (N) = B$ . Therefore, $β_{e} (N) = S$ .

If $e \in Cof$ , then we choose the least y such that $\begin{matrix} N \cap [y, \infty) \subseteq W_{e} . \end{matrix}$ Then the construction at stages $s + 1 = 2 c (y, u) + 2$ , $u \in N$ , and assignments (14) ensure that there is a $z > y$ such that $⟨ z, 0 ⟩ \notin η_{ν}$ and ${z} \notin γ_{e} (N)$ . Hence, $γ_{e} (N) \neq B$ . Therefore $β_{e} (N) \neq S$ . □

4. Numberings of families of reals

In this section, the results of the previous section are applied to computable families of reals. It follows from the results of Harris’ paper [17] that every infinite computable family $A \subseteq L$ containing only natural numbers has Friedberg computable numbering. The following theorem extends this statement to families $A \subseteq L$ containing not only integers.

Theorem 5.

Let $A \subseteq L$ be a nonempty computable family without the greatest element. Then it has a Friedberg computable numbering.

Proof.

M. Kummer has proved in his paper [18] that if a computable family $S$ can be partitioned into two disjoint computable families $S_{1}$ and $S_{2}$ such that $S_{1}$ has a Friedberg computable numbering and contains infinitely many extensions of every finite subset of any member of $S_{2}$ , then $S$ also has a Friedberg computable numbering. To prove the theorem, we will define such families $S_{1}$ and $S_{2}$ for the family $S = D (A)$ . In order to do this we define a binary computable function f nondecreasing in the second argument. Let γ be a computable numbering of $D (A)$ . Define $\begin{matrix} f (x, 0) = x \end{matrix}$ for each x. We assume by induction on s that $f (x, t)$ is defined for all $t < s$ and x. If there exists an $x ⩽ s$ such that $\begin{matrix} max (⋃_{y ⩽ f (x + 1, s)} γ_{s} (y)) - max (⋃_{y ⩽ f (x, s)} γ_{s} (y)) < {(f (x + 1, s))}^{- 1}, \end{matrix}$ then we choose the least such x and define $\begin{matrix} f (y, s + 1) = \{\begin{array}{ll} f (y, s) + 1, & if y > x, \\ f (y, s), & if y ⩽ x . \end{array} \end{matrix}$ If such x does not exist, then we define $\begin{matrix} f (y, s + 1) = f (y, s) \end{matrix}$ for each y. Since $A$ has no greatest element, for every x there exists a finite limit $\begin{matrix} lim_{s} f (x, s) . \end{matrix}$ Also, it is not hard to see that the sequence of reals ${sup (⋃_{y ⩽ x} γ (F (y)))}_{x \in N}$ , where $\begin{matrix} F (x) = lim_{s} f (x, s), x \in N, \end{matrix}$ is strictly increasing and has no upper bound belonging to $A$ . We define a Friedberg computable numbering β by letting $\begin{matrix} β (x) = ⋃_{y ⩽ x} γ (F (y)) \end{matrix}$ for each x. Let $\begin{matrix} S_{1} = {β (2 x) : x \in N} . \end{matrix}$ It remains to prove that the family $S_{2} = D (A) ∖ S_{1}$ is computable. In order to prove it, we define its computable numbering α. For an arbitrary triple x, y, t, we let $α (c (c (x, y), t)) = γ (y)$ if $\begin{matrix} (15) & max β_{s} (2 x) + t^{- 1} < max γ_{s} (y) < max β_{s} (2 x + 2) - t^{- 1}, \end{matrix}$ for each $s ⩾ t$ . Otherwise, we choose the least s for which (15) does not hold and then the least $c (v, z) = c (v (s), z (s))$ such that $γ_{s} (y) \subseteq β_{v} (2 z + 1)$ , and define $\begin{matrix} α (c (c (x, y), t)) = β (2 z + 1) . \end{matrix}$ By the definition of α we have $α (N) = S_{2}$ . Let us show that α is computable. For all natural numbers b, x, y, t we have $b \in α (c (c (x, y), t))$ if and only if one of the following conditions holds:

there exists a $u ⩽ t$ such that $b \in γ_{u} (y)$ and (15) holds for each s with $t ⩽ s ⩽ u$ ;

$b \in β (2 z (s) + 1)$ , where $s ⩾ t$ is the least integer for which (15) fails.

Thus, α is computable. This completes the proof of the theorem. □

Corollary 1.

If a nonempty computable family $A \subseteq L$ has no greatest element, then the classes $K_{Fr} (A)$ , $K_{dec} (A)$ , $K_{pos} (A)$ , $K_{min} (A)$ , $K_{neg} (A)$ and $K_{all} (A)$ are effectively infinite. In particular, this is true if $A$ is the family of all (Martin-Löf random [ 6 , 21 ]) left-c.e. reals.

Proof.

Any Friedberg computable numbering μ of $A$ and the identity function h satisfy the conditions of Theorem 2. Therefore, all those classes are effectively infinite. □

Corollary 2.

Let $A \subseteq L$ be an infinite computable family. Then the classes $K_{pos} (A)$ , $K_{min} (A)$ and $K_{all} (A)$ are effectively infinite.

Proof.

If $A$ has no greatest element, then we apply Corollary 1. Otherwise, we apply Theorem 4. □

Finally, we show that there exists an infinite computable family $A \subseteq L$ without Friedberg computable numberings.

Proposition 1.

There exists an infinite computable family $A \subseteq L$ without Friedberg computable numberings such that $A$ contains only nonpositive integers.

Proof.

Fix an arbitrary noncomputable c.e. set U. Define a computable family $A \subseteq L$ by $\begin{matrix} A = {- 2 n : n \in N} \cup {- 2 n - 1 : n \notin U} . \end{matrix}$ Let us show that $A$ has no Friedberg computable numberings. Assume for a contradiction that such a numbering does exist. Then the family $\begin{matrix} B = {Z \cap (- \infty, z] : z \in A} \end{matrix}$ also has a Friedberg computable numbering μ. Without loss of generality, we assume that $μ (0) = Z \cap (- \infty, 0]$ . Since μ is Friedberg, for every n we have $n \notin U$ if and only if there are pairwise distinct natural numbers $x_{0}, y_{0}, \dots, x_{n}, y_{n}$ such that $\begin{aligned} - 2 (n + 1) \in μ (x_{n}) & (- 2 n - 1) \in μ (y_{n}) & \\ & \forall m < n [- 2 (m + 1) \in μ (x_{m}) & [(- 2 m - 1) \in μ (y_{m}) \lor m \in U]] . \end{aligned}$ Hence, $\overline{U}$ is c.e. Since U is c.e., it is computable. This is the contradiction. □

Footnotes

Acknowledgements

The work of the first author was supported by the Russian Science Foundation (grant no. 23-21-00181) and performed under the development programme of the Volga Region Mathematical Center (agreement no. 075-02-2023-944).

References

S.A.

Badaev, Positive enumerations, Sib. Math. J.18 (1977), 483–496. doi:10.1007/BF00967026.

S.A.

Badaev and

S.S.

Goncharov, On computable minimal enumerations, in: Algebra. Proceedings of the Third International Conference on Algebra, Dedicated to the Memory of M.I. Kargopolov, Krasnoyarsk, August 23–28, 1993,

Y.L.

Ershov,

E.I.

Khukhro,

V.M.

Levchuk and

N.D.

Podufalov, eds, Walter de Gruyter, Berlin–New York, 1995, pp. 21–32. doi:10.1515/9783110813418-005.

S.A.

Badaev and

S.S.

Goncharov, The theory of numberings: Open problems, in: Computability Theory and Its Applications. Current Trends and Open Problems,

P.A.

Cholak,

Lempp,

Lerman and

R.A.

Shore, eds, Amer. Math. Soc., Providence, 2000, pp. 23–38. doi:10.1090/conm/257/04025.

S.A.

Badaev and

S.S.

Goncharov, Rogers semilattices of families of arithmetic sets, Algebra and Logic40 (2001), 283–291. doi:10.1023/A:1012516217265.

Brodhead and

Kjos-Hanssen, Numberings and randomness, in: Mathematical Theory and Computational Practice, CiE 2009,

Ambos-Spies,

Löwe and

Merkle, eds, Lecture Notes in Computer Science, Vol. 5635, Springer, Berlin, Heidelberg, 2009, pp. 49–58. doi:10.1007/978-3-642-03073-4_6.

R.G.

Downey and

D.R.

Hirschfeld, Algorithmic Randomness and Complexity, Springer-Verlag, New York, 2010.

Y.L.

Ershov, Theorie der numerierungen I, Z. Math. Logik und Grundlag. Math.19 (1973), 19–25. 289–388.

Y.L.

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

Y.L.

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

E.R.

Griffor, ed., Stud. Logic Found. Math., Vol. 140, Elsevier, Amsterdam, 1999, pp. 473–503. doi:10.1016/S0049-237X(99)80030-5.

10.

Faizrahmanov, Limitwise monotonic spectra and their generalizations, in: Connecting with Computability, CiE 2021,

De Mol,

Weiermann,

Manea and

Fernández-Duque, eds, Lecture Notes in Computer Science, Vol. 12813, Springer, Cham, 2021, pp. 189–198. doi:10.1007/978-3-030-80049-9_17.

11.

Faizrahmanov, A local version of the Slaman–Wehner theorem and families closed under finite differences, Notre Dame J. Form. Log.64 (2023), 197–203. doi:10.1215/00294527-10670074.

12.

Faizrahmanov, Effectively infinite classes of numberings of computable families of reals, Izv. Vyssh. Uchebn. Zaved. Mat.67 (2023), 96–100, (in Russian). doi:10.26907/0021-3446-2023-5-96-100.

13.

Faizrahmanov and

Kalimullin, Limitwise monotonic sets of reals, Math. Log. Quart.61 (2015), 224–229. doi:10.1002/malq.201400015.

14.

R.M.

Friedberg, Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication, J. Symb. Logic23 (1958), 309–316. doi:10.2307/2964290.

15.

S.S.

Goncharov and

Sorbi, Generalized computable numerations and nontrivial Rogers semilattices, Algebra and Logic36 (1997), 621–641. doi:10.1007/BF02671553.

16.

S.S.

Goncharov,

Yakhnis and

Yakhnis, Some effectively infinite classes of enumerations, Ann. and Pure Appl. Log.60 (1993), 207–235. doi:10.1016/0168-0072(93)90076-P.

17.

Harris, η-representation of sets and degrees, J. Symb. Logic73 (2008), 1097–1121. doi:10.2178/jsl/1230396908.

18.

Kummer, An easy priority-free proof of a theorem of Friedberg, Theoret. Comput. Sci.74 (1990), 249–251. doi:10.1016/0304-3975(90)90141-4.

19.

A.I.

Mal’tsev, Positive and negative enumerations, Dokl. Akad. Nauk SSSR160 (1965), 278–280.

20.

Myhill, Creative sets, Z. Math. Logik und Grundlag. Math.1 (1955), 97–108. doi:10.1002/malq.19550010205.

21.

Nies, Computability and Randomness, Oxford University Press, New York, 2009.

22.

R.I.

Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Funtions and Computably Generated Sets, Perspect. Math. Log., Springer-Verlag, Berlin, 1987.

23.

R.I.

Soare, Turing Computability: Theory and Applications, Springer, Berlin, 2016.

24.

V.A.

Uspenskii, Some notes on recursively enumerable sets, Z. Math. Log. und Grundl. Math.3 (1957), 157–170. doi:10.1002/malq.19570031202.