# Proof of a Theorem in Gao's 'Invariant Descriptive Set Theory'

Theorem 1.7.5 on p.35 of Gao's Invariant Descriptive Set Theory reads

Theorem 1.7.5 (Kleene)
If $A\subseteq X \times \omega^{\omega}$ is $\Pi^{1}_{1}$ and $$x \in B \Longleftrightarrow \exists y \in \Delta^{1}_{1}(x)\; (x,y) \in A,$$ then $B$ is also $\Pi^{1}_{1}$.

Here $X = \omega^{m} \times (\omega^\omega)^n$ for some $m$ and $n$ (or equivalently, $X=\omega^\omega$, I suppose).

Where can I find a proof of this result? Feel free to just prove it here.

I checked the bibliography, and, though it seems impossible, there are no references to Kleene; it goes straight from "Kelly" to "Louveau".

-
add comment

## 1 Answer

This is the Socalled Spector-Gandy's theorem. A proof can be found in higher recursion theory by Sacks or descriptive set theory by Moschovakis.

-
Moschovakis's book is available on his homepage –  t.b. May 5 '12 at 16:25
Thanks a lot, Liang. –  Quinn Culver May 6 '12 at 13:13
add comment