In this paper, we first prove that there exist computably enumerable (c.e.) degrees a and b such that ${\bf a\not\leq b}$ , and for any c.e. degree u, if ${\bf u\leq a}$ and u is cappable, then ${\bf u\leq b}$ , so refuting a conjecture of Lempp (in Slaman [1996]); secondly, we prove that: (A. Li and D. Wang) there is no uniform construction to build nonzero cappable degree below a nonzero c.e. degree, that is, there is no computable function (...) $f$ such that for all $e\in\omega,$ (i) $W_{f(e)}\leq_{\rm T}W_e$ , (ii) $W_{f(e)}$ has a cappable degree, and (iii) $W_{f(e)}\not\leq_{\rm T}\emptyset$ unless $W_e\leq_{\rm T}\emptyset.$. (shrink)

We give an algorithm for deciding whether an embedding of a finite partial order [Formula: see text] into the enumeration degrees of the [Formula: see text]-sets can always be extended to an embedding of a finite partial order [Formula: see text].

Say that a d.c.e. degree d is nonisolated if for any c.e. degree a

Download  

 

Export citation  

 

Bookmark   2 citations  

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)

Examining various kinds of isolation phenomena in the Turing degrees, I show that there are, for every n>0, (n+1)-c.e. sets isolated in the n-CEA degrees by n-c.e. sets below them. For n≥1 such phenomena arise below any computably enumerable degree, and conjecture that this result holds densely in the c.e. degrees as well. Surprisingly, such isolation pairs also exist where the top set has high degree and the isolating set is low, although the complete situation for jump classes remains unknown.

A set of natural numbers is called d.r.e. if it may be obtained from some recursively enumerable set by deleting the numbers belonging to another recursively enumerable set. Sacks showed that for each non-recursive recursively enumerable set A there are disjoint recursively enumerable sets B, C which cover A such that A is recursive in neither A ∩ B nor A ∩ C. In this paper, we construct a counterexample which shows that Sacks's theorem is not in general true when (...) A is d.r.e. rather than r.e. (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)

Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a low c.e. degree isolating (...) a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 259–266]; there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 31–51]. (shrink)

We prove that there is no maximal low d.c.e degree.

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.

The Turing degrees of infinite levels of the Ershov hierarchy were studied by Liu and Peng [8]. In this paper, we continue the study of Turing degrees of infinite levels and lift the study of density property to the levels beyond ω2. In doing so, we rely on notations with some nice properties. We introduce the concept of normalizing notations and generate normalizing notations for higher levels. The generalizations of the weak density theorem and the nondensity theorem are proved for (...) higher levels in the Ershov hierarchy. Furthermore, we also investigate the minimal degrees in the infinite levels of the Ershov hierarchy. (shrink)

We give some new examples of possible degree spectra of invariant relations on Δ 0 2 -categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ 0 2 (...) -categorical computable structure is either intrinsically computable or has infinite degree spectrum. This condition also allows us to use the proof of a result of Moses [23] to establish the same result for computable relations on computable linear orderings. We also place our results in the context of the study of what types of degree-theoretic constructions can be carried out within the degree spectrum of a relation on a computable structure, given some restrictions on the relation or the structure. From this point of view we consider the cases of Δ 0 2 -categorical structures, linear orderings, and 1-decidable structures, in the last case using the proof of a result of Ash and Nerode [3] to extend results of Harizanov [14]. (shrink)

We show that any partial order with a Σ3 enumeration can be effectively embedded into any partial order obtained by imposing a strong reducibility such as ≤tt on the c. e. sets. As a consequence, we obtain that the partial orders that result from imposing a strong reducibility on the sets in a level of the Ershov hiearchy below ω + 1 are co-embeddable.

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)

We provide three new results about interpolating 2-r.e. or 2-REA degrees between given r.e. degrees: Proposition 1.13. If c h are r.e. , c is low and h is high, then there is an a h which is REA in c but not r.e. Theorem 2.1. For all high r.e. degrees h g there is a properly d-r.e. degree a such that h a g and a is r.e. in h . Theorem 3.1. There is an incomplete nonrecursive r.e. A (...) such that every set REA in A and recursive in 0′ is of r. e. degree. The first proof is a variation on the construction of Soare and Stob . The second combines highness with a modified version of the proof strategy of Cooper et al. . The third theorem is a rather surprising result with a somewhat unusual proof strategy. Its proof is a 0‴ argument that at times moves left in the tree so that the accessible nodes are not linearly ordered at each stage. Thus the construction lacks a true path in the usual sense. Two substitute notions fill this role: The true nodes are the leftmost ones accessible infinitely often; the semitrue nodes are the leftmost ones such that there are infinitely many stages at which some extension is accessible. Another unusual feature of the construction is that it involves using distinct priority orderings to control the interactions of different parts of the construction. (shrink)

We show that for any ω-r.e. degree d and n-r.e. degree b with d

Download  

 

Export citation  

 

Bookmark   1 citation  

It will be shown that there exist computably enumerable degrees a and b such that a $>$ b, and for any computably enumerable degree u, if u $\leq$ a and u is cappable, then u $<$ b.

We study the global properties of [Formula: see text], the Turing degrees of the n-r.e. sets. In Theorem 1.5, we show that the first order of [Formula: see text] is not decidable. In Theorem 1.6, we show that for any two n and m with n < m, [Formula: see text] is not a Σ1-substructure of [Formula: see text].