## Higher computability : Constructive ordinal and $\Delta^1_1$ predicates

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 33, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9488143920898438, "perplexity_flag": "head"}