4
$\begingroup$

Does anyone know of a way of showing that a $\Sigma^0_n$-complete set is not $\Pi^0_n$ without having to appeal to $\Sigma^0_n$-universal sets?

For instance a more direct diagonalization argument to show that $\overline{\text{Tot}}$ is not $\Pi^0_2$.

Note: I'm aware that the fact that $\overline{\text{Tot}}$ is not $\Pi^0_2$ follows easily from the fact that $\text{Tot}$ is $\Pi^0_2$-complete and the recursion theorem.

$\endgroup$
0

1 Answer 1

5
$\begingroup$

Let $P$ be the complement of Tot. If $P$ was $\Pi^0_2$ then, since it is already $\Sigma^0_2$, it would be $\Delta^0_2$ and thus both $P$ and Tot would be computable from $0'$. For simplicity, identify sets with their characteristic functions.

Thus, by the limit lemma, there would be a uniformly computable sequence of functions $(f_i)$ such that $\text{Tot} = \lim_{i\to\infty} f_i$. Consider a program $e$ that does the following: on input $2^e3^n$, it returns the least $i > n$ such that $f_i(e) = 0$. On all other inputs, $e$ immediately returns 0. Now $e$ will be total if and only if there are arbitrarily large $i$ with $f_i(e) = 0$. But, because $(f_i)$ converges to Tot, there are arbitrarily large $i$ with $f_i(e) = 0$ if and only if $\lim_{i\to\infty} f_i(e) = 0$, if and only if $e$ is not in Tot. So $e$ computes a total function if and only if it is not in Tot, which is a contradiction, showing Tot (and its complement) are not $\Delta^0_2$.

Is that the sort of diagonalization you are looking for?

$\endgroup$

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.