1
$\begingroup$

I want to know, how I can prove $\Sigma_n^0 \not= \Pi_n^0$ in the arithmetic hierarchy.

For $\Sigma_1^0$ it is easy, since the diagonal halteproblem would be one example. But how to prove it for all $n \in \mathbb{N}$.

Would be happy for any hints and help. (One hint is to use a diagonal argument, but do not know how)

$\endgroup$
  • $\begingroup$ Do you know how to prove the existence of a $\Sigma_n$-truth predicate, or a $\Sigma^0_n$-universal set? $\endgroup$ – Asaf Karagila Feb 13 '16 at 12:18
  • $\begingroup$ I know how to prove the existence of $\Sigma_n^0$ universal set, but what do you mean with $\Sigma_n^0$-truth pedicate? $\endgroup$ – DerJFK Feb 13 '16 at 12:20
  • $\begingroup$ Can you show that a $\Sigma^0_n$ universal set cannot be $\Delta^0_n$ as well (so it's not $\Pi^0_n$)? A $\Sigma_n$-truth predicate is a $\Sigma_n$-formula which takes in a Godel number of a sentence, and it is true if and only if this sentence is a true $\Sigma_n$ sentence. It's more or less a parallel of a universal set. $\endgroup$ – Asaf Karagila Feb 13 '16 at 12:23
  • $\begingroup$ You should search for "Post's theorem" which is the standard name for the theorem that establishes the arithmetical hierarchy and relates it with computability theory. The result is in many textbooks. $\endgroup$ – Carl Mummert Feb 13 '16 at 13:44

Your Answer

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

Browse other questions tagged or ask your own question.