On Lachlan’s major sub-degree problem

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

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

Links

PhilArchive



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

External links

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

Through your library

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 - 2004 - 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
2013-11-23

Downloads
71 (#217,142)

6 months
1 (#1,241,711)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

A minimal pair of recursively enumerable degrees.C. E. M. Yates - 1966 - Journal of Symbolic Logic 31 (2):159-168.
Computability Theory.S. Barry Cooper - 2003 - Chapman & Hall.
Minimal pairs and high recursively enumerable degrees.S. B. Cooper - 1974 - Journal of Symbolic Logic 39 (4):655-660.
Bounding minimal pairs.A. H. Lachlan - 1979 - Journal of Symbolic Logic 44 (4):626-642.

View all 13 references / Add more references