Locally finite and finitely approximated unoids over computably separable equivalences
https://doi.org/10.26907/2949-3919.2024.1.55-73
Abstract
We prove that every coinfinite set is a characteristic transversal of a suitably computably separable equivalence relation, over which only locally finite, locally finite separable and finitely approximable unary algebras are represented. Similar properties for uniformly computable separable equivalences are considered.
About the Author
N. K. Kasymov
National Universitet of Uzbekistan
Uzbekistan
Uzbekistan
Nadimulla Khabibullaevich Kasymov
4 Universitetskaya str., Tashkent 100174
References
1. Yu.L. Ershov, Theory of numberings, Nauka, M., 1977 [in Russian.].
2. Yu. L. Ershov, Theory of numberings, in: E.R. Griffor (ed.), Handbook of computability theory (Stud. Logic Found. Math., 140), Amsterdam, Elsevier, 1999, 473–503. DOI: https://doi.org/10.1016/S0049-237X(99)80030-5
3. R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987. URL: https://link.springer.com/book/9783540666813
4. S.S. Goncharov, Yu.L. Ershov, Constructive Models, Siberian School of Algebra and Logic. Consultants Bureau, New York, 2000.
5. P.M. Cohn, Universal algebra, MAIA 6, D. Reidel Publishing Co., Dordrecht–Boston, Mass., 1981. DOI: https://doi.org/10.1007/978-94-009-8399-1
6. A.I.Mal’tsev, Algebraic Systems, Springer-Verlag, New York–Heidelberg, 1973. DOI: https://doi.org/10.1007/978-3-642-65374-2
7. 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
8. 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
9. 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
10. M.M. Arslanov, On effectively hypersimple sets, Algebra Logic 8 (2), 79–85 (1969). DOI: https://doi.org/10.1007/BF02219827
11. M.Kh. Faizrakhmanov, Universal generalized computable numberings and hyperimmunity, Algebra Logic 56 (4), 337–347 (2017). DOI: https://doi.org/10.1007/s10469-017-9454-5
12. N.Kh. Kasymov, Algebras with finitely approximable positively representable enrichments, Algebra Logic 26 (6), 441–450 (1987). DOI: https://doi.org/10.1007/BF01988315
13. A.I. Mal’tsev, Constructive algebras I, Russian Math. Surveys 16 (3), 77–129 (1961). DOI: https://doi.org/10.1070/RM1961v016n03ABEH001120
14. N.Kh. Kasymov, Positive algebras with congruences of finite index, Algebra Logic 30 (6), 190–199 (1991). DOI: https://doi.org/10.1007/BF01978852
15. N.Kh. Kasymov, Recursively separable enumerated algebras, Russian Math. Surveys 51 (3), 509–538 (1996). DOI: https://doi.org/10.1070/RM1996v051n03ABEH002913
16. N.Kh. Kasymov, Positive algebras with nonetherian congruence lattices, Siberian Math. J. 33 (2), 338–341 (1992). DOI: https://doi.org/10.1007/BF00971109
17. N.Kh. Kasymov, Positive algebras with countable congruence lattices, Algebra Logic 31 (1), 12–23 (1992). URL: https://doi.org/10.1007/BF02259854
18. 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
19. N.Kh. Kasymov, Homomorphisms onto negative algebras, Algebra Logic 31 (2), 81–89 (1992). DOI: https://doi.org/10.1007/BF02259847
20. N.Kh. Kasymov, Homomorphisms onto effectively separable algebras, Siberian Math. J. 57 (1), 36–50 (2016). DOI: https://doi.org/10.1134/S0037446616010055
21. 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
22. A.I. Mal’tsev, On the general theory of algebraic systems, Amer. Math. Soc. Transl. Ser. 2 27, 125–142 (1963).
23. N.Kh. Kasymov, R.N. Dadazhanov, S.K. Zhavliev, Structures of degrees of negative representations of linear orders, Russ. Math. 65 (12), 27–46 (2021). DOI: https://doi.org/10.3103/S1066369X21120045
24. N.Kh. Kasymov, Computably separable numbering of locally finite separable algebras, Sib. Electron. Math. Rep. (to appear).
25. C.G. Jockusch, J.C. Owings, Weakly semirecursive sets, J. Symb. Log. 55 (2), 637–644 (1990). DOI: https://doi.org/10.2307/2274653
26. 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
27. N.Kh. Kasymov, Algebras over negative equivalences, Algebra logic 33 (1), 46–48 (1994). DOI: https://doi.org/10.1007/BF00739416
Review
For citations:
Kasymov N.K. Locally finite and finitely approximated unoids over computably separable equivalences. Mathematics and Theoretical Computer Science. 2024;2(1):55-73. (In Russ.) https://doi.org/10.26907/2949-3919.2024.1.55-73
Views:
536
Email this article 