A subset $S$ of the natural numbers $\mathbb{N}$ is said to be recursive if its characteristic function

More generally, a subset $S\subseteq \mathbb{N}^n$ is recursive if its characteristic function $f_S$ is recursive.

A recursive set is also known as a decidable set or a computable set.

Examples of recursive sets are finite subset of $\mathbb{N}$ , the set $\mathbb{N}$ itself, the set of even integers, the set of Fibonacci numbers, the set of pairs $(a,b)$ where $a$ divides $b$ , and the set of prime numbers. In the last example, one may use the Sieve of Eratosthenes as an algorithm to determine the primality of an integer.

A set $S\subseteq \mathbb{N}$ is recursively enumerable if the partial function

Remarks

• A special case of a recursive set is that of a primitive recursive set. A set is primitive recursive if its characteristic function is primitive recursive. All of the examples cited above are primitive recursive.
• On the other hand, one can broaden the scope of recursiveness to sets which are not necessarily subsets of $\mathbb{N}^n$ . Below are two examples:
  • Since $\mathbb{Z}$ can be effectively embedded in $\mathbb{N}$ , so the notion of recursive sets be extended to subsets of $\mathbb{Z}$ .
  • Since every finite set $\Sigma$ can be encoded by the natural numbers, we can define a recursive language over $\Sigma$ to be a subset $L\subseteq \Sigma^*$ such that $L$ , when encoded by the natural numbers, is a recursive set. Equivalently, $L$ is recursive iff there is a Turing machine that decides $L$ (accepts $L$ and rejects $\Sigma^*-L$ ).
• Similarly, recursive enumerability can be defined on languages: a language $L$ over $\Sigma$ is recursively enumerable if its encoding by the natural numbers is a recursively enumerable set. This is equivalent to saying that $L$ is accepted by a Turing machine.
• Using the above definition, one can define a recursive predicate or a recursively enumerable predicate $\varphi(x)$ according to whether $\lbrace x\mid \varphi(x)\rbrace$ is a recursive or recursively enumerable set respectively.