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

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)].