Weakly semirecursive sets

Abstract We introduce the notion of “semi-r.e.” for subsets of ω , a generalization of “semirecursive” and of “r.e.”, and the notion of “weakly semirecursive”, a generalization of “semi-r.e.”. We show that A is weakly semirecursive iff, for any n numbers x 1 , …, x n , knowing how many of these numbers belong to A is equivalent to knowing which of these numbers belong to A . It is shown that there exist weakly semirecursive sets that are neither semi-r.e. nor co-semi-r.e. On the other hand, we exhibit nonzero Turing degrees in which every weakly semirecursive set is semirecursive. We characterize the notion “ A is weakly semirecursive and recursive in K ” in terms of recursive approximations to A . We also show that if a finite Boolean combination of r.e. sets is semirecursive then it must be r.e. or co-r.e. Several open questions are raised.

Перевод пока недоступен