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