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)

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)

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

Download  

 

Export citation  

 

Bookmark   2 citations  

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)

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)

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.

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].

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].

Say that an incomplete d.r.e. degree has almost universal cupping property, if it cups all the r.e. degrees not below it to 0′. In this paper, we construct such a degree d, with all the r.e. degrees not cupping d to 0′ bounded by some r.e. degree strictly below d. The construction itself is an interesting 0″′ argument and this new structural property can be used to study final segments of various degree structures in the Ershov hierarchy.

We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degrees f > e > d > 0 such that any degree u ≤ f is either comparable with both e and d, or incomparable with both.

Say that (a, d) is an isolation pair if a is a c.e. degree, d is a d.c.e. degree, a < d and a bounds all c.e. degrees below d. We prove that there are an isolation pair (a, d) and a c.e. degree c such that c is incomparable with a, d, and c cups d to o', caps a to o. Thus, {o, c, d, o'} is a diamond embedding, which was first proved by Downey in [9]. Furthermore, (...) combined with Harrington-Soare continuity of capping degrees, our result gives an alternative proof of N5 embedding. (shrink)

We investigate the algebraic structure of the upper semi-lattice formed by the recursively enumerable Turing degrees. The following strong generalization of Lachlan's Nonsplitting Theorem is proved: Given n ≥ 1, there exists an r.e. degree d such that the interval $\lbrack\mathbf{d, 0'}\rbrack \subset\mathbf{R}$ admits an embedding of the n-atom Boolean algebra B n preserving (least and) greatest element, but also such that there is no (n + 1)-tuple of pairwise incomparable r.e. degrees above d which pairwise join to 0' (and (...) hence, the interval $\lbrack\mathbf{d, 0'}\rbrack \subset\mathbf{R}$ does not admit a greatest-element-preserving embedding of any lattice L which has n + 1 co-atoms, including B n + 1 ). This theorem is the dual of a theorem of Ambos-Spies and Soare, and yields an alternative proof of their result that the theory of R has infinitely many one-types. (shrink)

We show that for every c.e. degree a > 0 there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. This result can be extended in two directions. First we show that for every uniformly c.e. collection of sets S there exists an intrinsically c.e. relation on the domain of a computable structure whose degree spectrum is the set of degrees of elements of S. Then we show that if α ∈ (...) ω∪{ω } then for any α-c.e. degree a > 0 there exists an intrinsically α-c.e. relation on the domain of a computable structure whose degree spectrum is {0, a}. All of these results also hold for m-degree spectra of relations. (shrink)

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 show that for any ω-r.e. degree d and n-r.e. degree b with d

Download  

 

Export citation  

 

Bookmark   1 citation  

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)

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 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.

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

There has been increasing interest over the last few decades in the study of the effective content of Mathematics. One field whose effective content has been the subject of a large body of work, dating back at least to the early 1960s, is model theory. Several different notions of effectiveness of model-theoretic structures have been investigated. This communication is concerned withcomputablestructures, that is, structures with computable domains whose constants, functions, and relations are uniformly computable.In model theory, we identify isomorphic structures. (...) From the point of view of computable model theory, however, two isomorphic structures might be very different. For example, under the standard ordering of ω the success or relation is computable, but it is not hard to construct a computable linear ordering of type ω in which the successor relation is not computable. In fact, for every computably enumerable degree a, we can construct a computable linear ordering of type ω in which the successor relation has degree a. It is also possible to build two isomorphic computable groups, only one of which has a computable center, or two isomorphic Boolean algebras, only one of which has a computable set of atoms. Thus, for the purposes of computable model theory, studying structures up to isomorphism is not enough. (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)

We show that the structure R of recursively enumerable degrees is not a Σ₁-elementary substructure of Dn, where Dn (n > 1) is the structure of n-r.e. degrees in the Ershov hierarchy.

In this paper, we study the bi-isolation phenomena in the d.c.e. degrees and prove that there are c.e. degrees c₁ < c₂ and a d.c.e. degree d ∈ (c₁, c₂) such that (c₁, d) and (d, c₂) contain no c.e. degrees. Thus, the c.e. degrees between c₁ and c₂ are all incomparable with d. We also show that there are d.c.e. degrees d₁ < d₂ such that (d₁, d₂) contains a unique c.e. degree.