matatecsМатематика и теоретические компьютерные наукиMathematics and Theoretical Computer Science2949-3919Казанский (Приволжский) федеральный университет10.26907/2949-3919.2024.1.55-73matatecs-39Research ArticleСТАТЬИЛокально конечные и финитно аппроксимируемые уноиды над вычислимо отделимыми эквивалентностямиLocally finite and finitely approximated unoids over computably separable equivalencesКасымовН. Х.KasymovN. K.

Надимулла Хабибуллаевич Касымов 

ул. Университетская, д. 4, г. Ташкент, 100174 

Nadimulla Khabibullaevich Kasymov 

4 Universitetskaya str., Tashkent 100174 

nadim59@mail.ruНациональный университет Узбекистана им. Мирзо УлугбекаУзбекистанNational Universitet of UzbekistanUzbekistan202415042024215573Copyright © Касымов Н.Х., 20242024Касымов Н.Х.Kasymov N.K.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://matatecs.elpub.ru/jour/article/view/39

Доказано, что всякое кобесконечное множество является характеристической трансверсалью подходящей вычислимо отделимой эквивалентности, над которой представимы только локально конечные, локально финитно отделимые и финитно аппроксимируемые унарные алгебры. Рассмотрены аналогичные свойства для равномерно вычислимо отделимых эквивалентностей.

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.

