Effective domination and the bounded jump. (English) Zbl 1461.03035

Ng, Keng Meng; Yu, Hongyuan

Notre Dame J. Formal Logic 61, No. 2, 203-225 (2020).

Authors’ abstract: We study the relationship between effective domination properties and the bounded jump. We answer two open questions about the bounded jump: (1) We prove that the analogue of Sacks jump inversion fails for the bounded jump and the wtt-reducibility. (2) We prove that no c.e. bounded high set can be low by showing that they all have to be Turing complete. We characterize the class of c.e. bounded high sets as being those sets computing the Halting problem via a reduction with use bounded by an \(\omega\)-c.e. function. We define several notions of a c.e. set being effectively dominant, and show that together with the bounded high sets they form a proper hierarchy.

Reviewer: Patrizio Cintioli (Camerino)

MSC:

03D30	Other degrees and reducibilities in computability and recursion theory
03D28	Other Turing degree structures

Keywords:

wtt-degrees; dominant function; bounded jump; jump inversion; high degrees

References:

[1]	Anderson, B., and B. F. Csima. “A bounded jump for the bounded Turing degrees,” Notre Dame Journal of Formal Logic, vol. 55 (2014), pp. 245-64. · Zbl 1307.03024
[2]	Anderson, B., B. F. Csima, and K. M. Lange, “Bounded low and high sets,” Archive for Mathematical Logic, vol. 56 (2017), pp. 507-21. · Zbl 1417.03239
[3]	Csima, B. F., R. Downey, and K. M. Ng, “Limits on jump inversion for strong reducibilities,” Journal of Symbolic Logic, vol. 76 (2011), pp. 1287-96. · Zbl 1248.03062
[4]	Downey, R., and N. Greenberg, “A hierarchy of computably enumerable degrees,” Bulletin of Symbolic Logic, vol. 24 (2018), pp. 53-89. · Zbl 06866160
[5]	Downey, R., and N. Greenberg, A Transfinite Hierarchy of Lowness Notions in the Computably Enumerable Degrees, Unifying Classes, and Natural Definability, vol. 385 of Annals of Mathematics Studies, Princeton University Press, Princeton, NJ, 2020. · Zbl 07178475
[6]	Downey, R., N. Greenberg, and R. Weber, “Totally \(\omega \)-computably enumerable degrees and bounding critical triples,” Journal of Mathematical Logic, vol. 7 (2007), pp. 145-71. · Zbl 1149.03032
[7]	Downey, R., C. Jockusch, and M. Stob, “Array nonrecursive sets and multiple permitting arguments,” pp. 141-73 in Recursion Theory Week (Oberwolfach, 1989), edited by K. Ambos-Spies, G. H. Müller, and G. E. Sacks, vol. 1432 of Lecture Notes in Mathematics, Springer, Berlin, 1990. · Zbl 0713.03020
[8]	Downey, R., A. G. Melnikov, and K. M. Ng, “Abelian \(p\)-groups and the Halting problem,” Annals of Pure and Applied Logic, vol. 167 (2016), pp. 1123-38. · Zbl 1402.03067
[9]	Harris, K., “The effective content of classical theorems on saturated models,” Ph.D. dissertation, University of Chicago, Chicago, 2007.
[10]	Ng, K. M., F. Stephan, Y. Yang, and L. Yu, “The computational aspects of hyperimmune-free degrees,” pp. 271-84 in Proceedings of the 12th Asian Logic Conference, edited by R. Downey, J. Brendle, R. Goldblatt, and B. Kim, World Scientific, Hackensack, NJ, 2013. · Zbl 1364.03054
[11]	Soare, R. · Zbl 0623.03042