# Recursive set

In computability theory, a set of natural numbers is called **recursive**, **computable** or **decidable** if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not.

A set which is not computable is called **noncomputable** or **undecidable**.

A more general class of sets than the decidable ones consists of the recursively enumerable sets, also called **semidecidable** sets. For these sets, it is only required that there is an algorithm that correctly decides when a number *is* in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set.

## Formal definitionEdit

A subset *S* of the natural numbers is called **recursive** if there exists a total computable function *f* such that *f*(*x*) = 1 if *x*∈*S* and *f*(*x*) = 0 if *x*∉*S*. In other words, the set *S* is recursive if and only if the indicator function 1_{S} is computable.

## Examples and non-examplesEdit

Examples:

- Every finite or cofinite subset of the natural numbers is computable. This includes these special cases:
- The empty set is computable.
- The entire set of natural numbers is computable.
- Each natural number (as defined in standard set theory) is computable; that is, the set of natural numbers less than a given natural number is computable.

- The set of prime numbers is computable.
- A recursive language is a recursive subset of a formal language.
- The set of Gödel numbers of arithmetic proofs described in Kurt Gödel's paper "On formally undecidable propositions of Principia Mathematica and related systems I" is computable; see Gödel's incompleteness theorems.

Non-examples:

- The set of Turing machines that halt is not computable.
- The isomorphism class of two finite simplicial complexes is not computable.
- The set of busy beaver champions is not computable.

## PropertiesEdit

If *A* is a recursive set then the complement of *A* is a recursive set. If *A* and *B* are recursive sets then *A* ∩ *B*, *A* ∪ *B* and the image of *A* × *B* under the Cantor pairing function are recursive sets.

A set *A* is a recursive set if and only if *A* and the complement of *A* are both recursively enumerable sets. The preimage of a recursive set under a total computable function is a recursive set. The image of a computable set under a total computable bijection is computable.

A set is recursive if and only if it is at level Δ^{0}_{1} of the arithmetical hierarchy.

A set is recursive if and only if it is either the range of a nondecreasing total computable function or the empty set. The image of a computable set under a nondecreasing total computable function is computable.

## ReferencesEdit

- Cutland, N.
*Computability.*Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7 - Rogers, H.
*The Theory of Recursive Functions and Effective Computability*, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1 - Soare, R.
*Recursively enumerable sets and degrees.*Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7