# How to understand definition of $\Pi_k$ in arithmetical heirarchy

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 …

Posted on Categories proxies