RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2010 Volume 51, Number 6, Pages 1435–1439 (Mi smj2172)

This article is cited 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.

UDC: 510.5

Received: 17.05.2009


 English version:
Siberian Mathematical Journal, 2010, 51:6, 1135–1138

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024