# Lectures on Hausdorff and Gromov–Hausdorff Distance Geometry
The course was given at Peking University, Fall 2019

Alexey A. Tuzhilin

###### Contents

  1. 1 Elements of general topology.
    1. 1.1 Basic facts of general topology
    2. 1.2 Base and subbase
    3. 1.3 Standard constructions of topologies
    4. 1.4 Continuous mappings
    5. 1.5 Homeomorphisms, embeddings
    6. 1.6 Convergence of sequences
    7. 1.7 Closure, interior, boundary, dense subsets, separability
    8. 1.8 Separated spaces
    9. 1.9 Connected spaces
    10. 1.10 Path-connected spaces
    11. 1.11 Compact and sequentially compact spaces
    12. 1.12 Hyperspaces
  2. 2 Introduction to Metric Spaces.
    1. 2.1 Distance
    2. 2.2 Lipschitz mappings and isometries
    3. 2.3 Standard constructions of metrics
      1. 2.3.1 Elements of graph theory, and metric constructions for graphs
    4. 2.4 Convergence and completeness
    5. 2.5 Compactness and sequential compactness
      1. 2.5.1 Completeness and compactness
    6. 2.6 Canonical isometric embeddings of metric spaces
  3. 3 Curves in Metric Spaces.
    1. 3.1 Rectifiable curves
    2. 3.2 Maximal and minimal pseudometrics, quotients
    3. 3.3 Hopf–Rinow condition
    4. 3.4 Local compactness
    5. 3.5 Lipschitz, convergence and uniform convergence
    6. 3.6 Arc-length and uniform curves
    7. 3.7 Arzela-Ascoli Theorem
    8. 3.8 Existence of shortest curves
    9. 3.9 Shortest curves and midpoints
  4. 4 Extreme graphs and networks.
    1. 4.1 Necessary information from graph theory
      1. 4.1.1 Some operations on graphs
    2. 4.2 Graphs and optimization problems
      1. 4.2.1 Minimum spanning tree problem
      2. 4.2.2 Steiner minimal tree problem
      3. 4.2.3 One-dimensional minimal filling problem
    3. 4.3 $\operatorname{mst}$-spectrum of a finite metric space
    4. 4.4 Networks
      1. 4.4.1 Networks and quotients
      2. 4.4.2 Splitting and splitting off for networks
    5. 4.5 Steiner minimal trees existence
  5. 5 Hausdorff distance.
    1. 5.1 Vietoris topology and Hausdorff metric
    2. 5.2 Limits Theory
      1. 5.2.1 Limits for compact $X$
      2. 5.2.2 Limits for complete $X$
      3. 5.2.3 Inheritance of total boundedness and compactness
    3. 5.3 Inheritance of geodesic
  6. 6 Gromov–Hausdorff Distance.
    1. 6.1 Irreducible correspondences
    2. 6.2 A few more examples
    3. 6.3 $\operatorname{GH}$-convergence and $\operatorname{GH}$-limits
  7. 7 Gromov–Hausdorff space.
    1. 7.1 Existence of optimal correspondences between compact metric spaces
    2. 7.2 The Gromov–Hausdorff space is geodesic
    3. 7.3 Cover number and packing number
    4. 7.4 Totally bounded families of compact metric spaces
    5. 7.5 Some other properties of Gromov–Hausdorff space
      1. 7.5.1 Completeness of Gromov–Hausdorff space
      2. 7.5.2 Separability of Gromov–Hausdorff space
    6. 7.6 Calculating $\operatorname{mst}$-spectrum by means of Gromov–Hausdorff distances
    7. 7.7 Steiner problem in Gromov–Hausdorff space
  8. 8 Calculating GH-distances to simplexes and some applications.
    1. 8.1 Gromov–Hausdorff distance to simplexes with more points
    2. 8.2 Gromov–Hausdorff distance to simplexes with at most the same number of points
    3. 8.3 Generalized Borsuk problem
    4. 8.4 Calculating clique covering and chromatic numbers of a graph

##  Chapter 1 Elements of general topology.

  * Schedule.

Definition of topology and topological space, induced topology, subspace of
topological space, discrete and anti-discrete topologies, metric spaces and
metric topology, standard topology on Euclidean space, base of topology, cover
of set and subset, Zariski topology, Sorgenfrey topology, subbase of topology,
disjoint union of topological spaces, Cartesian product of topological spaces,
Tychonoff or product topology, quotient topology and quotient space, Vietoris
topology, continuous mapping, homeomorphism, embedding, convergence of
sequences, closure, interior, boundary, dense subsets, separability, separated
or Hausdorff topological space, connected and disconnected topological spaces,
connected components, path-connected topological spaces, open cover, subcover,
compact and sequentially compact topological spaces, bounded metric spaces,
hyperspaces.

In this chapter we present an introduction to general topology.

###  1.1 Basic facts of general topology

For a set $X$, let $2^{X}$ denote the collection of all subsets of $X$. If
$\mathcal{A}\subset 2^{X}$ is a family of subsets of $X$, then
$\cup\mathcal{A}$ and $\cap\mathcal{A}$ denote the union and the intersection
of the elements from $\mathcal{A}$, respectively. If $\mathcal{A}$ is an
indexed family, i.e., $\mathcal{A}=\\{A_{i}\\}_{i\in I}$, then we use
$\cup_{i\in I}A_{i}$ and $\cap_{i\in I}A_{i}$ for the union and the
intersection. If different elements of $\mathcal{A}$ do not intersect each
other (such family $\mathcal{A}$ is called _disjoint_), then we write
$\sqcup\mathcal{A}$ instead of $\cup\mathcal{A}$, to emphasize that
$\mathcal{A}$ is disjoint; similarly, we write $\sqcup_{i\in I}A_{i}$ instead
of $\cup_{i\in I}A_{i}$ for indexed families. We can define $\sqcup_{i\in
I}A_{i}$ also in the case when some differen $A_{i}$ intersect each other, in
particular, when they coincide. In this situation we simply consider $A_{i}$
for different $i$ as nonintersecting sets. This can be done in a formal way if
we change the elements $a_{i}\in A_{i}$ to $(a_{i},i)$ and identify $A_{i}$
with the set $\bigl{\\{}(a_{i},i)\bigr{\\}}_{a_{i}\in A_{i}}$.

######  Definition 1.1.

A set $\tau=\\{U_{\alpha}\\}_{\alpha\in A}\subset 2^{X}$ is called _a topology
on $X$_ if $\tau$ satisfies the following properties:

  1. (1)

$\emptyset,\,X\in\tau$;

  2. (2)

for any $\mathcal{A}\subset\tau$ we have $\cup\mathcal{A}\in\tau$ (the union
of arbitrary collection of elements from $\tau$ belongs to $\tau$);

  3. (3)

for any finite $\mathcal{A}\subset\tau$ it holds $\cap\mathcal{A}\in\tau$ (the
intersection of arbitrary finite collection of elements from $\tau$ belongs to
$\tau$).

######  Definition 1.2.

A set $X$ with a given topology $\tau\subset 2^{X}$ is called _a topological
space_. It is also convenient to denote the topological space $X$ as the pair
$(X,\tau)$. Also, speaking about the topological space $X$, we will often
denote the topology defined on it by $\tau_{X}$, without specifically
mentioning it every time.

The elements of $X$ are usually called _points_ , and the elements of $\tau$
are called _open sets_. A set $F\subset X$ is called _closed_ if its
complement is open.

######  Problem 1.1.

Show that the family of all closed subsets of a topological space $X$ contains
$\emptyset$ and $X$, and that the intersection of any collection of closed
subsets, as well as the union of any finite collection of closed subsets are
some closed sets.

Take an arbitrary $Y\subset X$ and consider the family $\tau_{Y}:=\\{U\cap
Y:U\in\tau_{X}\\}$.

######  Problem 1.2.

Prove that $\tau_{Y}$ is a topology on $Y$.

######  Definition 1.3.

The $\tau_{Y}$ is called _the topology on $Y$ induced from $X$_. The $Y$ with
the topology $\tau_{Y}$ is usually called _a subspace_ of the topological
space $X$.

Generally speaking, there are many different topologies on each set $X$, and
the inclusion relation generates a partial order on the set of all such
topologies. The smallest topology in this order consists of two elements:
$\tau_{a}=\\{\emptyset,X\\}$. It is called _anti-discrete_. The largest
topology consists of all subsets: $\tau_{d}=2^{X}$. It is called _discrete_.
If $\mathcal{T}$ is a collection of topologies defined on the same set $X$,
then $\cap\mathcal{T}$ is a topology as well; it is smaller than each topology
$\tau\in\mathcal{T}$; for any topology $\tau^{\prime}$ on $X$ that is smaller
than all topologies from $\mathcal{T}$ it holds
$\tau^{\prime}\subset\cap\mathcal{T}$.

The most important for us example of topology will be generated by metrics.
Namely, suppose that for a set $X$ a function $\rho\colon X\times
X\to\mathbb{R}$ is given, which has the following properties:

  1. (1)

for any $x,y\in X$ it holds $\rho(x,y)\geq 0$, and $\rho(x,y)=0$ iff $x=y$
(positive definiteness);

  2. (2)

for any $x,y\in X$ we have $\rho(x,y)=\rho(y,x)$ (symmetry);

  3. (3)

for any $x,y,z\in X$ it holds $\rho(x,y)+\rho(y,z)\geq\rho(x,z)$ (triangle
inequality).

Then $\rho$ is called _a metric_ , and the set $X$ with the metric $\rho$ is
called _a metric space_. It is also convenient to denote the metric space $X$
as the pair $(X,\rho)$. Each $Y\subset X$ endowed with the restriction of
$\rho$ to $Y\times Y$ is called _a subspace of $X$_.

######  Example 1.4.

In calculus, the standard example of a metric space is the arithmetic space
$\mathbb{R}^{n}$ with the Euclidean metric defined on it: for
$x=(x_{1},\ldots,x_{n})$ and $y=(y_{1},\ldots,y_{n})$ it holds
$\rho(x,y)=\sqrt{\sum_{i=1}^{n}(x_{i}-y_{i})^{2}}$. This metric is called
_Euclidean_. We will also call _Euclidean_ the arithmetic space itself,
endowed with the Euclidean metric.

Let $X$ be a metric space with a metric $\rho$. For every $x\in X$ and $r>0$
we put

$U_{r}(x):=\bigl{\\{}y\in X:\rho(x,y)<r\bigr{\\}}$

and call _an open ball of radius $r>0$ and center $x$_. Using the metric
$\rho$, we construct the natural topology $\tau_{\rho}$, called _the metric
topology_ : we assign the subset $U\subset X$ to open sets of the metric
topology $\tau_{\rho}$ if and only if $U$ is either empty, or $U$ is a union
of open balls. Equivalent definition: $U\in\tau_{\rho}$ if and only if for any
point $x\in U$ there exists $r>0$ such that $U_{r}(x)\subset U$ (together with
each point the set $U$ contains some open ball with the center at this point).

######  Problem 1.3.

Prove that the family $\tau_{\rho}$ is a topology.

######  Remark 1.5.

Unless otherwise stated, on the real line $\mathbb{R}$ and, more generally, on
the arithmetic space $\mathbb{R}^{n}$, we consider the topologies generated by
the Euclidean metric (see. Example 1.4). This topology is called _standard_.

###  1.2 Base and subbase

The construction of metric topology described above leads to the following
important notion. Similar to linear algebra, where to describe a linear space
it is enough to choose a family of vectors that, using linear combinations,
generates the whole space, to define a topology, one can also select a
subfamily of open sets and generate the topology by means of set-theoretic
operations.

######  Definition 1.6.

A family $\beta\subset\tau$ is called _a base of the topology $\tau$_ if every
nonempty open set $U\in\tau$ is representable as a union of some elements from
$\beta$.

Thus, by the definition of metric topology, its base is the family of all open
balls.

######  Remark 1.7.

Note that a given topology can have many different bases. For example, not all
balls can be selected as the base of the metric space, but only, say, of radii
not exceeding $1$, or of only rational radii, or of only radii of the form
$1/n$, etc. On the Euclidean line, for example, only rational numbers can be
selected as centers.

We note two important properties of the topology base on the set $X$:

  1. (1)

each point $x\in X$ is contained in some element from the base (otherwise the
set $X$ cannot be obtained as the union of some elements from the base);

  2. (2)

a nonempty intersection of any two elements of the base is representable as
the union of some elements from the base (otherwise this intersection will not
belong to the topology).

It turns out that these two properties completely characterize the families
that are the bases of some topologies. Before formulating the corresponding
criterion, we introduce a definition of cover, which will be useful to us both
here and hereinafter.

######  Definition 1.8.

A family $\mathcal{A}\subset 2^{X}$ is called _a cover of the set $X$_ if
$X=\cup\mathcal{A}$. A family $\mathcal{A}\subset 2^{X}$ is called _a cover of
$Y\subset X$_ if $Y\subset\cup\mathcal{A}$.

It is clear that each base of a topological space $X$ is a cover of $X$.

######  Problem 1.4.

Prove that a family $\beta\subset 2^{X}$ is a base of some topology $\tau$ on
$X$ if and only if $\beta$ is a cover of $X$, and for any intersecting
$B_{1},B_{2}\in\beta$ their intersection $B_{1}\cap B_{2}$ is the union of
some elements from $\beta$. Moreover, each family satisfying these properties,
generates a unique topology.

Notice that a collection $\beta$ of open sets in a topological space $X$ which
satisfies the conditions of Problem 1.4 may generate a topology $\tau$
different from $\tau_{X}$. What do we need to add for to be sure that
$\tau=\tau_{X}$? The answer can be obtained from the following more general
result that is often used in proving the coincidence of topologies.

######  Problem 1.5.

Let some topologies $\tau_{1}$ and $\tau_{2}$ with bases $\beta_{1}$ and
$\beta_{2}$ be given on a set $X$. Then $\tau_{1}=\tau_{2}$ if and only if for
any $x\in X$ the following condition is fulfilled: for any
$B_{2}\in\beta_{2}$, $x\in B_{2}$, there is $B_{1}\in\beta_{1}$ for which
$x\in B_{1}\subset B_{2}$, and vice versa, for any $B_{1}\in\beta_{1}$, $x\in
B_{1}$, there exists $B_{2}\in\beta_{2}$ for which $x\in B_{2}\subset B_{1}$.
In particular, for a topological space $X$, a collection $\beta$ of open sets
satisfying the conditions of Problem 1.4 is a base of the topology $\tau_{X}$
if and only if for each open set $U\in\tau_{X}$ and any point $x\in U$ there
exists some $B\in\beta$ such that $x\in B\subset U$.

Recall that two sets are called _equivalent_ if there exists a bijection
between them. The equivalence classes of sets are called _cardinalities_ or
_cardinal numbers_. The cardinality of a set $X$ will be denoted by $\\#X$.

######  Example 1.9.

Let $X$ be an infinite set of cardinality $n$, and $m$ be an infinite cardinal
number, with $m\leq n$. Consider a family $\mathcal{F}$ of all $F\subset X$
such that $\\#F<m$, and let $\beta_{m}=\\{X\setminus F:F\in\mathcal{F}\\}$.
Then $\beta_{m}$ is a base of some topology $\tau$, which we call _the Zariski
topology of the weight $m$_.

######  Problem 1.6.

Prove that the family $\beta_{m}$ from Example 1.9 is a base of some topology.

######  Example 1.10.

As we noted above, on the Euclidean line we can take the family of all
intervals as the base of the standard topology. Another interesting example of
topology is obtained if, instead of intervals, we take all possible half-
intervals of the form $[a,b)$. The corresponding topology is called _the arrow
topology_ or _the Sorgenfrey topology_.

######  Remark 1.11.

The Sorgenfrey topology contains the standard topology of the line, since each
interval $(a,b)$ can be represented as a union of half-intervals $[a+1/n,b)$,
$n\in{\mathbb{N}}$.

######  Problem 1.7.

Show that the collection of all possible half-intervals of the form
$[a,b)\subset\mathbb{R}$ form a base of some topology that contains the
standard topology.

If, to generate a topology, we allowed also to use finite intersections, then
the generating family can, generally speaking, be reduced.

######  Definition 1.12.

A family $\sigma\subset\tau$ is called _a subbase of the topology $\tau$_ if
the set of all finite intersections of elements from $\sigma$ forms a base of
the topology $\tau$.

It is clear that, like the base, each subbase of a topological space $X$ is a
cover of $X$.

######  Problem 1.8.

Prove that a family $\sigma\subset 2^{X}$ is a subbase of some topology on $X$
if and only if $\sigma$ is a cover of $X$. Moreover, each cover of $X$
generates a unique topology.

######  Example 1.13.

The family of all subsets of the real line $\mathbb{R}$, each of which is an
open ray, forms a subbase of the standard topology and is not a base of this
topology.

###  1.3 Standard constructions of topologies

This section provides examples of standard constructions that allow to build
new examples of topological spaces from existing ones.

######  Construction 1.1.

Let $\sigma$ be an arbitrary family of subsets of a set $X$, and
$\mathcal{T}_{\sigma}$ be the family of all topologies on $X$ containing
$\sigma$. Then $\tau:=\cap\mathcal{T}_{\sigma}$ is the smallest topology
containing $\sigma$. If $\sigma$ is a cover of $X$, then $\sigma$ is a subbase
of $\tau$.

######  Construction 1.2 (Disjoint union).

Let $\mathcal{A}=\\{X_{i}\\}_{i\in I}$ be a family of topological spaces. We
define a topology on $\sqcup\mathcal{A}=\sqcup_{i\in I}X_{i}$, setting its
base to be equal to $\sqcup_{i\in I}\tau_{X_{i}}$. The set $\sqcup_{i\in
I}X_{i}$ with the corresponding topology is called _the disjoint union of the
topological spaces $X_{i}$_.

######  Construction 1.3 (Cartesian product).

Let $\mathcal{A}=\\{X_{i}\\}_{i\in I}$ be an arbitrary family of topological
spaces. The set of all mappings $w\colon I\to\sqcup_{i\in I}X_{i}$ such that
$w(i)\in X_{i}$ for every $i\in I$ is called _the Cartesian product_ of the
spaces $X_{i}$ and is denoted by $W:=\prod\mathcal{A}=\prod_{i\in I}X_{i}$. In
particular, if all $X_{i}$ are equal to the same space $X$, then $W=X^{I}$,
where the latter, recall, denotes the set of all mappings from $I$ to $X$. For
convenience, we will often write $w_{i}$ instead of $w(i)$, and we will call
this value _the $i$-th coordinate of the point $w\in\prod_{i\in I}X_{i}$_.

