1
$\begingroup$

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)

  • 0
    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?2012-03-21
  • 0
    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.2012-03-21
  • 0
    @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.2012-03-22

2 Answers 2