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)

  • $\begingroup$ I've only seen relativized pointclasses for functions on Baire space. What does it mean for $\alpha \leq_{T} \beta$, so that one element is recursive in another? $\endgroup$ Mar 21 '12 at 0:45
  • $\begingroup$ Basically, it means that the relations that describes their basic neighborhoods is recursive, i.e: $U(\alpha)=\{s: \alpha\in N(\omega^\omega,s)\}$ is recursive in $\beta$. Where $N(\omega^\omega,s)$ is a recursive presentation of Baire space. $\endgroup$
    – Rafa
    Mar 21 '12 at 11:40
  • $\begingroup$ @Isaac Solomon: a function from $\omega^\omega$ is Turing reducible to the second if and only if the graph of the first, considered as a set, is Turing reducible to the graph of the second, also considered as a set. Depending on the author, this can be a theorem or it can be the definition of Turing reducibility of functions. The key point is that the graph is computable from the function and vice-versa. $\endgroup$ Mar 22 '12 at 17:53

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.


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))$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.