The possible Turing degree of the nonzero member in a two element degree spectrum (Q1210135)

From MaRDI portal
Revision as of 19:04, 11 February 2024 by RedirectionBot (talk | contribs) (‎Removed claim: reviewed by (P1447): Item:Q247180)
scientific article
Language Label Description Also known as
English
The possible Turing degree of the nonzero member in a two element degree spectrum
scientific article

    Statements

    The possible Turing degree of the nonzero member in a two element degree spectrum (English)
    0 references
    16 May 1993
    0 references
    Ash and Nerode defined a recursive relation \(R\) on a recursive model \(A\) to be intrinsically recursive if in each recursive model \(B\) isomorphic to \(A\), the image of \(R\) is recursive. Not all relations \(R\) are intrinsically recursive, and in this paper the author continues her studies into the degree spectrum of such \(R\). The degree spectrum of \(R\) is the collection of Turing degrees realised by the images of \(R\). Such spectra can have uncountably many members, but can have other realisations. In an earlier paper [ibid. 55, No. 1, 51-65 (1991; Zbl 0756.03022)], the author established that there is a two-element degree spectrum whose nonzero degree can be realised by a \(\Delta_ 3^ 0- \Delta_ 2^ 0\) set. The present paper improves this to \(\Delta_ 2^ 0-\Sigma_ 1\). This is established via a technical result constructing a recursive family of r.e. sets with exactly two 1-1 recursive enumerations up to equivalence. This technical result is proven to quite an elaborate argument constituting the bulk of the paper and is of independent interest. Both this argument and the main result are modifications of an earlier argument of \textit{S. S. Goncharov} [Algebra Logika 19, 507-551 (1980; Zbl 0514.03029)].
    0 references
    intrinsically recursive relation
    0 references
    recursive model
    0 references
    degree spectrum
    0 references
    Turing degrees
    0 references
    recursive family of r.e. sets
    0 references

    Identifiers