3
$\begingroup$

For natural numbers $e$, $n$ and elements of Cantor space $X$ let $\{e\}^X(n)$ be the result of running the $e$th Turing machine with oracle $X$ on input $n$. Let $X'$ be the Turing jump of X.

Suppose $a$ is a fixed natural number such that for all $Y$ in Cantor space $\{a\}^{Y'}(0)$ converges. Let $$ Z = \{Y \in 2^\omega \colon \{a\}^{Y'}(0) = 0\}. $$

How complicated can $Z$ be from a descriptive set theoretic perspective?

$\endgroup$

1 Answer 1

5
$\begingroup$

Every such set is both $F_\sigma$ and $G_\delta$, i.e. ${\bf \Delta^0_2}$.

The clear upper bound is that $Y$ is in $Z$ iff for some finite string $\sigma$ such that $\{a\}^\sigma(0)\downarrow=0$ we have $\sigma\prec Y'$. The condition $\sigma\prec Y'$ is $\Pi_1\wedge\Sigma_1$ (each bit of $\sigma$ must guess the jump of $Y$ correctly), so for each specific $\sigma$ the set $J(\sigma):=\{Y:\sigma\prec Y'\}$ is the intersection of an open set and a closed set. The whole set $Z$, then, is a countable union of such sets, which is to say $F_\sigma$. Since the complement of such a $Z$ also has the same property (replace the index $a$ with an index $\hat{a}$ which outputs $0$ iff $a$ would not output $0$), the upper bound is ${\bf \Delta^0_2}$. (Note that this uses the "totality-on-jumps" hypothesis about $a$.)

To see that this is sharp, note there is an index $a$ with the such that $\{a\}^{C'}(0)\downarrow$ for all $C$ and $\{a\}^{C'}(0)\downarrow=0$ iff $C$ is a proper initial segment of $\omega$ (i.e. $C$ is a finite string of $1$s followed by an infinite string of $0$s), but the set of such $C$ is properly ${\bf \Delta^0_2}$ (being countable and not closed).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .