
> 
> Is there a relational countable ultra-homogeneous structure whose countable substructures do not have the amalgamation property?
> 
> 
> 


The question can be stated in a fashion not requiring much background:


Let $M$ be a countable ultra-homogeneous relational structure - namely, a countable set equipped with a bunch of relations on its finite cartesian powers, such that any isomorphism between two finite substructures of $M$ extends to an automorphism of $M$. It is classical (and easy to see) that the age of $M$, namely the class $K$ of finite substructures of $M$ (and isomorphic copies thereof) is a Fraïssé class, and in particular has the Amalgamation Property:


**Amalgamation Property (AP)** - whenever $A,B\_i \in K$ for $i=0,1$ and $f\_i\colon A \to B\_i$ are embeddings, there is $C \in K$ and further embeddings $g\_i\colon B\_i \to C$ such that $g\_0f\_0 = g\_1f\_1$ (i.e., $B\_0$ and $B\_1$ can be amalgamated in $K$ over $A$).


In all examples I am familiar with, the class of all countable substructures of $M$ also has the same property, but I see no reason why this should be true in general.
Any counterexample (or proof that this does hold in general) will be welcome.


[Of course, there are usually going to be in $M$ countable substructures $A\_0,A\_1$ with an isomorphism $f\colon A\_0 \to A\_1$ which does not arise from an automorphism - but this does not exclude the possibility of proper embeddings $g\_i\colon M \to M$ such that $g\_1^{-1} g\_0$ extends $f$.]


ADDENDUM: Notice that if $M$ is saturated then its countable substructures have AP, so a counter-example will have to be non saturated, and in particular non $\aleph\_0$-categorical, with an infinite language.


ADDENDUM #2: see also [A restatement, in terms of the semi-group product of the left-invariant completion of a Polish group, of http://mathoverflow.net/questions/71389](https://mathoverflow.net/questions/71485)



Is there a relational countable ultra-homogeneous structure whose countable substructures do not have the amalgamation property?
**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](http://www.oxfordscholarship.com/oso/public/content/maths/9780198568278/toc.html)]. 


**Theorem**. Let $M\_0$ be a countable recursively saturated model of $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.


