Switch to: References

Citations of:

Degree theoretic definitions of the low2 recursively enumerable sets

Rod Downey & Richard A. Shore

Journal of Symbolic Logic 60 (3):727 - 756 (1995)

Add citations

You must login to add citations.

A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.details We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of${\rm{\Delta }}_2^0$functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain. Download Export citation Bookmark 3 citations
Totally ω-computably enumerable degrees and bounding critical triples.Rod Downey, Noam Greenberg & Rebecca Weber - 2007 - Journal of Mathematical Logic 7 (2):145-171.details We characterize the class of c.e. degrees that bound a critical triple as those degrees that compute a function that has no ω-c.e. approximation. Download Export citation Bookmark 8 citations
Classes bounded by incomplete sets.Kejia Ho & Frank Stephan - 2002 - Annals of Pure and Applied Logic 116 (1-3):273-295.details We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We say that a class of computably enumerable sets bounded iff there is an m-incomplete computably enumerable set A such that every set in is m-reducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded (...) Download Export citation Bookmark
On supersets of non-low sets.Klaus Ambos-Spies, Rod G. Downey & Martin Monath - 2021 - Journal of Symbolic Logic 86 (3):1282-1292.details We solve a longstanding question of Soare by showing that if ${\mathbf d}$ is a non-low $_2$ computably enumerable degree then ${\mathbf d}$ contains a c.e. set with no r-maximal c.e. superset. Download Export citation Bookmark
Embeddings of N5 and the contiguous degrees.Klaus Ambos-Spies & Peter A. Fejer - 2001 - Annals of Pure and Applied Logic 112 (2-3):151-188.details Downey and Lempp 1215–1240) have shown that the contiguous computably enumerable degrees, i.e. the c.e. Turing degrees containing only one c.e. weak truth-table degree, can be characterized by a local distributivity property. Here we extend their result by showing that a c.e. degree a is noncontiguous if and only if there is an embedding of the nonmodular 5-element lattice N5 into the c.e. degrees which maps the top to the degree a. In particular, this shows that local nondistributivity coincides with (...) Download Export citation Bookmark 4 citations
Nonbounding and Slaman triples.Steven D. Leonhardi - 1996 - Annals of Pure and Applied Logic 79 (2):139-163.details We consider the relationship of the lattice-theoretic properties and the jump-theoretic properties satisfied by a recursively enumerable Turing degree. The existence is shown of a high2 r.e. degree which does not bound what we call the base of any Slaman triple. Download Export citation Bookmark 2 citations

1