Skip to main content
added 754 characters in body
Source Link

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 $C$$D$ such that

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

We think of each $R_i^C$$R_i^D$ as consisting of the edges of $C$$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.)

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 $C$ such that

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

We think of each $R_i^C$ as consisting of the edges of $C$ 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.

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.)

Source Link

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 $C$ such that

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

We think of each $R_i^C$ as consisting of the edges of $C$ 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.