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



    Upload a copy of this work     Papers currently archived: 100,601

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

$$sQ_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
22 (#965,538)

6 months
8 (#564,942)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

$$sQ_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