# 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:

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 forther 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 counter-example (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.

-
Maybe it would be helpful to note some of the necessary properties of a counterexample. The class has AP, but should not have what I have heard called the strong AP, in which one can amalgamate the $B_i's$ so that $g_1(B_1) \cap g_2(B_2)=g_0 f_0 (A)=g_1 f_1 (A).$ If the class has this property, then it seems like a compactness argument would work. –  James Freitag Jul 27 '11 at 15:19
@Itai: If we change your question to allow function symbols in the language (and define the notion of substructure accordingly) then I can think of a counterexample, but probably this is not of interest to you. In the counterexample, M is a countable rec. sat. model of PA. If this is of interest, I can elaborate. –  Ali Enayat Jul 28 '11 at 20:02
@Ali: Yes of course this is of interest. Once you have a counter-example in a functional language, can you not add relations for the graphs of all terms and get a relational one? –  Itaï BEN YAACOV Jul 29 '11 at 10:39
@Itai: yes, we can always transform a functional language to a relational one, but I was worried about substructures, which as you know behave very differently in a relational language; but I think I can now handle that hurdle and produce a relational counterexample that I can post later today once I go over it one more time. –  Ali Enayat Jul 29 '11 at 13:20

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$, 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.

-
This is a nice example. A couple of points: (1) does not hold in general if the model does not have quantifier elimination. (3): what is $X$ in the theorem? –  Emil Jeřábek Jul 29 '11 at 18:00
@Emil, thanks for your comments; I now see that I did say that $X$ is any prescribed subset of $\omega$. I will fix that. –  Ali Enayat Jul 29 '11 at 18:59
Thanks! A side remark - I took a look in the book, and they define "amalgamation" with stricter requirement (what some call disjoint amalgamation), making the result as stated weaker than what is needed. However, insomuch as I understood the proof, it also works for the usual model-theoretic notion of amalgamation. But this requires arithmetic! Can one prove that this is impossible for, say, a stable structure? –  Itaï BEN YAACOV Jul 30 '11 at 9:20
@Itai: You are right, the book defines it as you say, but the proof of Theorem 2.3.1 does not use disjointness. Maybe stable structures behave very differently for this problem. –  Ali Enayat Jul 30 '11 at 15:05

EDIT: the argument below assumes finite language, which I took for granted for no good reason.

$\DeclareMathOperator\Th{Th}\DeclareMathOperator\Diag{Diag}$ The class of countable substructures of $M$ does have the amalgamation property if the language of $M$ is finite.

First, ultrahomogeneity implies that for any $n$ there are only finitely many $n$-types realized in $M$, each of them principal (the type of any $n$-tuple is generated by the conjunction of its diagram). This implies that there are only finitely many nonequivalent formulas in $n$-variables (namely, disjunctions of the generators), hence $\Th(M)$ is $\omega$-categorical by the Ryll-Nardzewski theorem. Alternatively, $\mathrm{Aut}(M)$ is oligomorphic as two $n$-tuples with the same diagram are in the same orbit, which is also equivalent to $\omega$-categoricity by (another variant of) the Ryll-Nardzewski theorem.

Then, take $A,B_0,B_1\subseteq M$ and embeddings $f_i\colon A\to B_i$. Let $B_i^+$ be $B_i$ expanded with constants for every element $a\in A$ realized in $B_i^+$ by $f_i(a)$. Every finite subset of $T=\Th(M)\cup\Diag(B_0^+)\cup\Diag(B_1^+)$ is consistent because the class of finitely generated (= finite) substructures of $M$ has AP (or it is easily checked directly), hence there exists a countable model $C\models T$. Since $C\equiv M$, we may assume $C=M$ by categoricity, and then we can define $g_i\colon B_i\to C$ satisfying $g_0f_0=g_1f_1$ in the obvious way.

-
On the $\omega$-categoricity statement: Are you assuming a finite language here? Itai: Are you assuming the language is finite? Countable? No assumption? –  James Freitag Jul 27 '11 at 14:59
I should add that for those who have less experience with model theory, the proof of $\omega$-categoricity in the finite relational language case goes like this: the finite language means that there are only finitely many $n$-types, like Emil mentions. Then two finite tuples with the same type are in the same $Aut(M)$ orbit. Then it is clear that the automorphism group acts oligimorphically. This implies $\omega$-categoricity (the equivalence of this condition to $\omega$-categoricity is called the Ryll-Nardzewski theorem). –  James Freitag Jul 27 '11 at 15:06
Emil: Why are you talking about finitely generated substructures? The language is relational. Also, maybe you edited your post and I am missing something, but when you say to take $A,B_i,f$ "as above", do you mean as in Itai's post. Then the $B_i's$ are finite, so I don't understand what you are proving. –  James Freitag Jul 27 '11 at 15:11
My assumptions definitely do not imply $\aleph_0$-categoricity (I never said finite language). More generally, even, 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. –  Itaï BEN YAACOV Jul 27 '11 at 16:59
Ok, that is what I thought. In the finite language case, I agree with what Emil is trying to prove (but he does not seem to have proved it as written). This comment of yours clears all of that up (via saturation). –  James Freitag Jul 27 '11 at 17:31