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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

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

Q1-degrees of c.e. sets.R. Sh Omanadze & Irakli O. Chitaia - 2012 - Archive for Mathematical Logic 51 (5-6):503-515.
Hypersimplicity and semicomputability in the weak truth table degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
Embeddings in the Strong Reducibilities Between 1 and npm.Phil Watson - 1997 - Mathematical Logic Quarterly 43 (4):559-568.
Wtt-degrees and t-degrees of R.e. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Lattice embeddings and array noncomputable degrees.Stephen M. Walk - 2004 - Mathematical Logic Quarterly 50 (3):219.
1-reducibility inside an m-degree with maximal set.E. Herrmann - 1992 - Journal of Symbolic Logic 57 (3):1046-1056.
Non‐isolated quasi‐degrees.Ilnur I. Batyrshin - 2009 - Mathematical Logic Quarterly 55 (6):587-597.
Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
Bounded enumeration reducibility and its degree structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
Strong polynomial-time reducibility.Juichi Shinoda - 1997 - Annals of Pure and Applied Logic 84 (1):97-117.
Kleene index sets and functional m-degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.

Analytics

Added to PP
2021-05-25

Downloads
8 (#1,287,956)

6 months
5 (#629,136)

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.
Q1-degrees of c.e. sets.R. Sh Omanadze & Irakli O. Chitaia - 2012 - Archive for Mathematical Logic 51 (5-6):503-515.
Computational complexity, speedable and levelable sets.Robert I. Soare - 1977 - Journal of Symbolic Logic 42 (4):545-563.
Hyperhypersimple sets and Q1 -reducibility.Irakli Chitaia - 2016 - Mathematical Logic Quarterly 62 (6):590-595.

View all 8 references / Add more references