Abstract In 1998 R. Downey formulated a problem: to describe a property $P$ of classical order types, which guarantees that if $\mathcal{L}$ is a low linear order and $P$ holds for the order type of $\mathcal{L}$ then $\mathcal{L}$ is isomorphic to a computable linear order. We find a new such property $P$. Also, we give an upper bound on a complexity of an isomorphism between computable and low copies and show that this bound is sharp.

Abstract A low linear order with no computable copy constructed by C. Jockusch and R. Soare has Hausdorff rank equal to $2$ . In this regard, the question arises, how simple can be a low linear order with no computable copy from the point of view of the linear order type? The main result of this work is an example of a low strong $\eta $ -representation with no computable copy that is the simplest possible example.

In several classes of countable structures it is known that every hyperarithmetic structure has a computable presentation up to bi-embeddability. In this article we investigate the complexity of embeddings between bi-embeddable structures in two such classes, the classes of linear orders and Boolean algebras. We show that if L is a computable linear order of Hausdorff rank n, then for every bi-embeddable copy of it there is an embedding computable in 2n−1 jumps from the atomic diagrams. We furthermore show that this is the best one can do: Let L be a computable linear order of Hausdorff rank n≥1, then 0(2n−2) does not compute embeddings between it and all its computable bi-embeddable copies. We obtain that for Boolean algebras which are not superatomic, there is no hyperarithmetic degree computing embeddings between all its computable bi-embeddable copies. On the other hand, if a computable Boolean algebra is superatomic, then there is a least computable ordinal α such that 0(α) computes embeddings between all its computable bi-embeddable copies. The main technique used in this proof is a new variation of Ash and Knight's pairs of structures theorem.