Enumerations of families closed under finite differences

Abstract

Slaman and Wehner independently built a family of sets with the property that every non-computable degree can compute an enumeration of the family, but there is no computable enumeration of the family. We call such a family a Slaman–Wehner family. The original Slaman–Wehner argument relies on all sets in the family constructed being finite, and in particular, it diagonalizes against computably enumerated families using only finite differences. In this paper we ask whether this is a necessary feature, that is, whether there is a Slaman–Wehner family closed under finite differences. This question remains open but we obtain a number of interesting partial results which can be interpreted as saying that the question is quite hard.

First of all, no Slaman–Wehner family closed under finite differences can contain a finite set, and the enumeration of the family from a non-computable degree cannot be uniform (whereas, in the Slaman–Wehner construction, it is uniform). On the other hand, we build the following examples of families closed under finite differences which show the impossibility of several natural attempts to show that no Slaman–Wehner family exists: (1) a family that can be enumerated by every non-low degree, but not by any low degree; (2) a family that can be enumerated by any set in a given uniform list of c.e. sets, but which cannot be enumerated computably; and (3) a family that can be enumerated by a given $Δ_{2}^{0}$ set, but which cannot be computably enumerated.

Keywords

Slaman–Wehner family enumerations

1. Introduction

This paper is concerned with the computational properties of families of subsets of ω. Such families have played an important role in computable structure theory because they can be coded into countable structures. Many important examples have been produced by constructing a family with certain computational properties, and then coding that family into a countable graph (often called the bouquet graph of that family, see e.g. [1,8,9]). For example, Goncharov constructed a computable structure of effective dimension 2 in this way [6,7].

Given a family of subsets of ω, we can ask: how hard is it to build a copy of that family? To build a copy of the family, we must build a copy of each set in the family, though it does not matter what order we present the sets in.

Definition 1.1.
An enumeration of a countable family $F \subseteq P (ω)$ is a set $W \subseteq ω^{2}$ such that $F = {W^{[i]} : i \in ω}$ , where $W^{[i]}$ is the ith column of W. The order of the columns in W and their multiplicity is not relevant. To avoid issues with multiplicity, we may always assume that in an enumeration of a family each column is replicated infinitely many times. A family $F$ is computably enumerable from a set X if there is an X-c.e. enumeration of $F$ .

A surprising result of Slaman [13] and Wehner [17] is that there is a family consisting of finite sets that can be enumerated by every non-computable degree, but which has no computable enumeration. Thus the problem of enumerating this family captures exactly the property of being non-computable.

We focus on families that are closed under finite differences.
Definition 1.2.
We say that a family $F$ is closed under finite differences if whenever $A \in F$ and $B =^{} A$ , $B \in F$ . (Here, $A =^{} B$ means that A and B differ on only finitely many elements.)

There are natural places in which such families arise; for example natural computability-theoretic families such as the family of computable sets are closed under finite differences. The motivating example for us comes from torsion-free abelian groups. If G is a torsion-free abelian group, one can consider the family of sets ${p prime : p | g}$ for $g \in G$ . If G has no infinite divisibilities, then this family is closed under finite differences. One might hope to gain some insight into the following difficult open question by studying families closed under finite difference, though there are no formal implications in any direction:
Question 1.3.
Is there a torsion-free abelian group that has a presentation computable in every non-computable degree but no computable presentation?

Our main goal in writing this paper was to build a Slaman–Wehner family that is closed under finite differences. Unfortunately, we are unable to solve this question.
Question 1.4.
Is there a family closed under finite differences that can be enumerated by every non-computable degree, but which has no computable enumeration?

We call such a family a Slaman–Wehner family closed under finite differences. Standard forcing arguments (see Proposition 3.1) show that if there were such a family, then it would contain only c.e. sets, so we restrict our attention to those. Also, a theorem of Lachlan [10] quickly yields that from an enumeration of a family closed under finite differences allowing repetition, we can compute a Friedberg enumeration, i.e. an enumeration with no repetition (Corollary 2.2). So, unlike families not closed under finite differences, we do not need to make any convention about how many times each set is enumerated in an enumeration.

Though this question remains open, we prove a number of interesting results. We have two negative result which place some restriction on such a family, should it exist. First, we show that any Slaman–Wehner family closed under finite differences must consist only of infinite sets. Second, we show that such a family cannot be enumerated in a uniform way:
Theorem 1.5.
Let $F$ be a family of sets closed under finite differences. Suppose that there is a c.e. operator Φ such that for every non-computable set X, $Φ^{X}$ is an enumeration of $F$ . Then $F$ can be enumerated computably.

It is interesting to note that there is a Slaman–Wehner family (not closed under finite differences) that has no uniform enumeration. This is an argument due to Faizrahmanov and Kalimullin [4]; the non-uniformity comes from the fact that every non-computable set, viewed as a binary expansion, is either not left-c.e. or not right-c.e. (or neither), but which of these is the case is not effective.

On the other hand, there are no obvious obstacles to such a family existing. We prove the existence of the following families:
Theorem 1.6.
There is a family closed under finite differences that can be enumerated uniformly by every non-low degree, but which cannot be enumerated by any low degree.
Theorem 1.7.
Given a uniformly c.e. sequence ${(D_{e})}_{e \in ω}$ of non-computable c.e. sets, there is a family of c.e. sets closed under finite differences that can be enumerated by every $D_{e}$ , but which cannot be enumerated computably.
Theorem 1.8.
For any non-computable $Δ_{2}^{0}$ set D, there is a family of c.e. sets closed under finite differences that can be D-computably enumerated, but which cannot be enumerated computably.

Combining the first and third of these positive results, note that for every non-computable set X, there is a family of c.e. sets closed under finite differences that can be X-enumerated, but which cannot be enumerated computably. So no single set forms a barrier to the existence of a Slaman–Wehner family closed under finite differences. The next natural question is whether there is a minimal pair:
Question 1.9.
Is there a pair of non-computable sets X and Y such that any family of c.e. sets closed under finite differences that can be enumerated by both X and Y can be enumerated computably?

We know from Theorem 1.7 that no pair of c.e. sets is a minimal pair in this sense. Recently and following the work in this paper, Faizrahmanov has announced that there is a family of c.e. sets closed under finite differences which can be enumerated by every non-computable c.e. set, but which cannot be enumerated computably. Notation 1.10.
For a c.e. operator Φ, an oracle X, and $i \in ω$ , we let $Φ^{X, [i]} = {n : (i, n) \in Φ^{X}}$ be the $i^{th}$ column of $Φ^{X}$ . For a string ξ and $k < | ξ |$ we let $ξ ↾ ↾ k = ξ ↾ (k + 1)$ .

2. Friedberg enumerations

Friedberg [5] showed that there is an effective enumeration of the c.e. sets in which each set appears exactly once. More generally, a Friedberg enumeration or an injective enumeration of a family $F$ is an enumeration in which each set appears exactly once. There is a long history of providing sufficient conditions for a family with a computable enumeration to have a computable Friedberg enumeration. We will use the following condition due to Lachlan [10,11].

Given a finite set C, let $W_{C} = {W_{x} : x \in C}$ . A class $F$ has the property (E) if there is a binary partial computable function $η : {[ω]}^{< ω} \times {[ω]}^{< ω} \to ω$ such that if C and D are finite sets and $W_{C} \subseteq F$ , then $η (C, D)$ is defined if and only if $\begin{matrix} (F - W_{C}) \cap {X : X \supseteq D} \end{matrix}$ is non-empty, and in this case $η (C, D)$ is an index of a member of this class. Lachlan proved:

Theorem 2.1 (Lachlan [10,11]).

An infinite c.e. class $F$ has the property (E) if and only if given a finite subclass $G$ of $F$ we can effectively enumerate $F - G$ without repetition.

It is not hard to show that a family of infinite sets closed under finite differences satisfies condition (E), yielding:

Corollary 2.2.
Let $F$ be a family of sets closed under finite differences. From an enumeration of $F$ allowing repetition, we can compute an enumeration of $F$ with no repetition.
Proof.
If $F$ contains a finite set, then it contains every finite set. The standard Friedberg argument goes through. (See e.g. [12].)

Now suppose that every set in $F$ is infinite. We relativise Lachlan’s theorem to a given enumeration of $F$ . Fix a set $X \in F$ . Given finite sets C and D, for each $x \in C$ , look for $y_{x} \in W_{x} - D$ . Once we find such a $y_{x}$ for each $x \in C$ , which we eventually will if $W_{C} \subseteq F$ , then define $η (C, D)$ to be an index for $X \cup D - {y_{x} : x \in C}$ . This is a finite difference of the set X, and hence it is in $F$ . So $F$ has condition (E) relative to every enumeration of $F$ . □

3. Negative results

In this section we present our two negative results, i.e. results which say that families of a certain kind have computable enumerations, and hence cannot have Slaman–Wehner spectrum. These results are proved using the forcing relation; in all cases, when we say that a real is sufficiently generic, we mean with respect to Cohen forcing. We present the proof of the following well-known fact as a warm-up.1

