Am reading a text about computability theory, and according to the text, at each level $ k$ of the arithmetical hierarchy, we have two sets, $ \Sigma_k$ and $ \Pi_k$ , where $ \Pi_k$ is defined as:

$ $ \Pi_k=co-\Sigma_k $ $

So that for $ k=0$ , we have the class of decidable sets and $ \Sigma_0=\Pi_0$ , and for $ k=1$ , we have $ \Sigma_1$ as the class of computably enumerable (c.e.) sets and $ \Pi_1$ as the class of not computably enumerable sets (not c.e.)….

Let $ L(M_e)$ denote the language recognized by Turing Machine $ M_e$ with Godel number $ e$ . I came across the following language $ E$ , where:

$ $ E=\{e|L(M_e)=\Sigma^*\}$ $

i.e. $ E$ is the language of all Turing Machine codes $ e$ that are computably enumerable. By a diagonalization argument, it can be shown that $ E$ is not c.e. This implies that:

$ $ E \in \Pi_1 $ $

However, if $ E \in \Pi_1$ , it means that $ E = co-A$ , for some $ A \in \Sigma_1$ , using the definition in the above statement… However, the complement of $ E$ is:

$ $ \overline{E}=\overline{\{e|L(M_e)=\Sigma^*\}} $ $

which (I guess) means that $ \overline{E}$ is the language of all Turing Machines $ e$ such that on some inputs, $ e$ diverges… However, it has been shown that $ \overline{E} \equiv_m K^{2}$ , i.e. $ \overline{E} \equiv_m K^K$ , so that, where given two sets $ A$ and $ B$ , we have $ A \equiv_m B$ iff $ A \leq_m B$ and $ B \leq_m A$ , and $ \leq_m$ refers to a many-to-one reduction:

$ $ \overline{E} \equiv_m K^K \in \Sigma_2 $ $

Given that $ \Sigma_2 \neq \Sigma_1$ , it looks like that $ \overline{E}$ is not computably enumerable… But doesn’t this contradict the definition of $ \Pi_1$ which states that the complement of a not c.e. set is c.e. ?

I think am missing something in my understanding of the definitions …