World Library  
Flag as Inappropriate
Email this Article

Recursive set

Article Id: WHEBN0000332264
Reproduction Date:

Title: Recursive set  
Author: World Heritage Encyclopedia
Language: English
Subject: Set theory, Mathematical logic, Formal system, Infinite set, Element (mathematics)
Collection: Computability Theory, Theory of Computation
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Recursive set

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

A more general class of sets 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.

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

Contents

  • Formal definition 1
  • Examples 2
  • Properties 3
  • References 4
  • External links 5

Formal definition

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

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"; see Gödel's incompleteness theorems.

Properties

If A is a recursive set then the complement of A is a recursive set. If A and B are recursive sets then AB, AB 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.

References

  • 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

External links

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.