We define a topology on $W$, choosing as its subbase the family of all
products $\prod_{i\in I}U_{i}$, $U_{i}\in\tau_{X_{i}}$, in which only one
$U_{i}$ can differ from $X_{i}$. The corresponding base consists of
$\prod_{i\in I}U_{i}$, $U_{i}\in\tau_{X_{i}}$, in which only a finite number
of $U_{i}$ can differ from $X_{i}$. This topology is called _the product
topology_ or _the Tychonoff topology_.

In the case when $I$ is a finite set, say, $I=\\{1,\ldots,n\\}$, then the
Cartesian product of the spaces $X_{i}$ is denoted by $X_{1}\times\cdots\times
X_{n}$. In particular, in this way one can define the standard topology on the
$n$-dimensional arithmetic space $\mathbb{R}^{n}$.

######  Problem 1.9.

Show that the standard topology of the Euclidean space $\mathbb{R}^{n}$
coincides with the topology of the Cartesian product
$\mathbb{R}\times\cdots\times\mathbb{R}$ of real lines endowed with the
standard topology.

######  Example 1.14.

_Sorgenfrey space_ is the Cartesian product of the Sorgenfrey lines from
Example 1.10 and is used in general topology to illustrate numerous exotic
possibilities.

######  Construction 1.4 (Quotient topology).

Let $X$ be a topological space, and $\nu$ be some equivalence relation on $X$.
Denote by $X/\nu$ the set of classes of this equivalence. For each $x\in X$
denote by $[x]\in X/\nu$ the $\nu$-equivalence class containing $x$, and let
$\pi\colon X\to X/\nu$, $\pi\colon x\mapsto[x]$, be the canonical projection.
Then the family of all $U\subset X/\nu$ such that $\pi^{-1}(U)\in\tau_{X}$
forms a topology called _the quotient topology_. The set $X/\nu$ endowed with
the quotient topology is called _the quotient space_.

######  Construction 1.5 (Vietoris topology).

Let $X$ be an arbitrary topological space. For each finite collection of open
sets $U_{1},\ldots,U_{n}\in\tau_{X}$ we put

$\langle U_{1},\ldots,U_{n}\rangle=\\{Y\subset X:Y\subset\cup_{i=1}^{n}U_{i}\
\text{and $Y\cap U_{i}\neq\emptyset$ for all $i=1,\ldots,n$}\\}.$

Note that if at least one of $U_{i}$ is empty, then $\langle
U_{1},\ldots,U_{n}\rangle=\emptyset$.

######  Problem 1.10.

Show that the families

$\sigma=\bigl{\\{}\langle U\rangle:U\in\tau_{X}\bigr{\\}}\cup\bigl{\\{}\langle
X,U\rangle:U\in\tau_{X}\bigr{\\}}\ \ \text{and}\ \ \beta=\bigl{\\{}\langle
U_{1},\ldots,U_{n}\rangle:U_{1},\ldots,U_{n}\in\tau_{X}\bigr{\\}}$

form respectively a subbase and the corresponding base of some topology on
$2^{X}$.

The topology on $2^{X}$ defined in Problem 1.10 is called _the Vietoris
topology_.

######  Remark 1.15.

Usually, Vietoris topology is defined on the family of all nonempty closed
subsets of a topological space.

######  Problem 1.11.

Prove that each construction of these section provides a topology.

###  1.4 Continuous mappings

As a rule, all considered mappings between topological spaces are consistent
with topologies. Such mappings are called continuous. We give three equivalent
definitions of continuity.

######  Definition 1.16.

_A neighborhood of a point $x\in X$_ of a topological space $X$ is an
arbitrary open set $U\subset X$ containing $x$. _A neighborhood of a subset
$Z$_ of a topological space $X$ is an arbitrary open set $U\subset X$
containing $Z$.

######  Remark 1.17.

For convenience, we denote an arbitrary neighborhood of a point $x\in X$ by
$U^{x}$.

######  Definition 1.18.

A mapping $f\colon X\to Y$ between topological spaces _is continuous at $x\in
X$_ if for any neighborhood $U^{f(x)}$ there exists a neighborhood $U^{x}$
such that $f(U^{x})\subset U^{f(x)}$. The mapping $f$, continuous at all
points $x\in X$, is called _continuous_.

######  Definition 1.19.

A mapping $f\colon X\to Y$ between topological spaces _is continuous_ if for
any open set $U\subset Y$ its preimage $f^{-1}(U)\subset X$ is open (the
preimage of each open set is open).

######  Definition 1.20.

A mapping $f\colon X\to Y$ between topological spaces _is continuous_ if for
any closed set $F\subset Y$ its preimage $f^{-1}(F)\subset X$ is closed (the
preimage of each closed set is closed).

######  Problem 1.12.

Prove that the definitions 1.18, 1.19, and 1.20 are equivalent.

######  Problem 1.13.

Let $f\colon X\to Y$ be a mapping of topological spaces and $\sigma$ a subbase
of the topology on the space $Y$. Prove that $f$ is continuous if and only if
$f$-preimage of each element from the subbase $\sigma$ is open in $X$.

######  Remark 1.21.

When we speak of the continuity of a function $f\colon X\to\mathbb{R}$ or,
more generally, of a vector-valued mapping $f\colon X\to\mathbb{R}^{n}$ from a
topological space $X$, then, unless otherwise stated, on $\mathbb{R}$ and
$\mathbb{R}^{n}$ we consider the standard topologies (see. Remark 1.5).

######  Problem 1.14.

Show that the identity mapping and the composition of continuous mappings are
continuous.

######  Problem 1.15.

Let $X$ be a topological space, and $Z\subset X$ be its subspace. Show that
the inclusion mapping $i\colon Z\to X$, $i(z)=z$ for each point $z\in Z$, is
continuous.

######  Problem 1.16.

Let $X$, $Y$ be topological spaces, $W\subset Y$ be a subspace of $Y$, and
$f\colon X\to W$ be a continuous mapping. Let $g\colon X\to Y$ be a mapping
coinciding with $f$: for each $x\in X$ it holds $f(x)=g(x)$. Prove that the
mapping $g$ is continuous.

Let $f\colon X\to Y$ be an arbitrary mapping of sets. Choose arbitrary subsets
$Z\subset X$ and $W\subset Y$ such that $f(Z)\subset W$. Then _the restriction
$f|_{Z,W}$ of the mapping $f$ to $Z$ and $W$_ is the mapping $g\colon Z\to W$
that coincides on the domain with the mapping $f$, i.e., for any $x\in Z$ it
holds $f(x)=g(x)$.

######  Problem 1.17.

Let $f\colon X\to Y$ be a continuous mapping of topological spaces, $Z\subset
X$, $W\subset Y$, $f(Z)\subset W$. Then the restriction $f|_{Z,W}\colon Z\to
W$ is also continuous as the mapping of the topological spaces $Z$ and $W$
with the topologies induced on them from $X$ and $Y$, respectively.

######  Problem 1.18.

Let $\\{X_{i}\\}_{i\in I}$ be a cover of a topological space $X$ by open
subsets $X_{i}$, and $f\colon X\to Y$ a mapping to a topological space $Y$.
Show that $f$ is continuous if and only if all the restrictions $f|_{X_{i}}$
are continuous. In particular, this holds when $X=\sqcup_{i\in I}X_{i}$ is the
disjoint union of some topological spaces. Will this result remain true if we
replace $\\{X_{i}\\}$ with a cover of $X$ by arbitrary sets?

######  Problem 1.19.

Let $X=\sqcup_{i\in I}X_{i}$ be the disjoint union of some topological spaces
and $f\colon X\to Y$ be a map into a topological space $Y$. Show that $f$ is
continuous if and only if all its restrictions $f|_{X_{i}}$ are continuous.

######  Problem 1.20.

Let $\\{X_{i}\\}_{i\in I}$ be a family of topological spaces and
$X=\prod_{i\in I}X_{i}$. We define the canonical projection $\pi_{i}\colon
X\to X_{i}$ by setting $\pi_{i}(x)=x_{i}$. Prove that the product topology on
$X$ is the smallest of those topologies in which all the projections $\pi_{i}$
are continuous.

######  Problem 1.21.

Let $\\{Y_{i}\\}_{i\in I}$ be a family of topological spaces, $Y=\prod_{i\in
I}Y_{i}$, and $f_{i}\colon X\to Y_{i}$ be mappings from some topological space
$X$. We construct the mapping $F:=\prod_{i\in I}f_{i}\colon X\to Y$ by
associating with each point $x\in X$ the element $y\in Y$ defined as follows:
$y_{i}=f_{i}(x)$. Prove that the mapping $F$ is continuous if and only if all
$f_{i}$ are continuous.

######  Problem 1.22.

Let $A\subset\mathbb{R}^{n}$ be an arbitrary subset, $(x^{1},\ldots,x^{n})$
the Cartesian coordinates on $\mathbb{R}^{n}$, $f\colon A\to\mathbb{R}^{m}$ a
continuous mapping, $(y^{1},\ldots,y^{m})$ the Cartesian coordinates on
$\mathbb{R}^{m}$, and $y^{i}=y^{i}(x^{1},\ldots,x^{n})$ the coordinate
functions of the mapping $f$. Prove that the mapping $f$ is continuous if and
only if all the coordinate functions $y^{i}=y^{i}(x^{1},\ldots,x^{n})$ are
continuous.

######  Problem 1.23.

Describe all continuous functions on a topological space with Zariski
topology.

###  1.5 Homeomorphisms, embeddings

An important particular case of continuous mapping is a homeomorphism.

######  Definition 1.22.

A mapping $f\colon X\to Y$ of topological spaces is called _a homeomorphism_
if it is bijective, and both the maps $f$ and $f^{-1}$ are continuous.
Topological spaces between which there is a homeomorphism are called
_homeomorphic_.

######  Remark 1.23.

A homeomorphism, being a bijection, identifies not only points of spaces, but
also identifies topologies, establishing a one-to-one correspondence between
them. For clarity, we can imagine that the homeomorphism $f:X\to Y$ is a
replacement for the names of points in the space $X$: the point $x\in X$ is
“renamed” to $f(x)$, without changing the topology. From these considerations
it follows that all topological properties of homeomorphic spaces are the
same.

The next exercise follows directly from Problem 1.17.

######  Problem 1.24.

Let $f\colon X\to Y$ be a homeomorphism, and $Z\subset X$, $W=f(Z)$. Prove
that the restriction $f|_{Z,W}\colon Z\to W$ is also a homeomorphism.

An injective mapping $f\colon X\to Y$ of topological spaces is called _an
embedding of $X$ into $Y$_ if the restriction $f|_{X,f(X)}$ is a
homeomorphism.

######  Problem 1.25.

Show that every embedding is continuous. Give an example of a continuous
injective mapping of topological spaces that is not an embedding.

###  1.6 Convergence of sequences

_A sequence_ in a set $X$ is an arbitrary mapping $x\colon{\mathbb{N}}\to X$
from the set of natural numbers ${\mathbb{N}}=\\{1,2,\ldots\\}$. For
convenience, the points $x(n)$ are usually denoted by $x_{n}$. Also, for
brevity, it is customary to say that _a sequence of points $x_{n}$_ is given.

######  Definition 1.24.

A sequence of points $x_{n}$ in a topological space $X$ is called _convergent_
if, for some $x\in X$, called _a limit of this sequence_ , the following
holds: for any neighborhood $U^{x}$ there exists $N\in{\mathbb{N}}$ such that
for all $n\geq N$ we have $x_{n}\in U^{x}$. If the sequence is not convergent,
then it is called _divergent_.

######  Problem 1.26.

Let $\omega$ be a character not contained in ${\mathbb{N}}$. We define a
topology on the set $\bar{N}={\mathbb{N}}\cup\\{\omega\\}$, taking as a base
all points from ${\mathbb{N}}$, as well as all sets of the form $\\{n\geq
N\\}\cup\\{\omega\\}$, $N\in{\mathbb{N}}$. Show that a sequence
$x\colon{\mathbb{N}}\to X$ converges if and only if the mapping $x$ can be
extended to a continuous mapping on $\bar{{\mathbb{N}}}$.

######  Problem 1.27.

Show that a continuous mapping $f\colon X\to Y$ of topological spaces takes
convergent sequences to convergent ones. Show that if $X$ is a metric space,
then every mapping $g\colon X\to Y$ that takes convergent sequences into
convergent ones is continuous. Give an example of a topological space $X$ and
a mapping $h\colon X\to Y$ into a topological space $Y$, which takes
convergent sequences into convergent ones, but is not continuous nonetheless.

######  Problem 1.28.

Let $x_{1},x_{2},\ldots$ be a sequence of points in a metric space $X$.
Suppose that for some point $x\in X$ each neighborhood of $x$ intersects the
set $\\{x_{i}\\}_{i=1}^{\infty}\setminus\\{x\\}$. Prove that the sequence
$x_{1},x_{2},\ldots$ contains a convergent subsequence. Prove that if a
sequence of points in a metric space does not contain any convergent
subsequence, then for each $x\in X$ there exists $r>0$ such that the open ball
$U_{r}(x)$ does not contain points of this sequence other than $x$.

###  1.7 Closure, interior, boundary, dense subsets, separability

Let $Y$ be a subset of a topological space $X$. A point $x\in X$ is called _an
adherent point_ , or _a closure point_ , or _a contact point for $Y$_ if every
neighborhood of $x$ intersects $Y$. The set of all adherent points of the set
$Y$ is called its _closure_ and is denoted by $\overline{Y}$.

######  Problem 1.29.

Prove that the closure of a set $Y\subset X$ is the smallest closed subset of
$X$ containing $Y$, i.e., $\overline{Y}$ is the intersection of all closed
sets containing $Y$.

A subset of $Y$ of a topological space $X$ is called _everywhere dense in $X$_
if $\overline{Y}=X$.

######  Example 1.25.

The set of all rational numbers, like the set of all irrational numbers, are
everywhere dense in the real line.

######  Problem 1.30.

Let the topology of Zariski of weight $m$ be given on an infinite set $X$.
Then a subset $Y\subset X$ is everywhere dense in $X$ if and only if $\\#Y\geq
m$.

A topological space is called _separable_ if it contains an everywhere dense
sequence.

######  Example 1.26.

Each finite space is separable. The Euclidean space $\mathbb{R}^{n}$ is also
separable: as an everywhere dense sequence we can take arbitrary numbered set
of all points with rational coordinates. Each space with a countable Zariski
topology is separable. Sorgenfrey space (Example 1.14) is separable.

######  Problem 1.31.

Show that in metric space, separability is equivalent to having a countable
base. Extract from this that every subset of a separable metric space is
separable. Show that an open subset of an arbitrary separable topological
space is separable. Give an example of a separable topological space
containing an non-separable subset (use the Sorgenfrey plane).

A point $x$ from a subset $Y$ of a topological space $X$ is called _interior
for $Y$_ if some neighborhood of $x$ is contained in $Y$. The family of all
interior points of the set $Y$ is called its _interior_ and is denoted by
$\operatorname{Int}Y$.

######  Problem 1.32.

Show that the interior $\operatorname{Int}Y$ is the largest open subset of $X$
contained in $Y$.

######  Problem 1.33.

Prove that a subset $Y$ of the topological space $X$ is closed if and only if
$Y=\overline{Y}$, and is open if and only if $Y=\operatorname{Int}Y$.

A point $x\in X$ of a topological space $X$ is called _a boundary point for a
subset $Y\subset X$_ if each neighborhood of $x$ intersects both $Y$ and its
complement $X\setminus Y$. The set of all boundary points of the set $Y$ is
called its _boundary_ and is denoted by $\partial Y$.

######  Problem 1.34.

Prove that the boundary $\partial Y$ is a closed subset of $X$, and

$\partial
Y=\overline{Y}\setminus\operatorname{Int}Y=\overline{Y}\cap\overline{X\setminus
Y}.$

###  1.8 Separated spaces

There are a number of separation axioms that generate various classes of
topological spaces. We will not dwell on this in detail here, but formulate
only one axiom of separation, which will be useful to us in the future.

A topology on a set $X$, as well as the topological space $X$ itself, is
called _Hausdorff_ or _separated_ if any two points of $X$ have disjoint
neighborhoods.

######  Example 1.27.

Each discrete topology is Hausdorff. Each metric space is Hausdorff. If the
set $X$ consists of more than one point, then the anti-discrete topology is
not Hausdorff. Also, the Zariski topology is not a Hausdorff topology (see
Example 1.9).

######  Problem 1.35.

Show that in a Hausdorff topological space every point is closed. Give an
example of a non-Hausdorff topological space in which all points are closed.

######  Problem 1.36.

Show that the disjoint union and the Cartesian product of Hausdorff
topological spaces are also Hausdorff.

######  Problem 1.37.

Show that in a Hausdorff topological space the limit of a convergent sequence
is uniquely defined. Give an example of a topological space in which each
sequence converges to each point.

######  Problem 1.38.

Describe what sequences in a space with Zariski topology are convergent, and
what limits each convergent sequence has.

###  1.9 Connected spaces

We say that a set $X$ _is partitioned into subsets $\\{X_{i}\\}_{i\in I}$_ if
$X=\sqcup_{i\in I}X_{i}$.

A topological space (its topology) is called _disconnected_ if it can be
partitioned into two nonempty open (equivalently, closed) sets. If such a
partition does not exist, then the topological space is called _connected_. A
subset of a topological space is _connected_ (_disconnected_), if such is the
topology induced on it. In other words, a subset $Y$ of a topological space
$X$ is _disconnected_ if there exist $U,V\in\tau_{X}$ such that $Y\subset
U\cup V$, and both intersections $Y\cap U$ and $Y\cap V$ are nonempty and do
not intersect each other.

######  Problem 1.39.

Prove that each segment $[a,b]\subset\mathbb{R}$ is connected.

######  Problem 1.40.

Prove that the closure of a connected subset of a topological space is
connected.

######  Problem 1.41.

