Question

Rice-Shapiro theorem states that

version A

Let $\Gamma$ be a set of computably enumerable sets, and $I = \{e : W_e \in \Gamma\}$ its index set in some admissible enumeration of c.e sets. If $I$ is c.e, then for all $x$, $x \in I$ if and only if there is $y \in I$ such that $W_y$ is a finite subset of $W_x$.

Or equivalently

$I$ is c.e $\Rightarrow$

$~~~~(1):~ \forall x,y ~ (x \in I \land W_x \subseteq W_y \rightarrow y \in I)$

$\land ~~(2):~ \forall x ~ (x \in I \rightarrow \exists y~(y \in I \land W_y ~\text{is finite} \land W_y \subseteq W_x))$

My question is if it's converse is also true, that is, if (1) and (2) hold, then $I$ is c.e.


So I found another (weaker) formulation of the theorem in H. Rogers Theory of Recursive Functions and Effective Computability p. 324, which states:

version B

$I$ is c.e $\iff ~(3):~ \forall x ( x \in I \leftrightarrow \exists u (D_{f(u)} \subseteq W_x))$ for some totally computable function $f$

where $D$ is the canonical enumeration of the finite sets (see definition 2.4).

(3) implies that $I$ is c.e, for it is just a $\Sigma_1$ representation of $I$. On the other hand, if $I$ is c.e, by s-m-n theorem take the totally computable function $g$ to be defined such that $W_{g(x)} = D_x$. Now the set $g^{-1}(I) = \{ x : \exists y (g(x) = y \land y \in I)\}$ is also c.e, thus there must be a totally computable function $f$ such that $Range(f) = g^{-1}(I)$. So by version A of the theorem, we also have (1) and (2), which imply that this $f$ is the function that satisfies (3).


I also found these two answers which state the theorem in bidirectional form, but with an additional condition:

version C

$I$ is c.e $\iff (1) \land (2)$

$~~~~~~~~~~~~~~~~\land (4):~ \{ e : D_e \in \Gamma \}$ is c.e

Now this set in (4) is just the $g^{-1}(I)$ defined above, where we just saw that it is indeed c.e. by the sole fact that $I$ is c.e. So my primitive guess is that (4) is the ingredient for proving the other direction.


Considering all the observations above, my question is whether the right to left direction holds generally, i.e. does (1) and (2) imply $I$ is c.e? And is there a counterexample if that fails? Assuming (4), can we deduce that $I$ is c.e? And does that mean the wanted counterexample should refute (4)?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top