Effective complexity of $\leq_T$

Question

Remember that we say for $\alpha,\beta$ in $\omega^\omega$, that $\alpha\leq_T \beta$ if $\alpha$ is recursive in $\beta$.

Is $\leq_T$ a $\Sigma^1_1$ set, as a subset of $\omega^\omega\times \omega^\omega$?

Basically; I need this to prove that if $Q(x,y)$ is $\Pi^1_1$ then

\begin{equation} P(x) \Leftrightarrow \forall y\; (y\leq_Tx \Rightarrow Q(x,y)) \end{equation} is $\Pi^1_1$. So maybe the question above might have a negative answer; but another result such as a kind of parametrization for $\Sigma^0_1(x)$ points might work, so then the question will be if there is such a parametrization.

(All clases are lightfaced)

Answer 1

I think I found a possible solution. Basically; take a $G\subseteq \omega\times \omega\times \omega^\omega$ universal for the $\Sigma^0_1$-recursive sets of $\omega\times \omega^\omega$. We get the following:

$\alpha \leq_T \beta$ iff $\exists e \forall s(\alpha \in N(\omega^\omega,s) \Leftrightarrow G(e,s,\beta))$

We note that this is basically because saying $U(\alpha)$ is $\Sigma^0_1(\beta)$ (as in the comment above), is saying that there exists a $\Sigma^0_1$-recursive $H$ which uses $\beta$ as an oracle to check membership in $U(x)$; i.e. $\alpha \leq_T \beta$ iff $\exists H$ $\Sigma^0_1$-recursive $(s\in U(\alpha) \Leftrightarrow s\in H(\beta))$.

Answer 2

We have $\alpha \leq_T \beta$ if and only if there is an $e$ such that $\phi_e^\beta$ is total and $\alpha = \phi_e^\beta$. The Tarski-Kuratowsi algorithm for this shows that the complexity of the $\leq_T$ predicate is at most $\Sigma^0_3$.

One of the main characteristics of Turing reductions (compared to hyperarithmetical or arithmetical reductions) is that they are uniformly arithmetical in this way, and thus Turing reductions can be uniformly described by sentences in Peano arithmetic using Kleene's $T$ predicate.

The main thing that you need to know to answer this question is that the $T$ predicate is still primitive recursive when we add free function parameters to it. Thus the same analysis that shows "$\phi_e$ is total" is $\Pi^0_2$ shows that "$\phi^\beta_e$ is total" is $\Pi^{0,\beta}_2$; in both cases we have an $\forall \exists$ quantifier block in front of a primitive recursive predicate.