3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 喻 良 Jul 23 '14 at 10:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dan Turetsky Jul 23 '14 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.