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

Algebra Logika, 2018 Volume 57, Number 3, Pages 338–361 (Mi al853)

This article is cited in 3 papers

Turing degrees in refinements of the arithmetical hierarchy

V. L. Selivanovab, M. M. Yamaleevb

a Ershov Institute of Informatics Systems, pr. Akad. Lavrent'eva 6, Novosibirsk, 630090 Russia
b Kazan (Volga Region) Federal University, ul. Kremlevskaya 18, Kazan, 420008 Russia

Abstract: We investigate the problem of characterizing proper levels of the fine hierarchy (up to Turing equivalence). It is known that the fine hierarchy exhausts arithmetical sets and contains as a small fragment finite levels of Ershov hierarchies (relativized to $\varnothing^n$, $n<\omega$), which are known to be proper. Our main result is finding a least new (i.e., distinct from the levels of the relativized Ershov hierarchies) proper level. We also show that not all new levels are proper.

Keywords: Ershov hierarchy, fine hierarchy, arithmetical hierarchy, Turing degrees.

UDC: 510.51+510.54+510.531+510.532

Received: 12.12.2016
Revised: 20.10.2017

DOI: 10.17377/alglog.2018.57.306


 English version:
Algebra and Logic, 2018, 57:3, 222–236

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024