A NOTE ON THE STRUCTURE OF MINIMAL DARK CEERS

2025

Толық мәтін Ашық қол жеткізу: Gold Метадеректер (CSL-JSON)
DOI 10.55452/1998-6688-2025-22-3-199-209
Деректер сенімділігі 70 орташа
Бұл баға қалай есептеледі

Ол жазбаның өзінің тексерілетін белгілерінен құралады: мақаланың DOI-і бар ма, оның деректерін қанша тәуелсіз дереккөз растады, міндетті өрістер толтырылған ба және соңғы растау қаншалықты жаңа. Дереккөздер арасындағы алшақтық пен идентификатордың болмауы бағаны төмендетеді. 80-нен бастап мән жазбаның қосымша тексерусіз жарияланғанын, 60-тан 79-ға дейін — оның сенімділігі төмен күйде жарияланғанын және қолмен тексеру ұсынылатынын білдіреді. Редактор қолмен тексерген жазбаны қайта есептеу 90-нан төмен түсірмейді. Бұл — мақаланың өзіне емес, ол туралы деректерімізге берілген баға.

Аңдатпа

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.