¹
In fact, a result of de Leeuw, Moore, Shannon, and Shapiro says no non-c.e. set can be enumerated even by a positive measure of sets [2], see Theorem 8.12.1 of [3].

Proposition 3.1.

Let $F$ be a family of sets that can be enumerated by every degree $d > 0$ . Each set in $F$ is c.e.

Proof.

Let X be sufficiently generic relative to $F$ . Let Φ be a Turing functional such that $Φ^{X}$ is an enumeration of $F$ . Fix i. Let $Y = Φ^{X, [i]}$ . There is $σ ≼ X$ such that $σ ⊩ Y = Φ^{X, [i]}$ . Then $\begin{matrix} Y = {n | \exists ρ ≽ σ such that ρ ⊩ n \in Φ^{G, [i]}} . \end{matrix}$ The right-hand-side is c.e. □

Our first negative result is that a family that is closed under finite differences and contains a (and hence every) finite set cannot have Slaman–Wehner spectrum: if it can be enumerated by every non-computable degree, then it has a computable enumeration.

Theorem 3.2.

Let $F$ be a family of sets, closed under finite differences, that can be enumerated by every degree $d > 0$ . If $F$ contains a finite set, then $F$ can be enumerated computably.

This follows quickly from known results: The set $I (F) = {e : W_{e} is in F}$ is $Σ_{3}^{0}$ relative to positive measure many sets, and so by [15] $I (F)$ is $Σ_{3}^{0}$ . Then, since $I (F)$ is $Σ_{3}^{0}$ , by [18] (see also Theorem XII.3.2 of [14]), $F$ can be enumerated computably. However we will present a self-contained proof because it will illustrate some of the issues at hand.

The idea of the proof is as follows: $F$ can be enumerated by a generic set X via a function Φ, and there is an initial segment η of X that forces the fact that every set enumerated by Φ is a set in $F$ . Now for a given i, some of the extensions of η force that $Φ^{G, [i]}$ is a particular set $W_{e}$ , and others do not; if an extension σ of η does not force the identity of $Φ^{G, [i]}$ , then it has extensions $σ_{1}$ and $σ_{2}$ that force that $Φ^{G, [i]} = W_{e_{1}}$ and that $Φ^{G, [i]} = W_{e_{2}}$ respectively, with $W_{e_{1}} \neq W_{e_{2}}$ . For each σ and i, we will enumerate a set $Q_{i, σ}$ . By guessing at whether or not σ forces that $Φ_{e}^{G, [i]} = W_{e}$ for some e, we will be able to make $Q_{i, σ}$ equal to $W_{e}$ if σ does force this fact, and finite otherwise. Since $F$ contains the finite sets, it will not be a problem when $Q_{i, σ}$ is finite.

Proof.

Let X be sufficiently generic, and let Φ be a Turing functional such that $Φ^{X}$ is an enumeration of $F$ . There is an initial segment of X that forces this fact. We will assume for convenience that this initial segment is the empty string; otherwise, we just work among extensions of this string.

For each σ and i, we will define a set $Q_{i, σ}$ such that either $Q_{i, σ}$ is finite, or $σ ⊩ Φ^{G, [i]} = W_{e}$ and $Q_{i, σ} = W_{e}$ . Define $Q_{i, σ}$ as follows. Put $n \in Q_{i, σ}$ if:

for all $m < n$ , if $m \in Φ^{τ, [i]}$ for some $τ ≽ σ$ of length $| σ | + n$ , then for every $τ ≽ σ$ of length $| σ | + n$ there is $ρ ≽ τ$ with $m \in Φ^{ρ, [i]}$ , and

there is a string $ρ ≽ σ$ with $n \in Φ^{ρ, [i]}$ .

Suppose that $σ ⊩ Φ^{G, [i]} = W_{e}$ for some e. It is not hard to see that $Q_{i, σ} \subseteq W_{e}$ . On the other hand, suppose that $n \in W_{e}$ . We show that $n \in Q_{i, σ}$ , so that $Q_{i, σ} = W_{e}$ . For (1): Suppose that $m < n$ is such that $m \in Φ^{τ, [i]}$ for some τ of length $| σ | + n$ ; then $m \in W_{e}$ . Given any τ of length $| σ | + n$ , there is a sufficiently generic $Y ≽ τ$ . Then $Φ^{Y, [i]} = W_{e}$ and so $m \in Φ^{Y, [i]}$ . Thus there is $ρ ≽ τ$ with $m \in Φ^{ρ, [i]}$ . For (2): There is $Y ≽ σ$ sufficiently generic, and so $Φ^{Y, [i]} = W_{e}$ . So there is $ρ ≽ σ$ with $n \in Φ^{ρ, [i]}$ .

On the other hand, suppose that there is no e for which $σ ⊩ Φ^{G, [i]} = W_{e}$ . Then there are $Y, Z ≽ σ$ sufficiently generic with $Φ^{Y, [i]} \neq Φ^{Z, [i]}$ . Suppose without loss of generality that there is $m \in Φ^{Y, [i]} - Φ^{Z, [i]}$ . Let $τ_{Y} ≼ Y$ be such that $m \in Φ^{τ_{Y}, [i]}$ , and let $τ_{Z} ≼ Z$ be such that $τ_{Z} ⊩ m \notin Φ^{G, [i]}$ ; so there is no extension ρ of $τ_{Z}$ with $m \in Φ^{ρ, [i]}$ . Let $N = max (m, | τ |, | ρ |)$ . Then no $n ⩾ N$ satisfies (1), and so no element of $Q_{i, σ}$ is larger than N. Thus $Q_{i, σ}$ is finite.

In either case, $Q_{i, σ}$ is in $F$ . It remains to show that each element of $F$ is one of the $Q_{i, σ}$ . Fix $W_{e}$ in $F$ . Let X be sufficiently generic, and let i be such that $Φ^{X, [i]} = W_{e}$ . Let $σ ≼ X$ be such that $σ ⊩ Φ^{G, [i]} = W_{e}$ . Then $Q_{i, σ} = W_{e}$ . □

Now we will show that there is no Slaman–Wehner family closed under finite differences with this witnessed in a uniform way. The families constructed by Slaman and Wehner were uniform, so if there is a Slaman–Wehner family closed under finite differences it must be constructed in a different way. By “uniform”, we mean that there is an operator Φ such that $Φ^{X}$ enumerates the family whenever X is non-computable.

Theorem 3.3.

Let $F$ be a family of sets, closed under finite differences, that can be enumerated uniformly by every degree $d > 0$ . Then $F$ can be enumerated computably.

Proof.

Let Φ be a Turing functional which witnesses that $F$ can be uniformly enumerated by every non-computable degree. Uniformly in each σ and i, we will enumerate a set $Q_{i, σ}$ . For some 1-generic $X ≽ σ$ , we will have $Q_{i, σ} =^{*} Φ^{X, [i]} \in F$ . Before constructing the sets $Q_{i, σ}$ , we will show how they suffice to prove the theorem.

For each $W \in F$ , we argue that there are i and σ such that $W =^{*} Q_{i, σ}$ , so that if we take the family ${Q_{i, σ} | i \in ω, σ \in 2^{< ω}}$ and close it under finite differences we get an enumeration of $F$ . Let Y be sufficiently generic. There is i such that $W = Φ^{Y, [i]}$ . So there is $σ ≼ Y$ such that $σ ⊩ W = Φ^{G, [i]}$ . Let $X ≽ σ$ be a 1-generic such that $Q_{i, σ} =^{*} Φ^{X, [i]}$ . We claim that $W = Φ^{X, [i]}$ . Indeed, suppose that $n \in Φ^{X, [i]}$ . Then there is $ρ ≽ σ$ such that $ρ ⊩ n \in Φ^{G, [i]}$ , and so there is a sufficiently generic $Z ≽ ρ$ with $n \in Φ^{Z, [i]} = W$ . A similar argument works when $n \notin Φ^{X, [i]}$ .

We now construct $Q_{i, σ}$ and an approximation to a 1-generic $X ≽ σ$ with $Q_{i, σ} =^{*} Φ^{X, [i]}$ . Let ${(W_{e})}_{e \in ω}$ be an enumeration of the c.e. sets. For simplicity, we will write $Ψ^{X} = Φ^{X, [i]}$ .

We can think of the argument as a failed diagonalization argument. We will attempt to construct a set Y to meet the following requirements: $\begin{matrix} R_{e} : Ψ^{Y} \neq W_{e} . \end{matrix}$ Of course, we will not be able to meet all of these requirements, as no matter what Y is, $Ψ^{Y}$ is c.e. If Y is computable, $Φ^{Y}$ is c.e., and if Y is non-computable, then $Φ^{Y}$ is in the family $F$ and hence is c.e. (We use Y here because the 1-generic set X we want will be obtained by combining the approximation to Y with that of a 1-generic Z.)

