×

Tracing and domination in the Turing degrees. (English) Zbl 1247.03082

Summary: We show that if \(\mathbf 0^\prime\) is c.e. traceable by \(\mathbf a\), then \(\mathbf a\) is array non-computable. It follows that there is no minimal almost everywhere dominating degree, in the sense of N. Dobrinen and S. Simpson [J. Symb. Log. 69, No. 3, 914–922 (2004; Zbl 1075.03021)]. This answers a question of Simpson and a question of A. Nies [Computability and randomness. Oxford Logic Guides 51. Oxford: Oxford University Press (2009; Zbl 1169.03034), Problem 8.6.4]. Moreover, it adds a new arrow in [Nies, loc. cit., Figure 8.1], which is a diagram depicting the relations of various ‘computational lowness’ properties. Finally, it gives a natural definable property, namely non-minimality, which separates almost everywhere domination from highness.

MSC:

03D32 Algorithmic randomness and dimension
03D25 Recursively (computably) enumerable sets and degrees
03D28 Other Turing degree structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Binns, S.; Kjos-Hanssen, B.; Lerman, M.; Solomon, R., On a conjecture of Dobrinen and Simpson concerning almost everywhere domination, J. Symbolic Logic, 71, 1, 119-136 (2006) · Zbl 1103.03014
[2] Barmpalias, George; Morphett, Anthony, Non-cupping, measure and computably enumerable splittings, Math. Structures Comput. Sci., 19, 1, 25-43 (2009) · Zbl 1170.03020
[3] Cholak, P.; Greenberg, N.; Miller, J., Uniform almost everywhere domination, J. Symbolic Logic, 71, 3, 1057-1072 (2006) · Zbl 1109.03034
[4] Cooper, S. B., Minimal degrees and the jump operator, J. Symbolic Logic, 38, 249-271 (1973) · Zbl 0309.02048
[5] Cooper, S. Barry, Minimal pairs and high recursively enumerable degrees, J. Symbolic Logic, 39, 655-660 (1974) · Zbl 0309.02047
[6] Cole, Joshua A.; Simpson, Stephen G., Mass problems and hyperarithmeticity, J. Math. Log., 7, 2, 125-143 (2007) · Zbl 1150.03013
[7] Downey, R.; Hirschfeldt, D.; Nies, A.; Stephan, F., Trivial reals, (Proceedings of the 7th and 8th Asian Logic Conferences (2003), Singapore Univ. Press: Singapore Univ. Press Singapore), 103-131 · Zbl 1044.03027
[8] Downey, Rod; Jockusch, Carl G.; Stob, Michael, Array nonrecursive sets and genericity, (Computability, Enumerability, Unsolvability: Directions in Recursion Theory. Computability, Enumerability, Unsolvability: Directions in Recursion Theory, London Mathematical Society Lecture Notes Series, vol. 224 (1996), Cambridge University Press), 93-104 · Zbl 0849.03029
[9] Downey, Rodney G.; Lempp, Steffen; Shore, Richard, Highness and bounding minimal pairs, Math. Log. Q., 39, 475-491 (1993) · Zbl 0809.03029
[10] Dobrinen, N.; Simpson, S., Almost everywhere domination, J. Symbolic Logic, 69, 3, 914-922 (2004) · Zbl 1075.03021
[11] Kjos-Hanssen, Bjørn, Low for random reals and positive-measure domination, Proc. Amer. Math. Soc., 135, 11, 3703-3709 (2007), electronic · Zbl 1128.03031
[12] B. Kjos-Hanssen, J. Miller, R. Solomon, Lowness notions, measure, and domination, London Math. Soc. (in press).; B. Kjos-Hanssen, J. Miller, R. Solomon, Lowness notions, measure, and domination, London Math. Soc. (in press). · Zbl 1262.03068
[13] Kučera, Antonín; Terwijn, Sebastiaan A., Lowness for the class of random sets, J. Symbolic Logic, 64, 4, 1396-1402 (1999) · Zbl 0954.68080
[14] S. Kurtz, Randomness and genericity in the degrees of unsolvability. Ph.D. Dissertation, University of Illinois, Urbana, 1981.; S. Kurtz, Randomness and genericity in the degrees of unsolvability. Ph.D. Dissertation, University of Illinois, Urbana, 1981.
[15] Lachlan, A. H., Lower bounds for pairs of recursively enumerable degrees, Proc. London Math. Soc. (3), 16, 537-569 (1966) · Zbl 0156.00907
[16] Lerman, M., Degrees of Unsolvability, (Perspectives in Mathematical Logic (1983), Springer-Verlag: Springer-Verlag Heidelberg), 307 pages · Zbl 0193.31004
[17] Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlag. Math., 12, 295-310 (1966) · Zbl 0181.30504
[18] Miller, D., High recursively enumerable degrees and the anticupping property, (Logic Year 1979-80: University of Connecticut (1981)), 230-245
[19] Miller, Joseph S.; Nies, André, Randomness and computability: open questions, Bull. Symbolic Logic, 12, 3, 390-410 (2006) · Zbl 1169.03033
[20] Nies, André, Lowness properties and randomness, Adv. Math., 197, 1, 274-305 (2005) · Zbl 1141.03017
[21] Nies, André, Reals which compute little, (Logic Colloquium’02. Logic Colloquium’02, Lect. Notes Log., vol. 27 (2006), Assoc. Symbol. Logic: Assoc. Symbol. Logic La Jolla, CA), 261-275 · Zbl 1107.03047
[22] Nies, André, Computability and Randomness (2009), Oxford University Press, 444 pp · Zbl 1169.03034
[23] Simpson, Stephen G., Almost everywhere domination and superhighness, MLQ Math. Log. Q., 53, 4-5, 462-482 (2007) · Zbl 1123.03040
[24] Terwijn, S.; Zambella, D., Algorithmic randomness and lowness, J. Symbolic Logic, 66, 1199-1205 (2001) · Zbl 0990.03033
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.