10
$\begingroup$

Below, $W_e$ is the $e$th c.e. set according to some appropriate list of such.

In a very loose analogy with Hausdorff gaps, say that an effective gap is a pair of computable sequences $(c_i)_{i\in\mathbb{N}},(d_i)_{i\in\mathbb{N}}$ such that

  • for all $i$ we have $W_{c_i}<_TW_{c_{i+1}}<_TW_{d_{i+1}}<_TW_{d_i}$, and

  • ("unfilled") there is no $e$ such that $W_{c_i}<_TW_e<_TW_{d_i}$ for all $i\in\mathbb{N}$.

Additionally, if $W_a<_TW_b$, say that an effective $(a,b)$-gap is an effective gap where each $W_{c_i}$ and $W_{d_i}$ is in the interval $(W_a,W_b)$.

My main question is whether we can find effective gaps "appropriately densely," in the following sense:

Question: Is it the case that, for every $W_a<_TW_b$, there is an effective $(a,b)$-gap?

I suspect the answer is affirmative, but in fact it's not obvious to me that any effective gaps exist in the first place.

EDIT: here are two further questions which run into the same sorts of difficulties (so answers to them might help indicate an answer to this question): is there a comptable set of indices giving a maximal chain, or a maxmial antichain, of c.e. Turing degrees? (Really, any problem of the form "is there a computable set of indices giving a maximal [---] in the c.e. degrees" seems to face the same issues, and I'm not aware of results of this type in the literature.)

Improve this question
$\endgroup$
2
  • $\begingroup$ I suspect you might be able to modify the proof of the special case (of the theorem that all countable linear orders are embeddable in the c.e. degrees) that $\omega+\omega^*$ is embeddable to at least show that effective gaps exist. $\endgroup$
    – Steven Stadnicki
    Commented Apr 27 at 20:05
  • 1
    $\begingroup$ @StevenStadnicki Certainly it's easy to embed $\omega+\omega^*$ in any interval, just using Sacks density. The issue is the second bulletpoint, the "unfillability" - put another way, I see no easy way to prevent an embedding $f:\omega+\omega^*\rightarrow\mathcal{R}$ from extending to an embedding $g: \omega+1+\omega^*\rightarrow\mathcal{R}$. (Here $\mathcal{R}$ is the set of c.e. Turing degrees.) $\endgroup$
    – Noah Schweber
    Commented Apr 27 at 20:10

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .