|
This article is cited in 3 scientific papers (total in 3 papers)
Weakly precomplete equivalence relations in the Ershov hierarchy
N. A. Bazhenovab, B. S. Kalmurzaevc a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
c Al-Farabi Kazakh National University
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.
Keywords:
Ershov hierarchy, equivalence relation,
computable reducibility, universal equivalence relation, weakly
precomplete equivalence relation.
Received: 11.04.2018 Revised: 24.09.2019
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
Linking options:
https://www.mathnet.ru/eng/al896 https://www.mathnet.ru/eng/al/v58/i3/p297
|
Statistics & downloads: |
Abstract page: | 218 | Full-text PDF : | 18 | References: | 26 | First page: | 2 |
|