Index sets for classes of positive preorders

B. S. Kalmurzaev ; N. A. Bazhenov ; M. A. Torebekova

Algebra i logika, Tome 61 (2022) no. 1, pp. 42-76.

Résumé

We study the complexity of index sets with respect to a universal computable numbering of the family of all positive preorders. Let $\leq_c$ be computable reducibility on positive preorders. For an arbitrary positive preorder $R$ such that the $R$-induced equivalence $\sim_R$ has infinitely many classes, the following results are obtained. The index set for preorders $P$ with $R\leq_c P$ is $\Sigma^0_3$-complete. A preorder $R$ is said to be self-full if the range of any computable function realizing the reduction $R\leq_c R$ intersects all $\sim_R$-classes. If $L$ is a non-self-full positive linear preorder, then the index set of preorders $P$ with $P\equiv_c L$ is $\Sigma^0_3$-complete. It is proved that the index set of self-full linear preorders is $\Pi^0_3$-complete.

Détail

Keywords: positive preorder, positive equivalence, positive linear preorder, computable reducibility, index set.

Bibliographie

[1] Yu. L. Ershov, “Pozitivnye ekvivalentnosti”, Algebra i logika, 10:6 (1971), 620–650

[2] Yu. L. Ershov, Teoriya numeratsii, Nauka, M., 1977

[3] C. Bernardi, “On the relation provable equivalence and on partitions in effectively inseparable sets”, Stud. Log., 40:1 (1981), 29–37

[4] C. Bernardi, A. Sorbi, “Classifying positive equivalence relations”, J. Symb. Log., 48:3 (1983), 529–538

[5] A. H. Lachlan, “A note on positive equivalence relations”, Z. Math. Logik Grundlagen Math., 33 (1987), 43–46

[6] S. Gao, P. Gerdes, “Computably enumerable equivalence relations”, Stud. Log., 67:1 (2001), 27–59

[7] U. Andrews, A. Sorbi, “Joins and meets in the structure of ceers”, Computability, 8:3/4 (2019), 193–241

[8] U. Andrews, N. Schweber, A. Sorbi, “Self-full ceers and the uniform join operator”, J. Log. Comput., 30:3 (2020), 765–783

[9] U. Andrews, N. Schweber, A. Sorbi, “The theory of ceers computes true arithmetic”, Ann. Pure Appl. Logic, 171:8 (2020), 102811, 22 pp.

[10] U. Andrews, S. Lempp, J. S. Miller, K. M. Ng, L. S. Mauro, A. Sorbi, “Universal computably enumerable equivalence relations”, J. Symb. Log., 79:1 (2014), 60–88

[11] U. Andrews, A. Sorbi, “The complexity of index sets of classes of computably enumerable equivalence relations”, J. Symb. Log., 81:4 (2016), 1375–1395

[12] S. Badaev, A. Sorbi, “Weakly precomplete computably enumerable equivalence relations”, Math. Log. Q, 62:1/2 (2016), 111–127

[13] U. Andrews, S. A. Badaev, “On isomorphism classes of computably enumerable equivalence relations”, J. Symb. Log., 85:1 (2020), 61–86

[14] D. K. Kabylzhanova, “O pozitivnykh predporyadkakh”, Algebra i logika, 57:3 (2018), 279–284

[15] N. A. Bazhenov, B. S. Kalmurzaev, “O temnykh vychislimo perechislimykh otnosheniyakh ekvivalentnosti”, Sib. matem. zh., 59:1 (2018), 29–40

[16] S. A. Badaev, N. A. Bazhenov, B. S. Kalmurzaev, “O strukture pozitivnykh predporyadkov”, Algebra i logika, 59:3 (2020), 293–314

[17] R. I. Soare, Turing computability. Theory and applications, Theory Appl. Comput., Springer, Berlin, 2016

[18] S. A. Badaev, B. S. Kalmurzayev, D. K. Kabylzhanova, K. Sh. Abeshev, “Universal positive preorders”, Izvestiya NAN RK. Ser. fiz.-mat., 2018, no. 6(322), 49–53

[19] U. Andrews, S. Badaev, A. Sorbi, “A survey on universal computably enumerable equivalence relations”, Computability and complexity, Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday, Lect. Notes Comput. Sci., 10010, eds. A. Day et al., Springer, Cham, 2017, 418–451

[20] A. Gavrushkin, B. Khoussainov, F. Stephan, “Reducibilities among equivalence relations induced by recursively enumerable structures”, Theor. Comput. Sci., 612 (2016), 137–152