Computably enumerable sets

(1 ⇒ 2) If $A = W_e$, then $x \in A \iff \exists s\ \Phi_e(x)[s]\converge$, and the relation $\Phi_e(x)[s]\converge$ of $x$ and $s$ is primitive recursive (Proposition 1.4).

(2 ⇒ 3) Suppose $A \neq \emptyset$ and fix $a \in A$. Let $f(n) = \pi_0(n)$ if $R(\pi_0(n), \pi_1(n))$, and $f(n) = a$ otherwise. This $f$ is total computable, its values lie in $A$, and every $x \in A$ is a value: if $R(x, y)$, then $x = f(\langle x, y \rangle)$.

(3 ⇒ 4) A total function is partial, and $\emptyset$ is the range of the nowhere defined function.

(4 ⇒ 1) Let $A$ be the range of $\Phi_i$. The partial function $g(x) \simeq \mu n\ [\Phi_i(\pi_0(n))[\pi_1(n)]\converge = x]$ is partial computable, by Proposition 1.6 and Proposition 1.4. It is defined if and only if $\Phi_i(y)\converge = x$ for some $y$, that is, if and only if $x \in A$. So $A = \mathrm{dom}(g)$ is c.e.

(1 ⇒ 5) If $A = W_e$, the sequence $(W_e[s])_s$ is a c.e. approximation.

(5 ⇒ 2) If $(A_s)$ is a c.e. approximation, then $x \in A \iff \exists s\ x \in A_s$, and the relation $x \in A_s$ is computable.

The range of a total computable function is c.e. by Theorem 4.3. Conversely, let $f$ be total computable with range $A$. Define $g(0) = f(0)$, and $g(n+1) = f(m_{n+1})$, where $m_{n+1}$ is the least $m$ with $f(m) \notin \{ g(0), \dots, g(n) \}$. The search terminates since $A$ is infinite, so $g$ is total computable, and it is injective by construction. Let $m_0 = 0$. By induction on $n$, $\{ f(0), \dots, f(m_n) \} = \{ g(0), \dots, g(n) \}$: the values $f(m)$ for $m_n < m < m_{n+1}$ are already listed, by minimality of $m_{n+1}$. Hence $m_0 < m_1 < \cdots$, and every value of $f$ is a value of $g$.

By Theorem 4.3, write each c.e. set or relation as the projection of a computable relation, using a c.e. approximation for item 3.

1. If $x \in A \iff \exists s\ P(x, s)$ and $x \in B \iff \exists t\ Q(x, t)$, then $x \in A \cup B \iff \exists s\ (P(x, s) \vee Q(x, s))$, and $x \in A \cap B \iff \exists n\ (P(x, \pi_0(n)) \wedge Q(x, \pi_1(n)))$.
2. If $R(\vec x, y) \iff \exists s\ Q(\vec x, y, s)$, then $\exists y\ R(\vec x, y) \iff \exists n\ Q(\vec x, \pi_0(n), \pi_1(n))$.
3. Let $(R_s)$ be a c.e. approximation of $R$. Then $\forall z < y\ R(\vec x, z)$ holds if and only if $\exists s\ \forall z < y\ R_s(\vec x, z)$. Indeed, if each $z < y$ has a stage $s_z$ with $R_{s_z}(\vec x, z)$, then $s = \max_{z < y} s_z$ works since the approximation is increasing; the converse is clear. The relation $\forall z < y\ R_s(\vec x, z)$ of $\vec x, y, s$ is computable, by bounded quantification (Proposition 1.6).
4. Let $f = \Phi_i$ and let $(A_s)$ be a c.e. approximation of $A$. Then $x \in f^{-1}(A) \iff \exists s\ (\Phi_i(x)[s]\converge \wedge \Phi_i(x)[s] \in A_s)$, and $y \in f(A) \iff \exists x\, \exists s\ (x \in A_s \wedge \Phi_i(x)[s]\converge = y)$; both are projections of computable relations.

Write $R(x, y) \iff \exists s\ Q(x, y, s)$ with $Q$ computable, and let $g(x) \simeq \pi_0\big(\mu n\ Q(x, \pi_0(n), \pi_1(n))\big)$. The search terminates exactly when some pair $(y, s)$ satisfies $Q(x, y, s)$, that is, when $\exists y\ R(x, y)$, and then $g(x) = y$ for such a pair, so that $R(x, g(x))$.

If $f = \Phi_e$, its graph is $\{ (x, y) : \exists s\ \Phi_e(x)[s]\converge = y \}$, c.e. by Theorem 4.3. Conversely, if the graph $G$ of $f$ is c.e., apply Proposition 4.6 to $G$: the function $g$ has domain $\mathrm{dom}(f)$ and satisfies $G(x, g(x))$, that is, $g(x) = f(x)$, since $G$ is the graph of a function.

If $A$ is computable, $A = \{ x : \exists y\ \chi_A(x) = 1 \}$ is the projection of a computable relation (with a dummy variable), hence c.e.; and $\nat \setminus A$ is computable as well.

Conversely, let $A = W_a$ and $\nat \setminus A = W_b$. On input $x$, search for the least $s$ such that $x \in W_a[s]$ or $x \in W_b[s]$, and output $1$ in the first case, $0$ in the second. The search terminates, since $x$ belongs to one of the two sets and hence appears in its approximation at some stage; the two cases do not overlap, since the sets are disjoint. So this algorithm computes $\chi_A$.

$\emptyset' = \{ e : \exists s\ \Phi_e(e)[s]\converge \}$ is c.e. If its complement were c.e., then $\emptyset'$ would be computable by Proposition 4.8, contradicting Theorem 3.2.

If $f$ reduces $A$ to $B$, then $A = f^{-1}(B)$, which is c.e. by Proposition 4.5.

Let $B = W_a$. By Corollary 2.3, there is a total computable $f$ such that $\Phi_{f(x)}(y) \simeq \Phi_a(x)$ for all $x$ and $y$: the program $f(x)$ ignores its input and runs $\Phi_a$ on $x$. Then

so $f$ reduces $B$ to $\emptyset'$.

1. If $A$ is m-complete, then $\emptyset' \leq_m A$ since $\emptyset'$ is c.e. (Theorem 4.9). Conversely, if $\emptyset' \leq_m A$, every c.e. set reduces to $\emptyset'$ by Theorem 4.12, hence to $A$ by transitivity. The three sets are c.e., since $\langle e, x \rangle \in H \iff \exists s\ \Phi_e(x)[s]\converge$ and $W_e \neq \emptyset \iff \exists n\ \Phi_e(\pi_0(n))[\pi_1(n)]\converge$, and $\emptyset'$ reduces to them by Proposition 3.5.
2. By Proposition 3.5, $\nat \setminus \emptyset' \leq_m \mathrm{Tot}$, and $\emptyset' \leq_m \mathrm{Tot}$, which gives $\nat \setminus \emptyset' \leq_m \nat \setminus \mathrm{Tot}$. If $\mathrm{Tot}$ or its complement were c.e., then $\nat \setminus \emptyset'$ would be c.e. by Proposition 4.10, contradicting Theorem 4.9.