Numberings in the admissible sets over equivalence relations
Abstract
The paper contains a series of examples of admissible sets A in which the family of all A-c.e. sets has neither negative, nor positive computable A-numbeings.
Keywords
numberings,
decidable numberings,
positive numberings,
negative numberings,
computable numberings,
admissible sets
Supporting agencies: The work of I.Sh. Kalimullin is supported by the Russian Science Foundation (grant no. 22-21-20024) and performed under the development program of Volga Region Mathematical Center (agreement no. 075-02-2023-944). The work of V.G. Puzarenko is supported by project FWNF-2022-0012 (Classification Aspects of Syntax and Semantic of Logical Systems).
About the Authors
I. Sh. Kalimullin
Kazan Federal University, Volga Region Mathematical Center
Russian Federation
Russian Federation
Kalimullin Iskander Shagitovich
18 Kremlyovskaya str., Kazan 420008
V. G. Puzarenko
Sobolev Institute of Mathematics SB RAS; Novosibirsk State University
Russian Federation
Russian Federation
Puzarenko Vadim Grigorevich
4 Acad. Koptyug Ave., Novosibirsk 630090, e-mail: vagrig@math.nsc.ru
1 Pirogov str., Novosibirsk 630090
References
1. R.M. Friedberg, Three theorems on recursive enumeration. I: Decomposition. II: Maximal set. III: Enumeration without duplication, J. Symbolic Logic 23 (3), 309–316 (1958). DOI: https://doi.org/10.2307/2964290.
2. V.G. Puzarenko, Decidable Computable A-numberings, Algebra and logic 41 (5), 314–322 (2002). DOI: https://doi.org/10.1023/A:102093180
3. V.G. Puzarenko, Computability in special models, Sib. Math. J. 46 (1), 148–165 (2005). DOI: https://doi.org/10.1007/s11202-005-0016-z
4. I.Sh. Kalimullin, V.G. Puzarenko, M.K. Faizrakhmanov, Positive Numberings in Admissible Sets, Sib. Math. J. 61 (3), 478–489 (2020). DOI: https://doi.org/10.1134/S003744662003009X.
5. Yu.L. Ershov, Definability and Computability, Springer-Verlag, New York, 1996.
6. Yu.L. Ershov, Theory of Numberings, Nauka, M., 1977 (in Russian).
7. J. Barwise, Admissible Sets and Structures, Springer, 1975.
8. R. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987.
9. Yu.L. Ershov. Decidability Problems and Constructive Models, Nauka, M., 1980 [in Russian].
10. Yu.L. Ershov, S.S. Goncharov, Constructive Models, Springer-Verlag, New York, 2000.
11. V.G. Puzarenko, Generalized Enumerations and Definability of the field R in Admissible Sets, Vestnik NGU: ser. mat., mech., inf. 3 (2), 107–117 (2003) [in Russian].
12. V.G. Puzarenko, On computability over models of decidable theories, Algebra and logic, 39 (2), 98–113 (2000). DOI: https://doi.org/10.1007/BF02681664
13. Yu.L. Ershov, V.G. Puzarenko, A.I. Stukachev, HF-Computability, Computability in Context: Computation and Logic in the Real World (ed. S Barry Cooper and Andrea Sorbi), 169–242 (2011). DOI: https://doi.org/10.1142/p577.
Review
For citations:
Kalimullin I.Sh., Puzarenko V.G. Numberings in the admissible sets over equivalence relations. Mathematics and Theoretical Computer Science. 2023;1(3):33-45. (In Russ.)
Views:
124
Email this article 