recursive set
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, if this is the case we say that is decided by 
. 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
.
[cite:;taken from @computability_davis_1994 chapter 4.4 recursively enumerable sets]
an equivalent can be found in rogers':
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, if this is the case we say that is decided by . 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
.[cite:;taken from @computability_davis_1994 chapter 4.4 recursively enumerable sets]
a set is recursive if it possesses a recursive characteristic function.
[cite:;taken from @computability_rogers_1987 chapter 5 recursive and recursively enumerable sets]
note that a recursive set has to have a total computable function.
[cite:;taken from @computability_rogers_1987 chapter 5 recursive and recursively enumerable sets]
the class of recursive sets is closed under the operations of 
, and complementation
[cite:;taken from @computability_rogers_1987 chapter 5 recursive and recursively enumerable sets]
, and complementation[cite:;taken from @computability_rogers_1987 chapter 5 recursive and recursively enumerable sets]