Turing jump cofinal sets

120 Views Asked by At

This is a question about computability theory, so $\le_T$ denotes Turing reducibility and $x'$ denotes the Turing jump of $x$.

A set $A\subset 2^\omega$ is said to be Turing cofinal if for all $x\in2^\omega$ there is some $y\in A$ such that $x\le_T y$. On the other hand, I say that $A\subset 2^\omega$ is Turing jump cofinal if for all $x\in2^\omega$ there is some $y\in A$ such that $x\le_T y'$. (Note that the latter is not standard terminology).

An interesting question is: can a set $A\subset2^\omega$ be Turing jump cofinal even if it is not Turing cofinal?

This question is equivalent to the following: are there any Turing cones whose complement is Turing jump cofinal? (A Turing cone is a set of the form $\{x\in2^\omega:x\ge_T y\}$ for some $y$).

1

There are 1 best solutions below

1
On BEST ANSWER

For simplicity, I'll talk about sets of degrees instead of sets of reals.

The answer is yes. The simplest answer is to observe that Friedberg's jump inversion theorem can be made cone-avoiding: it's not hard to tweak the original proof to show that for every $a\ge_T0'$ and every $b>_T0$ there is some $x$ with $x'=a$ and $x\not\ge_Tb$ (see Exercise 4.18 in Lerman's book). This proves:

The complement of any nontrivial upper cone is jump cofinal, while obviously having jump cofinal (indeed, Turing cofinal) complement and not being Turing cofinal.

A much cooler solution can be gotten, however. Cooper's jump inversion theorem states that any Turing degree above $0'$ is the jump of a minimal Turing degree. This shows:

The set of minimal Turing degrees is jump cofinal, while obviously having jump cofinal (indeed, Turing cofinal) complement and not being Turing cofinal.

That covers the easiest and, in my opinion, the coolest solutions to your question. Other examples can be gotten by employing other jump inversion theorems.