# Connection between countable ordinals and Turing degrees

$\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?

• Yes, of course this has been explored. Did you have a more specific question about it? – Joel David Hamkins Nov 15 '17 at 3:53
• @JoelDavidHamkins is there a reference? I couldn't find any (although I probably didn't look very hard). – PyRulez Nov 15 '17 at 4:53
• One quibble: I don't believe that you can in fact generalize Kleene's $\mathcal{O}$ to arbitrary Turing degrees - while $\mathcal{O}^X$ makes sense for any set $X$, I don't see any way to get a notation system which is degree-invariant. @JoelDavidHamkins Do you know if such a thing exists? – Noah Schweber Nov 15 '17 at 15:49
• Interestingly, of course the map $X\mapsto\omega_1^{CK}(X)$ is degree-invariant. There are a couple ways to state this: one is that $X\equiv_TY$ implies $\sup\{\mu_X(n): n\in\mathcal{O}^X\}=\sup\{\mu_Y(n): n\in\mathcal{O}^Y\}$ where $\mathcal{O}^X,\mu_X$ are the usual notation system and valuation map assigned to $X$ a la Kleene and another is that if $X\equiv_TY$ then an ordinal $\alpha$ - identified with the structure $(\alpha; <)$ - has a copy computable in $X$ iff it has a copy computable in $Y$). Lesson: when relativizing concepts, we have to be very careful about uniformity issues. – Noah Schweber Nov 15 '17 at 15:59
• @JoelDavidHamkins Do you happen to know if a degree-invariant notation system exists? – Noah Schweber Nov 15 '17 at 22:50

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.

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}$.