the close relation between predicates and sets, lets us use the language of sets in talking about solvable and unsolvable problems. for example, the predicate is the characteristic function of the set . to say that a set , where , belongs to some class of functions means that the characteristic function of belongs to the class in question. thus, in particular, to say that the set is computable or recursive is just to say that is a computable function. likewise, is a primitive recursive set if is a primitive recursive predicate.
we may denote the collection of all decidable sets as .
an equivalent can be found in rogers'
a set is recursive if it possesses a recursive characteristic function.
the class of recursive sets is closed under the operations of , and complementation