Switch to: References

Add citations

You must login to add citations.
  1. On Extensions of Embeddings Into the Enumeration Degrees of the -Sets.Steffen Lempp, Theodore A. Slaman & Andrea Sorbi - 2005 - Journal of Mathematical Logic 5 (02):247-298.
    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].
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms.Denis R. Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697 - 720.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • The N-R.E. Degrees: Undecidability and Σ1 Substructures.Mingzhong Cai, Richard A. Shore & Theodore A. Slaman - 2012 - Journal of Mathematical Logic 12 (1):1250005-.
    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].
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  • Degree Spectra of Relations on Computable Structures in the Presence of Δ20 Isomorphisms.Denis Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697-720.
  • Generalized Nonsplitting in the Recursively Enumerable Degrees.Steven D. Leonhardi - 1997 - Journal of Symbolic Logic 62 (2):397-437.
    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 (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
    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 α ∈ (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Isolation and Lattice Embeddings.Guohua Wu - 2002 - Journal of Symbolic Logic 67 (3):1055-1064.
    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, (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • On Σ₁-Structural Differences Among Finite Levels of the Ershov Hierarchy.Yue Yang & Liang Yu - 2006 - Journal of Symbolic Logic 71 (4):1223 - 1236.
    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.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • On Downey's Conjecture.Marat M. Arslanov, Iskander Sh Kalimullin & Steffen Lempp - 2010 - Journal of Symbolic Logic 75 (2):401-441.
    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.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Interpolating D-R.E. And REA Degrees Between R.E. Degrees.Marat Arslanov, Steffen Lempp & Richard A. Shore - 1996 - Annals of Pure and Applied Logic 78 (1-3):29-56.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • An Almost-Universal Cupping Degree.Jiang Liu & Guohua Wu - 2011 - Journal of Symbolic Logic 76 (4):1137-1152.
    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.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  • In Memoriam: Barry Cooper 1943–2015.Andrew Lewis-Pye & Andrea Sorbi - 2016 - Bulletin of Symbolic Logic 22 (3):361-365.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • 1998–99 Annual Meeting of the Association for Symbolic Logic.Sam Buss - 1999 - Bulletin of Symbolic Logic 5 (3):395-421.
  • Splitting Theorems in Recursion Theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  • A Non-Splitting Theorem for D.R.E. Sets.Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (1):17-96.
    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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Nonisolated Degrees and the Jump Operator.Guohua Wu - 2002 - Annals of Pure and Applied Logic 117 (1-3):209-221.
    Say that a d.c.e. degree d is nonisolated if for any c.e. degree a
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Infima in the D.R.E. Degrees.D. Kaddah - 1993 - Annals of Pure and Applied Logic 62 (3):207-263.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Complementing Cappable Degrees in the Difference Hierarchy.Rod Downey, Angsheng Li & Guohua Wu - 2004 - Annals of Pure and Applied Logic 125 (1-3):101-118.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • Almost Universal Cupping and Diamond Embeddings.Jiang Liu & Guohua Wu - 2012 - Annals of Pure and Applied Logic 163 (6):717-729.
  • Bounding Computably Enumerable Degrees in the Ershov Hierarchy.Angsheng Li, Guohua Wu & Yue Yang - 2006 - Annals of Pure and Applied Logic 141 (1):79-88.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Isolation in the CEA Hierarchy.Geoffrey LaForte - 2004 - Archive for Mathematical Logic 44 (2):227-244.
    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.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Corrigendum to “The D.R.E. Degrees Are Not Dense” [Ann. Pure Appl. Logic 55 125–151].S. Barry Cooper, Leo Harrington, Alistair H. Lachlan, Steffen Lempp & Robert I. Soare - 2017 - Annals of Pure and Applied Logic 168 (12):2164-2165.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Intervals Containing Exactly One C.E. Degree.Guohua Wu - 2007 - Annals of Pure and Applied Logic 146 (1):91-102.
    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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
  • Bi-Isolation in the D.C.E. Degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409 - 420.
    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.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Bi-Isolation in the D.C.E. Degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409-420.
    In this paper, we study the bi-isolation phenomena in the d.c.e. degrees and prove that there are c.e. degrees c1 < c2 and a d.c.e. degree d∈ such that and contain no c.e. degrees. Thus, the c.e. degrees between c1 and c2 are all incomparable with d. We also show that there are d.c.e. degrees d1 < d2 such that contains a unique c.e. degree.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark