4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Version A item (1) looks wrong. $I=\{i | \varphi_i(0) = 0 \}$ is a c.e. index set, but does not satisfy (1) if we pick for all $n$, $\varphi_x(n)=0$ and $\varphi_y(n)=1$. Here $x \in I$ and $W_x = W_y = \mathbb N$, but $y \notin I$. Are you using $W_x$ for the domain of $\varphi_x$ or something else? $\endgroup$ – chi Jan 7 at 14:29
  • $\begingroup$ @chi You're right, my definitions were inconsistent. I have to either state the theorem as p.c functions too, or define $I$ as an index set for a collection of c.e sets (as stated in Rogers' book). Either way the theorem should hold since any index set for c.e sets is also an index set for p.c functions (but of course not vice versa, as in your example). $\endgroup$ – Beleg Jan 7 at 15:28
  • $\begingroup$ I corrected the definition. $\endgroup$ – Beleg Jan 7 at 15:48
2
$\begingroup$

No, the converse direction does not hold:

Pick some non-c.e. set $B \subseteq \mathbb{N}$. Now consider $\Gamma = \{A \ c.e. \mid A \cap B \neq \emptyset\}$. By construction, $\Gamma$ satisfies the conclusion of Rice-Shapiro (it suffices to consider singleton sets rather than all finite sets). However, for the resulting index set $I$ we find that $B \leq_m I$, so $I$ cannot be c.e..

Essentially, Rice-Shapiro says that the Markov-effectively open subsets of the subspace of ce subsets of $P(\omega)$ (with the Scott topology) are open, but for already for cardinality reasons alone, not all open subsets can be Markov-effectively open.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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