kaz29Вестник Казахстанско-Британского технического университетаHerald of the Kazakh-British Technical University1998-66882959-8109Казахстанско-Британский Технический Университет10.55452/1998-6688-2025-22-3-199-209kaz29-2116Research ArticleМАТЕМАТИЧЕСКИЕ НАУКИMATHEMATICAL SCIENCESО СТРУКТУРЕ МИНИМАЛЬНЫХ ТЕМНЫХ ВЫЧИСЛИМО ПЕРЕЧИСЛИМЫХ ОТНОШЕНИЙ ЭКВИВАЛЕНТНОСТИA NOTE ON THE STRUCTURE OF MINIMAL DARK CEERShttps://orcid.org/0000-0003-0444-2394БадаевС. А.BadaevS. A.

д.ф.-м.н., профессор

г. Алматы

Dr.Phys.-Math.Sc., Professor

Almaty

sbadaev@gmail.comhttps://orcid.org/0009-0005-2550-2079ИскаковА. М.IskakovA. M.

докторант

г. Алматы

PhD student

Almaty

bheadr73@gmail.comhttps://orcid.org/0000-0002-4386-5915КалмурзаевБ. С.KalmurzayevB. S.

PhD, ассоциированный профессор

г. Алматы

PhD, Associate Professor

Almaty

birzhan.kalmurzayev@gmail.comhttps://orcid.org/0000-0003-0075-4438АсқарбекқызыА.AskarbekkyzyA.

докторант

г. Алматы

PhD student

Almaty 

ms.askarbekkyzy@gmail.comКазахстанско-Британский технический университетКазахстанKazakh-British Technical UniversityKazakhstan202527092025223199209Copyright © Бадаев С.А., Искаков А.М., Калмурзаев Б.С., Асқарбекқызы А., 20252025Бадаев С.А., Искаков А.М., Калмурзаев Б.С., Асқарбекқызы А.Badaev S.A., Iskakov A.M., Kalmurzayev B.S., Askarbekkyzy A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.kbtu.edu.kz/jour/article/view/2116

Структура вычислимо перечислимых отношений эквивалентности относительно вычислимой сводимости (коротко – ceers) активно развивается на протяжении последних 25 лет. В обзоре Эндрюса и Сорби было показано множество структурных свойств структуры ceers. Эндрюс и Сорби исследовали существование супремумов и инфимумов. Они разделили структуру на две определимые части: темные (эквивалентности без эффективного трасверсаля) и светлые (с эффективным трансверсалем) эквивалентности и показали существование бесконечного числа минимальных (в том смысле, что строго под ними могут быть только конечные эквивалентности) темных ceers. Минимальные темные эквивалентности имеют следующее свойство: каждая пара классов вычислимо неотделима. Также в теории ceers изучаются слабо предполные эквивалентности (то есть те эквивалентности, для которых не существует вычислимых диагональных функций). Также у данных эквивалентностей каждая пара классов вычислимо неотделима. В связи с этим возникает вопрос о существовании минимальных темных эквивалентностей, не являющихся слабо предполными. В данной статье дается положительный ответ на этот вопрос. Через FS обозначим в.п. отношение эквивалентности все классы которого конечны. Эндрюс, Швебер, Сорби показали существование темных FS экивалентностей. В этой статье доказывается, что над любой темной FS эквивалентностью существует бесконечная антицепь темных FS эквивалентностей.

