# Computably enumerable set > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Computably_enumerable_set > Markdown URL: https://mediated.wiki/source/Computably_enumerable_set.md > Source: https://en.wikipedia.org/wiki/Computably_enumerable_set > Source revision: 1354688966 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) Mathematical logic concept "Enumerable set" redirects here. For the set-theoretic concept, see [Countable set](/source/Countable_set). In [computability theory](/source/Computability_theory), a set *S* of [natural numbers](/source/Natural_numbers) is called **computably enumerable (c.e.)**, **recursively enumerable (r.e.)**, **semidecidable**, **partially decidable**, **listable**, **provable** or **Turing-recognizable** if: - There is an [algorithm](/source/Algorithm) such that the set of input numbers for which the algorithm halts is exactly *S*. Or, equivalently, - There is an [algorithm that enumerates](/source/Enumeration_algorithm) the members of *S*. That means that its output is a list of all the members of *S*: *s*1, *s*2, *s*3, ... . If *S* is infinite, this algorithm will run forever, but each element of S will be returned after a finite amount of time. Note that these elements do not have to be listed in a particular way, say from smallest to largest. The first condition suggests why the term *semidecidable* is sometimes used. More precisely, if a number is in the set, one can *decide* this by running the algorithm, but if the number is not in the set, the algorithm can run forever, and no information is returned. A set that is "completely decidable" is a [computable set](/source/Computable_set). The second condition suggests why *computably enumerable* is used. The abbreviations **c.e.** and **r.e.** are often used, even in print, instead of the full phrase. In [computational complexity theory](/source/Computational_complexity_theory), the [complexity class](/source/Complexity_class) containing all computably enumerable sets is [RE](/source/RE_(complexity)). In recursion theory, the [lattice](/source/Lattice_(order)) of c.e. sets under inclusion is denoted E {\displaystyle {\mathcal {E}}} . ## Definition A set *S* of natural numbers is called **computably enumerable** if there is a [partial computable function](/source/Computable_function) whose [domain](/source/Domain_of_a_function) is exactly *S*, meaning that the function is defined if and only if its input is a member of *S*. ## Equivalent formulations The following are all equivalent properties of a set *S* of natural numbers: **Semidecidability:** - - The set *S* is computably enumerable. That is, *S* is the domain (co-range) of a partial computable function. - The set *S* is Σ 1 0 {\displaystyle \Sigma _{1}^{0}} (referring to the [arithmetical hierarchy](/source/Arithmetical_hierarchy)).[1] - There is a partial computable function *f* such that: f ( x ) = { 1 if x ∈ S undefined/does not halt if x ∉ S {\displaystyle f(x)={\begin{cases}1&{\mbox{if}}\ x\in S\\{\mbox{undefined/does not halt}}\ &{\mbox{if}}\ x\notin S\end{cases}}} **Enumerability:** - - The set *S* is the range of a partial computable function. - The set *S* is the range of a total computable function, or empty. If *S* is infinite, the function can be chosen to be [injective](/source/Injective). - The set *S* is the range of a [primitive recursive function](/source/Primitive_recursive_function) or empty. Even if *S* is infinite, repetition of values may be necessary in this case. **Diophantine:** - - There is a polynomial *p* with integer coefficients and variables x , a 1 , a 2 , a 3 , … , a 9 {\displaystyle x,a_{1},a_{2},a_{3},\dots ,a_{9}} ranging over the natural numbers such that x ∈ S ⇔ ∃ a 1 , a 2 , a 3 , … , a 9 ( p ( x , a 1 , a 2 , a 3 , … , a 9 ) = 0 ) . {\displaystyle x\in S\Leftrightarrow \exists a_{1},a_{2},a_{3},\dots ,a_{9}\ (p(x,a_{1},a_{2},a_{3},\dots ,a_{9})=0).} (The number of bound variables in this definition is the best known so far; it might be that a lower number can be used to define all Diophantine sets.) - There is a polynomial from the integers to the integers such that the set *S* contains exactly the non-negative numbers in its range. The equivalence of semidecidability and enumerability can be obtained by the technique of [dovetailing](/source/Dovetailing_(computer_science)). The Diophantine characterizations of a computably enumerable set, while not as straightforward or intuitive as the first definitions, were found by [Yuri Matiyasevich](/source/Yuri_Matiyasevich) as part of the negative solution to [Hilbert's Tenth Problem](/source/Hilbert's_tenth_problem). Diophantine sets predate recursion theory and are therefore historically the first way to describe these sets (although this equivalence was only remarked more than three decades after the introduction of computably enumerable sets). A computable enumeration of the set of all Turing machines halting on a fixed input: Simulate all Turing machines (enumerated on vertical axis) step by step (horizontal axis), using the shown diagonalization scheduling. If a machine terminates, print its number. This way, the number of each terminating machine is eventually printed. In the example, the algorithm prints "9, 13, 4, 15, 12, 18, 6, 2, 8, 0, ..." ## Examples - Every [computable set](/source/Computable_set) is computably enumerable, but it is not true that every computably enumerable set is computable. For computable sets, the algorithm must also say if an input is *not* in the set – this is not required of computably enumerable sets. - A [recursively enumerable language](/source/Recursively_enumerable_language) is a computably enumerable subset of a [formal language](/source/Formal_language). - The set of all provable sentences in an effectively presented axiomatic system is a computably enumerable set. - [Matiyasevich's theorem](/source/Matiyasevich's_theorem) states that every computably enumerable set is a [Diophantine set](/source/Diophantine_set) (the converse is trivially true). - The [simple sets](/source/Simple_set) are computably enumerable but not computable. - The [creative sets](/source/Creative_set) are computably enumerable but not computable. - Any [productive set](/source/Productive_set) is **not** computably enumerable. - Given a [Gödel numbering](/source/G%C3%B6del_numbering) ϕ {\displaystyle \phi } of the computable functions, the set { ⟨ i , x ⟩ ∣ ϕ i ( x ) ↓ } {\displaystyle \{\langle i,x\rangle \mid \phi _{i}(x)\downarrow \}} (where ⟨ i , x ⟩ {\displaystyle \langle i,x\rangle } is the [Cantor pairing function](/source/Cantor_pairing_function) and ϕ i ( x ) ↓ {\displaystyle \phi _{i}(x)\downarrow } indicates ϕ i ( x ) {\displaystyle \phi _{i}(x)} is defined) is computably enumerable (cf. picture for a fixed *x*). This set encodes the [halting problem](/source/Halting_problem) as it describes the input parameters for which each [Turing machine](/source/Turing_machine) halts. - Given a Gödel numbering ϕ {\displaystyle \phi } of the computable functions, the set { ⟨ x , y , z ⟩ ∣ ϕ x ( y ) = z } {\displaystyle \{\left\langle x,y,z\right\rangle \mid \phi _{x}(y)=z\}} is computably enumerable. This set encodes the problem of deciding a function value. - Given a partial function *f* from the natural numbers into the natural numbers, *f* is a partial computable function if and only if the graph of *f*, that is, the set of all pairs ⟨ x , f ( x ) ⟩ {\displaystyle \langle x,f(x)\rangle } such that *f*(*x*) is defined, is computably enumerable. ## Properties If *A* and *B* are computably enumerable sets then *A* ∩ *B*, *A* ∪ *B* and *A* × *B* (with the ordered pair of natural numbers mapped to a single natural number with the [Cantor pairing function](/source/Cantor_pairing_function)) are computably enumerable sets. The [preimage](/source/Preimage) of a computably enumerable set under a partial computable function is a computably enumerable set. A set T {\displaystyle T} is called **co-computably-enumerable** or **co-c.e.** if its [complement](/source/Complement_(set_theory)) N ∖ T {\displaystyle \mathbb {N} \setminus T} is computably enumerable. Equivalently, a set is co-r.e. if and only if it is at level Π 1 0 {\displaystyle \Pi _{1}^{0}} of the arithmetical hierarchy. The complexity class of co-computably-enumerable sets is denoted co-RE. A set *A* is [computable](/source/Computable_set) if and only if both *A* and the complement of *A* are computably enumerable. Some pairs of computably enumerable sets are [effectively separable](/source/Effectively_separable) and some are not. ## The lattice of recursively enumerable sets This section needs expansion. You can help by adding missing information. (May 2026) The set of all recursively enumerable subsets of the natural numbers can be made into a [poset](/source/Poset) under [set inclusion](/source/Set_inclusion); this poset is a [lattice](/source/Lattice_(order)).[2] The theory of this lattice is known to be an [undecidable problem](/source/Undecidable_problem).[2] Similarly, the set of all computably enumerable [vector spaces](/source/Vector_spaces) also forms a lattice.[3] In fact, one can generalize this even further to the lattice *L(Q)*, which is defined to consist of all recursively enumerable [filters](/source/Filter_(mathematics)), where *Q* is some [free Boolean algebra](/source/Free_Boolean_algebra) without any [atoms](/source/Atom_(order_theory)).[4] These lattices are closely tied to the study of recursively enumerable [Pi-0-1](/source/Pi-0-1_sentence) classes.[4] ### Intervals The [intervals](/source/Interval_(order_theory)) of this lattice are either [boolean algebras](/source/Boolean_algebras), or their first-order theory is also undecidable.[2] The possible structure of intervals of this lattice is not very well understood.[2] ### Maximal recursively enumerable sets The complement of the function which enumerates any maximal recursively enumerable set dominates every [general recursive function](/source/General_recursive_function).[5] There exists maximal recursively enumerable set of [Turing degree](/source/Turing_degree) at most **0′**.[5] For any two maximal recursively enumerable sets *A* and *B*, there exists an [order automorphism](/source/Order_automorphism) of the lattice of recursively enumerable sets that maps *A* to *B*; this automorphism, however, may not always be computable.[6] ## Remarks According to the [Church–Turing thesis](/source/Church%E2%80%93Turing_thesis), any effectively calculable function is calculable by a [Turing machine](/source/Turing_machine), and thus a set *S* is computably enumerable if and only if there is some [algorithm](/source/Algorithm) which yields an enumeration of *S*. This cannot be taken as a formal definition, however, because the Church–Turing thesis is an informal conjecture rather than a formal axiom. The definition of a computably enumerable set as the *domain* of a partial function, rather than the *range* of a total computable function, is common in contemporary texts. This choice is motivated by the fact that in generalized recursion theories, such as [α-recursion theory](/source/Alpha_recursion_theory), the definition corresponding to domains has been found to be more natural. Other texts use the definition in terms of enumerations, which is equivalent for computably enumerable sets. ## See also - [RE (complexity)](/source/RE_(complexity)) - [Recursively enumerable language](/source/Recursively_enumerable_language) - [Arithmetical hierarchy](/source/Arithmetical_hierarchy) ## References 1. **[^](#cite_ref-1)** Downey, Rodney G.; Hirschfeldt, Denis R. (29 October 2010). [*Algorithmic Randomness and Complexity*](https://books.google.com/books?id=FwIKhn4RYzYC&pg=PA23). Springer Science & Business Media. p. 23. [ISBN](/source/ISBN_(identifier)) [978-0-387-68441-3](https://en.wikipedia.org/wiki/Special:BookSources/978-0-387-68441-3). 1. ^ [***a***](#cite_ref-:0_2-0) [***b***](#cite_ref-:0_2-1) [***c***](#cite_ref-:0_2-2) [***d***](#cite_ref-:0_2-3) Nies, André (November 1997). ["Intervals of the Lattice of Computably Enumerable Sets and Effective Boolean Algebras"](https://www.cambridge.org/core/journals/bulletin-of-the-london-mathematical-society/article/abs/intervals-of-the-lattice-of-computably-enumerable-sets-and-effective-boolean-algebras/A5291ED7EECD1A29790F1C35F02B65EE). *Bulletin of the London Mathematical Society*. **29** (6): 683–692. [doi](/source/Doi_(identifier)):[10.1112/S0024609397003548](https://doi.org/10.1112%2FS0024609397003548). [ISSN](/source/ISSN_(identifier)) [1469-2120](https://search.worldcat.org/issn/1469-2120). 1. **[^](#cite_ref-3)** Dimitrov, Rumen D.; Harizanov, Valentina (2017), Day, Adam; Fellows, Michael; Greenberg, Noam; Khoussainov, Bakhadyr (eds.), ["The Lattice of Computably Enumerable Vector Spaces"](https://doi.org/10.1007/978-3-319-50062-1_23), *Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday*, Cham: Springer International Publishing, pp. 366–393, [doi](/source/Doi_(identifier)):[10.1007/978-3-319-50062-1_23](https://doi.org/10.1007%2F978-3-319-50062-1_23), [ISBN](/source/ISBN_(identifier)) [978-3-319-50062-1](https://en.wikipedia.org/wiki/Special:BookSources/978-3-319-50062-1), retrieved 2026-05-17{{[citation](https://en.wikipedia.org/wiki/Template:Citation)}}: CS1 maint: work parameter with ISBN ([link](https://en.wikipedia.org/wiki/Category:CS1_maint:_work_parameter_with_ISBN)) 1. ^ [***a***](#cite_ref-:2_4-0) [***b***](#cite_ref-:2_4-1) Downey, R. G. (June 1983). ["Abstract dependence, recursion theory, and the lattice of recursively enumerable filters"](https://www.cambridge.org/core/journals/bulletin-of-the-australian-mathematical-society/article/abstract-dependence-recursion-theory-and-the-lattice-of-recursively-enumerable-filters/E11C409991A5E8362EA4E59EBB86D934). *Bulletin of the Australian Mathematical Society*. **27** (3): 461–464. [doi](/source/Doi_(identifier)):[10.1017/S0004972700025958](https://doi.org/10.1017%2FS0004972700025958). [ISSN](/source/ISSN_(identifier)) [1755-1633](https://search.worldcat.org/issn/1755-1633). 1. ^ [***a***](#cite_ref-:1_5-0) [***b***](#cite_ref-:1_5-1) ["Document Zbl 0199.02504 - zbMATH Open"](https://web.archive.org/web/20221120035517/http://zbmath.org/0199.02504). *zbmath.org*. Archived from [the original](http://zbmath.org/0199.02504) on 2022-11-20. Retrieved 2026-05-17. 1. **[^](#cite_ref-6)** Soare, Robert I. (1974). ["Automorphisms of the Lattice of Recursively Enumerable Sets Part I: Maximal Sets"](https://www.jstor.org/stable/1970842). *Annals of Mathematics*. **100** (1): 80–120. [doi](/source/Doi_(identifier)):[10.2307/1970842](https://doi.org/10.2307%2F1970842). [ISSN](/source/ISSN_(identifier)) [0003-486X](https://search.worldcat.org/issn/0003-486X). - [Rogers, H.](/source/Hartley_Rogers_Jr.) *The Theory of Recursive Functions and Effective Computability*, [MIT Press](/source/MIT_Press). [ISBN](/source/ISBN_(identifier)) [0-262-68052-1](https://en.wikipedia.org/wiki/Special:BookSources/0-262-68052-1); [ISBN](/source/ISBN_(identifier)) [0-07-053522-1](https://en.wikipedia.org/wiki/Special:BookSources/0-07-053522-1). - [Soare, R.](/source/Robert_I._Soare) Recursively enumerable sets and degrees. *Perspectives in Mathematical Logic.* [Springer-Verlag](/source/Springer-Verlag), Berlin, 1987. [ISBN](/source/ISBN_(identifier)) [3-540-15299-7](https://en.wikipedia.org/wiki/Special:BookSources/3-540-15299-7). - Soare, Robert I. Recursively enumerable sets and degrees. *Bull. Amer. Math. Soc.* 84 (1978), no. 6, 1149–1181. v t e Mathematical logic General Axiom list Cardinality First-order logic Formal proof Formal semantics Foundations of mathematics Information theory Lemma Logical consequence Model Theorem Theory Type theory Theorems (list), paradoxes Gödel's completeness – incompleteness theorems Tarski's undefinability Banach–Tarski paradox Cantor's theorem – paradox – diagonal argument Compactness Halting problem Lindström's Löwenheim–Skolem Russell's paradox Logics Traditional Classical logic Logical truth Tautology Proposition Inference Logical equivalence Consistency Equiconsistency Argument Soundness Validity Syllogism Square of opposition Venn diagram Propositional Boolean algebra Boolean functions Logical connectives Propositional calculus Propositional formula Truth tables Many-valued logic 3 finite ∞ Predicate First-order list Second-order Monadic Higher-order Fixed-point Free Quantifiers Predicate Monadic predicate calculus Set theory Set hereditary Class (Ur-)Element Ordinal number Extensionality Forcing Relation equivalence partition Set operations: intersection union complement Cartesian product power set identities Types of sets Countable Uncountable Empty Inhabited Singleton Finite Infinite Transitive Ultrafilter Recursive Fuzzy Universal Universe constructible Grothendieck Von Neumann Maps, cardinality Function/Map domain codomain image In/Sur/Bi-jection Schröder–Bernstein theorem Isomorphism Gödel numbering Enumeration Large cardinal inaccessible Aleph number Operation binary Theories Zermelo–Fraenkel axiom of choice continuum hypothesis General Kripke–Platek Morse–Kelley Naive New Foundations Tarski–Grothendieck Von Neumann–Bernays–Gödel Ackermann Constructive Formal systems (list), language, syntax Alphabet Arity Automata Axiom schema Expression ground Extension by definition conservative Relation Formation rule Grammar Formula atomic closed ground open Free/bound variable Language Metalanguage Logical connective ¬ ∨ ∧ → ↔ = Predicate functional variable propositional variable Proof Quantifier ∃ ! ∀ rank Sentence atomic spectrum Signature String Substitution Symbol function logical/constant non-logical variable Term Theory list Example axiomatic systems (list) of true arithmetic Peano second-order elementary function primitive recursive Robinson Skolem of the real numbers Tarski's axiomatization of Boolean algebras canonical minimal axioms of geometry Euclidean Elements Hilbert's Tarski's non-Euclidean Principia Mathematica Proof theory Formal proof Natural deduction Logical consequence Rule of inference Sequent calculus Theorem Systems axiomatic deductive Hilbert list Complete theory Independence (from ZFC) Proof of impossibility Ordinal analysis Reverse mathematics Self-verifying theories Model theory Interpretation function of models Model atomic equivalence finite prime saturated spectrum submodel Non-standard model of non-standard arithmetic Diagram elementary Categorical theory Model complete theory Satisfiability Semantics of logic Strength Theories of truth semantic Tarski's Kripke's T-schema Transfer principle Truth predicate Truth value Type Ultraproduct Validity Computability theory Church encoding Church–Turing thesis Computably enumerable Computable function Computable set Decision problem decidable undecidable P NP P versus NP problem Kolmogorov complexity Lambda calculus Primitive recursive function Recursion Recursive set Turing machine Type theory Related Abstract logic Algebraic logic Automated theorem proving Category theory Concrete/Abstract category Category of sets History of logic History of mathematical logic timeline Logicism Mathematical object Philosophy of mathematics Supertask Mathematics portal --- Adapted from the Wikipedia article [Computably enumerable set](https://en.wikipedia.org/wiki/Computably_enumerable_set) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Computably_enumerable_set?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.