Recursive in a $\Sigma^0_2$-singleton implies recursive

Question

I've encountered two related remarks that I can't figure out. They are:

1. If a real number is recursive in a $\Sigma^0_2$-singleton, then it is recursive;
2. This is best possible, as $\{\emptyset^{(\omega)}\}$, the singleton containing the $\omega$th Turing jump, is a $\Sigma^0_3$-singleton.

I have trouble seeing why these two statements are true. To get $\{\emptyset^{(\omega)}\}$ to be a $\Sigma^0_3$-singleton, I was thinking $\emptyset^{(\omega)}$ is the unique real $x$ satisfying something like "some program with $x$ as an oracle can compute the halting problem for each finitely iterated Turing jumps $\emptyset^n$". But the problem is that this definition does not define a unique real, and this is most likely not $\Sigma^0_3$ (probably not even arithmetical).

For definiteness, a real number $x\subseteq\omega$ is a $\Sigma^0_n$-singleton if and only if for some $\Sigma^0_n$ formula $\varphi(y)$ with a real number variable $y$, such that $x$ is the unique real number satisfying $\varphi(y)$.

Answer 1

I'll start with the second point. In fact $\emptyset^{(\omega)}$ is a $\Pi^0_2$ singleton!

Recall the precise definition of $\emptyset^{(\omega)}$ as a kind of "jump array:"

$x=\langle a,b\rangle$ is in $\emptyset^{(\omega)}$ iff $a\in \emptyset^{(b)}$.

The point is that this definition can be recast in a "local (and inductive)" way:

• The first "column" of $\emptyset^{(\omega)}$ is all $0$s.

• For each $n$, the $n+1$th "column" of $\emptyset^{(\omega)}$ is the Turing jump of the $n$th "column" of $\emptyset^{(\omega)}$.

This turns out to be $\Pi^0_2$ once fully unwound. It's probably easiest to think about this dually: to tell that a real $y$ is not the same as $\emptyset^{(\omega)}$ we EITHER see a nonzero bit in the first "column" of $y$ (which is $\exists$), OR we search for a natural number $m$ such that the $m+1$th "column" of $y$ is not the jump of the $m$th "column" of $y$ (which is $\exists(\forall\vee\exists)=\exists\forall$). So $2^\omega\setminus\{\emptyset^{(\omega)}\}$ is $\Sigma^0_2$.

(This is a bit sketchy; it's a good exercise to fill in the details, but this is worked out fully in Sacks' book Higher recursion theory, which shows more generally that every .)

---

The first point is actually less technically difficult, but I think will feel most satisfying with the above argument understood.

Suppose I have a formula $$\varphi(x)\equiv\exists m\forall n\theta(m,n,x)$$ where $m,n$ are number variables, $x$ is a set variable, and $\theta$ uses only bounded (number) quantifiers. Moreover, suppose that $\varphi$ holds of at least one real $r$.

First we "remove a quantifier:" let $u$ be a natural number such that $\forall n\theta(u,n,r)$ holds. The set $$\{s\in 2^\omega: \forall n\theta(u,n,s)\}$$ is then a nonempty $\Pi^0_1$ class. Now, when does a $\Pi^0_1$ class have exactly one element?

Note that it's crucial that we work in Cantor space here. In Baire space, it is no longer the case that $\Pi^0_1$ singletons are boring. Sacks' book cited above has some material on this.