×

zbMATH — the first resource for mathematics

Ershov hierarchy and the T-jump. (English. Russian original) Zbl 0673.03033
Algebra Logic 27, No. 4, 292-301 (1988); translation from Algebra Logika 27, No. 4, 464-478 (1988).
Let \((O,<_ O)\) be the Kleene system of ordinal symbols, let \(\Sigma_ a^{-1}\), \(\Delta_ a^{-1}\) (a\(\in O)\) be the classes of the Ershov hierarchy [see Yu. L. Ershov’s papers, Algebra Logika 7, No.4, 15- 47 (1968; Zbl 0216.009) and ibid. 9, No.1, 34-51 (1970; Zbl 0233.02017)], and let ’ be the T-jump operator. The following main theorem is proved: 1) For any r.e. set A and any \(a\in O\) not being the least one, there exists a set \(R\in \Sigma_ a^{-1}\) such that \(R'\equiv_ TA'\) and R is not T-equivalent to any set of \(\Delta_ a^{-1}\). 2) For any r.e. set A and any limit ordinal \(a\in O\) there exists a set \(R\in \Delta_ a^{-1}\) such that \(R'\equiv_ TA'\) and R is not T-equivalent to any set of \(\cup_{b<_ Oa}\Sigma_ b^{-1}\).
Reviewer: Phan Dinh Dieu
MSC:
03D55 Hierarchies of computability and definability
03D30 Other degrees and reducibilities in computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] H. Rogers, Theory of Recursive Functions and Effective Computability [Russian translation], Mir, Moscow (1972).
[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] V. L. Selivanov, ”The Ershov hierarchy,” Sib. Mat. Zh.,26, No. 1, 134–149 (1985). · Zbl 0591.03025
[5] Sh. T. Ishmukhametov, ”Differences of recursively enumerable sets, their degrees of undecidability and index sets,” Doctoral Dissertation, Kazan Univ. (1986). · Zbl 0615.03028
[6] C. Jockusch and R. Shore, ”Pseudo-jump operators. II,” J. Symb. Logic,49, No. 4, 1205–1236 (1984). · Zbl 0574.03026 · doi:10.2307/2274273
[7] R. Epstein, R. Haas, and R. Kramer, ”Hierarchies of sets and degrees below0’,” Lect. Notes Math., No. 859 (1981). · Zbl 0467.03046
[8] A. H. Lachlan, ”Two theorems on many-one degrees of recursively enumerable sets,” Algebra Logika,11, No. 2, 216–229 (1972).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.