Let $\\{A_{i}\\}_{i\in I}$ be a family of connected pairwise intersecting
subsets of a topological space $X$, then the set $\cup_{i\in I}A_{i}$ is
connected.

######  Problem 1.42.

Show that the image of a connected topological space under a continuous
mapping is also connected.

######  Problem 1.43.

Prove that every continuous function on a connected topological space takes
all intermediate values.

The maximum (by inclusion) connected subset of a topological space is called a
_connected component_ of this space.

######  Problem 1.44.

Show that each connected component is closed, and that each topological space
is uniquely partitioned into its connected components. If such a partition is
finite, then connected components are also open. Give an example of a
topological space in which some connected components are not open.

###  1.10 Path-connected spaces

_A curve_ in a topological space $X$ is an arbitrary continuous map
$\gamma\colon[a,b]\to X$. It is said that the curve $\gamma$ _joins the points
$\gamma(a)$ and $\gamma(b)$_.

A topological space $X$ is called _path-connected_ if any two of its points
can be connected by a curve.

######  Problem 1.45.

Prove that a path-connected topological space is connected. Give an example of
a connected space that is not path-connected.

###  1.11 Compact and sequentially compact spaces

_A subcover of a cover_ is a subfamily of a cover, which itself is a cover. A
cover of a topological space composed of open sets is called _open_.

######  Definition 1.28.

A topological space $X$ is called _compact_ if a finite subcover can be found
in any of its open covers.

######  Remark 1.29.

To define a cover for a subset $Y$ of a topological space $X$, it is more
convenient to modify Definition 1.28, rather than reduce it to the
corresponding concept for the induced topology. Namely, an open cover of $Y$
is a family $\\{U_{a}\\}_{a\in A}$ of open subsets of $X$ such that
$Y\subset\cup_{a\in A}U_{a}$. Other definitions do not change.

######  Problem 1.46.

Show that a finite union of compact subsets of a topological space is compact.

######  Problem 1.47.

Prove the following statements:

  1. (1)

the image under a continuous mapping from a compact topological space is
compact;

  2. (2)

a closed subset of a compact topological space is compact;

  3. (3)

a compact subset of a Hausdorff topological space is closed;

  4. (4)

a continuous bijective mapping from a compact topological space to a Hausdorff
space is a homeomorphism;

  5. (5)

give an example of an infinite topological space in which all subsets are
compact. Note that in such a space there are compact subsets that are not
closed;

  6. (6)

give an example of a continuous bijective mapping of topological spaces that
is not a homeomorphism.

######  Problem 1.48 (Alexander subbase theorem).

Let $X$ be a topological space and $\sigma$ its subbase. Prove that $X$ is
compact if and only if each cover of $X$ by elements of the subbase $\sigma$
has a finite subcover.

######  Problem 1.49 (Tychonoff’s theorem).

Prove that the Cartesian product $\prod_{i\in I}X_{i}$ of topological spaces
$X_{i}$, endowed with Tychonoff topology, is compact if and only if all
$X_{i}$ are compact.

######  Problem 1.50.

Prove that each segment $[a,b]\subset\mathbb{R}$ is compact.

A subset of a metric space is called _bounded_ if it is contained in some
ball.

######  Problem 1.51.

Prove that a subset of a Euclidean space is compact if and only if it is
closed and bounded.

######  Problem 1.52.

Prove that every compact metric space is bounded. Prove that a continuous
function on a compact topological space is bounded and takes its largest and
smallest values.

######  Definition 1.30.

A topological space is called _sequentially compact_ if every sequence of its
points has a convergent subsequence.

######  Problem 1.53.

Prove that every sequentially compact metric space is bounded. Prove that a
continuous function on a sequentially compact topological space is bounded and
takes its largest and smallest values.

######  Remark 1.31.

Note that compactness and sequential compactness in the case of general
topological spaces are not related to each other: there are spaces that have
one of these properties and do not have the other. Since the examples are
quite complicated, we will omit them here. However, everything is much simpler
for metric spaces, see Theorem 2.20 in Chapter 2.

###  1.12 Hyperspaces

A family of various subsets of a topological or metric space endowed with a
certain topology or metric is called _a hyperspace_. In Construction 1.5
above, we defined the Vietoris topology on the set $2^{X}$ of all subsets of a
topological space $X$. Thus, $2^{X}$ is a special case of hyperspace.

Here are a few more examples of hyperspaces (in all these spaces, the topology
is induced from $2^{X}$ in the standard way):

  * •

by $\mathcal{P}_{0}(X)\subset 2^{X}$ we denote the set of all nonempty subsets
of $X$;

  * •

by $\mathcal{C\\!L}(X)\subset\mathcal{P}_{0}(X)$ we denote the set of all
nonempty closed subsets of $X$;

  * •

by $\mathcal{C}(X)\subset\mathcal{C\\!L}(X)$ the set of all nonempty closed
connected subsets of $X$;

  * •

by $\mathcal{C}_{n}(X)\subset\mathcal{C\\!L}(X)$ the set of all nonempty
closed subsets of $X$ having at most $n$ components;

  * •

by $\mathcal{C}_{\infty}(X)\subset\mathcal{C\\!L}(X)$ the set of all nonempty
closed subsets of $X$, each of which has finitely many components;

  * •

by $\mathcal{K}(X)\subset\mathcal{P}_{0}(X)$ the set of all nonempty compact
subsets of $X$;

  * •

by $\mathcal{F}_{n}(X)\subset\mathcal{K}(X)$ the set of all nonempty at most
$n$-point subsets of $X$;

  * •

by $\mathcal{F}_{\infty}(X)\subset\mathcal{K}(X)$ the set of all nonempty
finite subsets of $X$.

There are numerous, usually obvious, connections between these spaces. For
example, if the space $X$ is Hausdorff, then
$\mathcal{K}(X)\subset\mathcal{C\\!L}(X)$; if $X$ is Hausdorff and compact,
then $\mathcal{K}(X)=\mathcal{C\\!L}(X)$.

A connected nonempty compact Hausdorff topological space is called _a
continuum_. If the space $X$ is Hausdorff, then
$\mathcal{K}(X)\cap\mathcal{C}(X)$ is the set of all continua. In some
literature, for example, in [2], this space is denoted by $\mathcal{C}(X)$.

######  Problem 1.54.

Let $X=\\{a,b\\}$. We define the following topology on $X$ as follows:
$\tau=\bigl{\\{}\emptyset,X,\\{a\\}\bigr{\\}}$. Find out what the space
$\operatorname{CL}(X)$ is.

######  Definition 1.32.

A topological space is called _a space of class $T_{0}$_ if, for any two
different points of this space, at least one of them has a neighborhood that
does not contain the second point.

######  Problem 1.55.

Prove that the space $\operatorname{CL}(X)$ is always a space of class
$T_{0}$.

######  Problem 1.56.

A topological space is called _a space of class $T_{1}$_ if, for any two
different points of this space, each of them has a neighborhood that does not
contain the remaining point.

######  Problem 1.57.

Prove that if $X$ is a space of class $T_{1}$, then $\operatorname{CL}(X)$ is
also a space of class $T_{1}$. Give an example that demonstrates that the
converse is not true.

######  Problem 1.58.

Prove that the space $\mathcal{P}_{0}(X)$ belongs to the class $T_{1}$ if and
only if the space $X$ is discrete.

## References to Chapter 1

  * [1] R. Engelking, _General Topology_ , Heldermann, Berlin, 1989.
  * [2] S. Nadler, _Hyperspaces of Sets_ , 1978.

### Exercises to Chapter 1

######  Exercise 1.1.

Show that the family of all closed subsets of a topological space $X$ contains
$\emptyset$ and $X$, and that the intersection of any collection of closed
subsets, as well as the union of any finite collection of closed subsets are
some closed sets.

######  Exercise 1.2.

Let $X$ be a topological space and $Y\subset X$. Consider the family
$\tau_{Y}:=\\{U\cap Y:U\in\tau_{X}\\}$. Prove that $\tau_{Y}$ is a topology on
$Y$.

######  Exercise 1.3.

For a metric space $(X,\rho)$ define $\tau_{\rho}\subset 2^{X}$ as the
collection consisting of the empty set and all possible unions of open balls.
Prove that the family $\tau_{\rho}$ is a topology.

######  Exercise 1.4.

Prove that a family $\beta\subset 2^{X}$ is a base of some topology $\tau$ on
$X$ if and only if $\beta$ is a cover of $X$, and for any intersecting
$B_{1},B_{2}\in\beta$ their intersection $B_{1}\cap B_{2}$ is the union of
some elements from $\beta$. Moreover, each family satisfying these properties,
generates a unique topology.

######  Exercise 1.5.

Let some topologies $\tau_{1}$ and $\tau_{2}$ with bases $\beta_{1}$ and
$\beta_{2}$ be given on a set $X$. Then $\tau_{1}=\tau_{2}$ if and only iff
for any $x\in X$ the following condition is fulfilled: for any
$B_{2}\in\beta_{2}$, $x\in B_{2}$, there is $B_{1}\in\beta_{1}$ for which
$x\in B_{1}\subset B_{2}$, and vice versa, for any $B_{1}\in\beta_{1}$, $x\in
B_{1}$, there exists $B_{2}\in\beta_{2}$ for which $x\in B_{2}\subset B_{1}$.
In particular, for a topological space $X$, a collection $\beta$ of open sets
satisfying the condition of Exercise 1.4 is a base of the topology $\tau_{X}$
if and only if for each open set $U\in\tau_{X}$ and any point $x\in U$ there
exists some $B\in\beta$ such that $x\in B\subset U$.

######  Exercise 1.6.

Let $X$ be an infinite set of cardinality $n$, and $m$ be an infinite cardinal
number, with $m\leq n$. Consider a family $\mathcal{F}$ of all $F\subset X$
such that $\\#F<m$, and let $\beta_{m}=\\{X\setminus F:F\in\mathcal{F}\\}$.
Prove that the family $\beta_{m}$ is a base of some topology.

######  Exercise 1.7.

Show that the collection of all possible half-intervals of the form
$[a,b)\subset\mathbb{R}$ form a base of some topology that contains the
standard topology.

######  Exercise 1.8.

Prove that a family $\sigma\subset 2^{X}$ is a subbase of some topology on $X$
if and only if $\sigma$ is a cover of $X$. Moreover, each cover of $X$
generates a unique topology.

######  Exercise 1.9.

Show that the standard topology of the Euclidean space $\mathbb{R}^{n}$
coincides with the topology of the Cartesian product
$\mathbb{R}\times\cdots\times\mathbb{R}$ of real lines endowed with the
standard topology.

######  Exercise 1.10.

Let $X$ be an arbitrary topological space. For each finite collection
$U_{1},\ldots,U_{n}\in\tau_{X}$ we put

$\langle U_{1},\ldots,U_{n}\rangle=\\{Y\subset X:Y\subset\cup_{i=1}^{n}U_{i},\
\text{and $Y\cap U_{i}\neq\emptyset$ for all $i=1,\ldots,n$}\\}.$

Show that the families

$\sigma=\bigl{\\{}\langle U\rangle:U\in\tau_{X}\bigr{\\}}\cup\bigl{\\{}\langle
X,U\rangle:U\in\tau_{X}\bigr{\\}}\ \ \text{and}\ \ \beta=\bigl{\\{}\langle
U_{1},\ldots,U_{n}\rangle:U_{1},\ldots,U_{n}\in\tau_{X}\bigr{\\}}$

form respectively a subbase and the corresponding base of some topology on
$2^{X}$.

######  Exercise 1.11.

Prove that each construction from the section “Standard constructions of
topologies” provides a topology.

######  Exercise 1.12.

Prove that the definitions 1.18, 1.19, and 1.20 are equivalent.

######  Exercise 1.13.

Let $f\colon X\to Y$ be a mapping of topological spaces and $\sigma$ be a
subbase of the topology on the space $Y$. Prove that $f$ is continuous if and
only if $f$-preimage of each element from the subbase $\sigma$ is open in $X$.

######  Exercise 1.14.

Show that the identity mapping and the composition of continuous mappings are
continuous.

######  Exercise 1.15.

Let $X$ be a topological space, and $Z\subset X$ be its subspace. Show that
the inclusion mapping $i\colon Z\to X$, $i(z)=z$ for each point $z\in Z$, is
continuous.

######  Exercise 1.16.

Let $X$, $Y$ be topological spaces, $W\subset Y$ be a subspace of $Y$, and
$f\colon X\to W$ be a continuous mapping. Let $g\colon X\to Y$ be a mapping
coinciding with $f$: for each $x\in X$ it holds $f(x)=g(x)$. Prove that the
mapping $g$ is continuous.

######  Exercise 1.17.

Let $f\colon X\to Y$ be a continuous mapping of topological spaces, $Z\subset
X$, $W\subset Y$, $f(Z)\subset W$. Then the restriction $f|_{Z,W}\colon Z\to
W$ is also continuous as the mapping of the topological spaces $Z$ and $W$
with the topologies induced on them from $X$ and $Y$, respectively.

######  Exercise 1.18.

Let $\\{X_{i}\\}_{i\in I}$ be a cover of a topological space $X$ by open
subsets $X_{i}$, and $f\colon X\to Y$ a mapping to a topological space $Y$.
Show that $f$ is continuous if and only if all the restrictions $f|_{X_{i}}$
are continuous. In particular, this holds when $X=\sqcup_{i\in I}X_{i}$ is the
disjoint union of some topological spaces. Will this result remain true if we
replace $\\{X_{i}\\}$ with a cover of $X$ by arbitrary sets?

######  Exercise 1.19.

Let $X=\sqcup_{i\in I}X_{i}$ be the disjoint union of some topological spaces
and $f\colon X\to Y$ be a map into the topological space $Y$. Show that $f$ is
continuous if and only if all its restrictions $f|_{X_{i}}$ are continuous.

######  Exercise 1.20.

Let $\\{X_{i}\\}_{i\in I}$ be a family of topological spaces and
$X=\prod_{i\in I}X_{i}$. We define the canonical projection $\pi_{i}\colon
X\to X_{i}$ by setting $\pi_{i}(x)=x_{i}$. Prove that the product topology on
$X$ is the smallest of those topologies in which all the projections $\pi_{i}$
are continuous.

######  Exercise 1.21.

Let $\\{Y_{i}\\}_{i\in I}$ be a family of topological spaces, $Y=\prod_{i\in
I}Y_{i}$, and $f_{i}\colon X\to Y_{i}$ are mappings from some topological
space $X$. We construct the mapping $F:=\prod_{i\in I}f_{i}\colon X\to Y$ by
associating with each point $x\in X$ the element $y\in Y$ defined as follows:
$y_{i}=f_{i}(x)$. Prove that the mapping $F$ is continuous if and only if all
$f_{i}$ are continuous.

######  Exercise 1.22.

Let $A\subset\mathbb{R}^{n}$ be an arbitrary subset, $(x^{1},\ldots,x^{n})$
the Cartesian coordinates on $\mathbb{R}^{n}$, $f\colon A\to\mathbb{R}^{m}$ a
continuous mapping, $(y^{1},\ldots,y^{m})$ the Cartesian coordinates on
$\mathbb{R}^{m}$, and $y^{i}=y^{i}(x^{1},\ldots,x^{n})$ the coordinate
functions of the mapping $f$. Prove that the mapping $f$ is continuous if and
only if all the coordinate functions $y^{i}=y^{i}(x^{1},\ldots,x^{n})$ are
continuous.

######  Exercise 1.23.

Describe all continuous functions on a topological space with Zariski
topology.

######  Exercise 1.24.

Let $f\colon X\to Y$ be a homeomorphism, and $Z\subset X$, $W=f(Z)$. Prove
that the restriction $f|_{Z,W}\colon Z\to W$ is also a homeomorphism. Show
that the letters b, c, f, g, i, h, o are pairwise non-homeomorphic.

######  Exercise 1.25.

Show that every embedding is continuous. Give an example of a continuous
injective mapping of topological spaces that is not an embedding.

######  Exercise 1.26.

Let $\omega$ be a character not contained in ${\mathbb{N}}$. We define a
topology on the set $\bar{N}={\mathbb{N}}\cup\\{\omega\\}$, taking as a base
all points from ${\mathbb{N}}$, as well as all sets of the form $\\{n\geq
N\\}\cup\\{\omega\\}$, $N\in{\mathbb{N}}$. Show that a sequence
$x\colon{\mathbb{N}}\to X$ converges if and only if the mapping $x$ can be
extended to a continuous mapping on $\bar{{\mathbb{N}}}$.

######  Exercise 1.27.

Show that a continuous mapping $f\colon X\to Y$ of topological spaces takes
convergent sequences to convergent ones. Show that if $X$ is a metric space,
then every mapping $g\colon X\to Y$ that takes convergent sequences into
convergent ones is continuous. Give an example of a topological space $X$ and
a mapping $h\colon X\to Y$ into a topological space $Y$, which takes
convergent sequences into convergent ones, but is not continuous nonetheless.

######  Exercise 1.28.

Let $x_{1},x_{2},\ldots$ be a sequence of points in a metric space $X$.
Suppose that for some point $x\in X$ each neighborhood of $x$ intersects the
set $\\{x_{i}\\}_{i=1}^{\infty}\setminus\\{x\\}$. Prove that the sequence
$x_{1},x_{2},\ldots$ contains a convergent subsequence. Extract from this that
if a sequence of points in a metric space does not contain any convergent
subsequence, then for each $x\in X$ there exists $r>0$ such that the open ball
$U_{r}(x)$ does not contain points of this sequence other than $x$.

######  Exercise 1.29.

Prove that the closure of a set $Y\subset X$ is the smallest closed subset of
$X$ containing $Y$, i.e., $\overline{Y}$ is the intersection of all closed
sets containing $Y$.

######  Exercise 1.30.

Let the topology of Zariski of weight $m$ be given on an infinite set $X$.
Then a subset $Y\subset X$ is everywhere dense in $X$ if and only if $\\#Y\geq
m$.

######  Exercise 1.31.

Show that in metric space, separability is equivalent to having a countable
base. Extract from this that every subset of a separable metric space is
separable. Show that an open subset of an arbitrary separable topological
space is separable. Give an example of a separable topological space
containing an non-separable subset (use the Sorgenfrey plane).

######  Exercise 1.32.

Show that the interior $\operatorname{Int}Y$ is the largest open subset of $X$
contained in $Y$.

