3
$\begingroup$

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

1 Answers 1

2

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.

  • 1
    Moschovakis's book is available [on his homepage](http://www.math.ucla.edu/~ynm/books.htm)2012-05-05