The possible Turing degree of the nonzero member in a two element degree spectrum (Q1210135): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Stability of recursive structures in arithmetical degrees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Computable single-valued numerations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Problem of the number of non-self-equivalent constructivizations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3331204 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Uncountable degree spectra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some effects of Ash-Nerode and other decidability conditions on degree spectra / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4040892 / rank | |||
Normal rank |
Revision as of 15:48, 17 May 2024
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