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
id sg-ntu-dr.10356-154823
record_format dspace
spelling sg-ntu-dr.10356-1548232022-01-11T08:50:17Z Cupping and jump classes in the computably enumerable degrees Greenberg, Noam Ng, Keng Meng Wu, Guohua School of Physical and Mathematical Sciences Science::Mathematics Array Computable 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 -cuppable degrees coincide with the array computable-cuppable degrees, giving a full understanding of the latter class. Ministry of Education (MOE) Accepted version The first author is partially supported by the Marsden Fund of New Zealand. The second author is partially supported by grant MOE2015-T2- 2-055. The third author is supported by Singapore Ministry of Education Tier 2 grant MOE2016-T2-1-083 (M4020333); NTU Tier 1 grants RG32/16 (M4011672) and RG111/19 (M4012245). 2022-01-11T08:50:17Z 2022-01-11T08:50:17Z 2020 Journal Article Greenberg, N., Ng, K. M. & Wu, G. (2020). Cupping and jump classes in the computably enumerable degrees. Journal of Symbolic Logic, 85(4), 1499-1545. https://dx.doi.org/10.1017/jsl.2020.36 0022-4812 https://hdl.handle.net/10356/154823 10.1017/jsl.2020.36 2-s2.0-85104268910 4 85 1499 1545 en MOE2016-T2-1-083 (M4020333) RG32/16 (M4011672) RG111/19 (M4012245) MOE2015-T2-2-055 Journal of Symbolic Logic © 2020 Association for Symbolic Logic. All rights reserved.
institution Nanyang Technological University
building NTU Library
continent Asia
country Singapore
Singapore
content_provider NTU Library
collection DR-NTU
language English
topic Science::Mathematics
Array Computable
Computably Enumerable Degrees
spellingShingle Science::Mathematics
Array Computable
Computably Enumerable Degrees
Greenberg, Noam
Ng, Keng Meng
Wu, Guohua
Cupping and jump classes in the computably enumerable degrees
description 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.
author2 School of Physical and Mathematical Sciences
author_facet School of Physical and Mathematical Sciences
Greenberg, Noam
Ng, Keng Meng
Wu, Guohua
format Article
author Greenberg, Noam
Ng, Keng Meng
Wu, Guohua
author_sort Greenberg, Noam
title Cupping and jump classes in the computably enumerable degrees
title_short Cupping and jump classes in the computably enumerable degrees
title_full Cupping and jump classes in the computably enumerable degrees
title_fullStr Cupping and jump classes in the computably enumerable degrees
title_full_unstemmed Cupping and jump classes in the computably enumerable degrees
title_sort cupping and jump classes in the computably enumerable degrees
publishDate 2022
url https://hdl.handle.net/10356/154823
_version_ 1722355380005109760

Similar Items