Separable numberings of universal algebras
https://doi.org/10.26907/2949-3919.2024.4.66-102
Abstract
The review outlines the foundations of the theory of separable numberings of universal algebras.
Keywords
separable numbered algebra,
effectively separable numbering,
negative and effectively separable approximability,
translationally complete and pre-complete algebra,
topological numbered algebra,
subdirect indecomposability,
Artinian congruence lattice,
algebraic and logical data structure specifications
Supporting agencies: The work is performed under the development program of Volga Region Mathematical Center (agreement no. 075-02-2024-1438).
About the Author
N. Kh. Kasymov
National University of Uzbekistan
Uzbekistan
Uzbekistan
Nadimulla Khabibullaevich Kasymov
4 Universitetskaya str., Tashkent 100174
References
1. A.I. Malt’sev, Constructive algebras. I, Russian Math. Surveys, 16 (3), 77–129 (1961). DOI: https://doi.org/10.1070/rm1961v016n03abeh001120
2. Yu.L. Ershov, Decidability problems and constructive models, Nauka, M., 1980 [in Russian].
3. Yu.L. Ershov, Theory of numberings, in: E.R.Griffor (ed.), Handbook of computability theory (Stud. Logic Found. Math., 140), Elsevier, Amsterdam, 1999, 473–503. DOI: https://doi.org/10.1016/S0049-237X(99)80030-5
4. S.S. Goncharov, Yu.L. Ershov, Constructive Models, Siberian School of Algebra and Logic. Consultants Bureau, New York, 2000.
5. N.G. Khisamiev, Arithmetic hierarchy of abelian groups, Siberian Math. J. 29 (6), 987–999 (1988). DOI: https://doi.org/10.1007/BF00972425
6. S.P. Odintsov, V.L. Selivanov, Arithmetic hierarchy and ideals of enumerated Boolean algebras, Siberian Math. J. 30 (6), 952–960 (1989). DOI: https://doi.org/10.1007/BF00970918
7. V.A. Uspenskii, On computable operations, Dokl. AN SSSR 103 (5), 773–776 (1955) [in Russian]. URL: https://archive.org/details/uspensky-1955-dan-103-5-computable-operations/Uspensky_1955_DAN_103_5_Typeset_by_Zolin/mode/2up
8. V.A. Uspenskii, Systems of denumerable sets and their enumeration, Dokl. AN SSSR 105 (6), 1155–1158 (1955) [in Russian]. URL: https://archive.org/details/uspensky-1955-dan-105-6-enumerable-sets-numerations/Uspensky_1955_DAN_105_6_Typeset_by_Zolin/mode/2up
9. A. Nerode, General topology and partial recursive functionals, Summaries Summer Inst. Symbolic Logic 1957, 247–251 (1960).
10. A.I. Mal’tsev, On the theory of computable families of objects, Algebra Logic 3 (4), 5–31 (1964) [in Russian]. URL: https://www.mathnet.ru/rus/al1010
11. Yu.L. Ershov, Theory of numberings, Nauka, M., 1977 [in Russian].
12. N.Kh. Kasymov, Recursively separable enumerated algebras, Russian Math. Surveys 51 (3), 509–538 (1996). DOI: https://doi.org/10.1070/RM1996v051n03ABEH002913
13. A.I. Mal’tsev, Positive and negative enumerations, Dokl. AN SSSR 160 (2), 278–280 (1965) [in Russian]. URL: https://www.mathnet.ru/rus/dan30557
14. A.S. Morozov, A question of Higman, Algebra Logic 29 (1), 22–26 (1990). DOI: https://doi.org/10.1007/BF01980217
15. W. Baur, Rekursive Algebren mit Kettenbedingungen, Z. Math. Logik Grundlag. Math. 20 (1–3), 37–46 (1974). DOI: https://doi.org/10.1002/malq.19740200105
16. W. Baur, Über rekursive Strukturen, Invent. Math. 23 (2), 89–95 (1974). DOI: https://doi.org/10.1007/BF01405162
17. V.A. Uspenskii, A.L. Semenov, Algorithm theory: key discoveries and applications, Nauka, M., 1987 [in Russian].
18. J.C.C. McKinsey, The decision problem for some classes of sentences without quantifiers, J. Symbol. Logic 8 (3), 61–76 (1943). DOI: https://doi.org/10.2307/2268172
19. J.A. Bergstra, J.V. Tucker, A characterization of computable data types by means of a finite, equational specification method, Lecture Notes in Comput. Sci. 85, 76–90 (1980). DOI: https://doi.org/10.1007/3-540-10003-2_61
20. N.Kh. Kasymov, Homomorphisms onto negative algebras, Algebra Logic 31 (2), 81–89 (1992). DOI: https://doi.org/10.1007/BF02259847
21. N.Kh. Kasymov, Homomorphisms onto effectively separable algebras, Siberian Math. J. 57 (1), 36–50 (2016). DOI: https://doi.org/10.1134/S0037446616010055
22. N.Kh. Kasymov, A dual problem in the theory of constructive models, Vychisl. Sist. 129, 137–143 (1989) [in Russian]. URL: https://zbmath.org/1052.03527
23. U. Andrews, S. Lempp, J.S. Miller, K.M. Ng, L.S. Mauro, A. Sorbi, Universal computably enumerable equivalence relations, J. Symb. Logic 79 (1), 60–88 (2014). DOI: http://doi.org/10.1017/jsl.2013.8
24. U. Andrews, A. Sorbi, Joins and meets in the structure of ceers, Computability 8 (3–4), 193–241 (2019). DOI: https://doi.org/10.3233/COM-180098
25. U. Andrews, D.F. Belin, L. San Mauro, On the structure of computable reducibility on equivalence relations of natural numbers, J. Symb. Logic 88 (3), 1038–1063 (2023). DOI: https://doi.org/10.1017/jsl.2022.28
26. N.Kh. Kasymov, F.N. Ibragimov, Separable enumerations of division rings and effective embeddability of rings therein, Siberian Math. J. 60 (1), 62–70 (2019). DOI: https://doi.org/10.1134/S0037446619010075
27. N.Kh. Kasymov, A.S. Morozov, I.A. Khodzhamuratova, T<sub>1</sub>-separable numberings of subdirectly indecomposable algebras, Algebra Logic 60 (4), 263–278 (2021). DOI: https://doi.org/10.1007/s10469-021-09651-x
28. N.Kh. Kasymov, R.N. Dadazhanov, S.K. Zhavliev, Uniform m-equivalences and numberings of classical systems, Sib. Electron. Math. Rep. 19 (1), 49–65 (2022). DOI: http://doi.org/10.33048/semi.2022.19.005
29. N.Kh. Kasymov, Enumerated algebras with uniformly recursive-separable classes, Siberian Math. J. 34 (5), 869–882 (1993). DOI: https://doi.org/10.1007/BF00971403
30. N.Kh. Kasymov, Positive algebras with congruences of finite index, Algebra Logic 30 (6), 190–199 (1991). DOI: https://doi.org/10.1007/BF01978852
31. N.Kh. Kasymov, Positive algebras with nonetherian congruence lattices, Siberian Math. J. 33 (2), 338–341 (1992). DOI: https://doi.org/10.1007/BF00971109
32. N.Kh. Kasymov, Positive algebras with countable congruence lattices, Algebra Logic 31 (1), 12–23 (1992). DOI: https://doi.org/10.1007/BF02259854
33. R.N. Dadazhanov, N.Kh. Kasymov, I.A. Khodzhamuratova, Uniformly computably separable algebras with effectively splittable families of negative congruences, Siberian Math. J. 63 (3), 466–475 (2022). DOI: https://doi.org/10.1134/S0037446622030077
34. C.G. Jockusch, Semurecursive sets and positive reducibility, Trans. Amer. Math. Soc. 131 (2), 420–436 (1968). DOI: https://doi.org/10.2307/1994957
35. C.G. Jockusch, J.C. Owings, Weakly semirecursive sets, J. Symb. Logic 55 (2), 637–644 (1990). DOI: https://doi.org/10.2307/2274653
36. N.Kh. Kasymov, A.S. Morozov, Lower semilattices of separable congruences of numbered algebras, Siberian Math. J. 64 (4), 864–876 (2023). DOI: https://doi.org/10.1134/S0037446623040080
37. N.Kh. Kasymov, Computably separable numberings of locally finite separable algebras, Sib. Electron. Math. Rep. 21 (1), 315–346 (2024) [in Russian]. DOI: https://doi.org/10.33048/semi.2024.21.024
38. N.Kh. Kasymov, Locally finite and residually finite unoids over computably separable equivalences, MTCS 2 (1), 55–74 (2024) [in Russian]. DOI: https://doi.org/10.26907/2949-3919.2024.1.55-73
39. N.Kh. Kasymov, Separation axioms and partitions of the set of natural numbers, Siberian Math. J. 34 (3), 468–471 (1993). DOI: https://doi.org/10.1007/BF00971221
40. N.Kh. Kasymov, I.A. Khodzhamuratova, Topological spaces over algorithmic representations of universal algebras, J. Math. Sci. 245 (3), 311–322 (2020). DOI: https://doi.org/10.1007/s10958-020-04692-6
41. R.N. Dadazhanov, N.R. Karimova, N.Kh. Kasymov, Effective compacts over co-immune sets, Uzbek Math. J. 63 (3), 26–32 (2019). DOI: https://doi.org/10.29229/uzmj.2019-3-3
42. B. Khoussainov, T. Slaman, P. Semukhin, ∏<sup>0</sup><sub>1</sub>-Presentasions of Algebras, Arch. Math. Logic 45 (6), 769–781 (2006). DOI: https://doi.org/10.1007/s00153-006-0013-3
43. A.I. Malcev, On the immersion of an algebraic ring into a field, Math. Ann. 113 (1), 686–691 (1937). URL: https://doi.org/10.1007/BF01571659
44. S. Kamin, Some definitions for algebraic data type specifications, SIGPLAN Notes 14 (3), 28–37 (1979). DOI: https://doi.org/10.1145/988071.988075
45. J.A. Goguen, J. Meseguer, Completeness of many-sorted equational logic, Houston J. Math. 11 (3), 307–334 (1985).
46. M. Broy, W. Dosch, H. Partsch, P. Pepper, M. Wirsing, Existential quantifiers in abstract data types, Lect. Notes in Comp. Sci. 71, 73–87, (1979). DOI: https://doi.org/10.1007/3-540-09510-1_7
47. S.S. Goncharov, Data models and languages for their description, Trans. Amer. Math. Soc. 143, 139–152 (1989).
48. N.Kh. Kasymov, A.S. Morozov, Logical aspects of the theory of abstract data types, Vychisl. Sist. 122, 73–96 (1987) [in Russian]. URL: https://zbmath.org/0712.68067
49. M. Majster, Data types, abstract data types and their specification problem, Theor. Comp. Sci. 8 (1), 89–127 (1979). DOI: https://doi.org/10.1016/0304-3975(79)90059-8
50. D. Kapur, Specifications of Majster’s traversable stack and Veloso’s traversable stack, SIGPLAN Notes 14 (5), 46–53 (1979). DOI: https://doi.org/10.1145/988090.988096
51. N.Kh. Kasymov, Algebras with finitely approximable positively representable enrichments, Algebra Logic 26 (6), 441–450 (1987). DOI: https://doi.org/10.1007/BF01988315
52. J.W. Lloyd, Foundations of logic programming, Springer-Verlag, Berlin, 1987. DOI: https://doi.org/10.1007/978-3-642-83189-8
53. N.Kh. Kasymov, Positive models and universal propositions, Vychisl. Sist. 133, 3–13 (1990) [in Russian]. URL: https://zbmath.org/?q=an:0752.03016
54. A.I. Mal’cev, Algebraic Systems, Springer-Verlag, New York–Heidelberg, 1973. DOI: https://doi.org/10.1007/978-3-642-65374-2
55. A.I. Mal’cev, Algorithms and recursive functions, Wolters-Noordhoff Publishing, Groningen, 1970.
56. N.Kh. Kasymov, F.N. Ibragimov, Computably separable models, J. Math. Sci. 264 (6), 746–767 (2022). DOI: https://doi.org/10.1007/s10958-022-06033-1
57. N.Kh. Kasymov, The number of Q-congruences in positive algebras, Algebra Logic 31 (3), 182–187 (1992). DOI: https://doi.org/10.1007/BF02259947
58. N. Kasymov, N. Karimova, B. Khoussainov, Defining algorithmically presented structures in first-order logic, Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 1–13, art. No. 47 (2024). DOI: https://doi.org/10.1145/3661814.3662120
59. N.Kh. Kasymov, B.M. Khoussainov, Finitely generated enumerable and absolutely locally finite algebras, Vychisl. Sist. 116, 3–15 (1986) [in Russian]. URL: https://zbmath.org/0646.03042
60. N.Kh. Kasymov, Algebras over negative equivalences, Algebra Logic 33 (1), 46–48 (1994). DOI: https://doi.org/10.1007/BF00739416
61. N.Kh. Kasymov, Logical specifications of effectively separable data models, Russ. Math. 68 (6), 11–20 (2024). DOI: https://doi.org/10.3103/S1066369X24700397
Review
For citations:
Kasymov N.Kh. Separable numberings of universal algebras. Mathematics and Theoretical Computer Science. 2024;2(4):66-102. (In Russ.) https://doi.org/10.26907/2949-3919.2024.4.66-102
Views:
232
Email this article 