# A problem that is Turing degree greater than $0'$ and not co-re

I know that halting problem is Turing degree $0'$.

So, what degree would Co-RE complete problems be in?

And is there any problem we can formulate (<- this might be too general, but let us say in terms of writable problems) or think of that has Turing degree greater than $0'$ while not in Co-RE?

-
Assuming Co-RE means the compliment is RE, wouldn't the degree just be the set of compliments of sets/problems (you can turn a set into a problem via membership in the set, and vice-versa) in $0'$? –  Alex Becker May 21 '12 at 1:10
$A \equiv_T \omega - A$ so this would just be $\emptyset'$. –  William May 21 '12 at 1:57

Sure, anything which is $\Sigma_2^0$-complete (has degree $0''$) should suffice. For example, determining whether the set $\{x: \varphi_{n}(x)\text{ converges}\}$ is finite is $\Sigma_2^0$-complete and thus has degree greater than $0'$ and is not co-RE.

-

In terms of Turing Degrees, a set and its complement has the same Turing Degree. Therefore, any $\Sigma_1^0$ complete and $\Pi_1^0$ complete set has the same Turing Degree, $\emptyset'$.

One way of producing more complex sets in term of Turing Degrees are taking higher jumps. For example, $\emptyset'' \not\leq_T \emptyset'$ and $\emptyset''$ is not $\Sigma_1^0$ or $\Pi_1^0$.

Also to be clear, c.e. and co-c.e. are not degrees. They can either mean a set which is c.e. or co-c.e. or a degree containing such sets. There are even sets below $\emptyset'$ which are neither c.e. or co-c.e.

-