RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2019 Volume 58, Number 3, Pages 297–319 (Mi al896)

This article is cited 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.

UDC: 510.54

Received: 11.04.2018
Revised: 24.09.2019

DOI: 10.33048/alglog.2019.58.301


 English version:
Algebra and Logic, 2019, 58:3, 199–213

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024