Ershov hierarchy and the T-jump (Q1120565)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Ershov hierarchy and the T-jump
scientific article

    Statements

    Ershov hierarchy and the T-jump (English)
    0 references
    1988
    0 references
    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 \textit{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}\).
    0 references
    Kleene system of ordinal symbols
    0 references
    Ershov hierarchy
    0 references
    T-jump operator
    0 references
    limit ordinal
    0 references

    Identifiers