Conjectures and questions from Gerald Sacks's \textit{Degrees of unsolvability}

DOI10.1007/S001530050063MaRDI QIDQ1387091zbMATH OpenOpenAlexWikidataFDO

Publication date 9 September 1998

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001530050063

History of mathematics in the 20th century (01A60) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) History of mathematical logic and foundations (03-03) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30) Undecidability and degrees of sets of sentences (03D35) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Review text

This paper provides a broad and useful overview of the growth and complexity of the theory of degrees. Shore looks at ``the important role that the conjectures and questions posed at the end of the two editions of Gerald Sacks's \textit{Degrees of unsolvability} have had in the development of recursion theory over the past thirty years. They concerned \({\mathcal R}\), the r.e. degrees, and \({\mathcal D}\), the full set of degrees, each partially ordered by Turing reducibility. In his 1963 edition (Zbl 0143.25302), Sacks offered six conjectures and five questions, noting that each seemed to call for a ``new idea. In fact, they led to the development of the subject's most powerful techniques, including infinite injury arguments, tree constructions, and the full approximation method. Sacks's 1964 Density Theorem verified one conjecture about \({\mathcal R}\); 1966 results of Lachlan and Yates sustained two more, existence of a minimal pair of r.e. degrees and a pair with no g.l.b. in \({\mathcal R}\). The other conjectures concerned embedding in \({\mathcal D}\). Still open is the characterization of those partially ordered sets that are so embeddable. Sacks's five questions dealt with degrees below \(\underset\widetilde{} 0'\); all were answered by 1972. The 1966 edition made three further conjectures, all of which have been refuted; e.g., the elementary theory of \({\mathcal R}\) was proved undecidable, in fact recursively isomorphic to the theory of true first-order arithmetic. There were four new questions posed, two dealing with aspects of Post's problem, one with metarecursively enumerable degrees. Three of the questions have not been answered completely. Throughout, the author emphasizes that what has been found testifies to the unexpectedly great complexity of both \({\mathcal R}\) and \({\mathcal D}\).

Cited in

(11)

This page was built for publication: Conjectures and questions from Gerald Sacks's \textit{Degrees of unsolvability}

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1387091)