Computable embeddability for algebraic structures

In computability theory, the standard tool to classify preorders is provided by the computable reducibility. If R and S are preorders with domain ω, then R is computably reducible to S if and only if there is a computable function f such that for all x and y, xRy f(x)Sf(y). We study the complexity of preorders which arise in a natural way in computable structure theory. We prove that the relation of computable isomorphic embeddability among computable torsion abelian groups is a Σ⁰₃ complete preorder. A similar result is obtained for computable distributive lattices. We show that the relation of primitive recursive embeddability among punctual structures (in the setting of Kalimullin et al.) is a Σ⁰₂ complete preorder.