RUS  ENG
Full version
JOURNALS // Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki // Archive

Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2014 Volume 156, Book 1, Pages 22–30 (Mi uzku1226)

This article is cited in 4 papers

On limitwise monotonic reducibility of $\Sigma_2^0$-sets

D. Kh. Zainetdinov, I. Sh. Kalimullin

Institute of Mathematics and Mechanics, Kazan (Volga Region) Federal University, Kazan, Russia

Abstract: In this paper, we study the properties of lm-reducibility of sets belonging to the class of $\Sigma_2^0$-sets. In particular, we prove the existence of incomparable $\Sigma_2^0$-sets with respect to lm-reducibility. In addition, we construct an infinite uniform sequence of incomparable $\Sigma_2^0$-sets relative to lm-reducibility and show that every countable partial order can be embedded into the class of all lm-degrees of $\Sigma_2^0$-sets.

Keywords: computable functions, $\Sigma_2^0$-sets, limitwise monotonic functions, limitwise monotonic sets.

UDC: 510.5

Received: 27.01.2014



© Steklov Math. Inst. of RAS, 2024