7 - Recursive Sets and Relations

Summary

In the preceding chapter we introduced the classes of primitive recursive and recursive functions. In this chapter we introduce the related notions of primitive recursive and recursive sets and relations, which help provide many more examples of primitive recursive and recursive functions. The basic notions are developed in section 7.1. Section 7.2 introduces the related notion of a semirecursive set or relation. The optional section 7.3 presents examples of recursive total functions that are not primitive recursive.

Recursive Relations

A set of, say, natural numbers is effectively decidable if there is an effective procedure that, applied to a natural number, in a finite amount of time gives the correct answer to the question whether it belongs to the set. Thus, representing the answer ‘yes’ by 1 and the answer ‘no’ by 0, a set is effectively decidable if and only if its characteristic function is effectively computable, where the characteristic function is the function that takes the value 1 for numbers in the set, and the value 0 for numbers not in the set. A set is called recursively decidable, or simply recursive for short, if its characteristic function is recursive, and is called primitive recursive if its characteristic function is primitive recursive. Since recursive functions are effectively computable, recursive sets are effectively decidable. Church's thesis, according to which all effectively computable functions are recursive, implies that all effectively decidable sets are recursive.