Fact-checked by Grok 2 weeks ago

Computably enumerable set

In , a computably enumerable set (c.e. set), also known as a recursively enumerable set, is a of the natural numbers that is either empty or the of a total , allowing for repetitions in the enumeration. Equivalently, it is the domain of a partial , meaning there exists a that halts precisely on inputs in the set and may loop indefinitely on others. This class of sets captures the notion of semi-decidability, where membership can be verified algorithmically if true, but non-membership may not be detectable in finite time. Several equivalent characterizations highlight the foundational role of c.e. sets in recursion theory. A set A \subseteq \mathbb{N} is c.e. if there is a computable relation R \subseteq \mathbb{N}^{k+1} such that x \in A if and only if there exist witnesses y_1, \dots, y_k satisfying R(x, y_1, \dots, y_k). It can also be approximated by a computable sequence of finite sets (A_s)_{s \in \mathbb{N}} that is non-decreasing, starts empty, and whose union is A, with at most one new element added per stage. The collection of all c.e. sets is effectively enumerable, indexed as W_e = \dom(\phi_e), where \phi_e is the e-th partial computable function under a standard . C.e. sets form a central in understanding the , as every computable (recursive) set is c.e., but the converse fails: a set is computable if and only if both it and its complement are c.e.. The , defined as K = \{ e : \phi_e(e) \downarrow \}, exemplifies a c.e. set that is not computable, establishing the incompleteness of any effective . Basic operations preserve c.e.-ness: the and of two c.e. sets are c.e., and every c.e. set contains an computable . These properties underpin advanced results, such as the arithmetic hierarchy, where c.e. sets coincide with the \Sigma_1^0 class.

Core Definitions

Enumeration via Turing Machines

A set S \subseteq \mathbb{N} is computably enumerable if it is empty or there exists a M that computes a total f: \mathbb{N} \to \mathbb{N} such that the range of f is exactly S. In this setup, M runs indefinitely on successive inputs $0, 1, 2, \dots, producing the sequence f(0), f(1), f(2), \dots, where every element of S appears at least once (and possibly finitely many times if duplicates occur), and no element outside S is produced. The enumeration process relies on M systematically generating this sequence without halting, ensuring completeness by covering all of S over infinite time, though the order need not be increasing or unique. For effective implementation, M can output each f(k) as it computes it, allowing observers to collect the listing progressively; repetitions are permissible since the focus is on exhaustiveness rather than efficiency or uniqueness. This range-based view contrasts with input-focused characterizations by emphasizing output generation via a total computable mapping. The concept originated in the foundational work of and during the 1930s, as part of efforts to formalize and address the posed by . Church's development of recursive functions and Turing's introduction of Turing machines provided equivalent models that captured enumerable sets, laying the groundwork for modern . Formally, for a M_e with index e, the enumerated set is S = \{ y \in \mathbb{N} \mid \exists x \in \mathbb{N} \, (T_e(x, y) \downarrow) \}, where T_e is a total primitive recursive indicating that M_e on input x outputs y in finitely many steps; this ensures S is precisely the without extraneous elements.

Domain of Partial Recursive Functions

A set S \subseteq \mathbb{N} of natural numbers is computably enumerable if there exists an index e such that S is precisely the domain of the partial \phi_e, meaning \phi_e(x) \downarrow (converges to an output) if and only if x \in S. This characterization, introduced in the foundational development of recursion theory, identifies computably enumerable sets with the collection of inputs on which some partial recursive computation halts. Partial recursive functions are intimately connected to Turing machines: every partial recursive function \phi_e can be computed by a M_e, and the domain of \phi_e consists exactly of those inputs on which M_e halts. This equivalence, established through Church's thesis, underscores that the halting behavior of defines the same class of sets as the domains of partial recursive functions. The equivalence between this domain-based definition and direct enumeration arises from the ability to list the elements of any such systematically. Given S = \dom(\phi_e), one can enumerate S by dovetailing simulations of \phi_e on all inputs: at stage n, perform n steps of for each of the first n inputs (i.e., inputs 0 through n-1), and whenever a computation halts, output that input. This process outputs each element of S (possibly with repetitions, which can be eliminated via a primitive recursive check for prior outputs) in finite time, as every halting will eventually be simulated sufficiently long to converge. In contrast to total recursive functions, whose domains are always all of \mathbb{N} and thus characterize the empty set or its complement in the context of recursive sets, partial recursive functions permit divergence (non-halting) precisely on elements outside S. This asymmetry enables the semi-decidability of membership in S, as one can verify presence via halting but cannot confirm absence in general.

