Computability An Introduction to Recursive Function Theory

The sets mentioned in the title to this chapter are subsets of ℕ corresponding to decidable and partially decidable predicates. We discuss recursive sets briefly in § 1. The major part of this chapter is devoted to the study of recursively enumerable sets, beginning in § 2; many of the basic properties of these sets are derived directly from the results about partially decidable predicates in the previous chapter. The central new result in § 2 is the characterisation of recursively enumerable sets that gives them their name: they are sets that can be enumerated by a recursive (or computable) function.

In §§ 3 and 4 we introduce creative sets and simple sets: these are special kinds of recursively enumerable sets that are in marked contrast to each other; they give a hint of the great variety existing within this class of sets.

Recursive sets

There is a close connection between unary predicates of natural numbers and subsets of ℕ: corresponding to any predicate M(x) we have the set {x : M(x) holds}, called the extent of M (which could, of course, be 0); while to a set A ⊆ ℕ there corresponds the predicate ‘x ∈ A’. The name recursive is given to sets corresponding in this way to predicates that are decidable.

Definition

Let A be a subset of ℕ. The characteristic function of A is the function cA given by

Then A is said to be recursive if cA is computable, or equivalently, if ‘x ∈ A’ is a decidable predicate.

Notes

1. For obvious reasons, recursive sets are also called computable sets.

2. If cA is primitive recursive, the set A is said to be primitive recursive.

3. The idea of a recursive set can be extended in the obvious way to subsets of ℕn (n > 1), although in the text we shall (as is common practice) restrict the use of the term to subsets of ℕ.