Extensional Characterization of Index Sets

A classical result in recursion theory is the Rice-Shapiro theorem (conjectured by RICE [lo, p. 3611 and proved independently by MCNAUGHTON, MYHILL, and SHAPIRO [11, p. 3061). It gives an “extensional” characterization of classes Q of r.e. sets whose index set 0% is r.e., as follows: 0% is r.e. if and only if Q is an r.e. open class, i.e., V consists of all r.e. sets which extend an element of a canonically enumerable sequence of finite sets. This pappr addresses itself to the question of whether a similar extensional characterization can be given for the classes of r.e. sets whose index set is a Boolean combination of r.e. sets. It is an immediate consequence of the Rice-Shapiro theorem that the index set of a Boolean combination of r.e. open classes is a Boolean Combination of r.e. sets. Evidence for the converse was given by GRASSIN [3, Prop. 81 who showed that if 8% is a Boolean combination of r.e. sets then % is a Boolean combination of open classes; he left open the question of whether these must be r.e. open classes. It will be shown below that this is in fact false; hence an exact characterization in these terms cannot be givcn, since if r.e. open class” is weakened (say to “co-r.e. ”) 0 g netd not even be in A!. By contrast, it, will be shown that for generalized index sets (i.e., index sets 0,,(%) of classes Q of sets a t a fixed level of the finite Erghov hierarchy), the following extensional characterization holds: For all ?L 2 2 and classes V of sets a t level n of the hierarchy, On(%) is a Boolean combination of r.e. sets if and only if V is a Boolean combination of “small” open classes (i.e., open classes determined by finite sequences of finite sets). “