Merges of Smooth Classes and Their Properties

Morgan Bryant
University of Maryland Partially supported by NSF grant DMS-2154101

Abstract

Given two Fraïssé-like classes with generic limits, we ask whether we can merge the two classes into one class with a generic limit. We study the properties of these merges and their generics, as well as their connections to structural Ramsey theory and the Hrushovski property (EPPA).

1 Introduction

Given a countable, relational language $\mathcal{L}$ , a pair $(K,\leq)$ is a smooth class if $K$ is a class of finite $\mathcal{L}$ -structures whose elements are related by $\leq$ , which is determined by universal formulas (see §2). Fraïssé classes are smooth classes whose relation is simply $\subseteq$ , and these Fraïssé classes are the classes used in Fraïssé’s original constructions. The main motivation for this work, and many other works on smooth classes, comes from classes of Shelah-Spencer sparse graphs (see Example 2.2). These particular classes have served as counterexamples in several model theoretic settings, and have proved to have some interesting properties. The results of this paper were inspired by observations made when studying these classes of graphs.

Fraïssé limits/generics are $\omega$ -categorical, ultrahomogeneous structures with respect to a Fraïssé class, and they are well-understood, classical objects. The generics (also called limits) of proper smooth classes, on the other hand, are far more oblique and less free objects. The goal of this paper is to better understand general smooth classes and their generics in both the strictly model-theoretic sense and in applications of model theory.

In §2, we will study certain expansions of smooth classes and their generics by way of merging smooth classes. This is done by taking two smooth classes $K_{1}$ and $K_{2}$ in the languages $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ and forming a new smooth class, $K_{1}\circledast K_{2}$ , called the merge of $K_{1}$ and $K_{2}$ , in the language $\mathcal{L}_{1}\cup\mathcal{L}_{2}$ such that for $i=1,2$ and all $A\in K_{1}\circledast K_{2}$ , $A|_{\mathcal{L}_{i}}\in K_{i}$ . In some cases, $K_{1}\circledast K_{2}$ has a generic $M^{*}$ .

When $K_{1}$ and $K_{2}$ are closed under substructure, it is known by [EHN19] that for $i=1,2$ , $M^{*}|_{\mathcal{L}_{i}}\cong M_{i}$ , where $M_{i}$ is the generic of $K_{i}$ . We prove that this can be strengthened by assuming that each of $K_{1}$ and $K_{2}$ additionally have parallel strongness and smooth intersections (defined in §2.1.1). In this case, we show that for any $C^{*}\subseteq M^{*}$ an infinite set definable in $M^{*}$ by an existential $\mathcal{L}_{2}$ -formula, $C^{*}|_{\mathcal{L}_{1}}\cong M_{1}$ . We consider this to be the main theorem from the study of merging smooth classes, and it has many consequences, as described in §2.3.1. In particular, this theorem provides information about the generics of the original classes $K_{1}$ and $K_{2}$ .

In §2.3 we study which model theoretic properties are transferred from the generics $M_{1}$ and $M_{2}$ to $M^{*}$ . By strengthening a theorem in [KL92], we show that if $M_{1}$ and $M_{2}$ are both atomic, then $M^{*}$ is atomic. This does not hold for saturation; a merge of classes of Shelah-Spencer graphs gives a counterexample to this transfer.

In §3, we turn to structural Ramsey theory and study smooth classes and their merges in this context. Merges of Fraïssé classes have been the quintessential examples of classes with the Ramsey property (defined in §3). In [KPT04], for example, Fraïssé classes are often merged with the Fraïssé class of all finite linear orders as a way to "rigidify" the classes. The KPT correspondence, which is the main result of [KPT04], gives an equivalence between Fraïssé classes of rigid structures with the Ramsey property and their generics having an extremely amenable automorphism group. This correspondence has drummed up much of the recent interest in classes with the Ramsey property. The correspondence holds for smooth classes of rigid structures, as shown in [GKP16].

We are interested in which smooth classes and their merges have the Ramsey property. This is motivated by [Bod12], in which it is shown that whenever $K_{1}$ and $K_{2}$ are Fraïssé classes of rigid structures with the Ramsey property, then $K_{1}\circledast K_{2}$ has the Ramsey property. It remains unclear as to when this result extends to smooth classes. An intermediate step in the direction of this goal is studying which classes and their merges have the Hrushovski property (often written as EPPA) (defined in §3.1).

While it is known by [HO03] that any Fraïssé class with the free amalgamation property has EPPA, ([EHN19], [GKP16]) have shown that this does not extend to smooth classes. In §3.2, we give an explicit family of smooth classes with the free amalgamation property and prove these classes and their merges have EPPA. This expands upon the ideas given for a specific smooth class in ([EHN19],[EHN21]) and uses the strongest existing EPPA results from [HKN22]. We also put a smooth relation on the class of infinitely many equivalence relations given by [Iva15] and generalize the argument in [Iva15] to obtain a non-trivial smooth class without the free amalgamation property which has EPPA.

2 Merging Smooth Classes

2.1 Background

In this section, we will give the background needed to understand many of the results in this paper. Smooth classes, which also go under the name of "strong classes", are a generalization of Fraïssé’s original constructions. The definition of these classes can vary from author to author. We choose to use one of the most general versions of the definition of smooth classes for the most general results.

2.1.1 Smooth Classes

For the entirety of this paper, we will consider only countable, relational languages. This is done out of convenience; many of the constructions in this section and in section 2.2 still apply when the languages contain functions. We begin with recalling the following definition from [KL92]:

Definition 2.1.

Let $\mathcal{L}$ be a relational language. Let $K$ be a class of finite $\mathcal{L}$ -structures which is closed under isomorphism. We say the pair $(K,\leq)$ , where $\leq$ is a binary relation on the elements of $K$ , is a smooth class if

1.

$\leq$ is transitive and for all $A$ , $B\in K$ , $A\leq B\Rightarrow A\subseteq B$
2.

For all $B\in K$ and every enumeration $\overline{b}:=(b_{1},\dots,b_{n})$ of $B$ , there is a (possibly infinite) set $\Phi_{\overline{b}}(\overline{x})$ of universal $\mathcal{L}$ -formulas with $|\overline{x}|=n$ such that $\Delta_{\overline{b}}\subseteq\Phi_{\overline{b}}(\overline{x})$ , where $\Delta_{\overline{b}}$ is the atomic diagram of $B$ according to the enumeration $\overline{b}$ , such that for any $C\in K$ with $B\subseteq C$ ,

$B\leq C\Leftrightarrow C\models\Phi_{\overline{b}}(\overline{b})$
3.

For $A,B\in K$ , if $\overline{a}=(a_{1},\dots,a_{n})$ is an enumeration of $A$ and there exists an isomorphism $f:A\rightarrow B$ , then for the enumeration $\overline{b}=(f(a_{1}),\dots,f(a_{n}))$ of $B$ , we require that $\Phi_{\overline{a}}=\Phi_{\overline{b}}$ .
4.

$\emptyset\in K$ and for every $A\in K$ , $\emptyset\leq A$

Clearly, any class containing $\emptyset$ and equipped with $\subseteq$ as its relation is a smooth class. We now give an example of a smooth class whose relation is not $\subseteq$ . This particular class will appear in several parts of this paper:

Example 2.2.

Let $\alpha\in(0,1)$ , and $\mathcal{L}_{\alpha}$ a finite, relational language. For any $\mathcal{L}_{\alpha}$ -structure $A$ on which every relation $R\in\mathcal{L}_{\alpha}$ is symmetric and irreflexive, define the dimension function $\delta_{\alpha}$ on $A$ as

\delta_{\alpha}(A):=|A|-\alpha\cdot\sum_{R\in\mathcal{L}}N_{R}(A)

where $N_{R}(A)$ is the number of distinct subsets of $A$ on which $R$ holds. Define the class $(K_{\alpha},\leq_{\alpha})$ as

K_{\alpha}=\{A:\delta_{\alpha}(A^{\prime})\geq 0\text{ for all }A^{\prime}\subseteq A\}

and set

A\leq_{\alpha}B\Leftrightarrow\delta_{\alpha}(B^{\prime})-\delta_{\alpha}(A)\geq 0\text{ for all }B^{\prime}\text{ such that }A\subseteq B^{\prime}\subseteq B

$(K_{\alpha},\leq_{\alpha})$ is a well known smooth class and is called the class of Shelah-Spencer $\alpha$ -graphs in $\mathcal{L}_{\alpha}$ .

Smooth classes are meant to be a generalization of classes used in Fraïssé’s constructions. In particular, these classes may also have limits as in Fraïssé constructions. To see this, we will need to define the usual properties of a class with respect to the relation $\leq$ as opposed to $\subseteq$ :

Definition 2.3.

Let $(K,\leq)$ be a smooth class.

1.

$(K,\leq)$ has the amalgamation property (AP) if, for any $A,B,C\in K$ such that there exist embeddings $h_{1}:A\rightarrow C$ and $h_{2}:A\rightarrow B$ where $h_{1}(A)\leq C$ and $h_{2}(A)\leq C$ , then there exists some $D\in K$ such that there exists embeddings $f:B\rightarrow D$ and $g:C\rightarrow D$ with $f(B)\leq D$ , $g(C)\leq D$ , and $g\circ h_{1}=f\circ h_{2}$ .

We say $(K,\leq)$ has disjoint amalgamation (dAP) if we can find a $D\in K$ and embeddings $f:B\rightarrow D$ , $g:C\rightarrow D$ with $f(B)\leq D$ , $g(C)\leq D$ , $f\circ h_{2}=g\circ h_{1}$ , and $f(B)\cap g(C)=f\circ h_{2}(A)$ .
2.

For any $A,B,C\in K$ with $A\subseteq B,C$ , the structure $C*_{A}B$ is defined as the structure with universe $B\cup C$ where the only relations between $B$ and $C$ are contained in $A$ . We say $(K,\leq)$ has free amalgamation (fAP) if $A,B,C\in K$ and $A\leq B,C$ , then $B,C\leq C*_{A}B$ and $C*_{A}B\in K$ .
3.

$(K,\leq)$ has parallel strongness (PS) if for any $A,B,C\in K$ such that $A\subseteq C$ and $A\leq B$ , there exists some $D\in K$ and embeddings $f:C\rightarrow D$ and $g:B\rightarrow D$ such that $f(C)\leq D$ , $g(B)\subseteq D$ , and $g(A)=f(A)$ . $(K,\leq)$ has disjoint parallel strongness (dPS) if this can be done so that $f(C)\cap g(B)=g(A)=f(A)$ .
Note: This property is sometimes referred to as full amalgamation in the literature. (e.g., in [BS96])
4.

$(K,\leq)$ has smooth intersections if for every $A,B,C\in K$ , $A\leq B\Rightarrow A\cap C\leq B\cap C$
Note: Some authors assume this property as part of the definition of a smooth class. (e.g., in [BS96], [GKP16])

Only AP is required for a generalization of Fraïssé’s theorem; dPS, fAP, and dAP will have greater roles in the next sections. It is worth noting that the classes in Example 2.2 have dPS, fAP, and smooth intersections, as shown in [BS96], and we will use this fact throughout this paper.

We call a smooth class $(K,\leq)$ a Fraïssé class if for $A,B\in K$ , $A\leq B\Leftrightarrow A\subseteq B$ , $K$ has AP, and is closed under substructure. These classes have traditional Fraïssé limits, and they vacuously have smooth intersections and PS.

We must now define limits, or generics, for any smooth class, and then give conditions for the existence of a generic of a smooth class.

Suppose $(K,\leq)$ is a smooth class. Given an $\mathcal{L}$ -structure $M$ , for $A\in K$ with $A\subseteq M$ , we write $A\leq M$ if and only if for any enumeration $\overline{a}$ of $A$ , $M\models\Phi_{\overline{a}}(\overline{a})$ .

Definition 2.4.

We say an $\mathcal{L}$ -structure $M$ is a generic for $(K,\leq)$ if

1.

There exist $\{A_{i}\}_{i\in\omega}$ with $A_{i}\in K$ such that $M=\bigcup_{i\in\omega}A_{i}$ and $A_{i}\leq A_{j}$ when $i\leq j$ .
2.

If $A\leq M$ and $A\leq B$ , for $A,B\in K$ , then there is an embedding $f:B\rightarrow M$ such that $f|_{A}=Id_{A}$ and $f(B)\leq M$ .

This is essentially a word-for-word generalization of a Fraïssé limit. The following holds essentially by Fraïssé’s original proofs:

Proposition 2.5.

A smooth class $(K,\leq)$ has a generic $M$ if and only if $(K,\leq)$ has AP and $K$ contains only countably many isomorphism types. Moreover, any two generics of a smooth class $(K,\leq)$ are isomorphic.

As noted before, the study of the generics of smooth classes will be a central throughout this paper. In the next section, we will discuss the idea of combining smooth classes and studying the resulting expansions of their generics.

2.2 Merges

Our main motivation in the study of merges was to study certain, arguably natural, expansions of smooth classes, particularly the classes of Shelah-Spencer graphs. For any $\alpha\in(0,1)$ , the generic $M_{\alpha}$ of the Shelah-Spencer class $(K_{\alpha},\leq_{\alpha})$ (see 2.2) is well understood and its theory has a concrete $\forall_{2}$ -axiomatization given by ([Las07],[Gun18]). In studying expansions of these graphs, it became increasingly clear that certain expansions lead to the discovery of interesting properties of the generic $M_{\alpha}$ . This launched an investigation that led to the study of merges of smooth classes, which will be defined in this section.

2.2.1 The Set-Up

We now turn to the problem of combining smooth classes. The idea of combining Fraïssé classes is not new; in fact, it is a rather natural method of constructing new Fraïssé classes. This section can be thought of as a generalization of combining Fraïssé classes, but there are a number of technicalities brought on by the smooth relations that we must deal with.

Definition 2.6.

Fix languages $\mathcal{L}_{i}$ , $i\in\omega$ where $\mathcal{L}_{i}\cap\mathcal{L}_{j}=\emptyset\Leftrightarrow i\neq j$ . Fix a family of smooth classes $\{(K_{i},\leq_{i}):i\in\omega\}$ such that each $(K_{i},\leq_{i})$ is a class of $\mathcal{L}_{i}$ -structures. We define a new smooth class $(K^{*},\leq_{*})$ in the language $\mathcal{L}^{*}:=\bigcup_{i\in I}\mathcal{L}_{i}$ as follows:

K^{*}=\{A:A|_{\mathcal{L}_{i}}\in K_{i}\;\forall i\in I\}

and for $A,B\in K^{*}$ ,

A\leq_{*}B\Leftrightarrow A|_{\mathcal{L}_{i}}\leq_{i}B|_{\mathcal{L}_{i}}\;\;\forall i\in I

We call the class $(K^{*},\leq_{*})$ defined above the merge of $\{(K_{i},\leq_{i}):i\in I\}$ .

Notation: For smooth classes $(K_{1},\leq_{1})$ and $(K_{2},\leq_{2})$ , we will write $K_{1}\circledast K_{2}$ to denote the merge of the classes under the relation $\leq_{*}$ . For the set of classes $\{(K_{i},\leq_{i}):i\in I\}$ , we will write $\circledast_{i\in I}K_{i}$ to denote the merge of these classes under the relation $\leq_{*}$ .

It is clear from the definition of smooth classes that the merge of smooth classes will be itself a smooth class. Let $(K^{*},\leq_{*})$ be the merge of the family $\{(K_{i},\leq_{i}):i\in I\}$ . Let $A\in K^{*}$ and let $\overline{a}$ be an enumeration of $A$ . For $i\in I$ , let $\Phi^{i}_{\overline{a}}$ denote the set of universal $\mathcal{L}_{i}$ -formula such that for all $B\in K_{i}$ , $B\models\Phi^{i}_{\overline{a}}(\overline{a})\Leftrightarrow A|_{\mathcal{L}_{i}}\leq_{*}B$ . Let $\Phi^{*}_{\overline{a}}$ denote the set of universal $\mathcal{L}^{*}$ -formulas such that for all $B\in K^{*}$ , $B\models\Phi^{*}_{\overline{a}}(\overline{a})\Leftrightarrow A\leq_{*}B$ . Notice that $\Phi^{*}_{\overline{a}}$ can be chosen of the form $\bigcup_{i\in I}\Phi^{i}_{\overline{a}}$ .

We now give sufficient conditions for the existence of a generic of the merge. The conditions below can be much more flexible based on which classes one is attempting to merge. Essentially, we need to prove that the merge has AP. To get this, we must have that each class in the merge "agrees" on a cardinality of an amalgamation. We also need that the merged class does indeed have infinitely many elements.

This is essentially what the below definition ensures:

Notation: For a smooth class $(K,\leq)$ , define

C_{(K,\leq)}:=\{n:A\in K,\;\;|A|=n\}

Definition 2.7.

For languages $\mathcal{L}_{i}$ , $i\in\omega$ where $\mathcal{L}_{i}\cap\mathcal{L}_{j}=\emptyset\Leftrightarrow i\neq j$ , smooth classes $(K_{i},\leq_{i})$ which are classes of $\mathcal{L}_{i}$ -structures, and $I\subseteq\omega$ , we say the set of smooth classes $\{(K_{i},\leq_{i}):i\in I\}$ has uniform dAP if:

1.

$I\subseteq\omega$ and for all $i,j\in I$ ,

$C_{(K_{i},\leq_{i})}=C_{(K_{j},\leq_{j})}$
2.

For any $n,m,k\in C_{(K_{i},\leq_{i})}$ , there exists some $j\in C_{(K_{i},\leq_{i})}$ such that for any $i\in I$ , and any $A_{i}$ , $B_{i}$ , $C_{i}\in K_{i}$ where $|A_{i}|=n$ , $|B_{i}|=m$ , $|C_{i}|=k$ and $A_{i}\leq_{i}B_{i},C_{i}$ , then there exists a disjoint amalgam $D_{i}\in K_{i}$ of $B_{i}$ and $C_{i}$ over $A_{i}$ with $A_{i},B_{i},C_{i}\leq_{i}D_{i}$ and $|D_{i}|=j$ .

Remark 2.8.

When all classes in $\mathcal{S}:=\{(K_{i},\leq_{i}):i\in I\}$ with $I\subseteq\omega$ have closure under substructure and dAP, $\mathcal{S}$ has uniform dAP trivially. Because of this and Theorem 2.9 we will frequently work within this framework in the context of merging classes.

Theorem 2.9.

If a set of smooth classes $\mathcal{S}:=\{(K_{i},\leq_{i}):i\in I\}$ has uniform dAP, then the merge $(K^{*},\leq_{*})$ has a generic in $\mathcal{L}^{*}$ .

Proof:

We must prove, by Theorem 2.5, that $(K^{*},\leq_{*})$ has AP. We will in fact prove that it has dAP. For each $i\in I$ and $A\in K^{*}$ denote $A|_{\mathcal{L}_{i}}$ by $A_{i}$ . Let $A,B,C\in K^{*}$ such that there exist embeddings $\alpha:A\rightarrow C$ and $\beta:A\rightarrow B$ for which $\alpha(A)\leq C$ and $\beta(A)\leq B$ . For each $i\in I$ , let $\alpha_{i}$ and $\beta_{i}$ denote the $\mathcal{L}_{i}$ -embeddings $\alpha$ and $\beta$ restricted to the language $\mathcal{L}_{i}$ . Because $\mathcal{S}$ has uniform dAP, for each $i\in I$ , we may choose $D_{i}\in K_{i}$ such that for all $i,j\in I$ , $|D_{i}|=|D_{j}|$ , and for every $i\in I$ , there exist $\mathcal{L}_{i}$ -embeddings $f_{i}:C_{i}\rightarrow_{i}D_{i}$ and $g_{i}:B_{i}\rightarrow D_{i}$ with $f(C_{i})\leq_{i}D_{i}$ , $g(B_{i})\leq_{i}D_{i}$ , $f_{i}\circ\alpha_{i}=g_{i}\circ\beta_{i}$ , and $f(C_{i})\cap f(B_{i})=f_{i}\circ\alpha_{i}(A_{i})$ . Enumerate $A$ as $\{a_{1},\dots,a_{t}\}$ , $B-\beta(A)$ as $\{b_{1},\dots,b_{n}\}$ , and $C-\alpha(A)$ as $\{c_{1},\dots,c_{m}\}$ . Enumerate each $D_{i}$ as

D_{i}=\{c^{i}_{1},\dots,c^{i}_{m}\}\cup\{b^{i}_{1},\dots,b^{i}_{n}\}\cup\{a^{i}_{1},\dots,a_{t}^{i}\}\cup\{e^{i}_{1},\dots,e^{i}_{j}\}

where $c^{i}_{k}=f_{i}(c_{k})$ , $b^{i}_{k}=g_{i}(b_{k})$ , and $a_{k}^{i}=f_{i}\circ\alpha_{i}(a_{k})$ . Take a set $N$ with $|N|=|D_{i}|$ and enumerate

N=\{w_{1},\dots,w_{m}\}\cup\{d_{1},\dots,d_{n}\}\cup\{s_{1},\dots,s_{t}\}\cup\{e_{1},\dots,e_{j}\}

In each language $\mathcal{L}_{i}$ , we will define $N|_{\mathcal{L}_{i}}$ so that the function $h_{i}:N\rightarrow D_{i}$ for $i\in I$ defined $h_{i}(w_{k})=c^{i}_{k}$ , $h_{i}(d_{k})=b^{i}_{k}$ , $h_{i}(s_{k})=a_{k}^{i}$ and $h_{i}(e_{k})=e^{i}_{k}$ is an $\mathcal{L}_{i}$ -isomorphism. It follows that $N\in K^{*}$ by definition.

Moreover, $G:B\rightarrow N$ defined as $G(b_{k})=d_{k}$ and $G(\beta(a_{k}))=s_{k}$ and $F:C\rightarrow N$ defined as $F(c_{k})=w_{k}$ and $F(\alpha(a_{k}))=s_{k}$ are both $\mathcal{L}^{*}$ -embeddings by the construction of $N$ . It is also clear that $G(B)\leq_{*}N$ and $F(C)\leq_{*}N$ . Thus, $K^{*}$ has dAP.

Similar arguments to the proof above can show that if every class in $\mathcal{S}$ has dPS and/or fAP, then so does the merge $(K^{*},\leq_{*})$ .

Remark 2.10.

The assumptions in Theorem 2.5 can be loosened, but the assumption that each class has dAP is nearly necessary. Without each class having dAP, the possible merged classes with generics are often nearly trivial and highly constrainted, depending on how "strict" the AP in each class is. For example, let the class $(K,\leq)$ be such that $K$ is the class of all finite linear orders and $A\leq B$ if and only if $A$ is an initial segment of $B$ . This class has AP, but certainly not dAP. The only classes $(K_{2},\leq_{2})$ which can be merged with $(K,\leq)$ and produce a generic of the merge are the classes $(K_{2},\leq_{2})$ for which $\leq_{2}$ is $\subseteq$ and every relation in the language holds (or, equivalently, does not hold) on every tuple in every structure of $K_{2}$ .

2.3 Properties of Merges

2.3.1 Preserving Generics in the Merge

Ideally, when we merge classes and obtain a generic of the merged classes, we would like for the generic of the merged classes to be an expansion of each of the original generics. To have this, we must have that the merged class does not "miss" any information from the original classes. A way of ensuring this is to assume the classes are closed under substructure. In many natural applications, this is a reasonable assumption.

We now prove that this holds under some additional assumptions:

Proposition 2.11.

Suppose $(K_{1},\leq_{1})$ and $(K_{2},\leq_{2})$ are smooth classes in $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ respectively. Assume that both classes are closed under substructure, and both have dAP and dPS. Let $M^{*}$ be the generic of the merge $(K^{*},\leq_{*})$ of $K_{1}$ and $K_{2}$ . Then for $i=1,2$ , $M^{*}|_{\mathcal{L}_{i}}\cong M_{i}$ , where $M_{i}$ is the generic of $(K_{i},\leq_{i})$ .

Proof:

By symmetry, we need only prove the theorem for $i=1$ . We must prove that $M^{*}|_{\mathcal{L}_{1}}$ satisfies conditions (1) and (2) from Definition 2.4. For $\mathcal{L}^{*}$ -structures $A,B\in K^{*}$ , we write $A\leq_{1}B$ if and only if $A|_{\mathcal{L}_{1}}\leq_{1}B|_{\mathcal{L}_{1}}$ . It is easy to see that, since $M^{*}$ is the generic of $K^{*}$ , $M^{*}|_{\mathcal{L}_{1}}$ satisfies (1). It remains to show (2).

Let $A\leq_{1}M^{*}$ and suppose $A\leq_{1}B_{1}$ for some $B_{1}\in K_{1}$ . As $M^{*}$ is the generic of $(K^{*},\leq_{*})$ , we can write $M^{*}=\bigcup_{n\in\omega}C_{n}$ where $C_{n}\leq_{*}C_{n+1}$ and $C_{n}\in K^{*}$ . Thus, there is some $n$ for which $A\leq_{1}C_{n}$ . By taking an isomorphic copy of $B_{1}$ , we may assume $C_{n}\cap B_{1}=A$ .
By applying dAP and closure under substructure in $\mathcal{L}_{1}$ , we can find some $D_{1}\in K_{1}$ with universe $(C_{n}\cup B_{1})$ such that $D_{1}$ is a disjoint amalgam over $A$ in $\mathcal{L}_{1}$ with $C_{n},B_{1}\leq_{1}D_{1}$ . Define $B_{2}$ so that the universe of $B_{2}$ is the same as that of $B_{1}$ , and define the $\mathcal{L}_{2}$ -structure of $B_{2}$ so that $B_{2}\in K_{2}$ with $B_{2}\geq A$ and $B_{2}\cap C_{n}=A$ (in the $\mathcal{L}_{2}$ sense).

Now, in the language $\mathcal{L}_{2}$ , using dPS over $A$ , we can find an $\mathcal{L}_{2}$ -structure $D_{2}\in K_{2}$ with universe $C_{n}\cup B_{2}\in K_{2}$ so that $C_{n}\leq_{2}D_{2}$ , $B_{2}\subseteq_{2}D_{2}$ , and $|D_{1}|=|D_{2}|$ . Define structures $D,B\in K^{*}$ to be so that $D|_{\mathcal{L}_{i}}=D_{i}$ , $B|_{\mathcal{L}_{i}}=B_{i}$ for $i=1,2$ .

Notice this then implies that $C_{n}\leq_{*}D$ by definition of $\leq_{*}$ . By the genericity of $M^{*}$ , there exists some $\mathcal{L}^{*}$ -embedding $g:D\rightarrow M^{*}$ which is the identity on $C_{n}$ such that $D^{*}:=g(D)\leq_{*}M^{*}$ and $C_{n}\leq_{*}D^{*}$ . Now, $g(B)\leq_{1}D^{*}$ and $A\leq_{1}g(B)$ . Moreover, $g(B)|_{\mathcal{L}_{1}}\cong B_{1}$ . By transitivity, $g(B)\leq_{1}M^{*}$ . This proves (2).

When classes are only assumed to be closed under substructure, it is indeed true that the generic of the merge is an expansion of the original generics. This follows from a set-up and proof given in §2 of [EHN19], though one must convert their theorems to the language and ideas of merging smooth classes. Whenever smooth classes $(K_{1},\leq_{1})$ and $(K_{2},\leq_{2})$ are each closed under substructure with dAP, the merge $K_{1}\circledast K_{2}$ is a strong extension of both $K_{1}$ and $K_{2}$ in the sense defined in §2 of [EHN19]. Because $K_{1}\circledast K_{2}$ is a strong extension, it is proven that if $M^{*}$ is the generic of $K_{1}\circledast K_{2}$ , then $M^{*}|_{\mathcal{L}_{i}}\cong M_{i}$ where $M_{i}$ is the generic of $(K_{i},\leq_{i})$ .

The proof of this result from [EHN19] and the proof of Proposition 2.11 are entirely different. It turns out that the additional assumption that the classes both have dPS gives an even stronger result than Proposition 2.11, which will be shown in Theorem 2.12. This was inspired from behavior observed from the merge of a class of Shelah-Spencer graphs (Example 2.2) with the Fraïssé class of finite equivalence relations. We observed a relationship between equivalence classes in the merge of the generic and the original generic of the class of Shelah-Spencer graphs. The assumption that classes have dPS is modeled after the fact that classes of Shelah-Spencer graphs have dPS.

We will now state and prove Theorem 2.12, which we consider to be the main result in our study of merging smooth classes.

Notation: If $\leq_{1}$ is a relation on a class in $\mathcal{L}_{1}$ and $A,B$ are structures in a language $\mathcal{L}\supseteq\mathcal{L}_{1}$ , we write $A\leq_{1}B$ for $A|_{\mathcal{L}_{1}}\leq_{1}B|_{\mathcal{L}_{1}}$ . If $A|_{\mathcal{L}_{1}}\cong B|_{\mathcal{L}_{1}}$ in $\mathcal{L}_{1}$ , we write $A\cong_{\mathcal{L}_{1}}B$