######  Exercise 1.33.

Prove that a subset $Y$ of the topological space $X$ is closed if and only if
$Y=\overline{Y}$, and is open if and only if $Y=\operatorname{Int}Y$.

######  Exercise 1.34.

Prove that the boundary $\partial Y$ is a closed subset of $X$, and

$\partial
Y=\overline{Y}\setminus\operatorname{Int}Y=\overline{Y}\cap\overline{X\setminus
Y}.$

######  Exercise 1.35.

Show that in a Hausdorff topological space every point is closed. Give an
example of a non-Hausdorff topological space in which all points are closed.

######  Exercise 1.36.

Show that the disjoint union and the Cartesian product of Hausdorff
topological spaces are also Hausdorff.

######  Exercise 1.37.

Show that in a Hausdorff topological space the limit of a convergent sequence
is uniquely defined. Give an example of topological space in which each
sequence converges to each point.

######  Exercise 1.38.

Describe what sequences in a space with Zariski topology are convergent, and
what limits each convergent sequence has.

######  Exercise 1.39.

Prove that each segment $[a,b]\subset\mathbb{R}$ is connected.

######  Exercise 1.40.

Prove that the closure of a connected subset of a topological space is
connected.

######  Exercise 1.41.

Let $\\{A_{i}\\}_{i\in I}$ be a family of connected pairwise intersecting
subsets of a topological space $X$, then the set $\cup_{i\in I}A_{i}$ is
connected.

######  Exercise 1.42.

Show that the image of a connected topological space under a continuous
mapping is also connected.

######  Exercise 1.43.

Prove that every continuous function on a connected topological space takes
all intermediate values.

######  Exercise 1.44.

Show that each connected component is closed, and that each topological space
is uniquely partitioned into its connected components. If such a partition is
finite, then connected components are also open. Give an example of a
topological space in which some connected components are not open.

######  Exercise 1.45.

Prove that a path-connected topological space is connected. Give an example of
a connected space that is not path-connected.

######  Exercise 1.46.

Show that a finite union of compact subsets of a topological space is compact.

######  Exercise 1.47.

Prove the following statements:

  1. (1)

the image under a continuous mapping from a compact topological space is
compact;

  2. (2)

a closed subset of a compact topological space is compact;

  3. (3)

a compact subset of a Hausdorff topological space is closed;

  4. (4)

a continuous bijective mapping from a compact topological space to a Hausdorff
space is a homeomorphism;

  5. (5)

give an example of an infinite topological space in which all subsets are
compact. Note that in such a space there are compact subsets that are not
closed;

  6. (6)

give an example of a continuous bijective mapping of topological spaces that
is not a homeomorphism.

######  Exercise 1.48 (Alexander subbase theorem).

Let $X$ be a topological space and $\sigma$ its subbase. Prove that $X$ is
compact if and only if each cover of $X$ by elements of the subbase $\sigma$
has a finite subcover.

######  Exercise 1.49 (Tychonoff’s theorem).

Prove that the Cartesian product $\prod_{i\in I}X_{i}$ of topological spaces
$X_{i}$, endowed with Tychonoff topology, is compact if and only if all
$X_{i}$ are compact.

######  Exercise 1.50.

Prove that each segment $[a,b]\subset\mathbb{R}$ is compact.

######  Exercise 1.51.

Prove that a subset of a Euclidean space is compact if and only if it is
closed and bounded.

######  Exercise 1.52.

Prove that every compact metric space is bounded. Prove that a continuous
function on a compact topological space is bounded and takes its largest and
smallest values.

######  Exercise 1.53.

Prove that every sequentially compact metric space is bounded. Prove that a
continuous function on a sequentially compact topological space is bounded and
takes its largest and smallest values.

######  Notation.

The following matrix groups consist of real matrices of size $n\times n$ and
are considered as subsets of $\mathbb{R}^{n^{2}}$ with the induced topology
(their rows or columns are written out one after another and form vectors):
$\operatorname{O}(n)$ consists of all orthogonal matrices (_orthogonal
group_); $\operatorname{SO}(n)$ consists of all orthogonal matrices with
determinant $1$ (_special orthogonal group_); $\operatorname{GL}(n)$ consists
of all nondegenerate matrices (_general linear group_); $\operatorname{SL}(n)$
consists of all matrices with determinant $1$ (_special linear group_).

######  Exercise 1.54.

Find out which of the following matrix groups are connected, which are
compact:

$\operatorname{O}(n),\ \operatorname{SO}(n),\ \operatorname{GL}(n),\
\operatorname{SL}(n).$

######  Exercise 1.55.

Let $X=\\{a,b\\}$. We define the following topology on $X$:
$\tau=\bigl{\\{}\emptyset,X,\\{a\\}\bigr{\\}}$. Find out what the space
$\operatorname{CL}(X)$ is.

######  Definition 1.33.

A topological space is called _a space of class $T_{0}$_ if, for any two
different points of this space, at least one of them has a neighborhood that
does not contain the second point.

######  Exercise 1.56.

Prove that the space $\operatorname{CL}(X)$ is always a space of class
$T_{0}$.

######  Definition 1.34.

A topological space is called _a space of class $T_{1}$_ if, for any two
different points of this space, each of them has a neighborhood that does not
contain the remaining point.

######  Exercise 1.57.

Prove that if $X$ is a space of class $T_{1}$, then $\operatorname{CL}(X)$ is
also a space of class $T_{1}$. Give an example that demonstrates that the
converse is not true.

######  Exercise 1.58.

Prove that the space $\mathcal{P}_{0}(X)$ belongs to the class $T_{1}$ if and
only if the space $X$ is discrete.

##  Chapter 2 Introduction to Metric Spaces.

  * Schedule.

Distance, pseudometric or semimetric, metric, open ball, closed ball, sphere,
distance to a nonempty subset, open and closed $r$-neighborhoods of a nonempty
subset, diameter of a subset, natural quotient of pseudometric space,
Lipschitz mappings, Lipschitz constant, dilatation of a Lipschitz mapping,
uniform continuity, bi-Lipschitz mappings, isometric mapping, isometry,
isometry group, standard constructions of metrics, multiplying a metric by a
number, adding to metric a constant, induced distance, semidirect product of
metric spaces, examples, Levenshtein distance, elements of graph theory,
metric construction for graphs, distance on a connected graph, distance on a
connected weighted graph, Cayley graph of a group, quotient pseudometric and
metric, generalized distance, disjoint union of generalized spaces, maximal
pseudometric, the relation between quotient and maximal pseudometrics and
metrics, isometries groups actions and quotient spaces, metrized graphs,
polyhedron spaces, convergence of sequences and completeness, fundamental
sequences, completion of a metric space, equivalence of compactness and
sequential compactness for metric spaces, completeness and total boundedness
equivalent to compactness for metric spaces, canonical isometric embeddings of
metric spaces, Frechet-Kuratowski embedding to the space of bounded continuous
functions, Frechet embedding of a separable metric space to the space of
bounded sequences.

In this section, we discuss some basic facts from metric spaces theory.

###  2.1 Distance

Let $X$ be an arbitrary set. A function $\rho\colon X\times X\to\mathbb{R}$ is
called _a distance_ , if it is non-negative, it is equal to zero on all pairs
of the form $(x,x)$, and it is _symmetric_ : $\rho(x,y)=\rho(y,x)$ for any
$x,y\in X$.

If the distance function $\rho$ satisfies _the triangle inequality_ , namely,
$\rho(x,y)+\rho(y,z)\geq\rho(x,z)$, then such $\rho$ is called _a
pseudometric_ or _a semimetric_ , and the set $X$ with the introduced
pseudometric on it is _a pseudometric space_ or _a semimetric space_.

Thus, the metric defined above is a pseudometric not equal to zero on the
pairs $(x,y)$ with $x\neq y$.

######  Remark 2.1.

It will be convenient for us to introduce a universal notation for the
distance function defined on an arbitrary set, namely, the distance between
points $x$ and $y$ from this set will be denoted by $|xy|$. Even if several
sets are considered at the same time with the distances given on them, we will
denote these distances in the same way, while understanding what distance is
used according to which set the corresponding points belong to.

For each distance given on the set $X$, a number of subsets arise that play an
important role in the study of geometry:

  * •

_an open ball of radius $r>0$ and center $x\in X$_: $U_{r}(x):=\bigl{\\{}y\in
X:|xy|<r\bigr{\\}}$ (above we defined an open ball for a metric);

  * •

_a closed ball of radius $r\geq 0$ and center $x\in X$_:
$B_{r}(x):=\bigl{\\{}y\in X:|xy|\leq r\bigr{\\}}$;

  * •

_a sphere of radius $r\geq 0$ and center $x\in X$_: $S_{r}(x):=\bigl{\\{}y\in
X:|xy|=r\bigr{\\}}$;

Note that in metric space, for $r=0$, both a closed ball and a sphere of
radius $r$ degenerate to a point and are called _degenerate_.

For any point $x\in X$ and a nonempty set $A$, define _the distance from $x$
to $A$_ by setting

$|xA|=|Ax|=\inf\bigl{\\{}|xa|:a\in A\bigr{\\}}.$

This concept gives rise to a number of objects:

  * •

for $r>0$ _an open $r$-neighborhood of the set $A$_ is
$U_{r}(A)=\bigl{\\{}y\in X:|Ay|<r\bigr{\\}}$;

  * •

for $r\geq 0$ _a closed $r$-neighborhood of the set $A$_ is
$B_{r}(A)=\bigl{\\{}y\in X:|Ay|\leq r\bigr{\\}}$.

In addition, for a nonempty $A\subset X$, a numerical characteristic of the
set $A$ is defined — its _diameter_

$\operatorname{diam}A=\sup\bigl{\\{}|aa^{\prime}|:a,a^{\prime}\in
A\bigr{\\}}.$

Moreover, the diameter can also be naturally determined for the empty set by
setting $\operatorname{diam}\emptyset=0$.

######  Remark 2.2.

Sometimes an object $A$ under consideration can simultaneously belong to
different metric spaces, for example, in one space it is a subset, and in
another it is a point. Then, in the notation introduced above, $U_{r}(A)$,
$B_{r}(A)$, etc., as an upper index, we will add either the name of the space
to which $A$ belongs or the metric of this space. A typical case: $A$ can be
considered both as a nonempty subset of the space $X$ with the metric $d$, and
as a point in the space $\mathcal{H}(X)$ of all nonempty closed bounded
subsets of $X$ with some metric $d_{H}$. In this situation, instead of
$U_{r}(A)$ we will write $U_{r}^{X}(A)$ or $U_{r}^{d}(A)$ in the first case,
and $U_{r}^{\mathcal{H}(X)}(A)$ or $U_{r}^{d_{H}}(A)$ in the second one.

Each pseudometric on the set $X$ defines a natural equivalence relation:
$x\sim y$ if and only if $|xy|=0$. Let $X/\\!\\!\sim$ be the set of classes of
this equivalence, and for each $x\in X$ denote by $[x]$ the equivalence class
containing $x$.

######  Problem 2.1.

Prove that for any $x,y\in X$ and $x^{\prime}\in[x]$ and $y^{\prime}\in[y]$ it
is true that $|x^{\prime}y^{\prime}|=|xy|$. Thus, on the set $X/\\!\\!\sim$
the corresponding distance function is correctly defined:
$\bigl{|}[x][y]\bigr{|}=|xy|$. Show that this distance function is a metric.

######  Remark 2.3.

If $\rho$ is the pseudometric on $X$, then the quotient space $X/\\!\\!\sim$
from Problem 2.1 is sometimes denoted by $X/\rho$.

######  Problem 2.2.

Let $X$ be an arbitrary metric space, $x,y\in X$, $r\geq 0$, $s,t>0$, and
$A\subset X$ be nonempty. Verify that

  1. (1)

$U_{s}\bigl{(}\\{x\\}\bigr{)}=U_{s}\bigl{(}x)$ and
$B_{r}\bigl{(}\\{x\\}\bigr{)}=B_{r}\bigl{(}x)$;

  2. (2)

the functions $y\mapsto|xy|$, $y\mapsto|yA|$ are continuous;

  3. (3)

an open neighborhood $U_{s}(A)$ is an open subset of $X$, and a closed
neighborhood $B_{r}(A)$ is a closed subset of $X$;

  4. (4)

$U_{t}\bigl{(}U_{s}(A)\bigr{)}\subset U_{s+t}(A)$ and construct an example
demonstrating that the left-hand side can be different from the right-hand
side;

  5. (5)

$B_{t}\bigl{(}B_{s}(A)\bigr{)}\subset B_{s+t}(A)$ and construct an example
demonstrating that the left-hand side can be different from the right-hand
side;

  6. (6)

$\partial U_{s}(x)$, $\partial B_{s}(x)$ are not related by any inclusion;
$\partial U_{s}(x)\subset S_{s}(x)$ and $\partial B_{r}(x)\subset S_{r}(x)$;
the both previous inclusions can be strict;

  7. (7)

$\operatorname{diam}U_{s}(x)\leq\operatorname{diam}B_{s}(x)\leq 2s$;

  8. (8)

$\operatorname{diam}U_{s}(A)\leq\operatorname{diam}B_{s}(A)\leq\operatorname{diam}A+2s$.

###  2.2 Lipschitz mappings and isometries

Mappings of metric spaces that distort distances no more than a certain finite
number of times are called Lipschitz. More formally, a mapping $f\colon X\to
Y$ of metric spaces is called _Lipschitz_ , if there exists $C\geq 0$ such
that for any $x,x^{\prime}\in X$ the inequality
$\bigl{|}f(x)f(x^{\prime})\bigr{|}\leq C|xx^{\prime}|$ holds. Each such $C$ is
called _a Lipschitz constant_. Sometimes, for brevity, a Lipschitz mapping
with Lipschitz constant $C$ is called _$C$ -Lipschitz_. For $1$-Lipschitz
mapping is reserved the term _nonexpanding_.

######  Problem 2.3.

Let $\mathcal{L}(f)\subset\mathbb{R}$ be the set of all Lipschitz constants
for a Lipschitz mapping $f$. Prove that $\inf\mathcal{L}(f)$ is also a
Lipschitz constant.

The smallest Lipschitz constant for a Lipschitz mapping $f$ is called _the
dilatation of the mapping $f$_ and is denoted by $\operatorname{dil}f$.

A mapping $f\colon X\to Y$ of metric spaces is called _uniformly continuous_
if for any $\varepsilon>0$ there exists $\delta>0$ such that for any points
$x,x^{\prime}\in X$, $|xx^{\prime}|<\delta$, we have
$|f(x)f(x^{\prime})|<\varepsilon$.

######  Problem 2.4.

Show that each Lipschitz mapping is uniformly continuous, and each uniformly
continuous mapping is continuous.

A bijective mapping $f$ between metric spaces such that $f$ and $f^{-1}$ are
Lipschitz is called _bi-Lipschitz_. It is clear that each bi-Lipschitz mapping
is a homeomorphism.

A mapping of metric spaces $f\colon X\to Y$ is called _isometric_ if it
preserves distances: $\bigl{|}f(x)f(x^{\prime})\bigr{|}=|xx^{\prime}|$ for any
$x,x^{\prime}\in X$. A bijective isometric mapping is called _an isometry_.

######  Problem 2.5.

Show that each isometry is a homeomorphism, in particular, each isometric
mapping from one metric space into another one is an embedding, i.e., we
recall, it is a homeomorphism with its image.

######  Problem 2.6.

Verify that the identity map, the composition of isometries, and the inverse
mapping to an isometry are also isometries, i.e., the set of all isometries of
an arbitrary metric space forms a group.

######  Definition 2.4.

The set of all isometries $f\colon X\to X$ of the metric space $X$ endowed
with the composition operation is called _the isometry group of the space $X$_
and is denoted by $\operatorname{Iso}(X)$.

######  Problem 2.7.

Let $X$ be an arbitrary metric space, $x,y\in X$ and $A\subset X$ be nonempty.
Prove that $|Ax|+|xy|\geq|Ay|$, so that the function $\rho_{A}(x)=|Ax|$ is
$1$-Lipschitz and, therefore, uniformly continuous.

###  2.3 Standard constructions of metrics

This section provides examples of standard constructions that build various
metric spaces.

######  Construction 2.1 (Multiplying a metric by a number).

If $d$ is a distance function on the set $X$, then for each real $\lambda>0$
the function $\lambda\,d$ is also a distance on $X$; moreover, if $d$ was a
metric (pseudometric), then $\lambda\,d$ is the distance of the same type. The
corresponding space will be denoted by $\lambda\,X$.

######  Construction 2.2 (Adding a constant).

Let $d$ be the distance function on $X$. We define an analogue of the
Kronecker symbols for $x,y\in X$ by setting $\delta_{xy}=0$ for any $x\neq y$,
and $\delta_{xx}=1$ for any $x$. Then for every real $c\geq 0$ the function
$(d+c)(x,y)=d(x,y)+c\,(1-\delta_{xy})$ is a distance. Moreover, if $d$ is a
pseudometric (metric) and $c>0$, then $d+c$ is a metric. Note that this
construction can also be extended to some negative numbers $c$.

######  Problem 2.8.

Let $d$ be a metric. Find the least possible $c$ such that $d+c$ is a
pseudometric. Verify that for such $c$ and any $c^{\prime}>c$ the function
$d+c^{\prime}$ is a metric.

######  Construction 2.3 (Induced distance).

In fact, we have already implicitly used this obvious construction. Let $d$ be
a distance function on the set $X$, and $Y$ be a nonempty subset of $X$. We
define a distance function on $Y$ by setting $|yy^{\prime}|=d(y,y^{\prime})$
for any $y,y^{\prime}\in Y$, and call it _induced from $d$_ or _the
restriction of $d$ to $Y$_. Note that the restriction of a metric
(pseudometric) is always a metric (pseudometric). To emphasize that $Y$ is
equipped with the induce metric, we call such $Y$ _a subspace of $X$_.
However, in what follows, each subset of a metric space will be considered as
a subspace, unless otherwise stated.

######  Construction 2.4 (Product).

