A local version of the Slaman-Wehner theorem and families closed under finite differences. (English) Zbl 07720262

Faizrahmanov, Marat

Notre Dame J. Formal Logic 64, No. 2, 197-203 (2023).

Summary: The main question of this article is whether there is a family closed under finite differences (i.e., if \(A\) belongs to the family and \(B =^* A\), then \(B\) also belongs to the family) that can be enumerated by any noncomputable c.e. degree, but which cannot be enumerated computably. This question was formulated by Greenberg et al. (2020) in their recent work in which families that are closed under finite differences, close to the Slaman-Wehner families, are deeply studied.

MSC:

03D45	Theory of numerations, effectively presented structures
03C57	Computable structure theory, computable model theory
03D80	Applications of computability and recursion theory

Keywords:

c.e. family; c.e. set; family closed under finite differences

References:

[1]	Ash, C. J., and J. Knight, Computable Structures and the Hyperarithmetical Hierarchy, vol. 144 of Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 2000. · Zbl 0960.03001
[2]	Ershov, Y. L., “Theory of numberings,” Nauka, Moscow, 1977. · Zbl 0948.03040
[3]	Ershov, Y. L., “Theory of numberings,” pp. 473-506 in Handbook of Computability Theory, edited by E. R. Griffor, vol. 140 of Studies in Logic and the Foundations of Mathematics, North-Holland, Amsterdam, 1999. · Zbl 0948.03040 · doi:10.1016/S0049-237X(99)80030-5
[4]	Faizrahmanov, M., “Limitwise monotonic spectra and their generalizations,” pp. 189-98 in Connecting with Computability, edited by L. De Mol, A. Weiermann, F. Manea, and D. Fernández-Duque, vol. 12813 of Lecture Notes in Computer Science, Springer, Cham, 2021. · Zbl 07495167 · doi:10.1007/978-3-030-80049-9_17
[5]	Faizrahmanov, M., and I. Kalimullin, “Limitwise monotonic sets of reals,” Mathematical Logic Quarterly, vol. 61 (2015), pp. 224-29. · Zbl 1346.03041 · doi:10.1002/malq.201400015
[6]	Greenberg, N., M. Harrison-Trainor, J. S. Miller, and D. Turetsky, “Enumerations of families closed under finite differences,” preprint, https://homepages.ecs.vuw.ac.nz/ greenberg/Papers/75-Enumerations_with_Finite_Differences.pdf.
[7]	Greenberg, N., A. Montalbán, T. A. Slaman, “Relative to any non-hyperarithmetic set,” Journal of Mathematical Logic, vol. 13 (2013), no. 1250007. · Zbl 1308.03050 · doi:10.1142/S0219061312500079
[8]	Goncharov, S. S., “Computable univalent numerations,” Algebra and Logic, vol. 19 (1980), pp. 325-56. · Zbl 0514.03029 · doi:10.1007/BF01669607
[9]	Goncharov, S. S., “The problem of the number of nonautoequivalent constructivizations,” Algebra and Logic, vol. 19 (1980), pp. 401-14. · Zbl 0476.03046
[10]	Goncharov, S. S., V. Harizanov, J. Knight, C. McCoy, R. Miller, and R. Solomon, “Enumerations in computable structure theory,” Annals of Pure and Applied Logic, vol. 136 (2005), pp. 219-46. · Zbl 1081.03033 · doi:10.1016/j.apal.2005.02.001
[11]	Goncharov, S. S., and A. Sorbi, “Generalized computable numerations and nontrivial Rogers semilattices,” Algebra and Logic, vol. 36 (1997), pp. 359-69. · Zbl 0969.03052 · doi:10.1007/BF02671553
[12]	Khoussainov, B., “Strongly effective unars and nonautoequivalent constructivizations,” pp. 33-44 in Some Problems in Differential Equations and Discrete Mathematics, edited by M. M. Lavrent’ev, Novosibirsk. Gos. Univ., Novosibirsk, 1986. · Zbl 0679.03010
[13]	Slaman, T. A., “Relative to any nonrecursive set,” Proceedings of the American Mathematical Society, vol. 126 (1998), pp. 2117-22. · Zbl 0894.03017 · doi:10.1090/S0002-9939-98-04307-X
[14]	Soare, R. I., Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Springer, Berlin, 1987. · Zbl 0667.03030 · doi:10.1007/978-3-662-02460-7
[15]	Wehner, S., “Enumerations, countable structures and Turing degrees,” Proceedings of the American Mathematical Society, vol. 126 (1998), pp. 2131-39. · Zbl 0906.03044 · doi:10.1090/S0002-9939-98-04314-7