Equivalent Characterizations

Semi-Decidability

A computably enumerable set S \subseteq \mathbb{N} is formally characterized by the existence of a M that semi-decides membership in S: on input x, M halts x \in S, and otherwise loops indefinitely. This one-sided decision procedure, known as semi-decidability, allows algorithmic verification of positive membership but provides no guarantee of termination for non-members. The concept traces back to early work in , where Emil Post introduced the notion of recursively enumerable sets in this operational sense, emphasizing their generation through effective processes akin to computations. To semi-decide membership for a given x \in \mathbb{N}, the procedure simulates an enumerator for S that systematically generates elements of the set and checks whether x eventually appears in the output sequence; if it does, the machine halts affirmatively, but if x \notin S, the simulation continues indefinitely without resolution. This dovetails with the domain of partial recursive functions, where S corresponds to the set of inputs on which a is defined and halts. The equivalence between semi-decidability and enumerability follows from a bidirectional construction using dovetailing. To enumerate from a semi-decider M, simulate M on all natural number inputs $0, 1, 2, \dots in parallel: at stage n, run the first n simulations for n steps each, and output any input that halts during this stage; this ensures all elements of S are eventually listed without repetition or omission, as every halting computation will be reached in finite time. Conversely, from an enumerator, semi-decidability is direct via the checking procedure described above. This proof establishes that the two characterizations capture the same class of sets. This framework supports the Church-Turing thesis by identifying computably enumerable sets as precisely those effectively verifiable through mechanical procedures, aligning intuitive notions of effective computability with formal Turing machine models.

Placement in Arithmetical Hierarchy

Computably enumerable sets, also known as recursively enumerable sets, are precisely the sets in the \Sigma_1^0 class of the arithmetical hierarchy. This hierarchy classifies subsets of the natural numbers based on the complexity of their first-order arithmetic definitions, measured by the number and type of quantifiers over natural numbers in the defining formula. A set S \subseteq \mathbb{N} belongs to \Sigma_1^0 if it can be defined by a formula of the form x \in S \iff \exists y \, R(x,y), where R is a primitive recursive (hence decidable) predicate. The equivalence between computably enumerable sets and \Sigma_1^0 sets follows from Kleene's normal form theorem, which establishes that every computably enumerable set admits such an existential over a recursive , and conversely, any \Sigma_1^0 set is computably enumerable because the witnesses y can be effectively enumerated using the decidability of R. In contrast, the complements of computably enumerable sets form the \Pi_1^0 class, defined by universal quantifiers: x \in S \iff \forall y \, R(x,y) for recursive R. The recursive (decidable) sets occupy the \Delta_1^0 class, which is the \Sigma_1^0 \cap \Pi_1^0; thus, a set is recursive if and only if both it and its complement are computably enumerable. This placement highlights the semi-decidable nature of computably enumerable sets within the hierarchy, as membership can be verified but non-membership may not halt. Through , which assigns unique codes to arithmetic formulas, the set of Gödel numbers of sentences provable in Peano arithmetic is computably enumerable (hence \Sigma_1^0), since proofs can be mechanically enumerated and checked for validity. Gödel's first incompleteness theorem demonstrates that this set is not recursive, as Peano arithmetic cannot prove its own , underscoring the proper inclusion of \Sigma_1^0 beyond the recursive sets.

Illustrative Examples

Computable Examples

Computably enumerable sets include all computable (recursive) sets as a proper , since any set for which membership is decidable by a can be enumerated by systematically checking and listing elements in order. This inclusion holds because a total recursive allows enumeration via dovetailing: for each stage i = 1, 2, \dots, compute the characteristic function on all inputs up to i and output those n \leq i where it equals 1, ensuring every member is eventually listed since the function halts on all inputs. Finite sets provide the simplest examples of computable sets, hence computably enumerable ones. For any finite set S = \{a_1, a_2, \dots, a_k\} \subseteq \mathbb{N}, a Turing machine can enumerate it by hardcoding the fixed list and outputting each a_j in sequence, halting after the last element; membership is decidable by direct comparison to the list. Similarly, the empty set is computable and computably enumerable, as the enumerating machine simply halts without output. The set of even natural numbers, E = \{ n \in \mathbb{N} \mid n \equiv 0 \pmod{2} \}, is computable via a primitive recursive that checks divisibility by 2, allowing enumeration by the total recursive function f(i) = 2i for i = 0, 1, 2, \dots, which generates the sequence $0, 2, 4, \dots exhaustively. Membership decision follows immediately from this modulo operation, confirming E as recursive and thus computably enumerable. The set of numbers, P = \{ p \in \mathbb{N} \mid p > [1](/page/1) \text{ and } p \text{ has no divisors other than [1](/page/1) and itself} \}, is another computable example. Primality is recursive, decidable by up to \sqrt{p}, enabling via a total recursive generator that sequentially tests candidates starting from 2 and outputs only primes. For instance, the machine can use a sieve-like process to list primes in order: 2, 3, 5, 7, \dots, with the procedure halting on each for membership queries. Sets defined by recursive predicates, such as \{ n \mid \phi_e(n) = 0 \} for a computable \phi_e, are computable when the predicate is , with enumeration mirroring the domain of the . The of finitely many computable sets remains computable, further illustrating this . However, not all computably enumerable sets are computable, as some lack a membership .

Non-Computable Examples

A canonical example of a computably enumerable set that is not computable is the halting set K = \{ e \in \mathbb{N} \mid \phi_e(e) \downarrow \}, where \phi_e denotes the partial computed by the e-th and \downarrow indicates that the halts. This set is computably enumerable because one can enumerate all indices e for which the \phi_e(e) eventually halts by dovetailing simulations of all such computations in parallel. However, K is not computable, as established by Turing's diagonalization argument showing that no can decide membership for all e. The halting set occupies the lowest nontrivial level \Sigma_1^0 in the . Another fundamental non-computable computably enumerable set arises in formal logic: the set of Gödel numbers of theorems provable in Peano arithmetic (or any sufficiently strong consistent ). This set, denoted Th(PA) = \{ \ulcorner \sigma \urcorner \mid PA \vdash \sigma \}, is computably enumerable by systematically generating all proofs in the system and extracting their conclusions. Yet, Th(PA) is not computable due to Gödel's first incompleteness theorem, which demonstrates the existence of true but unprovable sentences in such systems, rendering membership undecidable. The connection between computably enumerable sets and number theory is highlighted by Diophantine sets, which are subsets of the natural numbers definable by existential quantifiers over polynomial equations with integer coefficients: a set S \subseteq \mathbb{N} is Diophantine if S = \{ x \in \mathbb{N} \mid \exists y_1, \dots, y_k \in \mathbb{N} \, P(x, y_1, \dots, y_k) = 0 \} for some polynomial P with integer coefficients. Matiyasevich's theorem (1970) proves that every computably enumerable set is Diophantine, resolving Hilbert's tenth problem negatively by showing that there is no algorithm to decide whether a given Diophantine equation has solutions in natural numbers. For instance, the halting set K admits a Diophantine representation, illustrating how undecidability permeates Diophantine problems. Simple sets, introduced by , provide further examples of computably enumerable sets that are not computable, characterized by their complements being yet "" in the sense of avoiding computably enumerable subsets. A set A \subseteq \mathbb{N} is if it is and computably enumerable, its complement \overline{A} is , and no computably enumerable set is contained entirely in \overline{A}. The existence of simple sets was established constructively by using a priority method to ensure the complement remains immune to computably enumerable subsets while keeping A . Such sets demonstrate the structural complexity within the class of computably enumerable sets beyond mere undecidability.

Fundamental Properties

Closure Properties