The possible outcomes of a requirement $R_{e}$ are the infinitary outcome ∞, and finitary outcomes and . An outcome represents that $n \notin W_{e}$ and $n \in Ψ^{τ}$ . An outcome represents that $n \in W_{e}$ and for all $ρ ≽ τ$ , $n \notin Ψ^{ρ}$ . These two types of outcomes are finitary because we will leave when n enters $W_{e}$ and we will leave when we find a $ρ ≽ τ$ with $n \in Ψ^{ρ}$ . If either of the finitary outcomes is the true outcome, then $R_{e}$ will be satisfied; but in the infinitary outcome, $R_{e}$ will not be satisfied.

For a strategy ξ on the tree, we also define the (finite) binary string $y (ξ)$ which is the initial segment of Y determined by ξ. The empty sequence $⟨ ⟩$ is a strategy and $y (⟨ ⟩) = σ$ . Suppose that we have determined that ξ, of length e, is a strategy. If the last entry of ξ is ∞, then ξ is terminal – no proper extensions of ξ are strategies. Otherwise, the possible outcomes of ξ on the tree of strategies are ∞, and the outcomes and with $τ ≽ y (ξ)$ . We let $y (ξ ˆ \infty) = y (ξ)$ . For all n and $τ ≽ y (ξ)$ , we let .

At each stage, we will define a strategy $ξ_{s}$ and let $y_{s} = y (ξ_{s})$ . We will let ξ, the true path, be the path of strategies leftmost visited infinitely often (where the outcome ∞ lies to the left of the others). We will argue that ξ is in fact finite (it is terminal, with last entry ∞); otherwise, we show that $Y = y (ξ)$ meets all requirements, which is impossible. The last entry of ξ indicates the least e for which the requirement $R_{e}$ is not met. Each $R_{i}$ , $i < e$ , will be satisfied with one of the finitary outcomes, and so once these have stabilized, say at stage $s^{*}$ , we will have $y (ξ) ≼ y_{s}$ for all $s ⩾ s^{*}$ , and $y_{s} = y (ξ)$ whenever $s ⩾ s^{*}$ is a true stage. (This will all be verified after the construction.)

Letting Z be a $Δ_{2}^{0}$ 1-generic with computable approximation ${(z_{s})}_{s \in ω}$ , our 1-generic $X ≽ σ$ will be $X = y (ξ) ˆ Z$ . We have an approximation to X given by $x_{s} = y_{s} z_{s}$ . (Note that this is not a $Δ_{2}^{0}$ approximation; we cannot specify $y (ξ)$ as a parameter, as the construction has to be uniform in i and σ). Using the fact that we failed to satisfy $R_{e}$ , we will show in Claim 3 that defining $Q_{i, σ} = {n : \exists s n \in Ψ_{s}^{x_{s}}}$ , we get $Q_{i, σ} =^{*} Ψ^{X} = W_{e}$ .

Construction.

Stage 0: Begin with $ξ_{0} = ⟨ \infty ⟩$ .

Stage $s + 1$ : a strategy $ζ ≺ ξ_{s}$ is discovered to be incorrect at stage $s + 1$ if, letting $e = | ζ |$ , we have:

and $n \in W_{e, s}$ ;

and $n \in Ψ_{s}^{ρ}$ for some $ρ ≽ τ$ ; or

$ξ_{s} (e) = \infty$ , and there are some n and $τ ≽ y (ζ)$ (with $n, | τ | ⩽ s$ ) such that either

$n \notin W_{e, s}$ and $n \in Ψ_{s}^{τ}$ ; or

$n \in W_{e, s}$ and $n \notin Ψ_{s}^{ρ}$ for all $ρ ≽ τ$ (of length $⩽ s$ ).

If no $ζ ≺ ξ_{s}$ is discovered to be incorrect at stage $s + 1$ , then we let $ξ_{s + 1} = ξ_{s}$ . Otherwise, let ζ be the shortest initial segment of $ξ_{s}$ discovered to be wrong at stage $s + 1$ . We define $ξ_{s + 1}$ as follows:

In cases (1) and (2), i.e., when $ξ_{s} (e) \neq \infty$ , we let $ξ_{s + 1} = ζ ˆ \infty$ .

In sub-case (3i), choosing the least τ and n, we let .

In sub-case (3ii), again choosing the least τ and n, we let .

End construction.

Verification.

Let ξ be the leftmost path visited infinitely often. Then either ξ is a finite, terminal strategy, or it is infinite (and so does not contain an entry ∞). We will shortly see that it is the former.

We note that if $ζ ≺ ξ$ is non-terminal, then $ζ ≺ ξ_{s}$ for all but finitely many stage s; for every $e < | ζ |$ , once $ζ ↾ e$ has stabilised, once the outcome $ζ (e)$ is chosen, it will never be un-chosen, as we cannot return to a discarded outcome.

If ξ is infinite, let $y (ξ) = ⋃_{ζ ≺ ξ} y (ζ)$ ; if ξ is finite, then $y (ξ)$ is already defined. We are in the slightly notationally awkward situation where we do not yet know whether ξ and $y (ξ)$ are finite or infinite strings, so in the next lemma we will have to talk about strings $Y \in 2^{ω}$ with $Y ≽ y$ where it might be that $Y = y (ξ)$ if y is infinite. Claim 1.

If $e < | ξ |$ and $ξ (e) \neq \infty$ then $Ψ^{Y} \neq W_{e}$ for any $Y ≽ y (ξ)$ .

Proof.

As discussed, there is some stage after which $ξ_{t} ↾ ↾ e = ξ ↾ ↾ e$ .

First suppose that . Then $n \notin W_{e}$ , since if we found that $n \in W_{e}$ , we would never again have this outcome. Also, when we first had this outcome, we had $n \in Ψ^{τ}$ . Since $Y ≽ τ$ , $Ψ^{Y} \neq W_{e}$ .

Now if , then $n \in W_{e}$ , but for all $ρ ≽ τ$ , $n \notin Ψ^{ρ}$ . Since $Y ≽ τ$ , $n \notin Ψ^{Y}$ and so $Ψ^{Y} \neq W_{e}$ . □

If $Y ≽ y (ξ)$ , then $Ψ^{Y}$ is a c.e. set $W_{e}$ (either for obvious reasons because Y is computable, or if Y is non-computable, then $Ψ^{Y}$ is in the family $F$ and hence a c.e. set). So as a consequence of this lemma, ξ must be finite, with last entry ∞, and $y : = y (ξ)$ is finite as well. Let $s_{0}$ be a stage after which $ξ^{-} ≺ ξ_{s}$ (where $ξ^{-}$ is the result of removing the last entry ∞ from ξ). So $y (ξ) ≼ y_{s}$ for all $s ⩾ s_{0}$ . We say that a stage $s ⩾ s_{0}$ is true if $ξ_{s} = ξ$ . There are infinitely many true stages. Claim 2.

Let $e = | ξ | - 1$ (so $ξ (e) = \infty$ ). Let $Y ≽ y$ be a 1-generic extending y. Then $Ψ^{Y} = W_{e}$ .

Proof.

If there is $n \in Ψ^{Y} - W_{e}$ , then there is some $τ ≼ Y$ with $n \in Ψ^{τ}$ . Then the outcome $ξ (e)$ would be for some such pair n, τ.

If there is $n \in W_{e} - Ψ^{Y}$ , then since Y is 1-generic, there is a τ such that $y ≼ τ ≺ Y$ and for all $ρ ≽ τ$ , $n \notin Ψ^{ρ}$ . Then the outcome $ξ (e)$ would be for some such pair n, τ. □

Let ${(z_{s})}_{s \in ω}$ be a $Δ_{2}^{0}$ approximation of a 1-generic Z. Let $X = y ˆ Z$ and $x_{t} = y_{t} z_{t}$ ; X is a 1-generic extending y. For each m, there are infinitely many stages $t ⩾ s_{0}$ such that $x_{t} = y_{t} z_{t} ≽ X ↾_{m}$ , indeed this holds for almost all true stages. Claim 3.

Let $Q_{i, σ} = {n : \exists s n \in Ψ_{s}^{x_{s}}}$ . Then $Q_{i, σ} =^{*} Ψ^{X} = W_{e}$ .

Proof.

Let e be as in the previous claim. Let $Q_{i, σ} [t] = {n : \exists s ⩽ t n \in Ψ_{s}^{x_{s}}}$ . Each of these sets is finite, and $Q_{i, σ} = ⋃_{t} Q_{i, σ} [t]$ .

For every stage $t ⩾ s_{0}$ , if $n \in Q_{i, σ} [t] - Q_{i, σ} [t - 1]$ , then $n \in Ψ_{t}^{x_{t}}$ . Since $t ⩾ s_{0}$ , $x_{t} ≽ y$ . This shows that $n \in Ψ_{t}^{τ}$ for some $τ ≽ y$ . There is some 1-generic $G ≽ τ$ ; so $n \in Ψ^{G}$ ; by the previous claim, $Ψ^{G} = W_{e} = Ψ^{X}$ . So $Q_{i, σ} \subseteq^{*} Ψ^{X}$ .

On the other hand, if $n \in Ψ^{X}$ , there is some t such that $n \in Ψ_{t}^{x_{t}}$ . As $X = y ˆ Z$ is a 1-generic extending y, $Ψ^{X} = W_{e}$ . So $Ψ^{X} = W_{e} \subseteq Q_{i, σ}$ . □

