ON TURBULENT RELATIONS

JESÚS A. ÁLVAREZ LÓPEZ AND ALBERTO CANDEL

ABSTRACT. This paper extends the theory of turbulence of Hjorth to certain classes of equivalence relations that cannot be induced by Polish actions. It applies this theory to analyze the quasi-isometry relation and finite Gromov-Hausdorff distance relation in the space of isometry classes of pointed proper metric spaces, called the Gromov space.

# 1. INTRODUCTION

The Gromov space, denoted here by $M_*$, is the set of isometry classes of pointed proper metric spaces endowed with the Gromov-Hausdorff topology, a Polish topology which resembles the compact-open topology on the space of continuous functions on $\mathbb{R}$ [4]. The space $M_*$ supports several equivalence relations of interest in geometry and dynamics: that of being (coarsely) quasi-isometric, of being at finite Gromov-Hausdorff distance, of being bi-Lipschitz equivalent, among others. Their dynamic complexity is reminiscent of the complexity exhibited by the turbulent group actions of Hjorth [5]. Understanding the structure of those relations on $M_*$ was the motive for working out the theory of turbulent relations presented in this paper, whose contents are presently described, section by section.

In Section 2, we discuss the concept of lower semicontinuity of relations on topological spaces and analyze their topological properties. These are rather elementary, but are not readily found in the literature. The goal of that analysis is to obtain a new version (Theorem 2.14) of the Kuratowski-Ulam theorem [10], which will be used to describe how topological properties of a subset of a space on which an equivalence relation is defined translate to properties of the intersection of that set with the orbits of the equivalence relation.

In Section 3, we review the basic concepts of classification of equivalence relations. Complexity of an equivalence relation is quantified by comparing that relation with one of the standard examples, like the identity relation,

<footnote n="2010">2010 Mathematics Subject Classification. Primary 03E15; Secondary 54H05, 54H20, 54E50.</footnote>

<footnote>Key words and phrases. Turbulence, generic ergodicity, classification, countable models, uniform equivalence relation, metric equivalence relation, Gromov space, Gromov-Hausdorff metric, quasi-isometry.</footnote>
$\Delta_X$, on a space $X$, or the orbit relation, $E_G^X$, on a $G$-space $X$. Two concepts used for describing the relative complexity of two equivalence relations, $E$ on $X$ and $F$ on $Y$, are reducibility and generic ergodicity. The relation $E$ is Borel reducible to $F$, denoted by $E \le_B F$, if there is an $(E, F)$-invariant Borel mapping $\theta: X \to Y$ such that the induced quotient mapping $\bar{\theta}: X/E \to Y/F$ is injective. The relation $E$ is generically $F$-ergodic if for any $(E, F)$-invariant Borel mapping $\theta: X \to Y$ there is a residual set $C \subseteq X$ which is a union of equivalence classes and such that the mapping $\bar{\theta}: C/E \to Y/F$ is constant.

The less complex equivalence relations, called smooth or concretely classifiable, are those Borel reducible to the identity relation on a standard Borel space. For example, the equivalence relation of being isometric in the space of compact metric spaces is smooth because the space of equivalence classes of this relation is itself a Polish metric space when endowed with the Gromov-Hausdorff metric.

At a higher level of complexity are the equivalence relations classifiable by isomorphism classes of countable structures (a structure on the natural numbers that is determined by countably many relations). The set of countable structures is endowed with a Polish topology and a continuous action of $S_\infty$, the Polish group of permutations of the natural numbers, so that two countable structures are isomorphic if and only if they are in the same orbit of this $S_\infty$-action. An equivalence relation over a Borel space is then classifiable by countable structures if it is Borel reducible to the orbit relation of the action of $S_\infty$ on the space of countable structures. A variety of examples of equivalence relations classifiable by countable structures and which arise in dynamical systems are given in Kechris [8] and Hjorth [5].

Among the equivalence relations that are not classifiable by countable structures are those that are generically $E_{S_\infty}^Y$-ergodic for every Polish $S_\infty$-space. A key concept for analyzing those Polish group actions that are of this latter type is that of turbulence, introduced by Hjorth [5]. A turbulent Polish group action is highly complex: its orbits are dense and meager, and its local orbits are somewhere dense (a local orbit is the orbit of a local action induced by an open neighborhood of the identity on an open subset of the space). If a Polish action of $G$ on $X$ is turbulent, then its orbit relation, $E_G^X$, is generically $E_{S_\infty}^Y$-ergodic for any Polish $S_\infty$-space $Y$ [5, Theorem 3.18]; in particular, $E_G^X$ is not classifiable by isomorphism classes of countable structures. Moreover, Hjorth [6] also proved that if $E_G^X$ is Borel in $X \times X$, then $E_G^X$ is not classifiable by isomorphism classes of countable
structures if and only if $X$ admits a continuous $G$-embedding of a turbulent Polish $G$-space.

The relations on $M_*$ of being at finite Gromov-Hausdorff distance and of being quasi-isometric are not reducible to an equivalence relation given by a Polish group action [1], and so they are not classifiable by isomorphism classes of countable structures. But that does not say whether they are generically $E_{S_\infty}^Y$-ergodic for any Polish $S_\infty$-space $Y$. This could be determined by amplifying the concept of turbulence to include equivalence relations other than those given by group actions, which is carried out in Section 4 for what we call uniform equivalence relations.

In Section 4, we define a uniform equivalence relation as a pair, $(\mathcal{V}, E)$, consisting of a uniformity $\mathcal{V}$ with a distinguished entourage $E$ which is an equivalence relation. A first example of this type of structure is the orbit relation, $E_G^X$, on a Polish $G$-space $X$. The uniformity $\mathcal{V}$ on $X$ is generated by the entourages $\{(x, gx) \mid x \in X, g \in W\}$, where $W$ belongs to the neighborhood system of the identity of $G$, and the equivalence relation $E$ is $E_G^X$. A second example is what we call a metric equivalence relation. This arises from a distance-like mapping, $d: X \times X \to [0, \infty]$, which may take infinite values; the uniformity $\mathcal{V}$ is generated by the entourages $\{(x, x') \mid d(x, x') < \epsilon\}$ and the equivalence relation $E_d$ is given by $xE_dy$ if and only if $d(x, y) < \infty$.

Taking Polish actions as model, a uniform equivalence relation, $(\mathcal{V}, E)$, on a space, $X$, will be called turbulent when the equivalence classes of $E$ are dense and meager, and the local equivalence classes of $E$ are somewhere dense (a local equivalence class is an equivalence class of the relation on an open set $U \subseteq X$ generated by $(U \times U) \cap V$, for an entourage $V$ of $\mathcal{V}$).

In Section 5, we introduce a class of metric equivalence relations, which we call type I, and show that for any Polish $S_\infty$-space $Y$, a turbulent, type I relation is generically $E_{S_\infty}^Y$-ergodic. The results and proofs in this section follow closely Hjorth's work, adapted to metric equivalence relations by using the concepts and preliminary results developed in earlier sections.

In Section 6, we give a sequence of hypothesis that collectively will guarantee that a metric equivalence relation satisfying them is of type I and turbulent.

In Section 7, as a prelude to the analysis of the “turbulent dynamics” of $M_*$, we study the metric equivalence relation $(d_\infty, E_\infty)$ on $C(\mathbf{R})$ defined by the supremum distance, where $C(\mathbf{R})$ is equipped with the compact-open topology.
In Section 8, we review the construction of $M_*$ and the pointed Gromov-Hausdorff distance with possible infinite values, $d_{GH}$, between isometry classes of pointed proper metric spaces. This distance defines the relation, $E_{GH}$, on $M_*$ given by being at finite Gromov-Hausdorff distance. We also analyze the relation, $E_{QI}$, on $M_*$ given by being quasi-isometric, showing in particular that it is induced by a distance-like function, $d_{QI}$, on $M_*$. In Sections 9 and 10, we study the metric equivalence relations given by $(d_{GH}, E_{GH})$ and $(d_{QI}, E_{QI})$ on $M_*$. Our work is summarized thus:

**Theorem 1.1.** If $(d, E)$ is $(d_\infty, E_\infty)$, $(d_{GH}, E_{GH})$ or $(d_{QI}, E_{QI})$, then:

(i) The metric equivalence relation $(d, E)$ is turbulent.

(ii) $E$ is generically $E_{S_\infty}^Y$-ergodic for every Polish $S_\infty$-space $Y$.

When $Y$ is the $S_\infty$-space of countable structures, part (ii) of this theorem may be seen as a validation, for proper metric spaces, of the so-called Gromov's principle: "No statement about all finitely presented groups is both non-trivial and true."

## 2. LOWER SEMicontinuous relations

A relation, $E$, from a set, $X$, to a set, $Y$, is a set $E \subseteq X \times Y$. If $X = Y$, then $E$ is said to be a relation on $X$. The notation $xEy$ means $(x, y) \in E$.

For a relation $E \subseteq X \times Y$ and a subset $A \subseteq X$, let

$$E(A) = \{y \in Y \mid \exists x \in A \text{ such that } xEy\}.$$

If $A = \{x\}$ is a singleton, then we write $E(x)$ for $E(\{x\})$. This set $E(x)$ (which could possibly be empty) is called the *fiber* of $E$ on $x$.

The inverse of a relation, $E \subseteq X \times Y$, is the relation $E^{-1} \subseteq Y \times X$ given by: $\forall y \in Y, \forall x \in X, yE^{-1}x$ if and only if $xEy$.

**Definition 2.1.** A relation, $E$, from a topological space, $X$, to a topological space, $Y$, is called *lower semicontinuous* (l.s.c., for short) if, for every open $V \subseteq Y$, the set $E^{-1}(V)$ is open in $X$ (where $E^{-1}$ is the inverse of $E$).

**Definition 2.2.** A relation from a topological space to a topological space is called *inversely lower semicontinuous* (inversely l.s.c., for short) if its inverse relation is lower semicontinuous, and it is called *bi-lower semicontinuous* (bi-l.s.c., for short) if it and its inverse are both lower semicontinuous.

**Example 2.3.** (i) If $E$ is the graph of a map $f: X \to Y$, then $E$ (respectively, $E^{-1}$) is l.s.c. just when $f$ is continuous (respectively, open). In particular, the diagonal $\Delta_X \subseteq X \times X$ is a bi-l.s.c. relation over $X$ because it is the graph of the identity of $X$.
(ii) If $E \subseteq X \times Y$ is an open subset, then $E$ is a bi-l.s.c. relation.

(iii) If $E$ is an l.s.c. relation from $X$ to $Y$, $A \subseteq X$, and $V \subseteq Y$ is open in $Y$, then $E \cap (A \times V)$ is an l.s.c. relation from $A$ to $V$.

(iv) If $E \subset U \times B$ is an l.s.c relation from $U$ to $B$, $U \subseteq X$ is open, and $B \subseteq Y$, then $E$ is an l.s.c. relation from $X$ to $Y$.

(v) Since $(E^{-1})^{-1} = E$, $E$ is inversely l.s.c. if and only if, for every open set $U \subseteq X$, the set $E(U)$ is open in $Y$.

(vi) For a symmetric relation $(E = E^{-1})$ on a topological space, being l.s.c., being inversely l.s.c., and being bi-l.s.c. are equivalent properties. In particular, the orbit relation of a continuous group action is bi-l.s.c.

**Lemma 2.4.** Let $X, Y$ be topological spaces, and let $\pi_X$ be the projection of $X \times Y$ onto $X$. A relation $E \subseteq X \times Y$ is l.s.c. if and only if the restriction $\pi_X|_E : E \to X$ is an open mapping.

*Proof.* This follows at once from the fact that if $A \subseteq X$ and $B \subseteq Y$, then $A \cap E^{-1}(B) = \pi_X|_E(E \cap (A \times B))$. For the “if” part, take $A = X$ and $B$ open in $Y$. For the “only if” part, use that every open subset of $E$ is a union of sets of the form $E \cap (U \times V)$, where $U$ and $V$ are open in $X$ and $Y$, respectively. $\square$

The following is a direct consequence of the definitions.

**Lemma 2.5.** The union of a set of l.s.c. (respectively, bi-l.s.c.) relations from $X$ to $Y$, is an l.s.c. (respectively, a bi-l.s.c.) relation from $X$ to $Y$.

**Remark 2.6.** The intersection of two l.s.c. relations need not be l.s.c. For example, if $E, F \subset \mathbf{R} \times \mathbf{R}$ are given by the graphs of two distinct linear maps, then $E \cap F$ is not l.s.c.

However, the intersection of two l.s.c. relations is l.s.c. when one of them is also an open subset.

**Lemma 2.7.** Let $F \subseteq X \times Y$ be an open set. If $E \subset X \times Y$ is l.s.c. (respectively, bi-l.s.c.), then so is $E \cap F$.

*Proof.* Since $F \subseteq X \times Y$ is open, the inclusion $i_{E \cap F} : E \cap F \to E$ is open, and because of this and Lemma 2.4, the composite $i_{E \cap F} \circ \pi_X|_E = \pi_X|_{E \cap F}$ is open. The bi-l.s.c. case is analogous. $\square$

The composition of two relations, $E \subseteq X \times Y$ and $F \subseteq Y \times Z$, is the relation $F \circ E \subseteq X \times Z$ given by

$$F \circ E = \{(x, z) \in X \times Z \mid \exists y \in Y \text{ such that } xEy \text{ and } yFz\}.$$
Composition of relations is an associative operation and $\Delta_X$ is the identity at $X$. Moreover

$$ (2.1) \qquad (F \circ E)^{-1} = E^{-1} \circ F^{-1}. $$

If $E' \subseteq X' \times Y'$ is another relation on topological spaces, let $E \times E'$ be the relation from $X \times X'$ to $Y \times Y'$ given by

$$ E \times E' = \{(x, x', y, y') \in X \times X' \times Y \times Y' \mid xEy \text{ and } x'E'y'\}. $$

Note that

$$ (2.2) \qquad (E \times E')^{-1} = E^{-1} \times E'^{-1}. $$

For relations $E \subseteq X \times Y$ and $G \subseteq X \times Z$, let $(E, G)$ denote the relation from $X$ to $Y \times Z$ given by

$$ (E, G) = \{(x, y, z) \in X \times Y \times Z \mid xEy \text{ and } xGz\}. $$

**Lemma 2.8.** Let $E, E', F$, and $G$ be relations as above.

(i) If $E$ and $F$ are l.s.c. (respectively, bi-l.s.c.), then so is $F \circ E$.

(ii) If $E$ and $E'$ are l.s.c. (respectively, bi-l.s.c.), then so is $E \times E'$.

(iii) If $E$ and $G$ are l.s.c., then so is $(E, G)$.

*Proof.* The statements about lower semicontinuity follow from the formulas

$$ \begin{align*} (F \circ E)^{-1}(W) &= E^{-1}(F^{-1}(W)), \\ (E \times E')^{-1}(V \times V') &= E^{-1}(V) \times E'^{-1}(V'), \\ (E, G)^{-1}(V \times W) &= E^{-1}(V) \cap G^{-1}(W), \end{align*} $$

for $W \subseteq Z$, $V \subseteq Y$ and $V' \subseteq Y'$. The statements about bi-lower semicontinuity in (i) and (ii) follow from (2.1) and (2.2). $\square$

**Lemma 2.9.** Let $X$ and $Y$ be topological spaces, with $Y$ second countable. If $E, F \subseteq X \times Y$ are l.s.c. relations and $E \subseteq F$, then

$$ \{x \in X \mid E(x) \text{ is dense in } F(x)\} $$

is a Borel subset of $X$, and it is a $G_\delta$-set in $X$ if $F = X \times Y$.

*Proof.* Let $\mathcal{B}$ be a countable base, consisting of non-empty open sets, for the topology of $Y$. Then

$$ \{x \in X \mid E(x) \text{ is dense in } F(x)\} $$

$$ \begin{align*} &= \bigcap_{V \in \mathcal{B}} \{x \in X \mid x \in F^{-1}(V) \Rightarrow x \in E^{-1}(V)\} \\ &= \bigcap_{V \in \mathcal{B}} (E^{-1}(V) \cup (X \setminus F^{-1}(V))), \end{align*} $$
the intersection of countably many Borel subsets of X which are open if $F = X \times Y$ (and then are equal to $E^{-1}(V)$, $V \in \mathcal{B}$). $\square$

The following concepts and notation will be used frequently.

**Definition 2.10.** (i) A subset of a topological space is called *meager* if it is the countable union of nowhere dense subsets.

(ii) A subset of a topological space is called *residual* if it contains the intersection of countably many open, dense subsets.

(iii) A subset of a topological space has the *Baire property* if it differs from an open set by a meager set.

(iv) A topological space is called *Baire* if every residual subset is dense.

**Definition 2.11.** Let $\mathcal{P}$ be a property that members of sets may or may not satisfy. Let $X$ be a topological space.

(i) Property $\mathcal{P}$ is satisfied by *residually many* members of $X$, and denoted by $(\forall^*x \in X) \mathcal{P}(x)$, if the set $\{x \in X \mid \mathcal{P}(x)\}$ is residual in $X$.

(ii) Property $\mathcal{P}$ is satisfied by *non-meagerly many* members of $X$, and denoted by $(\exists^*x \in X) \mathcal{P}(x)$, if the set $\{x \in X \mid \mathcal{P}(x)\}$ is non-meager.

**Lemma 2.12.** Let $E \subseteq X \times Y$ be an inversely l.s.c. relation. If $A \subseteq B \subseteq Y$ and $A$ is dense in $B$, then $E^{-1}(A)$ is dense in $E^{-1}(B)$.

*Proof.* Let $O$ be an open subset of $X$. Since $E$ is open, $E(O)$ is open in $Y$, and because $A$ dense in $B$,

$$O \cap E^{-1}(B) \neq \emptyset \iff E(O) \cap B \neq \emptyset \\ \implies E(O) \cap A \neq \emptyset \iff O \cap E^{-1}(A) \neq \emptyset. \quad \square$$

**Lemma 2.13.** Let $E \subset X \times Y$ be a bi-l.s.c. relation, and let $Y$ be second countable. If $B$ is open and dense in $Y$, then, $\forall^*x \in X$, $B \cap E(x)$ is open and dense in $E(x)$.

*Proof.* Let $\{V_n \mid n \in \mathbb{N}\}$ be a countable base for the topology of $Y$ and let

$$O_n = (X \setminus \overline{E^{-1}(V_n)}) \cup E^{-1}(V_n \cap B).$$

The boundary $\partial E^{-1}(V_n)$ is a meager set in $X$ because $E^{-1}(V_n)$ is open in $X$. Since $V_n \cap B$ is dense in $V_n$, Lemma 2.12 implies that $E^{-1}(V_n \cap B)$ is dense in $E^{-1}(V_n)$. Hence $O_n$ is open and dense in $X \setminus \partial E^{-1}(V_n)$ and thus in $X$. This proves that $\bigcap_{n \in \mathbb{N}} O_n$ is a residual subset of $X$. If $x$ is in $\bigcap_{n \in \mathbb{N}} O_n$, then $E(x) \cap B$ is dense in $E(x)$, for otherwise there would be some $V_n$ in the base for which $E(x) \cap B \cap V_n = \emptyset$ and $E(x) \cap V_n \neq \emptyset$, which conflicts with the definition of $O_n$. $\square$
The following is a generalization of the Kuratowski-Ulam Theorem [10].

**Theorem 2.14** (Cf. [7, Theorem 8.41]). Let $E \subset X \times Y$ be a bi-lower semicontinuous relation. Assume that $Y$ is second countable, and let $A \subseteq Y$ have the Baire property. The following properties are satisfied:

(i) $\forall^*x \in X, A \cap E(x)$ has the Baire property in $E(x)$;

(ii) if $A$ is meager in $Y$, then, $\forall^*x \in X, A \cap E(x)$ is meager in $E(x)$;

(iii) if $A$ is residual in $Y$, then, $\forall^*x \in X, A \cap E(x)$ is residual in $E(x)$.

In addition, if $X$ is a Baire space, $E(X)$ is dense in $Y$, and, $\forall^*x \in X, E(x)$ is a Baire space, the converses to (ii) and (iii) are also satisfied.

*Proof.* Lemma 2.13 implies (iii), which in turn implies (ii). For (i), if $A = U \Delta M$ for some meager set $M \subseteq Y$ and some open set $U \subseteq Y$, then, for all $x \in X, A \cap E(x)$ has the Baire property because

$$A \cap E(x) = (U \cap E(x)) \Delta (M \cap E(x)),$$

where $U \cap E(x)$ is open in $E(x)$, and, by (ii), $\forall^*x \in X, M \cap E(x)$ is meager in $E(x)$.

Assume now that $E(X)$ is dense in $Y$ and that, $\forall^*x \in X, E(x)$ is a Baire space. Let $A \subseteq Y$ be non-meager and have the Baire property. By [7, Proposition 8.26], there is a non-empty open $U \subseteq Y$ such that $A \cap U$ is residual in $U$; hence, by (iii), $\forall^*x \in X, A \cap U \cap E(x)$ is residual in $U \cap E(x)$. By [7, Proposition 8.22], $A \cap U$ has the Baire property in $X$, and thus in $U$; hence, by (i), $\forall^*x \in X, A \cap U \cap E(x)$ has the Baire property in $U \cap E(x)$. Because $E$ is l.s.c. and $E(X)$ is dense in $Y$, $E^{-1}(U)$ is an open non-empty subset of $X$. Since, $\forall^*x \in X, E(x)$ is also a Baire space, it follows from [7, Proposition 8.26] that, $\forall^*x \in E^{-1}(U), A \cap E(x)$ is not meager in $E(x)$. Thus $\exists^*x \in X$ such that $A \cap E(x)$ is not meager in $E(x)$, by [7, Proposition 8.26] since $X$ is a Baire space. This proves the converse of (ii), which in turn implies the converse of (iii). $\square$

**Corollary 2.15.** Let $X$ and $Y$ be second countable, Baire spaces, and let $E \subseteq X \times Y$ be a bi-l.s.c. relation. Suppose that $E$ is a Baire space and that $\forall^*x \in X, \forall^*y \in Y, E(x)$ and $E^{-1}(y)$ are Baire spaces. If $F \subseteq E$ has the Baire property in $E$, then, $\forall^*x \in X, \text{ the set } F(x)$ is residual in $E(x)$ if and only if, $\forall^*y \in Y, \text{ the set } F^{-1}(y)$ is residual in $E^{-1}(y)$.

*Proof.* Lemma 2.4 implies that the restrictions of the projections $\pi_X$ and $\pi_Y$ to $E$ are open mappings. By Example 2.3 (i), their graphs, $\Pi_{E,X} \subseteq E \times X$ and $\Pi_{E,Y} \subseteq E \times Y$, are bi-l.s.c. relations, and $\Pi_{E,X}^{-1}(X) = \Pi_{E,Y}^{-1}(Y) = E$.
Moreover, for $x \in X$ and $y \in Y$,

$$ 
\begin{align*}
\Pi_{E,X}^{-1}(x) &= \{x\} \times E(x) \equiv E(x), \\
\Pi_{E,Y}^{-1}(y) &= E^{-1}(y) \times \{y\} \equiv E^{-1}(y), \\
F \cap \Pi_{E,X}^{-1}(x) &= \{x\} \times F(x) \equiv F(x), \\
F \cap \Pi_{E,Y}^{-1}(y) &= F^{-1}(y) \times \{y\} \equiv F^{-1}(y).
\end{align*}
$$

Therefore, by Theorem 2.14 first applied to the relation $\Pi_{E,X}^{-1} \subseteq X \times E$ and the subset $F \subseteq E$, and subsequently to the relation $\Pi_{E,Y}^{-1} \subset Y \times E$ and the subset $F \subseteq E$, we have

$$ 
\begin{array}{l}
\forall^* x \in X, F(x) \text{ is residual in } E(x) \\
\iff F \text{ is residual in } E \\
\iff \forall^* y \in Y, F^{-1}(y) \text{ is residual in } E^{-1}(y). \quad \square
\end{array}
$$

**Remark 2.16.** The classical Kuratowski-Ulam Theorem (loc. cit., cf. also [7, Theorem 8.41]) may be obtained from Corollary 2.15 with $E = X \times Y$.

**Corollary 2.17.** Let $X$ and $Y$ be second countable Baire spaces, and let $\{E_n \subseteq X \times Y \mid n \in \mathbb{N}\}$ be a countable set of bi-l.s.c. relations. The following properties hold:

(i) If $A \subseteq X$ and $B \subseteq Y$ are residual subsets, then there are residual subsets $C \subseteq A$ and $D \subseteq B$ such that, for all $x \in C$, all $y \in D$ and all $n \in \mathbb{N}$, $D \cap E_n(x)$ is residual in $E_n(x)$ and $C \cap E_n^{-1}(y)$ is residual in $E_n^{-1}(y)$.

(ii) If $X = Y$ and $A \subseteq X$ is a residual subset, then there is a residual subset $C \subseteq A$ such that, for all $x \in C$ and all $n \in \mathbb{N}$, $C \cap E_n(x)$ is residual in $E_n(x)$.

*Proof.* To prove (i), define residual subsets, $C_i \subseteq X$ and $D_i \subseteq Y$, $i \in \mathbb{N}$, by the following induction process on $i \in \mathbb{N}$. Set $C_0 = A$ and $D_0 = B$. Assuming that $C_i$ and $D_i$ have been defined, let

$$ 
\begin{align*}
C_{i+1} &= \{x \in X \mid \forall n \in \mathbb{N}, D_i \cap E_n(x) \text{ is residual in } E_n(x)\}, \\
D_{i+1} &= \{y \in Y \mid \forall n \in \mathbb{N}, C_i \cap E_n^{-1}(y) \text{ is residual in } E_n^{-1}(y)\}.
\end{align*}
$$

By Theorem 2.14, for all $i \in \mathbb{N}$, $C_i$ is residual in $X$ and $D_i$ is residual in $Y$, and therefore $C = \bigcap_{i \in \mathbb{N}} C_i$ is residual in $A$ and $D = \bigcap_{i \in \mathbb{N}} D_i$ is residual in $B$ because $A$ and $B$ are dense in $X$ and $Y$, respectively, since $X$ and $Y$ are Baire spaces. Moreover, for all $n \in \mathbb{N}$, all $x \in C$ and all $y \in D$, $D \cap E_n(x) = \bigcap_{i \in \mathbb{N}} (D_i \cap E_n(x))$ is residual in $E_n(x)$, and $C \cap E_n^{-1}(y) = \bigcap_{i \in \mathbb{N}} (C_i \cap E_n^{-1}(y))$ is residual in $E_n^{-1}(y)$.
To prove (ii), let $C_0 = A$ and, assuming that $C_i$ has been defined, let

$$C_{i+1} = \{x \in X \mid \forall n \in \mathbb{N}, C_i \cap E_n(x) \text{ is residual in } E_n(x)\}.$$

By Theorem 2.14, for all $i \in \mathbb{N}$, $C_i$ is residual in $X$. Then $C = \bigcap_{i \in \mathbb{N}} C_i$ is residual in $A$ (because $A$ is dense in the Baire space $X$) and, for all $x \in C$ and all $n \in \mathbb{N}$, $C \cap E_n(x) = \bigcap_{i \in \mathbb{N}} (C_i \cap E_n(x))$ is residual in $E_n(x)$. $\square$

### 3. CLASSIFICATION AND GENERIC ERGODICITY

For a relation, $E \subseteq X \times X$, and positive integer $n$, $E^n$ denotes the $n$-fold composite relation $E \circ .^n \circ E$, and $E^0 = \Delta_X$. Relation $E$ is an equivalence relation if $E^{-1} = E$ and $E^2 = E$.

**Definition 3.1.** An equivalence relation on a topological space is called topologically transitive (respectively, topologically minimal) if some equivalence class is dense (respectively, every equivalence class is dense).

Let $X$ and $Y$ be topological spaces, and let $E \subseteq X \times X$ and $F \subseteq Y \times Y$ be equivalence relations. A mapping, $\theta: X \to Y$, is called $(E, F)$-invariant if, for all $x, x' \in X$,

$$xEx' \implies \theta(x)F\theta(x').$$

An $(E, F)$-invariant mapping $\theta: X \to Y$ induces a mapping, $\bar{\theta}: X/E \to Y/F$, between quotient spaces.

The relation $E$ is Borel reducible to $F$, written $E \leq_B F$, if there is an $(E, F)$-invariant Borel mapping $\theta: X \to Y$ such that, for all $x, x' \in X$,

$$xEx' \iff \theta(x)F\theta(x');$$

that is, such that the quotient mapping $\bar{\theta}: X/E \to Y/F$ is injective. If $E \leq_B F$ and $F \leq_B E$, then $E$ is said to be Borel bi-reducible with $F$, and is denoted by $E \sim_B F$.

The relation $E$ is generically $F$-ergodic if, for any $(E, F)$-invariant, Baire measurable mapping $\theta: X \to Y$, there is some residual saturated $C \subseteq X$ such that $\bar{\theta}: C/(E \cap (C \times C)) \to Y/F$ is constant.

**Remark 3.2.** If $E$ is a generically $F$-ergodic relation on $X$, then every equivalence relation on $X$ that contains $E$ is also generically $F$-ergodic.

The partial pre-order relation $\leq_B$ establishes a hierarchy on the complexity of equivalence relations on topological spaces. Two key ranks of this hierarchy are concretely classifiable (or smooth) relations and relations classifiable by countable structures. A relation, $E$, is said to be concretely classifiable if $E \leq_B \Delta_R$; this means that the equivalence classes of $E$ can be distinguished by some Borel mapping $X \to \mathbb{R}$.
**Theorem 3.3.** Let $X$ and $Y$ be second countable topological spaces. If $E$ is a topologically transitive, lower semicontinuous equivalence relation on $X$, then $E$ is generically $\Delta_Y$-ergodic.

*Proof.* Let $\theta: X \to Y$ be $(E, \Delta_Y)$-invariant and Baire measurable. By [7, Theorem 8.38], $\theta$ is continuous on some residual saturated set $C_0 \subseteq X$. By Lemma 2.9, and because $E$ is topologically transitive, there is residual saturated $C_1 \subseteq X$ such that, for all $x \in C_1$, $E(x)$ is dense in $X$. Then $C_0 \cap C_1$ is a residual subset of $X$ where $\theta$ is constant. $\square$

**Remark 3.4.** In the above proof, if $X$ is a Baire space, then $C_0 \cap C_1 \neq \emptyset$.

**Corollary 3.5** (Cf. [5, Theorem 3.2]). Let $X$ be a second countable space and let $E$ be a topologically transitive, l.s.c. equivalence relation on $X$. If $A \subseteq X$ is $E$-saturated and has the Baire property, then $A$ is either residual or meager.

*Proof.* Apply Theorem 3.3 to the characteristic function of $A$. $\square$

<figure><img src="image_1.png" /></figure>

**Corollary 3.6.** Let $X$ be a second countable Baire space and let $E$ be a topologically transitive, l.s.c. equivalence relation on $X$. If the equivalence classes of $E$ are meager subsets of $X$, then $E$ is not concretely classifiable.

*Proof.* By Theorem 3.3, each $(E, \Delta_R)$-invariant Borel map $\theta: X \to \mathbf{R}$ is constant on some residual saturated subset of $X$. So $\bar{\theta}: X/E \to \mathbf{R}/\Delta_R \equiv \mathbf{R}$ cannot be injective because $X$ is a Baire space and the equivalence classes are meager. $\square$

The second classification concept may be defined by using $\prod_{n=1}^{\infty} 2^{\mathbb{N}^n}$ endowed with the product topology, which is a Polish space. (Here $2$ is the discrete 2-point space and $2^A$ is the set of functions of the set $A$ into $2$.) Each element of $\prod_{n=1}^{\infty} 2^{\mathbb{N}^n}$ can be considered as a structure on $\mathbf{N}$ defined by a sequence $(R_n)$, where each $R_n$ is a relation on $\mathbf{N}$ with arity $n$. Two such structures are isomorphic when they correspond via some permutation of $\mathbf{N}$, which defines the isomorphism relation $\cong$ over $\prod_{n=1}^{\infty} 2^{\mathbb{N}^n}$. Then a relation $E$ is classifiable by countable structures if $E \le_B \cong$; that is, there is some Borel map $\theta: X \to \prod_{n=1}^{\infty} 2^{\mathbb{N}^n}$ such that $xEx'$ if and only if $\theta(x) \cong \theta(x')$.

The equivalence relation defined by the action of a group $G$ on a set $X$ will be denoted by $E_G^X$. The fiber $E_G^X(x)$ is the orbit of $x$ under $G$, and the notation $\mathcal{O}(x)$ will be used instead. If $G$ is a Polish group, the set of all relations defined by continuous actions of $G$ on Polish spaces has a maximum with respect to $\le_B$, which is unique up to $\sim_B$ and is denoted
by $E_G^\infty$ [2, 9]. As a special example, the group $S_\infty$ of permutations of $N$ becomes Polish with the topology induced by the product topology of $N^N$, where $N$ is considered with the discrete topology. Then the canonical action of $S_\infty$ on $\prod_{n=1}^\infty 2^{N^n}$ is a representative of $E_S^\infty$ [5].

Classification by countable structures and generic ergodicity for equivalence relations given by Polish actions are well understood by means of a dynamical concept called turbulence which was introduced by Hjorth [5].

### 4. TURBULENT UNIFORM RELATIONS

**Definition 4.1.** A uniform equivalence relation, or simply a uniform relation, on a set, $X$, is a pair, $(\mathcal{V}, E)$, consisting of a uniformity $\mathcal{V}$ on $X$ and an equivalence relation $E$ on $X$ such that $E \in \mathcal{V}$.

The pair $(\mathcal{V}, E)$ is determined by the entourages (members of $\mathcal{V}$) that are contained in $E$, and $\mathcal{V}$ induces a uniform structure on each equivalence class of $E$.

One important example of a uniform relation is that given by the action of a topological group, $G$, on a set, $X$. This is of the form $(\mathcal{V}, E_G^X)$, where $\mathcal{V}$ is the uniform structure on $X$ generated by the entourages

$$ (4.1) \qquad V_W = \{(x, gx) \mid x \in X, g \in W\}, $$

where $W$ belongs to the neighborhood system of the identity of $G$. Thus a uniform relation on a topological space can be considered as a generalized dynamical system.

Another important example of uniform relation arises as follows. A metric (or distance function) with possible infinite values on a set is a function $d: X \times X \to [0, \infty]$ satisfying the usual properties of a metric ($d$ is symmetric, equals 0 just on the diagonal of $X \times X$ and satisfies the triangle inequality). It defines an equivalence relation, $E_d^X$, on $X$ given by $x E_d^X y$ if and only if $d(x, y) < \infty$. There is a uniform relation induced by $d$ of the form $(\mathcal{V}, E_d^X)$, where $\mathcal{V}$ is the uniformity that has a base consisting of the entourages

$$ (4.2) \qquad V_\epsilon = \{(x, y) \in X \times X \mid d(x, y) < \epsilon\}. $$

The term metric equivalence relation (or metric relation) will be used for the pair $(d, E_d^X)$ (or even for $d$). Metrics with possible infinite values induce a topology on the underlying set which has a base of open sets consisting of open balls; unless otherwise indicated, the ball of center $x$ and radius $R$ will be denoted by $B_X(x, R)$ or $B_d(x, R)$, or simply by $B(x, R)$.
**Remark 4.2.** Let $d$ and $d'$ be two metric relations on $X$ that induce respective uniform relations $(\mathcal{V}, E)$ and $(\mathcal{V}', E')$. If $d' \le d$, then $\mathcal{V} \subseteq \mathcal{V}'$ and $E \subseteq E'$.

**Definition 4.3** (Cf. [5, Definition 3.15]). Let $(\mathcal{V}, E)$ be a uniform relation on a topological space $X$. For any non-empty open $U \subseteq X$ and any $V \in \mathcal{V}$ with $V \subseteq E$, the set

$$E(U, V) = \bigcup_{n=0}^{\infty} (V \cap (U \times U))^n$$

is an equivalence relation on $U$ that will be called a *local equivalence relation*. The $E(U, V)$-equivalence class of any $x \in U$ will be called a *local equivalence class* of $x$, and will be denoted by $E(x, U, V)$.

For a relation given by the action of a group $G$ on a space $X$, the local equivalence classes are called *local orbits* in Hjorth [5], and are denoted by $\mathcal{O}(x, U, W)$ instead of by $E_G^X(x, U, V)$ when $V$ is the $V_W$ of (4.1). For a uniform relation induced by a metric $d$ on a set $X$, $E_d^X(x, U, \epsilon)$ denotes $E_d^X(x, U, V)$ when $V$ is the $V_\epsilon$ of (4.2).

**Definition 4.4** (Cf. [5, Definition 3.13]). A uniform relation will be called *turbulent* if:

(i) every equivalence class is dense,

(ii) every equivalence class is meager, and

(iii) every local equivalence class is somewhere dense.

**Remark 4.5.** Definition 4.4 does not correspond exactly to the definition of turbulence for Polish actions introduced by Hjorth [5, Definition 3.13]. To generalize exactly Hjorth’s definition, condition (iii) of Definition 4.4 should be replaced with condition (iii’):

(iii’) every equivalence class meets the closure of each local equivalence class.

In fact, (i) already follows from (iii’). In the case of Polish actions, (iii) and (iii’) can be interchanged in the definition of turbulence by [5, Lemmas 3.14 and 3.16]; thus Definition 4.4 generalizes Hjorth’s definition. But in our setting, that equivalence is more delicate and our results become simpler by using (iii).

**Remark 4.6.** Let $(\mathcal{V}, E)$ and $(\mathcal{V}', E')$ be uniform relations on a topological space $X$ such that $\mathcal{V} \subseteq \mathcal{V}'$ and $E \subseteq E'$. If the local equivalence classes of $(\mathcal{V}, E)$ are somewhere dense (Definition 4.4 (iii)), then the local equivalence classes of $(\mathcal{V}', E')$ are also somewhere dense.
**Example 4.7.** The following examples illustrate the generalization of the concept of turbulence for uniform relations.

(i) If $E$ is an equivalence relation on a topological space $X$, then $\mathcal{V} = \{V \subseteq X \times X \mid E \subseteq V\}$ is a uniformity on $X$, and $(\mathcal{V}, E)$ is a uniform relation. Therefore $E$ is the only entourage of $\mathcal{V}$ contained in $E$, and $E(x, U, E) = E(x) \cap U$ for any open $U \subseteq X$ and all $x \in U$, so it follows that $(\mathcal{V}, E)$ is turbulent if the equivalence classes of $E$ are dense and meager.

(ii) Let $G$ be a first countable topological group whose topology is induced by a right invariant metric $d_G$. Suppose that $G$ acts continuously on the left on a topological space $X$. Then this action induces a pseudo-metric relation $d$ on $X$ with $E_d^X = E_G^X$ and

$$d(x, y) = \inf\{d_G(1_G, g) \mid g \in G, gx = y\}$$

for $(x, y) \in E_G^X$, where $1_G$ denotes the identity element of $G$. The pseudo-metric relation $d$ induces the same uniform relation as the action of $G$ on $X$, and therefore $d$ is turbulent if and only the action is turbulent.

(iii) Let $\mathbb{Z}$ be the additive group of integers with the discrete topology, and let $G \subseteq \mathbb{Z}^N$ denote the topological subgroup consisting of the sequences $(x_n)$ such that $x_n = 0$ for all but finitely many $n \in \mathbb{N}$. For some fixed irrational number $\theta$, consider the continuous action of $G$ on the circle $S^1 \equiv \mathbb{R}/\mathbb{Z}$ given by $(x_n) \cdot [r] = [r + \theta \sum_n x_n]$, where $[r]$ is the element of $S^1$ represented by $r \in \mathbb{R}$. The orbits of this action are dense and countable. For each $N \in \mathbb{N}$, the sets

$$W_N = \{(x_n) \in G \mid \forall n \in \{0, \dots, N\}, x_n = 0\}$$

are open and closed subgroups of $G$ which form a base of neighborhoods of the identity element. The induced action of each $W_N$ on $S^1$ has the same orbits as $G$; so $O([r], U, W_N) = U \cap O([r])$ for all open $U \subseteq S^1$ and each $[r] \in U$. It follows that this action is turbulent. In fact, the uniform equivalence relation induced by this action is of the type described in (i): we have $E_G^{S^1} \subseteq V$ for each entourage $V$. Moreover, for any invariant metric on $G$, the induced pseudo-metric relation $d$ on $S^1$ is determined by $d([r], [s]) = \infty$ if $O([r]) \neq O([s])$ and $d([r], [s]) = 0$ if $O([r]) = O([s])$. However, the action of $G$ on $S^1$ given by $(x_n) \cdot [r] = [r + \theta x_0]$ has the same orbits but is not turbulent: each point is a local orbit. Indeed this second action induces the same uniform equivalence
relation as the action of $\mathbb{Z}$ given by $x \cdot [r] = [r + \theta x]$, which is not turbulent because $\mathbb{Z}$ is locally compact.

**Definition 4.8** (Cf. [5, Definition 3.20]). A uniform relation $(\mathcal{V}, E)$ on a space $X$ will be called generically turbulent if:

(i) $\forall^* x \in X$, the equivalence class of $x$ is dense in $X$,

(ii) every equivalence class is meager, and

(iii) $\forall^* x \in X$, any local equivalence class of $x$ is somewhere dense.

A metric relation will be called (generically) turbulent if the induced uniform relation is (generically) turbulent.

## 5. TURBULENCE AND GENERIC ERGODICITY

From now on, we only consider metric relations on topological spaces because that suffices for the applications given in this paper. Certain restrictions on the topological structure of the space, and some compatibility of that structure with the metric relation will be required. These are given in the following definition; they are restrictive enough to prove the desired results, and general enough to be satisfied in our applications.

**Definition 5.1.** A metric relation, $d$, on a topological space, $X$, is said to be of type $I$ if:

(i) $X$ is Polish;

(ii) the topology induced by $d$ on $X$ is finer or equal than the topology of $X$; and

(iii) there is a set $\mathcal{E}$ of relations on $X$ such that:

(a) each $E \in \mathcal{E}$ is symmetric,

(b) each $E \in \mathcal{E}$ is a $G_\delta$ subset of $X \times X$,

(c) for each $r > 0$, there are some $E, F \in \mathcal{E}$ so that, for all $x \in X$,

$$E(x) \subseteq B_d(x, r) \subseteq F(x),$$

(d) for each $E \in \mathcal{E}$, there are some $r, s > 0$ so that

$$B_d(x, r) \subseteq E(x) \subseteq B_d(x, s)$$

for all $x \in X$,

(e) each $E \in \mathcal{E}$ is l.s.c., and

(f) for all $E, F, G \in \mathcal{E}$ and $x \in X$, if $E \circ F \supseteq G$ then $E \cap (F(x) \times G(x))$ is an inversely lower semicontinuous relation from $F(x)$ to $G(x)$.

In this case, $\mathcal{E}$ is called a witness (for $d$).

**Remark 5.2.** In Definition 5.1, observe the following:
(i) Each $E \in \mathcal{E}$ is a $G_\delta$ subset of $X \times X$ and, for each $x \in X$, $E(x) = E \cap (\{x\} \times X)$ is a $G_\delta$ subset of $X \equiv X \times \{x\}$. Therefore, by [7, Theorem 3.11], $E$ and $E(x)$ are Polish subspaces of $X \times X$ and $X$, respectively; in particular, they are Baire spaces.

(ii) Since $E_d^X = \bigcup_{E \in \mathcal{E}} E$, a metric relation of type I is l.s.c. by Lemma 2.5; however, its fibers need not be Polish spaces.

(iii) By properties (a) and (f) of the witness $\mathcal{E}$, for all $E, F, G \in \mathcal{E}$ and all $x \in X$, if $E \circ G \supseteq F$, then $E \cap (F(x) \times G(x))$ is a l.s.c. relation from $F(x)$ to $G(x)$.

(iv) It will be apparent that the general results presented in this paper hold if the metric equivalence relation is of type I only on some dense $G_\delta$ subset, but that generality will not be adopted because the conditions of Definition 5.1 are satisfied in the applications to be given.

(v) By property (d) of the witness $\mathcal{E}$, every $E \in \mathcal{E}$ contains the diagonal $\Delta_X$. So $E \circ F \supseteq F$, for all $E, F \in \mathcal{E}$.

**Lemma 5.3.** If a metric $d$ is of type I, then it has a witness $\mathcal{E} = \{E_n \mid n \in \mathbb{Z}\}$ consisting of countably many relations on $X$ such that, if $m < n$, then $E_m \subseteq E_n$.

*Proof.* Let $\mathcal{E}_0$ be a witness for $d$. For each $n \in \mathbb{Z}$, there is some $E_n \in \mathcal{E}_0$ so that

$$B_d(x, e^n) \subseteq E_n(x) \subseteq B_d(x, e^{n+1}).$$

Then $\mathcal{E} = \{E_n \mid n \in \mathbb{Z}\}$ is a witness for $d$ that satisfies the statement. $\square$

**Remark 5.4.** Any witness given by Lemma 5.3, $\mathcal{E} = \{E_n \mid n \in \mathbb{Z}\}$, satisfies condition (c) in the following form:

(c') for each $r > 0$, there are some $m \le n$ in $\mathbb{Z}$ so that, for all $x \in X$,

$$E_m(x) \subseteq B_d(x, r) \subseteq E_n(x).$$

**Lemma 5.5** (Cf. [5, Lemma 3.17]). Let $d$ be a metric relation of type I on a space $X$, and let $\mathcal{E} = \{E_n \mid n \in \mathbb{Z}\}$ be a witness for $d$ given by Lemma 5.3. Let $G$ be a Polish group and let $Y$ be a Polish $G$-space. If $\theta: X \to Y$ is an $(E_d^X, E_G^Y)$-invariant Borel map, then, for any neighborhood $W$ of the identity element $1_G$ in $G$, $\forall \ell \in \mathbb{Z}$, $\forall^*x \in X$, and $\forall^*x' \in E_\ell(x)$, there is some open neighborhood $U$ of $x$ in $X$ such that, $\forall k \in \mathbb{Z}$ and $\forall^*x'' \in U \cap E_k(x) \cap E_\ell(x')$, $\exists g \in W$ so that $g \cdot \theta(x) = \theta(x'')$.

*Proof.* Fix an open neighborhood $W$ of $1_G$ in $G$. The result follows from Corollary 2.15 and the following Claim 1.
**Claim 1.** $\forall \ell \in \mathbb{Z}, \forall x \in X$ and $\forall^*x' \in E_\ell(x)$, there exists some open neighborhood $U$ of $x'$ in $X$ such that, $\forall k \in \mathbb{Z}$ and $\forall^*x'' \in U \cap E_k(x') \cap E_\ell(x)$, $\exists g \in W$ so that $g \cdot \theta(x') = \theta(x'')$.

To prove this claim, let $W'$ be a symmetric open neighborhood of the identity $1_G \in G$ such that $W'^2 \subseteq W$. Since $G$ is a Polish group, there are countably many elements $g_i \in G, i \in \mathbb{N}$, such that $G \subseteq \bigcup_{i \in \mathbb{N}} W'g_i$. Therefore, given $\ell \in \mathbb{Z}$ and $x \in X$, the set $\theta(E_\ell(x)) \subseteq \bigcup_{i \in \mathbb{N}} W'g_i \cdot \theta(x)$. The pre-image of $W'g_i \cdot \theta(x)$ via the mapping $\theta: E_\ell(x) \to Y$ is analytic in $E_\ell(x)$ because $W'g_i \cdot \theta(x)$ is analytic [7, Proposition 14.4-(ii)]. Hence it has the Baire property [7, Theorem 21.6], and so there are open subsets $O_i \subseteq E_\ell(x)$ and residual subsets $C_i \subseteq O_i$ such that $\bigcup_i O_i$ is dense in $E_\ell(x)$ and $\theta(C_i) \subseteq W'g_i \cdot \theta(x)$. By using property (f) of the witness $\mathcal{E}$ and Remark 5.2 (iii),(v) applied to the relation $E_k \cap (E_\ell(x) \times E_\ell(x))$ on $E_\ell(x)$, and by Corollary 2.17 (ii) and Example 2.3 (iii), it follows that there is some residual $D_i \subseteq C_i$ such that, for all $x' \in D_i$ and $k \in \mathbb{Z}$, $E_k(x') \cap D_i$ is residual in $E_k(x') \cap O_i$.

The union $A = \bigcup_i D_i$ is residual in $E_\ell(x)$. If $x' \in A$, then $x' \in D_i$ for some $i$ and so $\theta(x') = g'g_i \cdot \theta(x)$ for some $g' \in W'$. Let $U$ be any open neighborhood of $x'$ in $X$ so that $U \cap E_\ell(x) \subseteq O_i$. Then, $\forall k \in \mathbb{N}, U \cap E_k(x') \cap D_i$ is residual in $U \cap E_k(x') \cap E_\ell(x)$. Moreover, for each $x'' \in E_k(x') \cap D_i$, there is $g'' \in W'$ so that $\theta(x'') = g''g_i \cdot \theta(x)$. Therefore, if

$$g = g''g'^{-1} \in W'W'^{-1} \subseteq W,$$

then

$$g \cdot \theta(x') = gg'g_i \cdot \theta(x) = g''g_i \cdot \theta(x) = \theta(x''),$$

which completes the proof of Claim 1. $\square$

<figure><img src="image_2.png" /></figure>

**Corollary 5.6.** Under the conditions of Lemma 5.5, for every neighborhood $W$ of the identity $1_G \in G$ and, $\forall^*x \in X$, $\exists k \in \mathbb{Z}$ such that, $\forall^*x' \in E_k(x)$, $\exists g \in W$ for which $g \cdot \theta(x) = \theta(x')$.

*Proof.* Let $\ell \in \mathbb{Z}$ and let $W$ be an open neighborhood of $1_G$ in $G$. Then, $\forall^*x \in X$ and $\forall^*x' \in E_\ell(x)$, let $U$ be an open neighborhood of $x$ in $X$ satisfying the statement of Lemma 5.5. By property (c') of the witness $\mathcal{E}$ (Remark 5.4), there is $k \le \ell$ so that $E_k(x) \subseteq U$, obtaining that, $\forall^*x'' \in E_k(x) \cap E_\ell(x')$, $\exists g \in W$ such that $g \cdot \theta(x) = \theta(x'')$. The statement follows from Theorem 2.14, property (f) of the witness $\mathcal{E}$ and Remark 5.2 (iii) with the relation $E_\ell \cap (E_\ell(x') \times E_k(x'))$ from $E_\ell(x')$ to $E_k(x')$. $\square$

<figure><img src="image_3.png" /></figure>
**Theorem 5.7** (Cf. [5, Theorem 3.18]). Let $d$ be a metric relation of type I on a space $X$ and let $Y$ be a Polish $S_\infty$-space. If there are residually many $x \in X$ for which every local equivalence class of $x$ is somewhere dense, then $E_d^X$ is generically $E_{S_\infty}^Y$-ergodic.

*Proof.* Let $\theta: X \to Y$ be an $(E_d^X, E_{S_\infty}^Y)$-invariant Borel map. Let $\mathcal{E} = \{E_n \mid n \in \mathbb{Z}\}$ be a witness for $d$ given by Lemma 5.3. The sets

$$W_N = \{h \in S_\infty \mid \forall \ell \le N, h(\ell) = \ell\},$$

with $N \in \mathbb{N}$, which are open and closed subgroups, form a base of neighborhoods of the identity $1_{S_\infty} \in S_\infty$. Define $I: X \times \mathbb{N} \to \mathbb{N} \cup \{\infty\}$ by setting $I(x, N)$ equal to the least $\ell \in \mathbb{N}$ such that, $\forall^* x' \in E_{-\ell}(x)$, $\exists h \in W_N$ so that $h \cdot \theta(x) = \theta(x')$ if there is such $\ell$, and setting $I(x, N) = \infty$ if there is not such $\ell$. Let $\mathbb{N}$ and $\mathbb{N} \cup \{\infty\}$ be endowed with the discrete topologies.

**Claim 2.** The map $I$ is Baire measurable.

Since $S_N = \{(y, h \cdot y) \mid y \in Y, h \in W_N\}$, $N \in \mathbb{N}$, is analytic in $Y \times Y$, and $E_{-\ell}$, $\ell \in \mathbb{N}$, is a Polish space by Remark 5.2 (i), the set $R_{\ell,N} = E_{-\ell} \cap (\theta \times \theta)^{-1}(S_N)$ is analytic in $E_{-\ell}$ [7, Proposition 14.4-(ii)], and therefore it has the Baire property [7, Theorem 21.6]. Hence there is an open set $U_{\ell,N} \subseteq E_{-\ell}$ such that $R_{\ell,N} \Delta U_{\ell,N}$ is meager in $E_{-\ell}$. The restriction $E_{-\ell} \to X$ of the first factor projection $X \times X \to X$ is continuous and open by Lemma 2.4, so its graph $\Pi_\ell \subseteq E_{-\ell} \times X$ is a bi-l.s.c. relation (Example 2.3 (i)). By Theorem 2.14 (ii), there is a residual set $D_{\ell,N} \subseteq X$ such that, $\forall x \in D_{\ell,N}$, $(R_{\ell,N} \Delta U_{\ell,N}) \cap \Pi_\ell^{-1}(x)$ is meager in $\Pi_\ell^{-1}(x)$. Note that $\Pi_\ell^{-1}(x) = \{x\} \times E_{-\ell}(x) \equiv E_{-\ell}(x)$ and

$$(R_{\ell,N} \Delta U_{\ell,N}) \cap \Pi_\ell^{-1}(x) = \{x\} \times (R_{\ell,N}(x) \Delta U_{\ell,N}(x)) \\ \equiv R_{\ell,N}(x) \Delta U_{\ell,N}(x).$$

Hence, $\forall x \in D_{\ell,N}$, $R_{\ell,N}(x) \Delta U_{\ell,N}(x)$ is meager in $E_{-\ell}(x)$. On the other hand,

$$I^{-1}(\{0, \dots, \ell\}) = \bigcup_{N=0}^{\infty} (Q_{\ell,N} \times \{N\}),$$

where

$$Q_{\ell,N} = \{x \in X \mid (E_{-\ell} \cap R_N)(x) \text{ is residual in } E_{-\ell}(x)\}.$$

Since

$$Q_{\ell,N} \cap D_{\ell,N} = \{x \in D_{\ell,N} \mid (E_{-\ell} \cap U_N)(x) \text{ is dense in } E_{-\ell}(x)\},$$

it follows that $Q_{\ell,N}$ has the Baire property in $X$ by Lemmas 2.7 and 2.9 (ii), and the proof of Claim 2 is finished.
By [7, Theorem 8.38], Claim 2, and Corollary 5.6, there is a dense $G_\delta$ subset $C_0 \subseteq X$ such that $\theta$ is continuous on $C_0$, $I$ is continuous on $C_0 \times \mathbf{N}$, and $I(C_0 \times \mathbf{N}) \subseteq \mathbf{N}$.

For $k \in \mathbf{Z}$, a non-empty open set $U \subseteq X$ and $x \in U$, define

$$ \mathcal{Q}(x, U, k) = \bigcup_{i=0}^{\infty} (E_k \cap (U \times U))^i(x). $$

The following properties are consequences of the properties (c') and (d) of the witness $\mathcal{E}$:

* for each $\epsilon > 0$, there is $k \in \mathbf{Z}$ such that $\mathcal{Q}(x, U, k) \subseteq E_d^X(x, U, \epsilon)$ for all $x \in U$, and

* for each $k \in \mathbf{Z}$, there is $\epsilon > 0$ such that $E_d^X(x, U, \epsilon) \subseteq \mathcal{Q}(x, U, k)$ for all $x \in U$.

Hence, by hypothesis, there is a residual set $C_1 \subseteq X$ such that, for any $U, x$ and $k$ as above, if $x \in C_1$, then $\mathcal{Q}(x, U, k)$ is somewhere dense. By Corollary 2.17 (ii), there is a residual set $C \subseteq C_0 \cap C_1$ such that, for all $x \in C$ and all $k \in \mathbf{Z}$, $E_k(x) \cap C$ is residual in $E_k(x)$.

Fix $x, y$ in $C$ and a complete metric inducing the topology of $Y$.

**Claim 3.** There exist sequences, $(x_i)$ and $(y_i)$ in $C$ with $x_1 = x$ and $y_1 = y$, $(g_i)$ and $(h_i)$ in $S_\infty$, $(U_i)$ and $(V_i)$ consisting of open subsets of $X$, and $(n_i)$ and $(k_i)$ in $\mathbf{N}$, such that:

(i) $g_i \cdot \theta(x) = \theta(x_i)$;

(ii) $h_i \cdot \theta(y) = \theta(y_i)$;

(iii) $x_{i+1} \in U_{i+1} \cap C \cap \mathcal{Q}(x_i, U_i, -n_i)$;

(iv) $y_{i+1} \in V_{i+1} \cap C \cap \mathcal{Q}(y_i, V_i, -k_i)$;

(v) $U_i \supseteq V_i \supseteq U_{i+1}$;

(vi) $\mathrm{diam}(\theta(U_i \cap C)) < 2^{-i}$;

(vii) $(U_{i+1} \cap C) \times \{N_{i+1}\} \subseteq I^{-1}(n_{i+1})$ for

$$ N_{i+1} = \max\{g_{i+1}(\ell), g_{i+1}^{-1}(\ell) \mid \ell \le i+1\}; $$

(viii) $(V_{i+1} \cap C) \times \{K_i\} \subseteq I^{-1}(k_i)$ for

$$ K_i = \max\{h_i(\ell), h_i^{-1}(\ell) \mid \ell \le i\}; $$

(ix) $g_{j+1}(\ell) = g_{i+1}(\ell)$ and $g_{j+1}^{-1}(\ell) = g_{i+1}^{-1}(\ell)$ for $\ell \le i+1 \le j+1$;

(x) $h_j(\ell) = h_i(\ell)$ and $h_j^{-1}(\ell) = h_i^{-1}(\ell)$ for $\ell \le i \le j$;

(xi) $\mathcal{Q}(x_i, U_i, -n_i) \cap V_i$ is dense in $V_i$; and

(xii) $\mathcal{Q}(y_i, V_i, -k_i) \cap U_{i+1}$ is dense in $U_{i+1}$.
If this assertion is true, then there exist $g = \lim_i g_i$ and $h = \lim_i h_i$ in $S_\infty$ by Claim 3 (ix),(x), and so $g \cdot \theta(x) = h \cdot \theta(y)$ by Claim 3 (i)–(vi), proving Theorem 5.7.

The construction of the sequences of Claim 3 is made by induction on $i \in \mathbb{N}$. Let $x_0 = x$, $U_0 = X$, $n_0 = 0$ and $g_0 = h_0 = 1_{S_\infty}$, and choose $V_0$ and $k_0$ so that $y \in V_0$ and

$$ (V_0 \cap C) \times \{0\} \subseteq I^{-1}(k_0). $$

Suppose that all the members of these sequences with indices $\le i \in \mathbb{N}$ have been constructed. Then $x_{i+1}$, $g_{i+1}$ and $U_{i+1}$ are constructed in the following manner. (The constructions of $y_{i+1}$, $h_{i+1}$ and $V_{i+1}$ are analogous.)

Let $U \subseteq V_i$ be a non-empty open set such that $Q(y_i, V_i, -k_i) \cap U$ is dense in $U$, and such that $\text{diam}(\theta(U \cap C)) < 2^{-i-1}$ (which is possible because $\theta$ is continuous on $C_0$). Choose $x_{i+1} \in Q(x_i, U_i, -n_i) \cap U$, and take $z_0, \dots, z_k \in U_i$ so that $z_0 = x_i$, $z_k = x_{i+1}$ and $z_a \in E_{-n_i}(z_{a-1})$ for $a \in \{1, \dots, k\}$. You may assume that $i > 0$ because (ix) does not restrict the choice of $g_1$.

**Claim 4.** We can assume that $z_a \in C$ for all $a \in \{0, \dots, k\}$.

Claim 4 is proved by showing that for each $a \in \{0, \dots, k\}$ there exists

$$ z'_{a} \in U_{i} \cap (E_{-n_{i}}^{k-a})^{-1}(U) \cap C $$

so that $z'_0 = x_i$ and, for $a \in \{1, \dots, k\}$, $z'_a \in E_{-n_i}(z'_{a-1})$; then we can choose $x'_{i+1} = z'_k$ instead of $x_{i+1}$, and $z'_a$ instead of $z_a$. We have

$$ z'_{0} = x_{i} \in U_{i} \cap (E_{-n_{i}}^{k})^{-1}(U) \cap C. $$

Suppose that $z'_a$ has been constructed for $a < k$. Since $z'_a \in C$ and $E_{-n_i}^{k-a-1}$ is l.s.c. by Lemma 2.8 (i), the set

$$ E_{n_i}(z'_a) \cap U_i \cap (E_{-n_i}^{k-a-1})^{-1}(U) \cap C $$

is residual in $E_{n_i}(z'_a) \cap U_i \cap (E_{-n_i}^{k-a-1})^{-1}(U)$. So, by Remark 5.2 (i), there is

$$ z'_{a+1} \in E_{n_i}(z'_a) \cap U_i \cap (E_{-n_i}^{k-a-1})^{-1}(U) \cap C, $$

as desired for the proof of Claim 4.

Continuing with the proof of Claim 3, Claim 4 gives $I(z_a, N_i) = n_i$ for all $a \in \{0, \dots, k\}$ by the induction hypothesis with Claim 3 (vii).

**Claim 5.** We can assume that, for each $a < k$, there exists some $f_a \in W_{N_i}$ such that $f_a \cdot \theta(z_a) = \theta(z_{a+1})$.

As in Claim 4, we show that the condition of this claim is satisfied by a new finite sequence of points

$$ z'_{a} \in U_{i} \cap (E_{-n_{i}}^{k-a})^{-1}(U) \cap C $$
so that $z'_0 = x_i$ and, for $a \in \{1, \dots, k\}$, $z'_a \in E_{-n_i}(z'_{a-1})$; in particular, $I(z'_a, N_i) = n_i$ as above. This new sequence is constructed by induction on $a$. First, let $z'_0 = x_i$, and suppose that $z'_a$ was constructed for all $a < k$. Since $I(z'_a, N_i) = n_i$, $\forall^* z \in E_{-n_i}(z'_a)$, $\exists f \in W_{N_i}$ so that $f \cdot \theta(z_a) = \theta(z)$. So the set of points

$$z \in E_{-n_i}(z'_a) \cap U_i \cap (E_{-n_i}^{k-a-1})^{-1}(U) \cap C$$

such that $\exists f \in W_{N_i}$ so that $f \cdot \theta(z_a) = \theta(z)$ is residual in

$$E_{-n_i}(z'_a) \cap U_i \cap (E_{-n_i}^{k-a-1})^{-1}(U) \cap C.$$

Hence $f_a \cdot \theta(z'_a) = \theta(z'_{a+1})$ for some $f_a \in W_{N_i}$ and some

$$z'_{a+1} \in E_{-n_i}(z'_a) \cap U_i \cap (E_{-n_i}^{k-a-1})^{-1}(P_U) \cap C$$

by Remark 5.2 (i), completing the proof of Claim 5.

According to Claim 5, $f_i^* \cdot \theta(x_i) = \theta(x_{i+1})$ for $f_i^* = f_{k-1} \cdots f_0 \in W_{N_i}$. Then let $g_{i+1} = f_i^* g_i$. Moreover we can take some open neighborhood $U_{i+1}$ of $x_{i+1}$ in $U$ and some $n_{i+1} \in \mathbb{N}$ such that $\text{diam}(\theta(U_{i+1} \cap C)) < 2^{-i-1}$ and

$$(U_{i+1} \cap C) \times \{N_{i+1}\} \subseteq I^{-1}(n_{i+1}),$$

where $N_{i+1}$ is defined according Claim 3 (vii). These choices of $x_{i+1}$, $g_{i+1}$, $U_{i+1}$ and $n_{i+1}$ satisfy the conditions of Claim 3. $\square$

**Remark 5.8.** The proofs of Lemma 5.5 and Theorem 5.7 are directly inspired by those of [5, Lemma 3.17 and Theorem 3.18].

## 6. A CLASS OF TURBULENT METRIC RELATIONS

In this section we introduce, consecutively, three hypotheses that apply to certain families of relations on a set, $X$. The first hypothesis allows to construct a metric, $d$, on $X$ satisfying parts of Definition 5.1; addition of the second suffices for $d$ to be of type I, and with the third $d$ becomes turbulent.

Let $X$ be a set, and let $\mathcal{U} = \{U_{R,r} \subseteq X \times X \mid R, r > 0\}$ be a set of relations on $X$ that satisfy the following hypothesis.

**Hypothesis 1.** (i) $\bigcap_{R,r>0} U_{R,r} = \Delta_X$;

(ii) each $U_{R,r}$ is symmetric;

(iii) if $R \le S$, then $U_{R,r} \supseteq U_{S,r}$ for all $r > 0$;

(iv) $U_{R,r} = \bigcup_{s<r} U_{R,s}$ for all $R, r > 0$; and

(v) there is some function $\phi : (\mathbb{R}_+)^2 \to \mathbb{R}_+$ such that, for all $R, S, r, s > 0$,

$$R \le \phi(R, r),$$

$$(R \le S, r \le s) \implies \phi(R, r) \le \phi(S, s),$$

$$U_{\phi(R,r+s),r} \circ U_{\phi(R,r+s),s} \subseteq U_{R,r+s}.$$
By Hypothesis 1, the sets $U_{R,r}$ form a base of entourages for a Hausdorff uniformity, denoted by $\mathcal{U}$, on $X$. This uniformity is metrizable because the entourages $U_{n,1/n}$, $n \in \mathbb{Z}_+$, form a countable base for it.

For each $r > 0$, let $E_r = \bigcap_{R>0} U_{R,r}$. This set is symmetric by Hypothesis 1 (ii); moreover

$$ (6.1) \qquad E_s \circ E_r \subseteq E_{r+s}, $$

for $r, s > 0$, by Hypothesis 1 (v).

**Lemma 6.1.** For $R, r > 0$ and $S = \phi(\phi(R, r), r)$ (where $\phi$ is the function given in Hypothesis 1-(v)), the set $U_{S,r} \subseteq \text{Int}(U_{R,r})$.

*Proof.* Let $(x, y) \in U_{S,r}$. By Hypothesis 1 (iv), there is some $r_0 < r$ such that $(x, y) \in U_{S,r_0}$. Let $r_1 = \frac{r - r_0}{2}$. By Hypothesis 1 (v),

$$ \begin{aligned} U_{S,r_1} \circ U_{S,r_0} \circ U_{S,r_1} &\subseteq U_{\phi(\phi(R,r), \frac{r+r_0}{2}), r_1} \circ U_{\phi(\phi(R,r), \frac{r+r_0}{2}), r_0} \circ U_{\phi(R,r), r_1} \\ &\subseteq U_{\phi(R,r), \frac{r+r_0}{2}} \circ U_{\phi(R,r), r_1} \subseteq U_{R,r}. \end{aligned} $$

So, by Hypothesis 1 (ii), $U_{S,r_1}(x) \times U_{S,r_1}(y) \subseteq U_{R,r}$, which implies that $(x, y) \in \text{Int}(U_{R,r}). \quad \square$

**Corollary 6.2.** For each $r > 0$, the set $E_r = \bigcap_{R>0} \text{Int}(U_{R,r})$.

Hypothesis 1 (iii) and Corollary 6.2 imply that $E_r = \bigcap_{n=1}^{\infty} \text{Int}(U_{n,r})$ for all $r > 0$ and so $E_r$ is a $G_\delta$ subset of $X \times X$. Hence the relations $E_r$ satisfy properties (a) and (b) of condition (iii) of Definition 5.1.

Let $d: X \times X \to [0, \infty]$ be defined by

$$ (6.2) \qquad d(x, y) = \inf\{r > 0 \mid (x, y) \in E_r\}, $$

where $\inf \emptyset = \infty$, so $d(x, y) = \infty$ if $x \notin \bigcup_{r>0} E_r(y)$. It follows from Hypothesis 1 that $d$ is a metric relation on $X$. Note also that, if $0 < r < s$,

$$ B_d(x, r) \subseteq E_r(x) \subseteq B_d(x, s), $$

and therefore

$$ (6.3) \qquad E_d^X = \bigcup_{r>0} E_r, $$

and $B_d(x, r) \subseteq U_{R,r}(x)$ for all $R, r > 0$ and all $x \in X$, which implies that the topology induced by $d$ on $X$ is finer than the topology induced by the uniformity $\mathcal{U}$ on $X$. Consequently, $d$ satisfies condition (ii) of Definition 5.1, and the relations $E_r$ satisfy the properties (c) and (d) of condition (iii) of Definition 5.1.
**Example 6.3.** Let $d_R, R > 0$, be pseudometrics on a set, $X$, such that

$$ (6.4) \qquad R \le S \implies d_R \le d_S, $$

$$ (6.5) \qquad (\forall R > 0, d_R(x, y) = 0) \implies x = y. $$

Then the sets

$$ U_{R,r} = \{(x, y) \in X \times X \mid d_R(x, y) < r\} $$

satisfy Hypothesis 1; in particular, Hypothesis 1 (v) holds with $\phi(R, r) = R$ since the triangle inequality of each $d_R$ and (6.4) give

$$ (6.6) \qquad U_{R,r} \circ U_{S,s} \subseteq U_{\min\{R,S\},r+s}, $$

for all $R, S, r, s > 0$. It follows that $U_{R,r}(x)$ is open for all $x \in X$ and all $R, r > 0$. In this case, the relations $U_{R,r}$ induce the topology defined by the set of pseudometrics $\{d_R\}$, and the corresponding sets $E_r$ define the metric relation $d = \sup_{R>0} d_R$.

For $d$ (the metric equivalence relation given by (6.2)) to satisfy the remaining conditions of Definition 5.1, further hypothesis are required.

**Hypothesis 2.** (i) $X$ is a Polish space (with the topology induced by the uniformity $\mathcal{U}$);

(ii) for all $R, r, s > 0$ and $x \in X$, if $y \in E_s(x)$, then there are some $T, t > 0$ such that $U_{T,t}(y) \subseteq E_s \circ U_{R,r}(x)$; and,

(iii) for all $r, s > 0$ and $x \in X$, if $y \in E_s(x)$ and $V$ is a neighborhood of $y$ in $X$, then there is a neighborhood $W$ of $y$ in $X$ such that

$$ E_r(W) \cap E_r(E_s(x)) \subseteq E_r(V \cap E_s(x)). $$

**Proposition 6.4.** If $\mathcal{U}$ satisfies also Hypothesis 2, then $d$ is of type I.

*Proof.* It only remains to show that the relations $E_r$ satisfy the properties (e) and (f) of condition (iii) of Definition 5.1.

Hypothesis 2 (ii) means that $E_s$ is inversely l.s.c. and so l.s.c. because it is symmetric.

Let $r, s, t > 0$, $x \in X$ and $y \in E_s(x)$. Suppose that $E_r \circ E_s \supseteq E_t$, and let $V$ be a neighborhood of $y$ in $X$. By Hypothesis 2 (iii), there is some open neighborhood $W$ of $y$ in $X$ such that

$$ E_r(W) \cap E_t(x) \subseteq E_r(W) \cap E_r(E_s(x)) \subseteq E_r(V \cap E_s(x)). $$

Since $E_r(W)$ is open in $X$, this proves that $E_r \cap (E_s(x) \times E_t(x))$ is an inverse-l.s.c. relation from $E_s(x)$ to $E_t(x)$. $\square$
**Remark 6.5.** In some applications, the following condition, which is stronger than Hypothesis 2 (ii), is satisfied: for all $R, r, s > 0$, there are some $T, t > 0$ such that $U_{T,t} \circ E_s \subseteq E_s \circ U_{R,r}$. This means that each $E_s$ is “uniformly inversely l.s.c.” (or “uniformly l.s.c.,” because it is symmetric).

The metric equivalence relation $d$ will be shown to be turbulent under the following additional hypothesis.

**Hypothesis 3.** (i) $E_d^X$ has more than one equivalence class;

(ii) for each $x, y$ in $X$ and each $R, r > 0$, there is $s > 0$ such that $U_{R,r}(x) \cap E_s(y) \neq \emptyset$; and

(iii) for each $x \in X$ and each $R, r > 0$, there are $S, s > 0$, a dense subset $\mathcal{D} \subseteq U_{S,s}(x) \cap E_d^X(x)$, and a $d$-dense subset of $\mathcal{D}$ such that every pair of points in $\mathcal{D}$ can be joined by a $d$-continuous path in $U_{R,r}(x)$.

**Lemma 6.6.** The relation $E_d^X$ is minimal.

*Proof.* This follows from Hypothesis 3 (ii) and (6.3). □

**Lemma 6.7.** If $r < s$, then, for all $x \in X$, $\overline{E_r(x)} \subseteq E_s(x)$.

*Proof.* If $y \in \overline{E_r(x)}$ and $R > 0$, then $U_{\phi(R,s),s-r}(y) \cap U_{\phi(R,s),r}(x) \neq \emptyset$. So $y \in \bigcap_{R>0} U_{R,s} = E_s(x)$ by Hypothesis 1 (ii),(v). □

**Lemma 6.8.** For all $x \in X$ and $r > 0$, $\mathrm{Int}(E_r(x)) = \emptyset$.

*Proof.* Suppose that $\mathrm{Int}(E_r(x)) \neq \emptyset$. Then, by (6.3) and Lemma 6.6, for each $y \in X$, there is $s > 0$ such that $E_s(y) \cap E_r(x) \neq \emptyset$. Therefore, by (6.1), $y \in E_{r+s}(x)$, and so, by (6.3), $X = E_d^X(x)$, contradicting Hypothesis 3 (i). □

**Proposition 6.9.** The relation $E_d^X$ is turbulent.

*Proof.* The relation $E_d^X$ is minimal by Lemma 6.6. Each equivalence class of $E_d^X$ is meager by Lemmas 6.7 and 6.8 and (6.3). Finally, the local equivalence classes of $E_d^X$ are somewhere dense because of Hypothesis 3 (iii). □

Theorem 5.7, and Propositions 6.4 and 6.9 have the following immediate consequence.

**Proposition 6.10.** For any Polish $S_\infty$-space $Y$, the relation $E_d^X$ is generically $E_{S_\infty}^Y$-ergodic.

**Remark 6.11.** If we also assume that, for all $r > 0$ and residually many $x, y \in X$, there exists $s_0 > 0$ such that, for all $s > s_0$, $E_s(y) \setminus E_r(x)$ is dense in $E_s(y)$, then the proof of [5, Theorem 8.2] can be adapted to show that $E_d^X \not\subseteq E_G^Y$ for any Polish group $G$ and any Polish $G$-space $Y$. However the proof is not given because, in the applications, this is proved in [1].
7. THE SUPREMUM METRIC RELATION

A concrete case of Example 6.3 is $C(\mathbf{R})$, the space of real valued continuous functions on $\mathbf{R}$ endowed with the compact-open topology, and the supremum metric relation, $d_\infty$, which is induced by the supremum norm, $\| \|_\infty$, defined by $\|f\|_\infty = \sup_{x \in \mathbf{R}} |f(x)|$. For each $R > 0$, let $d_R$ be the pseudometric on $C(\mathbf{R})$ induced by the seminorm $\| \|_R$ given by $\|f\|_R = \sup_{|x|<R} |f(x)|$. This set $\{d_R | R > 0\}$ of pseudometrics satisfies (6.4) and (6.5), and induces the compact-open topology of $C(\mathbf{R})$. Moreover $d_\infty = \sup_{R>0} d_R$. In this case, $U_{R,r}$ (respectively, $E_r$) consists of the pairs $(f,g)$ that satisfy $\|f-g\|_R < r$ (respectively, $|f(x)-g(x)| < r$ for all $x \in \mathbf{R}$).

Write $E_\infty = E_{d_\infty}^{C(\mathbf{R})}$, and $B_\infty(f,r) = B_{d_\infty}(f,r)$ for $f \in C(\mathbf{R})$ and $r > 0$. Then $fE_\infty g$ if and only if $f - g$ is bounded; in particular, the subset $C_b(\mathbf{R}) \subseteq C(\mathbf{R})$ consisting of all bounded functions is an equivalence class of $E_\infty$.

Theorem 1.1 for $(d_\infty, E_\infty)$ follows from Propositions 6.4 and 6.9–6.10 once Hypotheses 1–3 are shown to hold.

**Remark 7.1.** The sum of functions makes the space $C(\mathbf{R})$ into a Polish group, and $C_b(\mathbf{R})$ into a subgroup. The orbit relation of the action of $C_b(\mathbf{R})$ on $C(\mathbf{R})$ given by translation is $E_\infty$ and there is no Polish topology on $C_b(\mathbf{R})$ with respect to which this action is continuous [1].

For instance, consider the restriction of the compact-open topology to $C_b(\mathbf{R})$. Then the action of $C_b(\mathbf{R})$ on $C(\mathbf{R})$ is continuous, $C_b(\mathbf{R})$ is metrizable because $C(\mathbf{R})$ is completely metrizable, and $C_b(\mathbf{R})$ is separable because it contains $C_0(\mathbf{R})$, which is dense in $C(\mathbf{R})$ and separable (by the Stone-Weierstrass theorem). But $C_b(\mathbf{R})$ is not completely metrizable with the compact-open topology; in particular, it is not closed in $C(\mathbf{R})$.

Consider now the topology on $C_b(\mathbf{R})$ induced by $\| \|_\infty$. Then the action of $C_b(\mathbf{R})$ on $C(\mathbf{R})$ is continuous, and $C_b(\mathbf{R})$ is completely metrizable; indeed, it is a Banach algebra with $\| \|_\infty$. However $C_b(\mathbf{R})$ is not separable with $\| \|_\infty$. Indeed, for each $x \in \{\pm 1\}^\mathbb{Z}$, let $\tilde{x} \in C_b(\mathbf{R})$ be the function whose graph is the union of segments between all consecutive points in the graph of $x$. Then $\{B_\infty(\tilde{x}, 1) | x \in \{\pm 1\}^\mathbb{Z}\}$ is an uncountable set of disjoint open subsets of $C_b(\mathbf{R})$. So $C_b(\mathbf{R})$ is not second countable, and therefore it is not separable.

According to Example 6.3, the sets $U_{R,r}$ satisfy Hypothesis 1 and induce $d_\infty$. In this case, the inclusion (6.1) becomes the equality

$$ (7.1) \qquad E_r \circ E_s = E_{r+s} $$
for all $r, s > 0$; this holds because, if $g \in E_{r+s}(f)$, then

$$f + \frac{s}{r+s}(g-f) \in E_r(g) \cap E_s(f).$$

It is well known that $C(\mathbf{R})$ is Polish (Hypothesis 2 (i)). The following lemma shows that Hypothesis 2 (ii) is satisfied in this case.

**Lemma 7.2.** For all $R, r, s > 0$, $U_{R,r} \circ E_s = E_s \circ U_{R,r} = U_{R,r+s}$.

*Proof.* If $S \ge R$, then, for all $f, g, h \in C(\mathbf{R})$,

$$d_R(f, h) \le d_R(f, g) + d_R(g, h) \le d_R(f, g) + d_S(g, h),$$

because $d_R \le d_S$. This implies that $U_{R,r} \circ U_{S,s}$ and $U_{S,s} \circ U_{R,r}$ are both contained in $U_{R,r+s}$, which in turn implies that $U_{R,r} \circ E_s$ and $E_s \circ U_{R,r}$ are both contained in $U_{R,r+s}$.

To prove the reverse inclusions, let $f \in C(\mathbf{R})$ and $g \in U_{R,r+s}(f)$. Then

$$h_0 = f + \frac{s}{r+s}(g-f) \in U_{R,s}(f) \cap U_{R,r}(g),$$

$$h_1 = f + \frac{r}{r+s}(g-f) \in U_{R,r}(f) \cap U_{R,s}(g).$$

By continuity, $h_0 \in U_{S,s}(f)$ and $h_1 \in U_{S,s}(g)$ for some $S > R$. Let $\lambda : \mathbf{R} \to [0, 1]$ be any continuous function such that $\text{supp} \lambda \subseteq [-S, S]$ and $\lambda \equiv 1$ on $[-R, R]$. Then

$$f + \lambda(h_0 - f) \in E_s(f) \cap U_{R,r}(g),$$

$$g + \lambda(h_1 - g) \in U_{R,r}(f) \cap E_s(g),$$

which implies that $g \in (U_{R,r} \circ E_s)(f) \cap (E_s \circ U_{R,r})(f)$. $\square$

**Corollary 7.3.** If $R, S, r, s > 0$, then $U_{R,r} \circ U_{S,s} = U_{\min\{R,S\},r+s}$.

*Proof.* The inclusion “$\subseteq$” is (6.6), and “$\supseteq$” follows from Lemma 7.2. $\square$

**Lemma 7.4.** If $T, r, s, t > 0$, $f \in C(\mathbf{R})$ and $g \in E_s(f)$ are such that $U_{T,t'}(g) \subseteq U_{T,s}(f)$ for some $t' > t$, then

$$(7.2) \qquad U_{T,t+r}(g) \cap E_{r+s}(f) = E_r(U_{T,t}(g) \cap E_s(f)).$$

*Proof.* The inclusion “$\supseteq$” follows from (6.1) and Lemma 7.2. To prove “$\subseteq$”, let $h \in U_{T,t+r}(g) \cap E_{r+s}(f)$. By (7.1) and Lemma 7.2, there are $g_0 \in E_r(h) \cap U_{T,t}(g)$ and $f_0 \in E_r(h) \cap E_s(f)$. By continuity, $g_0 \in U_{T',t}(g) \subseteq U_{T',s}(f)$ for some $T' > T$. Let $\lambda : \mathbf{R} \to [0, 1]$ be any continuous function such that $\text{supp} \lambda \subseteq [-T', T']$ and $\lambda \equiv 1$ on $[-T, T]$. Then

$$f_0 + \lambda(g_0 - f_0) \in E_r(h) \cap U_{T,t}(g) \cap E_s(f),$$

and so $h \in E_r(U_{T,t}(g) \cap E_s(f))$. $\square$
**Corollary 7.5.** *The supremum metric relation $d_∞$ satisfies Hypothesis 2-(iii).*

*Proof.* Let $r, s > 0$, $f \in C(\mathbf{R})$, $g \in E_s(f)$, and $V$ a neighborhood $g$ in $C(\mathbf{R})$. Since $V$ can be chosen as small as desired, we can assume that $V = U_{T,t}(g)$ for some $T, t > 0$. Since $g \in E_s(f) \subseteq U_{T,s}(f)$, there is $t' > 0$ such that $U_{T,t'}(g) \subseteq U_{T,s}(f)$, and we can also suppose that $t < t'$, obtaining (7.2) by Lemma 7.4. But (7.2) gives the inclusion of Hypothesis 2 (iii) for $W = V$ by (7.1) and Lemma 7.2. □

The fact that $E_∞$ has more than one class (Hypothesis 3 (i)) is obvious because $d_∞(f, g) = ∞$ if $f$ is bounded and $g$ unbounded. Hypotheses 3 (ii),(iii) is a consequence of the following lemmas.

**Lemma 7.6.** *For every $f, g \in C(\mathbf{R})$ and every $R, r > 0$, if $s > d_{R'}(f, g)$ for some $R' > R$, then $U_{R,r}(f) \cap E_s(g) \neq \emptyset$.*

*Proof.* Let $\lambda : \mathbf{R} \to [0, 1]$ be a continuous function such that $\text{supp} \lambda \subseteq [-R', R']$ and $\lambda \equiv 1$ on $[-R, R]$. Then $g + \lambda(f - g) \in U_{R,r}(f) \cap E_s(g)$. □

**Lemma 7.7.** *For every $R, r > 0$ and every $f \in C(\mathbf{R})$, the set $U_{R,r}(f) \cap E_∞(f)$ is $d_∞$-path connected.*

*Proof.* For every $g \in U_{R,r}(f) \cap E_∞(f)$, the mapping $t \mapsto tf + (1-t)g$ defines a $d_∞$-continuous path in $U_{R,r}(f) \cap E_∞(f)$ from $g$ to $f$. □

**Remark 7.8.** The symmetric relations on $C(\mathbf{R})$ with fibers the balls $B_∞(f, r)$ cannot be used instead of the relations $E_r$ to show that $d_∞$ is of type I. For instance, each ball $B_∞(f, r)$ is not $G_δ$ in $C(\mathbf{R})$; otherwise it would be Polish, and therefore it would be a Baire space with the induced topology. But $\emptyset$ is residual in $B_∞(f, r)$ for all $r > 0$, as the following argument shows. Let $(r_n)$ and $(R_n)$ be sequences such that $0 < r_n \uparrow r$ and $0 < R_n \uparrow \infty$. For each $n$, let $U_n$ be the set of functions $g \in B_∞(f, r)$ such that

$$ \sup_{|x|>R_n} |f(x) - g(x)| > r_n. $$

The sets $U_n$ are open and dense in $B_∞(f, r)$ and their intersection is empty.

## 8. THE GROMOV SPACE

Let $M$ be a metric space and let $d_M$, or simply $d$, be its distance function. The *Hausdorff distance* between two non-empty subsets, $A, B \subseteq M$, is given
by

$$H_d(A, B) = \max\left\{\sup_{a \in A} \inf_{b \in B} d(a, b), \sup_{b \in B} \inf_{a \in A} d(a, b)\right\}.$$

Note that $H_d(A, B) = H_d(\bar{A}, \bar{B})$, and $H_d(A, B) = 0$ if and only if $\bar{A} = \bar{B}$. It is well known that $H_d$ satisfies the triangle inequality, and that its restriction to the set of non-empty, compact subsets of $M$ is finite valued, and defines there a complete metric if $M$ is complete.

Let $M$ and $N$ be arbitrary non-empty, metric spaces. A metric on the disjoint union $M \sqcup N$ is called *admissible* if its restrictions to $M$ and to $N$ are $d_M$ and $d_N$, respectively, where $M$ and $N$ are identified with their canonical injections in $M \sqcup N$. The *Gromov-Hausdorff distance* (or *GH distance*) between $M$ and $N$ is defined by

$$d_{GH}(M, N) = \inf_{d} H_{d}(M, N),$$

where the infimum is taken over all admissible metrics. It is well known that $d_{GH}(M, N) = d_{GH}(\bar{M}, \bar{N})$, where $\bar{M}$ and $\bar{N}$ denote the completions of $M$ and $N$, $d_{GH}(M, N) = 0$ if $\bar{M}$ and $\bar{N}$ are isometric, $d_{GH}$ satisfies the triangle inequality, and $d_{GH}(M, N) < \infty$ if $\bar{M}$ and $\bar{N}$ are compact.

The (*pointed*) *Gromov-Hausdorff distance* between two pointed metric spaces, $(M, x)$ and $(N, y)$, is defined by

$$d_{GH}(M, x; N, y) = \inf_{d} \max\{d(x, y), H_{d}(M, N)\},$$

where the infimum is taken over the set of all admissible metrics $d$ on $M \sqcup N$.

**Lemma 8.1.** If $f: M \to X$ and $g: N \to X$ are isometric injections, then

$$d_{GH}(M, x; N, y) \leq \max\{d_X(f(x), g(y)), H_{d_X}(f(M), g(N))\}.$$

*Proof.* The inequality follows at once by considering, for each $\epsilon > 0$, the unique admissible metric $d_{\epsilon}$ on $M \sqcup N$ satisfying, for all $u \in M$ and $v \in N$,

$$d_{\epsilon}(u, v) = d_{X}(f(u), g(v)) + \epsilon. \quad \square$$

A metric space in which the closure of every ball is compact is called *proper*. Every proper metric space is complete and locally compact, so its cardinality is at most that of the continuum. Therefore the underlying set of any proper metric space may be identified with a subset of $\mathbb{R}$. There is then a set whose members are the isometry classes of pointed, proper metric spaces. This set, denoted by $M_*$, is endowed with a topology introduced by M. Gromov [4, Section 6], [3], which can be described as follows.
For a metric space, $X$, two subspaces, $M, N \subseteq X$, two points, $x \in M$ and $y \in N$, and a real number $R > 0$, let $H_{d_X,R}(M, x; N, y)$ be given by

$$H_{d_X,R}(M, x; N, y) = \max\left\{\sup_{u \in B_M(x,R)} d_X(u, N), \sup_{v \in B_N(y,R)} d_X(v, M)\right\}.$$

Then, for $R, r > 0$, let $U_{R,r} \subseteq \mathcal{M}_* \times \mathcal{M}_*$ denote the subset of pairs $([M, x], [N, y])$ for which there is an admissible metric, $d$, on $M \sqcup N$ so that

$$\max\{d(x, y), H_{d,R}(M, x; N, y)\} < r.$$

The following lemma is obtained exactly as Lemma 8.1.

**Lemma 8.2.** For $([M, x], [N, y]) \in \mathcal{M}_* \times \mathcal{M}_*$ to be in $U_{R,r}$ it suffices that there exists a metric space, $X$, and isometric injections, $f: M \to X$ and $g: N \to X$, such that

$$\max\{d_X(f(x), g(y)), H_{d_X,R}(f(M), f(x); g(N), g(y))\} < r.$$

The following notation will be used: for a relation $E$ on $\mathcal{M}_*$ and $[M, x] \in \mathcal{M}_*$, $E([M, x])$ will be written $E(M, x)$, and for a metric relation $d$ on $\mathcal{M}_*$ and $[M, x], [N, y] \in \mathcal{M}_*$, $d([M, x], [N, y])$ will be written $d(M, x; N, y)$.

The sets $U_{R,r}$ satisfy Hypothesis 1 [1, Lemma 2.1]; in particular, Hypothesis 1 (v) is satisfied as stated in the following lemma.

**Lemma 8.3** ([1, Lemma 2.1 (v)]). If $R, r, s > 0$, then $U_{S,r} \circ U_{S,s} \subseteq U_{R,r+s}$, where $S = R + 2 \max\{r, s\}$.

Since the sets $U_{R,r}$ satisfy Hypothesis 1, they form a base of entourages for a metrizable uniformity on $\mathcal{M}_*$. Endowed with the induced topology, $\mathcal{M}_*$ is called the *Gromov space*. It is well known that $\mathcal{M}_*$ is a Polish space (Gromov [4] or Petersen [11]); in particular, the set of the pointed finite metric spaces with Q-valued metrics is a countable dense subset of $\mathcal{M}_*$.

Some examples of dynamical structures on $\mathcal{M}_*$ are the following:

**The canonical metric relation:** The canonical partition $E_{\text{can}}$ is defined by varying the distinguished point; that is, as a relation, $E_{\text{can}}$ consists of all the pairs $([M, x], [M, y])$, where $M$ is a proper metric space and $x, y \in M$. There is a canonical map $M \to \mathcal{M}_*$, $x \mapsto [M, x]$, which defines an embedding $\text{Isom}(M)\backslash M \to \mathcal{M}_*$ whose image is $E_{\text{can}}(M, x)$ for any $x \in M$. Note that $\mathcal{M}_*/E_{\text{can}}$ can be identified to the set of isometry classes of proper metric spaces.

**The GH metric relation:** It is defined by the pointed GH distance $d_{GH}$. The notation $E_{GH} = E_{d_{GH}}^{\mathcal{M}_*}$ will be used. Since $E_{\text{can}} \subseteq E_{GH}$, the quotient set $\mathcal{M}_*/E_{GH}$ can be identified to the set of classes of
proper metric spaces defined by the relation of being at finite GH distance.

**The Lipschitz metric relation:** The Lipschitz partition, $E_{Lip}$, is defined by the existence of pointed bi-Lipschitz bijections. It is induced by the Lipschitz metric relation, $d_{Lip}$, which is defined by using the infimum of the logarithms of the dilation constants of bi-Lipschitz bijections.

**The QI metric relation:** The quasi-isometric partition (or QI partition), $E_{QI}$, is the smallest equivalence relation on $M_*$ that contains $E_{GH} \cup E_{Lip}$. It is induced by the quasi-isometric metric relation (or QI relation), $d_{QI}$, defined as the largest metric relation on $M_*$ smaller than both $d_{GH}$ and $d_{Lip}$ (cf. [12, Lemma 6]). The quotient set $M_*/E_{QI}$ can be identified to the set of quasi-isometry classes of proper metric spaces.

**The dilation flow:** It is the multiplicative flow defined by $\lambda \cdot [M, x] = [\lambda M, x]$, where $\lambda M$ denotes $M$ with its metric multiplied by $\lambda$. This flow is used to define the asymptotic and tangent cones.

In Sections 9 and 10, we will study the GH and QI metric relations, respectively, and prove Theorem 1.1 for them. Some technical results and concepts related to the definition of $M_*$ to be used in those sections are given presently.

**Lemma 8.4.** Let $[M, x], [N, y] \in M_*$ and $r > 0$. If $d$ is an admissible metric on $M \cup N$ such that $d(x, y) < r$ and $H_d(M, N) < r$, then $d$ is proper.

*Proof.* For every $v \in N$,

$$d_N(y, v) \leq d(x, y) + d(x, v) < r + d(x, v),$$

and so

$$B_d(x, R) \subseteq B_M(x, R) \cup B_N(y, R+r)$$

for all $R > 0$. The statement now follows because $M$ and $N$ are proper. $\square$

**Lemma 8.5.** Let $[M, x], [N, y], [P, z] \in M_*$ and $R, r > 0$. Suppose that the pointed metric spaces $(B_P(z, R+2r), z)$ and $(B_N(y, R+2r), y)$ are isometric, and that there is an admissible metric, $d$, on $M \cup N$ such that $d(x, y) < r$ and $H_{d,R}(M, x; N, y) < r$. Then there exists a proper admissible metric, $d'$, on $M \cup P$ such that $d'(x, z) < r$ and $H_{d',R}(M, x; P, z) < r$.

*Proof.* Let $A = B_M(x, R+2r)$, $B = B_N(y, R+2r)$ and $C = B_P(z, R+2r)$, and let $\phi : (B, y) \to (C, z)$ be an isometry. Let $d'$ be the admissible metric
on $M \sqcup P$ satisfying, for $u \in M$ and $w \in P$,

$$d'(u, w) = \inf\{d_M(u, u') + d(u', v) + d_P(\phi(v), w) \mid u' \in A, v \in B\}.$$

Note that, for $u \in A$ and $v \in B$, $d'(u, \phi(v)) = d(u, v)$; in particular, $d'(x, z) < r$.

For each $u \in B_M(x, R)$, there is $v \in N$ such that $d(u, v) < r$. Since

$$d_N(y, v) \le d(y, x) + d_M(x, u) + d(u, v) < R + 2r,$$

this $v \in B_N(y, R+2r)$. So $d'(u, \phi(v)) = d(u, v) < r$, and therefore $d'(u, P) < r$. Similarly, $d'(w, M) < r$ for all $w \in B_P(z, R)$, so $H_{d',R}(M, x; P, z) < r$.

For each $S > 0$ and $w \in P \cap B_{d'}(x, S)$, there is $v \in B$ such that $d(x, v) + d_P(\phi(v), w) < S$. So

$$d_P(z, w) \le d_P(z, \phi(v)) + d_P(\phi(v), w) < R + 2r + S,$$

obtaining

$$B_{d'}(x, S) \subseteq B_M(x, S) \sqcup B_P(z, R + 2r + S).$$

Hence $\overline{B_{d'}(x, S)}$ is compact since $M$ and $P$ are proper. This shows that $d'$ is proper. $\square$

## 9. THE GH METRIC RELATION

For each $r > 0$, let $E_r \subseteq \mathcal{M}_* \times \mathcal{M}_*$ be the symmetric relation whose fibers are $E_r(M, x) = \bigcap_{R>0} U_{R,r}(M, x)$, where $U_{R,r}(M, x)$ is the fiber of the relation $U_{R,r}$ introduced in Section 8. The notation $B_{GH}(M, x; r) = B_{d_{GH}}([M, x], r)$ will be used.

**Lemma 9.1.** If $0 < r < s$, then

$$B_{GH}(M, x; r) \subseteq E_r(M, x) \subseteq B_{GH}(M, x; s).$$

*Proof.* The first inclusion is obvious. To verify the second one, let $[N, y]$ be any member of $E_r(M, x)$. For each $R > 0$ there exists an admissible metric, $d_R$, on $M \sqcup N$ such that $d_R(x, y) < r$ and $H_{d_R,R}(M, x; N, y) < r$. Let $\omega$ be a free ultrafilter on $[0, \infty)$. Then there is a unique admissible metric, $d$, on $M \sqcup N$ such that, for all $u \in M$ and $v \in N$,

$$d(u, v) = \lim_{R \to \omega} d_R(u, v) + \frac{s-r}{2}.$$

For each $\epsilon > 0$ there exists $\Omega \in \omega$ such that, for all $R \in \Omega$,

$$d(u, v) < d_R(u, v) + \frac{s-r}{2} + \epsilon,$$

and thus

$$d(x, y) \le d_R(x, y) + \frac{s-r}{2} + \epsilon < \frac{s+r}{2} + \epsilon.$$
Because this holds for each $\epsilon > 0$,

$$d(x, y) \leq \frac{s+r}{2} < s.$$

Next, for every $u \in M$, if $R \in \Omega$ is $> d(x, u)$, then $d_R(u, N) < r$, and so $d(u, N) < s$ as before. Similarly, $d(v, M) < s$ for all $v \in N$. Therefore $H_d(M, N) < s$. $\square$

**Corollary 9.2.** The metric relation on $M_*$ defined by the sets $U_{R,r}$ is $d_{GH}$.

By Propositions 6.4, 6.9 and 6.10, and Corollary 9.2, the case of $(d_{GH}, E_{GH})$ in Theorem 1.1 follows by showing that the sets $U_{R,r}$ also satisfy Hypotheses 2 and 3. It was already noted that $M_*$ is Polish (Hypothesis 2 (i)).

**Lemma 9.3.** If $R, r, s > 0$, then $U_{R+2r+s,s} \circ U_{R,r} \subseteq E_s \circ U_{R,r}$.

*Proof.* Let $S = R+2r+s$. If $[M, x] \in M_*$ and $[N, y] \in U_{S,s} \circ U_{R,r}(M, x)$, then there is $[P, z] \in U_{R,r}(M, x) \cap U_{S,s}(N, y)$. This means that there are admissible metrics, $d$ on $M \cup P$ and $\bar{d}$ on $N \cup P$, such that $d(x, z) < r$, $H_{d,R}(M, x; P, z) < r$, $\bar{d}(y, z) < s$ and $H_{\bar{d},S}(N, y; P, z) < s$. Moreover, because of Lemma 8.5, $\bar{d}$ may be assumed to be a proper metric. The subset

$$P' = (N \setminus B_N(y, S)) \cup \overline{B_P(z, S)} \subseteq N \cup P$$

is closed and so it becomes a proper metric space when endowed with the metric induced by $\bar{d}$.

**Claim 6.** The pointed metric space $(P', z)$ satisfies $d_{GH}(N, y; P', z) < s$.

Since $N \setminus P' \subseteq B_N(y, S)$ and $P' \setminus N = \overline{B_P(z, S)}$, the Hausdorff distance

$$H_{\bar{d}}(N, P') = \max \left\{ \sup_{v \in B_N(y, S)} \bar{d}(v, P'), \sup_{w \in B_P(z, S)} \bar{d}(w, N) \right\} \\ \leq H_{\bar{d},S}(N, y; P, z) < s,$$

and so Claim 6 follows from Lemma 8.1.

From Claim 6 and Corollary 9.2, it follows that $[P', z] \in E_s(N, y)$.

**Claim 7.** $B_{P'}(z, R+2r) = B_P(z, R+2r)$.

The inclusion "$\supseteq$" of this identity is obviously true. To prove that the reverse inclusion "$\subseteq$" is also true, it suffices to note that $B_{P'}(z, R+2r) \cap N = \emptyset$, which is true because, if there is $v \in B_{P'}(z, R+2r) \cap N$, then

$$d_N(y, v) \leq \bar{d}(y, z) + \bar{d}(z, v) < s + R + 2r = S,$$

which contradicts that $B_N(y, S) \cap P' = \emptyset$.

From Claim 7 and Lemma 8.5, it follows that $[P', z] \in U_{R,r}(M, x)$. Hence $[N, y] \in E_s \circ U_{R,r}(M, x)$. $\square$
A subset A of a metric space X is called a net (as defined in [4, Definition 2.14]) if there is $\epsilon > 0$ such that $d_X(u, A) \le \epsilon$ for all $u \in X$, and it is called separated if there is $\delta > 0$ such that $d_X(a, b) \ge \delta$ for all $a, b \in A$ with $a \ne b$; the terms $\epsilon$-net and $\delta$-separated are also used in these cases.

A separated subset of a metric space is discrete and therefore closed. Hence, every separated subset of a proper metric space is a proper metric space when endowed with the induced metric.

If $A \subseteq X$ is an $\epsilon$-net of a metric space, $(X, d_X)$, then $H_{d_X}(X, A) \le \epsilon$. So, if $A$ is endowed with the induced metric from $(X, d_X)$, then $d_{GH}(X, x; A, x) \le \epsilon$ for every $x \in A$ by Lemma 8.1. Therefore, if in addition $X$ is proper and $A$ is separated, then, for any $\delta > \epsilon$, $[A, x] \in E_\delta(X, x)$ by Lemma 9.1.

**Lemma 9.4.** Let $\epsilon > 0$. For each metric space $M$ and each $\epsilon$-separated subset $S \subseteq M$, there exists an $\epsilon$-separated $\epsilon$-net of $M$ that contains $S$.

*Proof.* By Zorn's lemma, the set of $\epsilon$-separated subsets of $M$ that contain $S$, ordered by inclusion, has a maximal element. It is easily checked that a maximal element is an $\epsilon$-net. $\square$

The following is a “converse” to Lemma 8.3.

**Lemma 9.5.** If $R, r, s > 0$, then $U_{R,r+s} \subseteq U_{R,s} \circ U_{R,r}$.

*Proof.* Let $[M, x] \in \mathcal{M}_*$ and $[N, y] \in U_{R,r+s}(M, x)$. Then there is an admissible metric, $d$, on $M \sqcup N$ such that $d(x, y) < r_0 + s_0$ and $H_{d,R}(M, x; N, y) < r_0 + s_0$ for some $r_0 \in (0, r)$ and $s_0 \in (0, s)$. By Lemma 8.5, $d$ may be assumed to be a proper metric.

Let $\epsilon > 0$ be such that $r_0 + 2\epsilon < r$ and $s_0 + 2\epsilon < s$. By Lemma 9.4, there are $\epsilon$-separated $\epsilon$-nets, $A$ of $B_M(x, R)$ and $B$ of $B_N(y, R)$, such that $x \in A$ and $y \in B$.

For each $u \in B_M(x, R)$, there is $v \in N$ such that $d(u, v) < r_0 + s_0$. Then there is $v' \in B$ so that $d_N(v, v') \le \epsilon$. So

$$d(u, v') \le d(u, v) + d_N(v, v') < r_0 + s_0 + \epsilon,$$

which implies $d(u, B) < r_0 + s_0 + \epsilon$. Similarly, for all $v \in B_N(y, R)$, $d(v, A) < r_0 + s_0 + \epsilon$.

Let $\Sigma$ denote the set of pairs $(u, v) \in A \times B$ such that $d(u, v) < r_0 + s_0 + \epsilon$ and $\min\{d_M(x, u), d_N(y, v)\} < R$; in particular, $(x, y) \in \Sigma$. The set $\Sigma$ is finite because $A$ and $B$ are separated and $d$ is proper. For each $(u, v) \in \Sigma$, let $I_{u,v}$ be the interval $[0, d(u, v)] \subseteq \mathbb{R}$ of length $d(u, v)$, and let $d_{u,v}$ be its standard metric. Let $h: \bigsqcup_{(u,v) \in \Sigma} \partial I_{u,v} \to M \sqcup N$ be a map that restricts to
a bijection $h : \partial I_{u,v} \to \{u, v\}$ for all $(u, v) \in \Sigma$, and let

$$ \hat{P} = (M \sqcup N) \cup_h \bigsqcup_{(u,v) \in \Sigma} I_{u,v}. $$

The spaces $M$, $N$ and each $I_{u,v}$ may be viewed as subspaces of $\hat{P}$; in particular, $\partial I_{u,v} = \{u, v\}$ in $\hat{P}$. Let $\hat{P}$ be endowed with the metric $\hat{d}$ whose restriction to $M \sqcup N$ is $d$, whose restriction to each $I_{u,v}$ is $d_{u,v}$, and such that, for all $(u, v), (u', v') \in \Sigma$, $w \in I_{u,v}$ and $w' \in I_{u',v'}$,

$$ \hat{d}(w, w') = \min \{ d_{u,v}(w, u) + d_M(u, u') + d_{u',v'}(u', w'), \\ d_{u,v}(w, v) + d_N(v, v') + d_{u',v'}(v', w') \}. $$

Let $P \subseteq \hat{P}$ be the finite subset consisting of the points $w \in I_{u,v}$ with $(u, v) \in \Sigma$ and

$$ d_{u,v}(w, u) = \frac{r_0 + \epsilon}{r_0 + s_0 + 2\epsilon} d(u, v). $$

Let $z$ be the unique point in $P \cap I_{x,y}$, and consider the restriction of $\hat{d}$ to $P$. If $(u, v) \in \Sigma$ and $w$ is the unique point in $P \cap I_{u,v}$, then

$$ \hat{d}(u, w) \le d_{u,v}(u, w) < \frac{r_0 + \epsilon}{r_0 + s_0 + 2\epsilon} d(u, v) < r_0 + \epsilon. $$

So $\hat{d}(x, z) < r_0 + \epsilon < r$, and, for all $u \in A$ and $w \in P$, $\hat{d}(u, P) < r_0 + \epsilon$ and $\hat{d}(w, M) < r_0 + \epsilon$. Since $A$ is an $\epsilon$-net in $B_M(x, R)$, it also follows that, for all $u \in B_M(x, R)$, $\hat{d}(u, P) < r_0 + 2\epsilon$. Similarly, $\hat{d}(y, z) < s$, and, for all $v \in B_N(y, R)$ and $w \in P$, $\hat{d}(v, P) < s_0 + 2\epsilon$ and $\hat{d}(w, N) < s_0 + \epsilon$. Thus

$$ H_{\hat{d},R}(M, x; P, z) \le r_0 + 2\epsilon < r, \quad H_{\hat{d},R}(N, y; P, z) \le s_0 + 2\epsilon < s, $$

and so $[P, z] \in U_{R,r}(M, x) \cap U_{R,s}(N, y)$ by Lemma 8.2. Therefore $[N, z] \in U_{R,s} \circ U_{R,r}(M, x)$. $\square$

Hypothesis 2 (ii) results from the next corollary.

**Corollary 9.6.** For $R, r, s > 0$, $U_{T,r} \circ E_s \subseteq E_s \circ U_{R,r}$, where

$$ T = R + 2r + s + 2 \max\{r, s\}. $$

*Proof.* Let $S = R + 2r + s$. By Lemmas 8.3, 9.3 and 9.5,

$$ U_{T,r} \circ E_s \subseteq U_{T,r} \circ U_{T,s} \subseteq U_{S,r+s} \subseteq U_{S,s} \circ U_{R,r} \subseteq E_s \circ U_{R,r}. \quad \square $$

Hypothesis 2 (iii) is the statement of the next lemma.

**Lemma 9.7.** Let $[M, x] \in \mathcal{M}_*$, $s > 0$ and $[N, y] \in E_s(M, x)$. If $r > 0$ and $V$ is a neighborhood of $[N, y]$ in $\mathcal{M}_*$, then there is a neighborhood $W$ of $[N, y]$ in $\mathcal{M}_*$ such that

$$ E_r(W) \cap E_r(E_s(M, x)) \subseteq E_r(V \cap E_s(M, x)). $$
Proof. By Lemma 8.5, there are $S > 0$ and an open neighborhood $W$ of $[N, y]$ in $M_*$ such that, for all $[N', y'] \in M_*$ and $[N'', y''] \in W$, if $(B_{N'}(y', S), y')$ is isometric to $(B_{N''}(y'', S), y'')$, then $[N', y'] \in V$. Since $[N, y] \in U_{T,s}(M, x)$ for $T = S + s + r$, we also assume that $W \subseteq U_{T,s}(M, x)$.

For each $[P, z] \in E_r(W) \cap E_r(E_s(M, x))$, there are $[N_1, y_1] \in W$ and $[N_2, y_2] \in E_s(M, x)$ such that $[P, z] \in E_r(N_1, y_1) \cap E_r(N_2, y_2)$, and admissible, proper (by Lemma 8.5) metrics, $d_1$ on $M \sqcup N_1$ and $\bar{d}_1$ on $N_1 \sqcup P$, so that $d_1(x, y_1) < s$, $H_{d_1,T}(M, x; N_1, y_1) < s$, $\bar{d}_1(y_1, z) < r$ and $H_{\bar{d}_1,T}(N_1, y_1; P, z) < r$. Let $(T_n)$ be a sequence in $\mathbb{R}$ with $T_n \uparrow \infty$ and $T_0 > T$; set also $T_{-1} = T$. For each $n \in \mathbb{N}$, let $(N_{2,n}, y_{2,n})$ be an isometric copy of $(N_2, y_2)$. Then there are admissible, proper (by Lemma 8.5) metrics, $d_{2,n}$ on $M \sqcup N_{2,n}$ and $\bar{d}_{2,n}$ on $N_{2,n} \sqcup P$, such that $d_{2,n}(x, y_{2,n}) < s$, $H_{d_{2,n},T_n}(M, x; N_{2,n}, y_{2,n}) < s$, $\bar{d}_{2,n}(y_{2,n}, z) < r$ and $H_{\bar{d}_{2,n},T_n}(N_{2,n}, y_{2,n}; P, z) < r$.

Let $d$ denote the metric on $M \sqcup N_1 \sqcup (\bigsqcup_{n=0}^{\infty} N_{2,n}) \sqcup P$ which extends $d_1$, $\bar{d}_1$, $d_{2,n}$ and $\bar{d}_{2,n}$ for all $n \in \mathbb{N}$, and such that, for $u \in M$ and $w \in P$,

$$d(u, w) = \inf\{d_1(u, v_1) + \bar{d}_1(v_1, w), \\ d_{2,n}(u, v_{2,n}) + \bar{d}_{2,n}(v_{2,n}, w) \mid v_1 \in N_1, v_{2,n} \in N_{2,n}, n \in \mathbb{N}\},$$

for $v_1 \in N_1$ and $v_{2,n} \in N_{2,n}$,

$$d(v_1, v_{2,n}) = \inf\{d_1(v_1, u) + d_{2,n}(u, v_{2,n}), \\ \bar{d}_1(v_1, w) + \bar{d}_{2,n}(w, v_{2,n}) \mid u \in M, w \in P\},$$

and, for $v_{2,m} \in N_{2,m}$ and $v_{2,n} \in N_{2,n}$ with $m \neq n$,

$$d(v_{2,m}, v_{2,n}) = \inf\{d_{2,m}(v_{2,m}, u) + d_{2,n}(u, v_{2,n}), \\ \bar{d}_{2,m}(v_{2,m}, w) + \bar{d}_{2,n}(w, v_{2,n}) \mid u \in M, w \in P\}.$$

Since the metrics $d_1$, $\bar{d}_1$, and $d_{2,n}$ and $\bar{d}_{2,n}$ for all $n \in \mathbb{N}$, are proper, the metric $d$ is proper as well. The set

$$N' = \overline{B_{N_1}(y_1, T)} \sqcup \left( \bigsqcup_{n=0}^{\infty} \left( \overline{B_{N_{2,n}}(y_{2,n}, T_n)} \setminus B_{N_{2,n}}(y_{2,n}, T_{n-1}) \right) \right)$$

is closed in $M \sqcup N_1 \sqcup (\bigsqcup_{n=0}^{\infty} N_{2,n}) \sqcup P$, and therefore it becomes a proper metric space with the restriction of $d$.

Then $H_d(M, x; N', y_1) < s$ and $H_d(N', y_1; P, z) < r$, as in Claim 6, and so $d_{GH}(M, x; N', y_1) < s$ and $d_{GH}(N', y_1; P, z) < r$ by Lemma 8.1, which in turn implies $[N', y_1] \in E_s(M, x) \cap E_r(P, z)$ by Lemma 9.1. On the other hand, like in Claim 7, it follows that $B_{N'}(y_1, S) = B_{N_1}(y_1, S)$ and so $[N', y_1] \in V$ because $[N_1, y_1] \in W$. Therefore $[P, z] \in E_r(V \cap E_s(M, x))$. $\square$
Hypothesis 3 (i) is plainly true: the relation $E_{GH}$ has more than one equivalence class because the GH distance between a bounded metric space and an unbounded one is always infinite.

Hypothesis 3 (ii) is a consequence of the next lemma.

**Lemma 9.8.** If $[M, x], [N, y] \in \mathcal{M}_*$ and $R, r > 0$, then there is $s > 0$ such that $U_{R,r}(M, x) \cap E_s(N, y) \neq \emptyset$.

*Proof.* Let $A$ and $B$ denote the balls of radius $R + 2r$ in $M$ and $N$ with centers $x$ and $y$, respectively. Let $s_0 > d_{GH}(A, x; B, y)$ and let $d$ be an admissible metric on $A \sqcup B$ such that $d(x, y) < s_0$ and $H_d(A, B) < s_0$. Let $d'$ be the admissible metric on $M \sqcup N$ satisfying, for all $u \in M$ and $v \in N$,

$$d'(u, v) = \inf\{d_M(u, u') + d(u', v') + d_N(v', v) \mid u' \in A, v' \in B\}.$$

By the proof of Lemma 8.5, the metric $d'$ is proper, and its restriction to $A \sqcup B$ equals $d$; in particular, $d'(x, y) < s_0$.

Let $A'$ and $B'$ denote the balls of radius $R + 2r + s_0$ in $M$ and $N$ with centers $x$ and $y$, respectively. The set $N' = \bar{A}' \sqcup (N \setminus B')$ is closed in $M \sqcup N$, and therefore it becomes a proper metric space with the restriction of $d'$. Take any

$$s > \max\{s_0, R + 2r + d'(x, N \setminus B')\}.$$

If $N \setminus B' \neq \emptyset$, then, for all $v \in N \setminus B'$ and $u \in \bar{A}'$,

$$d'(u, v) \leq d_M(u, x) + d'(x, v) < R + 2r + d'(x, v),$$

and so

$$H_{d'}(\bar{A}', N \setminus B') \leq R + 2r + d'(x, N \setminus B') < s.$$

It follows that $H_{d'}(N, N') < s$, and so $d_{GH}(N, y; N', x) < s$ by Lemma 8.1. Therefore $[N', x] \in E_s(N, y)$ by Lemma 9.1. Also, like in Claim 7, $B_{N'}(x, R+2r) = A$, and therefore $[N', x] \in U_{R,r}(M, x)$ by Lemma 8.5. $\square$

Hypothesis 3 (iii) is verified as follows. Let $R, r > 0$ and $[M, x] \in \mathcal{M}_*$. Let $S > R$ and $s > 0$ be such that $s < r$ and $R + 2 \max\{s, r - s\} < S$, and let $\mathcal{D}$ denote the set of points $[N, y] \in \mathcal{M}_*$ such that there is some admissible metric, $d$, on $M \sqcup N$ so that $d(x, y) < s$, $H_{d,S}(M, x; N, y) < s$ and $H_d(M, N) < \infty$.

**Lemma 9.9.** $\mathcal{D}$ is a dense subset of $U_{S,s}(M, x) \cap E_{GH}(M, x)$.

*Proof.* By its definition, the set $\mathcal{D} \subseteq U_{S,s}(M, x) \cap E_{GH}(M, x)$. It must to be shown that, for every $T, t, t' > 0$ and $[N, y] \in U_{S,s}(M, x) \cap B_{GH}(M, x; t')$, the intersection $U_{T,t}(N, y) \cap \mathcal{D} \neq \emptyset$. Let $(N_1, y_1)$ and $(N_2, y_2)$ be two isometric copies of $(N, y)$. There are admissible metrics, $d_1$ on $M \sqcup N_1$ and $d_2$ on
$M \sqcup N_2$, such that $d_1(x, y_1) < s$, $H_{d_1,R}(M, x; N_1, y_1) < s$, $d_2(x, y_2) < t'$ and $H_{d_2}(M, N_2) < t'$. Let $\hat{d}$ denote the metric on $M \sqcup N_1 \sqcup N_2$ whose restrictions to $M \sqcup N_1$ and $M \sqcup N_2$ are $d_1$ and $d_2$, respectively, and such that, for all $v_1 \in N_1$ and $v_2 \in N_2$,

$$ \hat{d}(v_1, v_2) = \inf\{d_1(v_1, u) + d_2(u, v_2) \mid u \in M\}. $$

Since $d_2$ is proper by Lemma 8.4, and $d_1$ can be assumed to be proper by Lemma 8.5, the metric $\hat{d}$ is proper as well. Let

$$ T' = \max\{S, T\} + 2\max\{s, t\} + t' + s, $$

let $A = B_M(x, T' + 2t')$, $B_1 = B_{N_1}(y_1, T')$ and $B_2 = B_{N_2}(y_2, T')$, and set $N' = \overline{B_1} \sqcup (N_2 \setminus B_2)$. Since $N'$ is closed in $M \sqcup N_1 \sqcup N_2$, it becomes a proper metric space with the restriction of $\hat{d}$. We have $\hat{d}(x, y_1) = d_1(x, y_1) < s$. With arguments used in Claims 6 and 7, we obtain $H_{\hat{d},R}(M, x; N', y_1) < s$ and

$$ H_{\hat{d}}(M, N') < \max\{H_{d_1}(A, B_1), t'\} < \infty. $$

It follows that $[N', y_1]$ satisfies the condition to be in $\mathcal{D}$ with the restriction of $\hat{d}$ to the subset $M \sqcup N'$ of $M \sqcup N_1 \sqcup N_2$. Also, since $\hat{d}(y_1, y_2) \le t' + s$, the proof of Claim 7 leads to

$$ B_{N'}(y_1, T + 2t) = B_{N_1}(y_1, T + 2t) \equiv B_N(y, T + 2t), $$

and therefore $[N', y_1] \in U_{T,t}(N, y)$ by Lemma 8.5. $\square$

<figure><img src="image_4.png" /></figure>

Let $\mathcal{E}$ be the set of those $[M, x] \in \mathcal{D}$ such that $M$ is separated (in itself). By Lemma 9.4, this $\mathcal{E}$ is $d_{GH}$-dense in $\mathcal{D}$. Let $\epsilon > 0$ be such that $s + 2\epsilon < r$ and $R + 2\max\{s + \epsilon, r - s - \epsilon\} < S$. Let $A$ be a separated $\epsilon$-net of $M$ that contains $x$, whose existence is guaranteed by Lemma 9.4, and consider the restriction of $d_M$ to $A$. Note that $[A, x] \in E_{r-s-\epsilon}(M, x)$ because $r - s - \epsilon > \epsilon$. Then the proof of Hypothesis 3 (iii) is completed by the following lemma.

**Lemma 9.10.** Any point of $\mathcal{E}$ can be joined to $[A, x]$ by a $d_{GH}$-continuous path in $U_{R,r}(M, x)$.

*Proof.* For any $[N, y] \in \mathcal{E}$, there is some admissible metric, $d$, on $M \sqcup N$ such that $d(x, y) < s$, $s_0 := H_{d,S}(M, x; N, y) < s$ and $s_1 := H_d(M, N) < \infty$. Moreover $d$ is proper by Lemma 8.4. Note that $H_{d,S}(A, x; N, y) < s_0 + \epsilon$ and $H_d(A, N) \le s_1 + \epsilon$.

Let $\Sigma$ be the set of pairs $(u, v) \in A \times N$ such that $d(u, v) \le s_1 + \epsilon$ and, if $u \in B_A(x, S)$ or $v \in B_N(y, S)$, then $d(u, v) \le s_0 + \epsilon$; in particular, $(x, y) \in \Sigma$. Like in the proof of Lemma 9.5, define $I_{u,v}$ and $d_{u,v}$ for each
$(u, v) \in \Sigma$, as well as $h : \bigsqcup_{(u,v) \in \Sigma} \to A \sqcup N$,

$$ \hat{P} = (A \sqcup N) \cup_h \bigsqcup_{(u,v) \in \Sigma} I_{u,v}, $$

and the metric $\hat{d}$ on $\hat{P}$. Since $d$ is proper and $A$ and $N$ are separated, the $d$-balls in $A \sqcup N$ are finite. Therefore, any ball in $\hat{P}$ is contained in a finite union of segments $I_{u,v}$, and so $\hat{P}$ is proper.

For each $t \in I = [0, 1]$, let $P_t \subseteq \hat{P}$ be the subset consisting of the points $w \in I_{u,v}$ with $d_{u,v}(w, u) = t d(u, v)$ for $(u, v) \in \Sigma$, and let $z_t$ denote the unique point of $P_t \cap I_{x,y}$. Each $P_t$ is a discrete subspace of $\hat{P}$, and it therefore becomes a proper metric space with the restriction of $\hat{d}$. Moreover $(P_0, z_0) = (A, x)$ and $(P_1, z_1) = (N, y)$. For all $t, t' \in I$, $(u, v) \in \Sigma$, $w \in P_t \cap I_{u,v}$ and $w' \in P_{t'} \cap I_{u,v}$,

$$ (9.1) \quad \hat{d}(w, w') = d_{u,v}(w, w') = d(u, v) |t - t'| $$

$$ \le \begin{cases} (s_1 + \epsilon) |t - t'| & \text{for arbitrary } (u, v) \in \Sigma \\ (s_0 + \epsilon) |t - t'| & \text{if } u \in B_A(x, S) \text{ or } v \in B_N(y, S). \end{cases} $$

Thus $\hat{d}(z_t, z_{t'}) \le (s_0 + \epsilon) |t - t'|$ and $H_{\hat{d}}(P_t, P_{t'}) \le (s_1 + \epsilon) |t - t'|$. By Lemma 8.1, it follows that $[P_t, z_t] \in E_{GH}(M, x)$ for all $t \in I$, and the mapping $t \mapsto [P_t, z_t]$ is $d_{GH}$-continuous.

From (9.1), it also follows that $\hat{d}(u, P_t) \le (s_0+\epsilon)t$ for all $u \in B_A(x, S)$ and $t \in I$. Moreover the ball $B_{P_t}(z_t, S)$ is contained in the union of the segments $I_{u,v}$ for $(u, v) \in \Sigma$ with $u \in B_A(x, S)$ or $v \in B_N(y, S)$. So $\hat{d}(w, P_t) \le (s_0+\epsilon)t$ for all $w \in B_P(z_t, S)$ by (9.1). It follows that

$$ H_{\hat{d},S}(A, x; P_t, z_t) \le (s_0 + \epsilon)t < s + \epsilon, $$

obtaining

$$ [P_t, z_t] \in U_{S,s+\epsilon}(A, x) \subseteq U_{S,s+\epsilon} \circ E_{r-s-\epsilon}(M, x) \subseteq U_{R,r}(M, x) $$

by Lemmas 8.2 and 8.3.

□

Hypotheses 1-3 have just been proved, and that suffices to confirm Theorem 1.1 for $(d_{GH}, E_{GH})$.

**Remark 9.11.** As in Remark 7.8, it can be proved that, for all $r > 0$, $\emptyset$ is residual in $B_{GH}(M, x; r)$ if $M$ is unbounded. To see this, for sequences $0 < r_n \uparrow r$ and $0 < R_n \uparrow \infty$, consider the sets $U_n$ consisting of the points $[N, y] \in B_{GH}(M, x; r)$ such that

$$ H_d \left( M \setminus \overline{B_M(x, R_n)}, N \setminus \overline{B_N(y, R_n)} \right) > r_n $$

for every admissible metric, $d$, on $M \sqcup N$.
## 10. THE QI METRIC RELATION

Since $d_{QI} \le d_{GH}$ and Theorem 1.1 is already proved for $d_{GH}$, Remarks 4.2 and 4.6 imply that the proof of Theorem 1.1 for $d_{QI}$ only requires the next proposition.

**Proposition 10.1.** The fibers of $E_{QI}$ are meager in $M_*$.

The proof of Proposition 10.1 requires an analysis of $d_{QI}$, which in turn requires an analysis of $d_{GH}$ and $d_{Lip}$.

A map between metric spaces, $\phi: M \to N$, is called bi-Lipschitz if there is some $\lambda \ge 1$ such that

$$ \frac{1}{\lambda} d_M(u, v) \le d_N(\phi(u), \phi(v)) \le \lambda d_M(u, v) $$

for all $u, v \in M$. A quasi-isometry from $M$ to $N$ is a bi-Lipschitz bijection, $\phi: A \to B$, between nets $A \subseteq M$ and $B \subseteq N$. The existence of a quasi-isometry from $M$ to $N$ is equivalent to the existence of a finite sequence of metric spaces $M = M_0, \dots, M_{2k} = N$ such that $d_{GH}(M_{2i-2}, M_{2i-1}) < \infty$ and such that there is a bi-Lipschitz bijection $M_{2i-1} \to M_{2i}$ for each $i \in \{1, \dots, k\}$. A pointed quasi-isometry is defined analogously, now with the nets having a base point and the bi-Lipschitz bijection between them preserving those base points. The existence of a pointed quasi-isometry has an analogous characterization involving pointed Gromov-Hausdorff distances and pointed bi-Lipschitz bijections.

As noted in Section 8, $d_{Lip}$ is the metric equivalence relation on $M_*$ defined by setting $d_{Lip}(M, x; N, y)$ equal to the infimum of the set of $r \ge 0$ for which there is a pointed $e^r$-bi-Lipschitz bijection $\phi: (M, x) \to (N, y)$.

The distance $d_{QI}(M, x; N, y)$ equals the infimum of all sums

$$ \sum_{i=1}^{k} d_{GH}(M_{2i-2}, x_{2i-2}; M_{2i-1}, x_{2i-1}) + d_{Lip}(M_{2i-1}, x_{2i-1}; M_{2i}, x_{2i}) $$

for finite sequences $[M, x] = [M_0, x_0], \dots, [M_{2k}, x_{2k}] = [N, y]$ in $M_*$. For $[M, x] \in M_*$ and $r > 0$, the notation $B_{Lip}(M, x; r) = B_{d_{Lip}}([M, x], r)$ and $B_{QI}(M, x; r) = B_{d_{QI}}([M, x], r)$ will be used.

**Lemma 10.2.** For $r > 0$ and $R \ge q > p > 2r$, if $[N, y] \in U_{R,r}(M, x)$ and $B_M(x, q) \setminus \overline{B_M(x, p)} \ne \emptyset$, then $B_N(y, q + 2r) \setminus \overline{B_N(y, p - 2r)} \ne \emptyset$.

*Proof.* By hypothesis, there is an admissible metric $d$ on $M \sqcup N$ such that $d(x, y) < r$ and $H_{d,R}(M, x; N, y) < r$, and there is $u \in M$ such that $p < d(x, u) < q$. Since $H_{d,R}(M, x; N, y) < r$, there is $v \in N$ such that $d(u, v) < r$.
Then

$$d_N(y, v) \leq d(x, u) + d(y, x) + d(u, v) < q + 2r,$$

and, similarly, $d_N(y, v) > p - 2r$.

<figure><img src="image_5.png" /></figure>

**Corollary 10.3.** If $d_{GH}(M, x; N, y) < r$ and $q > p > 2r$ are such that $B_M(x, q) \setminus \overline{B_M(x, p)} \neq \emptyset$, then $B_N(y, q + 2r) \setminus \overline{B_N(y, p - 2r)} \neq \emptyset$.

**Lemma 10.4.** If $d_{\text{Lip}}(M, x; N, y) < r$ and $p > q > 0$ are such that $B_M(x, q) \setminus \overline{B_M(x, p)} \neq \emptyset$, then $B_N(y, e^r q) \setminus \overline{B_N(y, e^{-r} p)} \neq \emptyset$.

*Proof.* By hypothesis, there is a pointed $e^r$-bi-Lipschitz bijection $\phi : (M, x) \to (N, y)$, and there is $u \in M$ such that $p < d(x, u) < q$. Then

$$d_N(y, \phi(u)) \leq e^r d_M(x, u) < e^r q,$$

and, similarly, $d_N(y, \phi(u)) > e^{-r} p$, showing the result.

<figure><img src="image_6.png" /></figure>

*Proof of Proposition 10.1.* The pointed compact metric spaces form an equivalence class of $E_{GH}$ which is meager in $M_*$ by Theorem 1.1 (i) for $(d_{GH}, E_{GH})$. Moreover any metric space bi-Lipschitz equivalent to a bounded one is also bounded. So the pointed compact metric spaces also form a class of $E_{QI}$. Thus, to prove Proposition 10.1, it is enough to consider the fiber $E_{QI}(M, y)$ for any unbounded proper metric space $M$. Hence there are sequences $p_n, q_n \uparrow \infty$ such that $q_n > p_n > 0$ and $B_M(x, q_n) \setminus \overline{B_M(x, p_n)} \neq \emptyset$.

**Claim 8.** Let $r, s > 0$ and $n \in \mathbb{N}$ so that $p_n > 2r$ and $2s < e^{-r}(q_n - 2r)$. If $[N, y] \in \overline{B_{QI}(M, x; r)}$, then

$$(10.1) \qquad B_N(y, e^r(q_n + 2r) + 2s) \setminus \overline{B_N(y, e^{-r}(p_n - 2r) - 2s)} \neq \emptyset.$$

For the proof, let $S > e^r(q_n + 2r)$. Since $[N, y] \in \overline{B_{QI}(M, x; r)}$, there is a finite sequence, $[M, x] = [M_0, x_0], \dots, [M_{2k}, x_{2k}]$ in $M_*$ such that $[M_{2k}, x_{2k}] \in U_{S,s}(N, y)$ and

$$\sum_{i=1}^{k} d_{GH}(M_{2i-2}, x_{2i-2}; M_{2i-1}, x_{2i-1}) + d_{\text{Lip}}(M_{2i-1}, x_{2i-1}; M_{2i}, x_{2i}) < r.$$

Let $r_1, \dots, r_{2k} > 0$ be such that $\sum_{j=1}^{2k} r_j < r$ and, for $j \in \{1, \dots, 2k\}$,

$$r_j > \begin{cases} d_{GH}(M_{j-1}, x_{j-1}; M_j, x_j) & \text{if } j \text{ is odd} \\ d_{\text{Lip}}(M_{j-1}, x_{j-1}; M_j, x_j) & \text{if } j \text{ is even.} \end{cases}$$

Let $\bar{r}_j = \sum_{a=1}^{j} r_a$. Arguing by induction on $j$, using Corollary 10.3 and Lemma 10.4, it follows that

$$B_{M_j}(x_j, e^{\bar{r}_j}(q_n + 2\bar{r}_j)) \setminus \overline{B_{M_{2k}}(x_{2k}, e^{-\bar{r}_j}(q_n - 2\bar{r}_j))} \neq \emptyset$$
for all $j$. So

$$B_{M_{2k}}(x_{2k}, e^r(q_n + 2r)) \setminus \overline{B_{M_{2k}}(x_{2k}, e^{-r}(q_n - 2r))} \neq \emptyset.$$

Then (10.1) follows by Lemma 10.2, completing the proof of Claim 8.

**Claim 9.** For each $r > 0$, $B_{QI}(M, x; r)$ is nowhere dense in $M_*$.

Let $[N, y] \in \overline{B_{QI}(M, x; r)}$. Given $S, s > 0$, there is some $n \in \mathbb{N}$ such that $p_n > 2r$ and $S < e^{-r}(q_n - 2r) - 2s$. Thus (10.1) is satisfied with these $[N, y]$, $r, s$ and $n$. Let

$$N' = N \setminus \left( B_N(y, e^r(q_n + 2r) + 2s) \setminus \overline{B_N(y, e^{-r}(q_n - 2r) - 2s)} \right).$$

With the restriction of $d_N$, $N'$ is a proper metric space with $B_{N'}(y, S) = B_N(y, S)$, obtaining $[N', y] \in U_{S,s}$. But $[N', y] \notin \overline{B_{QI}(M, x; r)}$ by Claim 8 because

$$B_{N'}(y, e^r(q_n + 2r) + 2s) \setminus \overline{B_{N'}(y, e^{-r}(p_n - 2r) - 2s)} = \emptyset.$$

So $U_{S,s}(N, y) \not\subseteq \overline{B_{QI}(M, x; r)}$. Then Claim 9 follows since $s$ can be chosen arbitrarily small, and $S$ arbitrarily large by choosing $n$ arbitrarily large.

Since $E_{QI}(M, x) = \bigcup_{r=1}^{\infty} B_{QI}(M, x; r)$, Claim 9 concludes the proof of Proposition 10.1. □

**Acknowledgements.** This research was partly supported by MICINN, Spain (grants no. MTM2008-02640, MTM2011-25656 and MTM2014-56950-P), and Xunta de Galicia (Consolidación e estructuración 2015 GPC GI-1574).

The authors thank the referees and editors for having contributed a variety of remarks which helped in improving the presentation of this paper.

## REFERENCES

[1] J.A. Álvarez López and A. Candel, *Non-reduction of relations in the Gromov space to Polish actions*, to appear in Notre Dame J. Form. Log., preprint arXiv:1501.02606.

[2] H. Becker and A.S. Kechris, *The descriptive set theory of Polish group actions*, London Mathematical Society Lecture Note Series, vol. 232, Cambridge University Press, Cambridge, 1996. MR 1425877 (98d:54068)

[3] M. Gromov, *Groups of polynomial growth and expanding maps. Appendix by Jacques Tits*, Inst. Hautes Études Sci. Publ. Math. (1981), no. 53, 53–73. MR 623534 (83b:53041)
[4] M. Gromov, *Metric structures for Riemannian and non-Riemannian spaces*, Progress in Mathematics, vol. 152, Birkhäuser Boston Inc., Boston, MA, 1999, Based on the 1981 French original [MR0682063 (85e:53051)], With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates. MR 1699320 (2000d:53065)

[5] G. Hjorth, *Classification and orbit equivalence relations*, Mathematical Surveys and Monographs, vol. 75, American Mathematical Society, Providence, RI, 2000. MR 1725642 (2000k:03097)

[6] G. Hjorth, *A dichotomy theorem for turbulence*, J. Symbolic Logic **67** (2002), no. 4, 1520–1540. MR 1955250 (2004b:03069)

[7] A.S. Kechris, *Classical descriptive set theory*, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597 (96e:03057)

[8] A.S. Kechris, *Descriptive dynamics*, Descriptive set theory and dynamical systems (Marseille-Luminy, 1996), London Math. Soc. Lecture Note Ser., vol. 277, Cambridge Univ. Press, Cambridge, 2000, pp. 231–258. MR 1774428 (2001j:37038)

[9] A.S. Kechris and B.D. Miller, *Topics in orbit equivalence*, Lecture Notes in Mathematics, vol. 1852, Springer-Verlag, Berlin, 2004. MR 2095154 (2005f:37010)

[10] C. Kuratowski and S. Ulam, *Quelques propriétés topologiques du produit combinatoire*, Fundamenta Mathematicae **19** (1932), no. 1, 247-251.

[11] P. Petersen, *Riemannian geometry*, Graduate Texts in Mathematics, vol. 171, Springer-Verlag, New York, 1998. MR 1480173 (98m:53001)

[12] F. Plastria, *Asymmetric distances, semidirected networks and majority in Fermat-Weber problems*, Ann. Oper. Res. **167** (2009), 121–155. MR 2506484 (2010f:90078)

DEPARTAMENTO DE MATEMÁTICAS, FACULTADE DE MATEMÁTICAS, UNIVERSIDADE DE SANTIAGO DE COMPOSTELA, 15782 SANTIAGO DE COMPOSTELA, SPAIN
*E-mail address: jesus.alvarez@usc.es*

DEPARTMENT OF MATHEMATICS, CALIFORNIA STATE UNIVERSITY AT NORTHRIDGE, 18111 NORDHOFF STREET, NORTHRIDGE, CA 91330, U.S.A.
*E-mail address: alberto.candel@csun.edu*