Computably enumerable (c.e.) sets, also known as recursively enumerable sets, exhibit several closure properties under basic algebraic operations, reflecting their effective enumerability. These properties arise from the ability to construct effective enumerators or Turing machines that simulate the behaviors of given c.e. sets in combination. Such closures are fundamental to understanding the structure of the class of c.e. sets within . The class of c.e. sets is closed under finite unions. Specifically, if A and B are c.e., then A \cup B is c.e. To see this, suppose there are computable enumerators f and g for A and B, respectively. A combined enumerator can dovetail the computations of f and g by simulating both in an interleaved manner: at stage n, simulate the first n steps of f(1), \dots, f(n) and g(1), \dots, g(n), outputting any newly produced elements without duplication. This process effectively enumerates all elements of A \cup B. The extension to finite unions follows by . Similarly, the class is closed under finite intersections. If A and B are c.e., then A \cap B is c.e. One construction involves enumerating potential elements by dovetailing over pairs (x, s, t), where x is a candidate, and s, t are stages of for enumerators of A and B. For each pair where x appears in the stage-s of A and the stage-t of B, output x if it has not been output before. Since elements of c.e. sets eventually stabilize in their approximations once enumerated, this will enumerate exactly A \cap B. In terms of indices, if e_A and e_B are indices for enumerators of A and B, there exists a h(e_A, e_B) providing an index for an enumerator of A \cap B. The class of c.e. sets is also closed under the formation of encoded products. If A and B are c.e., then the set \{\langle x, y \rangle \mid x \in A, y \in B\} is c.e., where \langle \cdot, \cdot \rangle denotes a computable , such as the pairing function \langle x, y \rangle = \frac{(x+y)(x+y+1)}{2} + y, which is a from \mathbb{N} \times \mathbb{N} to \mathbb{N}. To enumerate this set, dovetail enumerations of A and B to produce pairs (x_i, y_j) and compute \langle x_i, y_j \rangle for each, outputting these values in order. This ensures all paired elements are eventually listed. follows as a special case: if A and B are c.e. subsets of s, then \{uv \mid u \in A, v \in B\} is c.e. by similar dovetailing over string pairs. In terms, there is a computable function p(e_A, e_B) yielding an index for the product enumerator. The class is not closed under complementation: for example, the complement of the halting set K = \{e \mid \phi_e(e) \downarrow\}, which is c.e., is not c.e., as its c.e.-ness would imply the decidability of K, contradicting the undecidability of the .

Relations to Recursive Sets

A set A \subseteq \mathbb{N} is recursive if and only if both A and its complement \overline{A} are computably enumerable, allowing for a decision procedure that alternates between semi-deciders for A and \overline{A}. To decide membership of an element x in A, one dovetails the enumerations of A and \overline{A}; since exactly one of these sets contains x, the process will eventually enumerate x in one of them, confirming membership or non-membership accordingly. This equivalence, established by Post, highlights that recursive sets form a proper subclass of the computably enumerable sets, as there exist computably enumerable sets whose complements are not computably enumerable, such as the halting set. The complements of computably enumerable sets, known as co-computably enumerable (co-c.e.) sets, provide a symmetric to the computably enumerable sets. Neither properly contains the other, since for any computably enumerable set that is not recursive, its complement is co-c.e. but not computably enumerable, and . A key theorem states that a computably enumerable set A is recursive its complement \overline{A} is also computably enumerable. The forward direction follows from the definition of recursive sets, while the is proven by assuming an enumerator for \overline{A} exists alongside the one for A, the parallel enumeration procedure to terminate for every input, thus constructing a total decider for A. This result, due to , underscores the boundary between semi-decidability and full decidability. Additionally, every infinite c.e. set contains an infinite recursive .

Advanced Structures

Turing Degrees of c.e. Sets

