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)

Cooper proved in [S.B. Cooper, Strong minimal covers for recursively enumerable degrees, Math. Logic Quart. 42 191–196] the existence of a c.e. degree with a strong minimal cover . So is the greastest c.e. degree below . Cooper and Yi pointed out in [S.B. Cooper, X. Yi, Isolated d.r.e. degrees, University of Leeds, Dept. of Pure Math., 1995. Preprint] that this strongly minimal cover cannot be d.c.e., and meanwhile, they proposed the notion of isolated degrees: a d.c.e. degree is isolated (...) by a c.e. degree if is the greatest c.e. degree below , and we also say that isolates . In [G. Wu, Bi-isolation in the d.c.e. degrees, J. Symbolic Logic 69 409–420], Wu extended Cooper–Yi’s notion and proved that there are intervals of d.c.e. degrees containing exactly one c.e. degree . Following Cooper and Yi’s notion, is called a bi-isolating degree. The bi-isolating degrees are dense in the high c.e. degrees. Arslanov asked whether the bi-isolating degrees occur in every jump class. In this paper, we prove that there are low bi-isolating degrees, providing a partial solution to Arslanov’s question. (shrink)

A set A is symmetric enumeration (se-) reducible to a set B (A ≤\sb se B) if A is enumeration reducible to B and \barA is enumeration reducible to \barB. This reducibility gives rise to a degree structure (D\sb se) whose least element is the class of computable sets. We give a classification of ≤\sb se in terms of other standard reducibilities and we show that the natural embedding of the Turing degrees (D\sb T) into the enumeration degrees (D\sb e) (...) translates to an embedding (ι\sb se) into D\sb se that preserves least element, suprema, and infima. We define a weak and a strong jump and we observe that ι\sb se preserves the jump operator relative to the latter definition. We prove various (global) results concerning branching, exact pairs, minimal covers, and diamond embeddings in D\sb se. We show that certain classes of se-degrees are first-order definable, in particular, the classes of semirecursive, Σ\sb n ⋃ Π\sb n, Δ\sb n (for any n \in ω), and embedded Turing degrees. This last result allows us to conclude that the theory of D\sb se has the same 1-degree as the theory of Second-Order Arithmetic. (shrink)

Calhoun, W.C., Incomparable prime ideals of recursively enumerable degrees, Annals of Pure and Applied Logic 63 39–56. We show that there is a countably infinite antichain of prime ideals of recursively enumerable degrees. This solves a generalized form of Post's problem.

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.

By constructing a maximal incomplete d.r.e. degree, the nondensity of the partial order of the d.r.e. degrees is established. An easy modification yields the nondensity of the n-r.e. degrees and of the ω-r.e. degrees.

This paper analyzes several properties of infima in Dn, the n-r.e. degrees. We first show that, for every n> 1, there are n-r.e. degrees a, b, and c, and an -r.e. degree x such that a < x < b, c and, in Dn, b c = a. We also prove a related result, namely that there are two d.r.e. degrees that form a minimal pair in Dn, for each n < ω, but that do not form a minimal pair (...) in Dω. Next, we show that every low r.e. degree branches in the d.r.e. degrees. This result does not extend to the low2 r.e. degrees. We also construct a non-low r.e. degree a such that every r.e. degree b a branches in the d.r.e. degrees. Finally we prove that the nonbranching degrees are downward dense in the d.r.e. degrees. (shrink)

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies [14] and denoted by A≤LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes (...) induced by ≤LK are called LK degrees and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity. We show that with respect to ≤LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications. (shrink)

We exhibit a finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees. Our method promises to lead to a full characterization of the finite lattices embeddable into the enumerable 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.

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.

We present a necessary and sufficient condition for the embeddability of a finite principally decomposable lattice into the computably enumerable degrees preserving greatest element.

We prove that for any computably enumerable degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c d = 0′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.

We solve a question of McLaughlin by showing that if A is a regressive co-simple isol, there is a co-simple regressive isol B such that the intersection type of A and B is trivial. The proof is a nonuniform 0 priority argument that can be viewed as the execution of a single strategy from a 0-argument. We establish some limit on the properties of such pairs by showing that if AxB has low degree, then the intersection type of A and (...) B cannot be trivial. (shrink)

Let b and c be r.e. Turing degrees such that b>c. We show that there is an r.e. degree a such that b>a>c and all lattices containing a critical triple, including the lattice M5, cannot be embedded into the interval [c, a].

We define a class of finite partial lattices which admit a notion of rank compatible with embedding constructions, and present a necessary and sufficient condition for the embeddability of a finite ranked partial lattice into the computably enumerable degrees.

Ambos-Spies, K. and R.A. Shore, Undecidability and 1-types in the recursively enumerable degrees, Annals of Pure and Applied Logic 63 3–37. We show that the theory of the partial ordering of recursively enumerable Turing degrees is undecidable and has uncountably many 1-types. In contrast to the original proof of the former which used a very complicated O''' argument our proof proceeds by a much simpler infinite injury argument. Moreover, it combines with the permitting technique to get similar results for any (...) ideal of the r.e. degrees. (shrink)