We have shown that $Q_{i, σ} =^{*} Ψ^{X} = Φ^{X, [i]}$ for some 1-generic X extending σ. By the arguments given at the beginning of the proof, if we take the family ${Q_{i, σ} | i \in ω, σ \in 2^{< ω}}$ and close it under finite differences, we get an enumeration of $F$ . □

The next lemma gives another restriction on what a Slaman–Wehner family closed under finite differences would have to look like. Let A be a low set that enumerates such a family. Each set in the family has a computable enumeration, but also an enumeration relative to A as part of the enumeration of the family by A. We show that for at least one set in the family, the enumeration relative to A must be faster than any computable enumeration. Lemma 3.4.

Let A be a low set, and $F$ a family of c.e. sets closed under finite differences that can be enumerated by A using Φ. Suppose that for each i, for some e with $Φ^{A, [i]} = W_{e}$ we have $Φ_{s}^{A, [i]} \subseteq W_{e, s}$ for all s. Then $F$ can be computably enumerated.

Proof.

Let $π \in 2^{ω}$ be such that $π (e, i) = 1$ if and only if $(\forall n) (\forall s) n \in Φ_{s}^{A, [i]} \Rightarrow n \in W_{e, s}$ . Since A is low, $π ⩽ \emptyset^{'}$ . Let $σ_{s}$ be a computable sequence of finite binary strings that approximate π, and such that there are infinitely many true stages s with $σ_{s} ≺ π$ .

We will uniformly compute sets $U_{i} =^{*} Φ^{A, [i]}$ . Let $U_{i, s + 1} = U_{i, s} \cup [{0, \dots, s} ⋂_{σ_{s} (e, i) = 1} W_{e, s}]$ and let $U_{i} = ⋃ U_{i, s}$ . Fix a particular index $e^{'}$ such that $Φ^{A, [i]} = W_{e^{'}}$ and for all s we have $Φ_{s}^{A, [i]} \subseteq W_{e^{'}, s}$ . Let $s^{'}$ be a stage such that for all $s ⩾ s^{'}$ , $σ_{s} (e^{'}, i) = 1$ . Then for all $s ⩾ s^{'}$ , $U_{i, s + 1} - U_{i, s} \subseteq W_{e^{'}}$ and so $U_{i} \subseteq^{*} W_{e^{'}}$ . Now suppose that $n \in Φ_{s}^{A, [i]}$ , $s ⩾ s^{'}$ , and s is a true stage of the approximation $σ_{s}$ of π, so that $σ_{s} ≺ π$ . Then $n \in ⋂_{σ_{s} (e, i) = 1} W_{e, s}$ and so $n \in U_{i}$ . Thus $U_{i} =^{*} W_{e^{'}} = Φ^{A, [i]}$ . □

4. Examples of families

In this section, we produce the three examples of families of c.e. sets, closed under finite difference, that were promised in the introduction: (1) A family that can be enumerated exactly by the non-low degrees; (2) For any effective list of non-computable c.e. sets, a family that can be enumerated by those sets but not computably enumerated; and (3) For any non-computable $Δ_{2}^{0}$ set, a family that can be enumerated by that set but which cannot be computably enumerated. Recall that in all of these cases, our family consists of c.e. sets, so that in (3) for example we cannot simply take the family to consist solely of the given non-computable $Δ_{2}^{0}$ set.

We begin by adapting Wehner’s construction to produce a family of sets closed under finite differences that can be enumerated exactly by the non-low degrees. We can think of this as essentially a jump inversion of Wehner’s construction relativized to $0^{'}$ .

Theorem 1.6.

There is a family closed under finite differences that can be enumerated uniformly by every non-low degree, but which cannot be enumerated by any low degree.

Proof.

Following [8], relativizing Wehner’s construction of a family that can be enumerated by exactly the non-computable degrees, we get a family $\begin{matrix} F_{\emptyset^{'}} = {{e} \oplus F : e < ω, F \subseteq ω finite, and F \neq W_{e}^{\emptyset^{'}}} . \end{matrix}$ Then for $X ⩾_{T} \emptyset^{'}$ , X can enumerate $F$ if and only if $X >_{T} \emptyset^{'}$ . (See Propositions 2.3 and 2.4 of [8].)

Now, given a set S, define $\begin{matrix} U_{S} = {⟨ s, n ⟩ : s \notin S, n < ω} . \end{matrix}$ We have the following jump inversion result using $U_{S}$ : Lemma 4.2.

For finite sets S, we can uniformly pass between an X-index i for an enumeration of a set $W_{i}^{X} =^{*} U_{S}$ and an $X^{'}$ -index j for $W_{j}^{X^{'}} = S$ .

Proof.

Given $W_{i}^{X} =^{*} U_{S}$ , $X^{'}$ can enumerate S by, for each $s \in ω$ , searching for $n_{0}$ such that for all $n ⩾ n_{0}$ , $⟨ s, n ⟩ \notin W_{e}^{X}$ , and enumerating s if such an $n_{0}$ is found.

On the other hand, if $W_{j}^{X^{'}} = S$ , then S is $Σ_{2}^{0}$ relative to X. So we can find an X-computable function f such that if $s \in S$ , $W_{f (s)}^{X}$ is finite, and if $s \notin S$ , $W_{f (s)}^{X} = ω$ . Let $\begin{matrix} V = {⟨ s, n ⟩ : n \in W_{f (s)}} . \end{matrix}$ Since S is finite, $V =^{*} U_{S}$ . □

Define $\begin{matrix} G = {V : \exists S \in F_{\emptyset^{'}} [V =^{*} U_{S}]} . \end{matrix}$ We claim that $G$ is uniformly enumerable by all non-low degrees, and is not enumerable from any low degree.

If X is non-low, then $X^{'} >_{T} \emptyset^{'}$ . So $X^{'}$ uniformly enumerates $F_{\emptyset^{'}}$ , and by Lemma 4.2, X uniformly enumerates a family which, when we close under $=^{*}$ , will give us $G$ .

If X is low, then any enumeration of $G$ would give an $X^{'}$ -listing of $F_{\emptyset^{'}}$ , by Lemma 4.2, which is impossible. □

Next we consider an effective sequence of non-computable c.e. sets.

Theorem 1.7.

Given a uniformly c.e. sequence ${(D_{e})}_{e \in ω}$ of non-computable c.e. sets, there is a family of c.e. sets closed under finite differences that can be enumerated by every $D_{e}$ , but which cannot be enumerated computably.

Proof.

For each i, let $Q_{i}$ be a computable set of indices such that ${W_{k} : k \in Q_{i}}$ is the ith computable enumeration of a family of sets. When we construct our family $F$ , for each set in $F$ there will be some i such that the set has infinitely many elements of the form $⟨ i, \cdot ⟩$ and only finitely many elements of the form $⟨ j, \cdot ⟩$ for $j \neq i$ . We will diagonalize against the family ${W_{k} : k \in Q_{i}}$ using the sets containing only elements of the form $⟨ i, \cdot ⟩$ .

Let $P_{i}$ be a $Π_{1}^{0}$ set of indices for the c.e. sets ${n : ⟨ i, n ⟩ \in W_{k}}$ where $k \in Q_{i}$ and $W_{k}$ contains only elements of the form $⟨ i, n ⟩$ . The following lemma contains the heart of the argument: that we can diagonalize against this family. Lemma 4.4.

Given a $Π_{1}^{0}$ set $P \subseteq ω$ , there is a family of c.e. sets $F$ closed under finite differences such that $\begin{matrix} F \neq {W_{e} : e \in P} \end{matrix}$ and $F$ can be enumerated by every $D_{e}$ . Moreover, we can build $F$ uniformly from an index for P, and the enumeration of $F$ from the $D_{e}$ is uniform as well.

Before proving the lemma, we show how to use it to finish the theorem. For each i, let $F_{i}$ be the family of c.e. sets obtained by this lemma applied to $P_{i}$ . The families $F_{i}$ can be enumerated uniformly by every $D_{e}$ , and $F_{i} \neq {W_{k} : k \in P_{i}}$ . Now we need to combine each of these families into a single family $F$ ; let $F$ be the closure under taking finite differences of the family $\begin{matrix} {{⟨ i, n ⟩ : n \in W} : W \in F_{i}} . \end{matrix}$ Then $F$ can be enumerated by each $D_{e}$ , because $D_{e}$ can enumerate each $F_{i}$ uniformly. Also, we argue that $F$ is not the same as the ith computable enumeration ${W_{k} : k \in Q_{i}}$ . Note that $F_{i}$ is the family of all sets ${n : ⟨ i, n ⟩ \in W}$ for $W \in F$ containing only elements of the form $⟨ i, \cdot ⟩$ . Since $F_{i} \neq {W_{k} : k \in P_{i}}$ , and $P_{i}$ was obtained from $Q_{i}$ by the same process that $F_{i}$ is obtained from $F$ , $F \neq {W_{k} : k \in Q_{i}}$ . □

Now we prove Lemma 4.4. As one might expect, this is a c.e. permitting argument.

Proof of Lemma 4.4.

For each index e, we build a $D_{e}$ -enumeration of a family $F_{e}$ of c.e. sets. We will ensure that the families $F_{e}$ and $F_{e^{'}}$ enumerated by $D_{e}$ and $D_{e^{'}}$ are the same; we call this family $F$ . We will also make sure that $F$ is different from ${W_{e} : e \in P}$ . Though they will be the same family, the correspondence between the sets in $F_{e}$ and the sets in $F_{e^{'}}$ may not be computable, and this is why we give them different names.

First it will be helpful to think of what the construction does in the case of a single non-computable c.e. set $D_{e}$ . We will describe a restriction of the general strategy to this simpler case. The family $F_{e}$ will consist of a single set $U_{e}$ and its finite differences. We want to ensure that either $U_{e}$ is not in ${W_{k} : k \in P}$ , or that there is some set in ${W_{k} : k \in P}$ that is different from $U_{e}$ and all of its finite differences. What we will do is to consider each $W_{k}$ in turn, and try to make $U_{e}$ different from $W_{k}$ . We use the elements of the form $⟨ k, \cdot ⟩$ for the sake of $W_{k}$ .

For each k in turn, we do the following, beginning with $k = 0$ . We call this process the module for $W_{k}$ . Suppose that the module for $W_{k}$ begins at stage s. If $k \notin P_{s}$ , then we do not have to make $U_{e}$ different from $W_{k}$ , and we can just go on to $W_{k + 1}$ . Otherwise, if $k \in P_{s}$ , begin by putting $⟨ k, n ⟩$ into $U_{e}$ for each n, with use $D_{e, s} ↾ ↾ n$ where s is the current stage. At each later stage t, do one of the following:

If $k \notin P_{t}$ , then this means that we no longer have to make $U_{e}$ different from $W_{k}$ . We put $⟨ k, n ⟩$ into $U_{e}$ with no use, and go on to the module for $W_{k + 1}$ .

If there is some n that entered $D_{e}$ at stage t, and there is $m ⩾ n$ with $⟨ k, m ⟩ \in W_{k, t}$ , then we have received permission from $D_{e}$ to diagonalize against $W_{k}$ . For $n^{'} < n$ , put $⟨ k, n^{'} ⟩$ into $U_{e}$ with no use. On the other hand, because n has entered $D_{e}$ , we are able to remove $⟨ k, m ⟩$ from $U_{e}$ . So $U_{e} \neq W_{k}$ . We go on to the module for $W_{k + 1}$ .

Otherwise, it might be that $D_{e}$ has changed, but we have not been given an opportunity to diagonalize. Put $⟨ k, n ⟩$ into $U_{e}$ with use $D_{e, t} ↾ ↾ n$ and continue the module for $W_{k}$ at stage $t + 1$ .

If we end the module for

W_{k}

for any reason, then we have succeeded against

W_{k}

, either because

k \notin P

and we do not need to do anything, or because we have ensured that

U_{e} \neq W_{k}

. It is also possible that for some k, the module for

W_{k}

never ends. In this case, we will argue that

W_{k}

is not a finite difference of

U_{e}

. Suppose that it was; then

U_{e}

contains every element

⟨ k, n ⟩

, and so

W_{k}

must contain all but finitely many of those elements. But then by a standard permission argument, there must be some n that enters

D_{e}

at a stage t at which

⟨ k, m ⟩ \in W_{k, t}

for some

m ⩾ n

; otherwise, we would be able to compute

D_{e}

. This gives us a contradiction, because if this ever happened then the module for

W_{k}

would have been given permission.

We also need to make sure that the set $U_{e}$ is c.e. (and in fact computable). For each k, $U_{e}$ contains either finitely many elements $⟨ k, n ⟩$ , or every element $⟨ k, n ⟩$ . If the module for $W_{k}$ never ends, then $U_{e}$ is actually computable using the knowledge of how the modules for $W_{0}, \dots, W_{k}$ ended. Otherwise, each module ends; to decide which elements $⟨ k, n ⟩$ to put into $U_{e}$ , we can wait until the module for $W_{e}$ ends, at which point the construction fixes how many of those elements to put into $U_{e}$ .

Before returning to the general case, it will be helpful to show how we may assume that we can delete sets from our enumerations of the families $F_{e}$ . When we delete a set, we will delete its entire equivalence class under finite differences. We do this as follows. Reserve infinitely many elements $⟨ 0, n ⟩$ as garbage labels. Whenever we want to delete a set from the family $F_{e}$ , we put every label, including all of the garbage labels, into it; we also add all of these labels onto finite differences of the set, and add new sets to $F_{e}$ that are the finite differences of these sets. Since there are infinitely many garbage labels, each of these sets will still have infinitely many garbage labels. Instead of working with ${W_{e} : e \in P}$ , we work with $\begin{matrix} {W_{e} : e \in P and W_{e} does not contain any garbage labels} . \end{matrix}$ This is a still a $Π_{1}^{0}$ set of indices. If we can make the family of sets in $F$ not including a garbage label different from this family, then $F$ together with the deleted sets will be different from ${W_{e} : e \in P}$ . So for the rest of the construction, we will simply allow ourselves to delete sets from the families $F_{e}$ (without talking about garbage labels).

Now we return to the full sequence ${(D_{e})}_{e \in ω}$ . Now the main issue that arises is that the different sets $D_{e}$ might give us permission at different times, which would mean e.g. that $D_{e}$ would give us permission to remove $⟨ k, n ⟩$ from $U_{e}$ , but $D_{e^{'}}$ would not give us permission to remove $⟨ k, n ⟩$ from $U_{e^{'}}$ ; and then later $D_{e^{'}}$ would give us permission to remove some other $⟨ k, m ⟩$ from $U_{e^{'}}$ , but $D_{e}$ would not give use permission to remove it from $U_{e}$ .

The solution to this is to take advantage of the fact that $U_{e}$ and $U_{e^{'}}$ do not have to be the same set, as long as there is some other set in $F_{e}$ that is equal to $U_{e^{'}}$ , and some other set in $F_{e^{'}}$ that is equal to $U_{e}$ . Moreover, which set this is does not have to be fixed. Just before the start of the module for $W_{k}$ , each $F_{e}$ will consist only of the set $U_{e}$ (and of course, its finite differences), and we will have $U_{e} = U_{e^{'}}$ for each e, $e^{'}$ . At the start of the module for $W_{k}$ , we will add new sets $V_{e}^{e^{'}}$ to $F_{e}$ with the intent of copying $U_{e^{'}}$ .

Note that the subscripts of the sets denote which family they belong to, and the superscripts denote the set they are copying. We use the elements $⟨ k, e, n ⟩$ for $U_{e}$ in the module for $W_{k}$ . When $D_{e}$ gives permission to make $U_{e} \neq W_{k}$ by removing an element $⟨ k, e, n ⟩$ from $U_{e}$ , this element was never put in $U_{e^{'}}$ for $e^{'} \neq e$ ; so we can delete all of the sets V and make $U_{e} = U_{e^{'}}$ again for each e, $e^{'}$ . So if each module ends, then we end up with $U_{e} = U_{e^{'}}$ ; but if the module for $W_{k}$ never ends, then we have $U_{e} \neq U_{e^{'}}$ for each e, $e^{'}$ , but $V_{e^{'}}^{e} = U_{e}$ .

For a particular value of k, we act against $W_{k}$ using the following module. Assume that at each stage only a single element enters exactly one of $D_{0}, D_{1}, \dots$ . At the start of the module, each $F_{e}$ will consist of only a single set $U_{e}$ (plus its finite differences); the sets $U_{e}$ will contain exactly the same elements, and will contain only elements of the form $⟨ k^{'}, \cdot, \cdot ⟩$ for $k^{'} < k$ .

We will describe below the module for $W_{k}$ as it builds each $F_{e}$ . The events that trigger the beginning and ending of each module will be computable. The modules will build the families $F_{e}$ as c.e. operators, the $e th$ one with oracle $D_{e}$ , describing elements enumerated into sets in the families with various uses.

Module for $W_{k}$ :

Suppose that the module for $W_{k}$ begins at stage s. As described, at stage s, each $F_{e}$ consists of a set $U_{e}$ (and its finite differences). We begin the module by adding to each family $F_{e}$ infinitely many sets $V_{e}^{e^{'}}$ , all equal to the $U_{e}$ ’s, again with no use.

Now let $t ⩾ s$ be a stage, and suppose that the module for $W_{k}$ is still running at stage t. We do the following:

If $k \notin P_{t}$ :

delete all the sets $V_{e}^{e^{'}}$ from all the families $F_{e}$ ;

with no use, put $⟨ k, e^{'}, n ⟩$ into $U_{e}$ for each n and $e^{'}$ (including $e^{'} = e$ );

end the module.

Otherwise, suppose that some $n^{*}$ enters a set $D_{e^{*}}$ at stage t (recall there will be only one such pair $(n^{*}, e^{*})$ at each stage), and there is $m ⩾ n^{*}$ with $⟨ k, e^{*}, m ⟩ \in W_{k, t}$ :

delete all the sets $V_{e}^{e^{'}}$ from all the families $F_{e}$ ;

for every $e^{'} \neq e^{*}$ , every e and every n, put $⟨ k, e^{'}, n ⟩$ into $U_{e}$ with no use;

for every $n < n^{*}$ and every e, put $⟨ k, e^{*}, n ⟩$ into each $U_{e}$ with no use;

end the module.

Otherwise, for each e and n, put $⟨ k, e, n ⟩$ into $U_{e}$ with use $D_{e, t} ↾ ↾ n$ . Continue the module.

The complete construction piecing together the modules is as follows:

Construction: Run the module for $W_{0}$ ; if it returns, run the module for $W_{1}$ , and when that returns run the module for $W_{2}$ , and so on.

Now we must check that the construction works. We make a few remarks about the state of the construction whenever a module finishes. At the end of any module:

each $F_{e}$ consists of only the set $U_{e}$ (and finite differences);

every element in $U_{e}$ is in $U_{e}$ with no use;

$U_{e} = U_{e^{'}}$ for each e, $e^{'}$ .

Claim 1.

For each e, $e^{'}$ , $F_{e}$ and $F_{e^{'}}$ are the same family $F$ .

Proof.

Suppose first that each module ends. Then by the remark above, each $F_{e}$ consists of only of the finite differences of a single set $U_{e}$ , and $U_{e} = U_{e^{'}}$ for each e, $e^{'}$ .

So now suppose that the module for $W_{k}$ does not end. Then each $F_{e}$ will consist of a set $U_{e}$ and sets $V_{e}^{e^{'}}$ for $e^{'} \neq e$ , and all the finite differences. Moreover, after the beginning of the module no elements are ever removed from $U_{e^{'}}$ (since, if an element would be removed by a change in $D_{e^{'}}$ , it is added back into $U_{e^{'}}$ with the new use). So we have $V_{e}^{e^{'}} = U_{e^{'}}$ . Thus the families $F_{e}$ are all the same. □

Claim 2.

$F \neq {W_{k} : k \in P}$ .

Proof.

We have two cases. First suppose that each module ends. Then $F$ will consist of the equivalence class of a single set U (with $U = U_{e}$ for each e). We claim that $U \neq W_{k}$ for any $k \in P$ , so that $U \notin {W_{k} : k \in P}$ . Indeed, for each k, the module for $W_{k}$ ends, either because we find that $k \notin P$ , or because there is n that enters $D_{e}$ at a stage t, and there is $m ⩾ n$ with $⟨ k, e, m ⟩ \in W_{k, t}$ . In the latter case, $⟨ k, e, m ⟩ \in W_{k}$ but we remove $⟨ k, e, m ⟩$ from U; so $W_{k} \neq U$ .

Now suppose that the module for $W_{k}$ does not end. Then we claim that $W_{k} \notin F$ . The family $F$ consists of the sets $U_{e}$ and their finite differences; each $U_{e}$ contains the elements $⟨ k, e, n ⟩$ for all n while not containing $⟨ k, e^{'}, n ⟩$ for any $e^{'} \neq e$ . Suppose to the contrary that $W_{k} \in F$ , so that for some e, $W_{k} =^{*} U_{e}$ . Then choose N such that for all $n ⩾ N$ , $⟨ k, e, n ⟩ \in W_{k}$ . Since the module for $W_{k}$ does not end, whenever n enters $D_{e}$ at a stage t, there is no $m ⩾ n$ with $⟨ k, e, m ⟩ \in W_{k, t}$ . Thus $D_{e} ↾ ↾_{n} = D_{e, t} ↾ ↾ n$ if there is $m ⩾ n$ with $⟨ k, e, m ⟩ \in W_{k, t}$ . This allows us to compute the non-computable set $D_{e}$ . From this contradiction we can conclude that $W_{k} \notin F$ . □

This completes the proof of the lemma. □

It would be natural to try to extend this argument to all of the non-computable c.e. sets by showing that for any list ${(D_{e})}_{e \in ω}$ of c.e. sets, some of which might be computable, there is a family $F$ of c.e. sets closed under finite differences which has no computable enumeration, but has an enumeration from any non-computable $D_{e}$ . The problem we run into is that during the module for $W_{k}$ , $W_{k}$ could copy $U_{e}$ for some e with $D_{e}$ non-computable, so that we are never given permission. One would then have to add a guessing argument to guess at when $D_{e}$ is non-computable, but we could not make this work with the sets $V_{e}^{e^{'}}$ . We leave this question open:

Question 4.5.

If $F$ is a family of c.e. sets closed under finite differences, and it can be enumerated by every non-computable c.e. set, must it have a computable enumeration?

One way to show that there is no Slaman–Wehner family closed under finite differences would be to show that there is a degree d such that any family of c.e. sets closed under finite differences that can be enumerated by d has a computable enumeration. We show that this is not the case. We already know that such a family exists for any non-low degree, and now we show that such a family exists for any $Δ_{2}^{0}$ degree. Note that if we do not require the family to consist of c.e. sets, then it is not hard to construct such a family; so this is the main difficulty.

Theorem 1.8.

For any non-computable $Δ_{2}^{0}$ set X, there is a family of c.e. sets closed under finite differences that can be X-computably enumerated, but which cannot be enumerated computably.

Proof.

Let D be $Δ_{2}^{0}$ but not computable. The following lemma will give us a strategy for diagonalizing against a single set: Lemma 4.7.

There is, uniformly in e, a set $U_{e}^{D}$ that is c.e. with $U_{e}^{D} \neq^{*} W_{e}$ . That is, there is a total computable function h such that $W_{h (e)}^{D} \neq^{*} W_{e}$ for each e.

Before proving the lemma, we show how to use it to prove the theorem. Let ${W_{f (n, i)}}_{i \in ω}$ be an enumeration of the nth computably enumerable family of sets. Let $W_{g (n, i)} = {x : ⟨ 1, i, x ⟩ \in W_{f (n, i)}}$ . Let $F$ consist of, for each n, the set $A_{n}$ defined as follows, together with all finite differences. Let $i_{0}, i_{1}, \dots$ be an enumeration of the indices i for sets $W_{f (n, i)}$ that contain an element of the form $⟨ 0, n, m ⟩$ for some m. The set $A_{n}$ contains:

$⟨ 0, n, m ⟩$ for each $m \in ω$ ;

$⟨ 1, i_{ℓ}, x ⟩$ for $x \in U_{g (n, i_{ℓ})}^{D}$ , if $W_{f (n, i_{0})}, \dots, W_{f (n, i_{ℓ - 1})}$ all contain an element of the form $⟨ 0, n^{'}, m ⟩$ , $n^{'} \neq n$ .

$⟨ 1, i, x ⟩$ for each $x \in ω$ if $W_{f (n, i)}$ contains an element of the form $⟨ 0, n^{'}, m ⟩$ , $n^{'} \neq n$ .

Think of the elements

⟨ 0, n, m ⟩

as coding into

A_{n}

the value of n. Thus the indices

i_{0}, i_{1}, \dots

are an enumeration of the sets

W_{f (n, \cdot)}

that might be equal to

A_{n}

. The set

A_{n}

will diagonalize against the nth computably enumerable family of sets

{W_{f (n, i)} : i \in ω}

using the elements

⟨ 1, \cdot, \cdot ⟩

, and in particular it will diagonalize against

W_{f (n, i)}

using the elements

⟨ 1, i, \cdot ⟩

. If

W_{f (n, i)}

contains an element

⟨ 0, n^{'}, m ⟩

for some m, and

n^{'} \neq n

, then it cannot be

A_{n}

; so as in (3) we do not need to diagonalize against it. In (2), we find the least

W_{f (n, i)}

that might be

A_{n}

, and we use Lemma 4.7 to diagonalize against it. The function g strips off this first two entries of the elements

⟨ 1, i, \cdot ⟩

that we use to diagonalize. It is important to note that everything put into

A_{n}

for (2) is also put into

A_{n}

for (3); this is important as it is possible for the conditions for both (2) and (3) to be true.

It is clear that D can enumerate $F$ . We will show that the nth computably enumerable family is different from $F$ . Suppose that the nth computably enumerable family were equal to $F$ . Then there is some least ℓ such that $W_{f (n, i_{ℓ})} =^{*} A_{n}$ and such that $W_{f (n, i_{ℓ})}$ does not contain an element of the form $⟨ 0, n^{'}, m ⟩$ for $n^{'} \neq n$ . For each $k < ℓ$ such that $W_{f (n, i_{k})} \neq^{*} A_{n}$ , $W_{f (n, i_{k})} =^{*} A_{n^{'}}$ for some $n^{'} \neq n$ , and so it contains an element of the form $⟨ 0, n^{'}, m ⟩$ . Thus for every $k < ℓ$ , $W_{f (n, i_{k})}$ contains an element of the form $⟨ 0, n^{'}, m ⟩$ . Then $\begin{matrix} W_{g (n, i_{ℓ})} = {x : ⟨ 1, i_{ℓ}, x ⟩ \in W_{f (n, i_{ℓ})}} =^{*} {x : ⟨ 1, i_{ℓ}, x ⟩ \in A_{n}} = U_{g (n, i_{ℓ})}^{D} . \end{matrix}$ But $W_{g (n, i)} \neq^{*} U_{g (n, i)}^{D}$ , so this is a contradiction. Thus we have shown that $F$ cannot be computably enumerated.

We must also check that each $A_{n}$ is c.e. This is because we can non-uniformly know the least index $i_{ℓ}$ , if it exists, such that $W_{f (n, i_{0})}, \dots, W_{f (n, i_{ℓ - 1})}$ all contain elements of the form $⟨ 0, n^{'}, m ⟩$ for $n^{'} \neq n$ . For each $k^{'} < ℓ$ , any element enumerated by (2) is also enumerated by (3), and so $A_{n}$ consists of:

$⟨ 0, n, m ⟩$ for each $m \in ω$ ;

$⟨ 1, i_{ℓ}, x ⟩$ for $x \in U_{g (n, i_{ℓ})}^{D}$ ;

$⟨ 1, i, x ⟩$ for each $x \in ω$ if $W_{f (n, i)}$ contains an element of the form $⟨ 0, n^{'}, m ⟩$ , $n^{'} \neq n$ .

This is c.e. as

U_{g (n, i_{ℓ})}^{D}

is c.e. □

We now return to the proof of Lemma 4.7. We begin by discussing our strategy informally before giving the formal proof. Uniformly in e, we need to define $U_{e}^{D} \neq^{*} W_{e}$ . One can think of the construction as trying to define $\begin{matrix} U_{e}^{D} = {⟨ k, D (k), n ⟩ : k, n \in ω} \end{matrix}$ where $D (k) = 0$ or $D (k) = 1$ . This can easily be enumerated by D, and it is not equal to $W_{e}$ because any enumeration of $U_{e}^{D}$ can compute D. But $U_{e}^{D}$ is not c.e. We need to make $U_{e}^{D}$ c.e., but of course it cannot be c.e. uniformly in e.

It will be helpful to think of the c.e. set $W_{e}$ trying to copy the set ${⟨ k, D (k), n ⟩ : k, n \in ω}$ using the computable approximation $D_{s}$ , while we as the builders of $U_{e}^{D}$ are trying to come up with infinitely many differences between $W_{e}$ and $U_{e}^{D}$ . The two most extreme strategies that $W_{e}$ might take (neither of which will work of course) can be thought of as the greedy strategy and the cautious strategy. The greedy strategy computes, at each stage s, $D_{s} (k)$ , and puts $⟨ k, D_{s} (k), t ⟩$ , $t < s$ , into W. Then $W_{e}$ will include all of the elements $⟨ k, D (k), n ⟩$ , but it will also contain some elements $⟨ k, 1 - D (k), n ⟩$ . The cautious strategy never enumerates any elements into $W_{e}$ , because it can never be sure that $D_{s} (k)$ has stabilized.

Think of $W_{e}$ as choosing a different one of these strategy for each k; so for example it might be greedy for $k = 0$ , cautious for $k = 1$ , etc. (Of course $W_{e}$ might take some other strategy, but in some sense the cautious and greedy strategies are prototypical and we can consider those other strategies later.)

If $W_{e}$ chooses the cautious strategy for some least k, then we already have infinitely many differences between $W_{e}$ and $U_{e}^{D}$ using only the elements $⟨ k, \cdot, \cdot ⟩$ , because $W_{e}$ contains none of these elements and $U_{e}^{D}$ will contain all of the elements $⟨ k, D (k), \cdot ⟩$ . So we do not need to add to $U_{e}^{D}$ any elements $⟨ k^{'}, \cdot, \cdot ⟩$ for $k^{'} > k$ , and in fact we will keep all such elements out of $U_{e}^{D}$ . Then, non-uniformly knowing the values of $D (0), \dots, D (k)$ , we will be able to enumerate $U_{e}^{D}$ .

Otherwise, suppose that $W_{e}$ takes the greedy strategy for every k. Then we need to make sure that there are infinitely many elements $⟨ k, i, n ⟩ \in W_{e} - U_{e}^{D}$ . In this case, we will have $\begin{matrix} U_{e}^{D} = {⟨ k, D (k), n ⟩ : k, n \in ω} \cup V \end{matrix}$ where V is a c.e. set that also follows the greedy strategy for every k, but it will do so slower than $W_{e}$ does. What we mean by this is that, for example, $⟨ k, 0, 0 ⟩$ will not be enumerated into V until $⟨ k, 0, 1 ⟩$ is enumerated into $W_{e}$ , and only if $D_{s} (k)$ is still equal to 0, and $⟨ k, 0, 1 ⟩$ will not be enumerated into V until $⟨ k, 0, 2 ⟩$ is enumerated into $W_{e}$ , and so on; thus if in fact $D (k) = 1$ , then $W_{e}$ will still have made a mistake by containing at least one element $⟨ k, 0, n ⟩$ that is not in V. (Since V follows the greedy strategy, in fact it will contain ${⟨ k, D (k), n ⟩ : k, n \in ω}$ ; and it will contain only finitely many elements $⟨ k, 1 - D (k), n ⟩$ .)

Of course we have to be able to combine all of this, as well as defeating any other strategy $W_{e}$ might take. But this will be the guiding idea behind our construction of $U_{e}^{D}$ .

Proof of Lemma 4.7.

Let $D_{s}$ be a $Δ_{2}^{0}$ approximation to D. For each k, define $U_{e, k}^{D}$ as follows:

Enumerate $⟨ k, 0, n ⟩$ into $U_{e, k}^{D}$ if $D (k) = 0$ , and enumerate $⟨ k, 1, n ⟩$ into $U_{e, k}^{D}$ if $D (k) = 1$ .

If $⟨ k, 0, n ⟩$ is in $W_{e, s}$ and $D_{s} (k) = 0$ , enumerate $⟨ k, 0, 0 ⟩, \dots, ⟨ k, 0, n - 1 ⟩$ into $U_{e, k}^{D}$ .

If $⟨ k, 1, n ⟩$ is in $W_{e, s}$ and $D_{s} (k) = 1$ , enumerate $⟨ k, 1, 0 ⟩, \dots, ⟨ k, 1, n - 1 ⟩$ into $U_{e, k}^{D}$ .

This process is not uniformly computable in k because of (1), which requires the oracle D; but (2) and (3) enumerate elements computably. (2) and (3) are following the greedy strategy described above, but slower than

W_{e}

. If

D (k) = 0

, then

U_{e, k}^{D}

contains all of the elements

⟨ k, 0, n ⟩

and only finitely many elements

⟨ k, 1, n ⟩

; and if

D (k) = 1

, then

U_{e, k}^{D}

contains all of the elements

⟨ k, 1, n ⟩

and only finitely many elements

⟨ k, 0, n ⟩

Now we need to put the sets $U_{e, k}^{D}$ together into a single set $U_{e}^{D}$ . Recall that if $W_{e}$ follows the cautious strategy for k, then we do not want to put any elements $⟨ k^{'}, \cdot, \cdot ⟩$ into $U_{e}^{D}$ for $k^{'} > k$ ; so we do not want to put $U_{e, k^{'}}^{D}$ into $U_{e}^{D}$ . Define $agreement (k, s)$ to be ∞ if $k = 0$ , and otherwise it is the greatest $ℓ ⩽ s$ such that for $k^{'} < k$ , if $D_{s} (k^{'}) = 0$ then $W_{e, s}$ contains ℓ elements of the form $⟨ k, 0, n ⟩$ ; and if $D_{s} (k^{'}) = 1$ then $W_{e, s}$ contains ℓ elements of the form $⟨ k, 1, n ⟩$ . Let $\begin{matrix} U_{e}^{D} = ⋃_{k, s} U_{e, k}^{D} ↾_{agreement (k, s) - k} . \end{matrix}$ (If $k ⩾ agreement (k, s)$ then take $U_{e, k}^{D} ↾_{agreement (k, s) - k}$ to be empty.) Note that for a fixed s, $agreement (k, s)$ is decreasing in k, and that for each fixed k it will converge to a limit (which might be ∞) as $s \to \infty$ . So if ${lim}_{s \to \infty} agreement (k^{*}, s) < \infty$ for some $k^{*}$ , then $\begin{matrix} ⋃_{k ⩾ k^{*}, s} U_{e, k}^{D} ↾_{agreement (k, s) - k} \end{matrix}$ will be finite. One should think of the agreement function as measuring the extent to which $W_{e}$ is following a greedy strategy by actually enumerating elements. The agreement function is computable. Claim 1.

$U_{e}^{D}$ is c.e.

Proof.

Let $A_{k}$ be the c.e. set defined by (2) and (3), namely:

Whenever $⟨ k, 0, n ⟩$ enters $W_{e, s}$ and $D_{s} (k) = 0$ , enumerate $⟨ k, 0, 0 ⟩, \dots, ⟨ k, 0, n - 1 ⟩$ in $A_{k}$ .

Whenever $⟨ k, 1, n ⟩$ enters $W_{e, s}$ and $D_{s} (k) = 1$ , enumerate $⟨ k, 1, 0 ⟩, \dots, ⟨ k, 1, n - 1 ⟩$ in $A_{k}$ .

Let

\begin{matrix} A = ⋃_{k, s} A_{k} ↾_{agreement (k, s) - k} . \end{matrix}

One possibility is that

U_{e}^{D} = A

, so that

U_{e}^{D}

is c.e. since A is c.e. (Think of this as being when

W_{e}

follows a greedy strategy for every k.)

Now suppose otherwise. It is clear that $A \subseteq U_{e}^{D}$ . So suppose that there is an element $⟨ k, i, n ⟩ \in U_{e}^{D}$ with $⟨ k, i, n ⟩ \notin A$ ; thus $⟨ k, i, n ⟩ \notin A_{k}$ . We will show that $U_{e}^{D}$ is c.e. in this case as well. Choose such a $⟨ k^{*}, i, n ⟩$ with $k^{*}$ minimal. It must be that $⟨ k^{*}, i, n ⟩ \in U_{e}^{D}$ due to (1), namely that $D (k^{*}) = i$ . For sufficiently large stages s, $D_{s} (k^{*}) = i$ . Since $⟨ k^{*}, i, n ⟩ \notin A_{k}$ , there is no $⟨ k^{*}, i, m ⟩ \in W_{e}$ with $m > n$ . (Think of this as meaning that $W_{e}$ was following a cautious strategy for $k^{*}$ .) So for every $k > k^{*}$ , $agreement (k, s) ⩽ n$ . Thus $\begin{matrix} U_{e}^{D} = ⋃_{k, s} U_{e, k}^{D} ↾_{agreement (k, s) - k} =^{*} ⋃_{k < k^{*}, s} U_{e, k}^{D} ↾_{agreement (k, s) - k} . \end{matrix}$ Each $U_{e, k}^{D}$ is c.e., but not uniformly over k; one must know the value of $D (k)$ . So $U_{e}^{D}$ is a finite difference of a finite union of c.e. sets, hence c.e. □

Claim 2.

If D is non-computable, then $U_{e}^{D} \neq^{*} W_{e}$ .

Proof.

Suppose to the contrary that $U_{e}^{D} =^{*} W_{e}$ . We argue by induction on k that for each k, ${lim}_{s \to \infty} agreement (k, s) = \infty$ . For $k = 0$ , $agreement (k, s) = \infty$ by definition. Now suppose that ${lim}_{s \to \infty} agreement (k^{'}, s) = \infty$ for $k^{'} < k$ . Then for $k^{'} < k$ , $U_{e, k^{'}}^{D} \subseteq U_{e}^{D}$ , and so $U_{e, k^{'}}^{D} \subseteq^{*} W_{e}$ . If $D (k^{'}) = 0$ , then $U_{e, k^{'}}^{D}$ contains $⟨ k^{'}, 0, n ⟩$ for each n, and so $W_{e}$ contains infinitely many such elements; and from some stage $s_{k^{'}}$ on, $D_{s} (k^{'}) = 0$ . Similarly, if $D (k^{'}) = 1$ , then $U_{e, k^{'}}^{D}$ contains $⟨ k^{'}, 1, n ⟩$ for each n, and so $W_{e}$ contains infinitely many such elements; and from some stage $s_{k^{'}}$ on, $D_{s} (k^{'}) = 1$ . It follows that ${lim}_{s \to \infty} agreement (k, s) = \infty$ . So $\begin{matrix} U_{e}^{D} = ⋃_{k} U_{e, k}^{D} . \end{matrix}$ Note that every element in $U_{e, k}^{D}$ has the form $⟨ k, i, n ⟩$ , so it is easy to break $U_{e}^{D}$ up into the union $U_{e, k}^{D}$ .

Now for each k, wait for some element $⟨ k, i, n ⟩$ to enter $W_{e}$ . Define $C (k) = i$ where $⟨ k, i, n ⟩$ is the first such element to enter $W_{e}$ . Note that C is computable and defined on every input. We will argue that $C =^{*} D$ , showing that D is computable. In particular, we will argue that if $C (k) \neq D (k)$ , then there is an element $⟨ k, i, n ⟩ \in W_{e} - U_{e, k}^{D}$ . Since $W_{e} =^{*} U_{e}^{D}$ there can only be finitely many such elements.

If $C (k) \neq D (k)$ , then there is $⟨ k, i, n ⟩ \in W_{e}$ with $i \neq D (k)$ . Now as $i \neq D (k)$ , $⟨ k, i, n ⟩$ cannot have been enumerated into $U_{e, k}^{D}$ by (1). So it must have been enumerated by (2) or (3). There are at most finitely many stages s at which $D_{s} (k) = i$ , and at every such stage s there is some element $⟨ k, i, m ⟩$ in $W_{e, s}$ (namely, the largest such element) that is not enumerated into $U_{e, k}^{D}$ . So there is some such element $⟨ k, i, m ⟩ \in W_{e} - U_{e, k}^{D}$ . □

These claims complete the proof of the lemma. □

Footnotes

Acknowledgements

We thank Uri Andrews, Steffen Lempp, Noah Schweber, and Mariya Soskova for helpful discussions. Greenberg and Turetsky were partially supported by a Marsden Fund grant #17-VUW-090. Harrison-Trainor was partially supported by an NSERC Banting postdoctoral fellowship.

References

C.J.

Ash and

Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol. 144, North-Holland Publishing Co., Amsterdam, 2000, p. 346. ISBN 0-444-50072-3.

de Leeuw,

E.F.

Moore,

C.E.

Shannon and

Shapiro, Computability by probabilistic machines, in: Automata Studies, Annals of Mathematics Studies, Vol. 34, Princeton University Press, Princeton, N.J., 1956, pp. 183–212.

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010, p. 855. ISBN 978-0-387-95567-4. doi:10.1007/978-0-387-68441-3.

Faizrahmanov and

Kalimullin, Limitwise monotonic sets of reals, MLQ Math. Log. Q. 61(3) (2015), 224–229, ISSN 0942-5616. doi:10.1002/malq.201400015.

R.M.

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

S.S.

Gončarov, Computable univalent numerations, Algebra i Logika 19(5) (1980), 507–551617, ISSN 0373-9252.

S.S.

Gončarov, The problem of the number of nonautoequivalent constructivizations, Algebra i Logika 19(6) (1980), 621–639745, ISSN 0373-9252.

Greenberg,

Montalbán and

T.A.

Slaman, Relative to any non-hyperarithmetic set, J. Math. Log. 13(1) (2013), 1250007, ISSN 0219-0613. doi:10.1142/S0219061312500079.

B.M.

Khoussainov, Strongly effective unars and nonautoequivalent constructivizations, in: Some Problems in Differential Equations and Discrete Mathematics, Novosibirsk. Gos. Univ., Novosibirsk, 1986, pp. 33–44, (Russian).

10.

A.H.

Lachlan, On recursive enumeration without repetition, Z. Math. Logik Grundlagen Math. 11 (1965), 209–220. doi:10.1002/malq.19650110305.

11.

A.H.

Lachlan, A correction to: “On recursive enumeration without repetition”, Z. Math. Logik Grundlagen Math. 13 (1967), 99–100. doi:10.1002/malq.19670130703.

12.

A.I.

Mal’cev, Positive and negative enumerations, Dokl. Akad. Nauk SSSR 160 (1965), 278–280, ISSN 0002-3264.

13.

T.A.

Slaman, Relative to any nonrecursive set, Proc. Amer. Math. Soc. 126(7) (1998), 2117–2122, ISSN 0002-9939. doi:10.1090/S0002-9939-98-04307-X.

14.

R.I.

Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987, p. 437. ISBN 3-540-15299-7. doi:10.1007/978-3-662-02460-7.

15.

Stillwell, Decidability of the “almost all” theory of degrees, J. Symbolic Logic 37 (1972), 501–506, ISSN 0022-4812. doi:10.2307/2272735.

16.

Wehner, The index set of injectively enumerable classes of recursively enumerable sets is

Σ_{5}

-complete, Math. Logic Quart. 40(1) (1994), 87–94, ISSN 0942-5616. doi:10.1002/malq.19940400112.

17.

Wehner, Enumerations, countable structures and Turing degrees, Proc. Amer. Math. Soc. 126(7) (1998), 2131–2139, ISSN 0002-9939. doi:10.1090/S0002-9939-98-04314-7.

18.

C.E.M.

Yates, On the degrees of index sets. II, Trans. Amer. Math. Soc. 135 (1969), 249–266, ISSN 0002-9947. doi:10.2307/1995015.

Enumerations of families closed under finite differences

Abstract

Keywords

1. Introduction

Theorem 2.1 (Lachlan [10,11]).

1 In fact, a result of de Leeuw, Moore, Shannon, and Shapiro says no non-c.e. set can be enumerated even by a positive measure of sets [2], see Theorem 8.12.1 of [3].

Footnotes

Acknowledgements

References

¹
In fact, a result of de Leeuw, Moore, Shannon, and Shapiro says no non-c.e. set can be enumerated even by a positive measure of sets [2], see Theorem 8.12.1 of [3].