16
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jul 27, 2011 at 15:19
  • $\begingroup$ @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. $\endgroup$
    – Ali Enayat
    Jul 28, 2011 at 20:02
  • $\begingroup$ @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? $\endgroup$ Jul 29, 2011 at 10:39
  • $\begingroup$ @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. $\endgroup$
    – Ali Enayat
    Jul 29, 2011 at 13:20

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Jul 29, 2011 at 18:00
  • $\begingroup$ @Emil, thanks for your comments; I now see that I did say that $X$ is any prescribed subset of $\omega$. I will fix that. $\endgroup$
    – Ali Enayat
    Jul 29, 2011 at 18:59
  • $\begingroup$ 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? $\endgroup$ Jul 30, 2011 at 9:20
  • $\begingroup$ @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. $\endgroup$
    – Ali Enayat
    Jul 30, 2011 at 15:05
2
$\begingroup$

An example is the "complete rainbow graph without monochromatic triangles". Let $L = \{R_i : i \in \omega\}$ be a language consisting of $\omega$-many binary relation symbols $R_i$, and take the class $\mathcal{K}$ of finite $L$-structures $D$ such that

  • each $R_i^D$ is a graph relation (that is, irreflexive and symmetric);
  • the $R_i^D$s are disjoint;
  • every ordered pair of distinct elements of $D$ lies in some $R_i^D$ (completeness of the graph);
  • no $R_i^D$ contains a triangle.

We think of each $R_i^D$ as consisting of the edges of $D$ of colour $i$.

Then $\mathcal{K}$ is a strong amalgamation class (join the ears of the finite amalgam with edges of a colour that's not used in either ear). Let $M$ denote its Fraïssé limit, and let $\mathcal{U}$ denote the class of $L$-structures which embed into $M$ (so including countably infinite ones).

We will see that $\mathcal{U}$ does not have amalgamation.

Let $A \in \mathcal{U}$ be countably infinite. Then $A$ has two adjacent edges $a a_0, a a_1$ of different colours, as there are no monochromatic triangles in $A$ and $A$ is a complete graph. Enumerate $A$ as $a, a_0, a_1, a_2, \cdots$. Let $i_1$ be the colour of $a a_0$ and let $i_0$ be the colour of $a a_1$ (this is not a typo!). Enumerate the set $\omega$ of colours as $i_0, i_1, i_2, \cdots$.

Define structures $B, C$ as follows. Let $B$ consist of $A$ together with a new point $b$ such that $ba$ has colour $i_0$ and $ba_j$ has colour $i_j$ for $j \geq 0$. Let $C$ consist of $A$ together with a new point $c$ such that $ca$ has colour $i_1$ and $ca_j$ has colour $i_j$ for $j \geq 0$. Then $B$ and $C$ are complete and contain no monochromatic triangles, so lie in $\mathcal{U}$.

Then $B, C$ cannot amalgamate over $A$, as $b$ and $c$ cannot be identified in the amalgam due to their different coloured edges to $a$, and any coloured edge between $b$ and $c$ would form a monochromatic triangle.

(Note that $M$ is not $\omega$-categorical by the Ryll-Nardzewski theorem, as we have infinitely many isomorphism classes of substructures of size $2$. Also note that $M$ is not $\omega$-saturated: take the type which consists of formulae "$xy$ is not of colour $i$" for each $i \in \omega$.

In general, if a relational Fraïssé limit $M$ is $\omega$-categorical or has free amalgamation, then $\mathcal{U}$ has amalgamation. This follows for the $\omega$-categorical case by a König's lemma argument doing the amalgam finite piece by finite piece - for finite amalgams you only have finitely many possibilities by Ryll-Nardzewski - and for the free amalgamation case you take the canonical amalgam at each finite step.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ On the $\omega$-categoricity statement: Are you assuming a finite language here? Itai: Are you assuming the language is finite? Countable? No assumption? $\endgroup$ Jul 27, 2011 at 14:59
  • $\begingroup$ 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). $\endgroup$ Jul 27, 2011 at 15:06
  • $\begingroup$ 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. $\endgroup$ Jul 27, 2011 at 15:11
  • $\begingroup$ 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. $\endgroup$ Jul 27, 2011 at 16:59
  • $\begingroup$ 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). $\endgroup$ Jul 27, 2011 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.