Theorem 2.12.

Let $(K_{1},\leq_{1})$ and $(K_{2},\leq_{2})$ be smooth classes in languages $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ with generics $M_{1}$ and $M_{2}$ respectively. Assume both classes are closed under substructure and have dAP. Suppose $K_{1}$ has smooth intersections and dPS. Let $M^{*}$ denote the generic of the merge $(K^{*},\leq_{*})$ of $K_{1}$ and $K_{2}$ . Suppose $C^{*}=\varphi(M^{*},\overline{m})$ is infinite, where $\overline{m}\subseteq M^{*}$ and $\varphi$ is an existential formula in $\mathcal{L}_{2}$ . Then, $C^{*}|_{\mathcal{L}_{1}}$ is isomorphic to the generic of $(K_{1},\leq_{1})$

Proof:

We must verify that $C^{*}|_{\mathcal{L}_{1}}$ satisfies (1) and (2) from Definition 2.4.

Because $M^{*}$ is the generic of $(K^{*},\leq_{*})$ , we may write $M^{*}=\bigcup_{n\in\omega}W_{n}$ where $W_{n}\leq_{*}W_{n+1}$ and $W_{n}\in K^{*}$ for all $n\in\omega$ . By assumption, and definition of $\leq_{*}$ ,

C^{*}=\bigcup_{n\in\omega}(W_{n}\cap C^{*})\text{ with }W_{n}\cap C^{*}\leq_{1}W_{n+1}\cap C^{*}\text{ for all }n\in\omega

By the assumption that all classes are closed under substructure, $W_{n}\cap C^{*}|_{\mathcal{L}_{1}}\in(K_{1},\leq_{1})$ . Thus, $C^{*}|_{\mathcal{L}_{1}}$ satisfies (1).

It remains to show that $C^{*}|_{\mathcal{L}_{1}}$ satisfies (2). Suppose $A\leq_{1}C^{*}$ and $A\leq_{1}B_{1}$ where $B_{1}\in K_{1}$ . We may take $B_{1}$ so that $B_{1}\cap M^{*}=A$ . Write $B_{1}-A=\{b_{1},\dots,b_{k}\}$ . As $C^{*}$ infinite, we may find a set of $k$ elements $E:=\{e_{1},\dots,e_{k}\}\subseteq C^{*}$ . Note that $E\in K^{*}$ . For each $i\leq k$ , there exists a finite tuple $\overline{h}_{i}\subseteq M^{*}$ which witnesses that the existential $\varphi(e_{i},\overline{m})$ holds in $M^{*}$ . Let

V:=\{m:m\in\overline{m}\}\cup\{h:h\in\overline{h}_{i}\text{ for some }i\}

We may find some finite $W_{n}=\{w_{1},\dots,w_{\ell}\}$ for which $A\cup V\subseteq W_{n}$ and $W_{n}\leq_{*}M^{*}$ . Note that $A\leq_{1}C^{*}\cap W_{n}$ by assumption. Using dAP in $K_{1}$ , we can find an $\mathcal{L}_{1}$ -structure $B^{\prime}$ with universe $(W_{n}\cap C^{*})\cup B_{1}$ that is an amalgamation over $A$ so that $A,B_{1},W_{n}\cap C^{*}\leq_{1}B^{\prime}$ . Using dPS in $K_{1}$ , we can find an $\mathcal{L}_{1}$ -structure $D_{1}$ with universe $W_{n}\cup B^{\prime}$ that is a dPS amalgam over $W_{n}\cap C^{*}$ such that $B^{\prime}\subseteq D_{1}$ and $W_{n}\leq_{1}D_{1}$ . Write $D_{1}=\{d_{1}^{1},\dots,d_{k}^{1}\}\cup\{w_{1},\dots,w_{\ell}\}$ where $d_{i}^{1}=b_{i}$ for $i\leq k$ and $w_{i}=w_{i}\in W_{n}$ .

Note that $E\cup W_{n}\subseteq M^{*}$ , so $E\cup W_{n}\in K^{*}$ , and, moreover, $|E\cup W_{n}|=|D_{1}|$ . Now, in $\mathcal{L}_{2}$ , define a $\mathcal{L}_{2}$ -structure $D_{2}$ enumerated $\{d^{2}_{1},\dots,d^{2}_{k}\}\cup\{w_{i},\dots,w_{\ell}\}$ so that $W_{n}\subseteq D_{2}$ and the map $f:D_{2}\rightarrow E\cup W_{n}$ is such that $f(d^{2}_{i})=e_{i}$ and $f(w_{i})=w_{i}$ is an $\mathcal{L}_{2}$ -isomorphism. As $W_{n}\leq_{*}M^{*}$ , we know that $W_{n}\leq_{2}D_{2}$ .

Define the $\mathcal{L}^{*}$ -structure $D=\{d_{1},\dots,d_{k}\}\cup\{w_{1},\dots,w_{\ell}\}$ where $w_{i}\in W_{n}$ so that $W_{n}\subseteq D$ (in the $\mathcal{L}^{*}$ sense); the map $h:D\rightarrow D_{2}$ defined $h(d_{i})=d^{2}_{i}$ , $h(w_{i})=w_{i}$ is an $\mathcal{L}_{2}$ -isomorphism; and the map $p:D\rightarrow D_{1}$ defined $p(d_{i})=d^{1}_{i}$ , $p(w_{i})=w_{i}$ is a $\mathcal{L}_{1}$ -isomorphism. Then, notice that $W_{n}\leq_{*}D$ . Now, because $W_{n}\leq_{*}M^{*}$ and $M^{*}$ is the $K^{*}$ generic, then there is a $\mathcal{L}^{*}$ -embedding $\alpha:D\rightarrow M^{*}$ so that $\alpha|_{W_{n}}$ is the identity map on $W_{n}$ and $D^{*}:=\alpha(D)\leq_{*}M^{*}$ . Let $B^{*}:=\alpha(\{d_{1},\dots,d_{k}\})\cup A$ . There is a natural $\mathcal{L}_{1}$ -isomorphism $\rho:B_{1}\rightarrow B^{*}$ by $\rho(b_{i})=d_{i}$ , fixing $A$ .

Notice that $B^{*}\leq_{1}\alpha(B^{\prime})$ (where we are looking at the copy of the $\mathcal{L}_{1}$ -structure $B^{\prime}$ in $D$ ). We can write $B^{\prime}=(W_{n}\cap C^{*})\cup B$ , and notice that in $D$ , $D\models\varphi(d_{i},\overline{m})$ for each $i\leq k$ since $\varphi$ is a $\mathcal{L}_{2}$ formula and the construction of $D$ preserved and copied the $\mathcal{L}_{2}$ the relations between each $e_{i}$ , $\overline{m}$ and $h_{i}$ for $i\leq k$ . Thus, $\alpha(B^{\prime})\subseteq C^{*}$ , as $W_{n}\cap C^{*}$ is fixed by $\alpha$ and as $\varphi(x,\overline{m})$ is existential, $M^{*}\models\varphi(\alpha(d_{i}),\overline{m})$ , thus ensuring $\alpha(d_{i})\in C^{*}$ . Moreover, $D^{*}\cap C^{*}=\alpha(W_{n}\cup B^{\prime})\cap C^{*}=(W_{n}\cap C^{*})\cup\alpha(B^{\prime})=\alpha(B^{\prime})$ . Therefore,

\alpha(\rho(B_{1}))\leq_{1}\alpha(B^{\prime})=D^{*}\cap C^{*}\leq_{1}C^{*}

Finally, recall that $A\subseteq W_{n}$ , so $\alpha\circ\rho$ is an embedding over $A$ as required. This completes the proof of (2).

By essentially the same argument, we get

Theorem 2.13.

Suppose $\mathcal{S}=\{(K_{i},\leq_{i}):i\in I\}$ is a set of smooth classes with uniform dAP such that each class $(K_{i},\leq_{i})$ is closed under substructure and has dPS. Suppose $M^{*}$ is the generic of the merge $\circledast_{i\in I}(K_{i},\leq_{i})$ in the language $\mathcal{L}^{*}=\{\mathcal{L}_{i}:i\in I\}$ . For every $J\subseteq I$ , if $C^{*}=\varphi(M^{*},\overline{m})$ is infinite with $\overline{m}\subseteq M^{*}$ and $\varphi$ an existential formula in the language $\bigcup_{i\in I-J}\mathcal{L}_{i}$ , then $C^{*}\cong M_{i}$ , the generic of $(K_{i},\leq_{i})$ , for $i\in J$ .

Theorem 2.12 has the following direct consequences.

Suppose $(K_{1},\leq_{1})$ and $(K_{2},\leq_{2})$ are smooth classes closed under substructure with dAP, and that $(K_{1},\leq_{1})$ has smooth intersections and dPS. Let $M_{1}$ and $M_{2}$ denote their respective generics, and $M^{*}$ to be the generic of $K_{1}\circledast K_{2}$ .

Corollary 2.14.

$Aut(M^{*})\cong Aut(M_{1})\cap Aut(M_{2})$ as subgroups of $Sym(M^{*})$ .

Corollary 2.15.

If $a\in M_{1}$ , then $M_{1}\cong M_{1}-\{a\}$ .

Proof:

Using Theorem 2.12 and merging $(K_{1},\leq_{1})$ with any Fraïssé class $(K_{2},\leq_{2})$ , for any $a\in M^{*}$ , the set $C^{*}=\{b\in M^{*}:b\neq a\}$ is indeed isomorphic to $M_{1}$ .

The next corollary holds by taking $(K_{2},\leq_{2})$ to be the class of finite structures with a binary equivalence relation and applying the main theorem:

Corollary 2.16.

There is an expansion of $M_{1}$ by a binary equivalence relation $E$ such that for any $n\in\omega$ , and $\{P_{i}\}_{i\leq n}$ a set of $n$ equivalence classes of $M_{1}$ , $\bigcup_{i\leq n}P_{i}\cong M_{1}$

The class $(K_{1},\leq_{1})$ can be taken to be a class of Shelah-Spencer graphs $(K_{\alpha},\leq_{\alpha})$ with generic $M_{\alpha}$ , and the class $(K_{2},\leq)$ can be taken to be the Fraïssé class of all finite linear orders, giving:

Corollary 2.17.

There exists a family of sets $\{W_{i}\}_{i\in\omega}$ of subsets of $M_{\alpha}$ such that any finite, non-empty intersection of sets in $\{W_{i}\}_{i\in\omega}$ is isomorphic to $M_{\alpha}$ .

Take $(K_{1},\leq_{1})$ to be a class of Shelah-Spencer graphs $(K_{\alpha},\leq_{\alpha})$ in the language $\mathcal{L}_{\alpha}:=\{E_{\alpha}\}$ , where $E_{\alpha}$ is binary, and $(K_{2},\leq_{2})$ to be another class of Shelah-Spencer graphs $(K_{\beta},\leq_{\beta})$ in the language $\mathcal{L}_{\beta}:=\{E_{\beta}\}$ where $E_{\beta}$ is a binary relation. Let $E_{\beta}\in\mathcal{L}_{\beta}$ . Applying Theorem 2.12, the following holds:

Corollary 2.18.

For $a\in M^{*}$ and $C^{*}:=\{b\in M^{*}:\exists x(E_{\beta}(a,x)\land E_{\beta}(x,b)\land\neg E_{\beta}(a,b))\}$ , $C^{*}|_{\mathcal{L}_{\alpha}}\cong M_{\alpha}$ .

All of these, of course, can be extended to results with other Fraïssé classes such as the class of finite graphs, the class of $K_{n}$ free graphs, etc.

These results may be thought of as well-behaved expansions of generics. They also give an idea of the overall structure of a generic, reminiscent of the "self-referential" properties of some Fraïssé classes. For example, the rationals under the standard linear order, $(\mathbb{Q},\leq)$ , is the Fraïssé limit of the class of all finite linear orders, and it has the property that every open interval in $(\mathbb{Q},\leq)$ is indeed isomorphic to $(\mathbb{Q},\leq)$ . Here, we get that for a sufficiently nice class $(K_{1},\leq_{1})$ , its generic $M_{1}$ has the property that it can be linearly ordered so that every interval is isomorphic to $M_{1}$ .

Given Theorem 2.12, we see that in many cases there is a relationship between the generic of a merge and the generics of the original smooth class. The question is then what other properties of the generics of the original classes transfer to the generic of the merge. The remainder of the paper will discuss this transfer of properties.

2.3.2 Atomic Generics and Merges

In this section, we will study smooth classes with atomic generics and their merged generics. It turns out that the property of the generic of a smooth class being atomic is dependent on the universal formula definition of the relation of the smooth class. Because of this dependency, the property of the generic being atomic transfers very well to the generic of a merge.

We begin by proving the converse of Proposition 3.4 in [KL92], characterizing atomic generics of smooth classes. We will include both directions of the proof for convenience, and because we will need both directions.

Recall: By definition of smoothness, for every $A\in K$ and enumeration $\overline{a}$ of $A$ , there is a set of universal formulas $\Phi_{\overline{a}}$ such that

A\leq C\Leftrightarrow C\models\phi(\overline{a})\text{ for all }\phi\in\Phi_{\overline{a}}

Proposition 2.19.

Let $(K,\leq)$ be a smooth class with a generic $M$ . Then, $M$ is atomic if and only if for every $A\in K$ and every enumeration $\overline{a}$ of $A$ , $\Phi_{\overline{a}}$ is finitely generated modulo $Th(M)$ . I.e., there exists a finite subset $\Phi^{0}_{\overline{a}}\subseteq\Phi_{\overline{a}}$ such that for $\psi_{\overline{a}}(\overline{x}):=\bigwedge_{\phi\in\Phi^{0}_{\overline{a}}}\phi(\overline{x})$ , $M\models\forall\overline{x}(\psi_{\overline{a}}(\overline{x})\rightarrow\Phi_{\overline{a}}(\overline{x}))$ .

Proof:

$(\Rightarrow)$ : Let $A\in K$ and fix an enumeration $\overline{a}=(a_{1},\dots,a_{n})$ of $A$ , and suppose that $M\models\Phi_{\overline{a}}(\overline{a})$ . As $M$ is atomic, suppose $\theta(\overline{x})$ isolates $tp_{M}(\overline{a})$ . Suppose now that $B\subseteq M$ is enumerated by $\overline{b}=(b_{1},\dots,b_{n})$ and $M\models\Phi_{\overline{a}}(\overline{b})$ . We immediately have that $f:A\rightarrow B$ defined $f(a_{i})=b_{i}$ is an isomorphism. Then $B\in K$ , and we get that $\Phi_{\overline{a}}=\Phi_{\overline{b}}$ by definition. Thus, as $M\models\Phi_{\overline{b}}(\overline{b})$ , $B\leq M$ . By the genericity of $M$ , the isomorphism $f:A\rightarrow B$ extends to an automorphism of $M$ . This implies that $M\models\theta(b_{1},\dots,b_{n})$ . Thus,

