# Prove that $A^{(\omega)}\nleq_T A^{(n)}$

I am trying to solve Exercise 7.1.24 (i) of Computability Theory by Rebecca Weber. $$A^{(n)}$$ denotes the $$n$$-th Turing jump and $$A^{(\omega)}=\{\langle x,n\rangle: x\in A^{(n)}\}$$ the $$\omega$$-jump.

I am able to prove that $$A^{(n)}\leq_T A^{(\omega)}$$. Since $$x\in A^{(n)}\Leftrightarrow \langle x,n\rangle\in A^{(\omega)}$$ we get that $$\chi_{A^{(n)}}(x)=\chi_{A^{(\omega)}}(x,n)$$, which is computable. Hence, $$A^{(n)}$$ is $$A^{(\omega)}$$-computable, i.e. $$A^{(n)}\leq_T A^{(\omega)}$$.

I now want to show that $$A^{(\omega)}\nleq_T A^{(n)}$$. My idea was to use the Jumping Theorem which says that $$A^{(n+1)}\nleq_T A^{(n)}$$ but I couldn't find a way to do so.

• You've shown that $A^{(n)}\leq_TA^{(\omega)}$ for arbitrary $n$, so you've shown that $A^{(n+1)}\leq_TA^{(\omega)}$. Now just use transitivity of $\leq_T$. – Steven Stadnicki May 4 '20 at 15:27
• Ahh, thank you very much! – thehardyreader May 4 '20 at 15:29
• Here, let me make that a proper answer... :P – Steven Stadnicki May 4 '20 at 15:29

This can also be done from first principles, but the easiest way is to use what you've already shown. Since you've shown that $$A^{(n)}\leq_TA^{(\omega)}$$ for arbitrary $$n$$, you also know that $$A^{(n+1)}\leq_TA^{(\omega)}$$. Now, if it were the case that $$A^{(\omega)}\leq_TA^{(n)}$$, then by transitivity of $$\leq_T$$ you would have $$A^{(n+1)}\leq_TA^{(n)}$$, which you already know to be false.