Turing jumps in the Ershov hierarchy. (English. Russian original) Zbl 1287.03094

Faizrakhmanov, M. Kh.

Algebra Logic 50, No. 3, 279-289 (2011); translation from Algebra Logika 50, No. 3, 399-414 (2011).

In this paper the authors study infinite levels of the Ershov difference hierarchy which are proper for Turing jumps of degrees. It is proved that if a set \(A\) and an ordinal \(\alpha<\omega^{\omega}\) such that \(A'\in\Pi^{-1}_{\alpha}\), then \(A'\in\Delta^{-1}_{\alpha}\), if \(A'\in\Sigma^{-1}_{\omega^n}\), \(n>0\), then \(A'\in\Delta^{-1}_{\omega^n}\), if \(A'\in\Sigma^{-1}_{\omega^nm}\) for some \(m,n>0\), then \(A'\in\Delta^{-1}_{\omega^n}\), and for every \(n>0\) there exists a set \(A\) such that \(A'\in\Delta^{-1}_{\omega^{n+1}}-\Delta^{-1}_{\omega^{n}}\).

Reviewer: Marat M. Arslanov (Kazan)

MSC:

03D55	Hierarchies of computability and definability
03D28	Other Turing degree structures

Keywords:

Turing jumps; Ershov hierarchy; constructive ordinals; superlow sets

References:

[1]	Yu. L. Ershov, ”On a hierarchy of sets I,” Algebra Logika, 7, No. 1, 47–73 (1968). · Zbl 0216.00901
[2]	Yu. L. Ershov, ”On a hierarchy of sets II,” Algebra Logika, 7, No. 4, 15–47 (1968). · Zbl 0216.00902
[3]	Yu. L. Ershov, ”On a hierarchy of sets III,” Algebra Logika, 9, No. 1, 34–51 (1970).
[4]	M. M. Arslanov, The Ershov Hierarchy, A Special Course in Mathematics, Kazan State Univ., Kazan (2007). · Zbl 1279.03067
[5]	H. G. Carstens, ” $ \(\backslash\)Delta_2\^0 $ -Mengen,” Arch. Math. Logik Grundl., 18, 55–65 (1976). · Zbl 0356.02039 · doi:10.1007/BF02007257
[6]	B. Schaeffer, ”Dynamic notions of genericity and array noncomputability,” Ann. Pure Appl. Log., 95, Nos. 1–3, 37–69 (1998). · Zbl 0932.03048 · doi:10.1016/S0168-0072(98)00014-1
[7]	S. Walk, ”Towards a definition of the array computable degrees,” Ph. D. Thesis, Univ. Notre Dame (1999).
[8]	I. Sh. Kalimullin, ”Some notes on degree spectra of the structures,” Lect. Notes Comput. Sci., 4497, Springer-Verlag, Berlin (2007), pp. 389–397. · Zbl 1151.03330