Computable set

<h2 id="formal-definition">Formal definition</h2>
A subset 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of the <a href="/facts/Natural_number/u65og8JE">natural numbers</a> is called computable if there exists a <a href="/facts/Total_function/0vJMw0Nm">total</a> <a href="/facts/Computable_function/dzwBlLGn">computable function</a> 
 
 
 
 f
 
 
 {\displaystyle f}
 
 such that 
 
 
 
 f
 (
 x
 )
 =
 1
 
 
 {\displaystyle f(x)=1}
 
 if 
 
 
 
 x
 ∈
 S
 
 
 {\displaystyle x\in S}
 
 and 
 
 
 
 f
 (
 x
 )
 =
 0
 
 
 {\displaystyle f(x)=0}
 
 if 
 
 
 
 x
 ∉
 S
 
 
 {\displaystyle x\notin S}
 
. In other words, the set 
 
 
 
 S
 
 
 {\displaystyle S}
 
 is computable <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> the <a href="/facts/Indicator_function/QEuh04NM">indicator function</a> 
 
 
 
 
 
 1
 
 
 S
 
 
 
 
 {\displaystyle \mathbb {1} _{S}}
 
 is <a href="/facts/Computable_function/dzwBlLGn">computable</a>.

<h2 id="examples-and-non-examples">Examples and non-examples</h2>
Examples:

<ul><li>Every finite or <a href="/facts/Cofinite/LvpB23pu">cofinite</a> subset of the natural numbers is computable. This includes these special cases:
<ul><li>The <a href="/facts/Empty_set/ffEk3eA6">empty set</a> is computable.</li>
<li>The entire set of natural numbers is computable.</li>
<li>Each natural number (<a href="/facts/Set-theoretic_definition_of_natural_numbers/pdr0WSDC">as defined in standard set theory</a>) is computable; that is, the set of natural numbers less than a given natural number is computable.</li></ul></li>
<li>The subset of <a href="/facts/Prime_number/L20FLkgn">prime numbers</a> is computable.</li>
<li>A <a href="/facts/Recursive_language/4R0zBWJE">recursive language</a> is a computable subset of a <a href="/facts/Formal_language/crDTyP8q">formal language</a>.</li>
<li>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 <a href="/facts/G%C3%B6del%27s_incompleteness_theorems/du8PRu8g">Gödel's incompleteness theorems</a>.</li></ul>
Non-examples:

Main article: <a href="/facts/List_of_undecidable_problems/SqtIWqsk">List of undecidable problems</a>
<ul><li>The set of <a href="/facts/Halting_problem/Xz1bac40">Turing machines that halt</a> is not computable.</li>
<li>The <a href="/facts/Isomorphism_class/wDUgsJQ8">isomorphism class</a> of two finite simplicial complexes is not computable.</li>
<li>The set of <a href="/facts/Busy_beaver/qfdJPkVu">busy beaver champions</a> is not computable.</li>
<li><a href="/facts/Hilbert%27s_tenth_problem/EaGPklEc">Hilbert's tenth problem</a> is not computable.</li></ul>
<h2 id="properties">Properties</h2>
If A is a computable set then the <a href="/facts/Complement_(set_theory)/yWUePIYY">complement</a> of A is a computable set. If A and B are computable sets then A ∩ B, A ∪ B and the image of A × B under the <a href="/facts/Cantor_pairing_function/RdKC15Mk">Cantor pairing function</a> are computable sets.
A is a computable set <a href="/facts/If_and_only_if/bYSxGJ66">if and only if</a> A and the <a href="/facts/Complement_(set_theory)/yWUePIYY">complement</a> of A are both <a href="/facts/Computably_enumerable/lpzr8jHn">computably enumerable</a> (c.e.). The <a href="/facts/Preimage/KANefMAl">preimage</a> of a computable set under a <a href="/facts/Total_function/0vJMw0Nm">total</a> <a href="/facts/Computable_function/dzwBlLGn">computable function</a> is a computable set. The image of a computable set under a total computable <a href="/facts/Bijection/j4gTuTmW">bijection</a> is computable. (In general, the image of a computable set under a computable function is c.e., but possibly not computable).
A is a computable set if and only if it is at level 
 
 
 
 
 Δ
 
 1
 
 
 0
 
 
 
 
 {\displaystyle \Delta _{1}^{0}}
 
 of the <a href="/facts/Arithmetical_hierarchy/rQptcBFK">arithmetical hierarchy</a>.
A is a computable set 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.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Decidability_(logic)/17SHPMo0">Decidability (logic)</a></li>
<li><a href="/facts/Recursively_enumerable_language/yBV2vFoC">Recursively enumerable language</a></li>
<li><a href="/facts/Recursive_language/4R0zBWJE">Recursive language</a></li>
<li><a href="/facts/Recursion/CxSKxJoW">Recursion</a></li></ul>

<ul><li>Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-22384-9; <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-521-29465-7</li>
<li>Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-262-68052-1; <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 0-07-053522-1</li>
<li>Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 3-540-15299-7</li></ul>
<h2 id="external-links">External links</h2>
<ul><li>Sakharov, Alex. <a href="https://mathworld.wolfram.com/RecursiveSet.html">"Recursive Set"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li></ul>

Computable set open-in-new

Computable set