5
$\begingroup$

Consider the following definition. We define the 'index' of a Turing degree $A$, (denoted $i(A)$) as the smallest ordinal $\alpha\in \omega_1$ such that $A \ngeq 0^{(\alpha)}$. [is this concept found anywhere in the literature, and if so, under what name?]

I have 2 questions relating to this concept:

1) Does the following property hold: $i(A\vee B) = \max\{i(A), i(B)\}$?

2) If $A$ is a Turing degree, and $i(A)=\alpha+1$ is a successor ordinal, then can we always write $A = X \vee 0^{(\alpha)}$ where $X$ is a Turing degree satisfying $i(X) = 1$? Is there a natural way to extend this idea to limit ordinals?

I'm suspecting that the first question is false, and the second is true, but I don't know where to start.

Improve this question
$\endgroup$
1
  • $\begingroup$ If only consider recursive ordinals, the answer to your question 2 is also yes by Posner-Robinson theorem. $\endgroup$
    – 喻 良
    Commented Jul 12, 2017 at 22:42

2 Answers 2

Reset to default
5
$\begingroup$

First, note that "$0^{(\alpha)}$" doesn't make sense unless $\alpha$ is a computable ordinal. We can do a bit better, especially via mastercodes, but that still only reaches up to $\omega_1^L$ (which might be vastly smaller than $\omega_1$).

So let's restrict attention to those Turing degrees which are not above every set of the form $0^{(\alpha)}$ for $\alpha$ a computable ordinal (that is, those Turing degrees not bounding every hyperarithmetic degree).

The answer to your first question is extremely "no:" for any computable $\alpha$, we can find sets $A, B$ neither of which computes $0'$ but such that $A\oplus B$ computes $0^{(\alpha)}$.

Proof: let $\mathbb{P}$ be the set of pairs $(p, q)$ of finite partial maps $\omega\rightarrow 2$ with the same domain $D$, such that $\{a\in D: p(a)=q(a)\}\subseteq 0^{(\alpha)}$ and $\{a\in D: p(a)\not=q(a)\}\subseteq \overline{0^{(\alpha)}}$. Now taking a sufficiently generic filter through $\mathbb{P}$ yields a pair of sets which agree precisely on $0^{(\alpha)}$ (hence whose join computes $0^{(\alpha)}$) but neither of which computes $0'$ (since each of the two sets will be sufficiently Cohen-generic).

Improve this answer
$\endgroup$
5
$\begingroup$

Even if you fix a meaning for $0^{(\alpha)}$ for every countable ordinal $\alpha$, by fixing a code for $\alpha$, say, then it still isn't necessarily the case in ZFC that every real is below one of them, and so you haven't really defined a degree notion on the degrees. The reason is that this would imply the continuum hypothesis, as there are only $\omega_1$ many countable ordinals $\alpha$, and each $0^{(\alpha)}$ would compute only countably many reals.

In this sense, the existence of a backbone sequence of length $\omega_1$ cofinal in the Turing degrees is equivalent to CH.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But I see now that you wrote $\not\geq 0^{(\alpha)}$, rather than $\leq 0^{(\alpha)}$, and so you are not actually requiring those degrees to be cofinal. Any strictly increasing $\omega_1$-sequence will indeed define an index function. $\endgroup$
    – Joel David Hamkins
    Commented Jul 12, 2017 at 18:24
  • $\begingroup$ What do you mean by "fixing a code for $\alpha$", and could you do that with only Dependent Choice? $\endgroup$
    – Dylan Pizzo
    Commented Jul 12, 2017 at 21:24
  • 1
    $\begingroup$ @Dpiz Each countable ordinal can be represented by a binary relation on (a subset of) $\mathbb{N}$; in fact, by many. These are called codes of the ordinal. For any code $c$ of $\alpha$, $0^{(c)}$ has a natural definition; the problem is that $0^{(c)}$ and $0^{(d)}$ may differ wildly, even if $c$ and $d$ are both codes for $\alpha$, if $\alpha$ is not computable. As far as choosing codes goes, this definitely requires more than just DC: the theory ZF + AD + DC proves that we can't pick codes all at once. $\endgroup$
    – Noah Schweber
    Commented Jul 12, 2017 at 22:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .