This article is cited in 14 papers

Computability-theoretic properties of injection structures

D. Cenzer^a, V. Harizanov^b, J. B. Remmel<sup>c

a</sup> Dep. Math., Univ. Florida, Gainesville, FL 32611 USA
^b Dep. Math., George Washington Univ., Washington, DC 20052 USA
^c Dep. Math., Univ. California-San Diego, La Jolla, CA 92093 USA

Abstract: We study computability-theoretic properties of computable injection structures and the complexity of isomorphisms between these structures. It is proved that a computable injection structure is computably categorical iff it has finitely many infinite orbits. Again, a computable injection structure is $\Delta^0_2$-categorical iff it has finitely many orbits of type $\omega$ or finitely many orbits of type $Z$. Furthermore, every computably categorical injection structure is relatively computably categorical, and every $\Delta^0_2$-categorical injection structure is $\Delta^0_2$-categorical. Analogs of these results are investigated for $\Sigma^0_1$-, $\Pi^0_1$-, and $n$-c.e. injection structures.
We study the complexity of the set of elements with orbits of a given type in computable injection structures. For example, it is proved that for every c.e. Turing degree $\mathbf b$, there is a computable injection structure $\mathcal A$ in which the set of all elements with finite orbits has degree $\mathbf b$, and for every $\Sigma^0_2$ Turing degree $\mathbf c$, there is a computable injection structure $\mathcal B$ in which the set of elements with orbits of type $\omega$ has degree $\mathbf c$. We also have various index set results for infinite computable injection structures. For example, the index set of infinite computably categorical injection structures is a $\Sigma^0_3$-complete set, and the index set of infinite $\Delta^0_2$-categorical injection structures is a $\Sigma^0_4$-complete set.
We explore the connection between the complexity of the character and the first-order theory of a computable injection structure. It is shown that for an injection structure with a computable character, there is a decidable structure isomorphic to it. However, there are computably categorical injection structures with undecidable theories.

Keywords: computability theory, injections, permutations, effective categoricity, computable model theory.

UDC: 510.5

Received: 27.11.2012
Revised: 27.07.2013

 English version: Algebra and Logic, 2014, 53:1, 39–69

Bibliographic databases:

• 
• 
•