Borel ranks of Turing cones

Question

For a non recursive $x \in 2^{\omega}$, define $C_x = \{y \in 2^{\omega}: x \leq_T y\}$. Note that $y \in C_x$ iff $(\exists e)(\forall n)(\Phi^y_e(n) = x(n))$ where $\Phi_e$ is the $e$th Turing functional. So $C_x$ is a $G_{\delta \sigma}$-set (countable union of countable intersection of open sets). Can we show that it isn't an $F_{\sigma \delta}$-set?

Answer 1

Assume $x$ is noncomputable, as otherwise it isn't true. Fix a $G_{\delta\sigma}$ set $\bigcup_i \bigcap_j A_{i,j}$, where the $A_{i,j}$ are open. We'll show that this is not the complement of $C_x$ by building a real $y$ which is either in both sets or in neither. This will be a finite extension argument; I think it would be more elegant to rework it into a forcing argument, but that would be more complicated to write.

We're going to identify $2^{\omega}$ with $2^{\omega\times\omega\times\omega}$ by pairing, so we can think of $y$ as a binary function on triples. The general shape of $y$ is the following: if $i$ is least with $y \in \bigcap_j A_{i,j}$, then there will be an $n_0^i$ used to code $x(0)$. Specifically, there will be a unique value $b$ with $y(i, n_0^i, b) = 1$, and the parity of $b$ will code $x(0)$, and we define $n_1^i = \lfloor b/2\rfloor$. Then $n_1^i$ codes $x(1)$ in the same way. In this way, each column codes a value of $x$ and tells you the next column to look at. Note that if this happens, then $y$ computes $x$ by starting at $n_0^i$, searching for the $b$, and continuing.

If $y \not \in \bigcup_i \bigcap_j A_{i,j}$, then we need to diagonalize against all functionals $\Phi_e$ to ensure $\Phi_e^y \neq x$.

So we have requirements $R_i$ and $N_e$ for attempting to meet these, which we order $R_0, N_0, R_1, N_1, \dots$, and we proceed one at a time.

An $R_i$ requirement starts by picking a large $n_0^i$ and looking for an extension into $A_{i,0}$ that only puts $0$s on the $(i, n_0^i)$ column (and also only 0s on the $(i', n_{j_{i'}}^{i'})$ columns, for $i' < i$; see later). If there is such an extension, it extends to that, then extends further to put a 1 on $(i, n_0^i, b)$ for an appropriate large $b$, thus defining $n_1^i$, and repeats with $n_1^i$.

If it gets stuck at some $j_i$ without an appropriate extension, we require that the $(i, n_{j_i})$ column contain only 0s, and then we move on to the $N_i$ requirement.

The $N_e$ requirement looks for an extension $\tau$ and $m$ with $\Phi_e^{\tau}(m)\!\!\downarrow \neq x(m)$, and with $\tau$ containing only 0s on the $(i, n^i_{j_i})$ columns for $i \le e$. If there is such an extension, we take it. Otherwise, we must have already forced that $\Phi_e^y$ is partial, as otherwise $x$ is computable by searching all extensions $\tau$ with $0$s on the appropriate columns and believing any computation $\Phi_e^\tau(m)$ we see.

Either way, we then move on to $R_{e+1}$.

If $y \in \bigcup_i \bigcap_j A_{i,j}$, then fix the least $i$ with $y \in \bigcap_j A_{i,j}$. There is always an extension of the sort $R_i$ is looking for (in particular, some initial segment of $y$ suffices), so we stay forever at $R_i$, defining every $n_j^i$. As discussed above, this means $y \in C_x$.

If $y \not \in \bigcup_i \bigcap_j A_{i,j}$, then for every $i$ there is a least $j_i$ with $y \not \in A_{i, j_i}$. Then $R_i$ must get stuck at this $j_i$ and proceed to $N_i$. So every $N_e$ is addressed, ensuring $y \not \in C_x$.

Either way, $y$ witnesses that $2^\omega \setminus C_x \neq \bigcup_i \bigcap_j A_{i, j}$, so $C_x$ is not $F_{\sigma\delta}$.