Computably enumerable sets and quasi-reducibility

, &
Annals of Pure and Applied Logic 95 (1-3):1-35 (1998)
  Copy   BIBTEX

Abstract

We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(98)00013-x

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

My notes

Similar books and articles

Addendum to “computably enumerable sets and quasi-reducibility”.R. Downey, G. LaForte & A. Nies - 1999 - Annals of Pure and Applied Logic 98 (1-3):295.
On the filter of computably enumerable supersets of an r-maximal set.Steffen Lempp, André Nies & D. Reed Solomon - 2001 - Archive for Mathematical Logic 40 (6):415-423.
Differences of Computably Enumerable Sets.A. Nies & S. Lempp - 2000 - Mathematical Logic Quarterly 46 (4):555-562.
Every incomplete computably enumerable truth-table degree is branching.Peter A. Fejer & Richard A. Shore - 2001 - Archive for Mathematical Logic 40 (2):113-123.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
Definability, automorphisms, and dynamic properties of computably enumerable sets.Leo Harrington & Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (2):199-213.
A δ02 set with barely σ02 degree.Rod Downey, Geoffrey Laforte & Steffen Lempp - 1999 - Journal of Symbolic Logic 64 (4):1700 - 1718.
Non‐isolated quasi‐degrees.Ilnur I. Batyrshin - 2009 - Mathematical Logic Quarterly 55 (6):587-597.
Computably enumerable equivalence relations.Su Gao & Peter Gerdes - 2001 - Studia Logica 67 (1):27-59.
Codable sets and orbits of computably enumerable sets.Leo Harrington & Robert I. Soare - 1998 - Journal of Symbolic Logic 63 (1):1-28.
A $Delta^02$ Set with Barely $Sigma^02$ Degree.Rod Downey, Geoffrey Laforte & Steffen Lempp - 1999 - Journal of Symbolic Logic 64 (4):1700-1718.
Computably enumerable sets below random sets.André Nies - 2012 - Annals of Pure and Applied Logic 163 (11):1596-1610.
The computably enumerable degrees are locally non-cappable.Matthew B. Giorgi - 2004 - Archive for Mathematical Logic 43 (1):121-139.
Implicit measurements of dynamic complexity properties and splittings of speedable sets.Michael A. Jahn - 1999 - Journal of Symbolic Logic 64 (3):1037-1064.
On orbits, of prompt and low computably enumerable sets.Kevin Wald - 2002 - Journal of Symbolic Logic 67 (2):649-678.

Analytics

Added to PP
2014-01-16

Downloads
21 (#720,615)

6 months
7 (#418,426)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Hyperhypersimple sets and Q1 -reducibility.Irakli Chitaia - 2016 - Mathematical Logic Quarterly 62 (6):590-595.
Strong Enumeration Reducibilities.Roland Sh Omanadze & Andrea Sorbi - 2006 - Archive for Mathematical Logic 45 (7):869-912.
Some structural properties of quasi-degrees.Roland Sh Omanadze - 2018 - Logic Journal of the IGPL 26 (1):191-201.

View all 12 citations / Add more citations

References found in this work

Omitting quantifier-free types in generic structures.Angus Macintyre - 1972 - Journal of Symbolic Logic 37 (3):512-520.
Admissible ordinals and priority arguments.Manuel Lerman - 1973 - In A. R. D. Mathias & H. Rogers (eds.), Cambridge Summer School in Mathematical Logic. New York: Springer Verlag. pp. 311--344.
Ein Rekursiv Aufzählbarer btt-Grad, der Nicht Zum Wortproblem Einer Gruppe Gehört.Martin Ziegler - 1976 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 22 (1):165-168.

View all 7 references / Add more references