I am trying to read G.E. Sacks's book on higher order recursion theory, and he has this result (where $O$ is Kleene's $O$ and $H_x$ is a hyperarithmetic set, i.e. where we have sets of the form $H_{2^a} = (H_e)'$ for some $e$ and $'$ is the jump).
Chapter 2, Theorem 1.3: Each of the following predicates is $\Pi_1^1$:
(i) $x \in O$ and $y \in H_x$
(ii) $x \in O$ and $y \not \in H_x$
The proof for Theorem 1.3 in his book however only provides a proof for (i), which is to let $A(x)$ be the conjunction of:
- $(X)_1 = \emptyset$
- $ [a \in O \implies (X)_{2^a} = (X)'_a]$
- $[3 \cdot 5^e \in O \implies (X)_{3 \cdot 5^e} = \{ \langle x,n\rangle : x \in ( X )_{\{e\}(n)} \}$
Now, Sacks notes that the set $X^* := x \in O \text{ and } y \in H_x$ is the intersection of all solutions of $A(X)$, and that the Theorem follows from the fact that $x \in O$ is $\Pi_1^1$ and that since $X^*$ is the intersection of all solutions of $A(X)$, we have that $X^*$ is $\Pi_1^1$ (using Chapter 1, Theorem 1.6 I of his book and the fact that $A(X)$ is $\Sigma_1^1$). He then leaves the proof of (ii) to the reader, saying that the proof for (ii) is just the "the same" as (i)
However, to prove (ii), am I right to form $A'(x)$ ? where $A'(x)$ is:
- $(X)_1 = \emptyset$
- $ [a \in O \implies (X)_{2^a} \neq (X)'_a]$
- $[3 \cdot 5^e \in O \implies (X)_{3 \cdot 5^e} \neq \{ \langle x,n\rangle : x \in ( X )_{\{e\}(n)} \}$
But I am not sure if $A'(X)$ is $\Sigma_1^1$ so that I can use Chapter 1, Theorem 1.6I again to say that $A'(X)$ is $\Pi_1^1$ ... How to prove (ii) ?
Your definition of $A'$ doesn't do what you need it to do; it doesn't work to just give some set that $(X)_{2^a}$ and $(X)_{3\cdot 5^e}$ aren't equal to — you need to say what they actually are. (As a side note, it's probably best to avoid using notations like $A'$ in arguments involving the jump operator, since that's also denoted by $'$.)
Anyway, just follow Sacks's argument, but instead of using $H_x,$ use its complement $J_x = \omega \setminus H_x.$ These sets can be characterized by an effective transfinite induction on $x\in\mathscr O,$ similar to the one for $H_x:$
$$J_0=\omega$$
$$J_{2^a} = \omega \setminus \big((\omega\setminus J_a)\big)'$$
$$J_{3\cdot 5^e} = \omega\setminus\{ \langle x,n \rangle : x\not\in J_{\{e\}(n)} \}$$
(Here I'm just (1) taking the complement of the previous sets in the $J$ hierarchy to get sets in the $H$ hierarchy, (2) applying the effective transfinite induction in the $H$ hierarchy, and then (3) taking the complement again to get to the appropriate $J_x.)$
Now do the same thing that Sacks did for the $H_x$'s but use the above properties of the $J_x$'s instead when you define the set corresponding to $A.$