Let $\\{X_{i}\\}_{i\in I}$ be some family of sets, and $d_{i}$ be a distance
function on $X_{i}$. We call each $X_{i}$ equipped with $d_{i}$ _a space_. We
set $X=\prod_{i\in I}X_{i}$, and for any $x,x^{\prime}\in X$ we consider the
function $d_{I}(x,x^{\prime})\colon I\to\mathbb{R}$,
$d_{I}(x,x^{\prime})(i)=d_{i}\bigl{(}x_{i},x^{\prime}_{i}\bigr{)}$. Put

$D_{I}=\cup_{x,x^{\prime}\in X}\\{d_{I}(x,x^{\prime})\\},$

and let $\mathcal{V}_{I}\supset D_{I}$ be some linear subspace of the linear
space $\mathcal{F}_{I}$ consisting of all real-valued functions defined on the
set $I$, and $\mathcal{V}_{I}^{+}\subset\mathcal{V}_{I}$ consists of all
functions with non-negative values. We call the subset
$\mathcal{V}_{+}\subset\mathcal{V}$ by _the first orthant of $\mathcal{V}$_.
Denote by $0\in\mathcal{F}_{I}$ the zero function: $0(i)=0$ for any $i\in I$.
Let $\rho\colon\mathcal{V}_{I}^{+}\to[0,\infty)$ be an arbitrary function such
that $\rho(0)=0$. This function $\rho$ generates a distance function
$d_{\rho}$ on $X$:
$d_{\rho}(x,x^{\prime})=\rho\bigl{(}d_{I}(x,x^{\prime})\bigr{)}$. The function
$\rho$ is sometimes called _a binder_ , and the function $d_{\rho}$ is called
_the distance generated by $\rho$_; the space $X$ with the distance function
$d_{\rho}$ is called _the semidirect product of the spaces $X_{i}$ w.r.t.
$\rho$_. Below we will show a few examples in which all $d_{i}$ are metrics,
and the resulting $d_{\rho}$ is a metric as well.

######  Example 2.5.

Consider the standard partial ordering on the first orthant $\mathcal{V}_{+}$
of $\mathcal{V}$: $v\leq w$ if and only if $v(i)\leq w(i)$ for all $i\in I$.

We call the function $\rho$ from Construction 2.4

  * •

_positively definite_ if it vanishes only at the origin;

  * •

_subadditive_ if for any $v,w\in\mathcal{V}_{+}$ it holds
$\rho(v+w)\leq\rho(v)+\rho(w)$;

  * •

_monotone_ if it is monotone w.r.t. the standard partial order described
above.

######  Proposition 2.6.

Under notations of Construction 2.4, let all $X_{i}$ be metric spaces, and
$\rho$ be positively definite, subadditive and monotone. Then the distance
function $d_{\rho}$ on $\prod_{i\in I}X_{i}$ is a metric.

###### Proof.

Positive definiteness of $d_{\rho}$ follows from the one of metrics and of the
function $\rho$. It remains to verify the triangle inequality. Take arbitrary
$x,x^{\prime},x^{\prime\prime}\in X$, then

$d_{\rho}(x,x^{\prime\prime})=\rho\bigl{(}d_{I}(x,x^{\prime\prime})\bigr{)}\leq\rho\bigl{(}d_{I}(x,x^{\prime})+d_{I}(x^{\prime},x^{\prime\prime})\bigr{)}\leq\rho\bigl{(}d_{I}(x,x^{\prime})\bigr{)}+\rho\bigl{(}d_{I}(x^{\prime},x^{\prime\prime})\bigr{)}=d_{\rho}(x,x^{\prime})+d_{\rho}(x^{\prime},x^{\prime\prime}).$

Here the first inequality follows from monotonicity of $\rho$ and triangle
inequalities for metrics, and the second one from subadditivity of $\rho$. ∎

######  Example 2.7.

Let $I$ be a finite set, say, $I=\\{1,\ldots,n\\}$, and
$\mathcal{V}_{I}=\mathcal{F}_{I}=\mathbb{R}^{n}$. For $\rho$ we choose the
corresponding restriction of one of the following standard norms on
$\mathcal{V}_{I}$:

$\bigl{\|}(v_{1},\ldots,v_{n})\bigr{\|}_{p}=\sqrt[p]{\sum_{i=1}^{n}|v_{i}|^{p}}\
\ \text{for $1\leq p<\infty$\ \ and}\ \
\bigl{\|}(v_{1},\ldots,v_{n})\bigr{\|}_{\infty}=\max\bigl{\\{}|v_{i}|:i=1,\ldots,n\bigr{\\}}.$

Then the distance function $d_{\rho}$ is a metric because $\rho$ is positively
definite, subadditive and monotone (verify), thus we can apply Proposition
2.6. For $p=2$ (when the norm is Euclidean) we get _the direct product_ of the
spaces $X_{i}$.

######  Example 2.8.

On the first orthant $\mathbb{R}^{2}_{+}$ of the plane $\mathbb{R}^{2}$ with
coordinates $(x,y)$ consider the following function $\rho(x,y)=x+\sqrt{y}$.
This function is obviously positively definite and monotonic. To prove it is
subadditive, make the following calculation:

$\rho(x+x^{\prime},y+y^{\prime})=x+x^{\prime}+\sqrt{y+y^{\prime}}\leq
x+\sqrt{y}+x^{\prime}+\sqrt{y^{\prime}}=\rho(x,y)+\rho(x^{\prime},y^{\prime}).$

Let $X_{1}=X_{2}=\mathbb{R}$, then, by Proposition 2.6, the distance function
$d_{\rho}$ is a metric. In explicit form

$d_{\rho}\bigl{(}(x,y),(x^{\prime},y^{\prime})\bigr{)}=|x-x^{\prime}|+\sqrt{|y-y^{\prime}|}.$

######  Example 2.9.

Let $I$ be an arbitrary set, and the family $\\{X_{i}\\}_{i\in I}$ consists of
spaces with diameters bounded by the same constant, i.e., the set of numbers
$\\{\operatorname{diam}X_{i}\\}_{i\in I}$ is bounded. Then, for $\mathcal{V}$,
we can choose the linear space of all bounded functions $v\colon
I\to\mathbb{R}$, and for $\rho$ we can choose the norm
$\|v\|_{\infty}=\sup_{i\in I}\Bigl{\\{}\bigl{|}v(i)\bigr{|}\Bigr{\\}}$. If all
$X_{i}$ are metric spaces, then $d_{\rho}$ is a metric.

The previous construction can be generalized if we consider not all the
Cartesian product $X=\prod_{i\in I}X_{i}$, but only a part of it extracted by
some condition.

######  Example 2.10.

We choose the set of natural numbers ${\mathbb{N}}$ as $I$, and the real line
$\mathbb{R}$ as $X_{i}$, then each element of $\prod_{i\in{\mathbb{N}}}X_{i}$
can be represented as a sequence $(x_{1},x_{2},\ldots)$, where $x_{i}\in
X_{i}=\mathbb{R}$.

Consider a subset $\ell_{p}\subset\prod_{i\in{\mathbb{N}}}X_{i}$ consisting of
all sequences $x=(x_{1},x_{2},\ldots)$ for which

$\|x\|_{p}:=\begin{cases}\sqrt[p]{\sum_{i=1}^{\infty}|x_{i}|^{p}}&\text{for
$1\leq p<\infty$, and}\\\
\sup\bigl{\\{}|x_{i}|:i\in{\mathbb{N}}\bigr{\\}}&\text{for
$p=\infty$}\end{cases}$

is finite. Then $\|\cdot\|_{p}$ is a norm on $\ell_{p}$. The resulting metric
space is denoted by $\ell_{p}$. In particular, the space $\ell_{\infty}$
consists of all bounded sequences.

######  Example 2.11.

We choose an arbitrary set of indices $I$, and consider $I$ as topological
space with discrete topology. We put all $X_{i}$ equal to $\mathbb{R}$, and as
a subset of $\prod_{i\in I}X_{i}$ we take the family $\operatorname{Fin}_{I}$
of all maps $x\colon I\to\mathbb{R}$ with compact support, i.e., such that
$x(i)\neq 0$ only for a finite number of indices $i$. It is clear that
$\operatorname{Fin}_{I}$ forms a linear space, and each function

$\|x\|_{p}=\sqrt[p]{\sum_{i\in I}|x_{i}|^{p}}\ \ \text{for $1\leq
p<\infty$\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ and}\
\ \|x\|_{\infty}=\max_{i\in I}\bigl{\\{}|x_{i}|\bigr{\\}}$

is a norm on the space $\operatorname{Fin}_{I}$. If all $X_{i}$ are metric
space, and $\rho$ is a norm described above, then $d_{\rho}$ is a metric.

######  Construction 2.5 (Levenshtein distance).

Let $A$ be some set, and $A^{*}$ be the family of all finite sequences of
elements from $A$, as well as an empty sequence $\lambda$. We will interpret
$A$ as _an alphabet_ of some language. Then elements from $A$ are naturally
called _letters_ , and the elements from $A^{*}$ are _words_. _An editorial
operation on $A^{*}$_ is a word transformation consisting either in the
exclusion of one of the letters from the word (_deletion_), or in the
insertion of a letter into the word (_insertion_), or in replacing one letter
with another one (_substitution_). The smallest number of editorial operations
needed to move from one word to another is called _the Levenshtein distance_
and generates a metric on $A^{*}$. This distance plays an important role in
linguistics and bioinformatics.

Now we need to recall the notion of graph. We consider more general graphs
permitting infinite numbers of vertices and edges.

####  2.3.1 Elements of graph theory, and metric constructions for graphs

Consider a triple $G=(V,E,i)$, where $V$ and $E$ are arbitrary sets, and
$i\colon E\to\mathcal{F}_{2}(V)$ a mapping to the set of all at most $2$-point
nonempty subsets of $V$, see Section 1.12. The set $V$ is also denoted by
$V(G)$ and called _the set of vertices_ ; the set $E$ is also denoted by
$E(G)$ and called _the set of edges_ ; the mapping $i\colon
E\to\mathcal{F}_{2}(V)$ is also denoted by $i_{G}$ and called _the incidence
mapping_ , and it defines how edges are glued to vertices; the triple $G$ is
called _a non-oriented graph_. An edge $e$ is called _a loop_ , if
$\\#i(e)=1$. The number $\\#i^{-1}\bigl{(}i(e)\bigr{)}$ is called
_multiplicity of the edge $e$_. An edge $e$ is called _multiple_ , if its
multiplicity is more that $1$. Graph without loops and multiple edges is
called _simple_. In a simple graph each edge $e$ can be considered as the pair
$\\{v,w\\}=i(e)$ of different vertices $v$ and $w$, that is why we can reduce
the definition by setting $G=(V,E)$, where $E$ is a subset of $V^{(2)}$, where
$V^{(2)}$ is the set of all 2-point subsets of $V$. _A subgraph $H$ of the
graph $G$_ is a triple $(V^{\prime},E^{\prime},i^{\prime})$ such that
$V^{\prime}\subset V$, $E^{\prime}\subset E$, and
$i^{\prime}=i|_{E^{\prime}}$.

If instead $\mathcal{F}_{2}(V)$ we consider $V\times V$, then we obtain
definition of _an oriented graph_.

Let $G=(V,E,i)$ be an arbitrary non-oriented graph. For each edge $e\in E$ and
each vertex $v\in i(e)$ we say that $e$ and $v$ are _incident_ ; if
$i(e)=\\{v,w\\}$, the vertices $v$ and $w$ are called _adjacent_ , and we say
that $e$ _joins $v$ and $w$_; if $i(e)=\\{v\\}$, we say that $v$ is _adjacent
to itself_ , that $e$ _joins $v$ with $v$_. The number of non-loop edges plus
the double number of loops, incident to a vertex $v\in V$, is called _the
degree of $v$_ and is denoted by $\deg v$ or $\deg_{G}v$.

_A walk of length $n$ joining some vertices $v$ and $w$_ is a sequence
$v=v_{0},\,e_{1},\,v_{1},\,e_{2},\ldots,e_{n},\,v_{n}=w$ of alternating
vertices and edges such that each edge $e_{k}$ joins $v_{k-1}$ and $v_{k}$. If
$G$ is a simple graph, we do not need to indicate the edges since each pair of
adjacent vertices defines uniquely the edge incident to these vertices. The
walt is called _closed_ if $v_{0}=v_{n}$, and it is called _open_ otherwise.
_A trail_ is a walk with no repeated edges. _A path_ is an open trail with no
repeated vertices. _A circuit_ is a closed trail. _A cycle_ is a circuit with
no repeated vertices.

In the case of an oriented graph $G$, if $i(e)=(v,w)$, then we say that _$e$
starts at $v$ and ends at $w$_. We redefine the walk just demanding that each
$e_{k}$ starts at $v_{k-1}$ and ends at $v_{k}$. All other definitions remain
the same.

A graph $G$ is called _connected_ , if each pair of its vertices are joined by
a walk. A graph without cycles is called _a forest_ , and a connected forest
is called _a tree_. Clearly that each forest is a simple graph.

_A weighted graph_ is a graph $G=(V,E,i)$ equipped with _a weight function
$\omega\colon E\to[0,\infty)$_ (sometimes it is useful to consider more
general weight functions, for instance, with possibility of negative values).
Sometimes we denote the weighted graph as $(V,E,i,\omega)$ or $(G,\omega)$,
and, in the case of simple graph $G$, by $(V,E,\omega)$. _The weight of a
subgraph_ of a weighted graph is the sum of the weights of edges from this
subgraph. We can extend this definition to paths and cycles considering them
as subgraphs of $G$. In the case of the walk, its weight is defined as the sum
of weights of its consecutive edges. For graphs without weight functions these
notions are defined as well by assigning the weight $1$ to each edge by
default.

######  Construction 2.6 (Distance on a connected graph).

Let $\Gamma=(V,E,i)$ be a connected graph. We define a distance function on
$V$, setting it equal to the infimum of length of walks joining a given pair
of vertices (we can always change the walks to paths with the same result).
This function is a metric on $V$ (verify).

######  Construction 2.7 (Distance on a connected weighted graph).

If $\Gamma=(V,E,i,\omega)$ is a weighted connected graph with the weight
function $\omega\colon E\to[0,\infty)$, then we define the distance function
by setting it equal to the infimum of the weights of all walks (or paths)
joining a given pair of vertices. The resulting function is a pseudometric on
$V$. Note that even if $\omega$ is everywhere positive, the constructed
distance function does not have to be a metric (consider a graph with a
positive weight function in which some pair of vertices are connected by an
infinite number of paths with weights tending to zero).

######  Construction 2.8 (Cayley graph of a group).

Let $G$ be an arbitrary group with a set $S$ of generators. _The Cayley graph
of the pair $(G,S)$_ is the directed graph $\Gamma(G,S)=(G,E,i)$, in which
$(g,h)=i(e)$ for some $e\in E$ if and only if $h=gs$ for some $s\in S$.

We note that in geometric group theory the set $S$ usually satisfies the
following properties: the neutral element is not contained in $S$, and
$S=S^{-1}$, i.e., if $s\in S$, then $s^{-1}\in S$. In this case, the graph
$\Gamma(G,S)$ has no loops, and if $(g,h)=i(e)$ for some $e\in E$, then
$(h,g)=i(e^{\prime})$ for some $e^{\prime}\in E$, since $h=gs$ implies
$g=hs^{-1}$. Under these assumptions, by Cayley graph we mean a simple non-
oriented graph in which each pair of mutually opposite oriented edges were
replaced by one (non-oriented) edge. For such Cayley graph, Construction 2.6
defines a metric on $G$, which is used to determine the growth rate of the
group $G$.

######  Remark 2.12.

In what follows, we will always consider only those $S$ that satisfies the
both conditions: $S=S^{-1}$ and $S$ does not contain the neutral element of
$G$. However, we will not list in $S$ all inverses of its elements supposing
that this holds by default.

######  Problem 2.9.

Describe the Cayley graphs for the following groups $G$ and generating sets
$S$:

  1. (1)

$G={\mathbb{Z}}$ and $S=\\{1\\}$;

  2. (2)

$G={\mathbb{Z}}_{m}$ and $S=\\{1\\}$;

  3. (3)

$G={\mathbb{Z}}^{2}$ and $S=\bigl{\\{}(1,0)\,(0,1)\bigr{\\}}$;

  4. (4)

$G={\mathbb{Z}}^{2}$ and $S=\bigl{\\{}(1,0)\,(0,1),\,(1,1)\bigr{\\}}$;

  5. (5)

$G$ is a free group with generators $a$ and $b$.

######  Construction 2.9 (Quotient spaces).

Let $(X,\rho)$ be a metric (pseudometric) space, and $\sim$ an equivalence
relation on $X$. Define the following _quotient distance function_ on $X$:

$\rho_{\sim}(x,y)=\inf\Bigl{\\{}\sum_{i=0}^{n}\rho(p_{i},q_{i}):p_{0}=x,\,q_{n}=y,\,n\in{\mathbb{N}},\,q_{i}\sim
p_{i+1}\ \text{for all $i$}\Bigr{\\}}.$

The terms in the right-hand side can be naturally visualized as
$p_{0}-q_{0}\sim p_{1}-q_{1}\sim\cdots\sim p_{n}-q_{n}$, where $p_{i}-q_{i}$
indicates that we calculate the distance between $p_{i}$ and $q_{i}$, and
$q_{i}\sim p_{i+1}$ says that these points are taken from the same equivalency
class, and thus the distance between them is zero. We call such sequences
$p_{0}-q_{0}\sim p_{1}-q_{1}\sim\cdots\sim p_{n}-q_{n}$ an _admissible_ one
joining the classes $[x]$ and $[y]$, and the value
$\sum_{i=0}^{n}\rho(p_{i},q_{i})$ _the weight of this admissible sequence_.

######  Problem 2.10.

Prove that $\rho_{\sim}$ is a pseudometric on $X$.

Now, let $x\sim y$, then we can put $p_{0}=x=q_{0}$ and $p_{1}=q_{1}=y$, so
$\rho_{\sim}(x,y)\leq\rho(x,x)+\rho(y,y)=0$, thus $\rho_{\sim}(x,y)=0$.
Therefore, each equivalence class of $\sim$ consists of points on
$\rho_{\sim}$-zero distance from each other, thus $\rho_{\sim}$ generates
correctly a pseudometric on $X/\\!\\!\sim$ which we also denote by
$\rho_{\sim}$ and call in _the quotient pseudometric w.r.t. $\sim$_; the space
$X/\\!\\!\sim$ we will call the _the quotient pseudometric space w.r.t.
$\sim$_. The next step is to consider the space $X/\rho_{\sim}$ instead of the
$X/\\!\\!\sim$: these two spaces are different when the distance between some
distinct classes of $\sim$ vanishes. As above, we denote by the same
$\rho_{\sim}$ the corresponding metric on $X/\rho_{\sim}$, and the
$\rho_{\sim}$ and $X/\rho_{\sim}$ we call _the quotient metric space and the
quotient metric space w.r.t. $\sim$_, respectively.

To work effectively with the $\rho_{\sim}$, let us define the following
notions. The admissible sequence $p_{0}-q_{0}\sim p_{1}-q_{1}\sim\cdots\sim
p_{n}-q_{n}$ from definition of $\rho_{\sim}$ is called _reducible_ if it is
possible to delete a part of it in such a way that its ends remains to belong
to the classes $[x],[y]\in X/\\!\\!\sim$, and its weight did not increase.
Otherwise, its is called _irreducible_. It is evident that to calculate the
distance $\rho_{\sim}$, it is sufficient to consider irreducible admissible
sequences only. If $a$ and $b$ not equivalent, then we write it as $a\not\sim
b$.

######  Problem 2.11.

Let $\xi=(p_{0}-q_{0}\sim p_{1}-q_{1}\sim\cdots\sim p_{n}-q_{n})$ be an
irreducible admissible sequence. Prove that

  1. (1)

for any $i<j$ we have $p_{i}\not\sim p_{j}$, $q_{i}\not\sim q_{j}$;

  2. (2)

$q_{i}\sim p_{j}$ if and only if $j=i+1$;

  3. (3)

for any $i$ we have $q_{i}\not=p_{i+1}$.

######  Example 2.13.

Let us show how Problem 2.11 can be applied. Let $X=[0,a]\subset\mathbb{R}$ be
a segment of real line. Identify its ends. This means, that $x,y\in X$ are
equivalent if and only if either $x=y$, or $\\{x,y\\}=\\{0,a\\}$. Describe all
irreducible admissible sequences $\xi$. The are two possibilities (verify):

  1. (1)

$\xi$ consists of two different points, say $x$ and $y$, and its weight equals
$|xy|$;

  2. (2)

$\xi$ consists of $4$ points, its ends are distinct from $0$ and $a$, but the
middle points are these $0$ and $a$; w.l.o.g., $\xi=(x-0\sim a-y)$, thus its
weight equals $|0x|+|ya|$.

Thus, on the topological circle $[0,a]/\sim$ we introduce the distance in the
same way as we do for the standard circle when we choose the length of the
shortest arc between the points.

######  Problem 2.12.

Let $\sim$ be the trivial equivalence on a metric space $(X,\rho)$, i.e.,
$x\sim y$ if and only if $x=y$. Prove that $\rho_{\sim}=\rho$.

######  Problem 2.13.

Let $\sim$ be an equivalence on a pseudometric space $(X,\rho)$. Prove that
for any $x,y\in X$ it holds $\rho_{\sim}(x,y)\leq\rho(x,y)$. Thus, if we
define the function $b\colon X\to X\to\mathbb{R}$ such that $b(x,y)=0$ for
$x\sim y$, and $b(x,y)=\rho(x,y)$ otherwise, then $\rho_{\sim}\leq b$.

######  Construction 2.10 (Generalization of distance).

It is useful to allow infinite distances. A function $\rho\colon X\times
X\to[0,\infty]$ that satisfies the axioms of distance (pseudometric, metric)
will be called _generalized_ one. The corresponding spaces $X$ with such
distances we call _generalized_ as well.

######  Remark 2.14.

In some monographs the authors work with generalized distances from the very
beginning and because of that they call such distances without the word
“generalized”. However, the distances with values in $[0,\infty)$ they call
_finite_ ones.

The generalization of distance gives rise more metric constructions.

######  Construction 2.11 (Disjoint union of spaces).

Let $\bigl{\\{}(X_{i},\rho_{i})\bigr{\\}}_{i\in I}$ be an arbitrary family of
generalized spaces. Consider on $\sqcup_{i\in I}X_{i}$ the distance function
that is equal to $\rho_{i}$ on $X_{i}$, and to $\infty$ for any pair of points
from different $i$. The resulting space is called _the disjoint union of
spaces $X_{i}$_.

Evidently, if $X_{i}$ are generalized pseudometric (metric) spaces, then
$\sqcup_{i\in I}X_{i}$ is the space of the same type.

Let $X$ be a generalized pseudometric space. So, we can define two equivalence
relations: $x\mathop{\sim}\nolimits_{1}y$ if and only if $|xy|<\infty$; and
$x\mathop{\sim}\nolimits_{2}y$ if and only if $|xy|=0$.

######  Problem 2.14.

Prove that each class of equivalence $\mathop{\sim}\nolimits_{1}$ is a
pseudometric space (with finite distance), and that the distance between
points from different classes equals $\infty$. Thus, if we denote by $X_{i}$
the classes of equivalence $\mathop{\sim}\nolimits_{1}$, then $X=\sqcup
X_{i}$. Prove that the space $X/\\!\\!\mathop{\sim}\nolimits_{2}$ equals the
disjoint union $\sqcup(X_{i}/\\!\\!\mathop{\sim}\nolimits_{2})$ of metric
spaces $X_{i}/\\!\\!\mathop{\sim}\nolimits_{2}$.

Now we combine disjoint union and quotient operation.

######  Example 2.15.

Let $X$ and $Y$ be metric spaces, $Z\subset X$, and $f\colon Z\to Y$ a
mapping. Consider on $X\sqcup Y$ with generalized metric $\rho$ the
equivalence relation $\sim$ which identifies each $a\in f(Z)$ with all $b\in
f^{-1}(a)$. The quotient space $X\sqcup_{f}Y:=(X\sqcup Y)/\rho_{\sim}$ is
called the result of _gluing the spaces $X$ and $Y$ over the mapping $f$_.

######  Problem 2.15.

Suppose that $f$ is isometric. Prove that the restrictions of $\rho_{\sim}$ to
$X$ and $Y$ coincides with the initial metrics of $X$ and $Y$, respectively.

######  Problem 2.16.

Let $y_{0}\in Y$ and $f(X)=y_{0}$. Prove that $X\sqcup_{f}Y$ is isometric to
$Y$.

######  Construction 2.12 (Maximal pseudometric).

Consider an arbitrary function $b\colon X\times X\to[0,\infty]$, and denote by
$\mathcal{D}_{b}$ the set of all generalized pseudometrics $d\colon X\times
X\to[0,\infty]$ such that $d(x,y)\leq b(x,y)$ for any $x,y\in X$.

######  Lemma 2.16.

There exists and unique $d_{b}\in\mathcal{D}_{b}$ such that $d_{b}\geq d$ for
all $d\in\mathcal{D}_{b}$.

###### Proof.

We put $d_{b}(x,y)=\sup_{d\in\mathcal{D}_{b}}d(x,y)$. It is evident that
$d_{b}$ is nonnegative, symmetric, $d_{b}(x,x)=0$ for all $x\in X$, and
$d_{b}\leq b$. It remains to verify the triangle inequality:

$d_{b}(x,z)=\sup_{d\in\mathcal{D}_{b}}d(x,z)\leq\sup_{d\in\mathcal{D}_{b}}\bigl{(}d(x,y)+d(y,z)\bigr{)}\leq\sup_{d\in\mathcal{D}_{b}}d(x,y)+\sup_{d\in\mathcal{D}_{b}}d(y,z)=d_{b}(x,y)+d_{b}(y,z).$

The uniqueness of $d_{b}$ is evident. ∎

We denote $d_{b}$ by $\sup\mathcal{D}_{b}$ and call it _maximal pseudometric
w.r.t. the function $b$_.

######  Theorem 2.17.

Let $(X,\rho)$ be a pseudometric space, and $\sim$ an equivalence relation. We
put

$b(x,y):=b_{\sim}(x,y)=\begin{cases}0,&\text{if $x\sim y$},\\\
\rho(x,y),&\text{otherwise}.\end{cases}$

Then $d_{b}=\sup\mathcal{D}_{b}=\rho_{\sim}$, thus $X/\rho_{\sim}=X/d_{b}$.

###### Proof.

By Problem 2.13, we have $\rho_{\sim}\leq b$, thus
$\rho_{\sim}\in\mathcal{D}_{b}$. It remains to prove that $\rho_{\sim}\geq d$
for each $d\in\mathcal{D}_{b}$. To do that, we write down

$\rho_{\sim}(x,y)=\inf\Bigl{\\{}\sum_{i=0}^{n}\rho(p_{i},q_{i}):p_{0}=x,\,q_{n}=y,\,n\in{\mathbb{N}},\,q_{i}\sim
p_{i+1}\ \text{for all $i$}\Bigr{\\}}\geq\\\
\geq\inf\Bigl{\\{}d(p_{0},q_{0})+d(q_{0},p_{1})+\cdots+d(q_{n-1},p_{n})+d(p_{n},q_{n}):n\in{\mathbb{N}},\,q_{i}\sim
p_{i+1}\ \text{for all $i$}\Bigr{\\}}\geq d(x,y).$

∎

Now we apply the quotation technique to obtain a few more important classes of
metric spaces.

######  Construction 2.13 (Groups actions).

Let $X$ be a metric space and $G\subset\operatorname{Iso}(X)$ a subgroup of
its isometry group. Consider the action of $G$ on $X$, i.e., the mapping
$\varphi\colon G\times X\to X$ such that $\varphi(g,x)=:g(x)$ satisfies the
following conditions:

  1. (1)

$e(x)=x$ for the neutral element $e\in G$ and any $x\in X$;

  2. (2)

$(hg)(x)=h\bigl{(}g(x)\bigr{)}$ for any $g,h\in G$ and $x\in X$.

Consider the following equivalence relation on $X$: $x\sim y$ if and only if
$g(x)=y$ for some $g\in G$. We say that the equivalence $\sim$ _is generated
by the action of $G$ on $X$_. The corresponding quotient space $X/\\!\\!\sim$
is usually denoted by $X/G$. The sets $G(x)$ are called _orbits_ , they are
elements of $X/G$; the set $X/G$ is called _the orbit-space_.

######  Problem 2.17.

Let $X$ be a metric space and $G\subset\operatorname{Iso}(X)$ a subgroup of
its isometry group. For each two elements $G(x),G(y)\in X/G$ we set
$d\bigl{(}G(x),G(y)\bigr{)}=\inf\bigl{\\{}|x^{\prime}y^{\prime}|:x^{\prime}\in
G(x),\,y^{\prime}\in G(y)\bigr{\\}}$. Prove that $d=\rho_{\sim}$, where the
equivalence $\sim$ is generated by the action of $G$ on $X$.

######  Problem 2.18.

Let $S^{1}$ be the standard unit circle in the Euclidean plane. As a distance
between $x,y\in S^{1}$ we take the length of the shortest arc of $S_{1}$
between $x$ and $y$. By _the standard torus_ we mean the direct product
$T^{2}=S^{1}\times S^{1}$ (with the Euclidean binder). We describe the points
on the both $S^{1}$ by their polar angles $\varphi_{1}$ and $\varphi_{2}$,
defined up to $2\pi$. So, _the shifts_
$s_{a,b}\colon(\varphi_{1},\varphi_{2})\mapsto(\varphi_{1}+a,\varphi_{2}+b)$
are isometries of $T^{2}$. Fix some $(a,b)\in\mathbb{R}^{2}$ and consider a
subgroup $G_{a,b}\subset\operatorname{Iso}(T^{2})$ consisting of all shifts
$s_{ta,tb}$, $t\in\mathbb{R}$. For different $a$ and $b$, find the
corresponding pseudometric and metric quotient spaces.

######  Construction 2.14 (Metrized graphs).

Take an arbitrary collection of segments
$\bigl{\\{}[a_{k},b_{k}]\bigr{\\}}_{k\in K}$, and on the set
$\sqcup\\{a_{k},b_{k}\\}$ consider an equivalence $\sim$. The generalized
pseudometric metric space $\bigl{(}\sqcup[a_{k},b_{k}]\bigr{)}/\sim$ is called
a _metrized graph_. To obtained its combinatorial structure, we represent it
as we did before, namely, as a triple $G=(V,E,i)$. To do that, we put
$V:=\bigl{(}\sqcup\\{a_{k},b_{k}\\}\bigr{)}/\sim$,
$E:=\bigl{\\{}[a_{k},b_{k}]\bigr{\\}}_{k\in K}$, and
$\pi\colon\sqcup\\{a_{k},b_{k}\\}\to\bigl{(}\sqcup\\{a_{k},b_{k}\\}\bigr{)}/\sim$
be the canonical projection, then
$i\bigl{(}[a_{i},b_{i}]\bigr{)}:=\pi\bigl{(}\\{a_{i},b_{i}\\}\bigr{)}$.

######  Construction 2.15 (Polyhedral spaces).

By _a polyhedron of dimension $n$_ we mean an intersection of a finite number
of half-spaces in $\mathbb{R}^{n}$ that has nonempty interior. For each point
$x$ of a polyhedron $W$ we define its _dimension $\dim_{W}x$_ as follows:
consider all affine subspaces $L$ containing $x$ such that $x$ is an interior
point of $W\cap L$, and put $\dim_{W}x$ to be the maximal dimension of such
$L$. Denote by $W^{k}$ the subset in $W$ consisting of all points of dimension
$k$. One can show that $W^{k}$ consists of connected component each of which
belongs of an affine subspace $L$ of dimension $k$. The closures of these
connected components are called _the faces of $W$ of dimension $k$_.

Now, consider an arbitrary collection $\\{W_{k}\\}_{k\in K}$ of polyhedra
(probably, of different dimensions), and for some pairs $(W_{k},W_{l})$,
$k\neq l$, choose some faces $F_{k}^{p}\subset W_{k}$ and $F_{l}^{q}\subset
W_{l}$ such that there exists an isometry $\varphi\colon F_{k}^{p}\to
F_{l}^{q}$. Consider the generalized metric space $\sqcup_{k\in K}W_{k}$ and
the equivalence relation generated by the isometries $\varphi$: we put in one
class each point $x\in F_{k}^{p}$ and $\varphi(x)\in F_{l}^{q}$, for all
isometries $\varphi$ (we glue the faces by the isometry $\varphi$). The
resulting quotient generalized space is called _a polyhedron space_.

######  Problem 2.19.

Represent the standard torus from Problem 2.18 as a polyhedron space.

######  Problem 2.20.

Verify that the above constructions actually, as declared, define
(pseudo-)metrics.

A huge collection of metric spaces can be found in [1].

###  2.4 Convergence and completeness

Since each metric space is Hausdorff, the following result holds.

######  Proposition 2.18.

If a sequence converges in a metric space, then its limit is uniquely
determined.

A sequence $x_{1},\,x_{2},\ldots$ of points of a metric space $X$ is called
_fundamental_ if for any $\varepsilon>0$ there exists $N$ such that for all
$m,\ n\geq N$ the inequality $|x_{m}x_{n}|<\varepsilon$ holds. If every
fundamental sequence in a metric space $X$ is convergent, then such $X$ is
called _complete_.

######  Problem 2.21.

Show that a subspace of a complete metric space is complete if and only if it
is closed.

######  Theorem 2.19.

Each metric space $X$ is an everywhere dense subspace of some complete space
called a completion of $X$. The completion of the space $X$ is uniquely
defined: for any two completions $X^{\prime}\supset X$ and
$X^{\prime\prime}\supset X$ there is an isometry $f\colon X^{\prime}\to
X^{\prime\prime}$ that is identical on $X$.

######  Construction 2.16 (Completion).

The standard construction of completion of a metric space $X$ is as follows:

  * •

the set $W$ of all fundamental sequences in the space $X$ is considered;

  * •

on $W$, a pseudometric is set equal to the limit of the distances between the
points of two fundamental sequences (the existence of the limit follows from
the fundamentality);

  * •

$X$ can be realized as a subset of $W$ by associating each point $x\in X$ with
the constant sequence $x,\,x,\ldots$.

  * •

the desired completion is obtained by factorization as in Problem 2.1.

The uniqueness of completion implies the following result.

######  Problem 2.22.

Let $X$ be an arbitrary subspace of a complete metric space. Then the closure
$\overline{X}$ of the set $X$ is a completion of the space $X$.

######  Problem 2.23.

Let $f\colon X\to Y$ be a bi-Lipschitz mapping of metric spaces. Prove that
$X$ is complete if and only of $Y$ is complete. Construct a homeomorphism of
metric spaces that does not preserves completeness.

######  Problem 2.24.

Show that a metric space is complete if and only if the following condition
holds: for any sequence of closed subsets $X_{1}\supset X_{2}\supset
X_{3}\supset\cdots$ such that $\operatorname{diam}X_{n}\to 0$ as $n\to 0$, the
intersection $\cap_{i=1}^{\infty}X_{i}$ is not empty (in fact, it consists of
unique element). Show that the condition $\operatorname{diam}X_{n}\to 0$ is
essential.

######  Problem 2.25 (Fixed-point theorem).

Let $f\colon X\to X$ be a $C$-Lipschitz mapping of a complete metric spaces
$X$. Prove that for $C<1$ there exists and unique a point $x_{0}$ such that
$f(x_{0})=x_{0}$ (it is called _the fixed point of the mapping $f$_).

###  2.5 Compactness and sequential compactness

Recall that a topological space is called _compact_ if a finite subcover can
be extracted from any of its open cover, and _sequentially compact_ if any
sequence of its points has a convergent subsequence. As noted in Section 1, in
the case of general topological spaces, compactness and sequential compactness
are different concepts. However, for metric spaces this is not so.

######  Theorem 2.20.

A metric space is compact if and only if it is sequentially compact.

###### Proof.

Let $X$ be a compact metric space and $x_{1},x_{2},\ldots$ be an arbitrary
sequence of points from $X$. We must show that there is a convergent
subsequence in this sequence.

Suppose this is not so, then

  * •

the sequence $x_{i}$ contains an infinite number of different points;

  * •

for each point $x\in U:=X\setminus\\{x_{1},\,x_{2},\ldots\\}$ there is an
(open) neighborhood $U^{x}$ that does not contain points of the sequence
$x_{i}$, therefore $U=\cup_{x\in U}U^{x}$ and, thus, $U$ is an open set;

  * •

