Metrically universal generic structures in free amalgamation classes (Q2720319)

Let \(L\) be a finite relational language. For an \(L\)-structure \(A\), the graph \(G(A)\) is defined to be the graph whose vertices are the elements of \(A\) with two elements adjacent if they are components of some tuple in \(R^A\) for some \(R\in L\). For example, if \(L\) consists of one binary relation symbol and \(A\) is a graph then \(G(A)\) is just \(A\). We denote by \(A^+\) the definitional expansion of \(A\) by the binary relations ``the distance between \(x\) and \(y\) in \(G(A)\) is \(k\)'', for all \(k<\omega\). Let \(\mathcal K\) be an \(\forall\)-axiomatizable class of \(L\)-structures closed under free amalgamations. (Examples of such \(\mathcal K\) are the class of all \(L\)-structures and many classes of combinatorial structures like the classes of all graphs, oriented graphs, \(K_n\)-free graphs.) The class \(\mathcal K^+\) of all \(A^+\), where \(A\in K\), obviously is \(\forall\exists\)-axiomatizable. It is shown that the class \(\mathcal K^+_{\text{fin}}\) of finite members of \(\mathcal K^+\) has the amalgamation property and the joint embedding property; since there are only countably many isomorphism types in \(\mathcal K^+_{\text{ fin}}\), the Fraïssé construction gives, up to isomorphism, a unique countable generic structure \(M^+\) for \(\mathcal K^+_{\text{ fin}}\). Clearly, \(M^+\) belongs to \(\mathcal K^+\). The author proves that any countable structure in \(\mathcal K^+\) is the union of a chain of finite members of \(\mathcal K^+\). It follows that \(M^+\) embeds any countable structure in~\(\mathcal K^+\), and so \(\mathcal K^+\) has a universal countable structure. The theory of \(M^+\) is proven to be the model companion of the theory of~\(\mathcal K^+\). These results generalize the results of \textit{L.~S.~Moss} [Discrete Math. 102, No. 3, 287-305 (1992; Zbl 0754.03028)] where \(\mathcal K\) was the class of graphs. An explicit axiomatization of the model companion is given, and it is shown that the model companion is not finitely axiomatizable even over a strong form of the axiom scheme of infinity.