M\models\forall\overline{x}(\Phi_{\overline{a}}(\overline{x})\rightarrow\theta(\overline{x}))

But, this implies that some finite subset of $\Phi_{\overline{a}}$ must imply $\theta$ modulo $Th(M)$ , and hence $\Phi_{\overline{a}}$ itself.

$(\Leftarrow)$ : Let $A\subseteq M$ be enumerated by $\overline{a}=(a_{1},\dots,a_{n})$ . Let $A\subseteq B$ where $B$ is the smallest superstructure of $A$ with $B\leq M$ . Enumerate $B$ as $\overline{a}^{\smallfrown}\overline{b}$ , where $\overline{b}=(b_{1},\dots,b_{m})$ . Let $\psi_{\overline{a}^{\smallfrown}\overline{b}}$ be the formula in the assumption associated with $B$ and $\overline{a}^{\smallfrown}\overline{b}$ . We have that $M\models\psi_{\overline{a}^{\smallfrown}\overline{b}}(\overline{a}^{\smallfrown}\overline{b})$ . Set

\theta(y_{1},\dots,y_{n}):=\exists x_{1},\dots,x_{m}(\psi_{\overline{a}^{\smallfrown}\overline{b}}(y_{1},\dots,y_{n},x_{1},\dots,x_{m}))

Claim: $\theta(\overline{x})$ isolates $tp_{M}(\overline{a})$ .
Suppose $M\models\theta(\overline{d})$ . Then, this implies the existence of some $C$ enumerated $\overline{c}=\overline{d}^{\smallfrown}(c_{1},\dots,c_{m})$ where $M\models\psi_{\overline{a}^{\smallfrown}\overline{b}}(\overline{c})$ . We know by assumption that there is an isomorphism $f:B\rightarrow C$ with $f(a_{i})=d_{i}$ and $f(b_{i})=c_{i}$ . It follows that $C\leq M$ . By the genericity of $M$ , $f$ has an extension to an automorphism of $M$ . Thus, $tp(\overline{a})=tp(\overline{d})$ , and it follows that $\theta$ isolates $\overline{a}$ .

Corollary 2.20.

Let $(K_{1},\leq_{1})$ and $(K_{2},\leq_{2})$ be smooth classes in respective languages $\mathcal{L}_{1}$ , $\mathcal{L}_{2}$ and generics $M_{1}$ , $M_{2}$ . Suppose the merge $(K_{1}\circledast K_{2},\leq_{*})$ has a generic $M^{*}$ . Moreover, assume that $M^{*}|_{\mathcal{L}_{1}}\cong M_{1}$ and $M^{*}|_{\mathcal{L}_{2}}\cong M_{2}$ . If $M_{1}$ and $M_{2}$ are atomic then the merged generic $M^{*}$ is atomic.

Proof:

For simplicity, we will assume $M^{*}|_{\mathcal{L}_{i}}=M_{i}$ for $i=1,2$ . Given some $A\in K^{*}$ , write $A_{i}$ for $A|_{\mathcal{L}_{i}}$ . Let $\overline{a}$ be an enumeration of $A$ . Let $\psi_{\overline{a}}^{1}$ and $\psi^{2}_{\overline{a}}$ be the $\mathcal{L}_{1}$ - and $\mathcal{L}_{2}$ - formulas given by Proposition 2.19 such that for $i=1,2$ ,

M_{i}\models\forall\overline{x}(\psi^{i}_{\overline{a}}(\overline{x})\leftrightarrow\Phi^{i}_{\overline{a}}(\overline{x}))

Now, suppose $M^{*}\models\Phi^{*}_{\overline{a}}(\overline{b})$ for some $\overline{b}\subseteq M^{*}$ . For each $i=1,2$ , this immediately implies that $M^{*}\models\psi^{i}_{\overline{a}}(\overline{b})$ . Now, assume that $M^{*}\models\psi^{1}_{\overline{a}}(\overline{b})\land\psi^{2}_{\overline{a}}(\overline{b})$ . Then, $M_{i}\models\psi^{i}_{\overline{a}}(\overline{b})$ , and thus $M_{i}\models\Phi^{i}_{\overline{a}}(\overline{b})$ . But this implies that $M^{*}\models\Phi^{*}_{\overline{a}}(\overline{b})$ . Therefore, $M^{*}\models\forall\overline{x}([\psi^{1}_{\overline{a}}(\overline{x})\land\psi^{2}_{\overline{a}}(\overline{x})]\Leftrightarrow\Phi^{*}_{\overline{a}}(\overline{x}))$ . We can freely impose that $\psi^{1}_{\overline{a}}\land\psi^{2}_{\overline{a}}\in\Phi_{A}$ . By Proposition 2.19, $M^{*}$ is atomic.

From Corollary 2.20 we get another immediate result:

Proposition 2.21.

Let $(K_{1},\subseteq)$ be a Fraïssé class and $(K_{2},\leq_{2})$ a smooth class. Suppose the merge $(K_{1}\circledast K_{2},\leq_{*})$ has a generic $M^{*}$ such that for $i=1,2$ , $M^{*}|_{\mathcal{L}_{i}}\cong M_{i}$ , where $M_{i}$ is the generic of $K_{i}$ . If $M_{2}$ is $\omega$ -categorical, then $M^{*}$ is $\omega$ -categorical.

Proof:

We will show that every countable structure $N$ such that $N\models Th(M^{*})$ , $N\cong M^{*}$ . Suppose $N\models Th(M^{*})$ . We must prove that $N$ has properties (1) and (2) from Definition 2.4.

To prove (1), note that we have that $N\models Th(M_{1})\cup Th(M_{2})$ . By each of $Th(M_{1})$ and $Th(M_{2})$ being $\omega$ -categorical, $N|_{\mathcal{L}_{i}}\cong M_{i}$ for $i=1,2$ . In particular, we can write $N|_{\mathcal{L}_{2}}=\bigcup_{n\in\omega}A_{n}$ with $A_{n}\leq_{2}A_{n+1}$ . It follows by $(K_{1},\subseteq)$ being a Fraïssé class that $A_{n}\leq_{*}A_{n+1}$ in the full structure $N$ and $A_{n}\in K^{*}$ .

It remains to prove that $N$ has property (2). Suppose $A\leq_{*}N$ and $A\leq_{*}B$ for some $B\in K_{1}\circledast K_{2}$ . Let $\overline{a}=\{a_{1},\dots,a_{n}\}$ be an enumeration of $A$ and let $\overline{b}=\overline{a}^{\smallfrown}\{b_{1},\dots,b_{m}\}$ be an enumeration of $B$ . By Corollary 2.20, $M^{*}$ is atomic, and so by Proposition 2.19 there exist $\psi^{*}_{\overline{a}}$ and $\psi^{*}_{\overline{b}}$ such that $M^{*}\models\forall\overline{x}(\psi^{*}_{\overline{a}}(\overline{x})\leftrightarrow\Phi^{*}_{\overline{a}}(\overline{x}))$ and $M^{*}\models\forall\overline{y}(\psi^{*}_{\overline{b}}(\overline{y})\leftrightarrow\Phi^{*}_{\overline{b}}(\overline{y}))$ .

As $M^{*}$ is a generic, we have that

M^{*}\models\forall(x_{1},\dots,x_{n})(\psi^{*}_{\overline{a}}(x_{1},\dots,x_{n})\rightarrow\exists(y_{1},\dots,y_{m})(\psi^{*}_{\overline{b}}(x_{1},\dots,x_{n};y_{1},\dots,y_{m})))

Thus, as $N\models Th(M^{*})$ , there is an embedding of $f:B\rightarrow N$ such that $f|_{A}=id_{A}$ and $f(B)\leq_{*}N$ . This shows that $N$ has property (3).

In the next section, we will prove that there are classes with saturated generics for which the merged generic is not saturated. Similar arguments as in the next section show that Proposition 2.21 does not necessarily extend when both classes are smooth but not Fraïssé. In the proof of Proposition 2.21, the proof that every countable $N\models Th(M^{*})$ has property (2) always holds for $\omega$ -categorical smooth classes (not necessarily Fraïssé) $(K_{1},\leq_{1})$ , $(K_{2},\leq_{2})$ ; it is the proof that any such $N$ has property (1) that may fail.

2.3.3 Saturated generics and merges

We now ask how the merged generic behaves when both of the original generics are saturated. In contrast to atomic generics, the property of saturation transfers poorly to the generic of a merge. This is due, in part, by the relation $\leq_{*}$ in the merged generic being dependent the relations on the original classes; the result is that the generic of the merge cannot satisfy all the new types created.

To make this concrete, we will recall some results and definitions about saturation and smooth classes. For a full treatment of these results, see [BS96].

Definition 2.22.

Suppose $(K,\leq)$ is a smooth class of finite structures. We say for $A,B\in K$ , $(A,B)$ is a $\leq$ -minimal pair if for every $A\subseteq B^{\prime}\subsetneq B$ , $A\leq B^{\prime}$ but $A\not\leq B$ . $(K,\leq)$ has an infinite chain of $\leq$ -minimal pairs if there is a chain

A_{0}\subseteq A_{1}\subseteq\dots A_{n}\subseteq\dots

such that $A_{i}\in K$ and $(A_{i},A_{i+1})$ is a $\leq$ -minimal pair for $i\in\omega$ .

We reprove a well-known result about smooth classes and saturation:

Theorem 2.23.

If $(K,\leq)$ has a generic $M$ , smooth intersections, and an infinite chain of $\leq$ -minimal pairs, then $M$ is not saturated.

Proof:

Let $\{A_{i}\}_{i\in\omega}$ be an infinite chain of $\leq$ -minimal pairs. Let $k=|A_{0}|$ and let $\Delta_{i}(x_{1},\dots,x_{k},\overline{y})$ denote the elementary diagram of $A_{i}$ over $A_{0}$ . Set

