Skip to main content
1 of 3
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

"Effective gaps" in the c.e. degrees

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

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

(Here $W_e$ is the $e$th c.e. set according to some appropriate list of such.) 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.

Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331