Cupping and jump classes in the computably enumerable degrees

Cupping and jump classes in the computably enumerable degrees

We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are -cuppable, or indeed cuppable for any n, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the...

Full description

Saved in:
Bibliographic Details
Main Authors: Greenberg, Noam, Ng, Keng Meng, Wu, Guohua
Other Authors: School of Physical and Mathematical Sciences
Format: Article
Language:English
Published: 2022
Subjects:
Science::Mathematics
Array Computable
Computably Enumerable Degrees
Online Access:https://hdl.handle.net/10356/154823
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Nanyang Technological University
Language: English
Description
Summary:We show that there is a cuppable c.e. degree, all of whose cupping partners are high. In particular, not all cuppable degrees are -cuppable, or indeed cuppable for any n, refuting a conjecture by Li. On the other hand, we show that one cannot improve highness to superhighness. We also show that the -cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class.

Similar Items