Recursive and Computably Enumerable Sets

The structure of computably enumerable (c.e.) sets and their Turing degrees forms the core of classical computability theory. The c.e. sets sit between the decidable sets and the full arithmetic hierarchy.

Turing Reducibility

Definition5.4Turing Reducibility

A set $A$ is Turing reducible to $B$ (written $A \leq_T B$ ) if there is a Turing machine with oracle $B$ that decides $A$ . The Turing degree of $A$ is $\deg(A) = \{B : A \leq_T B \text{ and } B \leq_T A\}$ . The degree of the computable sets is $\mathbf{0}$ , and the degree of the halting problem is $\mathbf{0}'$ .

Definition5.5Many-One Reducibility

$A$ is many-one reducible to $B$ (written $A \leq_m B$ ) if there is a total computable function $f$ with $n \in A \iff f(n) \in B$ . A c.e. set $B$ is $m$ -complete if every c.e. set is many-one reducible to $B$ . The halting problem $K$ is $m$ -complete.

Examplec.e. but not Decidable

The set $\text{Tot} = \{e : \varphi_e \text{ is total}\}$ is not c.e. (it is $\Pi^0_2$ -complete in the arithmetic hierarchy). In contrast, $K = \{e : \varphi_e(e) \downarrow\}$ is c.e. but not decidable, and $\overline{K}$ is not c.e. (if both $K$ and $\overline{K}$ were c.e., $K$ would be decidable).

Post's Problem and Priority Arguments

Definition5.6Simple Set

A c.e. set $S$ is simple if $S$ is infinite, co-infinite, and $\overline{S}$ contains no infinite c.e. subset. Post constructed simple sets as a first attempt to find incomplete c.e. degrees, but simplicity alone does not guarantee incompleteness.

RemarkPriority Method

The Friedberg-Muchnik theorem (1956-57) resolved Post's problem: there exist c.e. sets $A$ and $B$ such that $A \not\leq_T B$ and $B \not\leq_T A$ . The proof uses the finite injury priority method, where requirements are ordered by priority and may be "injured" (reset) by higher-priority requirements. This technique revolutionized computability theory.

ExampleLow and High Degrees

A c.e. degree $\mathbf{a}$ is low if $\mathbf{a}' = \mathbf{0}'$ and high if $\mathbf{a}' = \mathbf{0}''$ . The low basis theorem states that every nonempty $\Pi^0_1$ class contains a member of low degree. High degrees are those where the jump is as large as possible for c.e. degrees.