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)

Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e. vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets $B<_{\rm T}A$ such (...) that the c.e. W-degrees below that of A are disjoint from the nonzero c.e. T-degrees below that of A and comparable to that of B. (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 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.

A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to obtain results about (...) the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory. (shrink)

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.

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.

Bailey, C. and R. Downey, Tabular degrees in \Ga-recursion theory, Annals of Pure and Applied Logic 55 205–236. We introduce several generalizations of the truth-table and weak-truth-table reducibilities to \Ga-recursion theory. A number of examples are given of theorems that lift from \Gw-recursion theory, and of theorems that do not. In particular it is shown that the regular sets theorem fails and that not all natural generalizations of wtt are the same.