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 (...) local nonmodularity in the computably enumerable degrees. (shrink)

In this article we show that it is possible to completely classify the degrees of r.e. bases of r.e. vector spaces in terms of weak truth table degrees. The ideas extend to classify the degrees of complements and splittings. Several ramifications of the classification are discussed, together with an analysis of the structure of the degrees of pairs of r.e. summands of r.e. spaces.

We show that for every nontrivial r.e. wtt-degree a, there are r.e. wtt-degrees b and c incomparable to a such that the infimum of a and b exists but the infimum of a and c fails to exist. This shows in particular that there are no strongly noncappable r.e. wtt-degrees, in contrast to the situation in the r.e. Turing degrees.

We show that the top of any diamond with bottom 0 in the r.e. degrees is also the top of a stack of n diamonds with bottom 0.

A set Asubset of or equal toω is called computably enumerable , if there is an algorithm to enumerate the elements of it. For sets A,Bsubset of or equal toω, we say that A is bounded Turing reducible to reducible to) B if there is a Turing functional, Φ say, with a computable bound of oracle query bits such that A is computed by Φ equipped with an oracle B, written image. Let image be the structure of the c.e. bT-degrees, (...) the c.e. degrees under the bounded Turing reductions. In this paper we study the continuity properties in image. We show that for any c.e. bT-degree image, there is a c.e. bT-degree image such that for any c.e. bT-degree image, image if and only if image. We prove that the analog of the Seetapun local noncappability theorem from the c.e. Turing degrees also holds in image. This theorem demonstrates that every image is noncappable with any nontrivial degree below some image. (shrink)

In this paper we examine a class of pairs of recursively enumerable degrees, which is related to the Slaman-Soare Phenomenon.

A computably enumerable (c.e.) degree is a maximal contiguous degree if it is contiguous and no c.e. degree strictly above it is contiguous. We show that there are infinitely many maximal contiguous degrees. Since the contiguous degrees are definable, the class of maximal contiguous degrees provides the first example of a definable infinite anti-chain in the c.e. degrees. In addition, we show that the class of maximal contiguous degrees forms an automorphism base for the c.e. degrees and therefore for the (...) Turing degrees in general. Finally we note that the construction of a maximal contiguous degree can be modified to answer a question of Walk about the array computable degrees and a question of Li about isolated formulas. (shrink)