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, if and only if. In this paper, we show that every c.e. degree b ≠ 0 or 0́ has a major sub-degree, answering Lachlan's question affirmatively.
| Original language | English |
|---|---|
| Pages (from-to) | 341-434 |
| Number of pages | 94 |
| Journal | Archive for Mathematical Logic |
| Volume | 47 |
| Issue number | 4 |
| DOIs | |
| State | Published - Aug 2008 |
| Externally published | Yes |
Keywords
- Computably enumerable set
- Major sub-degree problem
- Turing degree
Fingerprint
Dive into the research topics of 'On Lachlan's major sub-degree problem'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver