Some effects of Ash-Nerode and other decidability conditions on degree spectra (Q1182431): Difference between revisions

Many examples in recursive algebra/model theory/combinatorics can be viewed as asking when it is possible to find in the isomorphism type of a recursive model \(M\) with a recursive \((\Sigma_ n\), \(\pi_ n\), etc.) relation \(R\) a recursive copy of \(M\) with the image of \(R\) failing to be recursive (resp. \(\Sigma_ n\), \(\pi_ n)\). This question has been extensively studied by Ash, Knight, Moses, Goncharov, Nerode and others. \textit{C. J. Ash} and \textit{A. Nerode} [Aspects of effective algebra, Proc. Conf., Monash Univ. 1979, 26-41 (1981; Zbl 0467.03041)] gave syntactic conditions, which, subject to certain decidability conditions, classified when the answer was ``yes'', i.e., when the relation was ``intrinsically recursive''. Here the author contributes to these studies by a partial classification of the degree spectrum of a relation \(R\). That is, the collection of degrees that can be realized as the degrees of images of \(R\). The author establishes that while it is possible for a recursive nonintrinsically \(\Sigma_ 1\) relation to be a two-element degree spectrum, a nonintrinsically r.e. relation \(R\) that satisfies the Ash- Nerode decidability condition has an infinite degree spectrum. The first result is shown to follow from the difficult construction of \textit{S. S. Goncharov} [Algebra Logika 14, 647-680 (1975; Zbl 0367.02023)] and the second combines an Ash-Nerode construction with a Friedberg-Muchnik one. The author gives a number of examples as to the range of the degree spectrum (particularly in the setting of linear orderings).