MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
The set is finite, hence definitely r.e. – Emil Jeřábek Mar 15 '13 at 16:43
@Emil: Well, but the problem is whether the r.e. index could be found recursively in A. If yes, is it possible to exhibit such program? – Jing Zhang Mar 15 '13 at 17:03
@Joel: Since A is effectively immune, A is not possible to be c.e, since if so, A is the subset of itself and the cardinality is not bounded. I mean the members of A in the natural number order. – Jing Zhang Mar 15 '13 at 17:05
Ah, I had come to the same conclusion myself, and deleted my comment. – Joel David Hamkins Mar 15 '13 at 17:10
Note that $g$ is not recursive but recursive in $A$, so $g$ does have access to the oracle $A$ (though the individual computations for $W_{g(e)}$ do not). As Emil remarked, the first $p(\phi_e(e))$ elements from $A$ is a finite set which therefore has an r.e. index because all finite sets are r.e., so the existence of such a $g$ is at least plausible. – François G. Dorais Mar 15 '13 at 17:11
up vote 4 down vote accepted

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.

share|cite|improve this answer
Fantastic! This is a great answer! I had suspected that any such g must compute 0′, but couldn't see how to do it. (Incidentally, concerning the existence of Turing incomplete effectively immune sets, in the second part of your answer, it is proved in Soare's book that there is a low effectively immune set, in the section where he discussed effectively immune sets, and I believe he uses the low basis theorem.) – Joel David Hamkins Mar 15 '13 at 23:57
Sure. Given $A$ which is effectively immune, we'll build $f$ such that $f(x) = A\upharpoonright_n$ for appropriately chosen $n$. When defining $f(x)$, consider the r.e. set $\{i : \text{$\phi_e(x)$ is a string with a 1 in position $i$}\}$. We can effectively find an index $j$ for this, and then compute $p(j)$. As long as $A\upharpoonright_n$ contains more than $p(j)$ 1s, it must differ from $\phi_e(x)$. So choose $n$ sufficiently large, and you have your $f$ as desired. – Dan Turetsky Mar 17 '13 at 12:31
Huh, the comment I was replying to disappeared. – Dan Turetsky Mar 17 '13 at 12:32
Dan, I think Zhang will ask again as a separate question. – François G. Dorais Mar 17 '13 at 17:35

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

share|cite|improve this answer
This is great work, François. Let me point out merely that what you call $h(e)$ is different than what Dan calls $h(e)$ in his answer. – Joel David Hamkins Mar 16 '13 at 1:22
That $h$ was from Jockusch, but I'll change to $k$ to avoid confusion. – François G. Dorais Mar 16 '13 at 4:17

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'$...

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.