Confused about Cooper's book's proof of Selman's theorem on enumeration reducibility

Question

Here is an excerpt of Barry Cooper's book Computability Theory (2004), bottom half of page 179, which is short enough that I can copy it verbatim:

THEOREM 11.1.13 (Selman's Theorem, 1971) For any $A,B\subseteq\mathbb{N}$ $$A \mathrel{\leq_e} B \;\Longleftrightarrow\; \forall X[B\text{ c.e. in }X \Rightarrow A\text{ c.e. in }X]$$

PROOF (sketch) The left-to-right implication I will leave to you.

Conversely, assume that $A \mathrel{\not\leq_e} B$. We will construct a $C = \bigcup_{s\geq 0} C _ s$ such that $B$ is c.e. in $C$ but $A$ is not c.e., in $C$.

We satisfy “$B$ c.e. in $C$” by imposing an overall requirement $$\exists\langle x,y\rangle\in C \;\Longleftrightarrow\; x\in B \tag{11.1}$$ for each $x\geq 0$. Call a finite $D\supseteq C_s$ admissible if it satisfies Equation (11.1) with $D$ in place of $C$, but with the right-to-left half of Equation (11.1) restricted to $x\leq s$ (so that the admissible $D$'s can be enumerated from an enumeration of $B$ and a finite amount of information about $\overline{B}$).

We satisfy $A\neq W_s^C$ (at stage $s+1$) by looking for some admissible $D\supseteq C_s$ with $x \in W_s^D - A$. If $D$ exists, choose $C_{s+1} = D$ giving $A \neq W_s^C$. Otherwise, either $x\in A - W_s^D$ for some $x$, all admissible $D$ (so $A\neq W_s^C$ again), or $$\forall x(x\in A \;\Longleftrightarrow\; \exists\text{ an admissible }D\text{ such that }x\in W_s^D),$$ giving $A \mathrel{\not\leq_e} B$, a contradiction. ∎

Notation is mostly standard:

• $A \mathrel{\leq_e} B$ stands for enumeration reductibility, i.e., this means “there exists a computably enumerable set $U$ such that ($\forall n$) we have $n\in A$ iff $\exists D\text{ finite}\subseteq B$ such that $\langle n,D\rangle \in U$”;

• $W_e^X = \operatorname{dom}\Phi_e^X$ is the $e$-th set computably enumerable in $X$, where $\Phi_e^X$ stands for the $e$-th Turing machine with oracle the characteristic function of $X$; and “$A$ is c.e. in $X$” means there is $e$ such that $A = W_e^X$;

• and of course, $\langle,\rangle$ is a coding of pairs by natural numbers.

Now I understand the idea of the proof: we contruct $C$ in stages in such a way that the $s$-th stage ensures $B$ is its first projection up to $s$, and that $A$ does is not $W_s^C$.

But here's what I do not understand: why does $A\neq W_s^D$ ensure $A\neq W_s^C$? or more precisely, why does the construction of (the finite set) $D$ at stage $s$ ensure that we will have $A\neq W_s^C$ in the end?

My problem is that the Turing machine with oracle $\Phi_s^Z$, might have made some queries of the form “$k\in Z$?” which were responded negatively by the oracle when $Z=D$, but which get a positive answer when given $Z=C$ as oracle since the elements $k$ in question might be added at later stages of the construction of $C$. That is, the construction in the proof seems to record only positive information about $C$ (needed to satisfy the constraints), but no negative information (“we shouldn't add this element as it would change the elements of the $W_s^C$”), and I don't understand how this can work.

It almost seems like the proof is assuming that $X\subseteq Y$ implies $W_s^X \subseteq W_s^Y$ (which, unless I'm out of my mind, is completely wrong): this would make sense to me if we were to replace $W_s^X$ by the set of $n$ such that $\exists D\text{ finite}\subseteq X$ such that $\langle n,D\rangle \in W_s$, as in the definition of enumeration reducibility… but this is not what it is about. So I'm confused.

Can someone explain to me what I'm missing?

Answer 1

Here is how I think about it.

$A$ is enumeration reducible to $B$ means that there is an algorithm that with any enumeration of $B$ as oracle will produce an enumeration of $A$.

It is clear in this case that if $B$ is c.e. in some oracle $X$, then from $X$ we can produce an enumeration of $B$, from which we can produce an enumeration of $A$, so $A$ also is c.e. in $X$.

Conversely, suppose that $A$ is not enumeration reducible to $B$. We shall aim to produce a specific enumeration of $B$ in which $A$ is not c.e. We shall specify the enumeration in stages. At stage $s$ we have so far a finite enumeration $b_s$ of elements of $B$. Since the $s$th program $e_s$ is not an enumeration reduction of $A$ to $B$, this means either (1) we can extend $b_s$ to some $b_{s+1}$ with additional elements of $B$ in such a way that $e_s$ with that oracle produces a nonmember of $A$, or (2) there is some $a\in A$ such that all extensions of $b_s$ enumerating $B$ will fail to support a computation with $e_s$ adding $a$. (If both of these fail, then we can produce an enumeration reduction of $A$ to $B$ by waiting for $b_s$ to appear and then using $e_s$.) In either case, we may commit to a further $b_{s+1}$ that kills off $e_s$ as an enumeration of $A$ from the resulting enumeration of $B$. And we can also ensure that any given element of $B$ is added afterward before continuing with the next stage.

So this produces an enumeration of $B$ in which $A$ is not c.e. But $B$ is, so we're done.

It seems to follow from the argument that although enumeration reducibility is a uniform notion, a single program enumerates $A$ given any enumeration of $B$, in fact it is equivalent to the non-uniform version: $A$ is c.e. in every enumeration of $B$.

Answer 2

I think the proof is correct, but there are lots of missing details, and gosh it is hard to decipher. Here's my version in more concrete terms.

Definition: An enumeration-to-computation reduction from 𝐴 to 𝐵 is a Turing machine with oracle 𝐵 which enumerates 𝐴. (“If we can compute 𝐵, we can enumerate 𝐴.”)

Definition: An enumeration-to-enumeration reduction from 𝐴 to 𝐵 is a Turing machine which receives events “𝑥 ∈ 𝐵” forming an enumeration of 𝐵 (it has a special instruction to get the next event that doesn't block if there is none yet), and sends events “𝑥 ∈ 𝐴” forming an enumeration of 𝐴. (“If we can enumerate 𝐵, we can enumerate 𝐴.”)

Theorem: 𝐴 is enumeration-to-enumeration-reducible to 𝐵 iff 𝐴 is enumeration-to-computation-reducible to a set 𝑋 whenever 𝐵 is.

⇒: Just compose the reductions. (Written this way, it should be more obvious that this works.)

⇐: We construct the oracle 𝑋 in stages as an infinite bit string, by iteratively appending to a finite bit string. At all moments, the 1 indices in 𝑋 are numbers ‹𝑥, 𝑦› for 𝑥 ∈ 𝐵. A “good extension” of 𝑋 is an extension which respects this property.

At step 𝑛, we extend 𝑋 in two ways.

First, we ensure that there is a 1 at some ‹𝑥, 𝑦›, where 𝑥 is the 𝑛-th element of 𝐵. For that we just choose some 𝑦 large enough so that ‹𝑥, 𝑦› is at least the current length, and we extend the bit string with 1 at that index, padding with 0s before it. (This is the whole point of using these pairs ‹𝑥, 𝑦›: by making 𝑦 large, we can add ‹𝑥, 𝑦› without touching an existing bit of the string.)

Second: When 𝑌 is a good extension of 𝑋, let 𝑀(𝑌) be 𝑛-th oracle Turing machine fed with 𝑌 as an oracle. (It can make requests out of bounds, which return 0.) We distinguish three cases.

1. There is a good extension 𝑌 such that 𝑀(𝑌) enumerates some 𝑥 that is not in 𝐴. Fix such an 𝑥. We further extend 𝑌 by padding it with zeros until the oracle queries that were used by 𝑀(𝑌) before enumerating 𝑥 become in bounds, and we set 𝑋 to that extended 𝑌. This ensures that whatever we append to 𝑋 later, the 𝑛-th oracle Turing machine, when fed with 𝑋, will enumerate 𝑥, which is not in 𝐴.

2. There is some value 𝑥 in 𝐴 which is not enumerated by any 𝑀(𝑌), for any good extension 𝑌 of 𝑋. Whatever the eventual value of 𝑋, every invocation of the 𝑛-th oracle Turing machine fed with 𝑋 as oracle will make its invocations on a prefix which is a good extension of the current 𝑋. So, we are already guaranteed that it will never enumerate this 𝑥 and we don't have to append anything.

3. In this remaining case, all values enumerated by 𝑀(𝑌), for all good extension 𝑌, are in 𝐴, and conversely, every element of 𝐴 is enumerated by some 𝑀(𝑌), for some good extension 𝑌. In other words, 𝐴 is exactly the union of the values enumerated by the 𝑀(𝑌) for 𝑌 a good extension. So, we can build the machine which receives events “𝑥 ∈ 𝐵”, enumerates the good extensions 𝑌 while it receives the elements of 𝐵, runs all the 𝑀(𝑌) in parallel, and enumerates 𝐴. So, we can stop the whole process here: 𝐴 is enumeration-to-enumeration-reducible to 𝐵, we have what we wanted.

If this process to construct 𝑋 never terminates, then in the limit, we have 𝑋 such that 𝐵 is enumeration-to-computation-reducible to 𝑋 (because 𝑋 has an element ‹𝑥, 𝑦› for each 𝑥 ∈ 𝐵, and all elements of 𝑋 are of this form), and such that 𝐴 is not enumeration-to-computation-reducible to 𝑋 (because we've ensured, at the 𝑛-th step, that the 𝑛-th oracle Turing machine, when given 𝑋 as oracle, does not enumerate 𝐴). That is absurd. So, the process in fact terminates and 𝐴 is enumeration-to-enumeration-reducible to 𝐵. ∎

The biggest missing puzzle piece was the use property. We need to “freeze” 𝐶 on a large enough prefix when extending it. Indices of this in the original proof: the insistence on choosing some 𝑥 in $𝑊_𝑠^𝐷 - 𝐴$; the passage “from a finite amount of information about $\overline{𝐵}$”.