Degree structures of conjunctive reducibility

Archive for Mathematical Logic 61 (1):19-31 (2021)
  Copy   BIBTEX

Abstract

We show: for every noncomputable c.e. incomplete c-degree, there exists a nonspeedable c-degree incomparable with it; The c-degree of a hypersimple set includes an infinite collection of \-degrees linearly ordered under \ with order type of the integers and consisting entirely of hypersimple sets; there exist two c.e. sets having no c.e. least upper bound in the \-reducibility ordering; the c.e. \-degrees are not dense.

Other Versions

No versions found

Links

PhilArchive

    This entry is not archived by us. If you are the author and have permission from the publisher, we recommend that you archive it. Many publishers automatically grant permission to authors to archive pre-prints. By uploading a copy of your work, you will enable us to better index it, making it easier to find.

    Upload a copy of this work     Papers currently archived: 104,706

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

sQ1sQ_1 -degrees of computably enumerable sets.Roland Sh Omanadze - 2023 - Archive for Mathematical Logic 62 (3):401-417.
Hypersimplicity and semicomputability in the weak truth table degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
Q1-degrees of c.e. sets.R. Sh Omanadze & Irakli O. Chitaia - 2012 - Archive for Mathematical Logic 51 (5-6):503-515.
Completely mitotic c.e. degrees and non-jump inversion.Evan J. Griffiths - 2005 - Annals of Pure and Applied Logic 132 (2-3):181-207.
Non‐isolated quasi‐degrees.Ilnur I. Batyrshin - 2009 - Mathematical Logic Quarterly 55 (6):587-597.
Bi-Isolation in the D.C.E. Degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409 - 420.
Degree spectra of intrinsically C.e. Relations.Denis Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.

Analytics

Added to PP
2021-05-25

Downloads
23 (#1,031,444)

6 months
2 (#1,373,813)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

sQ1sQ_1 -degrees of computably enumerable sets.Roland Sh Omanadze - 2023 - Archive for Mathematical Logic 62 (3):401-417.

Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Computational complexity, speedable and levelable sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
Q1-degrees of c.e. sets.R. Sh Omanadze & Irakli O. Chitaia - 2012 - Archive for Mathematical Logic 51 (5-6):503-515.
Hyperhypersimple sets and Q1 -reducibility.Irakli Chitaia - 2016 - Mathematical Logic Quarterly 62 (6):590-595.

View all 8 references / Add more references