RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2019 Volume 60, Number 2, Pages 290–305 (Mi smj3076)

This article is cited in 2 papers

Rogers semilattices for families of equivalence relations in the Ershov hierarchy

N. A. Bazhenovab, B. S. Kalmurzaevc

a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
c Al-Farabi Kazakh National University, Almaty, Kazakhstan

Abstract: The paper studies Rogers semilattices for families of equivalence relations in the Ershov hierarchy. For an arbitrary notation $a$ of a nonzero computable ordinal, we consider $\Sigma^{-1}_a$-computable numberings of the family of all $\Sigma^{-1}_a$ equivalence relations. We show that this family has infinitely many pairwise incomparable Friedberg numberings and infinitely many pairwise incomparable positive undecidable numberings. We prove that the family of all c.e. equivalence relations has infinitely many pairwise incomparable minimal nonpositive numberings. Moreover, we show that there are infinitely many principal ideals without minimal numberings.

Keywords: Rogers semilattice, Ershov hierarchy, equivalence relation, computable numbering, Friedberg numbering, minimal numbering, universal numbering, principal ideal.

UDC: 510.55

Received: 13.06.2018
Revised: 13.06.2018
Accepted: 19.12.2018

DOI: 10.33048/smzh.2019.60.204


 English version:
Siberian Mathematical Journal, 2019, 60:2, 223–234

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024