Conjectures and questions from Gerald Sacks's \textit{Degrees of unsolvability}
type: Item
instance of: scholarly article
title: Conjectures and questions from Gerald Sacks's \textit{Degrees of unsolvability}
zbMATH Open document ID: 0907.03020
author: Richard A. Shore
published in: Archive for Mathematical Logic
publication date: 1998-09-09T00:00:00Z
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}\).
Mathematics Subject Classification ID: 03D30
Mathematics Subject Classification ID: 03-02
Mathematics Subject Classification ID: 03D25
Mathematics Subject Classification ID: 03D35
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03-03
Mathematics Subject Classification ID: 01A60
zbMATH DE Number: 1158097
zbMATH Keywords: degrees of unsolvability
reviewed by: Joseph S. Ullian
MaRDI profile type: Publication
full work available at URL: s001530050063
OpenAlex ID: W2028097918
Wikidata QID: Q123110910
DOI: 10.1007/S001530050063
description: scientific article; zbMATH DE number 1158097