# What would be a not arithmetically definable language that is not Turing reducible to another given not arithmetically definable language?

I have this question I'm struggling with.

Let $A=\{<i,n>|\;n \in \phi ^{(i)}\}$. In other words, $A$ is the language defined by the set of all pairs $<i,n>$ such that $n$ is $\leq_m$ to the $i$th Turing jump. A is definitely not an arithmetically definable language, and you can prove this by contradiction.

I have to find a language, let's say $B$, that is more complex than $A$ $i.e.$ $B\nleq_T A$. I thought about $B=\{<i,n>|\;n \not\in \phi ^{(i)}\}$, but I'm not sure about my reasoning, I think an oracle turing machine with an oracle $A$ couldn't reduce to $B$..

And one last thing, do you think there exists a language that is more complex than any other (it doesn't reduce to anything)?

If you have any hints that could help me solve those two questions I would be really grateful!

• The proof of the undecidability of the halting problem relativizes, so given any language $A$, we can always find a language not reducible to $A$, which corresponds to the halting problem with an oracle to $A$. Oct 21, 2013 at 1:13
• I'm not trying to get a full answer, just a hint or two so i can know what to search for! Thanks a lot for your tips! Oct 21, 2013 at 3:20
• I guess I was wrong because for any language $L$, $L\leq_T \overline{L}$... Oct 21, 2013 at 3:45

Reiterating my comment, for each $A$ we can construct a language $A'$ (read: $A$ jump) which cannot be reduced to $A$ by taking all halting TMs with oracle access to $A$. The classical proof of the undecidability of the halting problem applies, showing that $A'$ cannot be (Turing-)reduced to $A$.