for each $x_{i}$ there is a neighborhood $U^{x_{i}}$ for which
$U^{x_{i}}\cap\\{x_{1},\,x_{2},\ldots\\}=\\{x_{i}\\}$.

But then the family $\\{U,\,U^{x_{1}},\,U^{x_{2}},\ldots\\}$ is an open cover
of $X$ from which it is impossible to choose a finite subcover (each finite
subcover contains only finitely many points of the sequence $x_{i}$). The
obtained contradiction shows that $X$ is sequentially compact.

Now let the space $X$ be sequentially compact. Suppose that there exists an
open covering $\mathcal{U}=\\{U_{\alpha}\\}$ of the space $X$ that does not
contain finite subcovers. On $X$ we define a function $\rho\colon
X\to\mathbb{R}$ as follows:

$\rho(x)=\sup\\{r\in\mathbb{R}\mid\exists
U_{\alpha}\in\mathcal{U}:\operatorname{U}_{r}(x)\subset U_{a}\\}.$

This function is everywhere finite, since the sequentially compact space is
bounded, and everywhere positive by virtue of the definition of metric
topology.

######  Lemma 2.21.

The function $\rho$ defined above is $1$-Lipschitz and, therefore, continuous.

###### Proof.

Assume the contrary, i.e., that for some $x,\,y\in X$ the inequality
$|\rho(y)-\rho(x)|>|xy|$ holds. Without loss of generality, we assume that
$\rho(y)>\rho(x)$, then $\rho(y)>\rho(x)+|xy|$. Increase the number $\rho(x)$
a little to $\rho^{\prime}$ and slightly decrease the number $\rho(y)$ to
$\rho^{\prime\prime}$ so that $\rho^{\prime\prime}>\rho^{\prime}+|xy|$ is
still true, then

  * •

$U_{\rho^{\prime}}(x)\subset U_{\rho^{\prime\prime}}(y)$, because for an
arbitrary point $z\in U_{\rho^{\prime}}(x)$ we have

$|zy|\leq|zx|+|xy|<\rho^{\prime}+|xy|<\rho^{\prime\prime};$

  * •

there is $U_{\alpha}\in\mathcal{U}$ for which
$U_{\rho^{\prime\prime}}(y)\subset U_{\alpha}$.

But then $U_{\rho^{\prime}}(x)\subset U_{\alpha}$, therefore
$\rho(x)\geq\rho^{\prime}$ by the definition of the function $\rho$, a
contradiction. ∎

By virtue of Problem 1.53, the function $\rho$ achieves the smallest value
$\rho_{0}$, which is, therefore, strictly positive. Put $r=\rho_{0}/2$. Then
for each point $x\in X$ there exists $U_{\alpha}\in\mathcal{U}$ such that
$U_{r}(x)\subset U_{\alpha}$.

Choose an arbitrary point $x_{1}\in X$, and let $U_{1}\in\mathcal{U}$ be such
that $U_{r}(x_{1})\subset U_{1}$. There is $x_{2}\in X\setminus U_{1}$. Choose
$U_{2}\in\mathcal{U}$ such that $U_{r}(x_{2})\subset U_{2}$. In general, if
$x_{1},\ldots,x_{n}$ and $U_{1},\ldots,U_{n}$ are selected, then there is
$x_{n+1}\in X\setminus\cup_{i=1}^{n}U_{i}$ and $U_{n+1}\in\mathcal{U}$ such
that $U_{r}(x_{n+1})\subset U_{n+1}$. Since $\mathcal{U}$ does not have a
finite subcover, we construct an infinite sequence $x_{1},\,x_{2},\ldots$, and
it is clear that every point $x_{n+1}$ lies outside
$\cup_{i=1}^{n}U_{r}(x_{i})$, so for any $x_{i}$ and $x_{j}$, $i\neq j$, we
have $|x_{i}x_{j}|\geq r$. But such a sequence does not contain a convergent
subsequence, which contradicts the sequential compactness of $X$. ∎

######  Problem 2.26.

Give an example of a topological space that is

  1. (1)

compact, but not sequentially compact;

  2. (2)

sequentially compact, but not compact.

######  Problem 2.27 (Lebesgue’s lemma).

Let $X$ be a compact metric space. Prove the following statement: for any open
cover $\\{U_{i}\\}_{i\in I}$ of $X$ there exists $\rho>0$ such that for any
$x\in X$ one can find $U_{i}$ with $B_{\rho}(x)\subset U_{i}$.

######  Problem 2.28.

Show that each continuous mapping $f\colon X\to Y$ from a compact metric space
to an arbitrary metric space is uniformly continuous.

######  Problem 2.29.

Prove that the diameter $\operatorname{diam}X$ of a compact metric space $X$
if finite, and that there exist $x,y\in X$ such that
$\operatorname{diam}X=|xy|$.

####  2.5.1 Completeness and compactness

Theorem 2.20 easily yields the following result.

######  Corollary 2.22.

A compact metric space is complete.

###### Proof.

Let $X$ be a compact metric space. In the space $X$ we choose an arbitrary
fundamental sequence $x_{1},\,x_{2},\ldots$. By Theorem 2.20, there exists a
subsequence $x_{i_{1}},\,x_{i_{2}},\ldots$, converging to some point $x\in X$.
Due to fundamentality of $x_{1},\,x_{2},\ldots$, the whole this sequence
converges to $x$, therefore the space $X$ is complete. ∎

######  Definition 2.23.

For $\varepsilon>0$, a subset $S$ of a metric space $X$ is called _an
$\varepsilon$-net_ if for any point $x\in X$ there exists $s\in S$ such that
$|xs|<\varepsilon$. A metric space is called _totally bounded_ if for any
$\varepsilon>0$ there exists a finite $\varepsilon$-net in it.

######  Theorem 2.24.

A metric space is compact if and only if it is complete and totally bounded.

###### Proof.

Let $X$ be a compact metric space. Then, by virtue of Corollary 2.22, it is
complete. We choose an arbitrary $\varepsilon>0$, then
$\\{U_{\varepsilon}(x)\\}_{x\in X}$ is an open cover of $X$. Since $X$ is
compact, there exists a finite subcover
$\\{U_{\varepsilon}(x_{i})\\}_{i=1}^{n}$. But then $\\{x_{1},\ldots,x_{n}\\}$
is a finite $\varepsilon$-net. Thus, the space $X$ is totally bounded.

Now let $X$ be a complete and totally bounded metric space. We prove that $X$
is sequentially compact and apply Theorem 2.20. Consider an arbitrary sequence
$x_{i}$ in $X$. For each $n\in{\mathbb{N}}$, consider a finite $1/n$-net
$S_{n}$. The balls $\\{U_{1}(s)\\}_{s\in S_{1}}$ cover $X$, so there is a ball
$U_{1}$ among them that contains infinitely many elements of the sequence
$x_{i}$. The balls $\\{U_{1/2}(s)\\}_{s\in S_{2}}$ cover $U_{1}$, so there is
a ball $U_{2}$ among them for which $C_{2}=U_{1}\cap U_{2}$ contains
infinitely many $x_{i}$. If $U_{1},\,U_{2},\ldots,U_{k}$ are already selected
so that $C_{k}=\cap_{j=1}^{k}U_{j}$ contains infinitely many $x_{i}$, then the
family $\\{U_{1/(k+1)}(s)\\}_{s\in S_{k+1}}$, since it covers $C_{k}$,
contains a ball $U_{k+1}$ for which there are infinitely many $x_{i}$ in
$C_{k+1}=\cap_{j=1}^{k+1}U_{j}$.

Now, we choose an arbitrary $x_{i_{1}}\in C_{1}$. Since there are infinitely
many points of our sequence in $C_{2}$, there exists $i_{2}>i_{1}$ such that
$x_{i_{2}}\in C_{2}$. Continuing this process, we construct a subsequence
$x_{i_{1}},x_{i_{2}},\ldots$ such that $x_{i_{k}},x_{i_{k+1}},\ldots\in C_{k}$
for each $k$, and since $\operatorname{diam}C_{k}\to\emptyset$ as
$k\to\infty$, this subsequence is fundamental and, therefore, converges
because $X$ is complete. Thus, $X$ is sequentially compact. ∎

######  Problem 2.30.

Prove that every compact metric space is separable.

A subset of a topological space is called _nowhere dense_ if its closure has
empty interior.

######  Problem 2.31 (Baire’s theorem).

Prove that a complete metric space cannot be covered by at most countably many
nowhere dense subsets. Moreover, the complement of the union of at most
countably many nowhere dense subsets is everywhere dense.

######  Problem 2.32.

Prove that a compact metric space $X$ cannot be isometrically mapped to a
subspace $Y\subset X$ such that $Y\neq X$. In other words, each isometric
mapping $f\colon X\to X$ for a compact metric space $X$ is surjective.

######  Problem 2.33.

Let $X$ be a compact metric space and $f\colon X\to X$ be a mapping. Prove
that

  1. (1)

if $f$ is surjective and nonexpanding, then $f$ is an isometry _;_

  2. (2)

if $\bigl{|}f(x)f(y)\bigr{|}\geq|xy|$ for all $x,y\in X$, then $f$ is an
isometry.

###  2.6 Canonical isometric embeddings of metric spaces

Let $X$ be an arbitrary metric space. We denote by $C(X)$ the vector space of
functions continuous on $X$, and by $C_{b}(X)$ the subspace of $C(X)$ composed
of all bounded functions, and consider on $C_{b}(X)$ the norm
$\|f\|_{\infty}=\sup_{x\in X}\bigl{|}f(x)\bigr{|}$ and the corresponding
metric $|fg|_{\infty}=\|f-g\|_{\infty}$.

We define a mapping $\nu\colon X\to C_{b}(X)$ as follows. For each point $x\in
X$, by $d_{x}$ we denote the function $d_{x}\colon X\to[0,\infty)$ defined by
the rule $d_{x}(y)=|xy|$. This function is $1$-Lipschitz and, therefore,
$d_{x}\in C(X)$. Now we fix some point $p\in X$ and consider the function
$d_{x}-d_{p}$. Then for each $y\in X$ we have
$\bigl{|}d_{x}(y)-d_{p}(y)\bigr{|}\leq|xp|$, so the function $d_{x}-d_{p}$ is
bounded and, thus, belongs to $C_{b}(X)$.

######  Theorem 2.25 (Frechet, Kuratowski).

The mapping $\nu\colon X\to C_{b}(X)$ defined by the formula $\nu\colon
x\mapsto d_{x}-d_{p}$ is an isometric embedding.

###### Proof.

By virtue of Problem 2.5, it suffices to verify that the mapping $\nu$ is
isometric.

Choose arbitrary $x,y\in X$, then

$\bigl{|}(d_{x}-d_{p})(d_{y}-d_{p})\bigr{|}_{\infty}=\sup_{z\in
X}\bigl{|}d_{x}(z)-d_{y}(z)\bigr{|}\leq|xy|$

by triangle inequality. On the other hand, if $z=y$, then
$\bigl{|}d_{x}(z)-d_{y}(z)\bigr{|}=|xy|$, which implies the required result. ∎

Let us prove a finer result. Recall that by $\ell_{\infty}$ we denote the
space of all bounded sequences with the metric defined by the norm
$\|\cdot\|_{\infty}$.

######  Theorem 2.26 (Frechet).

Let $X$ be a separable metric space, then $X$ can be isometrically embedded
into $\ell_{\infty}$.

###### Proof.

Consider an everywhere dense sequence $x_{1},x_{2},\ldots$ in $X$, which
exists due to separability. Choose an arbitrary point $p\in X$ and associate
with each point $x\in X$ a sequence $\nu(x)$ obtained by restricting the
function $d_{x}-d_{p}$ to the sequence $x_{1},x_{2},\ldots$, namely,
$\nu(x)(i)=d_{x}(x_{i})-d_{p}(x_{i})$. Since the functions $d_{x}-d_{p}$ are
bounded, then $\nu(x)\in\ell_{\infty}$. The inequality
$\bigl{|}\nu(x)\nu(y)\bigr{|}_{\infty}\leq|xy|$ is verified in the same way as
in the proof of Theorem 2.25. The converse inequality follows from the fact
that the subset $\\{x_{i}\\}$ is everywhere dense in $X$: consider
$x_{i_{k}}\to x$, then

$\bigl{|}\nu(x)\nu(y)\bigr{|}_{\infty}=\sup_{z\in
X}\bigl{|}d_{x}(z)-d_{y}(z)\bigr{|}\geq\bigl{|}d_{x}(x_{i_{k}})-d_{y}(x_{i_{k}})\bigr{|}\to
d_{y}(x)=|xy|\ \text{as $k\to\infty$}.$

The theorem is proved. ∎

## References to Chapter 2

  * [1] M.M.Deza, E.Deza, _Encyclopedia of Distances_. Springer, 2009.

### Exercises to Chapter 2

######  Exercise 2.1.

Let $X$ be a pseudometric space and $\sim$ is the natural equivalence
relation: $x\sim y$ if and only if $|xy|=0$. For each $x\in X$ denote by $[x]$
the equivalence class containing $x$. Prove that for any $x,y\in X$,
$x^{\prime}\in[x]$, and $y^{\prime}\in[y]$ it is true that
$|x^{\prime}y^{\prime}|=|xy|$. Thus, on the set $X/\\!\\!\sim$ the
corresponding distance function is correctly defined:
$\bigl{|}[x][y]\bigr{|}=|xy|$. Show that this distance function is a metric.

######  Exercise 2.2.

Let $X$ be an arbitrary metric space, $x,y\in X$, $r\geq 0$, $s,t>0$, and
$A\subset X$ be nonempty. Verify that

  1. (1)

$U_{s}\bigl{(}\\{x\\}\bigr{)}=U_{s}\bigl{(}x)$ and
$B_{r}\bigl{(}\\{x\\}\bigr{)}=B_{r}\bigl{(}x)$;

  2. (2)

the functions $y\mapsto|xy|$, $y\mapsto|yA|$ are continuous;

  3. (3)

an open neighborhood $U_{s}(A)$ is an open subset of $X$, and a closed
neighborhood $B_{r}(A)$ is a closed subset of $X$;

  4. (4)

$U_{t}\bigl{(}U_{s}(A)\bigr{)}\subset U_{s+t}(A)$ and construct an example
demonstrating that the left-hand side can be different from the right-hand
side;

  5. (5)

$B_{t}\bigl{(}B_{s}(A)\bigr{)}\subset B_{s+t}(A)$ and construct an example
demonstrating that the left-hand side can be different from the right-hand
side;

  6. (6)

$\partial U_{s}(x)$, $\partial B_{s}(x)$ are not related by any inclusion;
$\partial U_{s}(x)\subset S_{s}(x)$ and $\partial B_{r}(x)\subset S_{r}(x)$;
the both previous inclusions can be strict;

  7. (7)

$\operatorname{diam}U_{s}(x)\leq\operatorname{diam}B_{s}(x)\leq 2s$;

  8. (8)

$\operatorname{diam}U_{s}(A)\leq\operatorname{diam}B_{s}(A)\leq\operatorname{diam}A+2s$.

######  Exercise 2.3.

Let $\mathcal{L}(f)\subset\mathbb{R}$ be the set of all Lipschitz constants
for a Lipschitz mapping $f$. Prove that $\inf\mathcal{L}(f)$ is also a
Lipschitz constant.

######  Exercise 2.4.

Show that each Lipschitz map is uniformly continuous, and each uniformly
continuous map is continuous.

######  Exercise 2.5.

Show that each isometry is a homeomorphism, in particular, each isometric
mapping of one metric space into another one is an embedding, i.e., we recall,
it is a homeomorphism with an image.

######  Exercise 2.6.

Verify that the identity map, the composition of isometries, and the inverse
mapping to an isometry are also isometries, i.e., the set of all isometries of
an arbitrary metric space forms a group.

######  Exercise 2.7.

Let $X$ be an arbitrary metric space, $x,y\in X$ and $A\subset X$ be nonempty.
Prove that $|Ax|+|xy|\geq|Ay|$, so that the function $\rho_{A}(x)=|Ax|$ is
$1$-Lipschitz and, therefore, uniformly continuous.

######  Exercise 2.8.

Describe the Cayley graphs for the following groups $G$ and generating sets
$S$:

  1. (1)

$G={\mathbb{Z}}$ and $S=\\{1\\}$;

  2. (2)

$G={\mathbb{Z}}_{m}$ and $S=\\{1\\}$;

  3. (3)

$G={\mathbb{Z}}^{2}$ and $S=\bigl{\\{}(1,0)\,(0,1)\bigr{\\}}$;

  4. (4)

$G={\mathbb{Z}}^{2}$ and $S=\bigl{\\{}(1,0)\,(0,1),\,(1,1)\bigr{\\}}$;

  5. (5)

$G$ is a free group with generators $a$ and $b$.

######  Exercise 2.9.

Let $(X,\rho)$ be a metric (pseudometric) space, and $\sim$ an equivalence
relation on $X$. Define the following _quotient distance function_ on $X$:

$\rho_{\sim}(x,y)=\inf\Bigl{\\{}\sum_{i=0}^{n}\rho(p_{i},q_{i}):p_{0}=x,\,q_{n}=y,\,n\in{\mathbb{N}},\,q_{i}\sim
p_{i+1}\ \text{for all $i$}\Bigr{\\}}.$

Prove that $\rho_{\sim}$ is a pseudometric on $X$.

######  Exercise 2.10.

Let $\xi=(p_{0}-q_{0}\sim p_{1}-q_{1}\sim\cdots\sim p_{n}-q_{n})$ be an
irreducible admissible sequence. Prove that

  1. (1)

for any $i<j$ we have $p_{i}\not\sim p_{j}$, $q_{i}\not\sim q_{j}$;

  2. (2)

$q_{i}\sim p_{j}$ if and only if $j=i+1$;

  3. (3)

for any $i$ we have $q_{i}\not=p_{i+1}$.

######  Exercise 2.11.

Let $\sim$ be the trivial equivalence on a metric space $(X,\rho)$, i.e.,
$x\sim y$ if and only if $x=y$. Prove that $\rho_{\sim}=\rho$.

######  Exercise 2.12.

