|
This article is cited in 1 scientific paper (total in 1 paper)
Geometry of the Gromov-Hausdorff distance on the class of all metric spaces
S. I. Borzova, A. O. Ivanovbcd, A. A. Tuzhilinb a Pyrus JSC, Moscow, Russia
b Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
c Bauman Moscow State Technical University, Moscow, Russia
d Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia
Abstract:
The geometry of the Gromov-Hausdorff distance on the class of all metric spaces considered up to isometry is studied. The concept of a class in the sense of von Neumann-Bernays-Gödel set theory is used. As in the case of compact metric spaces, continuous curves and their lengths are defined, and the Gromov-Hausdorff distance is shown to be intrinsic on the entire class. As an application, metric segments (classes of points lying between two given points) are considered and their extendability beyond endpoints is examined.
Bibliography: 13 titles.
Keywords:
Gromov-Hausdorff distance, class of all metric spaces, geodesic, metric segment, extendability of a geodesic.
Received: 09.08.2021
Introduction The geometry of ‘hyperspaces’ or spaces of subsets, which plays an essential role both in theoretical investigations and in numerous applications like comparison and recognition of images, has long attracted the attention of scientists working in a variety of specialized fields. One natural approach to the study of such spaces is to equip them with a distance function as a measure of ‘unlikeness’ of the corresponding objects. So, in 1914 Hausdorff (see [1]) defined a symmetric nonnegative function on pairs of nonempty subsets of a metric space $X$ as the infimum of the numbers $r$ such that the first set is contained in the $r$-neighbourhood of the second and vice versa. This function satisfies the triangle inequality, and the set of all closed bounded subsets of $X$ equipped with this function becomes a metric space. Subsequently, Edwards [2] and, independently, Gromov [3] used isometric embeddings in all possible ambient spaces (see the definition below) to generalize Hausdorff’s construction to the family of all compact metric spaces. The function thus obtained, which is known as the Gromov-Hausdorff distance, is also symmetric, nonnegative, satisfies the triangle inequality, but can assume infinite values. The Gromov-Hausdorff distance between isometric spaces is always zero. This has given an impetus to study the isometry classes of metric spaces. However, this distance can also be zero between nonisometric spaces (for example, between the closed interval $[0,1]$ and the open interval $(0,1)$). Nevertheless, if we content ourselves with the family $\mathcal M$ of isometry classes of all compact metric spaces, then the Gromov-Hausdorff distance satisfies all the axioms of a metric on $\mathcal M$. The set $\mathcal M$ equipped with the Gromov-Hausdorff distance is called the Gromov-Hausdorff space. The geometry of this metric space, which is quite nontrivial, is being actively studied at the present time. It is well known that $\mathcal M$ is path-connected, Polish (that is, separable and complete) and geodesic (see [4]). We also note that $\mathcal M$ is not proper (boundedly compact) and has no nontrivial symmetries (see [5]). For a detailed introduction to the geometry of the Gromov-Hausdorff space, see, for example, [6], Ch. 7, and [7]. In the equally interesting noncompact setting one does not usually deal with the Gromov-Hausdorff distance, but rather with its modification referred to as pointed convergence — namely, in each metric space one chooses a point, and convergence is defined to be the convergence of the balls of the same radius with centres at these points. For example, the tangent cones and asymptotic cones with apex at a given point are defined by means of this convergence. We also note that in some recent studies (see, for example, [8]) distance functions were proposed such that pointed convergence is convergence with respect to this distance. Moreover, these distance functions turn out to be metrics on the class of pointed proper metric spaces. In the present paper we study the Gromov-Hausdorff distance in its initial definition on the class $\operatorname{\mathcal{G\!H}}$ of all metric spaces considered up to isometry. Here a ‘class’ is understood in the sense of the von Neumann-Bernays-Gödel axiomatic system, using which one can consistently define a distance function on this proper class. However, this proper class cannot be endowed with a metric topology following the standard approach to ‘usual’ sets equipped with a distance function (for details, see below). This difficulty can be circumvented by using cardinality filtrations. As a result, continuous curves in $\operatorname{\mathcal{G\!H}}$ can be defined. Moreover, we will also show that the Gromov-Hausdorff distance is an intrinsic extended pseudometric, that is, the distance between any two points is equal to the infimum of the lengths of curves connecting these points. The machinery developed in our paper is used in the study of the geometry of so-called metric segments in the class $\operatorname{\mathcal{G\!H}}$. Here a metric segment is understood to be the class of all points lying between two fixed points (the endpoints of this metric segment). We show that a metric segment may turn out to be a proper class (rather than a set). Moreover, we examine the extendability of a metric segment (to a metric segment) beyond one of its endpoints. This problem was found to be quite challenging, and has at present no complete solution even for the Gromov-Hausdorff space $\mathcal M$. The key result here is Theorem 5, which gives a sufficient condition for the nonextendability of a metric segment beyond one of its endpoints. Several examples are given in the concluding section, § 4. Worthy of special mention is Example 3: this interesting example is based on Hadwiger’s theorem, which solves the Borsuk problem in a particular case. We conclude that section by showing that no metric segment whose endpoints are bounded metric spaces can be extended indefinitely beyond both endpoints.
§ 1. Necessary definitions and preliminary results In this section we give the necessary definitions and recall results from metric geometry, Gromov-Hausdorff distance geometry and von Neumann-Bernays-Gödel set theory. We also construct an analogue of a metric topology on proper set-filtered classes endowed with a distance function (the definition of a set-filtered class is given below). 1.1. Distance functions Let $X$ be an arbitrary set. We denote the cardinality of $X$ by $\#X$, and the set of all nonempty subsets of $X$ by $\mathcal P_0(X)$. A distance function on $X$ is by definition a symmetric mapping $d\colon X\times X\to[0,\infty]$ that vanishes on pairs of equal elements. If $d$ satisfies the triangle inequality, then $d$ is referred to as an extended pseudometric. In addition, if $d(x,y)>0$ for all $x\ne y$, then $d$ is called an extended metric. Furthermore, if $d(x,y) < \infty$ for all $x,y\in X$, then such a distance function is called a metric or, sometimes, a finite metric, to emphasize its difference from an extended metric. A set $X$ equipped with an (extended) (pseudo)metric is said to be an (extended) (pseudo)metric space. If $X$ is a space equipped with a distance function, then, as a rule, the distance between points $x$ and $y$ of $X$ will be denoted by $|xy|$. Next, if $\gamma\colon [a,b]\to X$ is a continuous curve in $X$, then the length of $|\gamma|$ is defined to be the supremum of the ‘lengths of inscribed polygonal lines’ (the supremum of the quantities $\sum_i|\gamma(t_i)\gamma(t_{i+1})|$, where we consider all finite partitions $a=t_1<\dots<t_k=b$ of the interval $[a,b]$). Let $x,y\in X$ and $|xy|<\infty$. We say that $z\in X$ lies between $x$ and $y$ if $|xz|+|zy|=|xy|$. If, moreover, $|xz|>0$ and $|zy|>0$, then we say that $z$ lies strictly between $x$ and $y$. The set of all $z$ lying between $x$ and $y$ is called the metric segment between $x$ and $y$ and denoted by $[x,y]$. If $|xy| > 0$, then the metric segment $[x,y]$ is called nondegenerate. Definition 1. We say that a metric segment $[x,y]$ is extendable beyond the point $y$ if there exists a point $z\in X$ such that $[x,z]$ contains $y$ and $|yz|>0$. Remark 1. If $|xy|=0$, then any point $z$ for which $|zx|>0$ (and therefore $|zy|=|zx|>0$) extends the metric segment both beyond $x$ and beyond $y$. We are mostly concerned with the extendability of nondegenerate metric segments. Let $X$ be a metric space. Given $A,B\in\mathcal P_0(X)$ and $x\in X$, we set
$$
\begin{equation*}
|xA|=|Ax|=\inf\bigl\{|xa|\colon a\in A\bigr\}, \qquad |AB|=\inf\bigl\{|ab|\colon a\in A,\,b\in B\bigr\}
\end{equation*}
\notag
$$
and
$$
\begin{equation*}
d_H(A,B)=\max\Bigl\{\sup_{a\in A}|aB|,\,\sup_{b\in B}|Ab|\Bigr\} =\max\Bigl\{\sup_{a\in A}\inf_{b\in B}|ab|,\,\sup_{b\in B}\inf_{a\in A}|ba|\Bigr\}.
\end{equation*}
\notag
$$
The function $d_H\colon \mathcal P_0(X)\times\mathcal P_0(X)\to[0,\infty]$ is called the Hausdorff distance. It is well known (see [6]) that $d_H$ is a metric on the subfamily $\mathcal H(X)\subset\mathcal P_0(X)$ of all closed nonempty bounded subsets of $X$. Let $X$ and $Y$ be metric spaces. A triplet $(X',Y',Z)$ consisting of a metric space $Z$ and two subsets $X'$ and $Y'$ of it that are isometric to $X$ and $Y$, respectively, is called a realization of the pair $(X,Y)$. The Gromov-Hausdorff distance $d_{GH}(X,Y)$ between $X$ and $Y$ is defined to be the infimum of the numbers $r$ for which there exists a realization $(X',Y',Z)$ of the pair $(X,Y)$ such that $d_H(X',Y')\leqslant r$. Notice that the Gromov-Hausdorff distance can assume both finite and infinite values; on the other hand it always satisfies the triangle inequality; see [6]. Moreover, this distance is zero for any pair of isometric spaces, hence by the triangle inequality, the Gromov-Hausdorff distance is well defined on isometry classes of metric spaces (it does not depend on the choice of representatives of these classes). It should be noted that there are examples of nonisometric metric spaces with zero Gromov-Hausdorff distance. Each nonempty set can be endowed with some metric (for example, by setting the distance between any two unequal points to be 1), and so there are ‘at least as many’ isometry classes of metric spaces as there are sets, that is, all these classes do not form a set, but rather a class, which, when equipped with the Gromov-Hausdorff distance, will be denoted by $\operatorname{\mathcal{G\!H}}$. Here, a class is understood in the sense of von Neumann-Bernays-Gödel ($\mathrm{NBG}$) set theory. 1.2. The von Neumann-Bernays-Gödel axioms, distance function and the topology on a proper class In NBG all objects (analogues of usual sets) are referred to as classes. There are two types of classes: sets and proper classes. An example of a proper class is the class of all sets. According to Gödel’s construction, we can distinguish a set from a proper class as follows: for a set there always exists a class containing this set as an element. However, there is no such a class for a proper class. So sets are elements of some class. Many standard operations are defined for classes — for example, intersection, complementation (for each class, there exists a class consisting precisely of the elements that are not members of the first class), direct product, mappings and so on. According to von Neumann’s theorem, a class is a proper class if and only if it can be mapped surjectively onto the class of all sets. Such concepts as a distance function, an (extended) pseudometric and an (extended) metric are defined for any class (for sets and proper class alike) because the direct product operation and mappings are defined for all classes. However, the definitions of other structures on proper classes are not so straightforward. For example, if we try to define a topology on some proper class $\mathfrak C$ in the usual way, then, on the one hand, the class $\mathfrak C$ should be an element of the topology. On the other hand, in this case $\mathfrak C$ must be a set, which is impossible. To circumvent this difficulty, we filter each class $\mathfrak C$ into the subclasses $\mathfrak C_n$ of elements of $\mathfrak C$ with cardinality at most $n$, where $n$ is a cardinal number. Recall that elements of any class are sets, for which the concept of cardinality is well defined. As basic examples of classes, we mention the class $\operatorname{\mathcal{G\!H}}$ defined above, and the class $\mathcal B$ of all bounded metric spaces considered up to isometry. Note that for any cardinal number $n$ $\operatorname{\mathcal{G\!H}}_n$ and $\mathcal B_n$ are sets. Indeed, the family of all cardinals not exceeding a given cardinal number is a set, and for any fixed cardinal $n$ the family of all isometry classes of metric spaces of cardinality $n$ ‘is not greater’ than the set of all subsets of $X\times X\times \mathbb R$, where $X$ is an arbitrary set of cardinality $n$. We say that a class $\mathfrak C$ is set-filtered if all of its subclasses $\mathfrak C_n$ are sets. It is clear that if a class $\mathfrak C$ is a set, then it is set-filtered. So let $\mathfrak C$ be a set-filtered class. We say that this class satisfies some property if this property holds for each set $\mathfrak C_n$. Now we give some examples. $\bullet$ Let $\mathfrak C$ be equipped with a distance function. This distance function induces a ‘usual’ distance function on each $\mathfrak C_n$. Thus, all the objects of metric geometry (see above) like open balls can be defined in each $\mathfrak C_n$, and they are sets. As a result, $\mathfrak C_n$ can be equipped with a metric topology $\tau_n$, for which these balls form a base. It is clear that if $n\leqslant m$, then $\mathfrak C_n\subset\mathfrak C_m$, and the topology $\tau_n$ on $\mathfrak C_n$ is induced from $\mathfrak C_m$. $\bullet$ More generally, a topology on a class $\mathfrak C$ is defined as follows: each $\mathfrak C_n$ is equipped with some topology $\tau_n$ so that the following consistency condition holds: if $n\leqslant m$, then $\tau_n$ is the topology on $\mathfrak C_n$ induced from $\mathfrak C_m$. $\bullet$ Given a topology on a class $\mathfrak C$, one can define, for example, continuous mappings from some topological space $Z$ to $\mathfrak C$. Note that, in accordance with the $\mathrm{NBG}$ axioms, for an arbitrary mapping $f\colon\mkern-1mu Z\mkern-2mu\to\mkern-2mu\mathfrak C$ from a set $Z$ to a class $\mathfrak C$ the image $f(Z)$ is a set, all elements of $f(Z)$ are also sets, and their union $\bigcup f(Z)$ is a set of some cardinality $n$. Hence the cardinality of each element of $f(Z)$ is at most $n$, and therefore $f(Z)\subset\mathfrak C_n$. A mapping $f$ is said to be continuous if $f$ is continuous as a mapping from $Z$ into $\mathfrak C_n$. The consistency condition implies that, for each $m\geqslant n$, the mapping $f$ is also continuous from $Z$ to $\mathfrak C_m$, and moreover, for each $k\leqslant n$ such that $f(Z)\subset\mathfrak C_k$ the mapping $f|_{\mathfrak C_k}$, considered as a mapping from $Z$ to ${\mathfrak C}_k$, is continuous. $\bullet$ The observations above allow us to define continuous curves in a class $\mathfrak C$ endowed with a topology. $\bullet$ Let a class $\mathfrak C$ be equipped with a distance function and the corresponding topology. We say that this distance function is intrinsic if it satisfies the triangle inequality and, in addition, for any two elements of $\mathfrak C$ lying at a finite distance from each other, this distance is the infimum of the lengths of curves connecting these elements. We show below that the Gromov-Hausdorff distance is intrinsic on both the class $\operatorname{\mathcal{G\!H}}$ and the class $\mathcal B$. 1.3. Properties of the Gromov-Hausdorff distance The best investigated subset of $\operatorname{\mathcal{G\!H}}$ is the set of isometry classes of compact metric spaces. This set, which is frequently denoted by $\mathcal M$, is called the Gromov-Hausdorff space. It is well known (see [6] and [4]) that the restriction of the Gromov-Hausdorff distance to $\mathcal M$ is a metric and the space $\mathcal M$ is Polish and geodesic. To simplify our notation we do not distinguish between isometry classes of metric spaces and their particular representatives. We used this convention already when we defined $\mathcal B$ to be the class of bounded metric spaces considered up to isometry. This identification will frequently be used below, and we will write, for example, $X\in\operatorname{\mathcal{G\!H}}$ bearing in mind that $X$ is a concrete metric space. As a rule, an evaluation of the Gromov-Hausdorff distance between particular metric spaces involves considerable difficulties, and this distance is currently known only for a few pairs of spaces (see, for example, [9]). Concrete calculations can be made substantially easier by using the following (equivalent) definition of the Gromov-Hausdorff distance. Recall that each subset of the Cartesian product $X\times Y$ is called a relation between the sets $X$ and $Y$. So $\mathcal P_0(X\times Y)$ is the set of all nonempty relations between $X$ and $Y$. Definition 2. Given $X,Y\in\operatorname{\mathcal{G\!H}}$ and $\sigma\in\mathcal P_0(X\times Y)$, the quantity
$$
\begin{equation*}
\operatorname{dis}\sigma=\sup\bigl\{\bigl||xx'|-|yy'|\bigr|\colon (x,y),(x',y')\in\sigma\bigr\}
\end{equation*}
\notag
$$
is called the distortion of the relation $\sigma$. A relation $R\subset X\times Y$ between sets $X$ and $Y$ is called a correspondence if the restrictions to $R$ of the canonical projections $\pi_X\colon (x,y)\mapsto x$ and $\pi_Y\colon (x,y)\mapsto y$ are surjective. Note that a correspondence can informally be viewed as a set-valued bijective mapping. We denote the set of all correspondences between $X$ and $Y$ by $\mathcal R(X,Y)$. Theorem 1 (see [6]). For any $X,Y\in\operatorname{\mathcal{G\!H}}$,
$$
\begin{equation*}
d_{GH}(X,Y)=\frac12\inf\bigl\{\operatorname{dis} R\colon R\in\mathcal R(X,Y)\bigr\}.
\end{equation*}
\notag
$$
We also need the following estimates, which can easily be derived with the help of Theorem 1. We denote the one-point metric space by $\Delta_1$. Proposition 1. For any $X,Y\in\operatorname{\mathcal{G\!H}}$, $\bullet$ $2d_{GH}(\Delta_1,X)=\operatorname{diam} X$; $\bullet$ $2d_{GH}(X,Y)\leqslant\max\{\operatorname{diam} X,\operatorname{diam} Y\}$; $\bullet$ if the diameter of $X$ or $Y$ is finite, then $|\operatorname{diam} X-\operatorname{diam} Y|\leqslant2d_{GH}(X,Y)$. Corollary 1. If $X,Y\in\mathcal B$, then $[X,Y]$ is well defined and $[X,Y]\subset\mathcal B$. Given topological spaces $X$ and $Y$, we regard $X\times Y$ as a topological space with the standard topology of a Cartesian product. In this case we can speak about closed relations and closed correspondences. A correspondence $R\in\mathcal R(X,Y)$ will be called optimal if $2d_{GH}(X,Y)=\operatorname{dis} R$. We denote the set of optimal correspondences between $X$ and $Y$ by $\mathcal R_{\mathrm{opt}}(X,Y)$ and the subset of $\mathcal R_{\mathrm{opt}}(X,Y)$ consisting of all closed optimal correspondences by $\mathcal R_{\mathrm{opt}}^c(X,Y)$. Theorem 2 (see [10] and [11]). For any spaces $X,Y\in\mathcal M$, there exist a closed optimal correspondence between them and also a realization $(X',Y',Z)$ of the pair $(X,Y)$ at which the Gromov-Hausdorff distance between $X$ and $Y$ is attained. Theorem 3 (see [10], [11]). For any $X,Y\in\mathcal M$ and each $R\in\mathcal R^c_{\mathrm{opt}}(X,Y)$ the family $R_t$, $t\in[0,1]$, of compact metric spaces such that $R_0=X$, $R_1=Y$ and, for each $t\in(0,1)$, the space $R_t$ is the set $R$ equipped with the metric
$$
\begin{equation*}
\bigl|(x,y),(x',y')\bigr|_t=(1-t)|xx'|+t|yy'|,
\end{equation*}
\notag
$$
is a shortest curve in $\mathcal M$ connecting $X$ and $Y$, and the length of this curve is $d_{GH}(X,Y)$. We will also use the following notation. Let $X$ be an arbitrary set and $m$, $1<m\leqslant\#X$ be a cardinal number. Let $\mathcal C_m(X)$ denote the family of all possible coverings of $X$ by $m$ nonempty subsets and $\mathcal D_m(X)$ denote the family of all partitions of $X$ into $m$ nonempty subsets. It is clear that $\mathcal D_m(X)\subset\mathcal C_m(X)$. If $X$ is a metric space, then for any $D=\{X_i\}_{i\in I}\in\mathcal C_m(X)$ we set
$$
\begin{equation*}
\operatorname{diam} D=\sup_{i\in I}\operatorname{diam} X_i\quad\text{and} \quad \alpha(D)=\inf\bigl\{|X_iX_j|\colon i\ne j\bigr\}.
\end{equation*}
\notag
$$
We also define
$$
\begin{equation*}
d_m(X)=\inf_{D\in\mathcal D_m(X)}\operatorname{diam} D\quad\text{and} \quad \alpha_m(X)=\sup_{D\in\mathcal D_m(X)}\alpha(D).
\end{equation*}
\notag
$$
§ 2. Gromov-Hausdorff distance is intrinsic Let $\mathfrak C$ be a set-filtered class endowed with a distance function that satisfies the triangle inequality, let $x,y \in \mathfrak C$, $|xy|<\infty$, and let $\gamma$ be a curve in $\mathfrak C$ connecting $x$ and $y$. We say that $\gamma$ is an $\varepsilon$-shortest curve for $x$ and $y$ if $0\leqslant|\gamma|-|xy|\leqslant\varepsilon$. It is easily seen that a distance function satisfying the triangle inequality on $\mathfrak C$ is intrinsic if and only if, for each pair of elements of $\mathfrak C$ lying at a finite distance from each other and each $\varepsilon>0$, there exists an $\varepsilon$-shortest curve for this pair. This fact is used in the proof of the following theorem. Theorem 4. Let $X$ and $Y$ be arbitrary metric spaces satisfying $d_{GH}(X,Y)<\infty$ and let $R\in\mathcal R(X,Y)$ be an arbitrary correspondence such that
$$
\begin{equation*}
\operatorname{dis} R-2d_{GH}(X,Y)\leqslant2\varepsilon.
\end{equation*}
\notag
$$
Consider the family $R_t$, $t\in[0,1]$, of metric spaces, where $R_0=X$ and $R_1=Y$, and, for $t\in(0,1)$, the space $R_t$ is the set $R$ equipped with the metric
$$
\begin{equation*}
\bigl|(x,y),(x',y')\bigr|_t=(1-t)|xx'|+t|yy'|.
\end{equation*}
\notag
$$
Then $R_t$, $t\in[0,1]$, is an $\varepsilon$-shortest curve in $\operatorname{\mathcal{G\!H}}$ connecting $X$ and $Y$. Moreover, if $X$ and $Y$ are bounded spaces, then all the $R_t$ are also bounded spaces, that is, $R_t$ is an $\varepsilon$-shortest curve in $\mathcal B$. Proof. We set $n=\#R$ and consider the following correspondences $R_X\subset X\times R$ and $R_Y\subset R\times Y$ between $X$ and $R_t$ and between $R_t$ and $Y$:
$$
\begin{equation*}
R_X=\bigl\{(x,(x,y))\colon x\in X,\,(x,y)\in R\bigr\}\quad\!\!\text{and}\!\!\quad R_Y=\bigl\{((x,y),y)\colon y\in Y,\,(x,y)\in R\bigr\}.
\end{equation*}
\notag
$$
Note that $\operatorname{dis} R_X=t\operatorname{dis} R$ and $\operatorname{dis} R_Y=(1-t)\operatorname{dis} R$. Next consider the identity correspondence between the spaces $R_t$ and $R_s$, $s,t\in(0,1)$. Then we see that $2d_{GH}(R_t,R_s)\leqslant|t-s|\operatorname{dis} R$. We also set $\gamma(t)=R_t$. It follows from the above that $\gamma$ is a continuous mapping from $[0,1]$ to $\operatorname{\mathcal{G\!H}}_n$, that is, $\gamma$ is a continuous curve in $\operatorname{\mathcal{G\!H}}$. Moreover, $2|\gamma|\leqslant\operatorname{dis} R$, hence $|\gamma|\leqslant d_{GH}(X,Y)+\varepsilon$, which implies that $\gamma$ is an $\varepsilon$-shortest curve connecting $X$ and $Y$. It remains to note that $\operatorname{diam} R_t\leqslant\max\{\operatorname{diam} X, \operatorname{diam} Y\}$, so that $R_t\in\mathcal B$ for all $t$ whenever $X,Y\in\mathcal B$.
Theorem 4 is proved. Corollary 2. The Gromov-Hausdorff distance is an intrinsic extended pseudometric on the class $\operatorname{\mathcal{G\!H}}$, and it is an intrinsic finite pseudometric on the class $\mathcal B$. The $\varepsilon$-shortest curve constructed in Theorem 4 will be called linear. Remark 2. The proof of Theorem 4 shows that a linear $\varepsilon$-shortest curve connecting metric spaces $X$ and $Y$ with finite $d_{GH}(X,Y)$ is a Lipschitz curve in $\operatorname{\mathcal{G\!H}}$, and moreover, one of its Lipschitz constants is $d_{GH}(X,Y)+\varepsilon$.
§ 3. Metric segments and their extendability We start with a description of simple properties of $\varepsilon$-shortest curves in an extended pseudometric space $\mathfrak C$, where $\mathfrak C$ is some set-filtered class. Lemma 1. Let $x,y\in\mathfrak C$, $|xy|<\infty$, let $\gamma$ be an $\varepsilon$-shortest curve connecting $x$ and $y$, and let $w$ be an arbitrary point on $\gamma$. Then the segments $\gamma_{xw}$ and $\gamma_{wy}$ of the curve $\gamma$ between the points $x$, $w$ and $w$, $y$, respectively, are $\varepsilon$-shortest curves for their endpoints, and, moreover, $|xw|+|wy|-|xy|\leqslant\varepsilon$. Proof. In fact, from the definition of an $\varepsilon$-shortest curve, by the additivity of the length of a curve, and from the triangle inequality we have
$$
\begin{equation*}
\varepsilon\geqslant|\gamma|-|xy|=|\gamma_{xw}|+|\gamma_{wy}|-|xy| \geqslant\bigl(|\gamma_{xw}|-|xw|\bigr)+\bigl(|\gamma_{wy}|-|wy|\bigr).
\end{equation*}
\notag
$$
The expressions in brackets are nonnegative, so each of them is majorized by $\varepsilon$. Hence $\gamma_{xw}$ and $\gamma_{wy}$ are $\varepsilon$-shortest curves. Further,
$$
\begin{equation*}
|xw|+|wy|\leqslant|\gamma_{xw}|+|\gamma_{wy}|=|\gamma_{xy}|\leqslant|xy|+\varepsilon,
\end{equation*}
\notag
$$
which completes the proof of Lemma 1. Of course, the union of two $\varepsilon$-shortest curves is not an $\varepsilon$-shortest curve in general. Nevertheless, the following result holds. Lemma 2. Let $x,y\in\mathfrak C$, $|xy|<\infty$, and let a point $w\in\mathfrak C$ lie between $x$ and $y$. Then the union of an $\varepsilon$-shortest curve $\gamma_{xw}$ for $x$ and $w$ and an $\delta$-shortest curve $\gamma_{wy}$ for $w$ and $y$ is an $(\varepsilon+\delta)$-shortest curve for $x$ and $y$. Proof. Denoting the union of the curves $\gamma_{xw}$ and $\gamma_{wy}$ by $\gamma_{xy}$, we have
$$
\begin{equation*}
|xy|=|xw|+|wy|\geqslant|\gamma_{xw}|-\varepsilon+|\gamma_{wy}|-\delta=|\gamma_{xy}|-(\varepsilon+\delta),
\end{equation*}
\notag
$$
as required. From Lemmas 1 and 2 we have the following estimate. Corollary 3. Let $x,y\in\mathfrak C$, $|xy|<\infty$, and let $w\in\mathfrak C$ be a point between $x$ and $y$. Next, let $\gamma_{xw}$ and $\gamma_{wy}$ be $\varepsilon$-shortest curves connecting $x$ with $w$ and $w$ with $y$, respectively. Then $|pw|+|wq|-|pq|\leqslant2\varepsilon$ for any points $p$ and $q$ on $\gamma_{xw}$ and $\gamma_{wy}$, respectively. We mention some elementary properties of metric segments. Lemma 3. Given $x,y,z\in\mathfrak C$, $\bullet$ if $y\in[x,z]$, then $[x,y]\subset[x,z]$ and $[y,z]\subset[x,z]$; $\bullet$ if $y$ lies between $x$ and $z$, then $y$ also lies between any points $x'\in[x,y]$ and $z'\in[y,z]$. Remark 3. If $\mathfrak C$ is a geodesic space, then the extendability of a metric segment $[x,y]$ beyond $y$ is equivalent to the existence of $z\in\mathfrak C$ such that any shortest curve connecting $x$ with $y$ lies in some shortest curve connecting $x$ with $z$. Remark 4. If $\mathfrak C$ is a proper class, then a metric segment can also be a proper class. For example, consider the space $\operatorname{\mathcal{G\!H}}$ and the metric segment $[\Delta_1,\Delta_n]$ in $\operatorname{\mathcal{G\!H}}$, where $\Delta_n$ is the metric space of cardinality $n$ in which all nonzero distances are equal to $1$. It is easily checked that the curve $\gamma(t)$, $t\in[0,1]$, where $\gamma(0)=\Delta_1$ and $\gamma(t)=t\Delta_n$ for the other $t$, is a shortest curve connecting $\Delta_1$ and $\Delta_n$. Here and in what follows let $\lambda\Delta_n$ denote the metric space of cardinality $n$ all distances in which are equal to $\lambda$, that is, $\lambda\Delta_n$ is obtained from $\Delta_n$ by a dilation by $\lambda$. Consider the space $Z=\frac12\Delta_n$ and replace a point $z\in Z$ by a nonempty set $A$ of arbitrary cardinality. Fix a positive $\varepsilon<1/2$, On the set $Z'=(Z\setminus\{z\})\sqcup A$ thus obtained we define a distance by setting $|aa'|=\varepsilon$ and $|az'|=|zz'|=1/2$ for all distinct $a,a'\in A$ and any $z'\in Z\setminus\{z\}$. It is easily checked that $d_{GH}(Z',\Delta_1)=d_{GH}(Z,\Delta_1)$ and $d_{GH}(Z',\Delta_n)=d_{GH}(Z,\Delta_n)$, hence any such space $Z'$ lies between $\Delta_1$ and $\Delta_n$, that is, in the metric segment $[\Delta_1,\Delta_n]$. The space $Z'$ can have an arbitrary cardinality, so $[\Delta_1,\Delta_n]$ is a proper class. Remark 5. Borisova [12] showed that if a metric segment in $\operatorname{\mathcal{G\!H}}$ contains at least one metric space lying at distance zero from one of its endpoints, then this segment is a proper class. Let $X\in\mathcal B$ and $C=\{X_i\}_{i\in I}$ be a covering of $X$ by nonempty subset. We say that $\{X_i\}_{i\in I}$ is a covering by sets of smaller diameter if $\operatorname{diam} C<\operatorname{diam} X$. Lemma 4. Let $X\in\mathcal B$ and let $C_X=\{X_i\}_{i\in I}$ be a covering of $X$ by nonempty subsets of smaller diameter. Set $\delta_X=\operatorname{diam} X-\operatorname{diam} C_X > 0$. Then any $Y\in\mathcal B$ such that $d_{GH}(X,Y)<\varepsilon=\delta_X/5$ has a similar representation, that is, there exists a covering $C_Y=\{Y_i\}_{i\in I}$ of $Y$ by nonempty subsets of smaller diameter such that $\operatorname{diam} Y-\operatorname{diam} C_Y>\varepsilon$. Proof. We have $d_{GH}(X,Y)\,{<}\,\varepsilon$, hence there exists $R\,{\in}\,\mathcal R(X,Y)$ such that ${\operatorname{dis} R\,{<}\,2\varepsilon}$. For $i\in I$ we set $Y_i=R(X_i)$. Since $R$ is a correspondence, we have $Y_i\ne\varnothing$ for $i\in I$ and $C_Y:=\{Y_i\}_{i\in I}$ is a covering of $Y$ by nonempty sets. Since $\operatorname{dis} R<2\varepsilon$, $\operatorname{diam} Y_i\leqslant\operatorname{diam} X_i+\operatorname{dis} R$, and since $\operatorname{diam} X\leqslant\operatorname{diam} Y+\operatorname{dis} R$, we have
$$
\begin{equation*}
\begin{aligned} \, \operatorname{diam} C_Y &\leqslant\operatorname{diam} C_X+\operatorname{dis} R<\operatorname{diam} C_X+2\varepsilon=\operatorname{diam} X-\delta_X+2\varepsilon \\ &=\operatorname{diam} X-3\varepsilon\leqslant\operatorname{diam} Y+\operatorname{dis} R-3\varepsilon<\operatorname{diam} Y-\varepsilon, \end{aligned}
\end{equation*}
\notag
$$
as required. Lemma 5. Let $X\in\operatorname{\mathcal{G\!H}}$ and $C_X=\{X_i\}_{i\in I}$ be a covering of $X$ by nonempty subsets of finite diameter. Then any $Y\in\operatorname{\mathcal{G\!H}}$ lying at a finite distance from $X$ has a similar representation, that is, there exists a covering $C_Y=\{Y_i\}_{i\in I}$ of $Y$ by nonempty subsets of finite diameter such that $\operatorname{diam} C_Y\leqslant\operatorname{diam} C_X+2d_{GH}(X,Y)$. Proof. Let $d_{GH}(X,Y)<\varepsilon$. Then there exists an $R\in\mathcal R(X,Y)$ such that $\operatorname{dis} R<2\varepsilon$. For $i\in I$ set $Y_i=R(X_i)$. Since $R$ is a correspondence, we have $Y_i\ne\varnothing$ for $i\in I$, and $C_Y:=\{Y_i\}_{i\in I}$ is a covering of $Y$ by nonempty sets. Next, $\operatorname{dis} R<2\varepsilon$, and so $\operatorname{diam} Y_i\leqslant\operatorname{diam} X_i+\operatorname{dis} R$ and $\operatorname{diam} C_Y\leqslant\operatorname{diam} C_X+2\varepsilon$, from which the required result follows. The following standard construction is instrumental in going over from a covering to a partition whose cardinality and diameter are the same or smaller. Construction 1. Let $X\in\operatorname{\mathcal{G\!H}}$ and let $C=\{X_i\}_{i\in I}$ be a covering of $X$ such that $\operatorname{diam} C<\operatorname{diam} X$. By Zermelo’s theorem, the index set $I$ can be well ordered. We also set
$$
\begin{equation*}
X'_i=X_i\setminus \bigcup_{j\colon j<i}X_j, \qquad i\in I.
\end{equation*}
\notag
$$
Throwing away the empty sets $X'_i$ we obtain a partition $D$ of $X$ into $m\leqslant\#I$ nonempty subsets; moreover, $\operatorname{diam} D\leqslant\operatorname{diam} C<\operatorname{diam} X$. Lemma 6. Let $X,Y\in\mathcal B$ be such that 1) $d:=\operatorname{diam} Y-\operatorname{diam} X>0$; 2) there exists a partition $D_X=\{X_i\}_{i\in I}$ of $X$ such that $\alpha(D_X)>0$; 3) there exists a covering $C_Y=\{Y_j\}_{j\in J}$ of $Y$ by sets of smaller diameter such that $\delta_Y:=\operatorname{diam} Y-\operatorname{diam} C_Y>0$; 4) $\#J\leqslant\#I$. Then $\operatorname{diam} Y-2d_{GH}(X,Y)\geqslant\min\{d,\alpha(D_X),\delta_Y\}>0$. Proof. Using Construction 1 above we transform the covering $C_Y=\{Y_j\}$ of the space $Y$ into a partition $D_Y=\{Y'_k\}_{k\in K}$ such that $\#K\leqslant\#J\leqslant\#I$ and $\operatorname{diam} D_Y\leqslant\operatorname{diam} C_Y$. Let $\sigma\colon K\to I$ be an arbitrary injection. Consider the correspondence
$$
\begin{equation*}
R=\biggl(\bigcup_{k\in K\setminus\{k_0\}}(X_{\sigma(k)}\times Y'_k)\biggr) \cup\biggl(\bigcup_{i\in I\setminus\sigma(K)}(X_i\times Y'_{k_0})\biggr),
\end{equation*}
\notag
$$
where $k_0\in K$ is an arbitrary fixed element. We estimate the distortion of the correspondence $R$. In $R$, to elements of distinct $Y'_k$ there always correspond elements of distinct $X_i$, so
$$
\begin{equation*}
\begin{aligned} \, 2d_{GH}(X,Y) &\leqslant\operatorname{dis} R\leqslant\max\bigl\{\operatorname{diam} X,\,\operatorname{diam} Y-\alpha(D_X),\,\operatorname{diam} D_Y\bigr\} \\ &\leqslant\max\bigl\{\operatorname{diam} Y-d,\,\operatorname{diam} Y-\alpha(D_X),\,\operatorname{diam} Y-\delta_Y\bigr\} \\ &\leqslant\operatorname{diam} Y-\min\{d,\alpha(D),\delta_Y\}, \end{aligned}
\end{equation*}
\notag
$$
as required. Definition 3. Let $X,Y\in\mathcal B$ be such that $d_{GH}(X,Y)>0$. We say that $Y$ is hyperextreme with respect to $X$ if
$$
\begin{equation*}
2d_{GH}(X,Y)=\operatorname{diam} Y\geqslant\operatorname{diam} X.
\end{equation*}
\notag
$$
We say that $Y$ is subextreme with respect to $X$ if
$$
\begin{equation*}
2d_{GH}(X,Y)=\operatorname{diam} Y-\operatorname{diam} X.
\end{equation*}
\notag
$$
Remark 6. If $Y$ is hyperextreme with respect to $X$, then by Proposition 1 the distance $d_{GH}(X,Y)$ between $X$ and $Y$ assumes its greatest value among the spaces with the above relation between the diameters. Conversely, if $2d_{GH}(X,Y)=\max\{\operatorname{diam} X,\operatorname{diam} Y\}>0$ and $\operatorname{diam} Y\geqslant\operatorname{diam} X$, then $Y$ is hyperextreme with respect to $X$. Remark 7. If $Y$ is subextreme with respect to $X$, then $\operatorname{diam} Y>\operatorname{diam} X$, and so by Proposition 1 the distance $d_{GH}(X,Y)$ assumes its smallest value among the spaces $X$ and $Y$ with the above relation between the diameters. Conversely, if $2d_{GH}(X,Y)=|\operatorname{diam} X -\operatorname{diam} Y|>0$, then the space with the larger diameter is subextreme with respect to that with the smaller diameter. Remark 8. Each space $Y\in\mathcal B$, $Y\ne \Delta_1$, is simultaneously hyperextreme and subextreme with respect to the one-point space $\Delta_1$. Moreover, if $Y$ is simultaneously subextreme and hyperextreme with respect to some $X$, then $2d_{GH}(X,Y)=\operatorname{diam} Y=\operatorname{diam} Y-\operatorname{diam} X$, so that $\operatorname{diam} X=0$, and therefore $X=\Delta_1$. Definition 4. If
$$
\begin{equation*}
2d_{GH}(X,Y)=\operatorname{diam} Y=\operatorname{diam} X>0,
\end{equation*}
\notag
$$
then $Y$ is hyperextreme with respect to $X$ and $X$ is hyperextreme with respect to $Y$. In this case we say that the spaces $X$ and $Y$ are mutually hyperextreme and the metric segment $[X,Y]\subset\mathcal B$ is extreme. Remark 9. Proposition 1 implies that spaces $X$ and $Y$ are mutually hyperextreme if and only if they are ‘diametrically opposite’ points of the sphere of radius $\frac12\operatorname{diam} X$ with centre at the one-point space $\Delta_1$, that is, these are points on this sphere which are most distant from each other. Now, if $Y$ is subextreme with respect to $X$, then $Y$ is a point on the sphere of radius $\frac12\operatorname{diam} Y$ with centre at $\Delta_1$ which is nearest to $X$, that is, $X$ and $Y$ ‘lie on the same radial ray’. Proposition 2. Let $X,Y\!\mkern-2mu\in\!\mathcal B$ and let the metric segment $[X,Y]$ be extreme. Assume that $[X,Y]$ can be extended beyond $Y$ to some $Z$. Then $Z\in\mathcal B$, $\operatorname{diam} Z>\operatorname{diam} Y$, and the space $Z$ is subextreme with respect to $Y$. Proof. Indeed, by assumption $Y$ lies between $X$ and $Z$, hence $d_{GH}(X,Z)<\infty$ by definition, which gives $Z\in\mathcal B$ by Proposition 1. Moreover, $d_{GH}(X,Z)=d_{GH}(X,Y)+d_{GH}(Y,Z)$ and, by the definition of an extension, $d_{GH}(Y,Z)>0$. Hence $d_{GH}(X,Z)> d_{GH}(X,Y)$. On the other hand, if $\operatorname{diam} Z\leqslant\operatorname{diam} Y$, then by Proposition 1
$$
\begin{equation*}
2d_{GH}(X,Z)\leqslant\max\{\operatorname{diam} X,\operatorname{diam} Z\}=\operatorname{diam} X,
\end{equation*}
\notag
$$
and, moreover, $\operatorname{diam} X=2d_{GH}(X,Y)$ because the segment $[X,Y]$ is extreme. Hence $d_{GH}(X,Y)=d_{GH}(X,Z)$. This contradiction shows that $\operatorname{diam} Z>\operatorname{diam} Y$.
Further, by assumption $Y$ lies between $X$ and $Z$, and thus, since the segment $[X,Y]$ is extreme, from Proposition 1 we obtain
$$
\begin{equation*}
\begin{aligned} \, \max\bigl\{\operatorname{diam} X,\operatorname{diam} Z\bigr\} &\geqslant2d_{GH}(X,Z)=2d_{GH}(X,Y)+2d_{GH}(Y,Z) \\ &=\operatorname{diam} X+2d_{GH}(Y,Z)\geqslant\operatorname{diam} X+|\operatorname{diam} Y-\operatorname{diam} Z|. \end{aligned}
\end{equation*}
\notag
$$
However, $\operatorname{diam} Z\geqslant\operatorname{diam} Y=\operatorname{diam} X$, hence here the left- and right-hand sides are equal to $\operatorname{diam} Z$, which gives $2d_{GH}(Y,Z)=\operatorname{diam} Z-\operatorname{diam} Y>0$, proving Proposition 2. Lemma 7. Let $Y,Z\in\mathcal B$ and let $Z$ be subextreme with respect to $Y$. Fix an arbitrary $\varepsilon$ on the interval $(0,\operatorname{diam} Z-\operatorname{diam} Y)$ and consider a linear $\varepsilon$-shortest curve $R_t$ connecting $Y$ and $Z$. Then
$$
\begin{equation*}
\operatorname{diam} R_t\geqslant(1-t)\operatorname{diam} Y+t\operatorname{diam} Z-4\varepsilon.
\end{equation*}
\notag
$$
Proof. Let $R\in\mathcal R(Y,Z)$ be an arbitrary correspondence satisfying $\operatorname{dis} R\leqslant2d_{GH}(Y,Z)+2\varepsilon$. If $z,z'\in Z$ are chosen so that $|zz'|\geqslant\operatorname{diam} Z-\varepsilon$, then $|zz'|>\operatorname{diam} Y$. Hence for each $y\in R^{-1}(z)$ and $y'\in R^{-1}(z')$,
$$
\begin{equation*}
\bigl||zz'|-|yy'|\bigr|\leqslant\operatorname{dis} R\leqslant2d_{GH}(Y,Z)+2\varepsilon=\operatorname{diam} Z-\operatorname{diam} Y+2\varepsilon,
\end{equation*}
\notag
$$
where the last equality holds because $Z$ is subextreme with respect to $Y$. On the other hand, $\bigl||zz'|-|yy'|\bigr|=|zz'|-|yy'|\geqslant\operatorname{diam} Z-\varepsilon-|yy'|$ by the choice of $z$, $z'$ and $\varepsilon$, hence
$$
\begin{equation*}
\operatorname{diam} Z-\operatorname{diam} Y+2\varepsilon\geqslant\operatorname{diam} Z-\varepsilon-|yy'|,
\end{equation*}
\notag
$$
which gives $\operatorname{diam} Y-|yy'|\leqslant3\varepsilon$. As a result,
$$
\begin{equation*}
\begin{aligned} \, \operatorname{diam} R_t &\geqslant\bigl|(y,z),(y',z')\bigr|_t =(1-t)|yy'|+t|zz'| \\ &\geqslant(1-t)(\operatorname{diam} Y-3\varepsilon)+t(\operatorname{diam} Z-\varepsilon) \geqslant(1-t)\operatorname{diam} Y+t\operatorname{diam} Z-4\varepsilon, \end{aligned}
\end{equation*}
\notag
$$
as required. Theorem 5. Let $X,Y\in\mathcal B$, let the metric segment $[X,Y]$ be extreme, and let $m$ and $n$ be cardinal numbers such that $1<n\leqslant\#X$ and $1<m\leqslant\#Y$. Assume that the following conditions are satisfied: 1) there exists a partition $D_X\in\mathcal D_n(X)$ such that $\alpha(D_X)>0$; 2) there exists a covering $C_Y\in\mathcal C_m(Y)$ such that $\operatorname{diam} C_Y<\operatorname{diam} Y$; 3) $m\leqslant n$. Then the metric segment $[X,Y]$ cannot be extended beyond $Y$. Proof. Suppose to the contrary that there exists a metric space $Z$ such that $Y$ lies between $X$ and $Z$. By Proposition 2, in this case $Z\in\mathcal B$, and moreover, $Z$ is subextreme with respect to $Y$. The following result is clear.
Lemma 8. For any $\delta>0$ and $d>0$ there exists $\varepsilon_0>0$ such that, for all $\varepsilon\in[0,\varepsilon_0)$,
$$
\begin{equation}
\frac{8\varepsilon}{d}<\frac{\delta}{10(d+\varepsilon)}.
\end{equation}
\tag{1}
$$
In the notation of Lemma 8, we can choose a corresponding $\varepsilon_0$ for $\delta=\operatorname{diam} Y- \operatorname{diam} C_Y$ and $d=2d_{GH}(Y,Z)=\operatorname{diam} Z-\operatorname{diam} Y>0$. We fix an arbitrary $\varepsilon$ satisfying
$$
\begin{equation*}
0<\varepsilon<\min\biggl\{\varepsilon_0,\frac d8,\frac\delta{20},\frac{\alpha(D_X)}4\biggr\}.
\end{equation*}
\notag
$$
Inequality (1) is satisfied by Lemma 8. We have $\varepsilon<d/8$, and hence the left-hand side of (1) is smaller than $1$. Hence there exists an $s\in(0,1)$ such that
$$
\begin{equation*}
\frac{8\varepsilon}{d}<s<\frac{\delta}{10(d+\varepsilon)}.
\end{equation*}
\notag
$$
Consider an arbitrary $R\in\mathcal R(Y,Z)$ such that $\operatorname{dis} R\leqslant2d + 2\varepsilon$, and consider a corresponding linear $\varepsilon$-shortest curve $R_t$, $t\in[0,1]$, connecting $Y$ and $Z$, where $R_0=Y$ and $R_1=Z$. For $s$ as above we consider $R_s$ and proceeding as in the proof of Theorem 4, we obtain $2d_{GH}(Y,R_s)\leqslant s\operatorname{dis} R$, which implies that
$$
\begin{equation*}
d_{GH}(Y,R_s)\leqslant s(2d+2\varepsilon)<\frac{\delta}{10(d+\varepsilon)}(2d+2\varepsilon)=\frac\delta5.
\end{equation*}
\notag
$$
By Lemma 4, there exists a covering $C_R$ of the space $R_s$ by nonempty subsets of smaller diameter such that $\#C_R=\#C_Y$ and $\operatorname{diam} R_s-\operatorname{diam} C_R>\delta/5$. We have $\operatorname{diam} Y<\operatorname{diam} Z$, $8\varepsilon<sd$, and therefore by Lemma 7,
$$
\begin{equation*}
\operatorname{diam} R_s\geqslant\operatorname{diam} Y+s(\operatorname{diam} Z-\operatorname{diam} Y)-4\varepsilon=\operatorname{diam} Y+sd-4\varepsilon>\operatorname{diam} Y+4\varepsilon.
\end{equation*}
\notag
$$
As a result, since $\operatorname{diam} X=\operatorname{diam} Y$, we find that $\operatorname{diam} R_s-\operatorname{diam} X>4\varepsilon>0$. Hence for $X$ and $R_s$ all the hypotheses of Lemma 6 are satisfied, and therefore
$$
\begin{equation*}
2d_{GH}(X,R_s) \leqslant\operatorname{diam} R_s-\min\bigl\{\operatorname{diam} R_s-\operatorname{diam} X,\,\alpha(D_X),\,\operatorname{diam} R_s-\operatorname{diam} C_R\bigr\}.
\end{equation*}
\notag
$$
However, each of the expressions in curly brackets is greater than $4\varepsilon$, hence $2d_{GH}(X,R_s)<\operatorname{diam} R_s-4\varepsilon$. On the other hand $2d_{GH}(Y,R_s)\geqslant|\operatorname{diam} Y-\operatorname{diam} R_s|=\operatorname{diam} R_s-\operatorname{diam} Y$, and now from Corollary 3 and since $2d_{GH}(X,Y)=\operatorname{diam} Y$, we conclude that
$$
\begin{equation*}
\begin{aligned} \, 2d_{GH}(X,R_s) &\geqslant2d_{GH}(X,Y)+2d_{GH}(Y,R_s)-4\varepsilon \\ &\geqslant2d_{GH}(X,Y)+\operatorname{diam} R_s-\operatorname{diam} Y-4\varepsilon=\operatorname{diam} R_s-4\varepsilon. \end{aligned}
\end{equation*}
\notag
$$
This contradiction proves Theorem 5. Remark 10. The reader might be tempted to think that the hypotheses of Theorem 5 can be relaxed by replacing the condition that the spaces $X$ and $Y$ be mutually hyperextreme by the condition that $Y$ be hyperextreme with respect to $X$. However if $Y$ is hyperextreme with respect to $X$ and if conditions 1)–3) in Theorem 5 are satisfied, then the spaces $X$ and $Y$ are mutually hyperextreme. In fact, if $\operatorname{diam} Y>\operatorname{diam} X$, then from Lemma 6 we obtain the inequality $2d_{GH}(X,Y)<\operatorname{diam} Y$, which contradicts the hyperextremality of $Y$ with respect to $X$. Hence only the case $2d_{GH}(X,Y)=\operatorname{diam} Y=\operatorname{diam} X$ is possible, but in this case $X$ and $Y$ are mutually hyperextreme. Corollary 4. Let $X,Y\in\mathcal M$, let $X$ and $Y$ be mutually hyperextreme, and let conditions 1)–3) in Theorem 5 hold. Then no shortest curve in $\mathcal M$ connecting $X$ and $Y$ can be extended beyond $Y$.
§ 4. Some examples Recall that $\Delta_1$ denotes a one-point metric space and $\lambda\Delta_n$ denotes a metric space of cardinality $n$ all nonzero distances in which are equal to $\lambda$. Such spaces are called single-distance spaces or, briefly, simplexes. Some formulae for distances from simplexes to bounded metric spaces were obtained in the paper [9], which we have already mentioned. We use these results to construct examples of extendable shortest curves and metric segments. 4.1. Extendability beyond a simplex Let $X$ be a metric space and $m$ be a cardinal number not exceeding $\#X$. Recall that above we have already defined some characteristics of possible partitions of the space $ X$ into $m$ subsets. In [9] the following formula for the distance from $X$ to a simplex was obtained. Theorem 6. If $X\in\mathcal B$ and $1<m\leqslant\#X$ is a cardinal number, then
$$
\begin{equation*}
2d_{GH}(\lambda\Delta_m,X)=\inf_{D\in\mathcal D_m}\max\bigl\{\operatorname{diam} D,\,\lambda-\alpha(D),\,\operatorname{diam} X-\lambda\bigr\}.
\end{equation*}
\notag
$$
We require the following particular case of this formula. Corollary 5. If $X\in\mathcal B$, $1<m\leqslant\#X$ is a cardinal number, and $\lambda\geqslant\operatorname{diam} X+\alpha_m(X)$, then $2d_{GH}(\lambda\Delta_m,X)=\lambda-\alpha_m(X)$. Proof. Indeed, if $\lambda \geqslant \operatorname{diam} X + \alpha_m(X)$, then $\lambda-\alpha(D)\geqslant\lambda-\alpha_m(X)\geqslant\operatorname{diam} X\geqslant\operatorname{diam} D$ and a fortiori $\lambda-\alpha (D)\geqslant\operatorname{diam} X-\lambda$. Hence for such $\lambda$ the maximum in the formula from Theorem 6 is equal to $\lambda-\alpha (D)$, so that
$$
\begin{equation*}
2d_{GH}(\lambda\Delta_m,X)=\inf_D(\lambda-\alpha (D))=\lambda-\sup_D\alpha (D)=\lambda-\alpha _m(X),
\end{equation*}
\notag
$$
as required. Corollary 6. If $X\!\in\!\mathcal B$, $1\!<\!m\!\leqslant\!\#X$ is a cardinal number and $\lambda\!\geqslant\!\operatorname{diam} X+ \alpha _m(X)$, then the metric segment $[X,\lambda\Delta_m]$ can be extended beyond $\lambda\Delta_m$ to any simplex $\lambda'\mkern-1mu\Delta_m$, where $\lambda'>\lambda$. Proof. Indeed, $2d_{GH}(\lambda\Delta_m,\lambda'\Delta_m)=|\lambda-\lambda'|$, hence $2d_{GH}(\lambda\Delta_m,X)=\lambda-\alpha _m(X)$ for any $\lambda\geqslant\operatorname{diam} X+\alpha _m(X)$ by Corollary 5. Consequently, the simplex $\lambda\Delta_m$ lies between $X$ and $\lambda'\Delta_m$, where $\lambda'>\lambda$, as required. 4.2. Extendability beyond a subextreme space The next result formalizes Remark 9. Proposition 3. Let $X,Y\in\mathcal B$ and let $Y$ be subextreme with respect to $X$. Then $X$ lies between $\Delta_1$ and $Y$. Proof. We have
$$
\begin{equation*}
\begin{aligned} \, 2d_{GH}(\Delta_1,Y) &=\operatorname{diam} Y=\operatorname{diam} X +(\operatorname{diam} Y-\operatorname{diam} X) \\ &=2d_{GH}(\Delta_1,X)+2d_{GH}(X,Y), \end{aligned}
\end{equation*}
\notag
$$
which is the result required. Corollary 7. Let $X,Y\in\mathcal B$, let $Y$ be subextreme with respect to $X$, and let $X\ne\Delta_1$. Then the metric segment $[X,Y]$ can be extended beyond both $X$ and $Y$. Construction 2. Assume that a space $Y\in\mathcal B$ contains points $y_1,y_2\in Y$ such that $\operatorname{diam} Y=|y_1y_2|$. Given arbitrary $r_1\geqslant0$ and $r_2\geqslant0$, we construct a two-point extension $Z_{r_1, r_2}(y_1, y_2)$ of $Y$. We set $Z\,{=}\,Z_{r_1,r_2}(y_1,y_2)\,{=}\,Y\sqcup\{z_1,z_2\}$ and extend the metric from $Y$ to $Z$ as follows: $|z_1z_2|=r_1+|y_1y_2|+r_2$ and, for $y\in Y$, we put $|yz_i|=r_i+|yy_i|$, $i=1,2$. Moreover, if $r_i=0$, then we identify $z_i$ with $y_i$. It is easily checked that for any $r_1\geqslant0$ and $r_2\geqslant0$ $Z_{r_1,r_2}(y_1,y_2)$ is a metric space and
$$
\begin{equation*}
\operatorname{diam} Z_{r_1, r_2}(y_1,y_2)=\operatorname{diam} Y+r_1+r_2=|z_1z_2|.
\end{equation*}
\notag
$$
The spaces
$$
\begin{equation*}
Z_{r_1}(y_1):=Z_{r_1,0}(y_1,y_2)\quad\text{and} \quad Z_{r_2}(y_2):=Z_{0,r_2}(y_1, y_2)
\end{equation*}
\notag
$$
will be referred to as one-point extensions of $Y$. It is clear that
$$
\begin{equation*}
Z_{0,0}(y_1, y_2)=Z_{0}(y_1)=Z_{0}(y_2)=Y.
\end{equation*}
\notag
$$
Lemma 9. Assume that a space $Y\in\mathcal B$ contains points $y_1,y_2\in Y$ such that $\operatorname{diam} Y=|y_1y_2|$, and let $Z_{r_1,r_2}(y_1,y_2)$ be the two-point extension of $Y$ defined in Construction 2. Then on the curve $\gamma(t)=Z_{r_1t,r_2t}(y_1,y_2)$, $t\in[0,1]$,
$$
\begin{equation*}
2d_{GH}(\gamma(t_1),\gamma(t_2))=|t_1-t_2|(r_1+r_2)
\end{equation*}
\notag
$$
for all $t_1,t_2\in[0,1]$, so that $\gamma$ is a shortest curve connecting $Y$ and $Z_{r_1,r_2}(y_1,y_2)$. In particular, putting $r_2=0$ or $r_1=0$ produces a shortest curve connecting $Y$ with the corresponding one-point extension $Z_{r_1}(y_1)$ or $Z_{r_2}(y_2)$. Proof. Let $R\in\mathcal R(\gamma(t_1),\gamma(t_2))$ be a correspondence that acts identically on the set $Y\cup\{z_1,z_2\}$. Then we have
$$
\begin{equation*}
\operatorname{dis} R=\max\bigl\{|t_1-t_2|r_1,\,|t_1-t_2|r_2,\,|t_1-t_2|(r_1+r_2)\bigr\}=|t_1-t_2|(r_1+r_2),
\end{equation*}
\notag
$$
and so $2d_{GH}(\gamma(t_1),\gamma(t_2))\leqslant|t_1-t_2|(r_1+r_2)$. On the other hand
$$
\begin{equation*}
\begin{aligned} \, &\bigl|\operatorname{diam}\gamma(t_1)-\operatorname{diam}\gamma(t_2)\bigr| \\ &\qquad =\bigl|\operatorname{diam} Y+(r_1+r_2)t_1-\operatorname{diam} Y-(r_1+r_2)t_2\bigr|=|t_1-t_2|(r_1+r_2), \end{aligned}
\end{equation*}
\notag
$$
hence $2d_{GH}(\gamma(t_1),\gamma(t_2))\geqslant|t_1-t_2|(r_1+r_2)$ by Proposition 1. Consequently,
$$
\begin{equation*}
2d_{GH}(\gamma(t_1),\gamma(t_2))=|t_1-t_2|(r_1+r_2),
\end{equation*}
\notag
$$
from which the required result follows. Proposition 4. Let $X,Y\in\mathcal B$ and let $Y$ be subextreme with respect to $X$. Assume that there exist $y_1,y_2\in Y$ such that $\operatorname{diam} Y=|y_1y_2|$. Then the metric segment $[X,Y]$ can be extended beyond the space $Y$ to any two-point extension ${Z:=Z_{r_1,r_2}(y_1, y_2)}$ of $Y$. Proof. By Lemma 9, $2d_{GH}(Y,Z)=r_1+r_2$. Now we estimate $d_{GH}(X,Z)$ by using Proposition 1 and the triangle inequality. We have
$$
\begin{equation*}
\begin{aligned} \, \operatorname{diam} Z-\operatorname{diam} X &\leqslant 2d_{GH}(X,Z)\leqslant 2d_{GH}(X,Y)+2d_{GH}(Y,Z) \\ &=\operatorname{diam} Y-\operatorname{diam} X+r_1+r_2=\operatorname{diam} Z-\operatorname{diam} X, \end{aligned}
\end{equation*}
\notag
$$
hence
$$
\begin{equation*}
\begin{aligned} \, 2d_{GH}(X,Z) &=\operatorname{diam} Z-\operatorname{diam} X=(\operatorname{diam} Z-\operatorname{diam} Y)+(\operatorname{diam} Y-\operatorname{diam} X) \\ &=2d_{GH}(Y,Z)+2d_{GH}(X,Y), \end{aligned}
\end{equation*}
\notag
$$
as required. Remark 11. In Proposition 4 the metric segment $[X,Y]$ can be extended in different ways beyond $Y$: to $Z_r(y_0)$, to $Z_r(y_1)$, or to $Z_{r_1, r_2}(y_1,y_2)$. Therefore, if, for instance, $X,Y\in\mathcal M$, where any pair of points can be connected by a shortest curve, then any shortest curve connecting $X$ and $Y$ can ramify at $Y$, like in the case of a cone with total angle $>2\pi$ at the apex. In particular, this takes place for $X=\Delta_1$ and the standard ‘radial’ shortest curve of the form $t\mapsto tY$, $t\in[0,1]$. Remark 12. If we restrict attention to the space $\mathcal M$ of compact metric spaces, then for any $X,Y\in\mathcal M$ satisfying the assumptions of Proposition 4 and any $r>0$ each shortest curve connecting $X$ and $Y$ can be extended beyond $Y$ to any space $Z$ in the intersection of the sphere $S_1(\Delta_1)$ of radius $(1/2)\operatorname{diam} Y+r/2$ with centre $\Delta_1$ with the sphere $S_2(Y)$ of radius $r/2$ with centre $Y$. In particular, this intersection contains all one-point extensions of $Y$ with parameter $r$, and all of its two-point extensions with parameters $r_1$ and $r_2$ such that $r_1+r_2=r$. The proof of the next lemma is a slight modification of the proof of Lemma 9. Lemma 10. Let $Y\in\mathcal B$ contain points $y_1,y_2\in Y$ such that $\operatorname{diam} Y=|y_1y_2|$ and let $Z_{r_1,r_2}(y_1,y_2)$ be the two-point extension of $Y$ defined in Construction $2$. Then for any $0\leqslant s_1\leqslant r_1$ and $0\leqslant s_2\leqslant r_2$,
$$
\begin{equation*}
2d_{GH}\bigl(Z_{r_1,r_2}(y_1,y_2),Z_{s_1,s_2}(y_1,y_2)\bigr)=s_1-r_1+s_2-r_2.
\end{equation*}
\notag
$$
The next result follows from Lemma 10. Proposition 5. Let $Y$ and $Z_{r_1,r_2}(y_1,y_2)$ be as in Lemma $10$ and let $r(t)$, $s(t)$ be nonnegative monotone increasing continuous functions of $t\in I$, where $I$ is a finite or infinite interval. Then $\gamma(t)=Z_{r(t),s(t)}(y_1,y_2)$ is a shortest curve. 4.3. Examples of nonextendable segments Theorem 5 can be applied to construct examples of nonextendable metric segments and shortest curves. Example 1. Let $X=\lambda\Delta_n$ and $Y=\lambda \Delta_m$ be single-distance spaces, $1<m<n$. Then the metric segment $[X,Y]$ cannot be extended beyond $Y$. In fact, $2d_{GH}(X,Y)=\lambda=\operatorname{diam} X=\operatorname{diam} Y$. Hence the spaces $X$ and $Y$ are mutually extreme. Next, $X$ and $Y$ can be partitioned into $n$ and $m$ one-point subsets of zero diameter, respectively. Now the assumptions of Theorem 5 are satisfied for $m<n$. We need another simple corollary to Theorem 6 (see [9]). Corollary 8. Let $X$ be a bounded metric space, let $1\!<\!m\!\leqslant\!\#X$, and let $\alpha_m(X)\!=\!0$. Then
$$
\begin{equation*}
2d_{GH}(\lambda\Delta_m,X)=\max\bigl\{d_m(X),\lambda,\operatorname{diam} X-\lambda\bigr\}.
\end{equation*}
\notag
$$
Example 2. Now let $X=\Delta_2$ be the space consisting of two points lying at distance $1$ from each other and let $Y=[0,1]$ be a closed interval of length $1$. Then $\alpha _2(Y)=0$, $d_2(Y)=1/2$, and therefore $2d_{GH}(\Delta_2,Y)=1$ by Corollary 8. As we saw already in Corollary 6, the metric segment $[X,Y]$ can be extended beyond the simplex $X$. On the other hand, the spaces $X$ and $Y$ are mutually extreme. We represent the simplex $X$ as the union of the two points in it, and we represent $Y$ as the union of the two intervals $Y_1=[0,1/2]$ and $Y_2=[1/2,1]$. Now it follows from Theorem 5 that $[X,Y]$ cannot be extended beyond $Y$. Example 3. Example 2 can be generalized as follows. Let $X=\Delta_k$ be a simplex consisting of $k$ elements, $1<k<\infty$, and let $Y$ be a closed convex body of diameter $1$ with smooth boundary in $(k-1)$-dimensional Euclidean space. Then $\alpha _k(Y)=0$ and the metric segment $[X,Y]$ can be extended beyond the simplex $X$. By Hadwiger’s theorem (see [13]) the space $Y$ can be covered by $k$ subsets of diameter $<1$. Hence $d_k(Y)<1$, and so $2d_{GH}(\Delta_k,Y)=1$ by Corollary 8. Therefore, the spaces $X$ and $Y$ are mutually extreme. We represent the simplex $X$ as the union of its points and cover $Y$ by $k$ subsets of diameter $<1$ as above. Now Theorem 5 applies, which shows that $[X,Y]$ cannot be extended beyond $Y$. 4.4. Two-side infinite nonextendability In this section we show that no metric segment in the space $\mathcal B$ of bounded metric spaces can be extended indefinitely in both sides. We start with the following lemma. Lemma 11. No metric segment $[X_1,X_2]\subset\operatorname{\mathcal{G\!H}}$ of length $s$ lies in a ball of radius $s$ with centre at the one-point space $\Delta_1$. Proof. Proposition 1 shows that $2s\leqslant\max\{\operatorname{diam} X_1,\operatorname{diam} X_2\}$. Next, we have $2d_{GH}(\Delta_1,X_i)=\operatorname{diam} X_i$, and so the distance of $\Delta_1$ to one of the $X_i$ is at least $s$, as required. Proposition 6. Let $Z\in\mathcal B$ be an interior point of an $\varepsilon$-shortest curve $\gamma$. Then at least one endpoint of $\gamma$ lies in the ball of radius $R=\operatorname{diam} Z+\varepsilon$ with centre at the one-point space $\Delta_1$. Proof. Let $\gamma$ be an $\varepsilon$-shortest curve connecting points $X_1$ and $X_2$ and let these points lie outside the ball of radius $R$ with centre $\Delta_1$. Then the segment of the curve $\gamma$ between $Z$ and $X_i$, $i=1,2$, contains a point $Y_i$ lying on the sphere $S$ of some radius $R'>R$ with centre $\Delta_1$. Therefore, $\operatorname{diam} Y_i=2R'$, $i=1,2$, and $2d_{GH}(Y_i,Z)\geqslant\operatorname{diam} Y_i-\operatorname{diam} Z=2R'-\operatorname{diam} Z$, $i=1,2$. Further, the segment of $\gamma$ between $Y_1$ and $Y_2$ is also an $\varepsilon$-shortest curve, hence
$$
\begin{equation*}
d_{GH}(Y_1,Y_2)\geqslant d_{GH}(Y_1,Z)+d_{GH}(Z,Y_2)-\varepsilon\geqslant2R'-\operatorname{diam} Z-\varepsilon
\end{equation*}
\notag
$$
by Lemma 1. On the other hand $d_{GH}(Y_1,Y_2)\leqslant\frac12\max\{\operatorname{diam} Y_1,\operatorname{diam} Y_2\}=R'$, so that $R<R'\leqslant\operatorname{diam} Z+\varepsilon$, which is a contradiction. Corollary 9. No metric segment $[X_1,X_2]\subset\mathcal B$ can be extended indefinitely beyond both endpoints. Proof. Suppose to the contrary that, for an arbitrary $\varepsilon > 0$ and each $i=1,2$, there exists an extension $Y_i$ of some metric segment $[X_1,X_2]$ beyond the endpoint $X_i$ such that $d_{GH}(X_i,Y_i)>\max\{\operatorname{diam} X_1,\operatorname{diam} X_2\}+\varepsilon$. By the definition of an extension, $Y_i\in\mathcal B$, $i=1,2$. By Corollary 2 there exist $(\varepsilon/3)$-shortest curves between $Y_1$ and $X_1$, between $X_1$ and $X_2$, and between $X_2$ and $Y_2$, respectively. By Lemma 2, the union of these three curves is an $\varepsilon$-shortest curve between $Y_1$ and $Y_2$ such that $X_1$ and $X_2$ lie in the interior of this curve. By Proposition 6, one of the endpoints of this curve (that is, one of the $Y_i$, say $Y_1$) is contained in the ball of radius $\max\{\operatorname{diam} X_1,\operatorname{diam} X_2\}+\varepsilon$ with centre $\Delta_1$, that is, $\operatorname{diam} Y_1\leqslant2\max\{\operatorname{diam} X_1,\operatorname{diam} X_2\}+2\varepsilon$. By Proposition 1,
$$
\begin{equation*}
d_{GH}(Y_1,X_1)\leqslant\frac12\max\{\operatorname{diam} Y_1,\operatorname{diam} X_1\}\leqslant\max\{\operatorname{diam} X_1,\operatorname{diam} X_2\}+\varepsilon,
\end{equation*}
\notag
$$
which is a contradiction.
|
|
|
Bibliography
|
|
|
1. |
F. Hausdorff, Grundzüge der Mengenlehre, Veit & Comp., Leipzig, 1914, viii+476 pp. |
2. |
D. A. Edwards, “The structure of superspace”, Studies in topology (Univ. North Carolina, Charlotte, NC 1974), Academic Press, New York, 1975, 121–133 |
3. |
M. Gromov, “Groups of polynomial growth and expanding maps”, Inst. Hautes Études Sci. Publ. Math., 53 (1981), 53–78 |
4. |
A. O. Ivanov, N. K. Nikolaeva and A. A. Tuzhilin, “The Gromov-Hausdorff metric on the space of compact metric spaces is strictly intrinsic”, Mat. Zametki, 100:6 (2016), 947–950 ; English transl. in Math. Notes, 100:6 (2016), 883–885 ; arXiv: 1504.03830 |
5. |
A. O. Ivanov and A. A. Tuzhilin, “Isometry group of Gromov-Hausdorff space”, Mat. Vesnik, 71:1–2 (2019), 123–154 |
6. |
D. Burago, Yu. Burago and S. Ivanov, A course in metric geometry, Grad. Stud. Math., 33, Amer. Math. Soc., Providence, RI, 2001, xiv+415 pp. |
7. |
A. O. Ivanov and A. A. Tuzhilin, Geometry of the Hausdorff and Gromov-Hausdorff distances:
The case of compact spaces, Board of Trustees of the Faculty of Mechanics and Mathematics of Moscow State University, Moscow, 2017, 111 pp. (Russian) |
8. |
D. A. Herron, “Gromov-Hausdorff distance for pointed metric spaces”, J. Anal., 24:1 (2016), 1–38 |
9. |
D. S. Grigor'ev, A. O. Ivanov and A. A. Tuzhilin, Gromov-Hausdorff distance to simplexes, Chebyshevskii Sb., 20, no. 2, 2019 ; English transl., arXiv: 1906.09644 |
10. |
A. Ivanov, S. Iliadis and A. Tuzhilin, Realizations of Gromov-Hausdorff distance, arXiv: 1603.08850 |
11. |
S. Chowdhury and F. Memoli, Constructing geodesics on the space of compact metric spaces, arXiv: 1603.02385v3 |
12. |
O. Borisova, Metric segments in Gromov-Hausdorff class, arXiv: 2009.13273 |
13. |
V. G. Boltjansky and I. Ts. Gohberg, Results and problems in combinatorial geometry, Nauka, Moscow, 1965, 108 pp. ; English transl., Cambridge Univ. Press, Cambridge, 1985, vii+108 pp. |
Citation:
S. I. Borzov, A. O. Ivanov, A. A. Tuzhilin, “Geometry of the Gromov-Hausdorff distance on the class of all metric spaces”, Mat. Sb., 213:5 (2022), 68–87; Sb. Math., 213:5 (2022), 641–658
Linking options:
https://www.mathnet.ru/eng/sm9651https://doi.org/10.1070/SM9651 https://www.mathnet.ru/eng/sm/v213/i5/p68
|
Statistics & downloads: |
Abstract page: | 322 | Russian version PDF: | 45 | English version PDF: | 58 | Russian version HTML: | 112 | English version HTML: | 72 | References: | 27 | First page: | 12 |
|