# Are lightface \Delta-1-1 classes of reals describable with hyperarthmetic formulae?

I'd appreciate if someone could check my reasoning. Suppose $S$ is a lightface $\Delta^1_1$ class of reals. I want to argue that there is a computable $\Delta^0_\alpha$ formula $\phi(Y)$, for $\alpha$ a computable ordinal and $Y$ a real free-variable, such that $X \in S \iff \phi(X)$. It seems to follow by a variant of the argument that $\Delta^1_1$ is the same as hyperarithmetic for sets of numbers, but I've never seen the argument made for classes of reals.

Since $S$ is $\Pi^1_1$, there is a computable tree $T_0 \subseteq 2^{<\omega}\times \omega^{<\omega}$ such that $X \in S$ iff $T_0(X)$ is well-founded. By $T_0(X)$, I mean $\{ \sigma : (X\!\!\upharpoonright_{|\sigma|}, \sigma) \in T_0\}$. Similarly, since $S$ is $\Sigma^1_1$, there is a computable tree $T_1$ such that $X \in S$ iff $T_1(X)$ is ill-founded.

So then define $T_2 = \{ (\tau, \sigma_0, \sigma_1) : |\tau| = |\sigma_0| = |\sigma_1| \wedge (\tau, \sigma_0) \in T_0 \wedge (\tau, \sigma_1) \in T_1\}$. Basically, we've glued $T_0$ and $T_1$ along their first coordinate. Then $T_2$ is a computable tree. Also, $T_2$ is well-founded, since any path through $T_2$ would project onto paths through $T_0$ and $T_1$, giving us an $X$ which is simultaneously in and out of $S$.

Now, let $\beta$ be the rank of $T_2$. Fix any $X$ with $T_0(X)$ well-founded, and let $f$ be such that $(X, f)$ is a path through $T_1$ (I'm abusing notation slightly by identifying pairs of sequences with sequences of pairs). Then $(X\!\!\upharpoonright_{|\sigma|}, \sigma) \mapsto (X\!\!\upharpoonright_{|\sigma|}, \sigma, f\!\!\upharpoonright_{|\sigma|})$ is an embedding of $T_0(X)$ into $T_2$, so the $\text{rank}(T_0(X)) \le \beta$. Similarly, $\text{rank}(T_1(X)) \le \beta$ whenever $T_1(X)$ is well-founded.

So then to decide if $X \in S$, it suffices to determine which of $T_0(X), T_1(X)$ has rank at most $\beta$. But since $T_0(X)$ and $T_1(X)$ are uniformly $X$-computable, this can be checked by $X^{(\alpha)}$ for $\alpha$ approximately $2\beta+3$. So there is a $\Delta^0_\alpha$ formula which does this.

Have I made a mistake somewhere? Or is this a standard argument that I've somehow managed to be ignorant of?

• This is a reformulation of the well known result due to Kleene which says that every $\Delta^1_1$ set of reals has a recursive Borel code. The details can be found either in Moschovakis book or Thm 2.7.2 in my joint book with CT. – 喻 良 Jul 23 '14 at 10:09

I just recognized you are asking a weaker version. Then it is even simpler. By Kleene's classical result, a real is $\Delta^1_1$ if and only if it is recursive in $0^{(\alpha)}$ for some recursive ordinal $\alpha$. Uniformly relativizing the proof, we have that a set $A$ of reals is $\Delta^1_1$ if and only if $\Phi^{x^{(\alpha)}}(0)=0$ for some fixed recursive ordinal $\alpha$ and recursive functional $\Phi$.
Your proof is essentially correct except that you have to prove that since $T_0(X)$ and $T_1(X)$ are uniformly $X$-computable, this can be checked by $X^{(\alpha)}\dots$". And to prove that claim, you have to use Kleene's method.
• Well, it's not hard to explicitly build the formula that says "this tree has rank at most $\beta$". But thank you, I'm glad to know there's a reference. – Dan Turetsky Jul 23 '14 at 13:08