© University of Kent - Contact | Feedback | Legal | FOI | Cookies
Embeddings in the strong reducibilities between 1 and npm
P. Watson
Mathematical Logic Quarterly, 43(4):182-196, December 1997.Abstract
We consider the strongest (most restricted) forms of enumeration reducibility, those that occur between 1- and (unknown variable npm)$-reducibility inclusive. By defining two new reducibilities (which we call (unknown variable n)1$- and (unknown variable n)i$-reducibility) which are counterparts to 1- and (unknown variable i)$-reducibility (respectively) in the same way that (unknown variable n)m$- and (unknown variable npm)$- reducibility are counterparts to (unknown variable m)$- and (unknown variable pm)$-reducibility respectively, we bring out the structure (under the natural relation on reducibilities `strong with respect to') of the strong reducibilities.
By further restricting (unknown variable n)1$- and (unknown variable n)m$-reducibility we are able to define infinite families of reducibilities which isomorphically embed the r.e. Turing degrees. Thus the many well-known results in the theory of the r.e. Turing degrees have counterparts in the theory of strong reducibilities.
We are also able to positively answer the question of whether there exist distinct reducibilities (unknown variable y)$ and (unknown variable z)$ between (unknown variable e)$ and (unknown variable m)$ such that there exists a non-trivial (unknown variable y)$-contiguous (unknown variable z)$ degree.
Bibtex Record
@article{736,
author = {P. Watson},
title = {Embeddings in the strong reducibilities between 1 and npm},
month = {December},
year = {1997},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1997/736},
journal = {Mathematical Logic Quarterly},
number = {4},
volume = {43},
}