Possible degrees in recursive copies (Q1902615): Difference between revisions

A recursive structure is a recursive set \(A\) together with recursive relations \(R\) on \(A\). We denote this \((A, R)\). It is of interest to know if there are isomorphic structures (called `recursive copies') \((A', R')\) where \(A'\) is recursive but \(R'\) is not. More generally, the degree spectra of \((A, R)\) is the set of Turing degrees \({\mathbf a}\) such that there is some recursive copy \((A', R')\) where \(R'\) has degree \({\mathbf a}\). \textit{V. S. Harizanov} [Ann. Pure Appl. Log. 55, 51-65 (1991; Zbl 0756.03022)] has isolated a syntactic condition (with additional effectiveness conditions) which is necessary and sufficient for \((A, R)\) to have degree spectra all the r.e. degrees. It is an open question to determine a condition under which the degree spectra is all the \(\Sigma_\alpha\) degrees. This paper shows that several conjectures of conditions are false.