|
Sibirskii Matematicheskii Zhurnal, 2010, Volume 51, Number 6, Pages 1435–1439
(Mi smj2172)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Computable numberings of families of low sets and Turing jumps in the Ershov hierarchy
M. Kh. Faizrahmanov Kazan State University, Kazan
Abstract:
If $\nu$ and $\mu$ are some $\Delta^0_2$-computable numberings of families of sets of the naturals then $P(x,y)\Leftrightarrow\nu(x)'\not=\mu(y)$ is a $\Sigma^0_2$-predicate. Deriving corollaries from this result, we obtain a sufficient condition for existence of a $\Delta^0_2$-computable numbering of the subfamily of all sets in a given family with the Turing jumps belonging to a fixed level of the Ershov hierarchy, and we deduce existence of a $\Sigma^{-1}_\omega$-computable numbering of the family of all superlow sets.
Keywords:
computable numbering, Ershov hierarchy, constructive ordinal, low set, superlow set.
Received: 17.05.2009
Citation:
M. Kh. Faizrahmanov, “Computable numberings of families of low sets and Turing jumps in the Ershov hierarchy”, Sibirsk. Mat. Zh., 51:6 (2010), 1435–1439; Siberian Math. J., 51:6 (2010), 1135–1138
Linking options:
https://www.mathnet.ru/eng/smj2172 https://www.mathnet.ru/eng/smj/v51/i6/p1435
|
Statistics & downloads: |
Abstract page: | 523 | Full-text PDF : | 98 | References: | 63 | First page: | 4 |
|