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

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-Gö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.

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.

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

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

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

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

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

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.

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.

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

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

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

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

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.

§ 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 $$

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

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

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 $$

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

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.

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.

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.

Citation in format AMSBIB

\Bibitem{BorIvaTuz22}

\by S.~I.~Borzov, A.~O.~Ivanov, A.~A.~Tuzhilin

\paper Geometry of the Gromov-Hausdorff distance on the class of all metric spaces

\jour Mat. Sb.

\yr 2022

\vol 213

\issue 5

\pages 68--87

\mathnet{http://mi.mathnet.ru/sm9651}

\crossref{https://doi.org/10.4213/sm9651}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4461447}

\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2022SbMat.213.....B}

\transl

\jour Sb. Math.

\yr 2022

\vol 213

\issue 5

\pages 641--658

\crossref{https://doi.org/10.1070/SM9651}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000992262800004}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85152473829}