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