The structure of computably enumerable equivalence relations under computable reducibility (commonly referred to as ceers) has been actively developed over the past 25 years. A comprehensive survey by Andrews and Sorbi presented numerous structural properties of ceers, most notably investigating the existence of joins and meets in the degree structure of ceers. They divided the structure into two definable parts: dark ceers (ceers without an effective transversal) and light ceers (ceers with an effective transversal). They also showed the existence of an infinite number of minimal dark ceers (modulo equivalence relations with finitely many classes). Minimal dark ceers exhibit the distinctive property that every pair of classes is computably inseparable. Furthermore, the classes of weakly precomplete equivalence relations (i.e. those that lack a computable diagonal functions) are also computably inseparable. In this context, a natural question arises: do minimal dark equivalence relations exist that are not weakly precomplete? This paper provides an affirmative answer to this question. Moreover, we establish the existence of an infinite family of non-weakly precomplete minimal dark ceers that avoids lower cone of a given non-universal ceer. We denote by FC the set of ceers consisting of only finite classes. Andrews, Schweber, Sorbi showed the existence of dark FC equivalences. In this paper, we prove that over any dark FC ceer, there exists an infinite antichain of dark FC ceers.

отношение эквивалентностивычислимо перечислимое отношение эквивалентностивычислимая сводимостьслабо предполные отношения эквивалентностиEquivalence relationcomputably enumerable equivalence relationcomputable reducibilityweakly precomplete equivalence relationThe work is supported by Science Committee of Ministry of Science and Higher Education of the Republic of Kazakhstan (Grand no. AP19676989).ReferencesErshov, Y. L. Positive equivalences. Algebra and Logic, 10(6), 378–394 (1971).Ershov, Y. L. Positive equivalences. Algebra and Logic, 10(6), 378–394 (1971).Bernardi, C. On the relation provable equivalence and on partitions in effectively inseparable sets. Studia Logica, 40, 29–37 (1981).Bernardi, C. On the relation provable equivalence and on partitions in effectively inseparable sets. Studia Logica, 40, 29–37 (1981).Bernardi, C., Sorbi, A. Classifying positive equivalence relations. The Journal of Symbolic Logic, 48(3), 529–538 (1983).Bernardi, C., Sorbi, A. Classifying positive equivalence relations. The Journal of Symbolic Logic, 48(3), 529–538 (1983).Andrews, U., Lempp, S., Miller, J. S., Ng, K. M., San Mauro, L., Sorbi, A. Universal computably enumerable equivalence relations. The Journal of Symbolic Logic, 79(1), 60–88 (2014).Andrews, U., Lempp, S., Miller, J. S., Ng, K. M., San Mauro, L., Sorbi, A. Universal computably enumerable equivalence relations. The Journal of Symbolic Logic, 79(1), 60–88 (2014).Andrews, U., Badaev, S., Sorbi, A. A survey on universal computably enumerable equivalence relations. In Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (pp. 418–451). Cham: Springer International Publishing (2016).Andrews, U., Badaev, S., Sorbi, A. A survey on universal computably enumerable equivalence relations. In Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday (pp. 418–451). Cham: Springer International Publishing (2016).Andrews, U., Sorbi, A. The complexity of index sets of classes of computably enumerable equivalence relations. The Journal of Symbolic Logic, 81(4), 1375–1395 (2016).Andrews, U., Sorbi, A. The complexity of index sets of classes of computably enumerable equivalence relations. The Journal of Symbolic Logic, 81(4), 1375–1395 (2016).Bazhenov, N. A., Kalmurzaev, B. S. On dark computably enumerable equivalence relations. Siberian Mathematical Journal, 59, 22–30 (2018).Bazhenov, N. A., Kalmurzaev, B. S. On dark computably enumerable equivalence relations. Siberian Mathematical Journal, 59, 22–30 (2018).Ng, K. M., Yu, H. On the degree structure of equivalence relations under computable reducibility. Notre Dame J. Formal Logic, 60(4), 733–761 (2019).Ng, K. M., Yu, H. On the degree structure of equivalence relations under computable reducibility. Notre Dame J. Formal Logic, 60(4), 733–761 (2019).Andrews, U., Badaev, S. A. On isomorphism classes of computably enumerable equivalence relations. The Journal of Symbolic Logic, 85(1), 61–86 (2020).Andrews, U., Badaev, S. A. On isomorphism classes of computably enumerable equivalence relations. The Journal of Symbolic Logic, 85(1), 61–86 (2020).Andrews, U., Schweber, N., Sorbi, A. Self-full ceers and the uniform join operator. Journal of Logic and Computation, 30(3), 765–783 (2020).Andrews, U., Schweber, N., Sorbi, A. Self-full ceers and the uniform join operator. Journal of Logic and Computation, 30(3), 765–783 (2020).Andrews, U., Sorbi, A. Effective inseparability, lattices, and preordering relations. The Review of Symbolic Logic, 14(4), 838–865 (2021).Andrews, U., Sorbi, A. Effective inseparability, lattices, and preordering relations. The Review of Symbolic Logic, 14(4), 838–865 (2021).Delle Rose, V., San Mauro, L., Sorbi, A. A note on the category of equivalence relations. Algebra and Logic, 60(5), 295–307 (2021).Delle Rose, V., San Mauro, L., Sorbi, A. A note on the category of equivalence relations. Algebra and Logic, 60(5), 295–307 (2021).Andrews, U., Belin, D. F., San Mauro, L. On the structure of computable reducibility on equivalence relations of natural numbers. The Journal of Symbolic Logic, 88(3), 1038–1063 (2023).Andrews, U., Belin, D. F., San Mauro, L. On the structure of computable reducibility on equivalence relations of natural numbers. The Journal of Symbolic Logic, 88(3), 1038–1063 (2023).Ershov Yu. L. The Theory of Enumerations, Nauka, Moscow (1977). [Russian].Ershov Yu. L. The Theory of Enumerations, Nauka, Moscow (1977). [Russian].Badaev S. A. On weakly pre-complete positive equivalences, Sib. Math. J., 32 (2), 321–323 (1991).Badaev S. A. On weakly pre-complete positive equivalences, Sib. Math. J., 32 (2), 321–323 (1991).Badaev, S.A., Sorbi, A. Weakly precomplete computably enumerable equivalence relations. Math. Log. Quart. 62, No. 1–2, 111–127 (2016).Badaev, S.A., Sorbi, A. Weakly precomplete computably enumerable equivalence relations. Math. Log. Quart. 62, No. 1–2, 111–127 (2016).Badaev, S.A., Bazhenov, N.A., Kalmurzayev, B.S., Mustafa, M. On diagonal functions for equivalence relations. Archive for Mathematical Logic. 63, 259–278 (2023).Badaev, S.A., Bazhenov, N.A., Kalmurzayev, B.S., Mustafa, M. On diagonal functions for equivalence relations. Archive for Mathematical Logic. 63, 259–278 (2023).Andrews, U., Sorbi, A. Joins and meets in the structure of ceers. Computability, 8 (3–4), 193–241 (2019).Andrews, U., Sorbi, A. Joins and meets in the structure of ceers. Computability, 8 (3–4), 193–241 (2019).Gao, S., Gerdes, P. Computably enumerable equivalence relations. Studia Logica, 27–59 (2001).Gao, S., Gerdes, P. Computably enumerable equivalence relations. Studia Logica, 27–59 (2001).Badaev, S. A., Kalmurzaev, B. S., Mukash, N. K., Khamitova, A. A. Special classes of positive preorders. Sib. Elektron. Mat. Izv., 18:2, 1657–1666 (2021).Badaev, S. A., Kalmurzaev, B. S., Mukash, N. K., Khamitova, A. A. Special classes of positive preorders. Sib. Elektron. Mat. Izv., 18:2, 1657–1666 (2021).Andrews, U., Schweber, N., Sorbi, A. The theory of ceers computes true arithmetic. Ann. Pure Appl. Logic. (171:8), 102811 (2020).Andrews, U., Schweber, N., Sorbi, A. The theory of ceers computes true arithmetic. Ann. Pure Appl. Logic. (171:8), 102811 (2020).Soare R. Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, SpringerVerlag, Berlin (1987).Soare R. Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, SpringerVerlag, Berlin (1987).

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