MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

Your Answer


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.