Embeddings of computable structures (Q976535)

The authors consider four notions of embedding property, namely, a class of computable presentations of computable structures is said to have {\parindent5.5mm \begin{itemize}\item[a)] the strong embedding property if for all its structures \(A_0\) and \(A_1\), if \(A_0\) is embeddable into \(A_1\) then there exists a computable embedding from \(A_0\) to \(A_1\); \item[b)] the weak domain embedding property if for all its structures \(A_0\) and \(A_1\), if \(A_0\) is embeddable into \(A_1\) then there is a computable presentation \(A_0'\cong A_0\) and a computable embedding from \(A_0'\) to \(A_1\); \item[c)] the weak range embedding property if for all its structures \(A_0\) and \(A_1\), if \(A_0\) is embeddable into \(A_1\) then there is a computable presentation \(A_1'\cong A_1\) and a computable embedding from \(A_0\) to \(A_1'\); \item[d)] the weak embedding property if for all its structures \(A_0\) and \(A_1\), if \(A_0\) is embeddable into \(A_1\) then there exist computable presentations \(A_0'\cong A_0\), \(A_1'\cong A_1\), and a computable embedding from \(A_0'\) to \(A_1'\). \end{itemize}} The authors give a complete picture of implications between these properties and give examples showing that there are no other implications. The examples used to distinguish these properties are found among the natural classes of structures, like computable ordered abelian groups, computable trees, some class of computable posets, computable equivalences, computable Boolean algebras, and computable algebraically closed fields.