Switch to: References

Add citations

You must login to add citations.
  1. Contiguity and Distributivity in the Enumerable Turing Degrees.Rodney G. Downey & Steffen Lempp - 1997 - Journal of Symbolic Logic 62 (4):1215-1240.
    We prove that a enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no $m$-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Automorphisms of the Lattice of Recursively Enumerable Sets. Part II: Low Sets.Robert I. Soare - 1982 - Annals of Mathematical Logic 22 (1):69.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Mass Problems and Density.Stephen Binns, Richard A. Shore & Stephen G. Simpson - 2016 - Journal of Mathematical Logic 16 (2):1650006.
    Recall that [Formula: see text] is the lattice of Muchnik degrees of nonempty effectively compact sets in Euclidean space. We solve a long-standing open problem by proving that [Formula: see text] is dense, i.e. satisfies [Formula: see text]. Our proof combines an oracle construction with hyperarithmetical theory.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Conjectures and Questions From Gerald Sacks's Degrees of Unsolvability.Richard A. Shore - 1997 - Archive for Mathematical Logic 36 (4-5):233-253.
    . We describe the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's Degrees of Unsolvability have had in the development of recursion theory over the past thirty years.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Parameter Definability in the Recursively Enumerable Degrees.André Nies - 2003 - Journal of Mathematical Logic 3 (01):37-65.
    The biinterpretability conjecture for the r.e. degrees asks whether, for each sufficiently large k, the [Formula: see text] relations on the r.e. degrees are uniformly definable from parameters. We solve a weaker version: for each k ≥ 7, the [Formula: see text] relations bounded from below by a nonzero degree are uniformly definable. As applications, we show that Low 1 is parameter definable, and we provide methods that lead to a new example of a ∅-definable ideal. Moreover, we prove that (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • A General Framework for Priority Arguments.Steffen Lempp & Manuel Lerman - 1995 - Bulletin of Symbolic Logic 1 (2):189-201.
    The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure theinformation contentof sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • There Are No Maximal Low D.C.E. Degrees.Liang Yu & Rod Downey - 2004 - Notre Dame Journal of Formal Logic 45 (3):147-159.
  • Highness and Bounding Minimal Pairs.Rodney G. Downey, Steffen Lempp & Richard A. Shore - 1993 - Mathematical Logic Quarterly 39 (1):475-491.
  • Recursively Enumerablem- Andtt-Degrees II: The Distribution of Singular Degrees. [REVIEW]R. G. Downey - 1988 - Archive for Mathematical Logic 27 (2):135-147.
  • Nonstandard Models in Recursion Theory and Reverse Mathematics.C. T. Chong, Wei Li & Yue Yang - 2014 - Bulletin of Symbolic Logic 20 (2):170-200.
    We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models, and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey’s Theorem for Pairs.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • The Theory of the Metarecursively Enumerable Degrees.Noam Greenberg, Richard A. Shore & Theodore A. Slaman - 2006 - Journal of Mathematical Logic 6 (1):49-68.
    Sacks [23] asks if the metarecursively enumerable degrees are elementarily equivalent to the r.e. degrees. In unpublished work, Slaman and Shore proved that they are not. This paper provides a simpler proof of that result and characterizes the degree of the theory as [Formula: see text] or, equivalently, that of the truth set of [Formula: see text].
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  • On the Existence of a Strong Minimal Pair.George Barmpalias, Mingzhong Cai, Steffen Lempp & Theodore A. Slaman - 2015 - Journal of Mathematical Logic 15 (1):1550003.
    We show that there is a strong minimal pair in the computably enumerable Turing degrees, i.e. a pair of nonzero c.e. degrees a and b such that a∩b = 0 and for any nonzero c.e. degree x ≤ a, b ∪ x ≥ a.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • On Strongly Jump Traceable Reals.Keng Meng Ng - 2008 - Annals of Pure and Applied Logic 154 (1):51-69.
    In this paper we show that there is no minimal bound for jump traceability. In particular, there is no single order function such that strong jump traceability is equivalent to jump traceability for that order. The uniformity of the proof method allows us to adapt the technique to showing that the index set of the c.e. strongly jump traceables is image-complete.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • The Role of True Finiteness in the Admissible Recursively Enumerable Degrees.Noam Greenberg - 2005 - Bulletin of Symbolic Logic 11 (3):398-410.
    We show, however, that this is not always the case.
    Direct download (13 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • A Splitting Theorem for the Medvedev and Muchnik Lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
    This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  • Splitting and Nonsplitting II: A Low {\Sb 2$} C.E. Degree About Which ${\Bf 0}'$ is Not Splittable.S. Barry Cooper & Angsheng Li - 2002 - Journal of Symbolic Logic 67 (4):1391-1430.
    It is shown that there exists a low2 Harrington non-splitting base-that is, a low2 computably enumerable (c.e.) degree a such that for any c.e. degrees x, y, if $0' = x \vee y$ , then either $0' = x \vee a$ or $0' = y \vee a$ . Contrary to prior expectations, the standard Harrington non-splitting construction is incompatible with the $low_{2}-ness$ requirements to be satisfied, and the proof given involves new techniques with potentially wider application.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Splitting Properties of R. E. Sets and Degrees.R. G. Downey & L. V. Welch - 1986 - Journal of Symbolic Logic 51 (1):88-109.
  • Variations on Promptly Simple Sets.Wolfgang Maass - 1985 - Journal of Symbolic Logic 50 (1):138-148.
  • Working Below a High Recursively Enumerable Degree.Richard A. Shore & Theodore A. Slaman - 1993 - Journal of Symbolic Logic 58 (3):824-859.
  • Definability in the Recursively Enumerable Degrees.André Nies, Richard A. Shore & Theodore A. Slaman - 1996 - Bulletin of Symbolic Logic 2 (4):392-404.
  • 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  
  • Decomposition and Infima in the Computably Enumerable Degrees.Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore - 2003 - Journal of Symbolic Logic 68 (2):551-579.
    Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Non-Splittings of Speedable Sets.Ellen S. Chih - 2015 - Journal of Symbolic Logic 80 (2):609-635.
  • Intervals and Sublattices of the R.E. Weak Truth Table Degrees, Part I: Density.R. G. Downey - 1989 - Annals of Pure and Applied Logic 41 (1):1-26.
  • The D.R.E. Degrees Are Not Dense.S. Barry Cooper, Leo Harrington, Alistair H. Lachlan, Steffen Lempp & Robert I. Soare - 1991 - Annals of Pure and Applied Logic 55 (2):125-151.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   26 citations  
  • 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  
  • The Density of the Nonbranching Degrees.Peter A. Fejer - 1983 - Annals of Pure and Applied Logic 24 (2):113-130.
  • A Non-Inversion Theorem for the Jump Operator.Richard A. Shore - 1988 - Annals of Pure and Applied Logic 40 (3):277-303.
  • Nonbounding and Slaman Triples.Steven D. Leonhardi - 1996 - Annals of Pure and Applied Logic 79 (2):139-163.
    We consider the relationship of the lattice-theoretic properties and the jump-theoretic properties satisfied by a recursively enumerable Turing degree. The existence is shown of a high2 r.e. degree which does not bound what we call the base of any Slaman triple.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • 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  
  • Incomparable Prime Ideals of Recursively Enumerable Degrees.William C. Calhoun - 1993 - Annals of Pure and Applied Logic 63 (1):39-56.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • On Definable Filters in Computably Enumerable Degrees.Wei Wang & Decheng Ding - 2007 - Annals of Pure and Applied Logic 147 (1):71-83.
  • On Lachlan’s Major Sub-Degree Problem.S. Barry Cooper & Angsheng Li - 2008 - Archive for Mathematical Logic 47 (4):341-434.
    The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, ${{\bf 0' = b \lor x}}$ if and only if (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Splittings of 0' Into the Recursively Enumerable Degrees.Xiaoding Yi - 1996 - Mathematical Logic Quarterly 42 (1):249-269.
    Lachlan [9] proved that there exists a non-recursive recursively enumerable degree such that every non-recursive r. e. degree below it bounds a minimal pair. In this paper we first prove the dual of this fact. Second, we answer a question of Jockusch by showing that there exists a pair of incomplete r. e. degrees a0, a1 such that for every non-recursive r. e. degree w, there is a pair of incomparable r. e. degrees b0, b2 such that w = b0 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • A Non-Splitting Theorem in the Enumeration Degrees.Mariya Ivanova Soskova - 2009 - Annals of Pure and Applied Logic 160 (3):400-418.
    We complete a study of the splitting/non-splitting properties of the enumeration degrees below by proving an analog of Harrington’s non-splitting theorem for the enumeration degrees. We show how non-splitting techniques known from the study of the c.e. Turing degrees can be adapted to the enumeration degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations