2 Fraïssé limits for metric structures

Ben Yaacov’s theory [Reference Urysohn19] concerns metric structures: these are metric spaces with collections of relations (which in continuous logic are real-valued functions of tuples of elements) and functions (which take tuples of elements to other elements). Here we will use Ben Yaacov’s theory only for relational metric structures, which are metric structures having no functions, and consequently no constants. This restriction has the advantage that finite structures are precisely the same as finitely generated structures.

The following corresponds to [Reference Urysohn19, Definition 3.1].

An embedding of $\mathcal {L}$ -structures $\phi \colon \mathfrak {A} \rightarrow \mathfrak {B}$ is a map $\phi \colon A \rightarrow B$ such that for each n-ary predicate symbol $R \in \mathcal {L}$ and all $\bar {a} \in A^n$

$$ \begin{align*} R^{\mathfrak{B}}(\phi(\bar{a})) = R^{\mathfrak{A}}(\bar{a}). \end{align*} $$

Note that since d is one of the predicate symbols, embeddings are always isometric. We define $\mathfrak {A}$ to be a substructure of $\mathfrak {B}$ if there is an embedding $\phi \colon \mathfrak {A} \rightarrow \mathfrak {B}$ . An isomorphism is a surjective embedding. An automorphism is an isomorphism from a structure to itself.

A partial isomorphism $\phi \colon \mathfrak {A} \dashrightarrow \mathfrak {B}$ is an embedding $\phi \colon A_0 \rightarrow B$ where $A _0 \subseteq A$ . We say that such a partial isomorphism is finite if its domain $A_0$ is finite.

Corresponding to [Reference Urysohn19, Definition 3.3], we say a separable structure $\mathfrak {M}$ is approximately ultrahomogeneous if every finite partial isomorphism $\phi \colon \mathfrak {M} \dashrightarrow \mathfrak {M}$ is arbitrarily close to the restriction of an automorphism of $\mathfrak {M}$ : for every $\epsilon>0$ , there is an automorphism f of $\mathfrak {M}$ such that $d(\phi a, f a) < \epsilon $ for all $a \in \mathrm {dom} \phi $ .

We say a separable structure $\mathfrak {M}$ is ultrahomogeneous if every finite partial isomorphism $\phi \colon \mathfrak {M} \dashrightarrow \mathfrak {M}$ extends to an automorphism.

Following [Reference Urysohn19, Definition 3.5], we have the following definitions.

Note that for the relational structures we consider here, AP implies NAP.

A key part of Ben Yaacov’s framework is studying the space of tuples of elements from metric structures as a metric space itself; these are called the enumerated structures. The metric he defines on the enumerated structures is analogous to the Gromov–Hausdorff distance between compact metric spaces.

So, $\bar {a} \in \mathcal {K}_n$ means that there is some structure $\mathfrak {A}$ with domain A such that $\bar {a} \in A^n$ . The tuple $\bar {a}$ is not a structure in $\mathcal {K}$ itself, because there may be repeated entries, and order is relevant. However, in a natural way, for each k-ary predicate symbol R and each k-length sub-tuple of $\bar {a}$ , we can apply R to that sub-tuple of $\bar {a}$ using the interpretation of R in $\mathcal {K}$ . Similarly, we can talk of embedding the tuples in $\mathcal {K}_n$ in structures in $\mathcal {K}$ . This is any map that takes the entries of $\bar {a} \in \mathcal {K}_n$ and maps them into a structure $\mathcal {K}$ while preserving the values of all the relations.

Informally, for given enumerated structures $\bar {a}$ and $\bar {b}$ in $\mathcal {K}_n$ we consider embedding them simultaneously in a common structure in $\mathcal {K}$ . We take the maximum distance in between corresponding $a_i$ and $b_i$ in the embedding for all i. Then we take the infimum of this quantity over all such embeddings to get $d_{\mathcal {K}}(\bar {a}, \bar {b})$ .

Ben Yaacov makes the following observation as a comment, citing his Lemma 3.8.

Proof Use JEP to show that $d_{\mathcal {K}}(\bar {a}, \bar {b})$ is well-defined and non-negative for all size-n structures $\bar {a}, \bar {b}$ . Symmetry is straightforward, as is $d_{\mathcal {K}}(\bar {a}, \bar {a})=0$ . For the triangle inequality, consider enumerated structures $\bar {a}, \bar {b}, \bar {c}$ . Let $\epsilon>0$ . Let $(\bar {a}', \bar {b}')$ be a joint embedding of $\bar {a}$ and $\bar {b}$ so that $\max _i d(\bar {a}_i', \bar {b}_i') \leq d_{\mathcal {K}}(\bar {a}, \bar {b}) + \epsilon /3$ , and likewise for $(\bar {b}'', \bar {c}'')$ so that $\max _i d(\bar {b}_i'', \bar {c}_i'') \leq d_{\mathcal {K}}(\bar {b}, \bar {c}) + \epsilon /3$ . Use NAP to get an amalgamation $(\bar {a}', \bar {b}', \bar {b}'', \bar {c}'')$ where $\max _i d(\bar {b}', \bar {b}'') \leq \epsilon /3$ , but distances between $\bar {a}'$ and $\bar {b}'$ , and between $\bar {b}''$ and $\bar {c}''$ are preserved. Then for all i

$$ \begin{align*} d(a_i',c_i'') \leq d(a_i',b_i') + d(b_i',b_i'') + d(b_i'',c_i'') \leq d_{\mathcal{K}}(a_i,b_i) + d_{\mathcal{K}}(b_i,c_i) + \epsilon \end{align*} $$

and so, taking the maximum over all i and letting $\epsilon $ go to zero gives $d_{\mathcal {K}}(a_i,c_i) \leq d_{\mathcal {K}}(a_i, b_i) + d_{\mathcal {K}}(b_i,c_i)$ .⊣

Our next two definitions follow [Reference Urysohn19, Definition 3.12]:

Our Def. 7 differs from Ben Yaacov’s in that we use AP and not NAP, because we want to obtain ultrahomogeneous limits and not just approximately ultrahomogeneous limits (though we will require another, stronger condition).

Ben Yaacov does not define the extension properties explicitly, but they are implicit in his Corollary 3.20. We define them here and use them as an alternative definition of a limit of a Fraïssé class.

In the following our approximate limits correspond to Ben Yaacov’s limits (his Def. 3.15).

Corresponding to Ben Yaacov’s Lemma 3.17, Theorem 3.19, and Theorem 3.21 we have the following results.

3 Approximate versus exact Fraïssé limits

Here we show that if the $\mathcal {K}$ -structures satisfy a property we call bAP (for “bounded Amalgamation Property”) then approximate Fraïssé limits are in fact exact Fraïssé limits. Recall from Definition 3 that for a class $\mathcal {K}$ of finite $\mathcal {L}$ -structures $\mathcal {K}_n$ is the class of enumerated $\mathcal {K}$ -structures of length n.

There is another way to define the distance between two enumerated relational structures that does not appear to have an analogue in Ben Yaacov’s paper. We define

(1) $$ \begin{align} d_{\infty} (\bar{a}, \bar{b}) = \max_{m \leq n} \max_{X \subseteq \{1,\ldots, n\}, |X|=m, R {\mbox{ arity }} m} | R( \bar{a}_X) - R( \bar{b}_X) |, \end{align} $$

where we include the metric d as a binary predicate. For each m, $1 \leq m \leq n$ , we look at all predicates of arity m. We then look at all subsets of $\bar {a}$ of size m and the corresponding subset of $\bar {b}$ and look at the difference between the predicates on those subsets. We take the $\max $ of the difference over all such m, predicates R, and index sets X. Unlike with $d_{\mathcal {K}}$ , $d_{\infty }$ does make use of any common embeddings of $\bar {a}$ and $\bar {b}$ into another metric structure. $d_{\infty }$ can be thought of as a distance obtained by using the predicates to map enumerated structures into $\ell ^k_{\infty }$ for some k. We will establish the Lipschitz equivalence of $d_{\mathcal {K}}$ and $d_{\infty }$ for given structures and then use this to prove statements about the space $(\mathcal {K}_n,d_{\mathcal {K}})$ .

Definition 13. We say that $\mathcal {K}$ satisfies bAP(the bounded Amalgamation Property) if there is a constant c depending only on n such that if $(\bar {a}, w)$ and $(\bar {a},z)$ are two enumerated structures in $\mathcal {K}_n$ with common substructure $\bar {a}$ , then there is an amalgamation $B=(\bar {a}, w, z)$ in $\mathcal {K}_{n+1}$ such that

$$ \begin{align*} d_B(w,z) \leq c \, d_{\infty}((\bar{a}, w), (\bar{a}, z)). \end{align*} $$

The idea behind bAP is to strengthen AP so that we have some control on how far apart the non-common points are in the amalgamated space. So if every predicate R takes almost the same value on corresponding subsets of $(\bar {a} ,w)$ and $(\bar {a},z)$ , then w and z are very close to each other in the amalgamation.

Note that bAP implies AP. To see this, observe that (forgetting the metric bound) this is a one-point amalgamation result for enumerated structures of the same length. By taking repeated elements if necessary, this is a one-point amalgamation result for finite structures. An induction argument gives the general amalgamation result.

The next result follows a result for metric spaces originally due to Urysohn; see [Reference Hallbäck19, Theorem 3.4] or [Reference Deza and Laurent9, Theorem 1.2.7]. (We proved a similar result, but in less generality, in [Reference Bryant and Dress4, Lemma 17].) Recall Definition 8 where definitions of approximate and exact extension properties are given.

Proof Let $\bar {a}$ be an enumerated structure of length n with elements taken from $\mathcal {M}$ . Let z be a point such that $(\bar {a},z) \in \mathcal {K}$ with $\bar {a}$ embedded in $(\bar {a}, z)$ . It suffices to show that there is a sequence $w_0, w_1, \ldots $ in $\mathfrak M$ such that for all p,

(2) $$ \begin{align} d(w_p,w_{p+1}) \leq 3 \cdot 2^{-(p+1)} \text{ and } d_{\infty}((\bar{a}, z),(\bar{a}, w_p)) \leq 2^{-p}. \end{align} $$

Because $\mathfrak M$ is complete, the first part of (2) shows that $\{w_p\}$ has a limit w. The second part of (2) shows that $(\bar {a}, w)$ is isomorphic to $(\bar {a},z)$ , as required.

Using induction, we will construct the sequence $\{w_p\}$ satisfying conditions (2), along with structures $M_p=(\bar {a}, z, w_0, \ldots , w_p)$ which are extensions of both $(\bar {a},z)$ and $(\bar {a}, w_0, \ldots , w_p )$ . In particular, the points $\{ w_p \}$ and the structures $M_p$ will satisfy for all $p\geq 0$ :

1. I. $d_{\infty }((\bar {a}, z),(\bar {a}, w_p)) \leq 2^{-p}$ ,

2. II.

   1. (a) $M_p$ is an extension of $(\bar {a}, w_0, \ldots , w_p )$ ,

   2. (b) $M_p$ is an extension of $(\bar {a}, z)$ , and

   3. (c) $d(w_p,z) \leq 2^{-p}$ in $M_p$ .

First, we use the approximate extension property to get a $w_0 \in M$ such that

$$ \begin{align*}d_{\infty}( (\bar{a}, w_0),(\bar{a}, z)) \leq \min( c^{-1}, 1), \end{align*} $$

where c is the constant (depending on n) in bAP for $\mathcal {K}$ . So $w_0$ satisfies condition (I), for $p=0$ . Then using bAP, there is an amalgamation $M_0=(\bar {a}, z, w_0)$ in which $d(z, w_0) <1$ , thereby satisfying condition (II) for $p=0$ .

For the inductive step, suppose, for $p\geq 0$ , we have $w_0,\ldots ,w_{p}$ and a structure $M_p$ satisfying the conditions (I) and (II) above. We show there exist $w_{p+1}$ and $M_p$ , satisfying the corresponding conditions for $p+1$ .

Condition (II.a) allows us to use the approximate extension property to get $w_{p+1} \in M$ so that

$$ \begin{align*} d_{\infty}( (\bar{a}, w_0, \ldots w_{p+1}), (\bar{a}, w_0, \ldots, w_p, z)) \leq \min( c^{-1}, 1) 2^{-(p+1)}.\end{align*} $$

This immediately gives us $d_{\infty }( (\bar {a}, w_{p+1}), (\bar {a}, z)) \leq 2^{-(p+1)}$ which is condition (I) for $p+1$ . bAP allows us to amalgamate $(\bar {a}, w_0, \ldots w_{p+1})$ and $(\bar {a}, w_0, \ldots w_{p}, z)$ to get $(\bar {a}, w_0, \ldots w_{p+1}, z)$ . bAP also gives us $d(w_{p+1},z)\leq 2^{-(p+1)}$ in the amalgamation, and so we have all of condition (II) for $p+1$ . This concludes the inductive argument.

Now it remains to show that $d(\{w_p, w_{p+1}\}) \leq 3 \cdot 2^{-(p+1)}$ for each $p \geq 1$ . In the structure $(\bar {a}, w_0, \ldots , w_p, w_{p+1},z)$ we have both $d(w_p,z) \leq 2^{-p}$ and $d(w_{p+1},z) \leq 2^{-(p+1)}$ , so the triangle inequality gives the result.⊣

4 A universal ultrahomogeneous stochastic process

In this section we apply our extension of Ben Yaacov’s metric Fraïssé theory to stochastic processes. We show the existence of a unique universal ultrahomogeneous stochastic process with a separable index set taking values in a finite set. A key step will be showing how to view stochastic processes as metric structures.

We recall the definition and basic theory of stochastic processes. Let the state space S be a finite set and index set T be arbitrary. Let $(\Omega ,\mathcal {F},\mathbb {P})$ be a probability space. A stochastic process is an S-valued family of random variables $(X_t)_{t \in T}$ on $\Omega $ . It is customary to denote the random variable $X_t$ by $X(t)$ .

Every stochastic process has an associated family of finite-dimensional distributions. For every tuple $(t_1,\ldots ,t_k)$ of distinct elements, $t_i \in T$ and tuple $(s_1,\ldots ,s_k)$ , $s_i \in S$ we define

$$ \begin{align*} F_{t_1,\ldots,t_k}(s_1,\ldots,s_k) = \mathbb{P}(X(t_1)=s_1, \ldots, X(t_k)=s_k). \end{align*} $$

In order to simplify notation, in what follows we will denote tuples of values by using an overbar, so that $\bar {t}=(t_1,\ldots ,t_k)$ and $\bar {s}=(s_1,\ldots ,s_k)$ . For example, we would write the above definition as $F_{\bar {t}}(\bar {s}) = \mathbb {P}(X(\bar {t})=\bar {s})$ . For any stochastic process on T taking values in S, the finite-dimensional distributions satisfy, for any k-tuple of distinct values $\bar {t}$ and any k-tuple of states $\bar {s}$ :

1. 1. $ F_{\bar {t}} (\bar {s}) \in [0,1] $ .

2. 2. $ \sum _{\bar {s} \in S^k} F_{\bar {t}} (\bar {s})=1 $ .

3. 3. $\sum _{z \in S}F_{\bar {t},t_{k+1}}(\bar {s},z) = F_{\bar {t}}(\bar {s})$ .

4. 4. For any permutation $\sigma $ of k-tuples, $F_{\sigma (\bar {t})}(\sigma (\bar {s})) =F_{\bar {t}}(\bar {s})$ .

The Kolmogorov existence theorem guarantees that any such family of functions $F_{\bar {t}}$ satisfying properties (1), (2), (3), (4) are the finite-dimensional distributions of some stochastic process. Of course, there is not a one-to-one relationship between stochastic processes and families of finite-dimensional distributions: any set of finite-dimensional distributions identifies a whole class of stochastic processes. In what follows, our theory will work at the level of families of finite-dimensional distributions, or in other words, stochastic processes in the weak sense. However, in order to make arguments more transparent we will often refer to a given stochastic process $(X_t)_{t \in T}$ whose distribution is $F_{\bar {t}}$ .

We can identify each such family of finite-dimensional distributions with a metric structure, once we add a single non-degeneracy condition: We assume that

1. 5. $\sum _{s \in S} F_{t_1,t_2}(s,s) < 1 $ for $t_1 \neq t_2$ .

This is equivalent to requiring $\mathbb {P}(X(t_1)= X(t_2))<1$ for $t_1 \neq t_2$ . We can view this either as a restriction on the stochastic processes or as identifying the point $t_1$ and $t_2$ in T when $X(t_1)=X(t_2)$ with probability 1. In either case, it ensures that the index set T is endowed with a metric, as the following lemma shows.

Lemma 16. Let T be a set and F a family of finite-dimensional distributions on T for a process taking values in a finite set S that satisfies condition (5). For $t_1, t_2 \in T$ , define the function

$$ \begin{align*} d(t_1,t_2) = 1- \sum_{s\in S} F_{t_1,t_2}(s,s). \end{align*} $$

Then $(T,d)$ is a metric space.

Note that if F consists of the finite-dimensional distributions for a stochastic process X, then

$$ \begin{align*} d(t_1,t_2) = \mathbb{P}(X(t_1) \neq X(t_2)). \end{align*} $$

Proof First note that $d(t,t) = 1 - \sum _{s \in S} F_{t,t}(s,s) = 0$ by property (2). Also, property (5) implies that $d(t_1,t_2)>0$ if $t_1 \neq t_2$ .

Next, property (4) implies $d(t_1,t_2)=d(t_2,t_1)$ .

To check the triangle inequality, we switch to the stochastic process viewpoint. Note that $X(t_1) \not = X(t_3)$ implies at least one of $X(t_1) \not = X(t_2)$ and $X(t_2) \not = X(t_3)$ . So

$$ \begin{align*} d(t_1,t_3) & = \mathbb{P}(X(t_1) \not = X(t_3)) \\ &\leq \mathbb{P}(X(t_1) \not = X(t_2)) + \mathbb{P} (X(t_2) \not = X(t_3)) \\ &= d(t_1,t_2) + d(t_2,t_3). \\[-32pt] \end{align*} $$

⊣

To view stochastic processes satisfying property (5) as relational metric structures, with domain being the index set T, we only need to define for every k-tuple of values from S the predicates

$$ \begin{align*} R_{\bar{s}}(\bar{t}) = F_{\bar{t}}(\bar{s}) = \mathbb{P}(X(\bar{t})=\bar{s}). \end{align*} $$

So the language $\mathcal {L}$ consists of the set of predicate symbols $R_{\bar {s}}$ for any finite tuple of values $\bar {s}$ , along with metric d, which we always interpret by $d(t_1,t_2) = 1 - \sum _{s \in S} R_{s,s}(t_1,t_2)$ .

We need to show that each of these predicates is uniformly continuous.

Proof Without loss of generality, consider the first argument. For $t_1, t_1^* \in T$ we have

$$ \begin{align*} R_{s_1,\ldots,s_k}(t_1,\ldots,t_k) & = \mathbb{P}( X(t_1)=s_1, \ldots, X(t_k)=s_k) \\ & \leq \mathbb{P}( X(t_1^*)=s_1, \ldots, X(t_k)=s_k) + \mathbb{P}(X(t_1^*) \neq X(t_1)) \\ & = R_{s_1,\ldots,s_k}(t_1^*, \ldots, t_k) + d(t_1,t_1^*), \end{align*} $$

where we have used the fact that $X(t_1)=s_1$ can only happen if at least one of $X(t^*_1)=s_1$ or $X(t_1^*) \not = X(t_1)$ occurs. Switching $t_1$ and $t_1^*$ gives

$$ \begin{align*} R_{s_1,\ldots,s_k}(t_1^*, \ldots, t_k) \leq R_{s_1,\ldots,s_k}(t_1,\ldots,t_k) + d(t_1,t_1^*), \end{align*} $$

and hence

$$ \begin{align*} |R_{s_1,\ldots,s_k}(t_1^*, \ldots, t_k) - R_{s_1,\ldots,s_k}(t_1,\ldots,t_k)| \leq d(t_1,t_1^*).\\[-30pt] \end{align*} $$

⊣

Now we formally define the class of metric structures $\mathcal {SP}$ .

Definition 18. A separable non-degenerate S-valued stochastic process is a separable metric space $(T,d)$ with k-ary predicates $R_{\bar {s}}$ for $k\geq 2$ , $\bar {s} \in S^k$ such that, if we let $F_{\bar {t}}(\bar {s}) = R_{\bar {s}}(\bar {t})$ for all $k, \bar {s}\in S^k, \bar {t}\in T^k$ , then conditions (1) through (4) as well as

$$ \begin{align*} (5') \quad \ 1- \sum_{s\in S} F_{t_1,t_2}(s,s)= d(t_1,t_2) \end{align*} $$

hold. We denote the set of all such metric structures by $\mathcal {SP}$ .

We will not actually use the notation $R_{\bar {s}}$ in what follows. Rather, we will stay with either $F_{\bar {t}}(\bar {s})$ or $X(\bar {t})$ to keep in line with probabilistic notation.

To summarize, any metric structure satisfying Definition 18 gives a family of finite-dimensional distributions corresponding to a non-degenerate stochastic process on T taking values in S. On the other hand, any such non-degenerate stochastic process corresponds to a metric structure of the type in Definition 18. This metric structure view of non-degenerate stochastic processes immediately gives a definition of completion and separability for stochastic processes, namely, whether the space $(T,d)$ with the induced metric d is complete and separable, respectively.

Let $\mathcal {K}$ be the class of all finite metric structures in $\mathcal {SP}$ . We will show that $\mathcal {K}$ is a Fraïssé class satisfying bAP. Note that for any two n-tuples in $\mathcal {K}_n$ , we have

$$ \begin{align*} d_{\infty}(\bar{a}, \bar{b})& = \max_{|A|\leq n, \bar{s} \in S^{|A|}} | R_{\bar{s}}(\bar{a}_A) - R_{\bar{s}}(\bar{b}_A) |\\ & = \max_{|A|\leq n, \bar{s} \in S^{|A|}} |\mathbb{P}(X(\bar{a}_A)=\bar{s}) - \mathbb{P}(X(\bar{b}_A)=\bar{s})| \end{align*} $$

where A runs over all subsets of $\{1, \ldots , n\}$ .

Here is our main result for this section.

A key component of the proof of this theorem is the Coupling Lemma of probability theory (see, for example [Reference Gao19, p. 19]). Between any two random variables X and Y taking values in some finite state space U, we can define the total variation distance between their distributions as

$$ \begin{align*} d_{TV}(X,Y) = \sup_{A \subseteq U} | \mathbb{P}(X \in A) - \mathbb{P}(Y \in A)| = \frac{1}{2} \sum_{u \in U} \left| \mathbb{P}(X = u) - \mathbb{P}(Y=u)\right|. \end{align*} $$

The Coupling Lemma asserts the following: given any two U-valued random variables X and Y, there are U-valued random variables $\tilde {X}$ and $\tilde {Y}$ defined on the same probability space so that $\tilde {X}$ has the same distribution as X, $\tilde {Y}$ has the same distribution as Y, and

$$ \begin{align*} \mathbb{P}(\tilde{X} \not = \tilde{Y}) = d_{TV}(X,Y). \end{align*} $$

In what follows, we will use the Coupling Lemma with X and Y being tuples of random variables of length n, and U being $S^n$ .

Proof of Theorem 19 HP. This follows immediately.

JEP. This follows from bAP if we identify a single point in each of the two index sets of the stochastic processes we want to jointly embed.

bAP. Let $X=(\bar {a},w)$ and $Y=(\bar {a}, z)$ be two enumerated structures in $\mathcal {K}_{n+1}$ , where X and Y agree on $\bar {a}$ . We wish to amalgamate X and Y to obtain $Z=(\bar {a}, w, z)$ .

To do this, we shift to random variable notation. X and Y correspond to two random pairs $(\mathbf {X}_{a},\mathbf {X}_{w})$ and $(\mathbf {Y}_{a},\mathbf {Y}_z)$ such that $\mathbf {X}_a$ and $\mathbf {Y}_a$ (taking values in $S^n$ ) have the same distribution and $\mathbf {X}_w$ and $\mathbf {Y}_z$ take values in S. We will create a random variable $(\mathbf {Z}_a,\mathbf {Z}_w,\mathbf {Z}_z)$ such that $(\mathbf {Z}_a,\mathbf {Z}_w)$ has the same distribution as $(\mathbf {X}_{a},\mathbf {X}_{w})$ , $(\mathbf {Z}_a,\mathbf {Z}_z)$ has the same distribution as $(\mathbf {Y}_{a},\mathbf {Y}_z)$ , and we can bound the probability that $\mathbf {Z}_w$ and $\mathbf {Z}_z$ are different.

Fix $\overline {s} \in S^n$ . We let $\mathbf {X}_{a|\overline {s}}$ denote the random variable $\mathbf {X}_w$ conditioned on $\mathbf {X}_a = \overline {s}$ ; this is the random variable defined by the distribution

$$ \begin{align*} \mathbb{P}[\mathbf{X}_{a|\overline{s}}= s ] = \frac{\mathbb{P}[(\mathbf{X}_a , \mathbf{X}_w) = (\overline{s},s) ]} { \mathbb{P}[\mathbf{X}_a = \overline{s}]}.\end{align*} $$

Let $\mathbf {Y}_{a|\overline {s}}$ be defined similarly.

For each value of $\overline {s}$ we apply the Coupling Lemma to $\mathbf {X}_{a|\overline {s}}$ and $\mathbf {Y}_{a|\overline {s}}$ to obtain the jointly defined random variables $\mathbf {Z}^X_{a|\overline {s}}$ and $\mathbf {Z}^Y_{a|\overline {s}}$ . $\mathbf {Z}^X_{a|\overline {s}}$ has the same distribution as $\mathbf {X}_{a|\overline {s}}$ , $\mathbf {Z}^Y_{a|\overline {s}}$ has the same distribution as $\mathbf {Y}_{a|\overline {s}}$ , and

$$ \begin{align*} \mathbb{P}\left( \mathbf{Z}^X_{a|\overline{s}} \neq \mathbf{Z}^Y_{a|\overline{s}}\right)= d_{TV}( \mathbf{X}_{a|\overline{s}}, \mathbf{Y}_{a|\overline{s}}). \end{align*} $$

We can assemble $(\mathbf {Z}_a,\mathbf {Z}_w,\mathbf {Z}_z)$ as follows. For each $\overline {s}\in S^n$ define

$$ \begin{align*} \mathbb{P} [ (\mathbf{Z}_a,\mathbf{Z}_w,\mathbf{Z}_z)=(\overline{s},s_1,s_2)]= \mathbb{P} [\mathbf{X}_a= \overline{s}] \mathbb{P} [ \mathbf{Z}^X_{a|\overline{s}} = s_1, \mathbf{Z}^Y_{a|\overline{s}}=s_2]. \end{align*} $$

We let the tuple $(a,w,z)$ correspond to the random variable $(\mathbf {Z}_a,\mathbf {Z}_w,\mathbf {Z}_z)$ . It remains to show that we can bound $d(w,z)$ . First we re-express the quantity in terms of $\mathbf {Z}^X_{a|\overline {s}}$ and $\mathbf {Z}^Y_{a|\overline {s}}$ by conditioning on $\mathbf {Z}_a$ .

$$ \begin{align*} d(w,z) & = \mathbb{P}(\mathbf{Z}_w \neq \mathbf{Z}_z) \\ & = \sum_{\overline{s}} \mathbb{P}[ \mathbf{Z}_a = \overline{s} ] \mathbb{P} [ \mathbf{Z}_w \neq \mathbf{Z}_z | \mathbf{Z}_a = \overline{s} ] \\ & = \sum_{\overline{s}} \mathbb{P}[ \mathbf{Z}_a = \overline{s} ] \mathbb{P} [ \mathbf{Z}^X_{a|\overline{s}} \neq \mathbf{Z}^Y_{a|\overline{s}}]. \end{align*} $$

By our use of the Coupling Lemma we then have

$$ \begin{align*} d(w,z) & = \sum_{\overline{s}} \mathbb{P}[ \mathbf{X}_a = \overline{s} ] d_{TV}( \mathbf{X}_{a|\overline{s}}, \mathbf{Y}_{a|\overline{s}}) \\ & = \sum_{\overline{s}} \mathbb{P}[ \mathbf{X}_a = \overline{s} ] \frac{1}{2} \sum_{s \in S} \left| \mathbb{P}( \mathbf{X}_{a|\overline{s}}=s ) - \mathbb{P}( \mathbf{Y}_{a|\overline{s}} = s) \right| \\ & \leq \frac{1}{2} \sum_{\overline{s}} \sum_{s \in S} \left| \mathbb{P}[ (\mathbf{X}_{a},\mathbf{X}_w)=(\overline{s},s) ] - \mathbb{P}[ (\mathbf{Y}_{a}, \mathbf{Y}_z) =(\overline{s},s)] \right| \\ & \leq \frac{1}{2} |S|^{n+1} d_{\infty}( (a,w), (a,z)), \end{align*} $$

as required.

PP. Note that, for each n, the conditions for a non-degenerate stochastic process define a closed subspace of $\mathbb {R}^k$ for a sufficiently large k. It suffices to show that $d_{\mathcal {K}}$ and $d_{\infty }$ are Lipschitz equivalent, since $d_{\infty }$ is Lipschitz equivalent to the Euclidean metric. We will show, for any pair of n-tuples $\bar {a}, \bar {b}$ that

$$ \begin{align*} \frac{1}{n} d_{\infty}(\bar{a}, \bar{b}) \leq d_{\mathcal{K}}(\bar{a}, \bar{b}) \leq |S|^n d_{\infty}(\bar{a}, \bar{b}). \end{align*} $$

To prove the first inequality, suppose that we have $\bar {a}$ and $\bar {b}$ embedded together in $(\bar {a}, \bar {b})$ so that $\max _{i} \mathbb {P}(X(a_i) \neq X(b_i) ) \leq d_{\mathcal {K}}(\bar {a}, \bar {b}) + \epsilon $ for some $\epsilon>0$ . For any subset X of $\{1, \ldots , n\}$ and any element $\alpha $ of $S^{|X|}$ we have

$$ \begin{align*} |\mathbb{P}(X(a_X) =\alpha) - \mathbb{P} (X(b_X) =\alpha )| &\leq \mathbb{P}( X(a_X)\neq X(b_X)) \leq \mathbb{P}( X(\bar{a}) \neq X(\bar{b}))\\ & \leq n \max_i \mathbb{P}(X(a_i) \neq X(b_i) ) \leq n d_{\mathcal{K}}(\bar{a}, \bar{b}) + n \epsilon. \end{align*} $$

Dividing by n and letting $\epsilon $ go to zero gives the first inequality.

To prove the second inequality, note that for any $A \subseteq S^n$ , we have

$$ \begin{align*} |\mathbb{P}(X(\bar{a})\hspace{-1pt}\in\hspace{-1pt} A)\hspace{-1pt} -\hspace{-1pt} \mathbb{P}(X(\bar{b})\hspace{-1pt}\in\hspace{-1pt} A)| \leq \sum_{\alpha \in A} |\mathbb{P}(X(\bar{a})\hspace{-1pt}=\hspace{-1pt}\alpha) - \mathbb{P}(X(\bar{b})\hspace{-1pt}=\hspace{-1pt}\alpha)| \leq |S|^n d_{\infty}(\bar{a}, \bar{b}). \end{align*} $$

So we obtain the following from the definition of total variation distance:

$$ \begin{align*} d_{TV}(X(\bar{a}),X(\bar{b})) \leq |S|^n d_{\infty}(\bar{a}, \bar{b}). \end{align*} $$

Using the Coupling Lemma on the whole random vectors $X(\bar {a})$ and $X(\bar {b})$ , we can find a joint embedding so that $\mathbb {P}(X(\bar {a}) \neq X(\bar {b})) \leq d_{TV}(X(\bar {a}),X(\bar {b})) \leq |S|^n d_{\infty }(\bar {a}, \bar {b})$ . Now we have that

$$ \begin{align*} \max_i \mathbb{P}( X(a_i) \neq X(b_i)) \leq \mathbb{P}(X(\bar{a}) \neq X(\bar{b})) \leq |S|^n d_{\infty}(\bar{a}, \bar{b}) \end{align*} $$

and the inequality is established.

CP. The n-ary predicates on $\mathcal {K}$ are, for tuples $\alpha \in S^n$ ,

$$ \begin{align*} R_{\alpha}(t_1, \ldots, t_n) = \mathbb{P}(X(t_1)= \alpha_1, \ldots, X(t_n)=\alpha_n). \end{align*} $$

Let $\bar {a}$ and $\bar {b}$ be two structures of length n such that $d_{\mathcal {K}}(\bar {a}, \bar {b})=\epsilon $ . Let them be jointly embedded in $(\bar {a}, \bar {b})$ such that $\max _i d(a_i,b_i) \leq 2 \epsilon $ . Then Lemma 17 implies that

$$ \begin{align*} |R_{\alpha}(\bar{a}) - R_{\alpha}(\bar{b})| \leq 2 n \epsilon. \end{align*} $$

as required.⊣

Now we will translate the existence of a Fraïssé limit for the class $\mathcal {K}$ into the language of stochastic processes. We will need to introduce some terminology that is non-standard in the context of stochastic processes. Let $X_t$ for $t \in T$ and $Y_u$ for $u \in U$ be two S-valued stochastic processes. Let $\phi \colon T \rightarrow U$ be given. The map $\phi $ embeds $(T,X)$ in $(U,Y)$ if the finite-dimensional distributions of $Y_{\phi (t)}, t \in T$ are identical to those of $X_t, t \in T$ . Furthermore, $\phi $ is an isomorphism if $\phi $ is onto. An automorphism is an isomorphism from a stochastic process to itself. A stochastic process is non-degenerate if $d(t_1,t_2) := \mathbb {P}(X(t_1) \not = X(t_2) )>0$ is non-zero for all $t_1 \not = t_2$ . A stochastic process is separable if $(T,d)$ is a separable metric space. (This conflicts with the notion of separability in the stochastic processes literature.) A stochastic process $X_t, t \in T$ is finite if T is finite.

A stochastic process is universal if any finite S-valued stochastic process can be embedded in it. A map $\phi $ is a partial isomorphism from $X_t, t \in T$ to $Y_u, u \in U$ if $\phi \colon T_0 \rightarrow U$ is an embedding for some $A_0 \subseteq T$ . We say $\phi $ is a finite partial isomorphism if $A_0$ is finite. A stochastic processes is ultrahomogeneous if any finite partial isomorphism from the process to itself can be extended to an automorphism.

5 Diversities

A diversity [Reference Bryant and Klaere5] is a pair $(X,\delta )$ where X is a set and $\delta $ is a function from the finite subsets of X to $\mathbb {R}$ satisfying

1. (D1) $\delta (A) \geq 0$ , and $\delta (A) = 0$ if and only if $|A|\leq 1$ .

2. (D2) If $B \neq \emptyset $ then $\delta (A\cup B) + \delta (B \cup C) \geq \delta (A \cup C)$

for all finite $A, B, C \subseteq X$ . Diversities form an extension of the concept of a metric space. Property (D2) is the triangle inequality and is the analogue of the triangle inequality for metric spaces. Every diversity has an induced metric, given by $d(a,b) = \delta (\{a,b\})$ for all $a,b \in X$ . Note also that $\delta $ is monotonic: $A \subseteq B$ implies $\delta (A) \leq \delta (B)$ . Also $\delta $ is subadditive on sets with nonempty intersection: $\delta (A \cup B) \leq \delta (A) + \delta (B)$ when $A \cap B \neq \emptyset $ [Reference Bryant and Klaere5, Proposition 2.1]. Monotonicity and subadditivity on overlapping sets are also sufficient to establish the triangle inequality: If $B\neq \emptyset $ ,

(3) $$ \begin{align} \delta(A \cup C ) \leq \delta( A \cup B \cup C) \leq \delta(A \cup B) + \delta(B \cup C). \end{align} $$

Just as a semimetric generalizes a metric space by allowing $d(x,y)=0$ for $x \neq y$ , we define a semidiversity to be a pair $(X,\delta )$ that satisfy (D1) and (D2) above except that we may have $\delta (A)=0$ for $|A|>1$ .

In [Reference Bryant and Dress4] we constructed the diversity analog $(\mathbb {U}, \delta _{\mathbb {U}})$ of the Urysohn metric space. It is determined uniquely by being universal for separable diversities, and ultrahomogeneous in the sense that isomorphic finite subdiversities are automorphic. We also showed that the induced metric space of $(\mathbb {U}, \delta _{\mathbb {U}})$ is the Urysohn metric space. Our method of constructing this Urysohn diversity in [Reference Bryant and Dress4] was analogous to Katětov’s construction of the Urysohn metric space [Reference Fraïssé19]. Andreas Hallbäck [Reference Yaacov, Berenstein, Henson and Usvyatsov10] has published results connecting our research on the universal ultrahomogeneous diversity to descriptive set theory. For instance, he shows that the automorphism group is a universal Polish group.

Here we demonstrate the existence of $(\mathbb {U}, \delta _{\mathbb {U}})$ via Ben Yaacov’s theory of metric Fraïssé limits [Reference Rado19], as we described in Section 2, along with our results in Section 3 is order to prove that the Fraïssé limit is ultrahomogeneous and not just approximately ultrahomogeneous.

In order to study diversities using Ben Yaacov’s theory, it is necessary to describe them as metric structures. Every diversity immediately has a metric space associated with it, the induced metric. The diversity function $\delta $ takes a variable number of distinct arguments, so this does not immediately fit into model theory. Hence we define $\delta _k$ as a predicate for $k \geq 1$ . We define $\delta _k$ of a tuple in $X^k$ to be $\delta $ of the set of values that the tuple takes. For example,

$$ \begin{align*} \delta_3(x,y,x)= \delta(\{x,y\}) \end{align*} $$

for all $x,y \in X$ . In this way, diversities are relational metric structures with a countable number of predicates, one with arity m for every $m\geq 2$ .

What axioms do diversities satisfy as metric structures? In the following all tuples are assumed to be of non-zero length. The set function $\delta $ being a diversity is equivalent to

1. 1. $\delta _1(x)=0$ for all points $x \in X$ .

2. 2. $\delta _k$ is permutation invariant.

3. 3. If $\delta _k(a_1,\ldots ,a_k)=0$ then $a_1=\cdots =a_k$ .

4. 4. For all $a_1,\ldots , a_k \in X$ , $ \delta _{k+1}( a_1, \ldots , a_{k-1}, a_k, a_k ) = \delta _k( a_1, \ldots , a_{k-1}, a_k). $

5. 5. $\delta _{k+1}(\bar {a},b) \geq \delta _k(\bar {a})$ for all $\bar {a} \in X^k$ , $b \in X$ .

6. 6. For all tuples $\bar {a}, \bar {b}, \bar {c}$ with lengths $j,k,\ell $ , if $k \geq 1$

   $$ \begin{align*} \delta_{j+\ell}( \bar{a}, \bar{c}) \leq \delta_{j+k}(\bar{a},\bar{b}) + \delta_{k+\ell}(\bar{b},\bar{c}). \end{align*} $$

Note that these conditions imply that $d \equiv \delta _2$ is a metric on X. To be a metric structure, we need to confirm that each predicate is uniformly continuous, as shown in the following lemma.

Proof Consider varying the ith argument of $\delta ^{(k)}$ from $x_i$ to $x_i'$ . We know from the triangle inequality that

$$ \begin{align*} \delta^{(k)}(x_1, \ldots, x_i, \ldots, x_k) & = \delta(\{x_1, \ldots, x_i, \ldots, x_k\}) \\ & \leq \delta(\{x_1, \ldots, x_i', \ldots, x_k\}) + \delta(\{ x_i, x_i'\}) \\ & = \delta^{(k)}(x_1, \ldots, x_i', \ldots, x_k) + d(x_i,x_i'). \end{align*} $$

Similarly, $\delta ^{(k)}(x_1, \ldots , x_i', \ldots , x_k) \leq \delta ^{(k)}(x_1, \ldots , x_i, \ldots , x_k) + d(x_i,x_i')$ . So

$$ \begin{align*} | \delta^{(k)}(x_1, \ldots, x_i, \ldots, x_k) - \delta^{(k)}(x_1, \ldots, x_i', \ldots, x_k)| \leq d(x_i, x_i') \end{align*} $$

as required.⊣

Since these are closed conditions, for any finite set X with $|X|=n$ , the set of diversities can be viewed as a closed subset of $\mathbb {R}^{k}$ for $k = n + n^2 + \cdots + n^n$ .

Diversities have already been given a definition of completeness and separability in [Reference Katětov19]: a diversity is complete if its induced metric space is complete and it is separable if its induced metric space is separable. Fortunately, these correspond precisely with the definitions one would get with viewing diversities as metric structures, so the Fraïssé limit will give us exactly what we want.

We define a special one-point amalgamation of diversities that yields the bounded Amalgamation Property (bAP).

Definition 22. Let $(X \cup \{z_1\},\delta )$ and $(X \cup \{z_2\},\delta )$ be two diversities that agree on X. The amalgamation of the diversities is defined on $X \cup \{z_1,z_2\}$ by

(4) $$ \begin{align} &\delta(A \cup \{z_1, z_2\}) \end{align} $$

$$\begin{align*} &=\max \left[\sup_{B \subseteq X} \delta( A \cup B \cup \{z_1\} ) - \delta( B \cup \{z_2\}) , \sup_{C \subseteq X} \delta( A \cup C \cup \{z_2\}) - \delta(C \cup \{z_1\})\hspace{-3pt}\right]\hspace{-3pt}.\nonumber \end{align*}$$

The idea of this definition of the amalgamation is to obtain the minimal diversity that extends both the diversities on $X \cup \{z_1\}$ and $X \cup \{z_2\}$ . To see this, note that however we define the amalgamation, the triangle inequality requires

$$ \begin{align*} \delta(A \cup \{z_1, z_2\}) \geq \delta( A \cup B \cup \{z_1\} ) - \delta( B \cup \{z_2\}) \end{align*} $$

for all $B \subseteq X$ and

$$ \begin{align*} \delta(A \cup \{z_1, z_2\}) \geq \delta( A \cup C \cup \{z_2\}) - \delta(C \cup \{z_1\}) \end{align*} $$

for all $C \subseteq X$ . So the value of $\delta (A \cup \{z_1,z_2\})$ can not be less than the one we have defined.

Proof To establish that $\delta $ is a diversity, it suffices to prove

1. (a) monotonicity: $\delta (A) \leq \delta (B)$ when $A \subseteq B$ and

2. (b) subadditivity on overlapping sets: $A \cap B \not = \emptyset $ implies $\delta (A \cup B) \leq \delta (A) + \delta (B)$ ,

see (3).

Monotonicity with respect to A follows easily from where A appears in the definition. To see $\delta (A \cup \{z_1, z_2\}) \geq \delta (A \cup \{z_1\})$ , just let $B = \emptyset $ , and likewise for $\delta (A \cup \{z_1, z_2\}) \geq \delta (A \cup \{z_2\})$ with $C = \emptyset $ .

For subadditivity on overlapping sets, start with the sets $A_1 \cup \{z_1\}$ and $A_2 \cup \{z_2\}$ where $A_1 \cap A_2 \neq \emptyset $ . Let $\epsilon>0$ be given. Without loss of generality, suppose we have a set B such that

$$ \begin{align*} \delta( A_1 \cup A_2 \cup \{z_1,z_2\}) -\epsilon \leq \delta( A_1 \cup A_2 \cup B \cup \{z_1\}) - \delta( B \cup \{z_2\}). \end{align*} $$

The triangle inequality gives $\delta ( A_1 \cup A_2 \cup B \cup \{z_1\}) \leq \delta (A_1 \cup \{z_1\}) + \delta ( A_2 \cup B)$ , and so

$$ \begin{align*} \delta( A_1 \cup A_2 \cup \{z_1,z_2\}) -\epsilon \leq \delta(A_1 \cup \{z_1\}) + \delta( A_2 \cup B) - \delta( B \cup \{z_2\}). \end{align*} $$

The triangle inequality again gives $\delta ( A_2 \cup B) \leq \delta (A_2 \cup \{z_2\}) + \delta (B \cup \{z_2\})$ and so

$$ \begin{align*} \delta( A_1 \cup A_2 \cup \{z_1,z_2\}) -\epsilon \leq \delta(A_1 \cup \{z_1\}) + \delta( A_2 \cup \{z_2\}). \end{align*} $$

Since $\epsilon>0$ was arbitrary, we have $\delta ( A_1 \cup A_2 \cup \{z_1,z_2\}) \leq \delta (A_1 \cup \{z_1\}) + \delta ( A_2 \cup \{z_2\})$ .

Next, consider the sets $A_1 \cup \{z_1\}$ and $A_2 \cup \{z_1, z_2 \}$ , where $A_1$ and $A_2$ do not necessarily intersect. Let $\epsilon>0$ be given. Suppose there exists $B \subseteq X$ such that

$$ \begin{align*} \delta(A_1 \cup A_2 \cup \{z_1, z_2\}) - \epsilon \leq \delta( A_1 \cup A_2 \cup B \cup \{z_1\}) - \delta(B \cup \{z_2\}). \end{align*} $$

The triangle inequality gives $\delta (A_1 \cup A_2 \cup B \cup \{z_1\}) \leq \delta (A_1 \cup \{z_1\}) + \delta (A_2 \cup B \cup \{z_1\})$ and so

$$ \begin{align*} \delta(A_1\cup A_2 \cup \{z_1, z_2\}) -\epsilon & \leq \delta(A_1 \cup \{z_1\}) + \delta(A_2 \cup B \cup \{z_1\}) - \delta(B \cup \{z_2\}) \\ & \leq \delta(A_1 \cup \{z_1\}) + \delta( A_2 \cup \{z_1, z_2 \}), \end{align*} $$

where we have used the definition of $\delta ( A_2 \cup \{z_1, z_2 \})$ .

On the other hand, suppose there exists a $C \subseteq X$ such that

$$ \begin{align*} \delta(A_1 \cup A_2 \cup \{z_1, z_2\}) - \epsilon \leq \delta( A_1 \cup A_2 \cup C \cup \{z_2\}) - \delta(C \cup \{z_1\}). \end{align*} $$

Add and subtract $\delta (A_1 \cup C \cup \{z_1\})$ from the left-hand side to get

$$ \begin{align*} \delta(A_1 \cup A_2 \cup \{z_1, z_2\}) - \epsilon &\leq \delta( A_1 \cup A_2 \cup C \cup \{z_2\}) - \delta( A_1 \cup C \cup \{z_1\}) +\\ &\qquad \delta( A_1 \cup C \cup \{z_1\})- \delta(C \cup \{z_1\}) \\ &\leq \delta( A_2 \cup \{z_1,z_2\}) + \delta( A_1 \cup \{z_1\}), \end{align*} $$

where we have used the definition of the amalgamation and the fact that

$$ \begin{align*} \delta( A_1 \cup C \cup \{z_1\})- \delta(C \cup \{z_1\} \leq \delta( A_1 \cup \{z_1\}) \end{align*} $$

by the triangle inequality.⊣

Proof To obtain HP, observe that the diversity axioms are just equalities and inequalities that hold for all points in the diversity, so taking a subset of the diversity cannot violate any of the axioms.

To obtain JEP, for any two finite diversities $(X,\delta _X)$ and $(Y,\delta _Y)$ , let Z be the disjoint union of X and Y. Let k be the largest value taken by either of the diversities $\delta _X$ and $\delta _Y$ . Let $\delta _Z$ be defined as the extension of $\delta _X$ and $\delta _Y$ such that $\delta _Z(A)=k$ for any set A with nonzero intersection with both X and Y. It is straightforward to check that $(Z,\delta _Z)$ is a diversity.

To show bAP, we apply the bounded amalgamation in Def. 22 to the two tuples $(\bar {a}, z_1)$ and $(\bar {a}, z_2)$ to get $(\bar {a}, z_1, z_2)$ . Within this tuple, we have that

$$ \begin{align*} d(z_1,z_2) = \delta(\{z_1,z_2\}) = \sup_{A \subseteq \bar{a}} | \delta( A \cup \{z_1\}) - \delta( A \cup \{z_2\}) | \end{align*} $$

giving $d(z_1,z_2) \leq d_{\infty }( (\bar {a},z_1), (\bar {a},z_2))$ , as required.

To show PP: The set of all enumerated diversities on n points can be viewed as a subset of ${\mathbb {R}}^k$ for some finite k. This subset is closed and separable under the Euclidean metric, since it is the set of points that satisfies a family of non-strict inequalities. So this subset of ${\mathbb {R}}^{k}$ is a Polish space. We just need to show that for each n, $d_{\mathcal {K}}$ is Lipschitz equivalent to the Euclidean metric. Since the Euclidean metric is Lipschitz equivalent to $d_{\infty }$ , it suffices to show that $d_{\mathcal {K}}$ is Lipschitz equivalent to $d_{\infty }$ which is the content of Lemma 25.

To show CP: The only n-ary predicate on $\mathcal {K}$ is the nth diversity predicate $\delta ^{(n)}(x_1,\ldots ,x_n)= \delta (\{x_1,\ldots ,x_n\})$ , deleting repeated elements in the set listing. Let $\bar {a}$ , $\bar {b}$ be two diversities in $\mathcal {K}_n$ . Suppose $d_{\mathcal {K}}(\bar {a}, \bar {b}) = \epsilon $ . Let $(\bar {a}', \bar {b}')$ be an embedding of $\bar {a}$ , $\bar {b}$ so that $\max _i (a_i',b_i') \leq 2 \epsilon $ . By Lemma 21,

$$ \begin{align*} |\delta^{(n)} (\bar{a}) - \delta^{(n)} (\bar{b}) | = |\delta'(\bar{a}')- \delta'(\bar{b}')| \leq 2 n \epsilon, \end{align*} $$

showing that the map $\delta ^{(n)} \colon \mathcal {K}_n \rightarrow {\mathbb {R}}$ is Lipschitz continuous.⊣

Lemma 25. For all n and $\bar {a}, \bar {b}$

$$ \begin{align*} \frac{1}{n} d_{\infty}(\bar{a},\bar{b}) \leq d_{\mathcal{K}}(\bar{a},\bar{b}) \leq d_{\infty} (\bar{a},\bar{b}). \end{align*} $$

Proof The first inequality follows from the predicates being one-Lipschitz. In particular, suppose we have an embedding of $\bar {a}$ and $\bar {b}$ into a third diversity $((\bar {a}',\bar {b}'),\delta )$ so that $\max _i d( a^{\prime }_i, b^{\prime }_i) < d_{\mathcal {K}}(\bar {a},\bar {b}) + \epsilon $ . For any set $X \subseteq \{1, \ldots , n\}$

$$ \begin{align*} |\delta_a( \bar{a}_X) - \delta_b(\bar{b}_X)| &= |\delta( \bar{a}^{\prime}_X) - \delta(\bar{b}^{\prime}_X)| \leq \sum_{i=1}^n d( \bar{a}^{\prime}_i, \bar{b}^{\prime}_i ) \leq n \max_i d( \bar{a}^{\prime}_i, \bar{b}^{\prime}_i )\\ &\quad < n d_{\mathcal{K}}(\bar{a}, \bar{b}) + n \epsilon, \end{align*} $$

where we have used Lemma 21. Taking the limit as $\epsilon \rightarrow 0$ and dividing by n gives the first inequality.

To prove the second inequality we will repeatedly use the bAP for diversities. Suppose $d_{\infty }(\bar {a},\bar {b}) =\epsilon $ . We will construct a joint embedding of $\bar {a}$ and $\bar {b}$ into a new diversity where corresponding points in the tuples are never further than $\epsilon $ away from each other.

First we identify $a_1$ and $b_1$ . Consider the two tuples $(a_1,b_1,a_2)$ and $(a_1,b_1,b_2)$ . Since $d_{\infty }(\bar {a},\bar {b})=\epsilon $ , we know that $d_{\infty }((a_1,b_1,a_2),(a_1,b_1,b_2)) \leq \epsilon $ , and so we can use bAP for diversities to find a joint embedding $(a_1,b_1,a_2,b_2)$ where $d(a_2,b_2) \leq \epsilon $ . We repeat this step for the tuples $(a_1,b_1,a_2,b_2,a_3)$ and $(a_1,b_1,a_2,b_2,b_3)$ , and so forth. In the end we have a joint embedding of all the points in $\bar {a}$ and $\bar {b}$ such that $d(a_i, b_i) \leq \epsilon $ for all $i= 1, \ldots , k$ , as required.⊣

6 $L_1$ metrics and $L_1$ diversities

Recall that $L_1(\Omega ,\mathcal {A},\mu )$ is the set of $\mathcal {A}$ -measurable functions f defined on $\Omega $ with $\int _{\Omega } |f(\omega )| d\mu (\omega ) < \infty $ equipped with the metric

$$ \begin{align*} d(f,g)= \int_{\Omega} |f(\omega) - g(\omega)| d\mu(\omega). \end{align*} $$

An $L_1$ metric space is a metric space that can be embedded in $L_1(\Omega ,\mathcal {A},\mu )$ for some measure space $(\Omega ,\mathcal {A},\mu )$ . (Here an embedding is a injective map that preserves the metric.) There is a well-developed theory of $L_1$ metric spaces, including many alternative characterizations of them in the finite case [Reference Bryant and Tupper7, Chapters 3 and 4]. In particular, a metric on a finite set X is $L_1$ if and only if it can be written as a non-negative linear combination of cut semimetrics, $d_{U|\bar {U}}$ [Reference Bryant and Tupper7, Theorem 4.2.6]. To explain, letting $\bar {U} = X \setminus U$ , the cut semimetric $d_{U|\bar {U}}$ is defined by

$$ \begin{align*} d_{U|\bar{U}}(x,y) = \left\{ \begin{array}{cl} 1, & \mbox{if } (x \in U \mbox{ and } y \in \bar{U}) \mbox{ or } (y \in U \mbox{ and } x \in \bar{U}),\\ 0, & \mbox{otherwise}. \end{array} \right. \end{align*} $$

Then d is an $L_1$ metric if and only if

$$ \begin{align*} d(x,y)= \sum_{U \subseteq X} \lambda_U d_{U| \bar{U}} (x,y) \end{align*} $$

for some $\lambda _U \geq 0$ .

$L_1$ diversities were introduced in [Reference Bryant, Nies and Tupper6]. To define this class of diversities, we first define a particular diversity function $\delta $ on $L_1(\Omega ,\mathcal {A},\mu )$ . For any finite set of functions F in $L_1(\Omega ,\mathcal {A},\mu )$ we define the diversity of F to be

(5) $$ \begin{align} \delta( F) = \int_{\Omega} \max_{f\in F} f(\omega) - \min_{g \in F} g(\omega) \, d\omega.\end{align} $$

In [Reference Bryant, Nies and Tupper6, p. 4] we showed that this is a diversity, and if we restrict F to only having two points this gives the $L_1$ metric as its induced metric. Now we define an $L_1$ diversity to be a diversity that can be embedded in $L_1(\Omega ,\mathcal {A},\mu )$ with the diversity function $\delta $ given by (5), for some measure space $(\Omega ,\mathcal {A},\mu )$ .

Analogous to cut semimetrics, for any partition $U|\bar {U}$ of a set X there is a cut semidiversity given by [Reference Bryant, Nies and Tupper6, p. 9]

$$ \begin{align*} \delta_{U|\bar{U}}(A) = \left\{ \begin{array}{cl} 1, & \mbox{if } (A \cap U \neq \emptyset) \mbox{ and } (A \cap \bar{U} \neq \emptyset ),\\ 0, & \mbox{otherwise}. \end{array} \right. \end{align*} $$

In [Reference Bryant, Nies and Tupper6, Proposition 9] we showed that a finite diversity $(X,\delta )$ is $L_1$ if and only if $\delta $ can be written as a non-negative linear combination of cut semidiversities:

$$ \begin{align*} \delta(A) = \sum_{U \subseteq X} \lambda_U \delta_{U|\bar{U}} (A), \end{align*} $$

where all $\lambda _U \geq 0$ . The induced metric of an $L_1$ diversity is $L_1$ , and conversely, every $L_1$ metric is the induced metric of some $L_1$ diversity. Both of these facts follow from the definition of both $L_1$ metrics and $L_1$ diversities in terms of embedding into $L_1(\Omega ,\mathcal {A},\mu )$ .

In general, finite $L_1$ metrics do not have a unique decomposition in cut semimetrics [Reference Bryant and Tupper7, Section 4.3]; see [Reference Witsenhausen2, Equation 9] for an example. An attractive feature of $L_1$ diversities is that each $L_1$ diversity has a unique decomposition into cut semidiversities; see [Reference Bryant, Nies and Tupper6, Proposition 10] which is derived from [Reference Yaacov3, Theorem 3 and 4]. Later we show another nice feature of finite $L_1$ diversities: they satisfy the bounded Amalgamation Property (bAP) and in turn have an exact Fraïssé limit. Conversely, we show that the class of $L_1$ metric spaces does not even satisfy NAP, and hence does not have even an approximate Fraïssé limit.

6.1 There is no approximate Fraïssé limit for $L_1$ metrics

We will prove that there is no Fraïssé limit (neither approximate nor exact) for finite $L_1$ metrics by showing that the class does not satisfy NAP. This can be done with a simple example.

We start by considering the simplest finite metric space that cannot be embedded in $L_1$ . All metric spaces on four or fewer points can be embedded in $L_1$ [Reference Poelstra19, p. 190]. The following five-point metric space cannot:

$$ \begin{align*} \begin{array}{l|ccccc} & a & b & c & z_1 & z_2\\ \hline a & 0 & 2 & 2 & 1 & 1 \\ b & & 0 & 2 & 1 & 1 \\ c & & & 0 & 1 & 1 \\ z_1 & & & & 0 & 2 \\ z_2 & & & & & 0 \end{array} \end{align*} $$

(This is the shortest path metric in the complete bipartite graph $K_{2,3}$ .) This metric is proved to not be $L_1$ by showing that it does not satisfy the following pentagonal inequality [Reference Bryant and Tupper7, Section 6.1]

(6) $$ \begin{align} \sum_{x,y \in \{a,b,c\}} d(x,y) + \sum_{x,y \in \{z_1,z_2\}} d(x,y) - 2 \sum_{x \in \{a,b,c\}, y \in \{z_1,z_2\}} d(x,y) \leq 0. \end{align} $$

A natural way to approach finding a counter-example to the NAP is to choose two metric spaces with a common substructure that when amalgamated must yield this metric or another one violating the pentagonal inequality. Some experimentation gave the following pair of metric spaces

$$ \begin{align*} \begin{array}{l|ccccc} & a & b & c & e & z_1\\ \hline a & 0 & 2 & 2 & 2 & 1 \\ b & & 0 & 2 & 2 & 1 \\ c & & & 0 & 1 & 1 \\ e & & & & 0 & 1 \\ z_1 & & & & & 0 \end{array} \quad \begin{array}{l|ccccc} & a & b & c & e & z_2\\ \hline a & 0 & 2 & 2 & 2 & 1 \\ b & & 0 & 2 & 2 & 1 \\ c & & & 0 & 1 & 1 \\ e & & & & 0 & 2 \\ z_2 & & & & & 0 \end{array} \end{align*} $$

Amalgamating these two metric spaces while identifying the common substructure on $\{a,b,c,e\}$ gives

$$ \begin{align*} \begin{array}{l|cccccc} & a & b & c & e & z_1 & z_2\\ \hline a & 0 & 2 & 2 & 2 & 1 & 1\\ b & & 0 & 2 & 2 & 1 & 1 \\ c & & & 0 & 1 & 1 & 1 \\ e & & & & 0 & 1 & 2 \\ z_1 & & & & & 0 & \gamma \\ z_2 & & & & & & 0 \end{array} \end{align*} $$

where $\gamma>0$ needs to be determined. For the amalgamation to be a valid metric space, we need $1 \leq \gamma \leq 2$ . However, the pentagonal inequality is not satisfied for any value of $\gamma $ in this range. Evaluating (6) for this metric space gives $2 \gamma \leq 0$ , which cannot hold for any $\gamma $ in the range. So the class of all finite $L_1$ metrics does not satisfy AP. Hence, there is not a exact Fraïssé limit for finite $L_1$ metrics.

Is it still possible for finite $L_1$ metrics to have an approximate Fraïssé limit? To rule out this possibility we show that the set of finite $L_1$ metrics does not even satisfy NAP. The approximate amalgamation property requires us to embed the two metric spaces above in a common metric space, where instead of the images of $a,b,c$ being common, they just have to be arbitrarily close to each other. But the pentagonal inequality is a closed condition, and so any metric space arbitrarily close to our counter-example must also fail to satisfy it. So NAP does not hold and there is no approximate Fraïssé limit for finite $L_1$ metric spaces.

6.2 An exact Fraïssé limit for $L_1$ diversities

Finally, if we consider $L_1$ diversities, there is an exact Fraïssé limit, as we show here. Its induced metric is a universal $L_1$ metric, but is not ultrahomogeneous, by the results of the previous subsection.

Theorem 26. The class of finite $L_1$ diversities viewed as relational metric structures satisfies HP, JEP, bAP, PP, CP, and is therefore a Fraïssé class with a separable ultrahomogeneous limit. Furthermore, the limit is universal with respect to separable $L_1$ diversities, and is the unique such $L_1$ diversity.

Proof HP. As in the general diversity case, taking a subset of points cannot violate any diversity axioms. Furthermore, if a diversity can be embedded in $L_1(\Omega ,\mathcal {A},\mu )$ so can any subdiversity of it.

JEP. This follows from bAP if we identify a single point in each of the finite $L_1$ diversities.

bAP. Suppose that $(A,\delta _A)$ embeds into $(B,\delta _B)$ and into $(C,\delta _C)$ . Suppose that all three diversities are $L_1$ -embeddable. We need to show that $(B,\delta _B)$ and $(C,\delta _C)$ can be simultaneously embedded into a $L_1$ diversity $(D,\delta _D)$ .

We assume that $B\setminus A$ is disjoint from $C\setminus A$ . To help index the splits, we fix $a \in A$ . Then the three diversities can be written as

$$ \begin{align*} \delta_A &= \sum_{U \subseteq A \setminus \{a\}, U \not = \emptyset} \alpha_{U} \delta_{U|(A \setminus U)},\\ \delta_B &= \sum_{V \subseteq B \setminus \{a\}, V \not = \emptyset} \beta_{V} \delta_{V|(B \setminus V)},\\ \delta_C &= \sum_{W \subseteq C \setminus \{a\}, W \not = \emptyset} \gamma_{W} \delta_{W|(C \setminus W)}, \end{align*} $$

where $\alpha _U, \beta _V, \gamma _W$ are all non-negative.

We know that the three diversities all agree on subsets of A:

$$ \begin{align*} \delta_A = \delta_B |_A = \delta_C |_A. \end{align*} $$

$L_1$ diversities on A are uniquely expressed as a weighted sum of splits of A. We need to figure out how to write $\delta _B|_A$ and $\delta _C |_A$ as a weighted sum of splits of A. But for each split of A, there are many corresponding splits of B (or C) that have the same effect on subsets of A. So we can break down $\delta _B|_A$ as

$$ \begin{align*} \delta_B = \sum_{U \subseteq A \setminus \{a\} , U \neq \emptyset} \left[ \sum_{V \subseteq B \colon V \cap A=U} \beta_V \delta_{V | (B\setminus V)} \right], \end{align*} $$

and a similar expression holds for $\delta _C$ . For each split $U \subseteq A$ , $a \not \in U$ , $U \not =\emptyset $ , we then have

$$ \begin{align*}\sum_{V \subseteq B: V \cap A = U } \beta_{V} = \sum_{W \subseteq C: W \cap A = U } \gamma_{W} = \alpha_{U}.\end{align*} $$

We will now define the amalgamated $L_1$ diversity. Let $M^{(U)}$ be a matrix with rows indexed by elements of $\{V \subseteq B: V \cap A = U\}$ ; columns indexed by elements of $\{W \subseteq C: W \cap A = U\}$ ; such that for all V

$$ \begin{align*}\sum_{W \subseteq C: W \cap A = U } M^{(U)}_{VW} = \beta_{V} \end{align*} $$

and for all W,

$$ \begin{align*}\sum_{V \subseteq B: V \cap A = U } M^{(U)}_{VW} = \gamma_W.\end{align*} $$

Any such matrix provides an amalgamation $\delta _D$ given by

$$ \begin{align*}\delta_D = \sum_{U \subseteq A \setminus \{a\}, U \neq \emptyset} \sum_{V \subseteq B: V \cap A = U } \sum_{W \subseteq C: W \cap A = U } M^{(U)}_{VW} \delta_{V \cup W | ((B \cup C) \setminus (V \cup W))}.\end{align*} $$

We need to find a choice of $M^{(U)}$ such that bAP holds. We just consider two-point amalgamation; the general case follows by induction. We let $B=A \cup \{z_1\}$ and $C = A \cup \{z_2\}$ . Now U runs over all nonempty subsets of A not containing $\{a\}$ . But for each U, V just takes the values U and $U \cup \{z_1\}$ and W just takes the values U and $U \cup \{z_2\}$ .

Now our amalgamated diversity simplifies to (only writing the one half of the splits in the split notation, i.e., U for $U |( (A \cup \{z_1,z_2\})\setminus U$ )

$$ \begin{align*} \delta_D &= \sum_{U \subseteq A \setminus \{a\}} M^{(U)}_{U,U} \delta_{U} + M^{(U)}_{U\cup \{z_1\},U} \delta_{U \cup \{z_1\}} + M^{(U)}_{U,U \cup \{z_2\}} \delta_{U \cup \{z_2\}} \\&\quad + M^{(U)}_{U \cup\{z_1\},U\cup \{z_2\}}\delta_{U \cup \{z_1,z_2\}}. \end{align*} $$

If we only want to know the value of the diversity on $\{z_1,z_2\}$ then it simplifies to

(7) $$ \begin{align} \delta_D(\{z_1,z_2\}) = \sum_{U \subseteq A \setminus \{a\}} M^{(U)}_{U\cup\{z_1\},U} + M^{(U )}_{U,U \cup \{z_2\}}. \end{align} $$

We choose the entries of $M^{(U)}$ analogously to how we chose to amalgamate stochastic processes in Section 4. We let

$$ \begin{align*} M_{U,U}^{(U)} & = \min(\beta_U,\gamma_U), \\ M_{U\cup\{z_1\},U\cup\{z_2\}}^{(U)} & = \min( \beta_{U \cup \{z_1\}}, \gamma_{U \cup \{z_2\}}). \\ M_{U\cup\{z_1\},U}^{(U)} & = \gamma_U - \min( \beta_U, \gamma_U ). \\ M_{U,U\cup\{z_2\}}^{(U)} & = \beta_U - \min( \beta_{U} , \gamma_{U}) \end{align*} $$

for each $U \subseteq A, a \not \in U$ .

Plugging these choices into (7) gives

$$ \begin{align*} \delta_D(\{z_1,z_2\}) = \sum_{U \subseteq A \setminus \{a\}} \beta_U + \gamma_U - 2 \min( \beta_U, \gamma_U) = \sum_{U \subseteq A \setminus \{a\}} |\beta_U- \gamma_U|. \end{align*} $$

We now have to bound this expression in terms of differences of $\delta _B(U \cup \{z_1\})$ and $\delta _C(U \cup \{z_2\})$ . To do this we need to express $\beta _U$ and $\gamma _U$ in terms of the diversities evaluated on set. Equation (7) in [Reference Bryant, Nies and Tupper6, p. 12] gives the expression for the weights when $\lambda = \bar {\lambda }$ . We are only taking splits $U|\bar {U}$ where U doesn’t contain A. So we have to double the weight in that paper. We get, for all $U \subseteq A$ , $a \not \in U$ :

$$ \begin{align*} \beta_U = \sum_{V: U\subseteq V, V \subseteq A} (-1)^{|U|-|V|+1} (\delta(V)- \delta(V \cup\{z_1\})). \end{align*} $$

$$ \begin{align*} \gamma_U = \sum_{V: U\subseteq V, V \subseteq A} (-1)^{|U|-|V|+1} (\delta(V)- \delta(V \cup\{z_2\})). \end{align*} $$

This gives us

$$ \begin{align*} \delta_D(\{z_1,z_2\}) & = \sum_{U \subseteq A \setminus \{a\}} \left| \sum_{V: U\subseteq V, V \subseteq A} (-1)^{|U|-|V|+1} (\delta(V \cup \{z_1\})- \delta(V \cup\{z_2\})) \right| \\ &\leq \sum_{U \subseteq A \setminus \{a\}} \sum_{V: U\subseteq V, V \subseteq A} \left|\delta(V \cup \{z_1\})- \delta(V \cup\{z_2\}) \right| \\ &\leq 2^{2n} \max_{V \subseteq A} \left|\delta(V \cup \{z_1\})- \delta(V \cup\{z_2\}) \right| \end{align*} $$

as required.

PP. We follow the exact same argument as in Theorem 24, noting that $L_1$ diversities also can be viewed as a closed subset of $\mathbb {R}^k$ for large enough k. We only need to establish the analogue of Lemma 25 for $L_1$ diversities. The inequality $d_{\infty }(\bar {a},\bar {b}) \leq n d_{\mathcal {K}}(\bar {a},\bar {b})$ follows exactly as in Lemma 25. To get a bound on $d_{\mathcal {K}}(\bar {a},\bar {b})$ in terms of $d_{\infty }(\bar {a},\bar {b})$ we use bAP for $L_1$ diversities repeatedly.

First, suppose that $d_{\infty }(\bar {a},\bar {b})=\epsilon $ . We will construct a joint embedding of $\bar {a}$ and $\bar {b}$ into a new $L_1$ diversity where corresponding points in the tuples are never further than $2^{2n} \epsilon $ from each other.

First we identify $a_1$ and $b_1$ . Consider the two tuples $(a_1,b_1,a_2)$ , $(a_1,b_1,b_2)$ . Since $d_{\infty }(\bar {a},\bar {b})=\epsilon $ , we know that $d_{\infty }((a_1,b_1,a_2),(a_1,b_1,b_2)) \leq \epsilon $ , and so be can use bAP for $L_1$ diversities to obtain a joint embedding $(a_1,b_1,a_2,b_2)$ where $d(a_2,b_2)\leq 2^{2n} \epsilon $ . We repeat this step for the tuples $(a_1,b_1,a_2,b_2,a_3)$ and $(a_1,b_1,a_2,b_2,b_3)$ , and so forth. In the end we have a joint embedding of all the points in $\bar {a}$ and $\bar {b}$ such that $d(a_i, b_i) \leq 2^{2n} \epsilon $ for all $i= 1, \ldots , k$ . Thus we have obtained

$$ \begin{align*} \frac{1}{n} d_{\infty}(\bar{a},\bar{b}) \leq d_{\mathcal{K}}(\bar{a},\bar{b}) \leq 2^{2n} d_{\infty} (\bar{a},\bar{b}), \end{align*} $$

as required.

CP. This follows exactly like the proof of the property CP in Theorem 24, the restriction to $L_1$ diversities not making any difference.⊣