Abstract:
We study computably enumerable (c.e.) relations on the set of naturals. A binary relation R on ω is computably reducible to a relation S (which is denoted by R≤cS) if there exists a computable function f(x) such that the conditions (xRy) and (f(x)Sf(y)) are equivalent for all x and y. An equivalence relation E is called dark if it is incomparable with respect to ≤c with the identity equivalence relation. We prove that, for every dark c.e. equivalence relation E there exists a weakly precomplete dark c.e. relation F such that E≤cF. As a consequence of this result, we construct an infinite increasing ≤c-chain of weakly precomplete dark c.e. equivalence relations. We also show the existence of a universal c.e. linear order with respect to ≤c.
N. A. Bazhenov was supported by the Russian Foundation for Basic Research (Grant 16-31-60058-mol_a_dk).
B. S. Kalmurzaev was supported by the Science Committee of the Republic of Kazakhstan (Grant GF4/3952).
Citation:
N. A. Bazhenov, B. S. Kalmurzaev, “On dark computably enumerable equivalence relations”, Sibirsk. Mat. Zh., 59:1 (2018), 29–40; Siberian Math. J., 59:1 (2018), 22–30
This publication is cited in the following 10 articles:
Serikzhan A. Badaev, Nikolay A. Bazhenov, Birzhan S. Kalmurzayev, Manat Mustafa, “On diagonal functions for equivalence relations”, Arch. Math. Logic, 63:3-4 (2024), 259
B. S. Kalmurzaev, N. A. Bazhenov, D. B. Alish, “On universal positive graphs”, Siberian Math. J., 64:1 (2023), 83–93
N. Bazhenov, B. Kalmurzayev, M. Zubkov, “A note on joins and meets for positive linear preorders”, Sib. elektron. matem. izv., 20:1 (2023), 1–16
B. S. Kalmurzaev, N. A. Bazhenov, M. A. Torebekova, “Ob indeksnykh mnozhestvakh dlya klassov pozitivnykh predporyadkov”, Algebra i logika, 61:1 (2022), 42–76
B. S. Kalmurzayev, N. A. Bazhenov, M. A. Torebekova, “Index Sets for Classes of Positive Preorders”, Algebra Logic, 61:1 (2022), 30
S. A. Badaev, B. S. Kalmurzayev, N. K. Mukash, A. A. Khamitova, “Special classes of positive preorders”, Sib. elektron. matem. izv., 18:2 (2021), 1657–1666
S. A. Badaev, N. A. Bazhenov, B. S. Kalmurzaev, “The structure of computably enumerable preorder relations”, Algebra and Logic, 59:3 (2020), 201–215
N. A. Bazhenov, B. S. Kalmurzaev, “Rogers semilattices for families of equivalence relations in the Ershov hierarchy”, Siberian Math. J., 60:2 (2019), 223–234
N. A. Bazhenov, B. S. Kalmurzaev, “Weakly precomplete equivalence relations in the Ershov hierarchy”, Algebra and Logic, 58:3 (2019), 199–213