The Turing degrees of computably enumerable (c.e.) sets, denoted \mathcal{D}_{\mathrm{c.e.}}, comprise all Turing degrees \mathbf{d} that contain at least one c.e. set, partially ordered by Turing reducibility \leq_{\mathrm{T}}. This structure captures the relative computational complexities of unsolvable problems whose positive instances can be enumerated by Turing machines. The least element is \mathbf{0}, the degree of all computable sets, while \mathbf{0}'—the degree of the K = \{ e \mid \phi_e(e) \downarrow \}—serves as the supremum of \mathcal{D}_{\mathrm{c.e.}}, since every c.e. set is Turing reducible to K. The c.e. degrees form an upper semilattice under the join operation \vee, where for c.e. degrees \mathbf{a} and \mathbf{b}, \mathbf{a} \vee \mathbf{b} is the Turing degree of the union of c.e. representatives from each, as the union of c.e. sets remains c.e.. However, \mathcal{D}_{\mathrm{c.e.}} is not a lattice: there exist incomparable c.e. degrees without a greatest lower bound in \mathcal{D}_{\mathrm{c.e.}}. The existence of such pairs was first established by Lachlan and Yates, who constructed two c.e. degrees a and b with no infimum in the structure. In the 1970s, further results by Lachlan and others, including non-splitting theorems, highlighted additional structural limitations, such as degrees that cannot be split into c.e. subdegrees above certain lower bounds. Emil Post's problem inquired whether all non-computable c.e. degrees coincide with \mathbf{0}', or equivalently, whether there exist c.e. degrees strictly between \mathbf{0} and \mathbf{0}'. This was resolved affirmatively: Friedberg and independently Muchnik constructed c.e. sets A and B such that \mathbf{0} < \deg(A), \deg(B) < \mathbf{0}' and \deg(A) \parallel_{\mathrm{T}} \deg(B), using the finite injury priority method to ensure incomparability. A related question—whether every Turing degree \leq_{\mathrm{T}} \mathbf{0}' contains a c.e. set—was answered negatively, revealing gaps in \mathcal{D}_{\mathrm{c.e.}} below \mathbf{0}'. Constructions of minimal degrees below \mathbf{0}', such as those using partial trees, yield degrees with no non-zero c.e. sets, as any c.e. set in a minimal degree above \mathbf{0} would contradict minimality. In contrast, above \mathbf{0}', the structure is complete for c.e. sets: every \geq_{\mathrm{T}} \mathbf{0}' contains a c.e. set, ensuring no analogous gaps occur in higher regions. This underscores the intricate partial of \mathcal{D}_{\mathrm{c.e.}}, with in some intervals but sparsity below the halting degree.

Productive and Creative Sets

A productively set B \subseteq \mathbb{N} is defined as a set for which there exists a total p: \mathbb{N} \to \mathbb{N} such that for every x, if W_x \subseteq B, then p(x) \in B \setminus W_x. This productive function p generates elements that witness the failure of for any computably enumerable set not fully included in B, ensuring B cannot be "avoided" by all c.e. sets in a computable way. Productive sets are necessarily non-computably enumerable, as their resists complete enumeration relative to c.e. subsets. A creative set A \subseteq \mathbb{N} is a computably enumerable set whose complement \overline{A} is productive. Equivalently, A is creative if and only if it is \Sigma_1^0-complete, meaning every c.e. set many-one reduces to A. The canonical example is the halting set K = \{ e \mid \phi_e(e) \downarrow \}, which is c.e. and \Sigma_1^0-complete; its complement \overline{K} admits a productive function derived from the universal Turing machine's enumeration, placing new indices outside enumerated sets when containment fails. Creative sets thus capture the full complexity of c.e. undecidability, serving as "maximally simple" non-recursive c.e. sets in the . Post's simple sets provide foundational examples in this context: these are infinite c.e. sets whose complements are infinite and immune, meaning the complement contains no infinite c.e. subset. While not all simple sets are creative—some reside in incomplete degrees—Post's constructions demonstrate the existence of c.e. sets that are productive in their avoidance properties, bridging to creative ones via Turing reducibility from K. Specifically, a simple set S is creative if K \leq_T S, embedding the halting problem's complexity. In , creative sets formalize limitations from . For a consistent theory T like Peano arithmetic that interprets arithmetic, the set of Gödel numbers of provable sentences in T is creative, as its complement is productive relative to the theory's proof enumeration; this follows from the theory's ability to represent c.e. sets and the undecidability of consistency. Such sets are "provably creative" within T, highlighting how formal systems inherit the non-enumerability of their own theorems. The existence of creative sets was established by Emil Post in his seminal 1944 paper, where he constructed r.e. sets with productive complements using methods to avoid infinite c.e. subsets in the complement while ensuring incompleteness. Post's work from the 1920s through the 1940s laid the groundwork for generalized recursion theory, introducing these notions to explore degrees beyond the and address pathological c.e. sets.