Let $\sim$ be an equivalence on a pseudometric space $(X,\rho)$. Prove that
for any $x,y\in X$ it holds $\rho_{\sim}(x,y)\leq\rho(x,y)$. Thus, if we
define the function $b\colon X\times X\to\mathbb{R}$ such that $b(x,y)=0$ for
$x\sim y$, and $b(x,y)=\rho(x,y)$ otherwise, then $\rho_{\sim}\leq b$.

######  Exercise 2.13.

Let $X$ be a generalized pseudometric space. We can define two equivalence
relations: $x\mathop{\sim}\nolimits_{1}y$ if and only if $|xy|=\infty$, and
$x\mathop{\sim}\nolimits_{2}y$ if and only if $|xy|=0$. Prove that each class
of equivalence $\mathop{\sim}\nolimits_{1}$ is a pseudometric space (with
finite distance), and that the distance between points from different classes
equals $\infty$. Thus, if we denote by $X_{i}$ the classes of equivalence
$\mathop{\sim}\nolimits_{1}$, then $X=\sqcup X_{i}$. Prove that the space
$X/\\!\\!\mathop{\sim}\nolimits_{2}$ equals the disjoint union
$\sqcup(X_{i}/\\!\\!\mathop{\sim}\nolimits_{2})$ of metric spaces
$X_{i}/\\!\\!\mathop{\sim}\nolimits_{2}$.

######  Exercise 2.14.

Let $X$ and $Y$ be metric spaces, $Z\subset X$, and $f\colon Z\to Y$ is an
isometric mapping. Let $\rho$ be the metric on the $X\sqcup_{f}Y$. Prove that
the restrictions of $\rho$ to $X$ and $Y$ coincides with the initial metrics
of $X$ and $Y$, respectively.

######  Exercise 2.15.

Let $y_{0}\in Y$ and $f(X)=y_{0}$. Prove that $X\sqcup_{f}Y$ is isometric to
$Y$.

######  Exercise 2.16.

Let $X$ be a metric space and $G\subset\operatorname{Iso}(X)$ a subgroup of
its isometry group. For each two elements $G(x),G(y)\in X/G$ we set
$d\bigl{(}G(x),G(y)\bigr{)}=\inf\bigl{\\{}|x^{\prime}y^{\prime}|:x^{\prime}\in
G(x),\,y^{\prime}\in G(y)\bigr{\\}}$. Prove that $d=\rho_{\sim}$, where the
equivalence $\sim$ is generated by the action of $G$ on $X$.

######  Exercise 2.17.

Let $S^{1}$ be the standard unit circle in the Euclidean plane. As a distance
between $x,y\in S^{1}$ we take the length of the shortest arc of $S_{1}$
between $x$ and $y$. By _the standard torus_ we mean the direct product
$T^{2}=S^{1}\times S^{1}$ (with the Euclidean binder). We describe the points
on the both $S^{1}$ by their polar angles $\varphi_{1}$ and $\varphi_{2}$,
defined up to $2\pi$. So, _the shifts_
$s_{a,b}\colon(\varphi_{1},\varphi_{2})\mapsto(\varphi_{1}+a,\varphi_{2}+b)$
are isometries of $T^{2}$. Fix some $(a,b)\in\mathbb{R}^{2}$ and consider a
subgroup $G_{a,b}\subset\operatorname{Iso}(T^{2})$ consisting of all shifts
$s_{ta,tb}$, $t\in\mathbb{R}$. For different $a$ and $b$, find the
corresponding pseudometric and metric quotient spaces.

######  Exercise 2.18.

Represent the standard torus from Exercise 2.17 as a polyhedron space.

######  Exercise 2.19.

Verify that the constructions given in Section 2.3 do define (pseudo-)metrics,
as declared.

######  Exercise 2.20.

Let $d$ be a metric. Find the least possible $c$ such that $d+c$ is a
pseudometric. Verify that for such $c$ and any $c^{\prime}>c$ the function
$d+c^{\prime}$ is a metric.

######  Exercise 2.21.

Show that a subspace of a complete metric space is complete if and only if it
is closed.

######  Exercise 2.22.

Let $X$ be an arbitrary subspace of a complete metric space. Then the closure
$\overline{X}$ of the set $X$ is a completion of the space $X$.

######  Exercise 2.23.

Let $f\colon X\to Y$ be a bi-Lipschitz mapping of metric spaces. Prove that
$X$ is complete if and only of $Y$ is complete. Construct a homeomorphism of
metric spaces that does not preserves completeness.

######  Exercise 2.24.

Show that a metric space is complete if and only if the following condition
holds: for any sequence of closed subsets $X_{1}\supset X_{2}\supset
X_{3}\supset\cdots$ such that $\operatorname{diam}X_{n}\to 0$ as $n\to 0$, the
intersection $\cap_{i=1}^{\infty}X_{i}$ is not empty (in fact, it consists of
unique element). Show that the condition $\operatorname{diam}X_{n}\to 0$ is
essential.

######  Exercise 2.25 (Fixed-point theorem).

Let $f\colon X\to X$ be a $C$-Lipschitz mapping of a complete metric spaces
$X$. Prove that for $C<1$ there exists and unique a point $x_{0}$ such that
$f(x_{0})=x_{0}$ (it is called _the fixed point of the mapping $f$_).

######  Exercise 2.26.

Give an example of a topological space that is

  1. (1)

compact, but not sequentially compact;

  2. (2)

sequentially compact, but not compact.

######  Exercise 2.27 (Lebesgue’s lemma).

Let $X$ be a compact metric space. Prove the following statement: for any open
cover $\\{U_{i}\\}_{i\in I}$ of $X$ there exists $\rho>0$ such that for any
$x\in X$ one can find $U_{i}$ with $B_{\rho}(x)\subset U_{i}$.

######  Exercise 2.28.

Show that each continuous mapping $f\colon X\to Y$ from a compact metric space
to an arbitrary metric space is uniformly continuous.

######  Exercise 2.29.

Prove that the diameter $\operatorname{diam}X$ of a compact metric space $X$
if finite, and that there exist $x,y\in X$ such that
$\operatorname{diam}X=|xy|$.

######  Exercise 2.30.

Prove that every compact metric space is separable.

######  Exercise 2.31 (Baire’s theorem).

A subset of a topological space is called _nowhere dense_ if its closure has
empty interior. Prove that a complete metric space cannot be covered by at
most countably many nowhere dense subsets. Moreover, the complement of the
union of at most countably many nowhere dense subsets is everywhere dense.

######  Exercise 2.32.

Prove that a compact metric space $X$ cannot be isometrically mapped to a
subspace $Y\subset X$ such that $Y\neq X$. In other words, each isometric
mapping $f\colon X\to X$ for a compact metric space $X$ is surjective.

######  Exercise 2.33.

Let $X$ be a compact metric space and $f\colon X\to X$ be a mapping. Prove
that

  1. (1)

if $f$ is surjective and nonexpanding, then $f$ is an isometry _;_

  2. (2)

if $\bigl{|}f(x)f(y)\bigr{|}\geq|xy|$ for all $x,y\in X$, then $f$ is an
isometry.

##  Chapter 3 Curves in Metric Spaces.

  * Schedule.

Curves in a topological space, parameter of a curve, reparametrization,
polygonal line in a metric space, its edges, the length of the edge, the
length of the polygonal line, the length of a curve in a metric space,
rectifiable curves, properties of the length functional, intrinsic metric,
generalized intrinsic pseudometric, maximal and minimal generalized
pseudometrics, minimum of generalized intrinsic pseudometrics, quotients of
generalized intrinsic pseudometric spaces, Hopf-Rinow condition, Hopf-Rinow
theorem Part 1, convergence and uniform convergence in terms of the
corresponding product spaces, limits of sequences of Lipschitz mappings, arc-
length and uniform curves, reparametrizations, uniform reparametrizations,
Arzela-Ascoli theorem, shortest curves and geodesics, existences theory for
shortest curves, geodesic metric space, midpoints and $\varepsilon$-midpoints,
existence of shortest curves in term of midpoints, intrinsic metrics and
$\varepsilon$-midpoints.

In this section we discuss some results related to the geometry of curves in
metric spaces.

Recall that _a curve_ in a topological space $X$ is any continuous mapping
$\gamma\colon[a,b]\to X$ from a segment $[a,b]\subset\mathbb{R}$ with the
standard topology; the variable $t\in[a,b]$ is called _the parameter of the
curve $\gamma$_, and the curve $\gamma$ is sometimes written in the form
$\gamma(t)$.

Each homeomorphism $\varphi\colon[c,d]\to[a,b]$ generates a new curve
$\gamma\circ\varphi\colon[c,d]\to X$, about which we say that it is obtained
from $\gamma$ _by replacement $\varphi$ of the parameter $t$ with the
parameter $s\in[c,d]$_. Moreover, if there is no misunderstanding, instead of
the curve $(\gamma\circ\varphi)(s)$ we simply write $\gamma(s)$. Such
replacement $\varphi$ is also called _a reparametrization_.

Note that each reparametrization is a strictly monotonic continuous function.
If the function $\varphi$ grows, then we say that $\varphi$ _reverses the
direction_ , otherwise that it _changes the direction_.

###  3.1 Rectifiable curves

Let $X$ be a metric space. A finite sequence $L=(A_{0},\ldots,A_{n})$ of
points in the space $X$ we called _a polygonal line in $X$_; moreover, the
pairs $(A_{i-1},A_{i})$ will be called _edges of the polygonal line $L$_, and
the numbers $|A_{i-1}A_{i}|$ _the lengths_ of these edges. The sum of the
lengths of all these edges we call _the length of the polygonal line $L$_ and
denote by $|L|$.

Let $\gamma\colon[a,b]\to X$ be an arbitrary curve. For each partition
$\xi=(a=t_{0}<t_{1}<\cdots<t_{m}=b)$, consider the corresponding polygonal
line $L_{\gamma}(\xi)=\bigl{(}\gamma(t_{0}),\ldots,\gamma(t_{m})\bigr{)}$
(such polygonal lines will be called _inscribed in the curve $\gamma$_), then
the value

$|\gamma|=\sup\Bigl{\\{}\bigl{|}L_{\gamma}(\xi)\bigr{|}:\text{$\xi$ is a
partition of the segment $[a,b]$}\Bigr{\\}}$

is called _the length of the curve $\gamma$_. A curve $\gamma$ is called
_rectifiable_ if $|\gamma|<\infty$.

Let us give some examples of rectifiable curves.

######  Example 3.1.

Each $C$-Lipschitz curve $\gamma\colon[a,b]\to X$ is rectifiable, because for
any partition $\xi$ of the segment $[a,b]$ we have $|L_{\gamma}(\xi)|\leq
C(b-a)$ and, therefore, $|\gamma|\leq C(b-a)<\infty$.

Denote by $\Omega(X)$ the family of all curves in a metric space $X$, and by
$\Omega_{0}(X)\subset\Omega(X)$ the subfamily of all rectifiable curves. Note
that on $\Omega(X)$ and on $\Omega_{0}(X)$ there are defined

  1. (1)

_the restriction_ of each curve $\gamma\colon[a,b]\to X$ to each subsegment
$[c,d]\subset[a,b]$;

  2. (2)

_the gluing $\gamma_{1}\cdot\gamma_{2}$_ of those pairs of curves
$\gamma_{1}\colon[a,b]\to X$, $\gamma_{2}\colon[b,c]\to X$ for which
$\gamma_{1}(b)=\gamma_{2}(b)$, namely,
$(\gamma_{1}\cdot\gamma_{2})\colon[a,c]\to X$ is the curve whose restrictions
to $[a,b]$ and $[b,c]$ coincide with $\gamma_{1}$ and $\gamma_{2}$,
respectively;

  3. (3)

_the reparametrization_ and equivalence identifying curves that differ by
parameterization.

The following proposition describes some properties of the length of a curve.

######  Proposition 3.2.

Let $X$ be an arbitrary metric space. Then

  1. (1)

generalized triangle inequality: if $\gamma\in\Omega(X)$ joins the points
$x,y\in X$, then $|\gamma|\geq|xy|$_;_

  2. (2)

additivity: if $\gamma=\gamma_{1}\cdot\gamma_{2}$ is the gluing of curves
$\gamma_{1},\gamma_{2}\in\Omega(X)$ then
$|\gamma|=|\gamma_{1}|+|\gamma_{2}|$_;_

  3. (3)

continuity: for any $\gamma\in\Omega_{0}(X)$, $\gamma\colon[a,b]\to X$, the
function $f(t)=\bigl{|}\gamma|_{[a,t]}\bigr{|}$ is continuous _;_

  4. (4)

independence from parameter: for each $\gamma\in\Omega(X)$,
$\gamma\colon[a,b]\to X$, and reparametrization $\varphi\colon[c,d]\to[a,b]$,
it holds $|\gamma|=|\gamma\circ\varphi|$_;_

  5. (5)

consistency with topology: for each $x\in X$, $\varepsilon>0$, $y\in
X\setminus U_{\varepsilon}(x)$, and a curve $\gamma\in\Omega(X)$ joining $x$
and $y$, it holds $|\gamma|\geq\varepsilon$_;_

  6. (6)

lower semicontinuity: for any sequence $\gamma_{n}\in\Omega_{0}(X)$ that
converges pointwise to some $\gamma\in\Omega_{0}(X)$, we have

$|\gamma|\leq\liminf_{n\to\infty}|\gamma_{n}|.$

###### Proof.

Only the items (3) and (6) are nontrivial, we prove them.

(3) Choose an arbitrary $t\in[a,b]$ and show that for any $\varepsilon>0$
there is $\delta>0$ such that for all $s\in[a,b]\cap(t-\delta,t+\delta)$ the
inequality $\bigl{|}f(t)-f(s)\bigr{|}<\varepsilon$ holds. Put $\ell=|\gamma|$.
By definition, there exists a partition $\xi$ of the segment $[a,b]$ such that
$\ell-\varepsilon/2<\bigl{|}L_{\gamma}(\xi)\bigr{|}\leq\ell$. If
$t\not\in\xi$, add it to $\xi$ (we denote the resulting partition by the same
letter). It is clear that for the resulting partition,
$\ell-\varepsilon/2<\bigl{|}L_{\gamma}(\xi)\bigr{|}\leq\ell$ is still
satisfied.

For $\delta_{1}$ we take the distance from $t$ to the nearest element of the
partition $\xi$, other than $t$. Since subdivisions of the partition $\xi$ can
change the length of the polygonal line $L_{\gamma}(\xi)$ only within
$(\ell-\varepsilon/2,\ell]$, then for each
$s\in[a,b]\cap(t-\delta_{1},t+\delta_{1})$ the length
$\ell_{ts}=\bigl{|}f(t)-f(s)\bigr{|}$ of the fragment of the curve $\gamma$
between points $\gamma(t)$ and $\gamma(s)$ differs from
$\bigl{|}\gamma(t)\gamma(s)\bigr{|}$ by less than $\varepsilon/2$. On the
other hand, since the map $\gamma$ is continuous, there exists $\delta_{2}>0$
such that for all $s\in[a,b]\cap(t-\delta_{2},t+\delta_{2})$ we have
$\bigl{|}\gamma(t)\gamma(s)\bigr{|}<\varepsilon/2$. It remains to put
$\delta=\min\\{\delta_{1},\delta_{2}\\}$.

(6) Choose an arbitrary $\varepsilon>0$ and show that for sufficiently large
$n$ the inequality $|\gamma|\leq|\gamma_{n}|+\varepsilon$ holds, thus
$|\gamma|\leq\liminf_{n\to\infty}|\gamma_{n}|+\varepsilon$ and, due to the
arbitrariness of $\varepsilon$, we get what is required.

So, let $\varepsilon>0$ be fixed. Choose a partition
$\xi=(a=t_{0}<t_{1}<\cdots<t_{m}=b)$ of the segment $[a,b]$ such that
$|\gamma|-\bigl{|}L_{\gamma}(\xi)\bigr{|}<\varepsilon/2$. There is $N$ such
that for any $n>N$ and all $i$ the inequality
$\bigl{|}\gamma(t_{i})\gamma_{n}(t_{i})\bigr{|}<\frac{\varepsilon}{4m}$ holds.
This immediately implies that

$\bigl{|}\gamma(t_{i-1})\gamma(t_{i})\bigr{|}<\bigl{|}\gamma_{n}(t_{i-1})\gamma_{n}(t_{i})\bigr{|}+\frac{\varepsilon}{2m},$

therefore
$\bigl{|}L_{\gamma}(\xi)\bigr{|}<\bigl{|}L_{\gamma_{n}}(\xi)\bigr{|}+\varepsilon/2$.
Thus,

$|\gamma|<\bigl{|}L_{\gamma}(\xi)\bigr{|}+\varepsilon/2<|L_{\gamma_{n}}(\xi)|+\varepsilon/2+\varepsilon/2\leq|\gamma_{n}|+\varepsilon,$

as required. ∎

######  Problem 3.1.

Prove the remaining items of Proposition 3.2.

######  Problem 3.2.

Will the items (3) and (6) of Proposition 3.2 remain true if we change
$\Omega_{0}(X)$ to $\Omega(X)$?

######  Problem 3.3.

Show that a piecewise smooth curve in $\mathbb{R}^{n}$ is Lipschitzian with a
Lipschitz constant equal to the maximum modulus of the velocity vector of the
curve, therefore every such curve is rectifiable.

Let $X$ be a metric space in which any two points are connected by a
rectifiable curve. Then for any $x,y\in X$ the quantity

$d_{in}(x,y)=\inf\bigl{\\{}|\gamma|:\text{$\gamma$ is a curve joining $x$ and
$y$}\bigr{\\}}$

is finite.

######  Problem 3.4.

Let $X$ be a metric space in which any two points are connected by a
rectifiable curve.

  1. (1)

Prove that $d_{in}$ is a metric.

  2. (2)

Denote by $\tau$ the metric topology of $X$ w.r.t. the initial metric on $X$,
by $\tau_{in}$ the metric topology w.r.t. $d_{in}$, by $X_{in}$ the set $X$
with metric $d_{in}$ and topology $\tau_{in}$. Show that
$\tau\subset\tau_{in}$. In particular, if a mapping $\gamma\colon[a,b]\to
X_{in}$ is continuous, then the mapping $\gamma\colon[a,b]\to X$ is continuous
as well.

  3. (3)

Construct an example when $\tau\neq\tau_{in}$.

  4. (4)