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?



Are lightface \Delta-1-1 classes of reals describable with hyperarthmetic formulae?
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.