\Gamma_{i}(x_{1},\dots,x_{k})=(\Delta_{0}(x_{1},\dots,x_{k})\land\exists\overline{y}(\Delta_{i}(x_{1},\dots,x_{k},\overline{y}))

Let $\Gamma^{n}(x_{1},\dots,x_{k})=\{\Gamma_{i}(x_{1},\dots,x_{k}):i\leq n\}$ . Note that $\Gamma^{n}$ is realized in $M$ by a strong embedding of $A_{n}$ into $M$ . Let $\Gamma:=\bigcup_{n\in\omega}\Gamma^{n}$ . It follows that $Th(M)\cup\Gamma$ is finitely satisfiable, and hence satisfiable by compactness. However, $M$ does not realize $\Gamma$ . To see this, suppose $M\models\Gamma(A^{0})$ for some $A^{0}\subseteq M$ . There is some finite $B\subseteq M$ such that $A^{0}\subseteq B\leq M$ . Suppose $n-1=|B|$ . As $M\models\Gamma(A^{0})$ , there exist sets $A^{i}$ such that $A^{0}\subseteq A^{i}\subseteq M$ and $(A^{i},A^{i+1})$ are $\leq$ -minimal pairs for $i\leq n$ . Note that $B\cap A^{i}\leq A^{i}$ , so if $B\cap A^{i}\neq A^{i}$ , then $A^{0}\leq B\cap A^{i}$ by definition of a $\leq$ -minimal pair . But this is a contradiction, so $A^{i}\subseteq B$ for all $i\in\omega$ . However, this implies $|B|\geq n$ , which is a contradiction.

Definition 2.24.

A smooth class $(K,\leq)$ has many minimal pairs if there exists some $m\in\omega$ such that for all $A\in K$ with $|A|\geq m$ and for all $n\geq 1$ , there exists some $A^{\prime}\in K$ such that $A\leq A^{\prime}$ , $|A^{\prime}|=|A|+n$ , and there is some $B\in K$ for which $(A^{\prime},B)$ is a $\leq$ -minimal pair

Example 2.25.

Note that for $\alpha\in\mathbb{Q}\cap(0,1)$ , the class of Shelah-Spencer $\alpha$ -graphs $(K_{\alpha},\leq_{\alpha})$ has many minimal pairs and the generic $M_{\alpha}$ of $(K_{\alpha},\leq_{\alpha})$ is saturated by [Gun18]. Theorem 2.26 will show that for $\alpha$ , $\beta\in\mathbb{Q}\cap(0,1)$ , the generic $M^{*}$ of the merge $(K_{\alpha}\circledast K_{\beta},\leq_{*})$ is not saturated, despite the fact that $M^{*}|_{\mathcal{L}_{\alpha}}\cong M_{\alpha}$ and $M^{*}|_{\mathcal{L}_{\beta}}\cong M_{\beta}$ . In fact, $Th(M^{*})$ is not small. This shows that there exist classes with saturated generics whose merged generic is not saturated, even when both classes satisfy the assumptions of Proposition 2.11.

Theorem 2.26.

Suppose $(K_{1},\leq_{1})$ and $(K_{2},\leq_{2})$ are smooth classes, each closed under substructure in the resp. languages $\mathcal{L}_{1}$ , $\mathcal{L}_{2}$ . Suppose both classes have many minimal pairs, and suppose the merge $(K^{*},\leq_{*})$ has a generic $M^{*}$ . Then $M^{*}$ is not saturated.

Proof:

We will show $(K^{*},\leq_{*})$ has an infinite chain $\{A_{i}\}_{i\in\omega}$ of $\leq_{*}$ -minimal pairs, and get the conclusion by applying Theorem 2.23. By assumption, there exists some $m\in\omega$ such that for $i=1,2$ , if $A\in K_{i}$ with $|A|\geq m$ , then there is some $A^{\prime}\in K_{i}$ such that $A\leq_{i}A^{\prime}$ and there exists some $B\in K_{i}$ such that $(A^{\prime},B)$ is a $\leq_{i}$ -minimal pair.

Choose some $A_{0}\in K^{*}$ such that $|A_{0}|\geq m$ . There exists some $B_{1}\in K_{1}$ so that $(A_{0}|_{\mathcal{L}_{1}},B_{1})$ forms a $\leq_{1}$ -minimal pair. On the same universe as $B_{1}$ , by assumption, we can define $B_{2}\in K_{2}$ so that $A_{0}\leq_{2}B_{2}$ and there exists some $C\in K_{2}$ so that $(B_{2},C)$ forms a $\leq_{2}$ -minimal pair. Define $A_{1}$ on the universe of $B_{1}$ so that $A_{1}|_{\mathcal{L}_{i}}=B_{i}$ for $i=1,2$ . Then, $A_{0}\leq_{2}A_{1}$ and $(A_{0}|_{\mathcal{L}_{1}},A_{1})$ is a $\leq_{1}$ -minimal pair. Thus, $(A_{0},A_{1})$ is a $\leq_{*}$ -minimal pair.

Suppose $n$ is odd and $A_{n}$ has been defined so that there exists some $C_{2}\in K_{2}$ for which $(A_{n}|_{\mathcal{L}_{2}},C_{2})$ is a $\leq_{2}$ -minimal pair. By assumption, we can find some $C_{1}\in K_{1}$ with the same universe as $C_{2}$ for which $A_{n}\leq_{1}C_{1}$ and there exists some $D_{1}\in K_{1}$ for which $(C_{1},D_{1})$ forms a $\leq_{1}$ -minimal pair. Let $A_{n+1}$ be defined on the same universe as $C_{2}$ so that $A_{n+1}|_{\mathcal{L}_{i}}=C_{i}$ for $i=1,2$ . Then, $A_{n}\leq_{1}A_{n+1}$ and $(A_{n},A_{n+1})$ forms a $\leq_{2}$ -minimal pair. Then, $(A_{n},A_{n+1})$ is a $\leq_{*}$ -minimal pair. For $n$ even, we switch the roles of $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ in the odd case.

Carrying out this construction, we have an infinite chain $\{A_{i}\}_{i\in\omega}$ of $\leq_{*}$ -minimal pairs.

3 Structural Ramsey Theory, EPPA Classes, and Merges

We now turn our attention to the branch of study of structural Ramsey theory. For many years, there has been a campaign to identify classes with the EPPA and Ramsey properties (defined below), especially after the links to topological dynamics were discovered. Most work has been done in the context of Fraïssé classes and, in particular, classes of rigid structures. It is notable that merges of Fraïssé classes have shown up as many of the examples of classes with the Ramsey property and as a way to "rigidify" classes.

The current goal is to try to expand the ideas used on Fraïssé classes to gain an understanding of smooth classes and their merges and which smooth classes have the Ramsey properties. The Ramsey property is hard to achieve in this context; however, a stepping stone is the Hrushovski/EPPA property. In this section we will expand and generalize on previous work to get some classes which do indeed have the EPPA property and for which the EPPA property transfers nicely to some merges of these classes.

3.1 Background & Motivation

Merges of Fraïssé classes have played an important role in the development of structural Ramsey theory. We first recall the definition of the Ramsey property in the smooth class setting:

Definition 3.1.

Suppose $(K,\leq)$ is a smooth class. Let $\binom{B}{A}=\{C\leq B:C\cong A\}$ . We say $K$ has the Ramsey property if for any $A\leq B$ with $A,B\in K$ , there exists some $C\in K$ for which $B\leq C$ for every coloring $c:\binom{C}{A}\rightarrow\{0,1\}$ , there is some $B^{\prime}\in\binom{C}{B}$ such that $c|_{\binom{B^{\prime}}{A}}$ is constant.

It is important to note that we are taking the Ramsey property to be on colorings of structures as opposed to colorings of embeddings. This is mostly to avoid ambiguity and to include classes of structures which are not rigid.

Much of the focus of the study of Ramsey classes is on classes of rigid structures because of their connection to extreme amenability. The so-called "KPT-Correspondence" coming from the main results of [KPT04] (and generalized by [GKP16]) asserts that if a smooth class $(K,\leq)$ is a class of rigid structures with generic $M$ , then $Aut(M)$ is extremely amenable if and only if $(K,\leq)$ has the Ramsey property.

Many Fraïssé classes which were proved to have the Ramsey property are indeed merges of Fraïssé classes. Let $(K_{LO},\subseteq)$ denote the Fraïssé class of all finite linear orders. When $(K_{F},\subseteq)$ is a Fraïssé class with fAP, by [NR83], $K_{LO}\circledast K_{F}$ has the Ramsey Property. This is, however, not always the case for any Fraïssé class merged with $K_{LO}$ . For example, the class $(K_{E},\subseteq)$ of finite structures with an equivalence relation has the Ramsey property, however, $K_{LO}\circledast K_{E}$ does not.

Merges behave better once we are merging classes which are already rigid and known to have the Ramsey property, as shown in the below theorem by [Bod12]:

Theorem 3.2.

If $(K_{1},\subseteq)$ and $(K_{2},\subseteq)$ are Fraïssé classes of rigid structures (i.e., every automorphism is trivial) and $K_{1}$ , $K_{2}$ both have the Ramsey property and dAP, then $K_{1}\circledast K_{2}$ has the Ramsey Property. Moreover, if $K_{3}$ is a Fraïssé class of rigid structures with the Ramsey property, and $K_{2}\circledast K_{LO}$ has the Ramsey property, then $K_{3}\circledast K_{2}$ has the Ramsey property.

This shows, for example, if $K_{1}$ and $K_{2}$ are two Fraïssé classes with fAP, $(K_{1}\circledast K_{LO})*(K_{2}\circledast K_{LO})$ has the Ramsey property (when we take the languages of each class to be disjoint) and, moreover, so does $K_{1}\circledast K_{2}\circledast K_{LO}$ . It is not yet clear when Theorem 3.2 will extend to the non-rigid case, or to the general smooth class setting. The proof of the above theorem relies heavily on $\omega$ -categoricity and the results of [KPT04] in rigid settings.

It is our current goal to identify smooth classes with the Ramsey property, but this is a difficult task. As many authors have noted, classes with the Hrushovski property (or EPPA) (defined below) often have connections with classes with the Ramsey property. For example, $K_{F}$ in the example above has been proven to have EPPA, as well as other classes which have a Ramsey property in some merge. Thus, it seems prudent to study EPPA in the smooth class case in hopes of getting an eventual grasp of the Ramsey property.

We now recall a definition for EPPA in the context of smooth classes:

Definition 3.3.

Let $(K,\leq)$ be a smooth class. We say $(K,\leq)$ has $\leq$ -EPPA if for any $A\in K$ , and for any partial automorphisms $f_{1},\dots,f_{n}$ of $A$ , where, for each $i$ , $dom(f_{i})\leq A$ and $range(f_{i})\leq A$ , then there exists some $B$ with $A\leq B$ such that there exist automorphisms $g_{1},\dots,g_{n}$ of $B$ with $f_{i}\subseteq g_{i}$ . (When $\leq$ is substructure, we simply say EPPA.)

There is a clear relationship between classes with EPPA and amenability, shown in [KR06], which [EHN19] realized extended to $\leq$ -EPPA:

Proposition 3.4.

Let $(K,\leq)$ be a smooth class with a generic $M$ . If $(K,\leq)$ has $\leq$ -EPPA, then $Aut(M)$ is amenable.

It is known by [HO03] that Fraïssé classes with free amalgamation have EPPA. This result does not extend to smooth classes. The Shelah-Spencer class $(K_{\alpha},\leq_{\alpha})$ as defined in 2.2, is a class with fAP. It was proven in [GKP16] and [EHN19] that $(K_{\alpha},\leq_{\alpha})$ has neither the Ramsey property nor $\leq$ -EPPA. In fact, they proved that the automorphism group is not amenable for any $\alpha\in(0,1)$ .

We also will make use of a definition of EPPA for permorphisms in the next few sections. These will be definitions originating from Herwig in [Her95] with which we will use the results from [HKN22].

Definition 3.5.

Let $\Gamma_{\mathcal{L}}=\{\chi_{1},\dots,\chi_{n}\}$ be a finite group of permutations of the language $\mathcal{L}$ which preserve arity of the relations and fix equivalence.

Given an $\mathcal{L}$ -structure $A$ and a bijective function $f:A\rightarrow A$ , $f$ is a $\chi_{i}$ -permorphism of $A$ if $A\models R(a_{1},\dots,a_{n})\Leftrightarrow A\models\chi_{i}(R)(f(a_{1}),\dots,f(a_{n}))$ for all relations $R\in\mathcal{L}$ .

Definition 3.6.

A class $(K,\leq)$ has $\Gamma_{\mathcal{L}}$ - $\leq$ -EPPA if whenever $A\in K$ and $f_{1},\dots,f_{n}$ are partial permorphisms of $A$ such that $f_{i}$ is a $\chi_{i}$ -permorphism for some $\chi_{i}\in\Gamma_{\mathcal{L}}$ and $dom(f_{i}),range(f_{i})\leq A$ for all $i$ , then there exists some $B\in K$ such that $A\leq B$ and there exist full permorphisms $g_{1},\dots,g_{n}$ of $B$ such that $g_{i}$ is a $\chi_{i}$ -permorphism and $g_{i}\supseteq f_{i}$ .

3.2 Smooth Classes with $\leq$ -EPPA

In this section, we will prove a particular type of smooth class with fAP has $\leq$ -EPPA. This will be a generalization on work done in both [EHN19] and [HKN22]. We may also extend this to some classes of the same type which do not have fAP. To do this, we will use a nonstandard notion of structure described in [HKN22].

3.2.1 Extended Structures

Because many of the current theorems that give EPPA results involve classes which are Fraïssé classes, or, at minimum, where the relation on the classes is $\subseteq$ , they cannot be directly applied to smooth classes. A method of remedying this is to convert proper smooth classes to Fraïssé classes by adding partial functions which map points to sets. The newest EPPA results from [HKN22] can handle this type of Fraïssé class and language. However, adding partial functions which map points to sets gives rise to non-standard model theoretic structures. For completeness, we will describe these structures.

Definition 3.7.

Let $\mathcal{L}$ be a relational language. An extended language of $\mathcal{L}$ is a language $\mathcal{L}_{ext}=\mathcal{L}\cup\{U\}\cup\mathcal{L}_{fun}$ , where $\mathcal{L}_{fun}$ is a set of function symbols and $U$ is a new unary predicate. For a $\mathcal{L}_{ext}$ -structure $\mathcal{A}$ , let $U_{\mathcal{A}}$ denote the set of all elements of $\mathcal{A}$ satisfying $U$ . A two-sorted $\mathcal{L}_{ext}$ -structure $\mathcal{A}$ is an extended $\mathcal{L}_{ext}$ -structure if the set $\mathcal{A}-U_{\mathcal{A}}$ is precisely the power set $\mathcal{P}(U_{\mathcal{A}})$ ; for every relation $R\in\mathcal{L}$ of arity $n$ , $R^{\mathcal{A}}\subseteq U_{\mathcal{A}}^{n}$ ; and for every function $f\in\mathcal{L}_{fun}$ of arity $n$ , $f$ is a partial function such that $dom(f)\subseteq U^{n}_{\mathcal{A}}$ and $range(f)\subseteq\mathcal{P}(U_{\mathcal{A}})$ .

Definition 3.8.

An extended homomorphism $\Phi:\mathcal{A}\rightarrow\mathcal{B}$ between two extended $\mathcal{L}_{ext}$ -structures $\mathcal{A}$ and $\mathcal{B}$ is a function $\Phi_{U}:U_{\mathcal{A}}\rightarrow U_{\mathcal{B}}$ such that for all relations $R\in\mathcal{L}$

(a_{1},\dots,a_{n})\in R^{\mathcal{A}}\Rightarrow(\Phi_{U}(a_{1}),\dots,\Phi_{U}(a_{n}))\in R^{\mathcal{B}}

and for any function $f\in\mathcal{L}_{fun}$ , we have that

f^{\mathcal{A}}(a_{1},\dots,a_{n})\subseteq f^{\mathcal{B}}(\Phi_{U}(a_{1}),\dots,\Phi_{U}(a_{n}))

$\Phi$ is an extended embedding of $\mathcal{A}$ into $\mathcal{B}$ if for all $R\in\mathcal{L}$ (including equality)

(a_{1},\dots,a_{n})\in R^{\mathcal{A}}\Leftrightarrow(\Phi_{U}(a_{1}),\dots,\Phi_{U}(a_{n}))\in R^{\mathcal{B}}

and for any function $f\in\mathcal{L}_{fun}$ , we have that

f^{\mathcal{A}}(a_{1},\dots,a_{n})=f^{\mathcal{B}}(\Phi_{U}(a_{1}),\dots,\Phi_{U}(a_{n}))

Whenever an extended embedding $\Phi:\mathcal{A}\rightarrow\mathcal{B}$ is onto, $\Phi$ is an extended isomorphism between $\mathcal{A}$ and $\mathcal{B}$ . An extended structure $\mathcal{A}$ is an extended substructure of the extended structure $\mathcal{B}$ if $U_{\mathcal{A}}\subseteq U_{\mathcal{B}}$ and the map $id:U_{\mathcal{A}}\rightarrow U_{\mathcal{B}}$ is an extended embedding between $\mathcal{A}$ and $\mathcal{B}$ . Whenever $\mathcal{A}$ is an extended substructure of $\mathcal{B}$ , we will write $\mathcal{A}\preceq\mathcal{B}$ . An extended automorphism of an extended structure $\mathcal{A}$ is an extended isomorphism $\Phi:\mathcal{A}\rightarrow\mathcal{A}$ . An extended partial automorphism of an extended structure $\mathcal{A}$ is an extended isomorphism $\Phi:\mathcal{C}\rightarrow\mathcal{D}$ such that $\mathcal{C},\mathcal{D}\preceq\mathcal{A}$ .

Definition 3.9.

Let $(\mathcal{K},\preceq)$ be a class of extended $\mathcal{L}_{ext}$ -structures related by $\preceq$ .

1.

We say $\mathcal{K}$ has closure under extended substructure if $K$ is closed under $\preceq$ .
2.

$(\mathcal{K},\preceq)$ is an disjoint amalgamation class if $\mathcal{K}$ is closed under extended substructure, and, for any $\mathcal{A},\mathcal{B},\mathcal{C}\in\mathcal{K}$ such that $U_{\mathcal{A}}=U_{\mathcal{B}}\cap U_{\mathcal{C}}$ , $\mathcal{A}\preceq\mathcal{B},\mathcal{C}$ , there is some $\mathcal{D}\in\mathcal{K}$ such that $U_{\mathcal{D}}=U_{\mathcal{C}}\cup U_{\mathcal{B}}$ and $\mathcal{B},\mathcal{A},\mathcal{C}\preceq\mathcal{D}$ .

$(\mathcal{K},\preceq)$ is a free amalgamation class if it is a disjoint amalgamation class and for any $\mathcal{A}$ , $\mathcal{B}$ , $\mathcal{C}\in\mathcal{K}$ as above, we can choose $\mathcal{D}\in\mathcal{K}$ such that for any tuple $\overline{d}$ which includes elements from both $U_{\mathcal{B}}-U_{\mathcal{A}}$ and $U_{\mathcal{C}}-U_{\mathcal{A}}$ , then no relation $R\in\mathcal{L}$ holds on $\overline{d}$ in $\mathcal{D}$ and $\overline{d}$ is not in the domain of any function $f\in\mathcal{L}_{fun}$ in $\mathcal{D}$ .

We will now only work with finite permutation groups $\Gamma_{\mathcal{L}}$ on the extended language $\mathcal{L}^{F}$ which fix $\mathcal{L}^{F}-\mathcal{L}$ and preserve equality, arity, and symbol type. The definitions of EPPA, and $\Gamma_{\mathcal{L}}$ -EPPA from the previous section generalize to extended structures and extended partial automorphisms. In this context, we use the following main result from [HKN22]:

Theorem 3.10.

Let $\mathcal{L}$ be a countable, relational language, and let $\mathcal{L}_{ext}$ be an extended language of $\mathcal{L}$ with only unary functions. Let $\Gamma_{\mathcal{L}}$ be a finite permutation group on $\mathcal{L}$ , and therefore on $\mathcal{L}_{ext}$ . If $(\mathcal{K},\preceq)$ is a free amalgamation class of extended $\mathcal{L}_{ext}$ -structures, then $\mathcal{K}$ has $\Gamma_{\mathcal{L}}$ -EPPA.

Note that this theorem still applies to standard model-theoretic structures in relational languages, as in these languages, the notion of structures and an extended structure can be viewed identically. The novelty of extended structures is in the advent of functions which map points to sets.

3.2.2 1-local smooth classes

In this section, we will prove that 1-local (defined below) classes have a "Fraïssé-ification" to a class of extended structures, generalizing the argument in §6 of [EHN19]. We prove that 1-local smooth classes have $\leq$ -EPPA and that $\leq$ -EPPA is preserved in a number of merges of these classes.

Definition 3.11.

A smooth class $(K,\leq)$ which is closed under substructure is $1$ -local if

1.

$(K,\leq)$ has smooth intersections. From the property of smooth intersections, for any $A,B\in K$ with $A\subseteq B$ there is a unique smallest $C$ such that $A\subseteq C\leq B$ . We define $cl_{B}(A)=C$ .
2.

Whenever $A,C\subseteq B$ are such that if $A,C\leq B$ , then $A\cup C\leq B$ .

Notice the above properties give us a characterization of the closure relation defined above:

Proposition 3.12.

If $(K,\leq)$ is closed under substructure and has smooth intersections, then $(K,\leq)$ satisfies (2) in Definition 3.11 if and only if for all $A,B\in K$ with $A\subseteq B$ , $cl_{B}(A)=\bigcup_{a\in A}cl_{B}(\{a\})$ .

Proof:

$(\Rightarrow):$ Let $A\subseteq B\in K$ . First, by condition (2) in Definition 3.11, and by definition of $cl_{B}$ , $\bigcup_{a\in A}cl_{B}(\{a\})\leq B$ , and thus $cl_{B}(A)\subseteq\bigcup_{a\in A}cl_{B}(\{a\})$ . Moreover, by definition of $cl_{B}$ , $cl_{B}(\{a\})\subseteq cl_{B}(A)$ for all $a\in A$ .

$(\Leftarrow):$ Suppose $A,C\leq B$ . By assumption, we have that $cl_{B}(A\cup C)=\bigcup_{b\in A\cup C}cl_{B}(\{b\})$ . But, note that $\bigcup_{b\in A\cup C}cl_{B}(\{b\})\subseteq A\cup C$ . This follows from the fact that since $A\leq B$ , for every $b\in A$ , $cl_{B}(\{b\})=cl_{A}(\{b\})$ . The same is true of $C$ . Thus, $A\cup C\leq B$ .

We also immediately get:

Proposition 3.13.

If $(K_{1},\leq_{1})$ and $(K_{2},\leq_{2})$ are both 1-local, then $(K_{1}\circledast K_{2},\leq_{*})$ is 1-local.

Definition 3.14.

Let $(K,\leq)$ be a 1-local smooth class in the language $\mathcal{L}$ . Let $\Gamma_{\mathcal{L}}$ be a finite permutation group of $\mathcal{L}$ . Call $\Gamma_{\mathcal{L}}$ closure-preserving on $K$ if whenever $A\in K$ , $\gamma\in\Gamma_{\mathcal{L}}$ and $f$ is a partial $\gamma$ -permorphism of $A$ with domain $D$ and range $R$ such that $D,R\leq A$ , then for any $d\in D$ , $f[cl_{A}(\{d\})]=cl_{A}(\{f(d)\})$ .

Lemma 3.15.

For any 1-local smooth class $(K,\leq)$ in a relational language $\mathcal{L}$ , $\Gamma_{\mathcal{L}}=\{id\}$ is closure-preserving on $K$ .

Proof:

Suppose $A\in K$ and $f$ is a partial automorphism of $A$ with domain $D$ and range $R$ such that $D,R\leq A$ . Let $d\in D$ . Note that $cl_{D}(\{d\})=cl_{A}(\{d\})$ since $D\leq A$ . Now, $f[cl_{A}(\{d\})]\leq A$ since $cl_{A}(\{d\})\leq A$ and $f$ is an isomorphism. By definition of $cl_{A}$ , $cl_{A}(\{f(d)\})\subseteq f[cl_{A}(\{d\}]$ . Moreover, $f^{-1}[cl_{A}(\{f(d)\})]\leq A$ and by definition, as $d\in f^{-1}[cl_{A}(\{f(d)\})]$ , $cl_{A}(\{d\})\subseteq f^{-1}[cl_{A}(\{f(d)\})]$ . Thus, $f[cl_{A}(\{d\})]\subseteq cl_{A}(\{f(d)\})$ . Therefore, $f[cl_{A}(\{d\})]=cl_{A}(\{f(d)\})$ .

We now give a construction used to prove the main result of this section.

Construction 3.16.

Let $(K,\leq)$ be a 1-local, smooth class in a relational language $\mathcal{L}$ with dAP. Define $\mathcal{L}^{F}=\mathcal{L}\cup\{U\}\cup\{f_{m}:m\geq 1\}$ , where each $f_{m}$ is a unary function. We will consider extended $\mathcal{L}^{F}$ - structures such that $f_{k}$ is unary and outputs a set of size $k$ .

For each $A\in K$ , define the extended expansion $\mathcal{A}^{F}$ of $A$ so that $U_{\mathcal{A}^{F}}$ is the universe of $A$ , and for all $R\in\mathcal{L}$ , and $(a_{1},\dots,a_{n})\in U_{\mathcal{A}^{F}}$ ,

\mathcal{A}^{F}\models R(a_{1},\dots a_{n})\Leftrightarrow A\models R(a_{1},\dots,a_{n})

Moreover, for every $j\in\omega$ , $dom(f^{\mathcal{A}^{F}}_{j})=\{a\in U_{\mathcal{A}^{F}}:|cl_{A}(\{a\})|=j\}$ and for $a\in dom(f^{\mathcal{A}^{F}}_{j})$ , $f^{\mathcal{A}^{F}}_{j}(a)=cl_{A}(\{a\})$ . Define $\mathcal{K}^{F}:=\{\mathcal{A}^{F}:A\in K\}$ , and consider the class $(K^{F},\preceq)$ , where $\preceq$ is the relation defined in Definition 3.8.

Claim 3.17.

$\mathcal{A}^{F}\preceq\mathcal{B}^{F}\Leftrightarrow A\leq B$

Proof:

If $\mathcal{A}^{F}$ and $\mathcal{B}^{F}$ are in $\mathcal{K}^{F}$ such that $\mathcal{A}^{F}\preceq\mathcal{B}^{F}$ , then for $A=U_{\mathcal{A}^{F}}$ and $B=U_{\mathcal{B}^{F}}$ , we have $A\subseteq B$ as $\mathcal{L}$ -structures and $A,B\in K$ . Moreover, from the definitions of $\mathcal{A}^{F}$ and $\mathcal{B}^{F}$ ,

cl_{B}(A)=\bigcup_{a\in A}cl_{B}(\{a\})=\bigcup_{a\in A}f^{\mathcal{B}^{F}}_{|cl_{B}(\{a\})|}(a)=\bigcup_{a\in A}f^{\mathcal{A}^{F}}_{|cl_{A}(\{a\})|}(a)=\bigcup_{a\in A}cl_{A}(\{a\})=cl_{A}(A)=A

Thus, by definition, $A\leq B$ .

On the other hand, if $A,B\in K$ such that $A\leq B$ , then $U_{\mathcal{A}^{F}}\subseteq U_{\mathcal{B}^{F}}$ and $cl_{A}(C)=cl_{B}(C)$ for any $C\subseteq A$ . By definition, we get that $f_{k}^{\mathcal{A}^{F}}=f_{k}^{\mathcal{B}^{F}}$ for all $k\in\omega$ . Thus, $\mathcal{A}\preceq\mathcal{B}$ .

Claim 3.18.

$(\mathcal{K}^{F},\preceq)$ is a disjoint amalgamation class

Note that if $(K,\leq)$ has fAP, then the same proof below immediately shows $(K^{F},\preceq)$ is a free amalgamation class, as all functions are unary.

Proof:

Suppose that $\mathcal{C}\preceq\mathcal{A}^{F}$ where $\mathcal{A}^{F}\in\mathcal{K}^{F}$ . We must show there exists some $D\in K$ such that $\mathcal{C}=\mathcal{D}^{F}$ . Clearly, $U_{\mathcal{C}}$ is an $\mathcal{L}$ -substructure of $U_{\mathcal{A}^{F}}$ . Denote the $\mathcal{L}$ -structure $U_{\mathcal{C}}$ as $C$ . Let $A$ denote the element of $K$ corresponding to $\mathcal{A}^{F}$ . As $(K,\leq)$ is closed under substructure, $C\in K$ . By definition of $\preceq$ , for all $c\in C$ with $|cl_{A}(\{c\})|=k$ , $f_{k}^{\mathcal{A}^{F}}(c)=f_{k}^{\mathcal{C}}(c)=cl_{A}(\{c\})\subseteq C$ . This implies that $C\leq A$ , so $cl_{A}(\{c\})=cl_{C}(\{c\})$ . For any $n\neq k$ , $f_{n}^{\mathcal{A}^{F}}$ , and therefore $f_{n}^{\mathcal{C}}$ , is undefined on $a$ . By definition, we have that $\mathcal{C}=\mathcal{C}^{F}$ , the extended structure corresponding to $C$ .

We now show that $(K^{F},\preceq)$ has disjoint amalgamation. Suppose $\mathcal{A}^{F}\preceq\mathcal{B}^{F}$ and $\mathcal{A}^{F}\preceq\mathcal{C}^{F}$ with $U_{\mathcal{B}^{F}}\cap U_{\mathcal{C}^{F}}=U_{\mathcal{A}^{F}}$ . Then, by Claim 3.17, $A\leq B$ and $A\leq C$ . As $(K,\leq)$ has dAP, there is some $D\in K$ for which $A,B,C\leq D$ and $D$ is a disjoint amalgam of $C$ , $B$ over $A$ . By Claim 3.17, $\mathcal{A}^{F},\mathcal{B}^{F},\mathcal{C}^{F}\preceq\mathcal{D}^{F}$ , and $U_{\mathcal{D}^{F}}$ is indeed the amalgamation of $U_{\mathcal{B}^{F}}$ and $U_{\mathcal{C}^{F}}$ over $U_{\mathcal{A}^{F}}$ . Thus, $(\mathcal{K}^{F},\preceq)$ has the amalgamation property.

Construction 3.16 originated from ([EHN19]. [EHN21]). It is worth noting that any smooth class which satisfies (1) in Definition 3.11 also corresponds to an extended class using a construction similar to Construction 3.16, but the functions needed for that construction need not be unary. The main magic of 1-local classes is that their closure relations can be described point by point, and thus only require the addition of unary functions. The advantage of unary functions is that they preserve free amalgamation from the smooth class. This allow us to apply Theorem 3.10.

We now prove the following:

Proposition 3.19.

If $(K,\leq)$ is a $1$ -local class with dAP in the relational language $\mathcal{L}$ , then there is some extended amalgamation class $(\mathcal{K}^{F},\preceq)$ in an extended language $\mathcal{L}^{F}$ of $\mathcal{L}$ such that for any closure preserving permutation group $\Gamma_{\mathcal{L}}$ on $(K,\leq)$ , $(K,\leq)$ has $\Gamma_{\mathcal{L}}$ - $\leq$ -EPPA if and only if $(\mathcal{K}^{F},\preceq)$ has $\Gamma_{\mathcal{L}}$ -EPPA

Proof:

Let $(\mathcal{K}^{F},\preceq)$ be the extended smooth class corresponding to $(K,\leq)$ given by Construction 3.16. Assume $(K,\leq)$ has $\Gamma_{\mathcal{L}}$ - $\leq$ -EPPA. Note that $\Gamma_{\mathcal{L}}$ only permutes elements of $\mathcal{L}$ , so we may consider it to be a permutation group on $\mathcal{L}^{F}$ . We now prove that $(\mathcal{K}^{F},\preceq)$ has $\Gamma_{\mathcal{L}}$ -EPPA. Let $\mathcal{A}^{F}$ be in $(\mathcal{K}^{F},\preceq)$ and $\gamma_{1},\dots,\gamma_{n}\in\Gamma_{\mathcal{L}}$ . Suppose for $i\leq n$ , $f_{i}$ is an extended partial $\gamma_{i}$ -permorphism of $\mathcal{A}^{F}$ . We want to find some $\mathcal{B}^{F}\in\mathcal{K}^{F}$ such that for $i\leq n$ , there exists an extended $\gamma_{i}$ -permorphism $g_{i}$ of $\mathcal{B}^{F}$ such that $g_{i}\supset f_{i}$ .

We may consider each extended $\gamma_{i}$ -permorphism $f_{i}$ as a $\gamma_{i}$ -permorphism $f_{i}$ of $A$ in the language $\mathcal{L}$ , as $dom(f_{i}),range(f_{i})\leq A$ by the construction of $\mathcal{A}^{F}$ . As $(K,\leq)$ has $\Gamma_{\mathcal{L}}$ -EPPA, there is some $B\in K$ such that $A\leq B$ and for $i\leq n$ , there exists some $\gamma_{i}$ -permorphism $g_{i}$ of $B$ such that $g_{i}\supset\phi_{i}$ . By construction, $\mathcal{A}^{F}\preceq\mathcal{B}^{F}$ . We now show that each $g_{i}$ is in fact an extended $\gamma_{i}$ -permorphism of $\mathcal{B}^{F}$ .

As $g_{i}$ is a $\gamma_{i}$ -permorphism of $B$ , we need only check that $g_{i}$ preserves the functions of $\mathcal{B}^{F}$ . Let $f_{k}\in\mathcal{L}^{F}$ and suppose $a\in\mathcal{B}^{F}$ is defined on $f_{k}$ . Then, we have $g_{i}(f_{k}(a))=g_{i}(cl_{B}(\{a\}))$ . As $g_{i}$ is a $\gamma_{i}$ -permorphism and $\Gamma_{\mathcal{L}}$ is closure-preserving, $g_{i}(cl_{B}(\{a\}))=cl_{B}(\{g_{i}(a)\})=f_{k}(g_{i}(a))$ . This shows $g_{i}$ preserves the functions of $\mathcal{B}^{F}$ . Thus, $(\mathcal{K}^{F},\preceq)$ has $\Gamma_{\mathcal{L}}$ -EPPA.

The other direction follows similarly.

Example 3.20.

We now give examples of classes which are $1$ -local

1.

$(K_{1},\leq_{1})$ where $K_{1}$ is the set of all graphs in the language $\mathcal{L}_{1}:=\{E\}$ , and $A\leq_{1}B$ if and only if for all $b\in B-A$ , $\forall a\in A(\neg E(a,b))$ . This class is 1-local.
2.

$(K_{2},\leq_{2})$ where $K_{2}$ is the set of all graphs in the language $\mathcal{L}_{2}:=\{E\}$ , and $A\leq_{2}B$ if and only if for all $b\in B-A$ , $\forall a\in A(E(a,b))$ . This class is 1-local.
3.

$(K_{3},\leq_{3})$ where $K_{3}$ is the set of all graphs in the language $\mathcal{L}_{3}:=\{R\}$ , with $R$ 3-ary, and $A\leq_{3}B$ if and only if for all $b_{1}\in B-A$ , $\forall b_{2}\in B$ $\forall a_{1}\in A(\neg R(a_{1},b_{1},b_{2}))$ . This class is 1-local.
4.

Any merge of $1$ -local classes is $1$ -local.
5.

All Fraïssé classes are trivially $1$ -local.

Thus we can prove:

Proposition 3.21.

If a class $(K,\leq)$ is $1$ -local and has fAP, then $K$ has $\leq$ -EPPA.

Proof:

Putting together Lemma 3.15 and Proposition 3.19, $(K,\leq)$ has $\leq$ -EPPA if and only if $(\mathcal{K}^{F},\preceq)$ has EPPA. Since $(K,\leq)$ has fAP, then $(\mathcal{K}^{F},\preceq)$ will have free amalgamation as an extended amalgamation class. By Theorem 3.10, $(\mathcal{K}^{F},\preceq)$ has EPPA, and therefore, $(K,\leq)$ has $\leq$ -EPPA.

This, in particular, shows that merges of 1-local classes which have fAP will also have $\leq$ -EPPA. Let $(K_{LO},\subseteq)$ once again denote the Fraïssé class of all finite linear orders. We now use the theorem given by [EHN21] tailored to extended classes to prove the following:

Corollary 3.22.

If $(K,\leq)$ is 1-local with free amalgamation, then $(K\circledast K_{LO},\leq)$ has the Ramsey property.

Proof:

This follows by converting $(K,\leq)$ to $(\mathcal{K}^{F},\preceq)$ , which has fAP and therefore $(\mathcal{K}^{F}\circledast K_{LO},\preceq)$ has the Ramsey property by Theorem 1.3 of [EHN21]. It will then follow that $(K\circledast K_{LO},\leq)$ will also have the Ramsey property.

These notions of 1-local classes come as a generalization of the arguments given in ([EHN19], [EHN21], [HKN22]) that the smooth class of $k$ -orientations under successor closures has $\leq$ -EPPA. 1-local classes all seem to have a similar definition of the relation $\leq$ , which accounts for their closure relations depending on individual points.

Remark 3.23.

It is also possible to apply the arguments above to show that certain 1-local classes which do not have fAP still have $\leq$ -EPPA. In particular, the class defined in (2) of Example 3.20 has $\leq$ -EPPA, although it certainly does not have fAP. This is done by looking at complements of smooth classes. Let $\mathcal{L}$ be a relational language. For an $\mathcal{L}$ -structure $A$ , let $A^{\sim}$ denote the structure with the same universe as $A$ such that for every relation $R$ , and $\overline{a}\in A^{lg(R)}$ , $A\models R(\overline{a})\Leftrightarrow A^{\sim}\models\neg R(\overline{a})$ . For a smooth class $(K,\leq)$ , the complement of $(K,\leq)$ is the class $(K^{\sim},\leq_{\sim})$ such that $K^{\sim}=\{A^{\sim}:A\in K\}$ and $A^{\sim}\leq_{\sim}B^{\sim}\Leftrightarrow A\leq B$ . It is easy to see that $(K,\leq)$ is 1-local if and only if $(K^{\sim},\leq_{\sim})$ is 1-local. It is also immediate that $(K,\leq)$ has $\leq$ -EPPA if and only if $(K^{\sim},\leq_{\sim})$ has $\leq_{\sim}$ -EPPA. Moreover, if $(K_{1},\leq_{1})$ is a smooth class, then $(K\circledast K_{1},\leq_{*})$ has $\leq_{*}$ -EPPA if and only if the merged class $(K^{\sim}\circledast K_{1},\leq_{*})$ has $\leq_{*}$ -EPPA.

3.2.3 Classes without EPPA via 1-local Smooth Classes

Studying smooth classes in the context of EPPA properties can also give some results for EPPA properties of true Fraïssé classes.

Definition 3.24.

Let $\mathcal{L}$ be a countable, relational language. For $F$ a family of finite $\mathcal{L}$ -structures, define $Forb_{m}(F)$ as the class of all $\mathcal{L}$ -structures $A$ so that there does not exist a $B\in F$ and a 1-1 mapping $f:B\rightarrow A$ such that for all $R\in\mathcal{L}$ , $B\models R(b_{1},\dots,b_{n})\Rightarrow A\models R(f(b_{1}),\dots,f(b_{n}))$ . Define $Forb_{e}(F)$ as the class of all $\mathcal{L}$ -structures $A$ so that there does not exist a $B\in F$ and an $\mathcal{L}$ -embedding $f:B\rightarrow A$ .

We say a $\mathcal{L}$ -structure is irreducible if it cannot be written as a free amalgamation of two of its proper subsets. Let $Forb_{he}(F)$ be the class of all $\mathcal{L}$ -structures $A$ so that there does not exist a $B\in F$ and a mapping $f:B\rightarrow A$ such that $f$ is injective on irreducible subsets $B^{\prime}\subseteq B$ and for all $R\in\mathcal{L}$ , $B\models R(b_{1},\dots,b_{n})\Rightarrow A\models R(f(b_{1}),\dots,f(b_{n}))$ .

It is known by [HO03] that if $Forb_{e}(F)$ is a Fraïssé class with fAP, then $Forb_{e}(F)$ has EPPA.

Suppose that $F$ is finite and for every $A\in Forb_{he}(F)$ , there is some infinite $\mathcal{L}$ -structure $M$ such that $A\subseteq M$ and every partial automorphism of $A$ extends to an automorphism of M, and, moreover, for every $B\subseteq M$ , $B\in Forb_{he}(F)$ . By [HKN22], $Forb_{he}(F)$ has EPPA.

Using examples of smooth classes, we can give a proof using a 1-local class that the assumptions above cannot be dropped completely.

Proposition 3.25.

There exists a finite, relational language $\mathcal{L}$ and a finite family $F$ of $\mathcal{L}$ -structures for which $Forb_{e}(F)$ , $Forb_{he}(F)$ , and $Forb_{m}(F)$ do not have EPPA.

Proof:

Let $\mathcal{L}=\{E\}$ , $E$ a binary relation. Let $K$ be the class of all finite $\mathcal{L}$ -structures. Define the smooth class $(K,\leq)$ as $A\leq B$ if and only if $\forall b\in B-A\forall a\in A(\neg E(a,b))$ .

Fix $A\in K$ such that $A$ contains two points $a_{1},a_{2}$ so that $A\models E(a_{1},a_{2})$ and a point $a_{3}$ which is not $E$ -connected to any other point in $A$ , including itself.
Observation: Consider the partial automorphism $f:\{a_{1}\}\rightarrow\{a_{3}\}$ . Suppose there were some $B\in K$ with $A\leq B$ for which there exists some automorphism $g:B\rightarrow B$ extending $f$ . As $E(a_{1},a_{2})$ holds, but $E(a_{3},a)$ fails for every $a\in A$ , there must be some $b\in B-A$ such that $B\models E(a_{3},b)$ . But this contradicts that $A\leq B$ . Thus, there is no $B\in K$ with $A\leq B$ for which there is an automorphism $g$ of $B$ extending $f$ .

Let $\mathcal{L}_{R}=\{R\}$ and $\mathcal{L}^{\#}=\mathcal{L}\cup\mathcal{L}_{R}$ , where $R$ is a binary relation. Extend $A$ to a $\mathcal{L}^{\#}$ -structure $A^{\#}$ by stipulating that $R$ holds on every 2-tuple of $A$ . Let $K_{R}$ be the class of all finite $\mathcal{L}_{R}$ -structures, and let $K^{\#}=K\circledast K_{R}$ . Define

F^{\#}:=\{C\in K^{\#}:C\text{ is a one-point extension of $A^{\#}$ so that }A^{\#}|_{\mathcal{L}}\not\leq C|_{\mathcal{L}}\}

We prove that $Forb_{he}(F^{\#})$ does not have EPPA. The results for $Forb_{m}(F^{\#})$ and $Forb_{e}(F^{\#})$ follow by a similar argument.

Suppose $Forb_{he}(F^{\#})$ did have EPPA. Note that $A^{\#}\in Forb_{he}(F^{\#})$ , as all $C\in F^{\#}$ are irreducible by definition of $\leq$ . Then, there would be some $B^{\#}\in Forb_{he}(F^{\#})$ such that for any partial $\mathcal{L}^{\#}$ -automorphisms $f_{1},\dots,f_{n}$ of $A^{\#}$ (Note: Here, the domain and range of these partial automorphisms are unrestricted), there exist $g_{1},\dots,g_{n}\in Aut(B^{\#})$ so that $g_{i}\supset f_{i}$ for all $i$ .

Notice that we necessarily have that $A=A^{\#}|_{\mathcal{L}}\leq B^{\#}|_{\mathcal{L}}$ by the definition of $\leq$ and $F^{\#}$ . Moreover, every partial automorphism of $A$ is a partial automorphism of $A^{\#}$ . Hence, for $B=B^{\#}|_{\mathcal{L}}$ , $A\leq B$ and $B$ is an EPPA witness for $A$ in the language $\mathcal{L}$ . This is a contradiction to the observation.

In general, smooth classes give rise to a large variety of classes which cannot have EPPA in the Fraïssé sense.

Fact 3.26.

For a smooth class $(K,\leq)$ with a generic $M$ , for $A\in K$ , let $K_{A}$ be the class of all $B\in K$ such that $A\leq B$ . If $K_{A}$ has EPPA, then every partial automorphism of $A$ (where the domain and range are simply subsets of $A$ ) extends to an automorphism of $M$ . If for every $A\in K$ , $K_{A}$ has EPPA, then $M$ is the Fraïssé limit of $(K^{+},\subseteq)$ where $K^{+}$ is the closure of $K$ under substructure.

Thus, if the generic $M$ of $(K,\leq)$ does not extend every partial automorphism of $A\in K$ , then $K_{A}$ does not have EPPA, and moreover, no subclass of $K_{A}$ has EPPA.

3.3 Merging with 1-local classes

We are now interested in merging classes with EPPA and investigating the resulting merged class. We first observe the following easy fact:

Fact 3.27.

Suppose for every $n\in\omega$ , $(K_{1},\leq_{1})$ contains a structure $A\in K_{1}$ for which for all $R\in\mathcal{L}$ , $R$ holds on every tuple of $A$ , and for every $A_{0}\subseteq A$ , $A_{0}\leq_{1}A$ . If $(K_{2},\leq_{2})$ is another smooth class such that $(K_{1}\circledast K_{2},\leq_{*})$ has $\leq_{*}$ -EPPA, then $(K_{2},\leq_{2})$ has $\leq_{2}$ -EPPA.

The Fraïssé class of equivalence relations under substructure, $(K_{E},\subseteq)$ , for example, would be an example of a $(K_{1},\leq_{1})$ as in the above fact. Merges of such classes cannot have any "surprise" EPPA results. For example, any merge $(K^{*},\leq_{*})$ of $(K_{E},\subseteq)$ with a class $(K_{2},\leq_{2})$ which does not have $\leq_{2}$ -EPPA will not have $\leq_{*}$ -EPPA.

We now turn to prove some results about classes we know have an EPPA property.

Notation: For every $n\in\omega$ , call $E_{n}$ an $n$ -tuple equivalence relation if $E_{n}$ is a $2n$ -ary relation which is transitive, symmetric, irreflexive on $n$ -tuples, and whenever $E_{n}(\overline{a},\overline{b})$ holds on $n$ tuples $\overline{a}$ and $\overline{b}$ , then for any permutation $\overline{b}_{\sigma}$ of the tuple $\overline{b}$ , $E(\overline{a},\overline{b}_{\sigma})$ holds. Let $(K_{E_{n}},\subseteq)$ denote the class of finite structures with an $n$ -tuple equivalence relation in the language $\mathcal{L}_{E_{n}}=\{E_{n}\}$ . Set $\mathcal{L}_{E_{\omega}}=\bigcup\{\mathcal{L}_{E_{n}}:n\in\omega\}$ .

We have the following result of [Iva15]:

Theorem 3.28.

The Fraïssé class $K_{E_{\omega}}:=\circledast_{i\in\omega}K_{E_{n}}$ in the language $\mathcal{L}_{E_{\omega}}$ has EPPA.

The fact that the class $K_{E_{\omega}}$ has EPPA is interestingly not immediately covered by basic EPPA results that use free amalgamation or forbidden classes. The proof of Theorem 3.28 proceeds by changing the language, extending to a merge of classes, proving the merge has a permorphism EPPA property, then proving the restriction back to $K_{E_{\omega}}$ has EPPA. It is reminiscent of the operation we applied to $1$ -local smooth classes to attain a class of extended structures, though here the goal is to gain a class with free amalgamation. At its core, the proof boils down to an application of Theorem 3.10. Using this, we prove a generalization:

Theorem 3.29.

Let $(K_{E_{\omega}},\subseteq)$ be the Fraïssé class defined above. Let $(K_{2},\leq_{2})$ be any $1$ -local smooth class with fAP in a countable relational language. Then, the merge $K_{0}:=K_{E_{\omega}}\circledast K_{2}$ in the language $\mathcal{L}_{0}:=\mathcal{L}_{E_{\omega}}\cup\mathcal{L}_{2}$ has $\leq_{*}$ -EPPA.

Proof:

Note that, in this merge, $A\leq_{*}B\Leftrightarrow A\leq_{2}B\;\&\;A|_{\mathcal{L}_{E_{\omega}}}\subseteq B|_{\mathcal{L}_{E_{\omega}}}$ .

Define a new language $\mathcal{L}^{\#}=\{P_{n,i}:i,n\in\omega\}$ where $P_{n,i}$ is an $n$ -ary relation, and let $K^{\#}$ be all $\mathcal{L}^{\#}$ structures such that $P_{n,i}\cap P_{n,j}=\emptyset$ whenever $i\neq j$ ; $P_{n,i}(a_{1},\dots,a_{n})\Leftrightarrow P_{n,i}(a_{\sigma(1)},\dots,a_{\sigma(n)})$ for any $\sigma\in Sym(n)$ ; and every $P_{n,i}$ is an irreflexive relation (i.e., $P_{n,i}$ does not hold on a tuple with repeated elements).

Now, let $K^{*}=K^{\#}\circledast K_{2}$ , and let $\mathcal{L}^{*}=\mathcal{L}^{\#}\cup\mathcal{L}_{2}$ . Let $\mathcal{L}^{\prime}$ be any set such that $\mathcal{L}_{2}\subseteq\mathcal{L}^{\prime}\subseteq\mathcal{L}^{*}$ and $\mathcal{L}^{\prime}-\mathcal{L}_{2}$ is finite. Define $K(\mathcal{L}^{\prime})$ to be all $\mathcal{L}^{\prime}$ structures which are in $K^{*}$ . Let $\Gamma_{\mathcal{L}^{\prime}}$ be all arity-preserving permutations of the language $\mathcal{L}^{\prime}-\mathcal{L}_{2}$ . The first observation we make is that $K(\mathcal{L}^{\prime})$ has free amalgamation with respect to $\leq_{*}$ . Since every $\gamma\in\Gamma_{\mathcal{L}^{\prime}}$ fixes $\mathcal{L}_{2}$ , by Theorem 3.10 and Theorem 3.19, $K(\mathcal{L}^{\prime})$ has $\Gamma_{\mathcal{L}^{\prime}}$ - $\leq_{*}$ -EPPA.

We now choose any $A_{0}\in K_{0}$ and any partial automorphisms $f_{1},\dots,f_{n}$ of $A_{0}$ for which $dom(f_{i})$ and $range(f_{i})\leq_{*}A_{0}$ for $i\leq n$ . There is a maximum $q$ for which $E_{q}$ is defined on $A_{0}$ . Thus, for $m\leq q$ we can enumerate all the classes of each $E_{m}$ which is satisfied on $A_{0}$ . Suppose for each $m\leq q$ , $E_{m}$ has $j_{m}$ many classes in $A$ . We will then set $\mathcal{L}^{\prime}:=\mathcal{L}_{2}\cup\{P_{m,r}:m\leq q,\;r\leq j_{m}\}$ .

On the universe of $A_{0}$ , we define an $\mathcal{L}^{\prime}$ -structure $A$ so that $A\models P_{k,i}(a_{1},\dots,a_{k})$ if and only if $(a_{1},\dots,a_{k})$ is in the $i$ th equivalence class of $E_{k}$ in $A_{0}$ . We also require that $A|_{\mathcal{L}_{2}}$ is precisely $A_{0}|_{\mathcal{L}_{2}}$ . Notice that for each $i$ , $f_{i}$ is a $\gamma$ -permorphism of $A$ for some $\gamma\in\Gamma_{\mathcal{L}^{\prime}}$ and permutes only symbols in $\mathcal{L}^{\prime}-\mathcal{L}_{2}$ .

We automatically get that $A\in K(\mathcal{L}^{\prime})$ . $A$ has a $\Gamma_{\mathcal{L}^{\prime}}$ - $\leq_{*}$ - EPPA witness $B\in K(\mathcal{L}^{\prime})$ such that $A\leq_{*}B$ and there exist $g_{1},\dots,g_{n}$ permorphisms of $B$ such that $g_{i}\supset f_{i}$ . For each $\ell\leq|B|$ , we can find some $r\in\omega$ such that $P_{\ell,r}$ is an $\mathcal{L}^{*}$ - relation not yet appearing in $\mathcal{L}^{\prime}$ . We will expand $B$ to a $\mathcal{L}^{\prime}\cup\{P_{\ell,r}:\ell\leq|B|\}$ structure as follows:

For any irreflexive tuple $(b_{1},\dots,b_{\ell})$ of $B$ , if $(b_{1},\dots,b_{\ell})$ does not hold on any relation in $\mathcal{L}^{\prime}$ , then we require that $P_{\ell,r}(b_{1},\dots,b_{\ell})$ holds in the expansion of $B$ , call it $B^{\prime}$ . Suppose $g$ is a permorphism of $B$ . Notice that because all tuples which did not belong to a relation in $B$ now belong to the same relation in $B^{\prime}$ , and since, for each $\ell$ and $r$ , $g$ must fix $P_{\ell,r}$ , $g$ must be a permorphism of $B^{\prime}$ as well.

We will define an $\mathcal{L}_{0}$ -structure $B_{0}$ with the same universe as $B^{\prime}$ such that for all $i$ , and any $i$ -ary tuples $\overline{a}$ , $\overline{b}$ from $B^{\prime}$ , $B_{0}\models E_{i}(\overline{a},\overline{b})$ if and only if $B^{\prime}\models P_{i,j}(\overline{a})\land P_{i,j}(\overline{b})$ for some $j$ . Moreover, we set $B_{0}|_{\mathcal{L}_{2}}=B|_{\mathcal{L}_{2}}$ . As every tuple of $B_{0}$ satisfies an appropriate equivalence relation, $B_{0}\in K_{0}$ .

Because we have preserved the $\mathcal{L}_{2}$ -structure in our construction, $A_{0}\leq_{2}B_{0}$ and $A_{0}\subseteq B_{0}$ with respect to the language $\mathcal{L}_{E_{\omega}}$ . Thus, $A_{0}\leq_{*}B_{0}$ . Now, any permorphism $g_{i}$ of $B^{\prime}$ is clearly an automorphism of $B_{0}$ , as

B_{0}\models E_{n}(g_{i}(\overline{b}),g_{i}(\overline{a}))\Leftrightarrow\exists t\;B^{\prime}\models P_{n,t}(g_{i}(\overline{a}))\land P_{n,t}(g_{i}(\overline{b}))\Leftrightarrow\exists w\;B^{\prime}\models P_{n,w}(\overline{a})\land P_{n,w}(\overline{b})\Leftrightarrow B_{0}\models E_{n}(\overline{a},\overline{b})

And, moreover, it is easy to see that $g_{i}\supseteq f_{i}$ , the original partial automorphisms of $A_{0}$ . Thus, $B_{0}$ is a $\leq_{*}$ -EPPA witness for $A_{0}$ .

Using the argument in Remark 3.23

Corollary 3.30.

Let $(K_{E_{\omega}},\subseteq)$ be the Fraïssé class defined above. Suppose $(K_{2},\leq_{2})$ is a (possibly infinite) merge of 1-local classes with fAP and/or their complements, then $(K_{E_{\omega}}\circledast K_{2},\leq_{*})$ has $\leq_{*}$ -EPPA.

We can generalize the proof above slightly:

Definition 3.31.

For $K_{E_{\omega}}$ defined as above, call a smooth class $(K_{E_{\omega}},\leq_{1})$ separably 1-local if there exists some partition $\omega=I\sqcup J$ where for all $A,B\in\circledast_{j\in J}K_{E_{j}}$ , $A\leq_{1}B\Leftrightarrow A\subseteq B$ , and on the class $\circledast_{i\in I}K_{E_{i}}$ , $\leq_{1}$ is a 1-local relation.

We can apply the argument in the proof above to a separably 1-local class $(K_{E_{\omega}},\leq_{1})$ which has fAP by cutting out $\circledast_{i\in I}K_{E_{i}}$ and merging it in with a 1-local smooth class $(K_{2},\leq_{2})$ to get

Proposition 3.32.

For a smooth class separably 1-local class $(K_{E_{\omega}},\leq_{1})$ with fAP and any 1-local smooth class $(K_{2},\leq_{2})$ with fAP, $(K_{E_{\omega}}\circledast K_{2},\leq_{*})$ has $\leq_{*}$ -EPPA.

An easy example of a separably 1-local class $(K_{E_{\omega}},\leq_{1})$ is to define for $A,B\in K_{E_{\omega}}$

A\leq_{1}B\Leftrightarrow\text{for $i>1$, }A|_{\mathcal{L}_{E_{i}}}\subseteq B|_{\mathcal{L}_{E_{i}}}\;\&\;\forall b\in B-A\;\forall a\in A(\neg E_{1}(a,b))

References

[Bod12] Manuel Bodirsky “New Ramsey Classes from Old”, 2012 arXiv: https://arxiv.org/abs/1204.3258
[BS96] John T. Baldwin and Niandong Shi “Stable generic structures” In Annals of Pure and Applied Logic 79.1, 1996, pp. 1–35 DOI: https://doi.org/10.1016/0168-0072(95)00027-5
[EHN19] David M. Evans, Jan Hubička and Jaroslav Nešetřil “Automorphism groups and Ramsey properties of sparse graphs” In Proceedings of the London Mathematical Society 119.2 Wiley, 2019, pp. 515–546 DOI: 10.1112/plms.12238
[EHN21] David M. Evans, Jan Hubička and Jaroslav Nešetřil “Ramsey properties and extending partial automorphisms for classes of finite structures” In Fundamenta Mathematicae 253.2 Institute of Mathematics, Polish Academy of Sciences, 2021, pp. 121–153 DOI: 10.4064/fm560-8-2020
[GKP16] Zaniar Ghadernezhad, Hamed Khalilian and Massoud Pourmahdian “Automorphism Groups of Generic Structures: Extreme Amenability and Amenability”, 2016 arXiv: https://arxiv.org/abs/1508.04628
[Gun18] Danul K. Gunatilleka “The theories of Baldwin-Shi hypergraphs and their atomic models”, 2018 arXiv: https://arxiv.org/abs/1803.01831
[Her95] Bernhard Herwig “Extending partial isomorphisms on finite structures” In Combinatorica 15, 1995, pp. 365–371 URL: https://api.semanticscholar.org/CorpusID:13082360
[HKN22] Jan Hubička, Matěj Konečný and Jaroslav Nešetřil “All those EPPA classes (Strengthenings of the Herwig-Lascar theorem)”, 2022 arXiv: https://arxiv.org/abs/1902.03855
[HO03] Ian Hodkinson and Martin Otto “Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures” In The Bulletin of Symbolic Logic 9.3 [Association for Symbolic Logic, Cambridge University Press], 2003, pp. 387–405 URL: http://www.jstor.org/stable/3109885
[Iva15] Aleksander Ivanov “An $\omega$ -categorical structure with amenable automorphism group” In Mathematical Logic Quarterly 61.4-5, 2015, pp. 307–314 DOI: https://doi.org/10.1002/malq.201400036
[KL92] D. W. Kueker and M. C. Laskowski “On generic structures” In Notre Dame Journal of Formal Logic 33.2 Duke University Press, 1992, pp. 175 –183 DOI: 10.1305/ndjfl/1093636094
[KPT04] A. S. Kechris, V. G. Pestov and S. Todorcevic “Fraisse Limits, Ramsey Theory, and Topological Dynamics of Automorphism Groups”, 2004 arXiv: https://arxiv.org/abs/math/0305241
[KR06] Alexander S. Kechris and Christian Rosendal “Turbulence, amalgamation and generic automorphisms of homogeneous structures”, 2006 arXiv: https://arxiv.org/abs/math/0409567
[Las07] Michael Laskowski “A simpler axiomatization of the Shelah-Spencer almost sure theory” In Israel Journal of Mathematics 161, 2007, pp. 157–186 DOI: 10.1007/s11856-007-0077-8
[NR83] Jaroslav Nešetřil and Vojtěch Rödl “Ramsey classes of set systems” In Journal of Combinatorial Theory, Series A 34.2, 1983, pp. 183–201 DOI: https://doi.org/10.1016/0097-3165(83)90055-9

Merges of Smooth Classes and Their Properties

Abstract

1 Introduction

2 Merging Smooth Classes

2.1 Background

2.1.1 Smooth Classes

Definition 2.1.

Example 2.2.

Definition 2.3.

Definition 2.4.

Proposition 2.5.

2.2 Merges

2.2.1 The Set-Up

Definition 2.6.

Definition 2.7.

Remark 2.8.

Theorem 2.9.

Proof:

Remark 2.10.

2.3 Properties of Merges

2.3.1 Preserving Generics in the Merge

Proposition 2.11.

Proof:

Theorem 2.12.

Proof:

Theorem 2.13.

Corollary 2.14.

Corollary 2.15.

Proof:

Corollary 2.16.

Corollary 2.17.

Corollary 2.18.

2.3.2 Atomic Generics and Merges

Proposition 2.19.

Proof:

Corollary 2.20.

Proof:

Proposition 2.21.

Proof:

2.3.3 Saturated generics and merges

Definition 2.22.

Theorem 2.23.

Proof:

Definition 2.24.

Example 2.25.

Theorem 2.26.

Proof:

3 Structural Ramsey Theory, EPPA Classes, and Merges

3.1 Background & Motivation

Definition 3.1.

Theorem 3.2.

Definition 3.3.

Proposition 3.4.

Definition 3.5.

Definition 3.6.

3.2 Smooth Classes with ≤\leq-EPPA

3.2.1 Extended Structures

Definition 3.7.

Definition 3.8.

Definition 3.9.

Theorem 3.10.

3.2.2 1-local smooth classes

Definition 3.11.

Proposition 3.12.

Proof:

Proposition 3.13.

Definition 3.14.

Lemma 3.15.

Proof:

Construction 3.16.

Claim 3.17.

Proof:

Claim 3.18.

Proof:

Proposition 3.19.

Proof:

Example 3.20.

Proposition 3.21.

Proof:

Corollary 3.22.

3.2 Smooth Classes with $\leq$ -EPPA