On $p$-Reducibility of Computable Numerations
Matematičeskie zametki, Tome 69 (2001) no. 1, pp. 31-35
Citer cet article
Voir la notice de l'article provenant de la source Math-Net.Ru
It is proved that if $\nu_1$ and $\nu_2$ are two computable numerations of a certain family of recursively enumerable sets such that $\nu_2<_p\nu_1$ and $\nu_1$ is not a $p$-principal numeration, then there exists a computable numeration $\nu_0$ p-incomparable with $\nu_1$ such that $\nu_2<_p\nu_0$. This yields the description of injective objects and the absence of numerated sets projective in the category $K_p$ conforming to $p$-reducibility of computable numeration.
[1] Degtev A. N., “O svodimosti numeratsii”, Matem. sb., 112:2 (1980), 207–219 | MR | Zbl
[2] Ershov Yu. L., Teoriya numeratsii, Nauka, M., 1977
[3] Degtev A. N., “On $p$-reducibility of numerations”, Ann. of Pure and Appl. Logic, 63 (1993), 57–60 | DOI | MR | Zbl
[4] Marchenkov S. S., “O vychislimykh numeratsiyakh semeistv obscherekursivnykh funktsii”, Algebra i logika, 11:5 (1972), 588–607 | MR | Zbl