Connection between countable ordinals and Turing degrees

Question

$\omega^{CK}_1$ is the supremum of all the recursive ordinals, where an ordinal $\alpha$ is recursive if there is a computable ordering of a subset of the naturals with order type $\alpha$.

For a Turing degree $D$, we will say that an ordinal $\alpha$ is $D$-recursive if there is a $D$-computable ordering of a subset of the naturals with order type $\alpha$. We will also say that the supremum of the $D$-recursive ordinals is $\omega^{CK}_D$.

This has some interesting properties that connects Turing degrees and countable ordinals. For example, for any countable ordinal $\alpha$ there is a Turing degree $D$ such that $\alpha$ is $D$-recursive (simply choose a ordering of the natural numbers with order type $\alpha$, and construct an oracle that computes that ordering). This in particular implies that supremum of the $\omega^{CK}_D$ over all Turing degrees $D$ is $\omega_1$. Additionally, the order type of the $\omega^{CK}_D$ over all Turing degrees $D$ is also $\omega_1$. Also, for each Turing degree $D$, we can construct an ordinal notation for the ordinals $< \omega^{CK}_D$, similar to Kleene's O.

My question is, has this relationship between Turing degrees and countable ordinals been explored before?

Answer 1

The ordinals of the form $\omega_D^{CK}$, as you denote it, are exactly the countable admissible ordinals, and these ordinals are intensely studied in the context of admissible set theory and fine structure theory.

Answer 2

This concerns Noah's question. First let me formulate Noah's question more precisely.

Question: Is there a $\Pi^1_1$-degree invariant function $f: 2^{\omega}\to 2^{\omega}$ such that $\forall x\forall y(x\equiv_T y\implies f(x)=f(y))$ and for any $x$, $f(x)$ is a $\Pi^1_1(x)$-real coding a well order with order type $\omega_1^{x}$?

The question has a negative answer under $ZF+AD+DC$. First note that $f$ is uniformly degree invariant function that cannot be a constant at any upper cone of Turing degrees.

Secondly, the following lemma is clear.

Lemma: There is a natural number $n_0$ so that both $A_0=\{x\mid f(x)(n_0)=0\}$ and $A_1=\{y\mid f(x)(n_0)=1\}$ are cofinal in the Turing degrees.

Proof: Otherwise, $f$ would be a constant at an upper cone of Turing degrees.

Then $A_0$ and $A_1$ are disjoint cofinal sets of Turing degrees, a contradiction to Martin's result.

Note that to negate the question, a fragment of $PD$ is sufficient. Under full $AD$, it actually shows that there is no such function (not just $\Pi^1_1$) $f$ at all. More precisely, what we actually prove is the following.

Theorem: Assume $ZF+AD+DC$. There is no function $f$ such that $\forall x\forall y(x\equiv_Ty\implies f(x)=f(y))$ and $f(x)$ is not constant at an upper cone of Turing degrees.

At right now I don't know how to negate the question under $ZFC$. But under the assumption $V=L$, it can be proved that there is a $\Pi^1_1$-degree invariant function $f: 2^{\omega}\to 2^{\omega}$ such that $\forall x\forall y(x\equiv_T y\implies f(x)=f(y))$ and for any $x$, $f(x)$ is a real coding a well order with order type $\omega_1^{x}$.