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?



Borel ranks of Turing cones
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}$.


