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

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 |

### 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 |

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.