Indices of r.e. sets

Question

The last part of the paper Located Sets and Reverse Mathematics [Journal of Symbolic Logic 65 (1999), 1451–1480] by Giusto and Simpson involves a proof as follows:

Given $A$ an effectively immune set, i.e. there exists a recursive function $p$ such that $A$ is infinite and $W_e\subseteq A$ implies $|W_e|< p(e)$, construct a r.e. set as follows:

$$W_{g(e)}=\begin{cases}\text{the first } p(\varphi_e(e)) \text{ elements from A} & \text{if }\varphi_e(e)\downarrow \\\\ \emptyset &\text{otherwise} \end{cases}$$

It was claimed that $g\leq_TA$, but an issue here is should the set be r.e relative to A, namely the set generated should be $W_{g(e)}^A$, which then should give a different index? The definition here seems to require unbounded amount of information about A to be known ahead of time so A should be deemed as an oracle, shouldn't it? Thanks! (BTW, the fact that the resulting set is r.e. not with respect to any nontrivial oracle is crucial in the proof that follows).

Answer 1

Edit: restoring my original answer, because I now believe it's correct.

It's not true, in general.

First, there's a total computable function $h$ such that if $\phi_e(e)\downarrow$, then $\phi_{h(e)}(h(e))\downarrow$ and outputs the modulus of $\phi_e(e)$. Next, suppose $A$ could compute such a $g$. Then $A$ can compute $p\circ g \circ h$, and by hypothesis this is at least as large as $\phi_{h(e)}(h(e))$, whenever the later converges. So $A$ computes a function that dominates the modulus function of $0'$, and thus $A$ must compute $0'$.

I then claim there's a Turing incomplete, effectively immune set. It should be possible to build a $\Pi^0_1$-class of such. Let $p(e) = 100^e$. We'll require that for each $e$, if $x$ is the first element of $W_e$ which is enumerated greater than $p(e)$, all elements of our $\Pi^0_1$-class exclude $x$. This will be enough for effective immune-ness, once we make sure that all elements of the class are infinite. We do that by requiring that all elements contain at least one element from the interval $(2^i, 2^{i+1}]$, for each $i$. $p(e)$ grows fast enough that it should always be possible to satisfy both of these requirements.

Then apply the low basis theorem to this class to get an incomplete element, and a contradiction.

Answer 2

I chased down the references to clear this up. Giusto and Simpson attribute the argument to Jockusch [Degrees of functions with no fixed points, in J. E. Fenstad et al., ed., Logic, Methodology and Philosophy of Science VIII, Elsevier Science Publishers B.V. (1989), 191–201]. That argument cannot be found in Jockush, but a very similar remark can be found that Jockusch attributes to Arslanov, Nadirov, and Solov'ev (I didn't chase that reference).

The remark in Jockusch simply defines $f$ to be such that $W_{f(e)}$ consists of the first $p(e)$ elements of $A$. Such an $f$ can easily computed from $A$ and it is necessarily fixed-point free (i.e. $W_{f(e)} \neq W_e$ for every index $e$). Proposition 1 from Jockusch's paper shows that the degrees of fixed-point free functions (FPF) and diagonally non-recursive (DNR) functions are the same. The argument for FPF → DNR proceeds as follows. Given an FPF $f$ (such as the one above) consider $g(e) = f(k(e))$ where $k$ is a recursive function such that $W_{k(e)} = W_{\varphi_e(e)}$ whenever $\phi_e(e){\downarrow}$. Then $W_{g(e)} \neq W_{k(e)} = W_{\phi_e(e)}$, which implies that $g(e) \neq \phi_e(e)$.

It appears that Giusto and Simpson attempted to combine the two arguments a little too swiftly. Indeed, the above $g$ is such that $W_{g(e)}$ consists of the first $p(k(e))$ elements of $A$ and not the first $p(\phi_e(e))$ elements of $A$.

Answer 3

This is too long for a comment, so I put it here.

First, it is clear that there is such a function $g$ that is computable from $A'$, and indeed, even from $A\oplus 0'$. On input $e$ we check from $0'$ whether or not $\varphi_e(e)\downarrow$, and if it does we can construct a program $g(e)$ that enumerates the first $p(\varphi_e(e))$ many elements of $A$ by hard-coding these numbers into the program $g(e)$; and let $g(e)$ compute the empty set otherwise.

In particular, if $A$ computes $0'$, then there is such a $g$ computable from $A$.

Second, let's point out that in any case, from oracle $g$ we can decide $A$, as follows: design programs $e_k$ such that $\varphi_{e_k}(x)=k$ on all input. Thus, we are in the good case for these programs, and so $W_{g(e_k)}$ enumerates the first $p(k)$ many elements of $A$. This process will tell us more and more about $A$, as much as we want. So from oracle $g$, I can compute $A$.

But I don't see how to get $g$ computable from $A$ when $A$ does not compute $0'$...