Hostname: page-component-7bb8b95d7b-fmk2r Total loading time: 0 Render date: 2024-09-13T03:49:46.195Z Has data issue: false hasContentIssue false

Interpretability and definability in therecursively enumerable degrees

Published online by Cambridge University Press:  01 September 1998

A Nies
Affiliation:
Department of Mathematics, 5734 S. University Avenue, University of Chicago, Chicago, IL 60637, USA. E-mail: [email protected]
RA Shore
Affiliation:
Department of Mathematics, White Hall, Cornell University, Ithaca, NY 14853-7901, USA. E-mail: [email protected]
TA Slaman
Affiliation:
Department of Mathematics, 5734 S. University Avenue, University of Chicago, Chicago, IL 60637, USA. E-mail: [email protected] Present address: Department of Mathematics, University of California at Berkeley, Berkeley CA 94720, USA. E-mail: [email protected]
Get access

Abstract

We investigate definability in $\mathcal{R}$, the recursively enumerable Turing degrees, using codings of standard models of arithmetic (SMAs) as a tool. First we show that an SMA can be interpreted in $\mathcal{R}$ without parameters. Building on this, we prove that the recursively enumerable $T$-degrees satisfy a weak form of the bi-interpretability conjecture which implies that all jump classes $\mathrm{Low}_n$ and $\mathrm{High}_{n-1}$$(n\ge 2)$ are definable in $\mathcal{R}$ without parameters and, more generally, that all relations on $\mathcal{R}$ that are definable in arithmetic and invariant under the double jump are actually definable in $\mathcal{R}$. This partially answers Soare's Question 3.7 (R. Soare, {\emRecursively enumerable sets and degrees} (Springer, Berlin, 1987), Chapter XVI).

1991 Mathematics Subject Classification: primary 03D25, 03D35; secondary 03D30.

Type
Research Article
Copyright
London Mathematical Society 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)