We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
COMPARING TWO VERSIONS OF THE REALS.
- Authors
IGUSA, G.; KNIGHT, J. F.
- Abstract
Schweber [10] defined a reducibility that allows us to compare the computing power of structures of arbitrary cardinality. Here we focus on the ordered field ${\cal R}$ of real numbers and a structure ${\cal W}$ that just codes the subsets of ω. In [10], it was observed that ${\cal W}$ is reducible to ${\cal R}$. We prove that ${\cal R}$ is not reducible to ${\cal W}$. As part of the proof, we show that for a countable recursively saturated real closed field ${\cal P}$ with residue field k, some copy of ${\cal P}$ does not compute a copy of k.
- Subjects
REAL numbers; COMPUTABILITY logic; ARBITRARY constants; CARDINAL numbers; MATHEMATICAL proofs; RECURSIVE functions
- Publication
Journal of Symbolic Logic, 2016, Vol 81, Issue 3, p1115
- ISSN
0022-4812
- Publication type
Article
- DOI
10.1017/jsl.2015.77