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

Sibirsk. Mat. Zh., 2021 Volume 62, Number 1, Pages 31–41 (Mi smj7535)

On universal pairs in the Ershov hierarchy

N. A. Bazhenovab, M. Mustafac, S. S. Ospichevab

a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Novosibirsk State University, Novosibirsk, Russia
c Nazarbayev University, Nur-Sultan, Kazakhstan

Abstract: We develop the Ershov theory of $C$-classes for some finite families of sets in the Ershov hierarchy. We generalize the result by Muchnik on multiple $m$-reducibility as follows: There exists an $m$-universal pair of disjoint sets for each level of the Ershov hierarchy.

Keywords: Ershov hierarchy, $m$-reducibility, $C$-class, computable numbering.

UDC: 510.5

MSC: 35R30

Received: 07.05.2020
Revised: 18.09.2020
Accepted: 09.10.2020

DOI: 10.33048/smzh.2021.62.103


 English version:
Siberian Mathematical Journal, 2021, 62:1, 23–31

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024