A set of integers is said to be recursive if there is a total recursive function such that for and for . Any recursive set is also recursively enumerable.
Finite sets, sets with finite complements, the odd numbers, and the prime numbers are all examples of recursive sets. The union and intersection of two recursive sets are themselves recursive, as is the complement of a recursive set.