Contiguity and Distributivity in the Enumerable Turing Degrees

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

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.

Download options

PhilArchive



    Upload a copy of this work     Papers currently archived: 72,879

External links

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

Through your library

Analytics

Added to PP
2009-01-28

Downloads
37 (#311,777)

6 months
2 (#257,834)

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
How can I increase my downloads?

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

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

Similar books and articles

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 (45):345-350.
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.
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.