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

Solution 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.