Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I finaly got an answer from another forum. The answer is simple, I was assuming that if $A \subseteq \omega$ is $\Delta^1_1(Y)$ it means that there is a $\Pi^1_1$ predicate $F \subseteq \omega \times 2^\omega$ and a $\Sigma^1_1$ predicate $E \subseteq \omega \times 2^\omega$ such that $\forall n\ \ A(n) \leftrightarrow F(n, Y) \leftrightarrow E(n, Y)$ and $\forall X\ \ \forall n\ \ F(n, X) \leftrightarrow E(n, X)$. But it does just mean that $\forall n\ \ F(n, Y) \leftrightarrow E(n, Y)$ which is indeed very different.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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