[proofplan] We first prove directly that a simple computably enumerable set cannot be computable: if it were computable, its infinite complement would itself be an infinite computably enumerable subset of the complement, contradicting immunity. This places every simple set strictly above the computable degree $0_T$. We then cite Post's [complete simple set theorem](/theorems/5431), which supplies a simple computably enumerable set of complete degree $0_T'$. These two facts show that simplicity excludes computability but does not exclude completeness, so it cannot characterize precisely the intermediate computably enumerable degrees. [/proofplan] [step:Show that every simple computably enumerable set has nonzero degree] Let $A \subset \mathbb{N}$ be a simple computably enumerable set. Suppose, toward a contradiction, that $A$ is computable. Then its complement \begin{align*} \overline{A} := \mathbb{N} \setminus A \end{align*} is computable, hence computably enumerable. Since $A$ is simple, $\overline{A}$ is infinite. Therefore $\overline{A}$ is an infinite computably enumerable subset of $\overline{A}$, contradicting the defining immunity condition for simplicity. Thus $A$ is not computable. Let $\deg_T(A)$ denote the Turing degree of $A$. A set has degree $0_T$ precisely when it is computable. Since $A$ is not computable, we have \begin{align*} \deg_T(A) \neq 0_T. \end{align*} Because $A$ is computably enumerable, this says that every simple computably enumerable set has nonzero computably enumerable degree. [guided] Let $A \subset \mathbb{N}$ be simple. The definition of simplicity contains three pieces of information: $A$ is computably enumerable, the complement $\mathbb{N} \setminus A$ is infinite, and the complement is immune, meaning that it contains no infinite computably enumerable subset. We prove noncomputability by contradiction. Assume that $A$ is computable. Define the complement of $A$ by \begin{align*} \overline{A} := \mathbb{N} \setminus A. \end{align*} Since computable sets are closed under complement, $\overline{A}$ is computable. Every computable set is computably enumerable, so $\overline{A}$ is computably enumerable. But simplicity also says that $\overline{A}$ is infinite. Hence $\overline{A}$ itself is an infinite computably enumerable subset of $\overline{A}$. This contradicts the immunity clause in the definition of simplicity. The contradiction came from assuming that $A$ was computable, so $A$ is not computable. Finally, the computable Turing degree $0_T$ consists exactly of the computable sets. Therefore, if $\deg_T(A)$ denotes the Turing degree of $A$, then \begin{align*} \deg_T(A) \neq 0_T. \end{align*} Thus every simple computably enumerable set has nonzero computably enumerable degree. [/guided] [/step] [step:Use Post's complete simple set theorem to obtain a simple set of complete degree] We use Post's complete simple set theorem as a standard external result in computability theory: there exists a set $S \subset \mathbb{N}$ such that $S$ is simple, computably enumerable, and Turing complete. Here Turing complete means that $K \leq_T S$ for a fixed Turing-complete computably enumerable set $K \subset \mathbb{N}$, and since $S$ is itself computably enumerable this is equivalent to \begin{align*} \deg_T(S) = 0_T'. \end{align*} Thus there is a simple computably enumerable set of complete degree. [guided] The previous step showed that simplicity forces noncomputability, but it did not rule out the possibility that simple sets might still all have intermediate degree. To rule that out, we need an example at the top c.e. degree. We invoke Post's complete simple set theorem, a standard theorem of computability theory. Its conclusion is that there exists a set $S \subset \mathbb{N}$ with the following three properties: $S$ is computably enumerable, $S$ is simple, and $S$ is Turing complete. There are no extra hypotheses to verify here beyond the ambient setting of computably enumerable subsets of $\mathbb{N}$, because the theorem is an existence theorem in that setting. Let $K \subset \mathbb{N}$ denote a fixed Turing-complete computably enumerable set. Turing completeness of $S$ means that $K \leq_T S$. Since $S$ is computably enumerable, its Turing degree is a c.e. degree; since $K$ has degree $0_T'$ and $K \leq_T S$, the c.e. degree of $S$ is at least $0_T'$. No c.e. degree is strictly above $0_T'$, so \begin{align*} \deg_T(S) = 0_T'. \end{align*} Therefore [Post's theorem](/theorems/5425) supplies a simple computably enumerable set whose degree is complete, not intermediate. [/guided] [/step] [step:Conclude that simplicity does not characterize intermediate computably enumerable degrees] An intermediate computably enumerable degree is a computably enumerable degree $d$ satisfying \begin{align*} 0_T < d < 0_T'. \end{align*} The first step shows that every simple computably enumerable set has degree strictly above $0_T$. The second step gives a simple computably enumerable set $S$ whose degree is exactly $0_T'$, not strictly below $0_T'$. Hence the class of simple computably enumerable sets is not the same as the class of computably enumerable sets of intermediate degree. Therefore simplicity alone does not characterize the intermediate computably enumerable degrees. [guided] By definition, an intermediate computably enumerable degree is a computably enumerable degree $d$ satisfying \begin{align*} 0_T < d < 0_T'. \end{align*} The [first inequality](/theorems/2897) says that the degree is noncomputable; the second says that it is not complete. The first step proves that if $A \subset \mathbb{N}$ is simple and computably enumerable, then \begin{align*} \deg_T(A) \neq 0_T. \end{align*} So simplicity does imply the left-hand part of being intermediate: simple computably enumerable sets cannot have computable degree. The second step proves that there is a simple computably enumerable set $S \subset \mathbb{N}$ such that \begin{align*} \deg_T(S) = 0_T'. \end{align*} This violates the right-hand strict inequality required for intermediate degree. Thus simplicity allows complete degree as well as nonzero degree. Consequently, the property of being simple cannot characterize exactly the computably enumerable sets of intermediate degree. [/guided] [/step]