Embeddings of computable structures. (English) Zbl 1207.03041

Kach, Asher M.; Levin, Oscar; Solomon, Reed

Notre Dame J. Formal Logic 51, No. 1, 55-68 (2010).

The authors consider four notions of embedding property, namely, a class of computable presentations of computable structures is said to have 5.5mm

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\);

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\);

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'\);

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'\).

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.

Reviewer: Andrei S. Morozov (Novosibirsk)

MSC:

03C57	Computable structure theory, computable model theory
03D45	Theory of numerations, effectively presented structures

Keywords:

computable embedding; computable structure; computable presentation; computable ordered abelian group; computable tree; computable equivalence; computable Boolean algebra; computable algebraically closed field