2
$\begingroup$

Everything I know on this subject comes from Sacks book : "Higher recursion theory"

Let $\mathcal{O^Y}$ be the set of codes for ordinals constructive in $Y$.

We should have the result that $A \subseteq \omega \times 2^\omega$ is $\Delta^1_1$ iff $\exists a \in \mathcal{O}\ \ \exists e \in \omega$ such that $A(n, Y) \leftrightarrow \varphi_e^{H_a^Y}(n) \downarrow$ where $H_a^Y$ is the $|a|$-th iteration of the turing jump of $Y$.

Two things are now in contradiction in my mind :

The first one :

$X$ is $\Delta^1_1(Y)$ iff $\exists a \in \mathcal{O^Y}\ \ \exists e \in \omega$ such that $n \in X \leftrightarrow \varphi_e^{H_a^Y}(n) \downarrow$. Potentially we can have $|a| \geq \omega_1^{ck}$ if $\omega_1^{Y} \geq \omega_1^{ck}$

The second one :

$X$ is $\Delta^1_1(Y)$ iff then there exists a $\Delta^1_1$ predicate $A \subseteq \omega \times 2^\omega$ and $\exists a \in \mathcal{O}\ \ \exists e \in \omega$ such that $n \in X \leftrightarrow A(n, Y) \leftrightarrow \varphi_e^{H_a^Y}(n) \downarrow$

This time, the code $a$ for the constructive ordinal is always smaller than $\omega_1^{ck}$.

Can anyone see where I made a mistake ? Thanks in advance

  • 1
    Which theorem from Sacks is the "should have" one?2012-03-23
  • 0
    Well this is not clearly stated in the Sacks, what is written is $A \subseteq 2^\omega$ is $\Delta^1_1$ iff $\exists a \in \mathcal{O}$ and $\exists e \in \omega$ such that $A(X) \leftrightarrow \varphi^{H_a^X}(0) \downarrow$. But using similar technics, I am pretty sure that one can extend this result to $\Delta^1_1$ predicate in $2^\omega \times \omega$2012-03-23
  • 0
    This can be found in II.5.6 page 44 in my version2012-03-23
  • 0
    If you want to relativize the latter result to $Y$ you would get that $A \subseteq 2^\omega$ is in $\Delta^1_1(Y)$ if there is an $a \in \mathcal{O}(Y)$ and $e \in \omega$ with $A(X) \leftrightarrow \phi_e^{H^{Y \oplus X}_a}(0)\downarrow$. In your "second case" in the question it appears you are not relativizing completely to $Y$.2012-03-23
  • 0
    Well, by definition (if not let me know) we have $A \subseteq 2^\omega$ is $\Delta^1_1(Y)$ iff there exists $P \subseteq \omega \times 2^\omega$ which is $\Delta^1_1$, such that $n \in A \leftrightarrow P(n, Y)$. And I can prove (maybe this is where I am wrong) that for any $P \subseteq \omega \times 2^\omega$ which is $\Delta^1_1$, we have some $o \in \mathcal{O}$ and $e \in \omega$ such that $P(n, X) \leftrightarrow \varphi_e^{H_o^X}(n) \downarrow$. This is not really chocking considering the result in my first comment (that $o$ can always be chosen in $\mathcal{O}$ for predicate of reals).2012-03-23
  • 0
    In the last comment it should be $A \in 2^\omega$ and not $A \subseteq 2^\omega$2012-03-23
  • 1
    That definition is not quite correct. For a set $X$ to be $\Delta^1_1(Y)$ means that there is a $\Pi^1_1$ formula $\Phi(n,Z)$ and a $\Sigma^1_1$ formula $\Psi(n,Z)$ such that for all $n$, $\Phi(n,Y) \leftrightarrow \Psi(n,Y)$, and $X = \{n : \Psi(n,Y)\}$. It may not be the case that $\Phi(n,z) \leftrightarrow \Psi(n,Z)$ for all $n$ and $Z$, it is only required for $Y$. Thus the $P$ in your question does not need to be $\Delta^1_1$, it only needs to be $\Delta^1_1(Y)$. I'm not sure if this is the issue in the question, though - please let me know if this helps.2012-03-23
  • 0
    It definitely is the issue ! Thanks a lot. In the striving to understand such complicated matters, I missed the simple things...2012-03-24

0 Answers 0