# Computably enumerable set

A **computably enumerable set** (c.e. set), traditionally called a **recursively enumerable set** (r.e. set), is a set of natural numbers whose members can be listed, at least once and with no outsiders, by a computable algorithm; the listing need never terminate, and an element may appear more than once.<sup>[1](https://www.cambridge.org/core/books/computability-enumerability-unsolvability/dynamic-properties-of-computably-enumerable-sets/9C4CD9D1A4C32E9F6820A38DBF6DEF5C)</sup><sup> • </sup><sup>[2](https://people.csail.mit.edu/kostas/papers/unComputability.pdf)</sup> The class is central to computability theory because it contains every set a program can positively confirm membership in, including sets, such as the halting problem, that are just beyond being computable.<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup>

| Key fact | Detail |
|---|---|
| Names | Computably enumerable (c.e.); older terms recursively enumerable (r.e.) and simply enumerable<sup>[1](https://www.cambridge.org/core/books/computability-enumerability-unsolvability/dynamic-properties-of-computably-enumerable-sets/9C4CD9D1A4C32E9F6820A38DBF6DEF5C)</sup> |
| Domain definition | A set is c.e. iff it is the domain of a partial computable function; \( W_e \) denotes the domain of the \( e \)-th partial computable function \( \varphi_e \)<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup> |
| Range definition | A set is c.e. iff it is empty or the range of a (total) computable function<sup>[4](https://seop.illc.uva.nl/entries////////recursive-functions/)</sup> |
| Definition by projection | \( x \in A \) iff \( \exists y_1, \ldots, y_k \, R(x, y_1, \ldots, y_k) \) for some computable relation \( R \)<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup> |
| Closure | If \( A \) and \( B \) are c.e., so are \( A \cup B \) and \( A \cap B \)<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup> |
| Gap to computability | \( A \) is computable iff both \( A \) and \( \mathbb{N} \setminus A \) are c.e.; the halting problem \( K \) is c.e. but not computable<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup> |
| Number-theoretic face | By the Davis–Putnam–Robinson–Matiyasevich theorem, the Diophantine sets are exactly the recursively enumerable sets<sup>[5](https://logic.pdmi.ras.ru/~yumat/H10Pbook/preface.htm)</sup> |

## Equivalent definitions

The same class of sets is captured in several ways, and the equivalence between them is a basic theorem rather than a convention.

**Enumeration by a function.** A set \( S \subset \mathbb{N} \) is recursively enumerable iff it is enumerated by a recursive function, which is the fact that explains the terminology.<sup>[6](https://web.stanford.edu/~bvchurch/assets/files/talks/GL.pdf)</sup> In the informal version, an algorithm outputs a list \( a_0, a_1, a_2, \ldots \) containing all and only the members of \( A \); if \( A \) is infinite the algorithm runs forever, repetitions are allowed, and the empty set is counted as r.e. by convention.<sup>[2](https://people.csail.mit.edu/kostas/papers/unComputability.pdf)</sup> Formally, \( A \) is r.e. iff \( A = \emptyset \) or there is a [Turing machine](https://www.edgepedia.org/turing-machine) \( M \) whose outputs \( \psi_M(0), \psi_M(1), \psi_M(2), \ldots \) comprise all and only the members of \( A \).<sup>[2](https://people.csail.mit.edu/kostas/papers/unComputability.pdf)</sup>

**Domain of a partial function.** A set is computably enumerable iff it is the domain of a partial computable function, that is, \( A = W_a = \{ x \in \mathbb{N} \mid \Phi_a(x) \downarrow \} \) for some machine \( M_a \).<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup><sup> • </sup><sup>[2](https://people.csail.mit.edu/kostas/papers/unComputability.pdf)</sup> The equivalence with the range definition is proved by dovetailing, a technique in which computations on many inputs are interleaved so that any computation that halts is eventually detected.<sup>[2](https://people.csail.mit.edu/kostas/papers/unComputability.pdf)</sup>

**Existential quantification.** A set \( A \) is c.e. iff membership is a computable relation followed by a block of existential quantifiers, \( x \in A \leftrightarrow \exists y_1, \ldots, y_k \, R(x, y_1, \ldots, y_k) \).<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup> In the same spirit, a relation \( R \) is recursively enumerable iff \( R(a_1, \ldots, a_n) \) holds exactly when \( \exists x \, Q(a_1, \ldots, a_n, x) \) for a recursive relation \( Q \).<sup>[6](https://web.stanford.edu/~bvchurch/assets/files/talks/GL.pdf)</sup> This form makes the semidecidable character of c.e. sets visible: a single witnessed computation confirms membership, while non-membership may never be confirmed.

## Computable versus c.e. sets

Every recursive (computable) set is recursively enumerable: given a computable characteristic function, one can build a total computable function whose range is the set.<sup>[2](https://people.csail.mit.edu/kostas/papers/unComputability.pdf)</sup> All finite sets are recursive, hence c.e.<sup>[2](https://people.csail.mit.edu/kostas/papers/unComputability.pdf)</sup> The converse fails: the halting problem \( K \), the set of \( n \) such that \( \varphi_n(n) \) halts, is c.e. but not computable, and in a precise sense \( K \) is the most complicated c.e. set.<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup> Within the c.e. sets that are not recursive there is great variety; creative sets and simple sets are special kinds of c.e. sets in marked contrast to each other, and the simple sets are recursively enumerable but not recursive.<sup>[7](https://www.cambridge.org/core/books/abs/computability/recursive-and-recursively-enumerable-sets/C88814C3B2971A80D33E17E2FD9FB803)</sup><sup> • </sup><sup>[8](https://personal.denison.edu/~whiteda/files/Lecture%20Notes/Recursively%20Enumerable%20%28GSS%29.pdf)</sup>

The exact boundary is given by a complementation theorem: \( A \) is computable iff both \( A \) and \( \mathbb{N} \setminus A \) are c.e.<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup> The proof runs both enumerations simultaneously and answers once \( x \) appears on one side. Related characterizations concern the order of listing: a c.e. set is computable iff it has a computable enumeration in increasing order, and the incomputability of a c.e. set arises because no computable bound can tell when all elements below a given \( x \) have already appeared; any such modulus must grow incomputably fast.<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup>

C.e. sets also connect to functions: a total function \( f : \mathbb{N} \to \mathbb{N} \) is computable iff its graph is a c.e. set.<sup>[3](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)</sup>

## History

The first formalizations of computability, motivated by Hilbert's *Entscheidungsproblem*, were designed to define computable functions, but effectiveness also arises when generating objects such as sets of formulas. [Alonzo Church](https://www.edgepedia.org/alonzo-church), a logician at Princeton University, introduced the term "recursively enumerable set" in his 1936 paper on Church's Thesis, for a set that is the range of a recursive function; this is apparently the first appearance of the term in the literature. Stephen Kleene's 1936 paper spoke of a "recursive enumeration," meaning a recursive sequence, the successive values of a recursive function of one variable.<sup>[9](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/comprec.pdf)</sup>

Emil Post, then at the [City College of New York](https://www.edgepedia.org/city-college-of-new-york), defined in 1936 a "finite combinatory process" closely resembling a Turing machine, and his 1943 paper on normal (production) systems led to generated sets; his famous 1944 paper inaugurated the modern study of computably enumerable sets. Post 1944 explicitly added the empty set as a c.e. set, which Church and Kleene had omitted, and defined a set of positive integers to be recursively enumerable if it is the range of a recursive function, adding that "the corresponding intuitive concept is that of an effectively enumerable set of positive integers."<sup>[9](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/comprec.pdf)</sup> Starting with Post 1944, much work has related the definable properties of a c.e. set \( A \) to its information content, namely its [Turing degree](https://www.edgepedia.org/turing-degree) \( \deg(A) \) under Turing reducibility; \( \varepsilon \) denotes the structure of the c.e. sets under inclusion.<sup>[1](https://www.cambridge.org/core/books/computability-enumerability-unsolvability/dynamic-properties-of-computably-enumerable-sets/9C4CD9D1A4C32E9F6820A38DBF6DEF5C)</sup> The methods developed in this tradition, such as the Friedberg–Muchnik priority method that solved Post's problem, influenced computability on \( \omega \) and set goals for higher-type computability theories.<sup>[10](https://www.sciencedirect.com/topics/mathematics/recursive-function-theory)</sup>

## Diophantine sets and Hilbert's tenth problem

A subset of the integers is Diophantine if it is the set of values, or solution set, of a polynomial equation with integer coefficients. The main technical result behind the negative solution of [Hilbert's tenth problem](https://www.edgepedia.org/hilberts-tenth-problem), reached in 1970, asserts that the class of Diophantine sets is identical with the class of recursively enumerable sets; the difficult direction is that every recursively enumerable set is Diophantine.<sup>[5](https://logic.pdmi.ras.ru/~yumat/H10Pbook/preface.htm)</sup><sup> • </sup><sup>[11](https://www.researchgate.net/publication/405519383_Hilbert%27s_Tenth_Problem_Beyond_Uniform_Decision_Certificate_Methods_and_Diophantine_Verification)</sup> This Davis–Putnam–Robinson–Matiyasevich theorem implies that Hilbert's tenth problem, which asks for an algorithm to decide solvability of Diophantine equations, is algorithmically unsolvable, since not all recursively enumerable sets are recursive.<sup>[12](https://core.ecu.edu/shlapentokha/book/1-2.pdf)</sup><sup> • </sup><sup>[5](https://logic.pdmi.ras.ru/~yumat/H10Pbook/preface.htm)</sup>

The identification has striking corollaries in pure number theory: there is an explicitly exhibitable polynomial with integer coefficients whose set of positive values, over integer inputs, is exactly the set of all prime numbers.<sup>[5](https://logic.pdmi.ras.ru/~yumat/H10Pbook/preface.htm)</sup> The theorem has also been fully mechanized: the first complete formal proof of the Davis–Putnam–Robinson–Matiyasevich theorem was given in the Coq proof assistant, using Conway's FRACTRAN language as an intermediate layer.<sup>[13](https://arxiv.org/abs/2003.04604)</sup>

## References

1. [Dynamic properties of computably enumerable sets, in *Computability, Enumerability, Unsolvability*, Cambridge University Press](https://www.cambridge.org/core/books/computability-enumerability-unsolvability/dynamic-properties-of-computably-enumerable-sets/9C4CD9D1A4C32E9F6820A38DBF6DEF5C)
2. [Principles of Computation and Uncomputability (course text), MIT](https://people.csail.mit.edu/kostas/papers/unComputability.pdf)
3. [Computability notes, Chapter 4: Computably enumerable sets, University of California, Berkeley](https://math.berkeley.edu/~marks/notes/computability_notes_v1.pdf)
4. [Recursive Functions, Stanford Encyclopedia of Philosophy](https://seop.illc.uva.nl/entries////////recursive-functions/)
5. [Preface to *Hilbert's Tenth Problem* by Yuri Matiyasevich](https://logic.pdmi.ras.ru/~yumat/H10Pbook/preface.htm)
6. [Computability Theory lecture notes, Stanford University](https://web.stanford.edu/~bvchurch/assets/files/talks/GL.pdf)
7. [Recursive and recursively enumerable sets, in *Computability*, Cambridge University Press (1980)](https://www.cambridge.org/core/books/abs/computability/recursive-and-recursively-enumerable-sets/C88814C3B2971A80D33E17E2FD9FB803)
8. [Recursively Enumerable Sets and the Church-Turing Thesis, Denison University lecture notes](https://personal.denison.edu/~whiteda/files/Lecture%20Notes/Recursively%20Enumerable%20%28GSS%29.pdf)
9. [Computably Enumerable Sets and Post (from a paper on the concepts "recursive" and "computable"), University of Maryland](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/comprec.pdf)
10. [Recursive Function Theory, ScienceDirect Topics overview](https://www.sciencedirect.com/topics/mathematics/recursive-function-theory)
11. [Hilbert's Tenth Problem Beyond Uniform Decision Certificate Methods and Diophantine Verification, ResearchGate](https://www.researchgate.net/publication/405519383_Hilbert%27s_Tenth_Problem_Beyond_Uniform_Decision_Certificate_Methods_and_Diophantine_Verification)
12. [Hilbert's Tenth Problem: Diophantine Classes, East Carolina University](https://core.ecu.edu/shlapentokha/book/1-2.pdf)
13. [Hilbert's Tenth Problem in Coq (Extended Version), arXiv](https://arxiv.org/abs/2003.04604)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Computability theory › Computably enumerable sets*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license