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).



Indices of r.e. sets
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.


