Article
Intrinsic Reducibilities
Mathematical Logic Quarterly
(2000)
Abstract
Let . We show that for many reducibilities, the requirement that a relation be intrinsically reducible to the α-th jump of a countable mode A has a syntactic equivalent. Furthermore, we show that many reducibilities coincide in such a situation.
Keywords
- bounded query classes,
- n-recursive enumerability,
- Intrinsically reducible,
- n-query reducibility,
- Truth-table reducibility
Disciplines
Publication Date
2000
DOI
10.1002/1521-3870(200008)46:3<393::AID-MALQ393>3.0.CO;2-H
Publisher Statement
This is the pre-peer reviewed version of the following article: McNicholl, Timothy H. "Intrinsic Reducibilities." Mathematical Logic Quarterly 46, no. 3 (2000): 393-407, which has been published in final form at http://dx.doi.org/10.1002/1521-3870(200008)46:3<393::AID-MALQ393>3.0.CO;2-H. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving.
© 2000 WILEY-VCH Verlag Berlin GmbH, Fed. Rep. of Germany.
Citation Information
Timothy H. McNicholl. "Intrinsic Reducibilities" Mathematical Logic Quarterly Vol. 46 Iss. 3 (2000) p. 393 - 407 Available at: http://works.bepress.com/timothy-mcnicholl/23/