вычислимо отделимая эквивалентностьравномерностьхарактеристическая трансверсальунарная алгебралокальная конечностьфинитная аппроксимируемостьлокально финитная отделимостьcomputably separable equivalenceuniformitycharacteristic transversalunary algebralocal finitenessfinite approximabilitylocally finite separabilityReferencesЮ.Л. Ершов, Теория нумераций, Наука, М., 1977.Yu.L. Ershov, Theory of numberings, Nauka, M., 1977 [in Russian.].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-5Yu. 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-5R.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/9783540666813R. 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С.С. Гончаров, Ю.Л. Ершов, Конструктивные модели, Научная книга, Новосибирск, 1999.S.S. Goncharov, Yu.L. Ershov, Constructive Models, Siberian School of Algebra and Logic. Consultants Bureau, New York, 2000.П.М. Кон, Универсальная алгебра, Мир, М., 1968.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А.И. Мальцев, Алгебраические системы, Наука, М., 1970.A.I.Mal’tsev, Algebraic Systems, Springer-Verlag, New York–Heidelberg, 1973. DOI: https://doi.org/10.1007/978-3-642-65374-2U. 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-180098U. 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-180098U. 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.28U. 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Н.Х. Касымов, Ф.Н. Ибрагимов, Отделимые нумерации тел и эффективная вложимость в них колец, Сиб. матем. журн. 60 (1), 82–94 (2019). DOI: https://doi.org/10.33048/smzh.2019.60.107N.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М.М. Арсланов, Об эффективно гиперпростых множествах, Алгебра и логика 8 (2), 143–153 (1969). URL: https://www.mathnet.ru/rus/al1187M.M. Arslanov, On effectively hypersimple sets, Algebra Logic 8 (2), 79–85 (1969). DOI: https://doi.org/10.1007/BF02219827М.Х. Файзрахманов, Универсальные обобщенно вычислимые нумерации и гипериммунность, Алгебра и логика 56 (4), 506–521 (2017). DOI: https://doi.org/10.17377/alglog.2017.56.408M.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Н.Х. Касымов, Об алгебрах с финитно аппроксимируемыми позитивно представимыми обогащениями, Алгебра и логика 26 (6), 715–730 (1987). URL: https://www.mathnet.ru/rus/al1999N.Kh. Kasymov, Algebras with finitely approximable positively representable enrichments, Algebra Logic 26 (6), 441–450 (1987). DOI: https://doi.org/10.1007/BF01988315А.И. Мальцев, Конструктивные алгебры. I, УМН 16 (3), 3–60 (1961). URL: https://www.mathnet.ru/rus/rm6619A.I. Mal’tsev, Constructive algebras I, Russian Math. Surveys 16 (3), 77–129 (1961). DOI: https://doi.org/10.1070/RM1961v016n03ABEH001120Н.Х. Касымов, Позитивные алгебры с конгруэнциями конечного индекса, Алгебра и логика 30 (3), 293–305 (1991). URL: https://www.mathnet.ru/rus/al2151N.Kh. Kasymov, Positive algebras with congruences of finite index, Algebra Logic 30 (6), 190–199 (1991). DOI: https://doi.org/10.1007/BF01978852Н.Х. Касымов, Рекурсивно отделимые нумерованные алгебры, УМН 51 (3), 145–176 (1996). DOI: https://doi.org/10.4213/rm971N.Kh. Kasymov, Recursively separable enumerated algebras, Russian Math. Surveys 51 (3), 509–538 (1996). DOI: https://doi.org/10.1070/RM1996v051n03ABEH002913Н.Х. Касымов, Позитивные алгебры с нетеровыми решетками конгруэнций, Сиб. матем. журн. 33 (2), 181–185 (1992). URL: https://www.mathnet.ru/rus/smj3208N.Kh. Kasymov, Positive algebras with nonetherian congruence lattices, Siberian Math. J. 33 (2), 338–341 (1992). DOI: https://doi.org/10.1007/BF00971109Н.Х. Касымов, Позитивные алгебры со счетными решетками конгруэнций, Алгебра и логика 31 (1), 21–37 (1992). URL: https://www.mathnet.ru/rus/al2179N.Kh. Kasymov, Positive algebras with countable congruence lattices, Algebra Logic 31 (1), 12–23 (1992). URL: https://doi.org/10.1007/BF02259854J.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_61J.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Н.Х. Касымов, О гомоморфизмах на негативные алгебры, Алгебра и логика 31 (2), 132–144 (1992). URL: https://www.mathnet.ru/rus/al21868. 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.28N.Kh. Kasymov, Homomorphisms onto negative algebras, Algebra Logic 31 (2), 81–89 (1992). DOI: https://doi.org/10.1007/BF02259847Н.Х. Касымов, О гомоморфизмах на эффективно отделимые алгебры, Сиб. матем. журн. 57 (1), 47–66 (2016). DOI: https://doi.org/10.17377/smzh.2016.57.105N.Kh. Kasymov, Homomorphisms onto effectively separable algebras, Siberian Math. J. 57 (1), 36–50 (2016). DOI: https://doi.org/10.1134/S0037446616010055Н.Х. Касымов, Нумерованные алгебры с равномерно рекурсивно отделимыми классами, Сиб. матем. журн. 34 (5), 85–102 (1993). URL: https://www.mathnet.ru/rus/smj836N.Kh. Kasymov, Enumerated algebras with uniformly recursive-separable classes, Siberian Math. J. 34 (5), 869–882 (1993). DOI: https://doi.org/10.1007/BF00971403А.И. Мальцев, К общей теории алгебраических систем, Матем. сб. 35 (1), 3–20 (1954). URL: https://www.mathnet.ru/rus/sm5264A.I. Mal’tsev, On the general theory of algebraic systems, Amer. Math. Soc. Transl. Ser. 2 27, 125–142 (1963).Н.Х. Касымов, Р.Н. Дадажанов, С.К. Джавлиев, Структуры степеней негативной представимости линейных порядков, Изв. вузов. Матем. 65 (12), 31–55 (2021). URL: https://doi.org/10.26907/0021-3446-2021-12-31-55N.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Н.Х. Касымов, Вычислимо отделимые нумерации локально финитно отделимых алгебр, Сиб. электрон. матем. изв. (принята к печати).N.Kh. Kasymov, Computably separable numbering of locally finite separable algebras, Sib. Electron. Math. Rep. (to appear).C.G. Jockusch, J.C. Owings, Weakly semirecursive sets, J. Symb. Log. 55 (2), 637–644 (1990). DOI: https://doi.org/10.2307/2274653C.G. Jockusch, J.C. Owings, Weakly semirecursive sets, J. Symb. Log. 55 (2), 637–644 (1990). DOI: https://doi.org/10.2307/2274653Н.Х. Касымов, А.С. Морозов, Нижние полурешетки отделимых конгруэнций нумерованных алгебр, Сиб. матем. журн. 64 (4), 753–769 (2023). DOI: https://doi.org/10.33048/smzh.2023.64.408N.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Н.Х. Касымов, Об алгебрах над негативными эквивалентностями, Алгебра и логика 33 (1), 76–90 (1994). URL: https://www.mathnet.ru/rus/al2257N.Kh. Kasymov, Algebras over negative equivalences, Algebra logic 33 (1), 46–48 (1994). DOI: https://doi.org/10.1007/BF00739416

The authors declare that there are no conflicts of interest present.