The \(n\)-rea enumeration degrees are dense (Q1204114): Difference between revisions

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\) has such an approximation, so does \(X \oplus Y\) for every \(Y\) r.e. in \(X\). We thus immediately conclude that no \(n\)-rea set \(Y\) is a minimal cover (in the e-degrees). (The \(n\)-rea sets are just those gotten by starting with the empty set and iterating the process of going from \(X\) to \(X \oplus Y\) for some \(Y\) r.e. in \(X\).) Another observation shows that, in fact, the e-degrees of the \(n\)-rea sets are dense for each \(n\). This result includes Cooper's result for the \(\Sigma^0_2\) sets as their e-degrees are clearly just the ones of the 2-rea sets. An application of the precise form of Theorem 1.2 proved by Gutteridge combined with one more simple construction of an approximation then shows that none of the e-degrees proven not to be minimal covers can have minimal covers either.