2 added 365 characters in body; added 8 characters in body; deleted 1 characters in body

EDIT NOTE: Thanks to Emil Jeřábek's comment, (1) has been modified; $X$ in the theorem has been quantified, and the bold sentence in (4) has been added.

I will first present a counterexample using a structure that has (infinitely many) functions; then I will explain how this functional counterexample can be turned into a relational one.

We begin with some preliminaries:

(1) Recursively saturated models that have elimination of quantifiers are ultra-homogeneous. This is a basic result in model theory.

(2) If $M_0$ and $M_1$ are models of $PA$ (Peano arithmetic), and $M_0$ is a submodel of $M_1$, then $SSy(M_{0})\subseteq SSy(M)$. This follows from the definition of $SSy(M)$ (the standard system of $M$). Recall that for a model $M$ of $PA$, $SSy(M)$ is the collection of subsets of $\omega$ that are "coded" by some element of $M$, where "coded" can be defined in various ways, e.g., as: $X \subseteq \omega$ is coded by $c \in M$ if for all $n \in \omega$, $M \models$ “the $n$-th prime divides $c$” iff $n \in X$.

(3) The heart of this counterexample is the following theorem [it is Theorem 2.3.1 (p.40) of the Kossak-Schmerl text on models of Peano arithmetic].

Theorem. Let $M_0$ be a countable recursively saturated model of $PA$. PA$, and suppose$X$is some fixed subset of$\omega$. Then$M_0$has elementary end extensions$M_1$and$M_2$, such that$M_0 \cong M_{1} \cong M_2$, and whenever$M_{3}\models PA$is an amalgamation of$M_1$and$M_2$, then$X\in SSy(M_3)$. (4) Given$M \models PA$, let$M^{+}$be the EXPANSION of$M$by the first-order definable functions of$M$. We observe that if$N^{+}$is a substructure of$M^{+}$, then the reduct$N$is a model of$PA$since the universe of$N$is closed under the functions available in$M^{+}$, and therefore$N$is an elementary submodel of$M$because$PA$has definable Skolem functions. Note, furthermore, that$M^{+}$eliminates quantifiers, and is also recursively saturated, hence ultrahomogeous. (1)-(4) show that for a countable recursively saturated model$M$of$PA$, the collection of substructures of$M^{+}$do not satisfy amalgamation. More specifically, thanks to the aforementioned theorem in (3), by first choosing some subset$X$of$\omega$that is missing from the standard system of$M$, we can be assured of the existence of (end) embeddings$f_{i}:M^{+}\rightarrow M^{+}$for$i=0,1$with the property that if there is a structure$N^{+}$, and embeddings$g_{i}:M\rightarrow N^{+}$for$i=0,1$, with$g_{0}f_{0}=g_{1}f_{1}$, then by (2) and (4)$N^{+}$is not a substructure of$M^{+}$. Now we explain how to obtain a relational counterexample. Given a model$A$in a language with functions, let$\cal{A}$be the relational structure obtained by replacing each$n$-ary function$f$in$A$by the usual$(n+1)$-ary relation known as the graph of$f$. Let$M$be a countable recursively saturated model of$PA$. To see that the family of substructures of$\cal{M^{+}}$do not satisfy amalgamation, we simply observe that if$(X,\cdot \cdot \cdot)$is a substructure of$\cal{M^{+}}$, and$\overline {X}$is the closure of$X$under the functions available in$M^{+}$, then the inclusion map$i_{X}:X\rightarrow \overline{X}$is an embedding of the substructure of$\cal{M^{+}}$determined by$X$into the substructure of$\cal{M^{+}}$determined by$\overline{X}$. Therefore, if$AP$holds in this relational context for some amalgamating substructure with universe$X$, by composing each$g_i$with$i_{X}$then$AP$would also have to hold in the functional context. 1 I will first present a counterexample using a structure that has (infinitely many) functions; then I will explain how this functional counterexample can be turned into a relational one. We begin with some preliminaries: (1) Recursively saturated models are ultra-homogeneous. This is a basic result in model theory. (2) If$M_0$and$M_1$are models of$PA$(Peano arithmetic), and$M_0$is a submodel of$M_1$, then$SSy(M_{0})\subseteq SSy(M)$. This follows from the definition of$SSy(M)$(the standard system of$M$). Recall that for a model$M$of$PA$,$SSy(M)$is the collection of subsets of$\omega$that are "coded" by some element of$M$, where "coded" can be defined in various ways, e.g., as:$X \subseteq \omega$is coded by$c \in M$if for all$n \in \omega$,$M \models$“the$n$-th prime divides$c$” iff$n \in X$. (3) The heart of this counterexample is the following theorem [it is Theorem 2.3.1 (p.40) of the Kossak-Schmerl text on models of Peano arithmetic]. Theorem. Let$M_0$be a countable recursively saturated model of$PA$. Then$M_0$has elementary end extensions$M_1$and$M_2$, such that$M_0 \cong M_{1} \cong M_2$, and whenever$M_{3}\models PA$is an amalgamation of$M_1$and$M_2$, then$X\in SSy(M_3)$. (4) Given$M \models PA$, let$M^{+}$be the EXPANSION of$M$by the first-order definable functions of$M$. We observe that if$N^{+}$is a substructure of$M^{+}$, then the reduct$N$is a model of$PA$since the universe of$N$is closed under the functions available in$M^{+}$, and therefore$N$is an elementary submodel of$M$because$PA$has definable Skolem functions. (1)-(4) show that for a countable recursively saturated model$M$of$PA$, the collection of substructures of$M^{+}$do not satisfy amalgamation. More specifically, thanks to the aforementioned theorem in (3), by first choosing some subset$X$of$\omega$that is missing from the standard system of$M$, we can be assured of the existence of (end) embeddings$f_{i}:M^{+}\rightarrow M^{+}$for$i=0,1$with the property that if there is a structure$N^{+}$, and embeddings$g_{i}:M\rightarrow N^{+}$for$i=0,1$, with$g_{0}f_{0}=g_{1}f_{1}$, then by (2) and (4)$N^{+}$is not a substructure of$M^{+}$. Now we explain how to obtain a relational counterexample. Given a model$A$in a language with functions, let$\cal{A}$be the relational structure obtained by replacing each$n$-ary function$f$in$A$by the usual$(n+1)$-ary relation known as the graph of$f$. Let$M$be a countable recursively saturated model of$PA$. To see that the family of substructures of$\cal{M^{+}}$do not satisfy amalgamation, we simply observe that if$(X,\cdot \cdot \cdot)$is a substructure of$\cal{M^{+}}$, and$\overline {X}$is the closure of$X$under the functions available in$M^{+}$, then the inclusion map$i_{X}:X\rightarrow \overline{X}$is an embedding of the substructure of$\cal{M^{+}}$determined by$X$into the substructure of$\cal{M^{+}}$determined by$\overline{X}$. Therefore, if$AP$holds in this relational context for some amalgamating substructure with universe$X$, by composing each$g_i$with$i_{X}$then$AP\$ would also have to hold in the functional context.