Logical Approaches to Computational Barriers

Joining to High Degrees

Speaker:
| Jiang Liu |

Author(s): |
Guohua Wu and Jiang Liu |

Slot: |
Array, 11:20-11:40, col. 3 |

Cholak, Groszek and Slaman proved that there is a nonzero computably enumerable (c.e.) degree cupping every low c.e. degree to a low c.e. degree. In the same paper, they pointed out that every nonzero c.e. degree can cup a low$_2$ c.e. degree to a nonlow$_2$ degree. Later, Jockusch, Li and Yang improved the latter result by showing that every nonzero c.e. degree $\mathbf{c}$ is cuppable to a high c.e. degree by a low$_{2}$ c.e. degree $\mathbf{b}$. It is natural to ask in which subclass of low$_2$ c.e. degrees can $\mathbf{b}$ in Jockusch, Li and Yang's result be located in. Wu improved that $\mathbf{b}$ can be cappable. We prove in this paper that ${\bf b}$ can even be noncuppable, improving both Jockusch, Li and Yang, and Wu's results.

websites: Arnold Beckmann | 2008-06-03 |