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

• Your first mistake is that if $E \not\in \Sigma_k$ then we need to have $E \in \Pi_k$. This is not the case. There are many problems that are, e.g. $\Sigma_2$-hard, meaning that these problems are neither in $\Sigma_1$ nor in $\Pi_1$. – Pål GD Jun 3 '20 at 6:43
• Let me be more explicit than @PålGD: it is not true that $\Pi_1$ is the class of sets which are not c.e. The correct statement is: $\Pi_1$ is the class of sets whose complements are c.e. (A similar mistake is sometimes made by topology students who think that a set is closed if it is not open, but that's wrong.) – Andrej Bauer Jun 3 '20 at 8:23

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"}$$

• thanks, does this mean that $E$ (as I wrote above) is really in $\Pi_2$ and not $\Pi_1$ as I thought ? – Link L Jun 3 '20 at 8:30
• Your $E$ is the same as my $\mathsf{TOT}$, which is known to be $\Pi_2$-complete. In particular, it is not in $\Pi_1$. – Yuval Filmus Jun 3 '20 at 8:54