Degrees of selector functions and relative computable categoricity
https://doi.org/10.26907/2949-3919.2023.4.67-80
Abstract
We study the classes of Turing degrees of selector functions in which a rigid computable structure is relatively computably categorical. It is proved that for some structures such classes of degrees can be represented as the unions of upper cones of c.e. degrees. In addition we show that there are non-c.e. upper cones realized as the degrees in which some computable structure is relatively computably categorical.
Keywords
computably enumerable (c.e.) sets,
n-c.e. sets,
Turing degrees,
computable alebrai structures,
relative computable categoricity,
selector functions
Supporting agencies: The work was supported by the Theoretical Physics and Mathematics Advancement Foundation “BASIS”
About the Author
I. I. Sh. Kalimullin
Kazan Federal University
Russian Federation
Kalimullin Iskander Shagitovich
Volga Region Mathematical Center
18 Kremlyovskaya str., Kazan 420008, Russia
Russian Federation
Kalimullin Iskander Shagitovich
Volga Region Mathematical Center
18 Kremlyovskaya str., Kazan 420008, Russia
References
1. C. Ash, J. Knight, M. Manasse, T. Slaman, Generic copies of countable structures, Ann. Pure Appl. Log. 42 (3), 195–205 (1989). DOI: https://doi.org/10.1016/0168-0072(89)90015-8
2. J. Chisholm, Effective model theory vs. recursive model theory, J. Symb. Log. 55 (3), 1168– 1191 (1990). DOI: https://doi.org/10.2307/2274481
3. C.G. Jockusch, R.A. Shore, Pseudo-jump operators, II: transfinite iterations, hierarchies and minimal covers, J. Symb. Log. 49 (4), 1205–1236 (1984). DOI: https://doi.org/10.2307/2274273
4. M.M. Arslanov, G. LaForte, T.A. Slaman, Relative enumerability in the difference hierarchy, J. Symb. Log. 63 (2), 411–420 (1998). DOI: https://doi.org/10.2307/2586839
5. S.B. Cooper, Computability theory, Chapman and Hall/CRC, New York, 2004. DOI: https://doi.org/10.1201/9781315275789
6. R. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.
Review
For citations:
Kalimullin I.I. Degrees of selector functions and relative computable categoricity. Mathematics and Theoretical Computer Science. 2023;1(4):67-80. (In Russ.) https://doi.org/10.26907/2949-3919.2023.4.67-80
Views:
252
Email this article 