Skip to main content
added 485 characters in body
Source Link
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

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.)

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.

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.)

added 60 characters in body
Source Link
Noah Schweber
  • 21.2k
  • 10
  • 110
  • 331

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

(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.

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.

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.

Source Link
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.