On Lachlan’s major sub-degree problem

Archive for Mathematical Logic 47 (4):341-434 (2008)

Abstract
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 ${{\bf 0' = a \lor x}}$ . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively
Keywords Computably enumerable set  Turing degree  Major sub-degree problem
Categories (categorize this paper)
DOI 10.1007/s00153-008-0083-5
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,000
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Computability Theory.S. Barry Cooper - 2004 - Chapman & Hall.
A Minimal Pair of Recursively Enumerable Degrees.C. E. M. Yates - 1966 - Journal of Symbolic Logic 31 (2):159-168.
Working Below a Low2 Recursively Enumerably Degree.Richard A. Shore & Theodore A. Slaman - 1990 - Archive for Mathematical Logic 29 (3):201-211.
Bounding Minimal Pairs.A. H. Lachlan - 1979 - Journal of Symbolic Logic 44 (4):626-642.

View all 9 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On the Distribution of Lachlan Nonsplitting Bases.S. Barry Cooper, Angsheng Li & Xiaoding Yi - 2002 - Archive for Mathematical Logic 41 (5):455-482.
On the R.E. Predecessors of D.R.E. Degrees.Shamil Ishmukhametov - 1999 - Archive for Mathematical Logic 38 (6):373-386.
On a Conjecture of Kleene and Post.S. Barry Cooper - 2001 - Mathematical Logic Quarterly 47 (1):3-34.
On Relative Enumerability of Turing Degrees.Shamil Ishmukhametov - 2000 - Archive for Mathematical Logic 39 (3):145-154.
An Interval of Computably Enumerable Isolating Degrees.Matthew C. Salts - 1999 - Mathematical Logic Quarterly 45 (1):59-72.
A Minimal Pair Joining to a Plus Cupping Turing Degree.Dengfeng Li & Angsheng Li - 2003 - Mathematical Logic Quarterly 49 (6):553-566.
Prime Models of Computably Enumerable Degree.Rachel Epstein - 2008 - Journal of Symbolic Logic 73 (4):1373-1388.
A Hierarchy for the Plus Cupping Turing Degrees.Yong Wang & Angsheng Li - 2003 - Journal of Symbolic Logic 68 (3):972-988.
On a Problem of Ishmukhametov.Chengling Fang, Guohua Wu & Mars Yamaleev - 2013 - Archive for Mathematical Logic 52 (7-8):733-741.
Complementation in the Turing Degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
The Computably Enumerable Degrees Are Locally Non-Cappable.Matthew B. Giorgi - 2003 - Archive for Mathematical Logic 43 (1):121-139.
Maximal Contiguous Degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
Bounding Non- GL ₂ and R.E.A.Klaus Ambos-Spies, Decheng Ding, Wei Wang & Liang Yu - 2009 - Journal of Symbolic Logic 74 (3):989-1000.

Analytics

Added to PP index
2013-11-23

Total views
26 ( #307,400 of 2,236,206 )

Recent downloads (6 months)
9 ( #148,007 of 2,236,206 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature