Abstract:
We study the computable reducibility $\leq_c$ for equivalence relations
in the Ershov hierarchy. For an arbitrary notation $a$ for a nonzero
computable ordinal, it is stated that there exist a
$\Pi^{-1}_a$-universal
equivalence relation and a weakly precomplete
$\Sigma^{-1}_a$-universal
equivalence relation. We prove that for any
$\Sigma^{-1}_a$ equivalence relation
$E$, there is a weakly precomplete
$\Sigma^{-1}_a$ equivalence relation
$F$ such
that $E\leq_c F$.
For finite levels $\Sigma^{-1}_m$ in the Ershov hierarchy at which
$m=4k+1$
or $m=4k+2$, it is shown that there exist infinitely many
$\leq_c$-degrees containing weakly precomplete, proper $\Sigma^{-1}_m$
equivalence relations.
Citation:
N. A. Bazhenov, B. S. Kalmurzaev, “Weakly precomplete equivalence relations in the Ershov hierarchy”, Algebra Logika, 58:3 (2019), 297–319; Algebra and Logic, 58:3 (2019), 199–213
This publication is cited in the following 3 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
I. Yu. Mogilnykh, “Perfect codes from $\mathrm{PGL}(2,5)$ in Star graphs”, Sib. elektron. matem. izv., 17 (2020), 534–539
N. A. Bazhenov, M. Mustafa, L. San Mauro, M. M. Yamaleev, “Minimal equivalence relations in hyperarithmetical and analytical hierarchies”, Lobachevskii J. Math., 41:2, SI (2020), 145–150