×

The \(n\)-rea enumeration degrees are dense. (English) Zbl 0848.03023

The minimality problem for e-degrees was solved by 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 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 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.

MSC:

03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Cooper, S.B.: Partial degrees and the density problem. J. Symb. Logic47, 854–859 (1982) · Zbl 0511.03019
[2] Cooper, S.B.: Partial degrees and the density problem. Part 2: the enumeration degrees of the{\(\Sigma\)} 2 sets are dense. J. Symb. Logic49, 503–513 (1984) · Zbl 0574.03027
[3] Cooper, S.B.: Enumeration reducibility, non-deterministic computations and relative computability of partial functions. In: Ambos-Spies, K., Müller, G.H., Sacks, G.E. (eds.) Recursion Theory Week, Proceedings Oberwolfach. (Lect. Notes Math., vol. 1432, pp. 57–110) Berlin Heidelberg New York: Springer 1989
[4] Friedberg, R.M., Rogers, H. Jr.: Reducibilities and completeness for sets of integers, Zeit. Math. Log. Grund. Math.5, 117–125 (1959) · Zbl 0108.00602
[5] Gutteridge, L.: Some results on enumeration reducibility. (Thesis) Simon Fraser University (1971)
[6] Jockusch, C.G. Jr.: Semirecursive sets and positive reducibility. Trans. Am. Math. Soc.131, 420–436 (1968) · Zbl 0198.32402
[7] Jockusch, C.G. Jr., Shore, R.A.: Pseudo-jump operators. II. Transfinite iterations, hierarchies and minimal covers. J. Symb. Logic49, 1205–1236 (1984) · Zbl 0574.03026
[8] Kleene, S.C.: Introduction to metamathematics. New York: Van Nostrand 1952 · Zbl 0047.00703
[9] Medvedev, Y.T.: Degrees of difficulty of the mass problem. Dokl. Akad. Nauk SSSR,104, 501–504 (1952)
[10] Myhill, J.: A note on degrees of partial functions. Proc. Am. Math. Soc.12, 519–521 (1961) · Zbl 0101.01201
[11] Rogers, H. Jr.: Theory of recursive functions and effective computability. McGraw Hill, New York: McGraw Hill 1967 · Zbl 0183.01401
[12] Soare, R.I.: Recursively enumerable sets and degrees. Berlin Heidelberg New York: Springer 1987 · Zbl 0667.03030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.