Skip to main navigation Skip to search Skip to main content

On Lachlan's major sub-degree problem

  • S. Barry Cooper
  • , Angsheng Li*
  • *Corresponding author for this work
  • University of Leeds
  • CAS - Institute of Software

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)341-434
Number of pages94
JournalArchive for Mathematical Logic
Volume47
Issue number4
DOIs
StatePublished - Aug 2008
Externally publishedYes

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