Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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?
