Contiguity and Distributivity in the Enumerable Turing Degrees

&
Journal of Symbolic Logic 62 (4):1215-1240 (1997)
  Copy   BIBTEX

Abstract

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.

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,349

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Corrigendum: ``Contiguity and distributivity in the enumerable Turing degrees''.Rodney G. Downey & Steffen Lempp - 2002 - Journal of Symbolic Logic 67 (4):1579-1580.
Embeddings of N5 and the contiguous degrees.Klaus Ambos-Spies & Peter A. Fejer - 2001 - Annals of Pure and Applied Logic 112 (2-3):151-188.
Maximal contiguous degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
On relative enumerability of Turing degrees.Shamil Ishmukhametov - 2000 - Archive for Mathematical Logic 39 (3):145-154.
Degrees of d. c. e. reals.Rod Downey, Guohua Wu & Xizhong Zheng - 2004 - Mathematical Logic Quarterly 50 (4-5):345-350.
Infima in the Recursively Enumerable Weak Truth Table Degrees.Rich Blaylock, Rod Downey & Steffen Lempp - 1997 - Notre Dame Journal of Formal Logic 38 (3):406-418.
On the Structures Inside Truth-Table Degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
On the structures inside truth-table degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
Strong Minimal Covers for Recursively Enumerable Degrees.S. Barry Cooper - 1996 - Mathematical Logic Quarterly 42 (1):191-196.
A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees.Steffen Lempp & Manuel Lerman - 1997 - Annals of Pure and Applied Logic 87 (2):167-185.
On Lachlan’s major sub-degree problem.S. Barry Cooper & Angsheng Li - 2008 - Archive for Mathematical Logic 47 (4):341-434.
Splittings of 0' into the Recursively Enumerable Degrees.Xiaoding Yi - 1996 - Mathematical Logic Quarterly 42 (1):249-269.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
Degrees of unsolvability of continuous functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555-584.
Computably Enumerable Reals and Uniformly Presentable Ideals.S. A. Terwijn & R. Downey - 2002 - Mathematical Logic Quarterly 48 (S1):29-40.

Analytics

Added to PP
2009-01-28

Downloads
42 (#368,825)

6 months
1 (#1,533,009)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

A Hierarchy of Computably Enumerable Degrees.Rod Downey & Noam Greenberg - 2018 - Bulletin of Symbolic Logic 24 (1):53-89.
Embeddings of N5 and the contiguous degrees.Klaus Ambos-Spies & Peter A. Fejer - 2001 - Annals of Pure and Applied Logic 112 (2-3):151-188.
Completing pseudojump operators.R. Coles, R. Downey, C. Jockusch & G. LaForte - 2005 - Annals of Pure and Applied Logic 136 (3):297-333.

Add more citations

References found in this work

Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
Splitting theorems in recursion theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
The density of infima in the recursively enumerable degrees.Theodore A. Slaman - 1991 - Annals of Pure and Applied Logic 52 (1-2):155-179.

View all 14 references / Add more references