The possible Turing degree of the nonzero member in a two element degree spectrum
type: Item
instance of: scholarly article
title: The possible Turing degree of the nonzero member in a two element degree spectrum
zbMATH Open document ID: 0773.03027
DOI: 10.1016/0168-0072(93)90190-O
author: Valentina Harizanov
published in: Annals of Pure and Applied Logic
publication date: 1993-05-16T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 03C57
Mathematics Subject Classification ID: 03D30
zbMATH DE Number: 169661
zbMATH Keywords: intrinsically recursive relation
zbMATH Keywords: recursive model
zbMATH Keywords: degree spectrum
zbMATH Keywords: Turing degrees
zbMATH Keywords: recursive family of r.e. sets
reviewed by: Rodney G. Downey
MaRDI profile type: Publication
cites work: Stability of recursive structures in arithmetical degrees
cites work: Computable single-valued numerations
cites work: Problem of the number of non-self-equivalent constructivizations
cites work: Q3331204
cites work: Uncountable degree spectra
cites work: Some effects of Ash-Nerode and other decidability conditions on degree spectra
cites work: Q4040892
full work available at URL: 0168-0072(93)90190-o
OpenAlex ID: W2032686575
description: scientific article; zbMATH DE number 169661