Recursively Enumerable Sets

Origin. Kleene, Post (1944). The semi-decidable sets and their structure. Post's problem and the priority method (Friedberg, Muchnik, 1956) 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.

Symbol	Unicode	Name	Meaning
W_e	—	r.e. set	dom(φ_e)
K	—	Halting set	Complete r.e. set
≤_m	—	Many-one	Reduction by f
Σ⁰₁	—	Sigma-0-1	Existential over recursive

Metatheory. r.e. sets form a lattice under inclusion. Myhill: creative sets are exactly the m-complete sets, all recursively isomorphic to K. Priority arguments yield rich degree structure below 0′.

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

Limitations. Non-membership not semi-decidable. Priority constructions intricate. Purely computability-theoretic — no complexity information.