2
$\begingroup$

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

$\endgroup$
11
  • 7
    $\begingroup$ Yes, of course this has been explored. Did you have a more specific question about it? $\endgroup$ Nov 15, 2017 at 3:53
  • 1
    $\begingroup$ @JoelDavidHamkins is there a reference? I couldn't find any (although I probably didn't look very hard). $\endgroup$ Nov 15, 2017 at 4:53
  • 2
    $\begingroup$ 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? $\endgroup$ Nov 15, 2017 at 15:49
  • 2
    $\begingroup$ 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. $\endgroup$ Nov 15, 2017 at 15:59
  • 1
    $\begingroup$ @JoelDavidHamkins Do you happen to know if a degree-invariant notation system exists? $\endgroup$ Nov 15, 2017 at 22:50

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.