EXPANDING THE REALS BY CONTINUOUS FUNCTIONS ADDS NO COMPUTATIONAL POWER
- 26 September 2022
- journal article
- research article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 88 (3), 1083-1102
- https://doi.org/10.1017/jsl.2022.66
Abstract
We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel quotient of the reals reduces to it.Keywords
This publication has 18 references indexed in Scilit:
- Borel structures: a brief surveyPublished by Cambridge University Press (CUP) ,2013
- Fixed points for the jump operatorAlgebra and Logic, 2011
- A jump inversion theorem for the semilattices of sigma-degreesSiberian Advances in Mathematics, 2010
- A certain reducibility on admissible setsSiberian Mathematical Journal, 2009
- Notes on the Jump of a StructureLecture Notes in Computer Science, 2009
- A Jump Inversion Theorem for the Degree SpectraJournal of Logic and Computation, 2008
- A Jump Inversion Theorem for the Degree SpectraLecture Notes in Computer Science, 2007
- Classifying Borel StructuresPublished by Springer Science and Business Media LLC ,1992
- Borel Structures for First-order and Extended LogicsStudies in Logic and the Foundations of Mathematics, 1985
- Degrees of recursively saturated modelsTransactions of the American Mathematical Society, 1984