The \(n\)-rea enumeration degrees are dense
type: Item
instance of: scholarly article
title: The \(n\)-rea enumeration degrees are dense
zbMATH Open document ID: 0848.03023
DOI: 10.1007/BF01794984
author: Alistair H. Lachlan
author: Richard A. Shore
published in: Archive for Mathematical Logic
publication date: 1993-09-01T00:00:00Z
review text: The minimality problem for e-degrees was solved by \textit{L. Gutteridge} [Some results on enumeration reducibility (Thesis), Simon Fraser Univ. (1971)] in a two step process: Theorem 1.2 (Gutteridge). If (the e-degree of) \(Y\) is a minimal cover of (the e-degree of) \(X\), then \(Y\) is \(\Delta^0_2\) in \(X\). Thus, in particular, every e-degree has at most countably many minimal covers. Theorem 1.3 (Gutteridge). If \(Y\) is \(\Delta^0_2\) then \(Y\) is not of minimal e-degree and hence by Theorem 1.2 there are no minimal e-degrees. The proof of Theorem 1.3 does not relativize (except to degrees of total functions) and so the general problem of density in the e-degrees was left open. A simple presentation of the proof of Theorem 1.3 based on notes of Sasso from 1972 is presented by \textit{S. B. Cooper} [J. Symb. Log. 47, 854-859 (1982; Zbl 0511.03019)]. The next major step in the investigation of the density problem appears in \textit{S. B. Cooper}'s paper [ibid. 49, 503-513 (1984; Zbl 0574.03027)], in which it is proven that the e-degrees of the \(\Sigma^0_2\) sets (or equivalently the ones e-reducible to the (graph of the) characteristic function of \(\emptyset')\) are dense. Cooper [loc. cit., 1982] also announced that the e-degrees are not dense. He presents a sketch of the plan of the proof and some of the ideas in Lect. Notes Math. 1432, 57-110 (1990; Zbl 0707.03034), Sect. 6. It is our goal in this paper to show how all of the known density results as well as some new ones can be derived from the simple proof of Gutteridge's theorem that there are no \(\Delta^0_2\) sets of minimal e-degrees. The key idea is to precisely describe the properties of the \(\Delta_2^0\) approximations actually needed to carry out the proof. We then give the proof using only these properties of the approximation. It is then an easy observation that, for example, every total function and every \(\Delta^0_2\) set has such an approximation. A bit more work then shows that if \(X\)…
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 126093
zbMATH Keywords: enumeration degrees
zbMATH Keywords: \(n\)-rea sets
zbMATH Keywords: e-degrees
zbMATH Keywords: minimal e-degrees
zbMATH Keywords: density
zbMATH Keywords: approximations
zbMATH Keywords: minimal cover
MaRDI profile type: Publication
cites work: Partial degrees and the density problem
cites work: Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense
cites work: Reducibility and Completeness for Sets of Integers
cites work: Semirecursive Sets and Positive Reducibility
cites work: Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
cites work: Q5812175
cites work: Note on Degrees of Partial Functions
cites work: Q5573961
cites work: Q3819052
description: scientific article; zbMATH DE number 126093