2
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Pål GD Jun 3 at 6:43
  • 1
    $\begingroup$ 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.) $\endgroup$ – Andrej Bauer Jun 3 at 8:23
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thanks, does this mean that $E$ (as I wrote above) is really in $\Pi_2$ and not $\Pi_1$ as I thought ? $\endgroup$ – Link L Jun 3 at 8:30
  • 2
    $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Jun 3 at 8:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.