Computability-theoretic properties of injection structures

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.