Higher computability : Constructive ordinal and $\Delta^1_1$ predicates - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T19:57:05Z http://mathoverflow.net/feeds/question/91939 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/91939/higher-computability-constructive-ordinal-and-delta1-1-predicates Higher computability : Constructive ordinal and $\Delta^1_1$ predicates Archimondain 2012-03-22T18:49:48Z 2012-03-25T21:14:06Z <p>Everything I know on this subject comes from Sacks book : "Higher recursion theory"</p> <p>Let $\mathcal{O^Y}$ be the set of codes for ordinals constructive in $Y$.</p> <p>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$.</p> <p>Two things are now in contradiction in my mind :</p> <p>The first one :</p> <p>$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}$</p> <p>The second one :</p> <p>$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$</p> <p>This time, the code $a$ for the constructive ordinal is always smaller than $\omega_1^{ck}$.</p> <p>Can anyone see where I made a mistake ? Thanks in advance</p> http://mathoverflow.net/questions/91939/higher-computability-constructive-ordinal-and-delta1-1-predicates/92201#92201 Answer by Archimondain for Higher computability : Constructive ordinal and $\Delta^1_1$ predicates Archimondain 2012-03-25T21:14:06Z 2012-03-25T21:14:06Z <p>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.</p>