PlanetMath: recursive set

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

recursive set

(Definition)

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

$\displaystyle \chi_S(x)$

$\displaystyle :=$

$\begin{displaymath}\left\{ \begin{array}{ll} 1 & \mbox{ if } x\in S \ 0 & \mbox{ if } x\in \mathbb{N}-S \end{array}\right.\end{displaymath}$

is computable. In other words, there is an algorithm (via Turing machine for example) that determines whether an element is in

or not in

Examples of recursive sets are finite set, the set of integers, the set of positive integers, 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

$\displaystyle f(x)$

$\displaystyle :=$

$\begin{displaymath}\left\{ \begin{array}{ll} 1 & \mbox{ if } x\in S \ \mbox{undefined} & \mbox{ if } x\in \mathbb{N}-S \end{array}\right.\end{displaymath}$

is computable. In other words, there is an algorithm that halts (and returns

) only when an element in

is used as an input.

Remarks

A recursive set is variably known as a decidable set or a computable set.
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 , when encoded by the natural numbers, is a recursive set. Equivalently, is recursive iff there is a Turing machine that accepts and rejects $\Sigma^*-L$ .
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.

"recursive set" is owned by CWoo.

(view preamble)

Other names:

decidable set, computable set, decidable predicate, computable predicate

Also defines:

recursively enumerable set, recursive predicate, recursively enumerable predicate, recursive language

Keywords:

decidable

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: iff, partial function, recursively enumerable, primality, sieve of Eratosthenes, prime numbers, positive, integers, finite set, Turing machine, algorithm, computable, characteristic function, natural numbers, subset
There are 4 references to this entry.

This is version 10 of recursive set, born on 2007-10-12, modified 2008-01-26.
Object id is 9993, canonical name is RecursiveSet.
Accessed 1220 times total.

Classification:

AMS MSC:	03D20 (Mathematical logic and foundations :: Computability and recursion theory :: Recursive functions and relations, subrecursive hierarchies)
	03B25 (Mathematical logic and foundations :: General logic :: Decidability of theories and sets of sentences)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact