When is the independence relation induced by the amalgamation property not monotonic?

54 Views Asked by At

Let's consider a Fraïssé class $K$ whose amalgamation property is witnessed functionally: for a diagram $A \leftarrow B \rightarrow C$ of embeddings in $K$, the structure $A\otimes_B C$ is an amalgam of the diagram. Moreover, let's assume that automorphisms on $A$ and $C$ fixing $B$ pointwise extend onto $A\otimes_B C$. (I don't know if the second part is strictly relevant in my question, but I'm following Tent and Ziegler's On the isometry group of the Urysohn space. It's a natural requirement, anyway.)

Let $M$ be the limit of $K$. We can define a ternary relation $A \downarrow_B C$ on the finite subsets of $B$ by letting $A \downarrow_B C$ hold if and only if there is an isomorphism $ABC \to AB \otimes_B BC$ respecting the relevant embeddings (I denote unions by justapositions. Also, this definition may not make sense in a non-relational language, but it can be modified so it may make sense.)

The said work by Tent and Ziegler considers several properties of the ternary relation and lists those that hold under the aforementioned most general setting. A property that is excluded from that list is Monotonicity: if $A \downarrow_B CD$, then $A \downarrow_B C$ and $A \downarrow_{BC} D$.

After thinking about this a bit, it seems to me that for many, if not all, natural class $K$ and $\otimes$, the induced ternary relation does satisfy Monotonicity. For what $(K, \otimes)$ does $\downarrow$ not satisfy monotonicity? Ideally I would like to have a natural (counteexample.

1

There are 1 best solutions below

2
On BEST ANSWER

Certainly it's easy to give ad hoc counterexamples.

For example, let $K$ be the class of finite graphs. If $|B|>1$, define $A\otimes_B C$ to be the free amalgamation (the disjoint union of $A$ and $C$ over $B$, with no edges between vertices of $A\setminus B$ and $C\setminus B$). If $|B|\leq 1$, define $A\otimes_B C$ to be the co-free amalgamation (the disjoint union of $A$ and $C$ over $B$, with an edge between each vertex in $A\setminus B$ and each vertex in $C\setminus B$). To see that this doesn't satisfy monotonicity, consider the graph $\{a,b,c,d\}$ with edges $aEc$ and $aEd$. Then $a\downarrow_b cd$, but $a\not\downarrow_{bc} d$.

Of course, the above definition of $\otimes$ doesn't seem "canonical", because of the distinction between the cases $|B|\leq 1$ and $|B|>1$. I agree that "canonical" classes $(K,\otimes)$ will tend to satisfy monotonicity. But sometimes there's no way to make "uniform" decisions about how to amalgamate.

A natural counterexample is actually given by one of the key classes in the paper you're reading: $K = $ finite metric spaces with all distances in $\mathbb{Q}$. When $B$ is non-empty, we can define the "free amalgamation" $A\otimes_B C$ by setting, for each pair of points $a\in A\setminus B$ and $c\in C\setminus B$, $$d(a,c) = \min_{b\in B} \,(d(a,b)+d(b,c)).$$ This puts $a$ and $c$ as far apart as possible without violating the triangle inequality. But the formula doesn't work when $B$ is empty, since we cannot put $a$ and $c$ at distance $\infty$. So if we want to extend the definition down to amalgamation over the empty metric space, we need to make some choice of how to define $A\otimes_{\varnothing} C$, e.g. define $D= \max(\max_{a,a'\in A} d(a,a'),\max_{c,c'\in C}d(c,c'))$ and set $d(a,c) = D$ for all $a\in A$ and $c\in C$. But this definition breaks monotonicity.

In fact, there is no way to extend $\otimes$ down to amalgamation over $\varnothing$ while preserving monotonicity. Suppose for contradiction that we have a "good" definition of $\otimes$. Let $A = \{a\}$, $B = \{b\}$, and $C = \{b,c\}$ with $d(b,c) = 1$. Consider $A\otimes_\varnothing C$, i.e. assume $A\downarrow_\varnothing BC$. Since $C$ has an automorphism swapping $b$ and $c$, we must have $d(a,b) = d(a,c)$. But if $A\downarrow_B C$, then we would have $d(a,c) = d(a,b)+d(b,c) = d(a,b)+1$.