Kleene Index Sets and Functional $m$-Degrees
Mohrherr, Jeanleah
J. Symbolic Logic, Tome 48 (1983) no. 1, p. 829-840 / Harvested from Project Euclid
A many-one degree is functional if it contains the index set of some class of partial recursive functions but does not contain an index set of a class of r.e. sets. We give a natural embedding of the r.e. m-degrees into the functional degrees of $0'$. There are many functional degrees in $0'$ in the sense that every partial-order can be embedded. By generalizing, we show there are many functional degrees in every complete Turning degree. There is a natural tie between the studies of index sets and partial-many-one reducibility. Every partial-many-one degree contains one or two index sets.
Publié le : 1983-09-14
Classification: 
@article{1183741343,
     author = {Mohrherr, Jeanleah},
     title = {Kleene Index Sets and Functional $m$-Degrees},
     journal = {J. Symbolic Logic},
     volume = {48},
     number = {1},
     year = {1983},
     pages = { 829-840},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183741343}
}
Mohrherr, Jeanleah. Kleene Index Sets and Functional $m$-Degrees. J. Symbolic Logic, Tome 48 (1983) no. 1, pp.  829-840. http://gdmltest.u-ga.fr/item/1183741343/