Positive preorders. (English. Russian original) Zbl 1485.03113
Algebra Logic 57, No. 3, 182-185 (2018); translation from Algebra Logika 57, No. 3, 279-284 (2018).
Summary: We consider positive preorders, i.e., computably enumerable equivalences, endowed with the structure of a partial order between equivalence classes. On positive preorders, a computable reducibility relation and the corresponding notion of degree of a positive preorder are introduced in the natural way. It is proved that the degree of any positive preorder contains either exactly one computable isomorphism class or an infinite set of computable isomorphism classes.
MSC:
| 03C57 | Computable structure theory, computable model theory |
| 03D45 | Theory of numerations, effectively presented structures |
References:
| [1] | Yu. L. Ershov, “Positive equivalences,” Algebra and Logic, 10, No. 6, 378-394 (1971). · Zbl 0276.02024 · doi:10.1007/BF02218645 |
| [2] | S. Gao and P. Gerdes, “Computably enumerable equivalence relations,” Stud. Log., 67, No. 1, 27-59 (2001). · Zbl 0981.03046 · doi:10.1023/A:1010521410739 |
| [3] | U. Andrews, S. Lempp, J. S. Miller, K. M. Ng, L. S. Mauro, and A. Sorbi, “Universal computably enumerable equivalence relations,” J. Symb. Log., 79, No. 1, 60-88 (2014). · Zbl 1338.03076 · doi:10.1017/jsl.2013.8 |
| [4] | A. Gavrushkin, B. Khoussainov, and F. Stephan, “Reducibilities among equivalence relations induced by recursively enumerable structures,” Theor. Comput. Sci., 612, 137-152 (2016). · Zbl 1338.03077 · doi:10.1016/j.tcs.2015.11.042 |
| [5] | S. Badaev and A. Sorbi, “Weakly precomplete computably enumerable equivalence relations,” Math. Log. Q., 62, Nos. 1/2, 111-127 (2016). · Zbl 1361.03043 · doi:10.1002/malq.201500057 |
| [6] | N. Kh. Kasymov and B. M. Khusainov, “Positive equivalences with finite classes and related algebras,” Sib. Math. J., 33, No. 5, 923-927 (1992). · Zbl 0781.03019 · doi:10.1007/BF00971000 |
| [7] | N. Kh. Kasymov and B. M. Khusainov, “Positive and negative numerations of algebras,” Vych. Sist., 139, 103-110 (1991). |
| [8] | S. P. Odintsov and V. L. Selivanov, “Arithmetic hierarchy and ideals of enumerated Boolean algebras,” Sib. Math. J., 30, No. 6, 952-960 (1989). · Zbl 0711.03016 · doi:10.1007/BF00970918 |
| [9] | E. B. Fokina and S. D. Friedman, “Equivalence relations on classes of computable structures,” in Lect. Notes Comput. Sci., 5635, Springer-Verlag, Berlin (2009), pp. 198-207. · Zbl 1268.03039 |
| [10] | S. D. Friedman and L. Motto Ros, “Analytic equivalence relations and bi-embeddability,” J. Symb. Log., 76, No. 1, 243-266 (2011). · Zbl 1256.03050 · doi:10.2178/jsl/1294170999 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
