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
    @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

1

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.

0

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