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

Question

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 ...

Answer 1

For $k$ even, a language $L$ is in $\Pi_k$ if there exists a recursive predicate $R$ such that $$ x \in L \Longleftrightarrow \forall y_1 \exists y_2 \cdots \forall y_{k-1} \exists y_k \, R(x,y_1,\ldots,y_k) $$ The quantifiers alternate between $\forall$ and $\exists$.

When $k$ is odd, the same definition works, but the last quantifier is $\forall$: $$ x \in L \Longleftrightarrow \forall y_1 \exists y_2 \cdots \exists y_{k-1} \forall y_k \, R(x,y_1,\ldots,y_k) $$

For example, the language of all total Turing machines is $\Pi_2$ since $$ x \in \mathsf{TOT} \Longleftrightarrow \forall y \exists z \, \text{"Machine $x$ halts on input $y$ within $z$ steps"} $$

The class $\Sigma_k$ is defined in the same way, with the first quantifier being $\exists$ rather than $\forall$.

If you complement a language in $\Sigma_k$ you get one in $\Pi_k$, and vice versa. This is due to de Morgan's laws for quantifiers, and the fact that the negation of a recursive predicate is also recursive.

For example, the language of non-total Turing machines is $\Sigma_2$ since $$ x \in \mathsf{NTOT} \Longleftrightarrow x \notin \mathsf{TOT} \Longleftrightarrow \exists y \forall z \, \text{"Machine $x$ doesn't halt on input $y$ within $z$ steps"} $$