TOPICS
Search

Recursive Set


A set S of integers is said to be recursive if there is a total recursive function f(x) such that f(x)=1 for x in S and f(x)=0 for x not in S. 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.


See also

Recursively Enumerable Set, Recursively Undecidable

This entry contributed by Alex Sakharov (author's link)

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Davis, M. Computability and Unsolvability. New York: Dover 1982.Rogers, H. Theory of Recursive Functions and Effective Computability. Cambridge, MA: MIT Press, 1987.

Referenced on Wolfram|Alpha

Recursive Set

Cite this as:

Sakharov, Alex. "Recursive Set." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/RecursiveSet.html

Subject classifications