Recursively Enumerable Sets

Origin. Kleene, Post (1944). The semi-decidable sets and their structure. Post's problem and the priority method (Muchnik 1956, Friedberg 1957) opened the study of r.e. degrees.

Models. A set is r.e. (computably enumerable) if it can be effectively listed. Equivalently the domain of a partial recursive function, or Σ⁰₁-definable. Membership is confirmable but non-membership need not be.

Formalism.

Equivalent definitions: A r.e. iff A = dom(φ_e) for some e. iff A = ran of a total recursive function (or ∅). iff A is Σ⁰₁-definable. W_e = dom(φ_e): the e-th r.e. set.

Post's complementation: A recursive iff A and its complement are both r.e. Recursive = decidable both ways.

Halting set: K = {e : φ_e(e)↓}. r.e. but not recursive. Complete: every r.e. set ≤_m K.

Creative and simple sets: Creative: r.e. with effective witness to non-membership; ≡ complete (Myhill). Simple: r.e., co-infinite, complement contains no infinite r.e. set.

Post's problem: Is there an r.e. degree strictly between 0 and 0′? Simple/hypersimple sets do not settle it.

Priority method: Friedberg-Muchnik: build incomparable r.e. sets A, B. Requirements R_e injured finitely often (finite-injury). Yes: intermediate r.e. degrees exist.

Symbols.

Metatheory. Post (1944) proved a set recursive iff it and its complement are r.e., proved K creative, and introduced simple, hypersimple and hyperhypersimple sets in an attempt to make the complement thin enough to force incompleteness; the attempt failed, since there are simple sets of degree 0′, and Post's problem was settled instead by Muchnik (1956) and Friedberg (1957) with the finite-injury priority method, which builds Turing-incomparable r.e. sets directly. Myhill (1955) proved the creative sets are exactly the many-one complete sets and, by his isomorphism theorem, all recursively isomorphic to K. The degree structure is rich but not smooth: Sacks proved splitting (1963) and density (1964), so every nonzero c.e. degree is the join of two smaller ones and no c.e. degree is an immediate successor; Lachlan and Yates (1966) independently constructed minimal pairs, two nonzero c.e. degrees meeting at 0; and Lachlan showed the c.e. degrees are only an upper semilattice, since some pairs have no infimum. The inclusion lattice ℰ has its own theory — Friedberg (1958) constructed a maximal set, Soare (1974) proved the maximal sets form a single orbit under automorphisms of ℰ, and Harrington and Soare (1991) finally found a property definable in ℰ that forces incompleteness, vindicating Post's programme in a form he did not have.

Applies to. Undecidability proofs. Degree theory. Formal systems (theorems of an axiomatizable theory are r.e.). Logic programming semantics.

Limitations. The class is not closed under complement, and Post's complementation theorem makes that exact: a set whose complement is also r.e. is already recursive, so non-membership is never semi-decidable for anything genuinely undecidable. The degree structure is not a lattice — Lachlan's non-infimum result blocks meets — so the algebra available is only that of an upper semilattice with 0 and 0′, and the first-order theory of that semilattice is undecidable (Harrington–Shelah 1982). Index sets climb the arithmetical hierarchy without bound: {e : W_e recursive} is Σ⁰₃-complete, so even asking which r.e. sets are decidable is three quantifiers hard. Priority constructions specify their sets only through the construction, giving a recursive approximation with no bound on the number of changes and no member one can name. Nothing here has complexity content; every r.e. set is enumerable with no constraint whatever on how long the enumeration takes to produce an element.

© 2026 Lingenic LLC