Pure metric geometry: introductory lectures
We discuss domestic affairs of metric spaces, keeping away from any extra structure. Topics include universal spaces, injective spaces, Hausdorff and Gromov--Hausdorff convergences, and ultralimits.

\chapter{Space of sets}

\section{Hausdorff distance}

Let $\spc{X}$ be a metric space.
Given a subset $A\subset \spc{X}$,
consider the distance function to $A$
$$\distfun_A: \spc{X} \to [0,\infty)$$
defined as 
$$\distfun_A(x)
\df
\inf_{a\in A}\{\,\dist ax{\spc{X}}\,\}.$$

\begin{thm}{Definition}\label{def:hausdorff-convergence}
Let $A$ and $B$ be two compact subsets of a metric space $\spc{X}$.
Then the \index{Hausdorff distance}\emph{Hausdorff distance} between $A$ and $B$ is defined as 
$$|A-B|_{\Haus\spc{X}}
\df
\sup_{x\in \spc{X}}\{\,|\distfun_A(x)-\distfun_B(x)|\,\}.
$$

\end{thm}

The following observation gives a useful reformulation of the definition:

\begin{thm}{Observation}\label{obs:Haus-nbhds}
Suppose $A$ and $B$ be two compact subsets of a metric space $\spc{X}$.
Then $|A-B|_{\Haus\spc{X}}< R$ if and only if and only if 
$B$ lies in an $R$-neighborhood of $A$, 
and 
$A$ lies in an $R$-neighborhood of~$B$.
\end{thm}



Note that the set of all nonempty compact subsets of a metric space $\spc{X}$ equipped with the Hausdorff metric forms a metric space.
This new metric space will be denoted as $\Haus\spc{X}$.


\begin{thm}{Exercise}\label{ex:diam}
Let $\spc{X}$ be a metric space.
Given a subset $A\subset \spc{X}$ define its \index{diameter}\emph{diameter} as 
$$\diam A\df\sup_{a,b\in A} |a-b|.$$

Show that 
$$\diam\:\Haus\spc{X}\to \RR$$ 
is a \index{Lipschitz function}\emph{$2$-Lipschitz function};
that is,
\[|\diam A-\diam B|\le 2\cdot\dist{A}{B}{\Haus\spc{X}}\]
for any two compact nonempty sets $A,B\subset\spc{X}$.
\end{thm}


\begin{thm}{Exercise}\label{ex:Hausdorff-bry}
Let $A$ and $B$ be two compact subsets in the Euclidean plane $\RR^2$.
Assume $|A-B|_{\Haus\RR^2}<\eps$.

\begin{subthm}{ex:Hausdorff-bry:conv}
Show that $|\Conv A-\Conv B|_{\Haus\RR^2}<\eps$, where $\Conv A$ denoted the convex hull of $A$.
\end{subthm}
\begin{subthm}{ex:Hausdorff-bry:bry}
Is it true that
$|\partial A-\partial B|_{\Haus\RR^2}<\eps$,
where $\partial A$ denotes the boundary of $A$.

Does the converse hold? That is, assume $A$ and $B$ be two compact subsets in $\RR^2$
and $|\partial A-\partial B|_{\Haus\RR^2}<\eps$; 
is it true that $|A-B|_{\Haus\RR^2}\z<\eps$?
\end{subthm}

\end{thm}

Note that part \ref{SHORT.ex:Hausdorff-bry:conv} implies that $A\mapsto \Conv A$ defines a short map $\Haus\RR^2\to \Haus\RR^2$. 

\begin{thm}{Exercise}\label{ex:Haus-func}
Let $A$ and $B$ be two compact subsets in metric space $\spc{X}$.
Show that 
\[\dist{A}{B}{\Haus\spc{X}}=\sup_f\, \{\,\max_{a\in A}\{f(a)\}-\max_{b\in B}\{f(b)\,\},\]
where the least upper bound is taken for all $1$-Lipschitz functions $f$.

\end{thm}


\section{Hausdorff convergence}

\begin{thm}{Blaschke selection theorem}\label{thm:compact+Hausdorff}
A metric space $\spc{X}$ is compact if and only if
so is $\Haus\spc{X}$.
\end{thm}

The Hausdorff metric can be used to define convergence.
Namely, suppose $K_1,K_2,\dots$, and $K_\infty$ are compact sets in a metric space $\spc{X}$.
If $|K_\infty-K_n|_{\Haus\spc{X}}\to0$ as $n\to\infty$, then we say that 
the sequence $(K_n)$ {}\emph{converges} to $K_\infty$ \index{convergence in the sense of Hausdorff}\emph{in the sense of Hausdorff};
or we can say that $K_\infty$ is \emph{Hausdorff limit} of the sequence $(K_n)$.

Note that the theorem implies that from any sequence of compact sets in $\spc{X}$ one can select a subsequence that converges in the sense of Hausdorff; 
for that reason, it is called a \emph{selection} theorem. 

\parit{Proof; ``only if'' part.}
Consider the map $\iota$ that sends point $x\in \spc{X}$ to the one-point subset $\{x\}$ of $\spc{X}$.
Note that $\iota\:\spc{X}\to \Haus\spc{X}$ is distance-preserving.

Suppose that $A\subset \spc{X}$.
Note that $\diam A=0$ if and only if $A$ is a one-point set.
Therefore, from Exercise~\ref{ex:diam}, it follows 
that $\iota(\spc{X})$ is a closed subset of the compact space $\Haus\spc{X}$.
Whence $\iota(\spc{X})$, and therefore $\spc{X}$, are compact.
\qeds

To prove the ``if'' part we will need the following two lemmas.

\begin{thm}{Monotone convergence}\label{lem:decreasing-converges}
Let $K_1\supset K_2\supset\dots$ be a nested sequence of nonempty compact sets in a metric space $\spc{X}$
then $K_\infty\z=\bigcap_n K_n$ is the Hausdorff limit of $K_n$;
that is, $|K_\infty-K_n|_{\Haus\spc{X}}\to0$ as $n\to\infty$.
\end{thm}

\parit{Proof.}
By finite intersection property, $K_\infty$ is a nonempty compact set.

If the assertion were false, 
then there is $\eps>0$ such that for each $n$ 
one can choose $x_n\in K_n$
such that $\distfun_{K_\infty}(x_n)\ge\eps$.
Note that $x_n\in K_1$ for each $n$.
Since $K_1$ is compact, 
there is 
a \index{partial limit}\emph{partial limit}%
\footnote{Partial limit is a limit of a subsequence.}
 $x_\infty$ of $x_n$.
Clearly, $\distfun_{K_\infty}(x_\infty)\ge \eps$.

On the other hand, since $K_n$ is closed and $x_m\in K_n$ for $m\ge n$,
we get $x_\infty\in K_n$ for each $n$.
It follows that $x_\infty\in K_\infty$ and therefore $\distfun_{K_\infty}(x_\infty)=0$ ---
a contradiction.\qeds


\begin{thm}{Lemma}\label{lem:complete+Hausdorff}
If $\spc{X}$ is a compact metric space, then $\Haus\spc{X}$
is complete.
\end{thm}

\parit{Proof.}
Let $(Q_n)$ be a Cauchy sequence in $\Haus\spc{X}$.
Passing to a subsequence of $Q_n$ we may assume that 
$$|Q_n-Q_{n+1}|_{\Haus\spc{X}}\le \tfrac1{10^n}\eqlbl{eq:eps=1/10}$$
for each $n$.

Denote by $K_n$ the closed $\tfrac1{10^n}$-neighborhood of $Q_n$;
that is,
\begin{align*}
K_n&= \set{x\in \spc{X}}{\distfun_{Q_n}(x)\le \tfrac1{10^n}}
\end{align*}
Since $\spc{X}$ is compact so is each $K_n$.

By \ref{obs:Haus-nbhds}, $|Q_n-K_n|_{\Haus\spc{X}}\le \tfrac1{10^n}$.
From \ref{eq:eps=1/10}, we get
$K_n\supset K_{n+1}$ 
for each $n$.
Set 
$$K_\infty=\bigcap_{n=1}^\infty K_n.$$
By the monotone convergence (\ref{lem:decreasing-converges}),
 $|K_n-K_\infty|_{\Haus\spc{X}}\to 0$ as $n\to\infty$.
Since $|Q_n-K_n|_{\Haus\spc{X}}\le \tfrac1{10^n}$, we get $|Q_n-K_\infty|_{\Haus\spc{X}}\to 0$ as $n\to\infty$ --- hence the lemma.
\qeds

\begin{thm}{Exercise}\label{ex:closure-union}
Let $\spc{X}$ be a complete metric space and $K_1,K_2,\dots$ be a sequence of compact sets 
that converges in the sense of Hausdorff.
Show that the union $K_1\cup K_2\cup\dots$ is a compact closure.

Use this statement to show that in Lemma~\ref{lem:complete+Hausdorff} compactness of $\spc{X}$ can be exchanged to completeness.
\end{thm}

\parit{Proof of ``if'' part in \ref{thm:compact+Hausdorff}.}
According to Lemma~\ref{lem:complete+Hausdorff},
$\Haus\spc{X}$ is complete.
It remains to show that $\Haus\spc{X}$ is totally bounded (\ref{totally-bounded});
that is, given $\eps>0$ there is a finite $\eps$-net in $\Haus\spc{X}$.

Choose a finite $\eps$-net $A$ in $\spc{X}$.
Denote by $B$ the set of all subsets of $A$.
Note that  $B$ is a finite set in $\Haus\spc{X}$.
For each compact set $K\subset \spc{X}$, consider the subset $K'$ of all points $a\in A$
such that $\distfun_K(a)\le \eps$.
Observe that $K' \in B$ and $|K-K'|_{\Haus\spc{X}}\le\eps$.
In other words, $B$ is a finite $\eps$-net in $\Haus\spc{X}$.
\qeds

\begin{thm}{Exercise}\label{ex:Haus-length}
Let $\spc{X}$ be a complete metric space.
Show that $\spc{X}$ is a length space if and only if so is $\Haus\spc{X}$.
\end{thm}

\section{An application}

The following statement is called \index{isoperimetric inequality}\emph{isoperimetric inequality in the plane}.

\begin{thm}{Theorem}\label{thm:isoperimetric}
Among the plane figures bounded by closed curves of length at most $\ell$ the round disk has the maximal area.
\end{thm}

In this section, we will sketch a proof of the isoperimetric inequality that uses the Hausdorff convergence.
It is based on the following exercise.

\begin{thm}{Exercise}\label{ex:Huas-perimeter-area}
Let $\spc{C}$ be a subspace of $\Haus\RR^2$ formed by all compact convex subsets in $\RR^2$.
Show that perimeter\footnote{If the set degenerates to a line segment of length $\ell$, then its perimeter is defined as $2\cdot \ell$.} and area are continuous on~$\spc{C}$.
That is, if a sequence of convex compact plane sets $X_n$ converges to $X_\infty$ in the sense of Hausdorff, then 
\[\perim X_n\to \perim X_\infty\quad\text{and}\quad\area X_n\to\area X_\infty\]
as $n\to\infty$.
\end{thm}

\parit{Semiproof of \ref{thm:isoperimetric}.}
It is sufficient to consider only convex figures of the given perimeter; if a figure is not convex, pass to its convex hull and observe that it has a larger area and smaller perimeter.


Note that the selection theorem (\ref{thm:compact+Hausdorff}) together with the exercise imply the existence of figure $D$ with perimeter $\ell$ and maximal area.

It remains to show that $D$ is a round disk.
This is a problem in elementary geometry.

Let us cut $D$ along a chord $[ab]$ into two lenses, $L_1$ and $L_2$.
Denote by $L_1'$ the reflection of $L_1$ across the perpendicular bisector of $[ab]$.
Note that $D$ and $D'=L_1'\cup L_2$ have the same perimeter and area.
That is, $D'$ has perimeter $\ell$ and maximal possible area;
in particular, $D'$ is convex.

The following exercise will finish the proof.
\qeds

{

\begin{wrapfigure}{o}{57 mm}
\vskip-5mm
\centering
\includegraphics{mppics/pic-405}
\end{wrapfigure}

\begin{thm}{Exercise}\label{ex:round-disc}
Suppose $D$ is a convex figure such that for any chord $[ab]$ of $D$ the above construction produces a convex figure $D'$.
Show that $D$ is a round disk.
\end{thm}


}

Another popular way to prove that $D$ is a round disk is given by the so-called {}\emph{Steiner's 4-joint method} \cite{blaschke}.

\section{Remarks}\label{sec:H-variation}

It seems that Hausdorff convergence was first introduced by Felix Hausdorff~\cite{hausdorff}.
A couple of years later an equivalent definition was given by Wilhelm Blaschke~\cite{blaschke}.

The following refinement of the definition was introduced by  Zdeněk Frolík \cite{frolik},
later it was rediscovered by Robert Wijsman~\cite{wijsman}.  
This refinement is also called \index{Hausdorff convergence}\emph{Hausdorff convergence};
in fact, it takes an intermediate place between the original Hausdorff convergence and {}\emph{closed convergence}, also introduced by Hausdorff in \cite{hausdorff}.

\begin{thm}{Definition}\label{def:gen-Haus-conv}
Let $(A_n)$ be a sequence of closed sets in a metric space $\spc{X}$.
We say that $(A_n)$ converges to a closed set $A_\infty$ in the sense of Hausdorff if for any $x\in\spc{X}$, we have
$\distfun_{A_n}(x)\to \distfun_{A_\infty}(x)$ as $n\to\infty$.
\end{thm}

For example, suppose $\spc{X}$ is the Euclidean plane and $A_n$ is the circle with radius $n$ and center at the point $(n,0)$.
If we use the standard definition (\ref{def:hausdorff-convergence}), then the sequence $(A_n)$ diverges, but it converges to the $y$-axis in the sense of Definition~\ref{def:gen-Haus-conv}.

The following exercise is analogous to the Blaschke selection theorem (\ref{thm:compact+Hausdorff}) for the modified Hausdorff convergence.

\begin{thm}{Exercise}\label{ex:generalized-selection}
Let $\spc{X}$ be a proper metric space
and $(A_n)_{n=1}^\infty$ be a sequence of closed sets in~$\spc{X}$.
Assume that for some (and therefore any) point  $x\in\spc{X}$, 
the sequence $a_n=\distfun_{A_n}(x)$ is bounded.
Show that the sequence  $(A_n)_{n=1}^\infty$ has a convergent subsequence in the sense of Definition~\ref{def:gen-Haus-conv}.
\end{thm}

\chapter{Space of spaces}

\section{Gromov--Hausdorff metric}

The goal of this section is to cook up a metric space out of metric spaces.
More precisely, we want to define the so-called  Gromov--Hausdorff metric on the set of {}\emph{isometry classes} of compact metric spaces.
(Being isometric is an equivalence relation, 
and an isometry class is an equivalence class with respect to this equivalence relation.)

The obtained metric space will be denoted by $\GH$.
Given two metric spaces $\spc{X}$ and $\spc{Y}$,
denote by $[\spc{X}]$ and $[\spc{Y}]$ their isometry classes;
that is, $\spc{X}'\in [\spc{X}]$ if and only if $\spc{X}'\iso \spc{X}$.
Pedantically, the Gromov--Hausdorff distance from $[\spc{X}]$ 
to $[\spc{Y}]$ should be denoted as $|[\spc{X}]-[\spc{Y}]|_{\GH}$;
but we will write it as $|\spc{X}\z-\spc{Y}|_{\GH}$ and say (not quite correctly) 
``$|\spc{X}\z-\spc{Y}|_{\GH}$ is the Gromov--Hausdorff distance from  $\spc{X}$ 
to  $\spc{Y}$''.
In other words, from now on the term {}\emph{metric space} might also stand for its {}\emph{isometry class}.

The metric on $\GH$ is defined as the maximal metric such that {}\emph{the distance between subspaces in a metric space is not greater than the Hausdorff distance between them}.
Here is a formal definition:

\begin{thm}{Definition}\label{def:GH}
Let $\spc{X}$ and $\spc{Y}$ be compact metric spaces. 
The Gromov--Hausdorff distance $|\spc{X}-\spc{Y}|_{\GH}$ is defined by the following
relation.
 
Given  $r > 0$, we have that $|\spc{X}-\spc{Y}|_{\GH} < r$ if and only if there exist a metric
space $\spc{Z}$ and subspaces $\spc{X}'$ and $\spc{Y}'$ in $\spc{Z}$ that are isometric to $\spc{X}$ and $\spc{Y}$
respectively and such that $|\spc{X}'-\spc{Y}'|_{\Haus\spc{Z}} < r$. 
(Here $|\spc{X}'-\spc{Y}'|_{\Haus\spc{Z}}$ denotes the Hausdorff distance between sets $\spc{X}'$ and $\spc{Y}'$ in $\spc{Z}$.)
\end{thm}

Note that passing to the subspace $\spc{X}'\cup\spc{Y}'$ of $\spc{Z}$ does not affect the definition.
Therefore we can always assume that $\spc{Z}$ is compact.

\begin{thm}{Theorem}\label{thm:GH-is-a-metric}
The set of isometry classes of compact metric spaces equipped with Gromov--Hausdorff metric forms a metric space (which is denoted by $\GH$).

In other words, for arbitrary  compact metric spaces $\spc{X}$, $\spc{Y}$ and $\spc{Z}$ the following conditions hold:

\begin{subthm}{GH-1} $|\spc{X}-\spc{Y}|_{\GH}\ge 0$;
\end{subthm}

\begin{subthm}{GH-2} $|\spc{X}-\spc{Y}|_{\GH}=0$ if and only if $\spc{X}$ is isometric to $\spc{Y}$;
\end{subthm}

\begin{subthm}{GH-3} $|\spc{X}-\spc{Y}|_{\GH}=|\spc{Y}-\spc{X}|_{\GH}$;
\end{subthm}

\begin{subthm}{GH-4} $|\spc{X}-\spc{Y}|_{\GH}+|\spc{Y}-\spc{Z}|_{\GH}\ge |\spc{X}-\spc{Z}|_{\GH}$.
\end{subthm}
\end{thm}


Note that \ref{SHORT.GH-1}, \ref{SHORT.GH-3},
and the ``if''-part of \ref{SHORT.GH-2} follow directly from Definition \ref{def:GH}.
Part \ref{SHORT.GH-4} will be proved in Section~\ref{sec:GH-approx}.
The ``only-if''-part of \ref{SHORT.GH-2} will be proved in Section~\ref{sec:alm-isom}.

Recall that $a\cdot\spc{X}$ denotes $\spc{X}$ \index{scaled space}\emph{scaled} by factor $a>0$;
that is, $a\cdot\spc{X}$ is a metric space with the underlying set of $\spc{X}$ and the metric defined by
\[\dist{x}{y}{a\cdot\spc{X}}\df a\cdot\dist{x}{y}{\spc{X}}.\]

\begin{thm}{Exercise}\label{ex:d_GH-and-diam}
Let $\spc{X}$ be a compact metric space,
$\spc{P}$ be the one-point metric space.

Prove that 
\begin{subthm}{ex:d_GH-and-diam:point}
\[|\spc{X}-\spc{P}|_{\GH}=\tfrac12\cdot \diam \spc{X}.\]

\end{subthm}

\begin{subthm}{ex:d_GH-and-diam:scale}
\[|a\cdot\spc{X}-b\cdot \spc{X}|_{\GH}=\tfrac12\cdot|a-b|\cdot\diam\spc{X}.\]
\end{subthm}


\end{thm}

\begin{thm}{Exercise}\label{ex:rectangle}
Let $\spc{A}_r$ be a rectangle $1$ by $r$ in the Euclidean plane 
and $\spc{B}_r$ be a closed line interval of length $r$.
Show that 
\[|\spc{A}_r-\spc{B}_r|_{\GH}>\tfrac1{10}\]
for all large $r$.
\end{thm}

\begin{thm}{Advanced exercise}\label{ex:GH-inj}
Let $\spc{X}$ and $\spc{Y}$ be compact metric spaces;
denote by $\hat{\spc{X}}$ and $\hat{\spc{Y}}$ their injective envelopes (see the definition on page \pageref{page:InjX}).
Show that 
\[|\hat{\spc{X}}-\hat{\spc{Y}}|_{\GH}\le 2\cdot|\spc{X}- \spc{Y}|_{\GH}.\] 

\end{thm}

\section{Approximations}\label{sec:GH-approx}

\begin{thm}{Definition}\label{ex:defGHR}
Let $\spc{X}$ and $\spc{Y}$ be two metric spaces.
A relation $\approx$ between points in $\spc{X}$ and $\spc{Y}$ is called $\eps$-approximation if the following conditions hold:
\begin{itemize}
\item For any $x\in  \spc{X}$ there is $y\in \spc{Y}$ such that $x\approx y$.
\item For any $y\in  \spc{Y}$ there is $x\in \spc{X}$ such that $x\approx y$.
\item If for some $x, x'\in  \spc{X}$ and $y,y'\in \spc{Y}$ we have $x\approx y$ and $x'\approx y'$, then 
\[\bigl|\dist{x}{x'}{\spc{X}}-\dist{y}{y'}{\spc{Y}}\bigr|<2\cdot\eps.\]
\end{itemize}

\end{thm}

\begin{thm}{Exercise}\label{ex:H-R}
Let $\spc{X}$ and $\spc{Y}$ be two compact metric spaces.
Show that
\[\dist{\spc{X}}{\spc{Y}}{\GH}<\eps\]
if and only if there is an $\eps$-approximation between $\spc{X}$ and $\spc{Y}$.

In other words $\dist{\spc{X}}{\spc{Y}}{\GH}$ is the greatest lower bound of values $\eps>0$ such that  there is an $\eps$-approximation between $\spc{X}$ and $\spc{Y}$.
\end{thm}

\parit{Proof of \ref{GH-4}.}
Suppose that 
\begin{itemize}
\item $\approx_1$ is a relation between points in $\spc{X}$ and $\spc{Y}$,
\item $\approx_2$ is a relation between points in $\spc{Y}$ and $\spc{Z}$.
\end{itemize}
Consider the relation $\approx_3$ between points in $\spc{X}$ and $\spc{Z}$ such that
$x\approx_3 z$ if and only if there is $y\in  \spc{Y}$ such that 
$x\approx_1 y$ and $y\approx_2 z$.

It is straightforward to check that if $\approx_1$ is an $\eps_1$-approximation and $\approx_2$ is an $\eps_2$-approximation, then $\approx_3$ is an $(\eps_1+\eps_2)$-approximation.

Applying \ref{ex:H-R}, we get that if 
\[|\spc{X}-\spc{Y}|_{\GH}<\eps_1
\quad\text{and}\quad
|\spc{Y}-\spc{Z}|_{\GH}<\eps_2
\]
then 
\[|\spc{X}-\spc{Z}|_{\GH}<\eps_1+\eps_2.\]
Hence \ref{GH-4} follows.
\qeds


\section{Almost isometries}\label{sec:alm-isom}

\begin{thm}{Definition} Let $\spc{X}$ and $\spc{Y}$ be metric spaces and $\eps>0$. 
A  map\footnote{possibly noncontinuous} $f\: \spc{X} \z\to \spc{Y}$ is called an \index{almost isometry}\emph{$\eps$-isometry} 
if $f(\spc{X})$ is an $\eps$-net in $\spc{Y}$ and
\[\bigl|\dist{x}{x'}{\spc{X}}-\dist{f(x)}{f(x')}{\spc{Y}}\bigr|<\eps.\]
for any $x,x'\in \spc{X}$.
\end{thm}

\begin{thm}{Exercise}\label{ex:eps-isom}
Let $\spc{X}$ and $\spc{Y}$ be compact metric spaces.

\begin{subthm}{ex:eps-isom:GH>isom}
If $\dist{\spc{X}}{\spc{Y}}{\GH}<\eps$, then there is a $2\cdot\eps$-isometry $f\:\spc{X}\to\spc{Y}$.
\end{subthm}

\begin{subthm}{ex:eps-isom:isom>GH}
If there is an $\eps$-isometry $f\:\spc{X}\to\spc{Y}$, then $\dist{\spc{X}}{\spc{Y}}{\GH}<\eps$.
\end{subthm}

\end{thm}

\parit{Proof of the ``only if''-part in \ref{GH-2}.}
\label{page:GH-2-proof}
Let $\spc{X}$ and $\spc{Y}$ be compact metric spaces.
Suppose that $\dist{\spc{X}}{\spc{Y}}{\GH}<\eps$ for any $\eps>0$;
we need to show that there is an isometry $\spc{X}\to\spc{Y}$.

By \ref{ex:eps-isom:GH>isom}, for each positive integer $n$, we can choose a $\tfrac1n$-isometry $f_n\:\spc{X}\to\spc{Y}$.

Since $\spc{X}$ is compact, 
we can choose a countable dense set
$S$ in~$\spc{X}$.
Applying the diagonal procedure if necessary, we can assume that for every $x \in S$ the sequence $(f_n(x))$ 
converges in $\spc{Y}$. 
Consider the pointwise limit map  $f_\infty \: S \to \spc{Y}$,
 $$f_\infty(x) \df \lim_{n\to\infty} f_n (x)$$ for every $x \in S$. 
Since $$|f_n (x)- f_n (x')|_{\spc{Y}}\lg |x- x'|_\spc{X} \pm\tfrac1n,$$ 
we have 
$$|f_\infty(x)-f_\infty (x')|_{\spc{Y}} 
= \lim_{n\to\infty} |f_n(x)-f_n (x')|_{\spc{Y}} 
= |x -x'|_\spc{X}$$ for all
$x, x' \in S$; 
that is, the map $f_\infty\:S\to \spc{Y}$ is distance-preserving. 
Therefore, $f_\infty$ can be extended to a distance-preserving map from the whole $\spc{X}$ to $\spc{Y}$.

The latter can be done by setting 
$$f_\infty(x)=\lim_{n\to\infty} f_\infty(x_n)$$ 
for some sequence of points $(x_n)$ in $S$
that converges to $x$ in $\spc{X}$.
Indeed, if $x_n\to x$, then $(x_n)$ is Cauchy.
Since $f_\infty$ is distance-preserving, $y_n=f_\infty(x_n)$ is also a Cauchy sequence in $\spc{Y}$;
therefore it converges.
It remains to observe that this construction does not depend on the choice of the sequence $(x_n)$.

This way we obtain a distance-preserving map $f_\infty\:\spc{X}\to \spc{Y}$. 
It remains to show that $f_\infty$ is surjective; that is, $f_\infty(\spc{X})=\spc{Y}$.

The same argument produces a distance-preserving map $g_\infty\:\spc{Y}\z\to \spc{X}$.
If $f_\infty$ is not surjective, then neither is the composition $f_\infty\z\circ g_\infty\:\spc{Y}\to \spc{Y}$.
So $f_\infty \z\circ g_\infty$ is a distance-preserving map from a compact space to itself which is not an isometry.
The latter contradicts \ref{ex:non-contracting-map}. 
\qeds

\section{Convergence}

The Gromov--Hausdorff metric is used to define Gromov--Hausdorff convergence.
Namely, a sequence of compact metric spaces $\spc{X}_n$ converges to compact metric spaces $\spc{X}_\infty$ in the sense of Gromov--Hausdorff if 
\[\dist{\spc{X}_n}{\spc{X}_\infty}{\GH}\to 0\quad\text{as}\quad n\to\infty.\]

This convergence is more important than the metric ---
in all applications, we use only the topology on $\GH$
and we do not care about the particular value of Gromov--Hausdorff distance between spaces.
The following observation follows from \ref{ex:eps-isom}:

\begin{thm}{Observation}\label{obs:GH-e-isom}
A sequence of compact metric spaces $(\spc{X}_n)$ converges to  $\spc{X}_\infty$ in the sense of Gromov--Hausdorff if and only if there is a sequence $\eps_n\to0+$
and an $\eps_n$-isometry $f_n\:\spc{X}_n\to \spc{X}_\infty$ for each $n$.
\end{thm}

In the following exercises {}\emph{converge} means {}\emph{converge in the sense of Gromov--Hausdorff}.

\begin{thm}{Exercise}\label{ex:GH-SC}
\begin{subthm}{ex:GH-SC:circle}
Show that a sequence of compact simply connected length spaces cannot converge to a circle.
\end{subthm}

\begin{subthm}{ex:GH-SC:nonsc-limit}
Construct a sequence of compact simply connected length spaces that converges to a compact non-simply connected space.
\end{subthm}
\end{thm}

\begin{thm}{Exercise}\label{ex:sphere-to-ball}
\begin{subthm}{ex:sphere-to-ball:2}
Show that a sequence of length metrics on the 2-sphere cannot converge to the unit disk.
\end{subthm}

\begin{subthm}{ex:sphere-to-ball:3}
Construct a sequence of length metrics on the 3-sphere that converges to a unit 3-ball.
\end{subthm}

\end{thm}

Given two metric spaces $\spc{X}$ and $\spc{Y}$, we will write $\spc{X}\le \spc{Y}$ if there is a noncontracting map $f\:\spc{X}\to \spc{Y}$;
that is, if 
$$ |x-x'|_{\spc{X}}\le|f(x)-f(x')|_{\spc{Y}}$$
for any $x,x'\in \spc{X}$.

Further, given $\eps>0$, we will write $\spc{X}\le \spc{Y}+\eps$
if there is a map $f\:\spc{X}\to \spc{Y}$ such that 
$$|x-x'|_{\spc{X}}\le|f(x)-f(x')|_{\spc{Y}}+\eps$$
for any $x,x'\in \spc{X}$.

\section{Uniformly totally bonded families}

\begin{thm}{Definition}\label{def:utb}
A family $\spc{Q}$ of (isometry classes) of compact metric spaces is called  \index{uniformly totally bonded family}\emph{uniformly totally bonded} if it meets the following two conditions:

\begin{subthm}{}
spaces in $\spc{Q}$ have uniformly bounded diameters; that is, there is $D\in\RR$ such that
\[\diam\spc{X}\le D\]
for any space $\spc{X}$ in $\spc{Q}$.
\end{subthm}

\begin{subthm}{}
For any $\eps>0$ there is $n\in\NN$ such that any space $\spc{X}$ in $\spc{Q}$ admits an $\eps$-net with at most $n$ points.
\end{subthm}
\end{thm}

\begin{thm}{Exercise}\label{ex:utb+pack}
Let $\spc{Q}$ be a family of compact spaces with uniformly bounded diameters.
Show that $\spc{Q}$ is uniformly totally bonded if for any $\eps>0$ there is $n\in\NN$ such that 
\[\pack_\eps\spc{X}\le n\]
for any space $\spc{X}$ in $\spc{Q}$.
\end{thm}


Fix a real constant $C$.
A Borel measure $\mu$ on a metric space $\spc{X}$ is called \index{doubling space}\emph{$C$-doubling} if
\[\mu[\oBall(p,2\cdot r)]< C\cdot\mu[\oBall(p,r)]\]
for any point $p\in \spc{X}$ and any $r>0$.
A Borel measure is called \index{doubling measure}\emph{doubling} if it is {}\emph{$C$-doubling} for some real constant $C$.

\begin{thm}{Exercise}\label{pr:doubling}
Let $\spc{Q}(C,D)$ be the set of all the compact metric spaces with diameter at most $D$ that admit a $C$-doubling measure.
Show that $\spc{Q}(C,D)$ is totally bounded.
\end{thm}

Recall that we write $\spc{X}\le\spc{Y}$ if there is a distance-nondecreasing map $\spc{X}\to\spc{Y}$.

\begin{thm}{Exercise}\label{pr:under}

\begin{subthm}{pr:under:if}
Let $\spc{Y}$ be a compact metric space.
Show that the set of all spaces $\spc{X}$ such that $\spc{X}\le\spc{Y}$
is uniformly totally bounded.
\end{subthm}

\begin{subthm}{pr:under:only-if}
Show that for any uniformly totally bounded set $\spc{Q}\subset\GH$ there is a compact space $\spc{Y}$
such that $\spc{X}\le\spc{Y}$ for any $\spc{X}$ in $\spc{Q}$.
\end{subthm}

\end{thm}

\section{Gromov's selection theorem}

The following theorem is analogous to Blaschke selection theorems (\ref{thm:compact+Hausdorff}).

\begin{thm}{Gromov selection theorem}\label{thm:gromov-compactness}
Let $\spc{Q}$ be a closed subset of $\GH$.
Then $\spc{Q}$ is compact if and only if it is totally bounded.
\end{thm}

\begin{thm}{Lemma}\label{lem:GH-complete}
The space $\GH$ is complete.
\end{thm}


Let us define gluing of metric spaces that will be used in the proof of the lemma.

Suppose 
$\spc{U}$ and $\spc{V}$ are metric spaces 
with isometric closed sets $A\subset\spc{U}$ and $A'\subset\spc{V}$;
let $\iota\:A\to A'$ be an isometry.
Consider the space $\spc{W}$ of all equivalence classes in $\spc{U}\sqcup\spc{V}$ with the equivalence relation given by $a\sim\iota(a)$ for any $a\in A$.

It is straightforward to check that the following defines a metric on~$\spc{W}$:
\begin{align*}
\dist{u}{u'}{\spc{W}}&\df\dist{u}{u'}{\spc{U}}
\\
\dist{v}{v'}{\spc{W}}&\df\dist{v}{v'}{\spc{V}}
\\
\dist{u}{v}{\spc{W}}&\df\min\set{\dist{u}{a}{\spc{U}}+\dist{v}{\iota(a)}{\spc{V}}}{a\in A}
\end{align*}
where $u,u'\in \spc{U}$ and $v,v'\in \spc{V}$.

The  space $\spc{W}$ is called the \index{gluing}\emph{gluing} of $\spc{U}$ and  $\spc{V}$ along~$\iota$; briefly, we can write
$\spc{W}=\spc{U}\sqcup_\iota\spc{V}$.
If one applies this construction to two copies of one space $\spc{U}$ with a set $A\subset \spc{U}$ and the identity map $\iota\:A\to A$, then the obtained space is called the \index{double}\emph{double} of $\spc{U}$ along~$A$; this space can be denoted by $\sqcup_A^2\spc{U}$.

Note that the inclusions $\spc{U}\hookrightarrow \spc{W}$ and $\spc{V}\hookrightarrow \spc{W}$ are distance preserving.
Therefore we can and will conside $\spc{U}$ and $\spc{V}$ as the subspaces of $\spc{W}$;
this way the subsets $A$ and $A'$ will be identified and denoted further by~$A$.
Note that $A=\spc{U}\cap \spc{V}\subset \spc{W}$.

\parit{Proof.}
Let $(\spc{X}_n)$ be a Cauchy sequence in $\GH$.
Passing to a subsequence if necessary, 
we can assume that $|\spc{X}_n-\spc{X}_{n+1}|_{\GH}<\tfrac1{2^n}$ for each~$n$.
In particular, for each $n$ there is a metric space $\spc{V}_n$ with distance preserving inclusions $\spc{X}_n\hookrightarrow \spc{V}_n$ and $\spc{X}_{n+1}\hookrightarrow \spc{V}_n$ such that
\[|\spc{X}_n-\spc{X}_{n+1}|_{\Haus\spc{V}_n}<\tfrac1{2^n}\]
for each $n$.
Moreover, we may assume that $\spc{V}_n=\spc{X}_n\cup\spc{X}_{n+1}$.

Let us glue $\spc{V}_1$ to $\spc{V}_2$ along $\spc{X}_2$;
to the obtained space glue $\spc{V}_3$ along $\spc{X}_3$, and so on.
The obtained metric space $\spc{W}$
has an underlying set formed by the disjoint union of all $\spc{X}_n$ such that each inclusion $\spc{X}_n\z\hookrightarrow\spc{W}$ is distance preserving and
\[|\spc{X}_n-\spc{X}_{n+1}|_{\Haus\spc{W}}<\tfrac1{2^n}\]
for each $n$.
In particular,
\[|\spc{X}_m-\spc{X}_n|_{\Haus\spc{W}}<\tfrac1{2^{n-1}}\eqlbl{eq:|x_m-X_n|}\] 
if $m>n$.

Denote by $\bar{\spc{W}}$ the completion of $\spc{W}$.
Observe that the union $\spc{X}_1\z\cup \spc{X}_2\cup\z\dots\cup \spc{X}_n$ is compact and \ref{eq:|x_m-X_n|} implies that it forms a $\tfrac1{2^{n-1}}$-net in $\bar{\spc{W}}$.
Whence $\bar{\spc{W}}$ is compact; see \ref{totally-bounded} and \ref{ex:compact-net}.

Applying Blaschke selection theorem (\ref{thm:compact+Hausdorff}),
we can pass to a subsequence of $(\spc{X}_n)$ that converges in $\Haus\bar{\spc{W}}$; denote its limit by $\spc{X}_\infty$.
It remains to observe that $\spc{X}_\infty$ is the Gromov--Hausdorff limit of $(\spc{X}_n)$.
\qeds

\parit{Proof of \ref{thm:gromov-compactness}; ``only if'' part.}
Suppose that there is no sequence $\eps_n\to0$ as described in \ref{def:utb}.
Observe that in this case
there is a sequence of spaces $\spc{X}_n\in\spc{Q}$ such that 
$$\pack_\delta \spc{X}_n\to\infty
\quad\text{as}\quad
n\to\infty$$
for some fixed $\delta>0$.

Since $\spc{Q}$ is compact, 
this sequence has a partial limit, say $\spc{X}_\infty\in\spc{Q}$.
Observe that $\pack_{\delta} \spc{X}_\infty=\infty$.
Therefore, $\spc{X}_\infty$ is not compact --- a contradiction.

\parit{``If'' part.}
Suppose sequence $(\eps_n)$ as in the definition of uniformly totally bonded families (\ref{def:utb}).

Note that $\diam \spc{X}\le \eps_1$ for any $\spc{X}\in \spc{Q}$.
Given a positive integer $n$ consider the set of all metric spaces $\spc{W}_n$
with the number of points at most $n$ and diameter $\le \eps_1$.
Note that $\spc{W}_n$ is a compact set in $\GH$ for each $n$.

Further, a subspace formed by a maximal $\eps_n$-net of any $\spc{X}\in\spc{Q}$ belongs to $\spc{W}_n$.
Therefore, $\spc{W}_n\cap\spc{Q}$ is a compact $\eps_n$-net in  $\spc{Q}$.
That is, $\spc{Q}$ has a compact $\eps$-net for any $\eps>0$.
Since $\spc{Q}$ is closed in a complete space $\GH$, it implies that $\spc{Q}$ is compact.
\qeds

\begin{thm}{Exercise}\label{ex-GH-length}
Show that the space $\GH$ is 

\begin{subthm}{ex-GH-length:length}
length,
\end{subthm}

\begin{subthm}{ex-GH-length:geodesic}
geodesic.
\end{subthm}

\end{thm}

\begin{thm}{Exercise}\label{ex:GH-po}
\begin{subthm}{ex:GH-po:a}
Show that 
$$\dist{\spc{X}}{\spc{Y}}{\GH'}=\inf\set{\eps>0}{\spc{X}\le \spc{Y}+\eps
\quad\text{and}\quad
\spc{Y}\le \spc{X}+\eps}$$
defines a metric on the space of (isometry classes) of compact metric spaces.
\end{subthm}

\begin{subthm}{ex:GH-po:b}
Moreover $\dist{*}{*}{\GH'}$ is equivalent to the Gromov--Hausdorff metric;
that is,
$$|\spc{X}_n-\spc{X}_\infty|_{\GH}\to 0 
\quad\iff\quad 
\dist{\spc{X}_n}{\spc{X}_\infty}{\GH'}\to 0$$ 
as $n\to\infty$.
\end{subthm}
\end{thm}

\section{Universal ambient space}

Recall that a metric space is called universal if it contains an isometric copy of any separable metric space (in particular, any compact metric space).
Examples of universal spaces include Urysohn space and $\ell^\infty$ --- the space of bounded infinite sequences with the metric defined by $\sup$-norm; see \ref{prop:sep-in-urys} and \ref{ex:frechet}.

The following proposition says that the space $\spc{W}$ in Definition~\ref{def:GH} can be exchanged to a fixed universal space.

\begin{thm}{Proposition}\label{prop:GH-with-fixed-Z}
Let $\spc{U}$ be a universal space.
Then for any compact metric spaces $\spc{X}$ and $\spc{Y}$ we have
$$|\spc{X}-\spc{Y}|_{\GH} = \inf \{|\spc{X}'-\spc{Y}'|_{\Haus\spc{U}}\}$$ 
where the greatest lower bound is taken over all pairs of sets $\spc{X}'$ and $\spc{Y}'$ in $\spc{U}$
which isometric to  $\spc{X}$ and $\spc{Y}$ respectively.  
\end{thm}




\parit{Proof of \ref{prop:GH-with-fixed-Z}.}
By the definition (\ref{def:GH}), we have that 
\[|\spc{X}-\spc{Y}|_{\GH} \le \inf \{|\spc{X}'-\spc{Y}'|_{\Haus\spc{U}}\};\]
it remains to prove the opposite inequality.

Suppse $|\spc{X}-\spc{Y}|_{\GH}<\eps$;
let $\spc{X}'$, $\spc{Y}'$ and $\spc{Z}$ be as in \ref{def:GH}.
We can assume that $\spc{Z}=\spc{X}'\cup\spc{Y}'$;
otherwise pass to the subspace $\spc{X}'\cup\spc{Y}'$ of~$\spc{Z}$.
In this case, $\spc{Z}$ is compact;
in particular, it is separable.

Since $\spc{U}$ is universal, there is a distance-preserving embedding of $\spc{Z}$ in $\spc{U}$;
let us keep the same notation for $\spc{X}'$, $\spc{Y}'$, and their images.
It follows that 
\[|\spc{X}'-\spc{Y}'|_{\Haus\spc{U}}<\eps,\]
--- hence the result.
\qeds

\begin{thm}{Exercise}\label{ex:GH-urysohn}
Let $\spc{U}_\infty$ be the Urysohn space.
Given two compact set $A$ and $B$ in $\spc{U}_\infty$ define 
\[\|A-B\|=\inf\{|A-\iota(B)|_{\Haus\spc{U}_\infty}\},\]
where the greatest lower bound is taken for all isometrics $\iota$ of $\spc{U}_\infty$.
Show that $\|{*}\z-{*}\|$ defines a pseudometric%
\footnote{The value $\|A-B\|$ is called \emph{Hausdorff distance up to isometry} from $A$ to $B$ in $\spc{U}_\infty$.}
on nonempty compact subsets of $\spc{U}_\infty$ and its corresponding metric space is isometric to $\GH$.
\end{thm}

\section{Remarks}

Suppose $\spc{X}_n\GHto \spc{X}_\infty$, then there is a metric on the disjoint union 
\[\bm{X}=\bigsqcup_{n\in \NN\cup\{\infty\}} \spc{X}_n\] 
that satisfies the following property:

\begin{thm}{Property}\label{propery:GH}
The restriction of metric on each $\spc{X}_n$ and $\spc{X}_\infty$ coincides with its original metric 
and $\spc{X}_n\Hto \spc{X}_\infty$ as subsets in $\bm{X}$.
\end{thm}


Indeed, since $\spc{X}_n\GHto \spc{X}_\infty$, there is a metric on $\spc{V}_n=\spc{X}_n\sqcup \spc{X}_\infty$ such that the restriction of metric on each $\spc{X}_n$ and $\spc{X}_\infty$ coincides with its original metric and $\dist{\spc{X}_n}{\spc{X}_\infty}{\Haus\spc{V}_n}<\eps_n$ for some sequence $\eps_n\to 0$.
Gluing all $\spc{V}_n$ along $\spc{X}_\infty$, we obtain the required space $\bm{X}$.

In other words, the metric on $\bm{X}$ defines the convergence $\spc{X}_n\z\GHto \spc{X}_\infty$.
This metric makes it possible to talk about limits of sequences $x_n\in \spc{X}_n$ as $n\to\infty$, as well as weak limits of a sequence of Borel measures $\mu_n$ on $\spc{X}_n$ and so on.

For that reason, it is useful to define convergence by specifying the metric on $\bm{X}$ that satisfies the property
for the variation of Hausdorff convergence described in Section~\ref{sec:H-variation}.
This approach is very flexible;
in particular, it can be used to define Gromov--Hausdorff convergence of arbitrary metric spaces (net necessarily compact).

In this case, a limit space for this generalized convergence is not uniquely defined.
\begin{figure}[h!]
\vskip-0mm
\centering
\includegraphics{mppics/pic-500}
\end{figure}
For example, if each space $\spc{X}_n$ in the sequence is isometric to the half-line, then its limit might be isometric to the half-line or the whole line.
The first convergence is evident and the second could be guessed from the diagram.



Often the isometry class of the limit can be fixed by marking a point $p_n$ in each space $\spc{X}_n$, it is called \index{pointed convergence}\emph{pointed Gromov--Hausdorff convergence} --- we say that $(\spc{X}_n,p_n)$ converges to $(\spc{X}_\infty,p_\infty)$ if there is a metric on $\bm{X}$ such that $\spc{X}_n\Hto \spc{X}_\infty$ and $p_n\to p_\infty$.
For example, the sequence $(\spc{X}_n,p_n)=(\RR_+,0)$ converges to $(\RR_+,0)$, while $(\spc{X}_n,p_n)=(\RR_+,n)$ converges to $(\RR,0)$.

The pointed convergence works nicely only for proper metric spaces;
the following theorem is an analog of Gromov's selection theorem for this convergence.

\begin{thm}{Theorem}\label{thm:pointed-gromov-compactness}%
Let $\spc{Q}$ be a set of isometry classes of pointed proper metric spaces
$(\spc{X},p)$.
Assume that for any $R>0$, the $R$-balls in the spaces centered at the marked points form a uniformly totally bounded family of spaces.
Then $\spc{Q}$ is precompact with respect to pointed Gromov--Hausdorff convergence. 
\end{thm}








\chapter{Injective spaces}

{}\emph{Injective spaces} (also known as {}\emph{hyperconvex spaces}) are the metric analog of convex sets.

This lecture is based on a paper by John Isbell \cite{isbell}.

\section{Admissible and extremal functions}

Let $\spc{X}$ be a metric space.
A function $r\:\spc{X}\to\RR$ is called \label{page:admissible function}\index{admissible function}\emph{admissible} if the following inequality
\[r(x)+r(y)\ge \dist{x}{y}{\spc{X}}\eqlbl{eq:admissible}\]
holds for any $x,y\in \spc{X}$.

\begin{thm}{Observation}\label{obs:admissible}

\begin{subthm}{obs:admissible:nonnegative}
Any admissible function is nonnegative.
\end{subthm}

\begin{subthm}{obs:admissible:balls}
If $\spc{X}$ is a geodesic space, then a function $r\:\spc{X}\to\RR$ is admissible if and only if 
\[\cBall[x,r(x)]\cap\cBall[y,r(y)]\ne \emptyset\]
for any $x,y\in \spc{X}$.
\end{subthm}
 
\end{thm}

\parit{Proof.} For \ref{SHORT.obs:admissible:nonnegative}, take $x=y$ in \ref{eq:admissible}.

Part \ref{SHORT.obs:admissible:balls} follows from the triangle inequality and the existence of a geodesic $[xy]$.
\qeds

A minimal admissible function will be called \label{page:extremal function}\index{extremal function}\emph{extremal}.
More precisely, an admissible function $r\:\spc{X}\to\RR$ is extremal 
if for any admissible function $s\:\spc{X}\to\RR$ we have
\[s\le r\quad\Longrightarrow\quad s=r.\]


\begin{thm}{Key exercise}\label{ex:+-c}
Let $r$ be an extremal function and $s$ an admissible function on a metric space $\spc{X}$.
Suppose that $r\ge s-c$ for some constant $c$.
Show that $c\ge 0$ and $r\le s+c$.
\end{thm}


\begin{thm}{Observations}\label{obs:extremal}
Let $\spc{X}$ be a metric space.

\begin{subthm}{obs:extremal:distfun}
For any point $p\in\spc{X}$
the distance function $r\z=\distfun_p$ is extremal.
\end{subthm}

\begin{subthm}{lem:extremal-lipschitz}
Any extremal function $r$ on $\spc{X}$ is \index{1-Lipschitz function}\emph{1-Lipschitz};
that is,
\[|r(p)-r(q)|\le \dist{p}{q}{}\]
for any $p,q\in\spc{X}$.
In other words, any extremal function is an extension function; see the definition on page \pageref{page:extension function}.
\end{subthm}

\begin{subthm}{lem:opposite}
Let $r$ be an extremal function on $\spc{X}$.
Then for any point $p\in\spc{X}$ and any $\delta>0$, there is a point $q\in \spc{X}$
such that 
\[r(p)+r(q)<\dist{p}{q}{\spc{X}}+\delta.\]
Moreover, if $\spc{X}$ is compact, then there is $q$ such that 
\[r(p)+r(q)=\dist{p}{q}{\spc{X}}.\]
\end{subthm}


\begin{subthm}{obs:extremal:below}
For any admissible function $s$ there is an extremal function $r$ such that $r\le s$.
\end{subthm}

\end{thm}

\parit{Proof; \ref{SHORT.obs:extremal:distfun}.}
By the triangle inequality, \ref{eq:admissible} holds;
that is, $r=\distfun_p$ is an admissible function.

Further, if $s\le r$ is another admissible function, then $s(p)=0$ and \ref{eq:admissible} implies that $s(x)\z\ge\dist{p}{x}{}$.
Whence $s=r$.

\parit{\ref{SHORT.lem:extremal-lipschitz}.}
By \ref{SHORT.obs:extremal:distfun}, $\distfun_p$ is admissible.
Since $r$ is admissible, we have that
\[r\ge \distfun_p-r(p).\]
Since $r$ is extremal, \ref{ex:+-c} implies that
\[r\le \distfun_p+r(p),\]
or, equivalently,
\[r(q)-r(p)\le \dist{p}{q}{}\]
for any $p,q\in\spc{X}$.
The same way we can show that
$r(p)-r(q)\le \dist{p}{q}{}$.
Whence the statement follows.

\parit{\ref{SHORT.lem:opposite}.}
Again, by \ref{SHORT.obs:extremal:distfun}, $\distfun_p$ is an extremal function.
Arguing by contradiction, assume 
\[r(q)\ge \distfun_p(q)-r(p)+\delta\]
for any $q$.
By \ref{ex:+-c}, we get that
\[r(q)\le \distfun_p(q)+r(p)-\delta\]
for any $q$.
Taking $q=p$, we get $r(p)\le r(p)-\delta$, a contradiction.

Suppose $\spc{X}$ is compact.
Denote by $q_n$ the point provided by the first part of \ref{SHORT.lem:opposite} for $\delta=\tfrac1n$.
Let $q$ be a partial limit of $q_n$. 
Then 
\[r(p)+r(q)\le\dist{p}{q}{\spc{X}}.\]
Since $r$ is admissible, the opposite inequality holds;
whence the second part of \ref{SHORT.lem:opposite} follows.

\parit{\ref{SHORT.obs:extremal:below}.}
Follows by Zorn's lemma. 
\qeds

\section{Injective spaces}

\begin{thm}{Definition}\label{def:injective}
A metric space $\spc{Y}$ is called \index{injective space}\emph{injective} if for any metric space $\spc{X}$ and any of its subspaces $\spc{A}$
any short map $f\:\spc{A}\to \spc{Y}$ can be extended to a short map $F\:\spc{X}\to \spc{Y}$;
that is, $f=F|_{\spc{A}}$.
\end{thm}

\begin{thm}{Exercise}\label{ex:inj=complete-geodesic-contractible}
Show that any injective space is 

\begin{subthm}{ex:inj=complete-geodesic-contractible:complete}
complete,
\end{subthm}

\begin{subthm}{ex:inj=complete-geodesic-contractible:geodesic}
geodesic, and
\end{subthm}

\begin{subthm}{ex:inj=complete-geodesic-contractible:contractible}
contractible.
\end{subthm}
\end{thm}


\begin{thm}{Exercise}\label{ex:injective-spaces}
Show that the following spaces are injective:
\begin{subthm}{ex:injective-spaces:R}
the real line;
\end{subthm}

\begin{subthm}{ex:injective-spaces:tree}
complete metric tree;
\end{subthm}

\begin{subthm}{ex:injective-spaces:ell-infty}
coordinate plane with the metric induced by the $\ell^\infty$-norm.
\end{subthm}

\end{thm}

The following exercise deals with metric spaces that in some sense dual to the injective spaces. 

\begin{thm}{Exercise}\label{ex:ultrametric}
Suppose that a metric space $\spc{X}$ satisfies the following property:
For any subspace $\spc{A}$ in $\spc{X}$ and any other metric space $\spc{Y}$, any short map $f\:\spc{A}\to \spc{Y}$ can be extended to a short map $F\:\spc{X}\to \spc{Y}$.

Show that $\spc{X}$ is an \index{ultrametric space}\emph{ultrametric space};
that is, the following strong version of the triangle inequality
\[\dist{x}{z}{\spc{X}}
\le
\max\{\,\dist{x}{y}{\spc{X}},\dist{y}{z}{\spc{X}}\,\}\]
holds for any three points $x,y,z\in \spc{X}$.
\end{thm}

\begin{thm}{Theorem}\label{thm:injective=hyperconvex}
For any metric space $\spc{Y}$ the following condition are equivalent:

\begin{subthm}{thm:injective=hyperconvex:injective}
$\spc{Y}$ is injective
\end{subthm}


\begin{subthm}{thm:injective=hyperconvex:extremal}
If $r\:\spc{Y}\to\RR$ is an extremal function, then there is a point $p\in \spc{Y}$ such that 
\[\dist{p}{x}{}\le r(x)\]
for any $x\in \spc{Y}$.
\end{subthm}

\begin{subthm}{thm:injective=hyperconvex:balls}
$\spc{Y}$ is \index{hyperconvex space}\emph{hyperconvex};
that is, if $\{\cBall[x_\alpha,r_\alpha]\}_{\alpha\in\IndexSet}$ is a family of closed balls in $\spc{Y}$ such that 
 \[r_\alpha+r_\beta\ge \dist{x_\alpha}{x_\beta}{}\]
 for any $\alpha,\beta\in \IndexSet$,
then all the balls in the family $\{\cBall[x_\alpha,r_\alpha]\}_{\alpha\in\IndexSet}$ have a common point.
\end{subthm}

\end{thm}

\parit{Proof.} We will prove implications 
\ref{SHORT.thm:injective=hyperconvex:injective}$\Rightarrow$\ref{SHORT.thm:injective=hyperconvex:extremal}$\Rightarrow$\ref{SHORT.thm:injective=hyperconvex:balls}$\Rightarrow$\ref{SHORT.thm:injective=hyperconvex:injective}.

\parit{\ref{SHORT.thm:injective=hyperconvex:injective}$\Rightarrow$\ref{SHORT.thm:injective=hyperconvex:extremal}.}
Let us apply the definition of injective space to a one-point extension of $\spc{Y}$.
It follows that for any extension function $r\:\spc{Y}\to\RR$ there is a point $p\in \spc{Y}$ such that 
\[\dist{p}{x}{}\le r(x)\]
for any $x\in \spc{Y}$.
By \ref{lem:extremal-lipschitz}, any extremal function is an extension function, whence the implication follows.

\parit{\ref{SHORT.thm:injective=hyperconvex:extremal}$\Rightarrow$\ref{SHORT.thm:injective=hyperconvex:balls}.}
By \ref{obs:admissible:balls}, part \ref{SHORT.thm:injective=hyperconvex:balls} is equivalent to the following statement:
\begin{itemize}
 \item If $r\:\spc{Y}\to\RR$ is an admissible function, then there is a point $p\in \spc{Y}$ such that 
\[\dist{p}{x}{}\le r(x)\eqlbl{eq:|p-x|=<r(x)}\]
for any $x\in \spc{Y}$.
\end{itemize}
Indeed, set $r(x)\df\inf\set{r_\alpha}{x_\alpha=x}$.
(If $x_\alpha\ne x$ for any $\alpha$, then $r(x)=\infty$.)
The condition in \ref{SHORT.thm:injective=hyperconvex:balls} implies that $r$ is admissible.
It remains to observe that $p\in \cBall[x_\alpha,r_\alpha]$ for every $\alpha$ if and only if \ref{eq:|p-x|=<r(x)} holds.

By \ref{obs:extremal:below}, for any admissible function $r$ there is an extremal function $\bar r\le r$;
whence \ref{SHORT.thm:injective=hyperconvex:extremal}$\Rightarrow$\ref{SHORT.thm:injective=hyperconvex:balls}.

\parit{\ref{SHORT.thm:injective=hyperconvex:balls}$\Rightarrow$\ref{SHORT.thm:injective=hyperconvex:injective}.}
Arguing by contradiction, suppose $\spc{Y}$ is not injective;
that is, there is a metric space $\spc{X}$ with a subset $\spc{A}$
such that a short map $f\:\spc{A}\to \spc{Y}$ cannot be extended to a short map $F\:\spc{X}\to \spc{Y}$.
By Zorn's lemma, we may assume that $\spc{A}$ is a maximal subset; that is, the domain of $f$ cannot be enlarged by a single point.%
\footnote{In this case, $\spc{A}$ must be closed, but we will not use it.}

Fix a point $p$ in the complement $\spc{X}\backslash \spc{A}$.
To extend $f$ to $p$, we need to choose $f(p)$ in the intersection of the balls 
$\cBall[f(x),r(x)]$, where $r(x)=\dist{p}{x}{}$.
Therefore, this intersection for all $x\in \spc{A}$ has to be empty.

Since $f$ is short, we have that 
\begin{align*}
r(x)+r(y)&\ge \dist{x}{y}{\spc{X}}\ge
\\
&\ge \dist{f(x)}{f(y)}{\spc{Y}}.
\end{align*}
Therefore, by \ref{SHORT.thm:injective=hyperconvex:balls} the balls 
$\cBall[f(x),r(x)]$ have a common point --- a contradiction. 
\qeds

\begin{thm}{Exercise}\label{ex:one-point-gluing}
Suppose a length space $\spc{W}$ has two subspaces $\spc{X}$ and $\spc{Y}$ such that $\spc{X}\cup\spc{Y}=\spc{W}$ and $\spc{X}\cap\spc{Y}$ is a one-point set.
Assume $\spc{X}$ and $\spc{Y}$ are injective.
Show that  $\spc{W}$ is injective
\end{thm}

\begin{thm}{Exercise}\label{ex:urysohn-hyperconvex}
Show that the $d$-Urysohn space is {}\emph{finitely hyperconvex} but not {}\emph{countably hyperconvex};
that is, the condition in \ref{thm:injective=hyperconvex:balls} holds for any finite family of balls, but may not hold for a countable family.
Conclude that the $d$-Urysohn space is not injective.

Try to do the same for the Urysohn space.
\end{thm}



\section{Space of extremal functions}

Let $\spc{X}$ be a metric space.
Consider the space $\Inj \spc{X}$ of extremal functions on $\spc{X}$ equipped with sup-norm; \label{page:InjX}
that is,
\[\dist{f}{g}{\Inj \spc{X}}\df\sup\set{|f(x)-g(x)|}{x\in \spc{X}}.\]

Recall that by \ref{obs:extremal:distfun}, any distance function is extremal.
It follows that the map $x\mapsto \distfun_x$ produces a distance-preserving embedding $\spc{X}\hookrightarrow\Inj \spc{X}$.
So we can (and will) treat $\spc{X}$ as a subspace of $\Inj \spc{X}$,
or, equivalently, $\Inj \spc{X}$ as an extension of $\spc{X}$.

Since any extremal function is 1-Lipschitz, for any $f\in \Inj \spc{X}$ and $p\in \spc{X}$, we have that
$f(x)\le f(p)+\distfun_p(x)$.
By \ref{ex:+-c}, we also get $f(x)\ge -f(p)+\distfun_p(x)$.
Therefore
\[
\begin{aligned}
\dist{f}{p}{\Inj \spc{X}}&=\sup\set{|f(x)-\distfun_p(x)|}{x\in \spc{X}}=
\\
&=f(p).
\end{aligned}
\eqlbl{eq:f(p)=|f-p|}
\]
In particular, the statement in \ref{lem:opposite} can be written as 
\[\dist{f}{p}{\Inj\spc{X}}+\dist{f}{q}{\Inj\spc{X}}<\dist{p}{q}{\Inj\spc{X}}+\delta.\]

\begin{thm}{Exercise}\label{ex:Inj(compact)}
Let $\spc{X}$ be a metric space.
Show that $\Inj\spc{X}$ is compact if and only if so is $\spc{X}$.
\end{thm}

\begin{thm}{Exercise}\label{ex:tripod+square}
Describe the set of all extremal functions on a metric space $\spc{X}$ and the metric space $\Inj \spc{X}$ in each of the following case:

\begin{subthm}{ex:tripod+square:tripod} 
$\spc{X}$ is a metric space with exactly three points $a,b,c$ such that 
\[\dist{a}{b}{\spc{X}}=\dist{b}{c}{\spc{X}}=\dist{c}{a}{\spc{X}}=1.\]
\end{subthm}

\begin{subthm}{ex:tripod+square:square}
$\spc{X}$ is  a metric space with exactly four points $p,q,x,y$ such that 
\[\dist{p}{x}{\spc{X}}=\dist{p}{y}{\spc{X}}=\dist{q}{x}{\spc{X}}=\dist{q}{x}{\spc{X}}=1\]
and
\[\dist{p}{q}{\spc{X}}=\dist{x}{y}{\spc{X}}=2.\]
\end{subthm}

\end{thm}

\begin{thm}{Proposition}\label{prop:InjX-is-injective}
For any metric space $\spc{X}$, its extension $\Inj\spc{X}$ is  injective.
\end{thm}

\begin{thm}{Lemma}\label{lem:r|X-extremal}
Let $\spc{X}$ be a metric space.
Suppose that $r$ is an extremal function on $\Inj \spc{X}$.
Then $r|_\spc{X}\in \Inj \spc{X}$;
that is, the restriction of $r$ to $\spc{X}$ is an extremal function.
\end{thm}

\parit{Proof.}
Arguing by contradiction, suppose that there is an admissible function $s\:\spc{X}\to \RR$ such that $s(x)\le r(x)$ for any $x\in\spc{X}$ and $s(p)\z< r(p)$ for some point $p\in\spc{X}$.
Consider another function $\bar r\:\Inj \spc{X}\to\RR$ such that $\bar r(f)\df r(f)$ if $f\ne p$ and $\bar r(p)\df s(p)$.

Let us show that $\bar r$ is admissible; that is, 
\[\dist{f}{g}{\Inj \spc{X}}\le\bar r(f)+\bar r(g)
\eqlbl{r-admissible}\]
for any $f,g\in \Inj \spc{X}$.

Since $r$ is admissible and $\bar r= r$ on $(\Inj \spc{X})\backslash \{p\}$, it is sufficient to prove \ref{r-admissible} if $f\ne g=p$.
By \ref{eq:f(p)=|f-p|}, we have $\dist{f}{p}{\Inj \spc{X}}=f(p)$.
Therefore, \ref{r-admissible} boils down to the following inequality
\[r(f)+s(p)\ge f(p).\eqlbl{eq:r(f)+s(p)>=f(p)}\]
for any $f\in\Inj \spc{X}$.

Fix small $\delta>0$. 
Let $q\in\spc{X}$ be the point provided by \ref{lem:opposite}.
Then
\begin{align*}
r(f)+s(p)&\ge [r(f)-r(q)]+[r(q)+s(p)]\ge
\intertext{since $r$ is 1-Lipschitz, and $r(q)\ge s(q)$, we can continue}
&\ge -\dist{q}{f}{\Inj \spc{X}}+[s(q)+s(p)]\ge
\intertext{by \ref{eq:f(p)=|f-p|} and since $s$ is admissible}
&\ge -f(q)+\dist{p}{q}{}>
\intertext{by \ref{lem:opposite}}
&> f(p)-\delta.
\end{align*}
Since $\delta>0$ is arbitrary, \ref{eq:r(f)+s(p)>=f(p)} and \ref{r-admissible} follow.

Summarizing: the function $\bar r$ is admissible, $\bar r\le r$ and $\bar r(p)<r(p)$;
that is, $r$ is not extremal --- a contradiction.
\qeds

\parit{Proof of \ref{prop:InjX-is-injective}.}
Choose an extremal function $r\:\Inj\spc{X}\to\RR$.
Set $s\z\df r|_{\spc{X}}$.
By \ref{lem:r|X-extremal}, $s\in \Inj\spc{X}$;
that is, $s$ is extremal.
By \ref{thm:injective=hyperconvex:extremal},
it is sufficient to show that  
\[r(f)\ge\dist{s}{f}{\Inj\spc{X}}
\eqlbl{eq:r(f)>=| r-f|}\]
for any $f\in\Inj\spc{X}$.

Since $r$ is $1$-Lipschitz (\ref{lem:extremal-lipschitz}) we have that
\[
s(x)-f(x)=r(x)-\dist{f}{x}{\Inj \spc{X}}\le r(f).
\]
for any $x\in\spc{X}$.
Since $r$ is admissible we have that
\[
s(x)-f(x)=r(x)-\dist{f}{x}{\Inj \spc{X}}\ge -r(f).
\]
for any $x\in\spc{X}$.
That is, $|s(x)-f(x)|\le r(f)$ for any $x\in \spc{X}$.
Recall that
\[\dist{s}{f}{\Inj \spc{X}}
\df
\sup\set{|s(x)-f(x)|}{x\in\spc{X}};\] 
hence \ref{eq:r(f)>=| r-f|} follows.
\qeds

\begin{thm}{Exercise}\label{ex:4-on-a-line}
Let $\spc{X}$ be a compact metric space.
Show that for any two points $f,g\in\Inj \spc{X}$ lie on a geodesic $[pq]$ with $p,q\in \spc{X}$.
\end{thm}

\section{Injective envelope}

An extension $\spc{E}$ of a metric space $\spc{X}$ will be called its \index{injective envelope}\emph{injective envelope} if $\spc{E}$ is an injective space and there is no proper injective subspace of $\spc{E}$ that contains $\spc{X}$.

Two injective envelopes $e\:\spc{X}\hookrightarrow \spc{E}$ and $f\:\spc{X}\hookrightarrow \spc{F}$ are called  equivalent if there is an isometry $\iota\: \spc{E}\to\spc{F}$ such that $f=\iota\circ e$.

\begin{thm}{Theorem}\label{thm:inj-envelope}
For any metric space $\spc{X}$, its extension $\Inj\spc{X}$ is an injective envelope.

Moreover, any other injective envelope of $\spc{X}$ is equivalent to $\Inj\spc{X}$.
\end{thm}

\parit{Proof.} 
Suppose $S\subset \Inj\spc{X}$ is an injective subspace containing $\spc{X}$.
Since $S$ is injective, there is a short map $w\:\Inj\spc{X}\to S$ that fixes all points in $\spc{X}$.

Suppose that $w\:f\mapsto f'$; observe that $f(x)\ge f'(x)$ for any $x\in \spc{X}$.
Since $f$ is extremal, $f=f'$;
that is, $w$ is the identity map and therefore $S=\Inj\spc{X}$.

Assume we have another injective envelope $e\:\spc{X}\hookrightarrow \spc{E}$.
Then there are short maps $v\:\spc{E}\to \Inj\spc{X}$ and $w\:\Inj\spc{X}\to \spc{E}$ such that $x=v\circ e(x)$ and $e(x)=w(x)$ for any $x\in\spc{X}$.
From above, the composition $v\circ w$ is the identity on $\Inj\spc{X}$.
In particular, $w$ is distance-preserving.

The composition $w\circ v\:\spc{E}\to \spc{E}$ is a short map that fixes points in $e(\spc{X})$.
Since $e\:\spc{X}\hookrightarrow \spc{E}$ is an injective envelope, the composition $w\circ v$ and therefore $w$ are onto.
Whence $w$ is an isometry.
\qeds

\begin{thm}{Exercise}\label{ex:d-p-inclusion}
Suppose $\spc{X}$ is a subspace of a metric space $\spc{U}$.
Show that the inclusion $\spc{X}\hookrightarrow\spc{U}$ can be extended to a distance-preserving inclusion $\Inj\spc{X}\hookrightarrow\Inj\spc{U}$.
\end{thm}


\section{Remarks}

Injective spaces were introduced by Nachman Aronszajn and Prom Panitchpakdi \cite{aronszajn-panitchpakdi}.
The injective envelope was introduced by John Isbell \cite{isbell}.
It was rediscovered a couple of times since then;
as a result the injective envelope has many other names including \index{tight span}\emph{tight span} and \index{hyperconvex hull}\emph{hyperconvex hull}.



\chapter{Definitions}

In this lecture we give some conventions used further
and remind some definitions related to metric spaces.

We assume some prior knowledge of metric spaces.
For a more detailed introduction, we recommend the first couple of chapters in the book by Dmitri Burago, Yuri Burago, and Sergei Ivanov \cite{burago-burago-ivanov}.

\section{Metric spaces}
\label{sec:metric spaces}

The distance between two points $x$ and $y$ in a metric space $\spc{X}$ will be denoted by $\dist{x}{y}{}$ or $\dist{x}{y}{\spc{X}}$.
The latter notation is used if we need to emphasize 
that the distance is taken in the space~${\spc{X}}$.

Let us recall the definition of metric. 

\begin{thm}{Definition}\label{def:metric}
A \index{metric}\emph{metric} on a set $\spc{X}$ is a real-valued function $(x,y)\z\mapsto\dist{x}{y}{\spc{X}}$ that satisfies the following conditions for any three points $x,y,z\in \spc{X}$:

\begin{subthm}{metric>=0}
$\dist{x}{y}{\spc{X}}\ge 0$,
\end{subthm}

\begin{subthm}{metric=0} $\dist{x}{y}{\spc{X}}= 0$ $\iff$ $x=y$,
\end{subthm}

\begin{subthm}{metric:sym} $\dist{x}{y}{\spc{X}}=\dist{y}{x}{\spc{X}}$,
\end{subthm}

\begin{subthm}{metric:triangle} $\dist{x}{y}{\spc{X}}+\dist{y}{z}{\spc{X}}\ge\dist{x}{z}{\spc{X}}$.
\end{subthm}

\end{thm}

Recall that a \index{metric space}\emph{metric space} is a set with a metric on it.
The elements of the set are called \emph{points}. 
Most of the time we keep the same notation for the metric space and its underlying set.

The function 
\[\distfun_x\:y\mapsto \dist{x}{y}{}\]
is called the \index{distance function}\emph{distance function} from~$x$. 

Given $R\in[0,\infty]$ and $x\in \spc{X}$, the sets
\begin{align*}
\oBall(x,R)&=\{y\in \spc{X}\mid \dist{x}{y}{}<R\},
\\
\cBall[x,R]&=\{y\in \spc{X}\mid \dist{x}{y}{}\le R\}
\end{align*}
are called, respectively, the  \index{open ball}\emph{open} and  the \index{closed ball}\emph{closed  balls}   of radius $R$ with center~$x$.
If we need to emphasize that these balls are taken in the metric space $\spc{X}$,
we write 
\[\oBall(x,R)_{\spc{X}}\quad\text{and}\quad\cBall[x,R]_{\spc{X}}.\]

\begin{thm}{Exercise}\label{ex:quad-inq}
Show that
\[\dist{p}{q}{\spc{X}}+\dist{x}{y}{\spc{X}}\le\dist{p}{x}{\spc{X}}+\dist{p}{y}{\spc{X}}+\dist{q}{x}{\spc{X}}+\dist{q}{y}{\spc{X}}\]
for any four points $p$, $q$, $x$, and $y$ in a metric space $\spc{X}$.
\end{thm}

\section{Variations of definition}

\parbf{Pseudometris.}
A metric for which the distance between two distinct points can be zero is called a \index{pseudometric}\emph{pseudometric}.
In other words, to define pseudometric, we need to remove condition \ref{SHORT.metric=0} from \ref{def:metric}.

The following observation shows that
nearly any question about pseudometric spaces can be reduced to a question about genuine metric spaces.

Assume $\spc{X}$ is a pseudometric space.
Consider an equivalence relation $\sim$ on $\spc{X}$ defined by
\[x\sim y\quad\iff\quad\dist{x}{y}{}=0.\] 
Note that if $x\sim x'$, then $\dist{y}{x}{}=\dist{y}{x'}{}$ for any $y\in\spc{X}$.
Thus, $\dist{*}{*}{}$ defines a metric on the
quotient set $\spc{X}/{\sim}$.
This way we obtain a metric space $\spc{X}'$.
The space $\spc{X}'$ is called the 
\emph{corresponding metric space} for the pseudometric space $\spc{X}$.
Often we do not distinguish between $\spc{X}'$ and~$\spc{X}$. 

\parbf{$\bm{\infty}$-metrics.}
One may also consider metrics with values in $\RR\cup\{\infty\}$;
we might call them \index{metric!$\infty$-metric}\emph{$\infty$-metrics}, but most of the time we use the term {}\emph{metric}.

Again nearly any question about $\infty$-metric spaces can be reduced to a question about genuine metric spaces. 

Set 
\[x\approx y\quad\iff\quad\dist{x}{y}{}<\infty;\]
it defines another equivalence relation on $\spc{X}$.
The equivalence class of a point $x\in\spc{X}$ will be called the \index{metric component}\emph{metric component} 
 of $x$; it will be denoted by $\spc{X}_x$.
One could think of $\spc{X}_x$ as  $\oBall(x,\infty)_{\spc{X}}$ --- the open ball centered at $x$ and radius $\infty$ in $\spc{X}$.

It follows that any $\infty$-metric space is a {}\emph{disjoint union} of genuine metric spaces --- the metric components of the original $\infty$-metric space.

\begin{thm}{Exercise}\label{ex:pseudo-infty-metric}
Given two sets $A$ and $B$ on the plane, set 
\[\dist{A}{B}{}=\mu(A\bigtriangleup B),\]
where $\mu$ denotes the Lebesgue measure and $\bigtriangleup$ denotes symmetric difference
\[A\bigtriangleup B\df(A\cup B)\setminus(B\cap A).\]

\begin{subthm}{ex:pseudo-infty-metric:pseudo}
Show that $\dist{*}{*}{}$ is a pseudometric on the set of bounded closed subsets.
\end{subthm}

\begin{subthm}{ex:pseudo-infty-metric:infty}
Show that $\dist{*}{*}{}$ is an $\infty$-metric on the set of all open subsets.
\end{subthm}
\end{thm}

\section{Completeness}

A metric space $\spc{X}$ is called \index{complete space}\emph{complete} if every Cauchy sequence of points in $\spc{X}$ converges in $\spc{X}$.

\begin{thm}{Exercise}\label{ex:almost-min}
Suppose that $\rho$ is a positive continuous function on a complete metric space $\spc{X}$ and $\eps>0$.
Show that there is a point $x\in \spc{X}$ such that 
\[\rho(x)<(1+\eps)\cdot\rho(y)\]
for any point $y\in \oBall(x,\rho(x))$.
\end{thm}

Most of the time we will assume that a metric space is complete.
The following construction produces a complete metric space $\bar{\spc{X}}$ for any given metric space $\spc{X}$.


\parbf{Completion.}
Given a metric space $\spc{X}$, 
consider the set $\spc{C}$ of all Cauchy sequences in $\spc{X}$.
Note that for any two Cauchy sequences $(x_n)$ and $(y_n)$ the right-hand side in \ref{eq:cauchy-dist} is defined;
moreover, it defines a pseudometric on~$\spc{C}$
\[\dist{(x_n)}{(y_n)}{\spc{C}}\df\lim_{n\to\infty}\dist{x_n}{y_n}{\spc{X}}.\eqlbl{eq:cauchy-dist}\]
The corresponding metric space $\bar{\spc{X}}$ is called \index{completion}\emph{completion} of $\spc{X}$.

Note that the original space $\spc{X}$ forms a dense subset in its completion $\bar{\spc{X}}$.
More precisely,  for each point $x\in\spc{X}$ one can consider a constant sequence $x_n=x$ which is Cauchy.
It defines a natural map $\spc{X}\to \bar{\spc{X}}$.
It is easy to check that this map is distance-preserving.
In particular, we can (and will) consider $\spc{X}$ as a subset of $\bar{\spc{X}}$.

\begin{thm}{Exercise}\label{ex:complete-completion}
Show that the completion of a metric space is complete.
\end{thm}


\section{Compact spaces}

Let us recall few equivalent definitions of compact metric spaces.

\begin{thm}{Definition}\label{def:compact}
A metric space $\spc{K}$ is compact if and only if one of the following equivalent conditions hold:

\begin{subthm}{}
 Every open cover of $\spc{K}$ has a finite subcover.
\end{subthm}

\begin{subthm}{}
 For any open cover of $\spc{K}$ there is $\eps>0$ such that any $\eps$-ball in $\spc{K}$ lies in one element of the cover. (The value $\eps$ is called a \index{Lebesgue number}\emph{Lebesgue number} of the covering.)
\end{subthm}

\begin{subthm}{}
 Every sequence of points in $\spc{K}$ has a subsequence that converges in $\spc{K}$.
\end{subthm}

\begin{subthm}{totally-bounded}
The space $\spc{K}$ is complete and \index{totally bounded space}\emph{totally bounded}; that is, for any $\eps>0$, the space $\spc{K}$ admits a finite cover by open $\eps$-balls.
\end{subthm}

\end{thm}

A subset $N$ of a metric space $\spc{K}$ is called \index{net}\emph{$\eps$-net} if any point $x\in \spc{K}$ lies on the distance less than $\eps$ from a point in $N$.
Note that totally bounded spaces can be defined as spaces that admit a finite $\eps$-net for any $\eps>0$.

\begin{thm}{Exercise}\label{ex:compact-net}
Show that a space $\spc{K}$ is totally bounded if and only if it contains a compact $\eps$-net for any $\eps>0$. 
\end{thm}


Let $\pack_\eps\spc{X}$ be the exact upper bound on the number of points $x_1,\z\dots,x_n\in \spc{X}$ such that $\dist{x_i}{x_j}{}\ge\eps$ if $i\ne j$.

If $n=\pack_\eps\spc{X}<\infty$, then
the collection of points $x_1,\dots,x_n$ is called a \index{maximal packing}\emph{maximal $\eps$-packing}.
Note that $n$ is the maximal number of open disjoint $\tfrac\eps2$-balls in $\spc{X}$.

\begin{thm}{Exercise}\label{ex:pack-net}
Show that any maximal $\eps$-packing is an $\eps$-net.

Conclude that a complete space $\spc{X}$ is compact if and only if $\pack_\eps\spc{X}\z<\infty$ for any $\eps>0$.
\end{thm}


\begin{thm}{Exercise}\label{ex:non-contracting-map}
Let $\spc{K}$  be a compact metric space and
\[f\:\spc{K}\z\to \spc{K}\] 
be a distance-nondecreasing map.
Prove that $f$ is an \index{isometry}\emph{isometry};
that is, $f$ is a distance-preserving bijection.
\end{thm}

A metric space $\spc{X}$ is called \index{locally compact space}\emph{locally compact} if any point in $\spc{X}$ admits a compact neighborhood;
in other words, for any point $x\in\spc{X}$ a closed ball $\cBall[x,r]$ is compact for some $r>0$.

\section{Proper spaces}

A metric space $\spc{X}$ is called \index{proper space}\emph{proper} if all closed bounded sets in $\spc{X}$ are compact. 
This condition is equivalent to each of the following statements:
\begin{itemize}
\item For some (and therefore any) point $p\in \spc{X}$ and any $R<\infty$, 
the closed ball $\cBall[p,R]_{\spc{X}}$ is compact. 
\item The function $\distfun_p\:\spc{X}\to\RR$ is \index{proper function}\emph{proper} for some (and therefore any) point $p\in \spc{X}$;
that is, for any compact set $K\subset \RR$, its inverse image 
\[\distfun_p^{-1}(K)=\set{x\in \spc{X}}{\dist{p}{x}{\spc{X}}\in K}\]
is compact.
\end{itemize}

\begin{thm}{Exercise}\label{ex:loc-compact-not-proper}
Give an example of space which is locally compact but not proper.
\end{thm}

\section{Geodesics}
\label{sec:geods}

Let $\spc{X}$ be a metric space 
and $\II$\index{$\II$} a real interval. 
A~globally isometric map $\gamma\:\II\to \spc{X}$ is called a \index{geodesic}\emph{geodesic}%
\footnote{Different authors call it differently: {}\emph{shortest path}, {}\emph{minimizing geodesic}.
Also, note that the meaning of the term \emph{geodesic} is different from what is used in Riemannian geometry, altho they are closely related.}; 
in other words, $\gamma\:\II\to \spc{X}$ is a geodesic if 
\[\dist{\gamma(s)}{\gamma(t)}{\spc{X}}=|s-t|\]
for any pair $s,t\in \II$.

If $\gamma\:[a,b]\to \spc{X}$ is a geodesic and $p=\gamma(a)$, $q=\gamma(b)$, then we say that $\gamma$ is a geodesic from $p$ to $q$.
In this case, the image of $\gamma$ is denoted by $[p q]$\index{$[{*}{*}]$}, and, with abuse of notations, we also call it a \index{geodesic}\emph{geodesic}.
We may write $[p q]_{\spc{X}}$ 
to emphasize that the geodesic $[p q]$ is in the space  ${\spc{X}}$.

In general, a geodesic from $p$ to $q$ need not exist and if it exists, it need not  be unique.  
However, once we write $[p q]$ we assume that we have chosen such geodesic.

A \index{geodesic path}\emph{geodesic path} is a geodesic with constant-speed parameterization by the unit interval $[0,1]$.

\section{Geodesic spaces and metric trees}

A metric space is called \index{geodesic}\emph{geodesic} if any pair of its points can be joined by a geodesic.

\begin{thm}{Exercise}\label{ex:pogorelov}
Let $f$ be a centrally symmetric positive continuous function on $\mathbb{S}^2$.
Given two points $x,y\in \mathbb{S}^2$,
set 
\[\|x-y\|=\int_{B(x,\frac \pi2)\backslash B(y,\frac\pi2)}f.\]

Show that $(\mathbb{S}^2,\|{*}-{*}\|)$ is a geodesic space
and the geodesics in $(\mathbb{S}^2,\|{*}-{*}\|)$ run along great circles of $\mathbb{S}^2$.
\end{thm}

A geodesic space $\spc{T}$ is called a \index{metric tree}\emph{metric tree} if any pair of points in $\spc{T}$ are connected by a unique geodesic,
and the union of any two geodesics $[xy]_{\spc{T}}$, and $[yz]_{\spc{T}}$ contain the geodesic $[xz]_{\spc{T}}$.
In other words any triangle in $\spc{T}$ is a tripod;
that is, for any three geodesics $[xy]$, $[yz]$, and $[zx]$ have a common point.


\begin{thm}{Exercise}\label{ex:4-point-trees}
Let $p,x,y,z$ be points in a metric tree.
Consider three numbers 
\begin{align*}
a&=|p-x|+|y-z|,
&
b&=|p-y|+|z-x|,
&
c&=|p-z|+|x-y|.
\end{align*}
Suppose that $a\le b\le c$.
Show that $b=c$.

\end{thm}

Recall that the set 
\[S_r(p)_{\spc{X}}=\set{x\in\spc{X}}{\dist{p}{x}{\spc{X}}=r}\]
is called a \emph{sphere} with center $p$ and radius $r$ in a metric space $\spc{X}$.


\begin{thm}{Exercise}\label{ex:spheres-in-trees}
Show that spheres in metric trees are ultrametric spaces.
That is, 
\[\dist{x}{z}{}
\le
\max\{\,\dist{x}{y}{},\dist{y}{z}{}\,\}\]
for any $x,y,z\in S_r(p)_{\spc{T}}$.
\end{thm}


\section{Length}

A \index{curve}\emph{curve} is defined as a continuous map from a real interval $\II$ to a metric space.
If $\II=[0,1]$, that is, if the interval is unit, then the curve is called a \index{path}\emph{path}.

\begin{thm}{Definition}
Let $\spc{X}$ be a metric space and
$\alpha\: \II\to \spc{X}$ be a curve.
We define the \index{length}\emph{length} of $\alpha$ as 
\[
\length \alpha \df \sup_{t_0\le t_1\le\ldots\le t_n}\sum_i \dist{\alpha(t_i)}{\alpha(t_{i-1})}{}.
\]

A curve $\alpha$ is called \index{rectifiable curve}\emph{rectifiable} if $\length \alpha<\infty$.
\end{thm}



\begin{thm}{Theorem}\label{thm:length-semicont}
Length is a lower semi-continuous with respect to the pointwise convergence of curves. 

More precisely, assume that a sequence
of curves $\gamma_n\:\II\to \spc{X}$ in a metric space $\spc{X}$ converges pointwise 
to a curve $\gamma_\infty\:\II\to \spc{X}$;
that is, for any fixed $t \in \II$, $\gamma_n(t)\z\to\gamma_\infty(t)$ as $n\to\infty$. 
Then 
$$\liminf_{n\to\infty} \length\gamma_n \ge \length\gamma_\infty.\eqlbl{eq:semicont-length}$$
\end{thm}

\begin{wrapfigure}{o}{20 mm}
\vskip-0mm
\centering
\includegraphics{mppics/pic-100}
\end{wrapfigure}

Note that the inequality \ref{eq:semicont-length} might be strict.
For example, the diagonal $\gamma_\infty$ of the unit square 
can be  approximated by stairs-like
polygonal curves $\gamma_n$
with sides parallel to the sides of the square ($\gamma_6$ is on the picture).
In this case
\[\length\gamma_\infty=\sqrt{2}\quad
\text{and}\quad \length\gamma_n=2\]
for any $n$.

\parit{Proof.}
Fix a sequence $t_0\le t_1\le\dots\le t_k$ in $\II$.
Set 
\begin{align*}\Sigma_n
&\df
|\gamma_n(t_0)-\gamma_n(t_1)|+\dots+|\gamma_n(t_{k-1})-\gamma_n(t_k)|.
\\
\Sigma_\infty
&\df
|\gamma_\infty(t_0)-\gamma_\infty(t_1)|+\dots+|\gamma_\infty(t_{k-1})-\gamma_\infty(t_k)|.
\end{align*}

Note that for each $i$ we have 
\[|\gamma_n(t_{i-1})-\gamma_n(t_i)|\to|\gamma_\infty(t_{i-1})-\gamma_\infty(t_i)|\]
and therefore
\[\Sigma_n\to \Sigma_\infty\] 
as $n\to\infty$.
Note that 
\[\Sigma_n\le\length\gamma_n\]
for each $n$.
Hence,
$$\liminf_{n\to\infty} \length\gamma_n \ge \Sigma_\infty.$$

Since the partition was arbitrary, by the definition of length, the inequality  \ref{eq:semicont-length} is obtained.
\qeds

\section{Length spaces}\label{sec:intrinsic}

If for any $\eps>0$ and any pair of points $x$ and $y$ in a metric space $\spc{X}$, there is a path $\alpha$ connecting $x$ to $y$ such that
\[\length\alpha< \dist{x}{y}{}+\eps,\]
then $\spc{X}$ is called a \index{length space}\emph{length space} and the metric on $\spc{X}$ is called a \index{length metric}\emph{length metric}.\label{page:length metric}

An $\infty$-metric space is a length space if each of its metric components is a length space.
In other words, if $\spc{X}$ is an $\infty$-metric space, 
then in the above definition we assume in addition that $\dist{x}{y}{\spc{X}}<\infty$.

Note that any geodesic space is a length space.
The following example shows that the converse does not hold.


\begin{thm}{Example}
Suppose a space $\spc{X}$ is obtained by gluing a countable collection of disjoint intervals $\{\II_n\}$ of length $1+\tfrac1n$, where for each $\II_n$ the left end is glued to $p$ and the right end to~$q$.

Observe that the space $\spc{X}$ carries a natural complete length metric with respect to which $\dist{p}{q}{\spc{X}}=1$ but there is no geodesic connecting $p$ to~$q$.
\end{thm}

\begin{thm}{Exercise}\label{ex:no-geod}
Give an example of a complete length space $\spc{X}$ such that no pair of distinct points in $\spc{X}$ can be joined by a geodesic.
\end{thm}

Directly from the definition, it follows that if $\alpha\:[0,1]\to\spc{X}$ is a path from $x$ to $y$ 
(that is, $\alpha(0)=x$ and $\alpha(1)=y$), then 
\[\length\alpha\ge \dist{x}{y}{}.\]
Set 
\[\yetdist{x}{y}{}=\inf\{\length\alpha\}\]
where the greatest lower bound is taken for all paths from $x$ to~$y$.
It is straightforward to check that $(x,y)\mapsto \yetdist{x}{y}{}$ is an $\infty$-metric; moreover, $(\spc{X},\yetdist{*}{*}{})$ is a length space.
The metric $\yetdist{*}{*}{}$ is called the \index{induced length metric}\emph{induced length metric}.

\begin{thm}{Exercise}\label{ex:compact+connceted}
Let $\spc{X}$ be a complete length space.
Show that for any compact subset $K$ in $\spc{X}$
there is a compact path-connected subset $K'$ that contains $K$.  
\end{thm}

\begin{thm}{Exercise}\label{ex:compact=>complete}
Suppose $(\spc{X},\dist{*}{*}{})$ is a complete metric space.
Show that $(\spc{X},\yetdist{*}{*}{})$ is complete.
\end{thm}

Let $A$ be a subset of a metric space $\spc{X}$.
Given two points $x,y\in A$,
consider the value
\[\dist{x}{y}{A}=\inf_{\alpha}\{\length\alpha\},\]
where the greatest lower bound is taken for all paths $\alpha$ from $x$ to $y$ in~$A$.
In other words $\dist{*}{*}{A}$ denotes the induced length metric on the subspace $A$.%
\footnote{The notation $\dist{*}{*}{A}$ conflicts with the previously defined notation for distance $\dist{x}{y}{\spc{X}}$ in a metric space $\spc{X}$. However, most of the time we will work with ambient length spaces where the meaning will be unambiguous.}

Let $x$ and $y$ be points in a metric space $\spc{X}$.

\begin{enumerate}[(i)]
\item A point $z\in \spc{X}$ is called a \index{midpoint}\emph{midpoint} between $x$ and $y$
if 
\[\dist{x}{z}{}=\dist{y}{z}{}=\tfrac12\cdot\dist[{{}}]{x}{y}{}.\]
\item Assume $\eps\ge 0$.
A point $z\in \spc{X}$ is called an \index{$\eps$-midpoint}\emph{$\eps$-midpoint} between $x$ and $y$
if 
\[\dist{x}{z}{},\quad\dist{y}{z}{}\le\tfrac12\cdot\dist[{{}}]{x}{y}{}+\eps.\]
\end{enumerate}


Note that a $0$-midpoint is the same as a midpoint.


\begin{thm}{Lemma}\label{lem:mid>geod}
Let $\spc{X}$ be a complete metric space.
\begin{subthm}{lem:mid>length}
Assume that for any pair of points $x,y\in \spc{X}$,  
and any $\eps>0$,
there is an $\eps$-midpoint~$z$.
Then $\spc{X}$ is a length space.
\end{subthm}

\begin{subthm}{lem:mid>geod:geod}
Assume that for any pair of points $x,y\in \spc{X}$, 
there is a midpoint~$z$.
Then $\spc{X}$ is a geodesic space.
\end{subthm}
\end{thm}

\parit{Proof.}
We first prove \ref{SHORT.lem:mid>length}.
Let $x,y\in \spc{X}$ be a pair of points.

Set $\eps_n=\frac\eps{4^n}$, $\alpha(0)=x$ and $\alpha(1)=y$.

Let $\alpha(\tfrac12)$ be an $\eps_1$-midpoint between $\alpha(0)$ and $\alpha(1)$.
Further, let $\alpha(\frac14)$ 
and $\alpha(\frac34)$ be $\eps_2$-midpoints between the pairs $(\alpha(0),\alpha(\tfrac12))$ 
and $(\alpha(\tfrac12),\alpha(1))$ respectively.
Applying the above procedure recursively,
on the $n$-th step we define $\alpha(\tfrac{k}{2^n})$,
for every odd integer $k$ such that $0<\tfrac k{2^n}<1$, 
as an $\eps_{n}$-midpoint of the already defined
$\alpha(\tfrac{k-1}{2^n})$ and $\alpha(\tfrac{k+1}{2^n})$.


In this way we define $\alpha(t)$ for $t\in W$,
where $W$ denotes the set of dyadic rationals in $[0,1]$.
Since $\spc{X}$ is complete, the map $\alpha$ can be extended continuously to $[0,1]$.
Moreover,
\[\begin{aligned}
\length\alpha&\le \dist{x}{y}{}+\sum_{n=1}^\infty 2^{n-1}\cdot\eps_n\le
\\
&\le \dist{x}{y}{}+\tfrac\eps2.
\end{aligned}
\eqlbl{eq:eps-midpoint}
\]
Since $\eps>0$ is arbitrary, we get \ref{SHORT.lem:mid>length}.

To prove \ref{SHORT.lem:mid>geod:geod}, 
one should repeat the same argument 
taking midpoints instead of $\eps_n$-midpoints.
In this case, \ref{eq:eps-midpoint} holds for $\eps_n=\eps\z=0$.
\qeds

Since in a compact space a sequence of $\tfrac1n$-midpoints $z_n$ contains a convergent subsequence, \ref{lem:mid>geod} immediately implies the following.

\begin{thm}{Proposition}\label{prop:length+proper=>geodesic}
Any proper length space is geodesic.
\end{thm}

\begin{thm}{Hopf--Rinow theorem}\label{thm:Hopf-Rinow}
Any complete, locally compact length space is proper.
\end{thm}

Before reading the proof, it is instructive to solve \ref{ex:loc-compact-not-proper}.

\parit{Proof.}
Let $\spc{X}$ be a locally compact length space.
Given $x\in \spc{X}$, denote by $\rho(x)$ the least upper bound of all $R>0$ such that
the closed ball $\cBall[x,R]$ is compact.
Since $\spc{X}$ is locally compact, 
$$\rho(x)>0
\quad\text{for any}\quad
x\in \spc{X}.\eqlbl{eq:rho>0}$$
It is sufficient to show that $\rho(x)=\infty$ for some (and therefore any) point $x\in \spc{X}$.

\begin{clm}{} If $\rho(x)<\infty$, then $B=\cBall[x,\rho(x)]$ is compact.
\end{clm}

Indeed, $\spc{X}$ is a length space;
therefore for any $\eps>0$, 
the set $\cBall[x,\rho(x)-\eps]$ is a compact $\eps$-net in~$B$.
Since $B$ is closed and hence complete, it must be compact.
\claimqeds

\begin{clm}{} $|\rho(x)-\rho(y)|\le \dist{x}{y}{\spc{X}}$ for any $x,y\in \spc{X}$;
in particular, $\rho\:\spc{X}\to\RR$ is a continuous function.
\end{clm}

Indeed, 
assume the contrary; that is, $\rho(x)+|x-y|<\rho(y)$ for some $x,y\in \spc{X}$. 
Then 
$\cBall[x,\rho(x)+\eps]$ is a closed subset of $\cBall[y,\rho(y)]$ for some $\eps>0$.
Then  compactness of $\cBall[y,\rho(y)]$ implies compactness of $\cBall[x,\rho(x)+\eps]$, a contradiction.\claimqeds

Set $\eps=\min\set{\rho(y)}{y\in B}$; the minimum is defined since $B$ is compact and $\rho$ is continuous.
From \ref{eq:rho>0}, we have $\eps>0$.

Choose a finite $\tfrac\eps{10}$-net $\{a_1,a_2,\dots,a_n\}$ in $B=\cBall[x,\rho(x)]$.
The union $W$ of the closed balls $\cBall[a_i,\eps]$ is compact.
Clearly,
$\cBall[x,\rho(x)+\frac\eps{10}]\subset W$.
Therefore, $\cBall[x,\rho(x)+\frac\eps{10}]$ is compact,
a contradiction.
\qeds

\begin{thm}{Exercise}\label{exercise from BH}
Construct a geodesic space $\spc{X}$ that is locally compact,
but whose completion $\bar{\spc{X}}$ is neither geodesic nor locally compact.
\end{thm}


\begin{thm}{Advanced exercise}\label{ex:gross}
Show that for any compact length-metric space $\spc{X}$ there is a number $\ell$ such that for any finite collection of points there is a point $z$ that lies on average distance $\ell$ from the collection;
that is, for any $x_1,\dots,x_n\in \spc{X}$ there is $z\in \spc{X}$ such that
\[\tfrac1n\cdot\sum_i|x_i-z|_{\spc{X}}=\ell.\]
\end{thm}







\chapter{Semisolutions}
\input{metric-sol}
\input{uryson-sol}
\input{injective-sol}
\input{converge-sol}
\input{ultralimit-sol}

{\small\sloppy
\input{pure-metric.ind}

\printbibliography[heading=bibintoc]
\fussy
}


\end{document}


\chapter{Ultralimits}

Ultralimits provide a very general way to pass to a limit.
This procedure works for \emph{any} sequence of metric spaces, its result reminds limit in the sense of Gromov Gausdorff, but has some strange features; for example, the limit of a constant sequence does \emph{not} coincide with this constant (see \ref{ex:ultrapower:compact}).

In geometry, ultralimits are used only as a canonical way to pass to a convergent subsequence.
It is a useful thing in the proofs where one needs to repeat ``pass to convergent subsequence'' too many times.

This lecture is based on the introduction to the paper by Bruce Kleiner and Bernhard Leeb \cite{kleiner-leeb}.

\section{Faces of ultrafilters}

Recall that $\NN$ denotes the set of natural numbers, $\NN=\{1,2,\dots\}$

\begin{thm}{Definition}
A finitely additive measure $\omega$ 
on  $\NN$ 
is called an \index{ultrafilter}\emph{ultrafilter} if it satisfies the following condition:
\begin{subthm}{}
$\omega(\NN)=1$ and 
$\omega(S)=0$ or $1$ for any subset $S\subset \NN$.
\end{subthm}
An ultrafilter $\omega$ is called 
\emph{nonprincipal}\index{ultrafilter!nonprincipal ultrafilter}\index{nonprincipal ultrafilter} if in addition 
\begin{subthm}{}
$\omega(F)=0$ for any finite subset $F\subset \NN$.
\end{subthm}
\end{thm}

If $\omega(S)=0$ for some subset $S\subset \NN$,
we say that $S$ is \index{$\omega$-small}\emph{$\omega$-small}. 
If $\omega(S)=1$, we say that $S$ contains \index{$\omega$-almost all}\emph{$\omega$-almost all} elements of $\NN$.

\parbf{Classical definition.}
More commonly, a nonprincipal ultrafilter is defined as a collection, say $\mathfrak{F}$, of sets in $\NN$ such that
\begin{enumerate}
\item\label{filter:supset} if $P\in \mathfrak{F}$ and $Q\supset P$, then $Q\in \mathfrak{F}$,
\item\label{filter:cap} if $P, Q\in \mathfrak{F}$, then $P\cap Q\in \mathfrak{F}$,
\item\label{filter:ultra} for any subset $P\subset\NN$, either $P$ or its complement is an element of $\mathfrak{F}$.
\item\label{filter:non-prin} if $F\subset \NN $ is finite, then $F\notin \mathfrak{F}$.
\end{enumerate}
Setting $P\in\mathfrak{F}\Leftrightarrow\omega(P)=1$ makes these two definitions equivalent.

A nonempty collection of sets $\mathfrak{F}$ that does not include the empty set and satisfies only conditions \ref{filter:supset} and \ref{filter:cap} is called a \index{filter}\emph{filter}; 
if in addition $\mathfrak{F}$ satisfies condition \ref{filter:ultra} it is called an \index{ultrafilter}\emph{ultrafilter}.
From Zorn's lemma, it follows that every filter contains an ultrafilter.
Thus there is an ultrafilter $\mathfrak{F}$ contained in the filter of all complements of finite sets; clearly, this ultrafilter $\mathfrak{F}$ is nonprincipal.


\parbf{Stone--\v{C}ech compactification.}
Given a set $S\subset \NN$, consider subset $\Omega_S$ of all ultrafilters $\omega$ such that $\omega(S)=1$.
It is straightforward to check that the sets $\Omega_S$ for all $S\subset \NN$ form a topology on the set of ultrafilters on $\NN$. 
The obtained space is called \index{Stone--\v{C}ech compactification}\emph{Stone--\v{C}ech compactification} of $\NN$;
it is usually denoted as $\beta\NN$.

Let $\omega_n$ denotes the principal ultrafilter such that $\omega_n(\{n\})=1$; that is, $\omega_n(S)=1$ if and only if $n\in S$.
Note that $n\mapsto\omega_n$ defines a natural embedding $\NN\hookrightarrow\beta\NN$. 
Using the described embedding, we can (and will) consider $\NN$ as a subset of $\beta\NN$.

The space $\beta\NN$ is the maximal compact Hausdorff space that contains $\NN$  as an everywhere dense subset.
More precisely, for any compact Hausdorff space $\spc{X}$ 
and a map $f\:\NN\to \spc{X}$ there is a unique continuous map $\bar f\:\beta\NN\to X$ such that the restriction $\bar f|_\NN$ coincides with $f$. 

\section{Ultralimits of points}
\label{ultralimits}\index{ultralimit}

Further, we will need the existence of a nonprincipal  ultrafilter $\omega$,
which we fix once and for all.

Assume $(x_n)$ is a sequence of points in a metric space $\spc{X}$. 
Let us define the \index{$\omega$-limit}\emph{$\omega$-limit} of $(x_n)$ as the point $x_\omega$ 
such that for any $\eps>0$, $\omega$-almost all elements of $(x_n)$ lie in $\oBall(x_\omega,\eps)$; 
that is,
\[\omega\set{n\in\NN}{\dist{x_\omega}{x_n}{}<\eps}=1.\]
In this case, we will write 
\[x_\omega=\lim_{n\to\omega} x_n
\ \ \text{or}\ \ 
x_n\to x_\omega\ \text{as}\ n\to\omega.\]

For example, if $\omega$ is the {}\emph{principal} ultrafilter such that $\omega\{n\}=1$ for some $n\in\NN$, then
$x_\omega=x_n$.

Alternatively, the sequence $(x_n)$ can be regarded as a map $\NN\to\spc{X}$.
In this case, the map $\NN\to\spc{X}$ can be extended to a continuous map $\beta\NN\to\spc{X}$ from the Stone--\v{C}ech compactification $\beta\NN$ of $\NN$.
Then the $\omega$-limit $x_\omega$ can be regarded as the image of $\omega$.

Note that $\omega$-limits of a sequence and its subsequence may differ.
For example, sequence $y_n=-(-1)^n$ is a subsequence of $x_n=(-1)^n$, but for any ultrafilter $\omega$, we have
\[\lim_{n\to\omega}x_n
\ne
\lim_{n\to\omega}y_n.\] 

\begin{thm}{Proposition}\label{prop:ultra/partial}
Let $\omega$ be a nonprincipal ultrafilter.
Assume $(x_n)$ is a sequence of points in a metric space $\spc{X}$
and $x_n\to  x_\omega$ as $n\to\omega$.
Then $x_\omega$ is a partial limit of the sequence $(x_n)$;
that is, there is a subsequence $(x_n)_{n\in S}$ that converges to $x_\omega$ in the usual sense.
\end{thm}

\parit{Proof.}
Given $\eps>0$, 
set $S_\eps=\set{n\in\NN}{\dist{x_n}{x_\omega}{}<\eps}$.

Note that $\omega(S_\eps)=1$ for any $\eps>0$.
Since $\omega$ is nonprincipal, the set $S_\eps$ is infinite.
Therefore, we can choose an increasing sequence $(n_k)$
such that $n_k\in S_{\frac1k}$ for each $k\in \NN$.
Clearly, $x_{n_k}\to x_\omega$ as $k\to\infty$.
\qeds

The following proposition 
is analogous to the statement that any sequence in a compact metric space 
has a convergent subsequence;
it can be proved the same way.

\begin{thm}{Proposition}\label{prop:ultra/compact}
Let $\spc{X}$ be a compact metric space.
Then
any sequence of points $(x_n)$ in $\spc{X}$ has a unique $\omega$-limit $x_\omega$.

In particular, a bounded sequence of real numbers has a unique $\omega$-limit.
\end{thm}

The following lemma is an ultralimit analog of the Cauchy convergence test.

\begin{thm}{Lemma}\label{lem:X-X^w}
Let $(x_n)$ be a sequence of points in a complete space~$\spc{X}$. 
Assume for each subsequence $(y_n)$ of $(x_n)$, 
the $\omega$-limit 
\[y_\omega=\lim_{n\to\omega}y_{n}\in \spc{X}\]
is defined and does not depend on the choice of subsequence, 
then the sequence $(x_n)$ converges in the usual sense.
\end{thm}

\parit{Proof.} If $(x_n)$ is not a Cauchy sequence,
then for some $\eps>0$, there is a subsequence $(y_n)$ of $(x_n)$ such that $\dist{x_n}{y_n}{}\ge\eps$ for all $n$.

It follows that $\dist{x_\omega}{y_\omega}{}\ge \eps$, a contradiction.\qeds

Ultralimits could shorten some proofs in the previous lecture.
The following exercise provides an example.

\begin{thm}{Exercise}\label{ex:prop:eps-isometry=isometry}
Use ultralimits to give a shorter proof of \ref{GH-2} (page~\pageref{page:GH-2-proof}).
\end{thm}

\begin{thm}{Exercise}\label{ex:linear}
Denote by $S$ the space of bounded sequences of real numbers.
Show that there is a linear functional $L\:S\to\RR$ such that
for any sequence $\bm{s}=(s_1,s_2,\dots)\in S$ the image $L(\bm{s})$ is a partial limit of $s_1,s_2,\dots$.
\end{thm}



\section{Ultralimits of spaces}\label{sec:Ultralimit of spaces}

Recall that $\omega$ denotes a nonprincipal ultrafilter on the set of natural numbers.

Let $\spc{X}_n$ be a sequence of metric spaces.
Consider all sequences of points $x_n\in \spc{X}_n$.
On the set of all such sequences,
define a pseudometric by
\[\dist{(x_n)}{(y_n)}{}
=
\lim_{n\to\omega} \dist{x_n}{y_n}{\spc{X}_n}.
\eqlbl{eq:olim-dist}\]
Note that the $\omega$-limit on the right-hand side is always defined 
and takes a value in $[0,\infty]$. 
(The $\omega$-convergence to $\infty$ is defined analogously to the usual convergence to $\infty$).

Set $\spc{X}_\omega$ to be the corresponding metric space; 
that is, the underlying set of $\spc{X}_\omega$ is formed by classes of equivalence of sequences of points $x_n\in\spc{X}_n$ 
defined by 
\[(x_n)\sim(y_n)
\ \Leftrightarrow\ 
\lim_{n\to\omega} \dist{x_n}{y_n}{}=0\]
and the distance is defined by \ref{eq:olim-dist}.

The space $\spc{X}_\omega$ is called the \index{$\omega$-limit space}\emph{$\omega$-limit} of $\spc{X}_n$.
Typically  $\spc{X}_\omega$ will denote the  
$\omega$-limit of sequence $\spc{X}_n$;
we may also write  
\[\spc{X}_n\to\spc{X}_\omega\ \ \text{as}\ \  n\to\omega\ \ \text{or}\ \ \spc{X}_\omega=\lim_{n\to\omega}\spc{X}_n.\]

Given a sequence $x_n\in \spc{X}_n$,
we will denote by $x_\omega$ its equivalence class which is a point in $\spc{X}_\omega$;
it can be written as
\[x_n\to x_\omega \ \ \text{as}\ \  n\to\omega,\ \ \text{or}\ \ x_\omega=\lim_{n\to\omega} x_n.\]

\begin{thm}{Observation}\label{obs:ultralimit-is-complete}
The $\omega$-limit of any sequence of metric spaces is complete. 
\end{thm}

\parit{Proof.}
Let $\spc{X}_n$ be a sequence of metric spaces and $\spc{X}_n\to\spc{X}_\omega$ as $n\to\omega$.
Choose a Cauchy sequence $x_1,x_2,\dots\in\spc{X}_\omega$.
Passing to a subsequence, we can assume that $\dist{x_k}{x_{m}}{\spc{X}_\omega}<\tfrac1{k}$ for any $k<m$.

Let us choose a double sequence $x_{n,m}\in \spc{X}_n$ such that for any fixed $m$ we have $x_{n,m}\to x_m$ as $n\to\omega$.
Note that for any $k<m$ the inequality $\dist{x_{n,k}}{x_{n,m}}{}<\tfrac1{k}$ holds for $\omega$-almost all $n$.
It follows that we can choose a nested sequence of sets 
\[\NN= S_1\supset S_2\supset\dots\] 
such that 
\begin{itemize}
\item $\omega(S_m)=1$ for each $m$, 
\item $\bigcap_m S_m=\emptyset$, and
\item $\dist{x_{n,k}}{x_{n,l}}{}<\tfrac1{k}$ for $k<l\le m$ and $n\in S_m$.
\end{itemize}

Consider the sequence $y_n=x_{n,m(n)}$, where $m(n)$ is the largest value such that $n\in S_{m(n)}$.
Denote by $y_\omega\in \spc{X}_\omega$ the $\omega$-limit of $y_n$.

Observe that $|y_m-x_{n,m}|<\tfrac1{m}$ for $\omega$-almost all $n$.
It follows that $|x_m-y_\omega|\le \tfrac1{m}$ for any $m$.
Therefore, $x_n\to y_\omega$ as $n\to \infty$.
That is, any Cauchy sequence in $\spc{X}_\omega$ converges.
\qeds

\begin{thm}{Observation}\label{obs:ultralimit-is-geodesic}
The $\omega$-limit of any sequence of length spaces is geodesic. 
\end{thm}

\parit{Proof.}
If $\spc{X}_n$ is a sequence of length spaces, then for any sequence of pairs $x_n, y_n\in X_n$ there is a sequence of $\tfrac1n$-midpoints $z_n$.

Let $x_n\to x_\omega$, $y_n\to y_\omega$ and $z_n\to z_\omega$ as $n\to \omega$.
Note that $z_\omega$ is a midpoint of $x_\omega$ and $y_\omega$ in $\spc{X}_\omega$.

By Observation~\ref{obs:ultralimit-is-complete}, $\spc{X}_\omega$ is complete.
Applying Lemma~\ref{lem:mid>geod} we get the statement.
\qeds


\begin{thm}{Exercise}\label{ex:lim(tree)}
Show that an ultralimit of metric trees is a metric tree. 
\end{thm}

\section{Ultrapower}

If all the metric spaces in the sequence are identical $\spc{X}_n=\spc{X}$, 
its $\omega$-limit 
$\lim_{n\to\omega}\spc{X}_n$
is denoted by $\spc{X}^\omega$
and called $\omega$-power of $\spc{X}$.



\begin{thm}{Exercise}\label{ex:ultrapower}
For any point $x\in \spc{X}$, consider the constant sequence $x_n=x$
and set $\iota(x)=\lim_{n\to\omega}x_n\in\spc{X}^\omega$.

\begin{subthm}{ex:ultrapower:a}
Show that $\iota\:\spc{X}\to\spc{X}^\omega$ is distance-preserving embedding. (So we can and will consider $\spc{X}$ as a subset of $\spc{X}^\omega$.)
\end{subthm}

\begin{subthm}{ex:ultrapower:compact} 
Show that $\iota$ is onto if and only if $\spc{X}$ compact.
\end{subthm}

\begin{subthm}{ex:ultrapower:proper} 
Show that if $\spc{X}$ is proper, then $\iota(\spc{X})$ forms a metric component of $\spc{X}^\omega$; that is, a subset of $\spc{X}^\omega$ that lie at a finite distance from a given point.
\end{subthm}

\end{thm}

Note that \ref{SHORT.ex:ultrapower:compact} implies that the inclusion $\spc{X}\hookrightarrow\spc{X}^\omega$ is not onto if the space $\spc{X}$ is not compact. However, the spaces $\spc{X}$ and $\spc{X}^\omega$ might be isometric; here is an example:

\begin{thm}{Exercise}\label{ex:isom-ultrapower}
Let $\spc{X}$ be a countable set with discrete metric;
that is $\dist{x}{y}{\spc{X}}=1$ if $x\ne y$.
Show that 

\begin{subthm}{ex:isom-ultrapower:no}
$\spc{X}^\omega$ is not isometric to $\spc{X}$.
\end{subthm}

\begin{subthm}{ex:isom-ultrapower:yes}
$\spc{X}^\omega$ is  isometric to $(\spc{X}^\omega)^\omega$.
\end{subthm}

\end{thm}



\begin{thm}{Observation}\label{obs:ultrapower-is-geodesic}
Let $\spc{X}$ be a complete metric space. 
Then $\spc{X}^\omega$ is geodesic space if and only if $\spc{X}$ is a length space.
\end{thm}

\parit{Proof.}
The ``if''-part follows from \ref{obs:ultralimit-is-geodesic}; it remains to prove the ``only-if''-part

Assume $\spc{X}^\omega$ is geodesic space.
Then any pair of points $x,y\in \spc{X}$ has a midpoint $z_\omega\in\spc{X}^\omega$.
Fix a sequence of points $z_n\in  \spc{X}$ such that $z_n\to z_\omega$ as $n\to \omega$.

Note that 
$\dist{x}{z_n}{\spc{X}}\to \tfrac12\cdot \dist{x}{y}{\spc{X}}$
and 
$\dist{y}{z_n}{\spc{X}}\to \tfrac12\cdot \dist{x}{y}{\spc{X}}$
as 
$n\to\omega$.
In particular, for any $\eps>0$, the point $z_n$ is an $\eps$-midpoint of $x$ and $y$ for $\omega$-almost all $n$.
It remains to apply \ref{lem:mid>geod}.
\qeds

\begin{thm}{Exercise}\label{ex:two-geodesics-in-ultrapower}
Assume $\spc{X}$ is a complete length space 
and $p,q\in\spc{X}$ cannot be joined by a geodesic in $\spc{X}$.  
Then there are at least two distinct geodesics between $p$ and $q$ 
in the ultrapower $\spc{X}^\omega$.
\end{thm}

\begin{thm}{Exercise}\label{ex:notproper-limit}
 Construct a proper metric space $\spc{X}$ such that $\spc{X}^\omega$ is not proper; that is, there is a point $p\in \spc{X}^\omega$ and $R<\infty$ such that the closed ball $\cBall[p,R]_{\spc{X}^\omega}$ is not compact.
\end{thm}

\section{Tangent and asymptotic spaces}

Choose a space $\spc{X}$ and a sequence of $\lambda_n>0$.
Consider the sequence of \index{scaled space}\emph{scalings} $\spc{X}_n=\lambda_n\cdot\spc{X}=(\spc{X},\lambda_n\cdot\dist{*}{*}{\spc{X}})$.

Choose a point $p\in \spc{X}$ and denote by $p_n$ the corresponding point in $\spc{X}_n$.
Consider the $\omega$-limit $\spc{X}_\omega$ of $\spc{X}_n$ (one may denote it by $\lambda_\omega\cdot \spc{X}$);
set $p_\omega$ to be the $\omega$-limit of $p_n$.

If $\lambda_n\to 0$ as $n\to\omega$, then the metric component of $p_\omega$ in $\spc{X}_\omega$ is called \index{$\lambda_\omega$-tangent space}\emph{$\lambda_\omega$-tangent space} at $p$ and denoted by $\T_p^{\lambda_\omega}\spc{X}$ (or $\T_p^{\omega}\spc{X}$ if $\lambda_n=n$).\label{page:ultratangent space}

If $\lambda_n\to \infty$ as $n\to\omega$, then the metric component of $p_\omega$ is called \index{$\lambda_\omega$-asymptotic space}\emph{$\lambda_\omega$-asymptotic space}\footnote{Often it is called \emph{asymptotic cone} despite that it is not a cone in general; this name is used since in good cases it has a cone structure.} and denoted by $\Asym\spc{X}$ or $\Asym^{\lambda_\omega}\spc{X}$.
Note that the space $\Asym\spc{X}$ and its point $p_\omega$ does not depend on the choice of $p\in \spc{X}$.

The following exercise states that the tangent and asymptotic spaces depend on the sequence $\lambda_n$ and a nonprincipal ultrafilter $\omega$.

\begin{thm}{Exercise}\label{ex:ultraT}
Construct a metric space $\spc{X}$ with a point $p$ such that the tangent space
$\T_p^{\lambda_\omega}\spc{X}$ depends on the sequence $\lambda_n$ and/or ultrafilter~$\omega$.
\end{thm}

For nice spaces, different choices may give the same space.

\begin{thm}{Exercise}\label{ex:Asym(Lob)}
Let $\spc{L}$ be the Lobachevsky plane; $\spc{T}=\Asym\spc{L}$.

\begin{subthm}{ex:Asym(Lob):metric-tree}
Show that $\spc{T}$ is a complete metric tree.
\end{subthm}

\begin{subthm}{ex:Asym(Lob):homogeneous}
Show that $\spc{T}$ is one-point homogeneous; that is, given two points $s,t\in \spc{T}$ there is an isometry of $\spc{T}$ that maps $s$ to $t$.
\end{subthm}

\begin{subthm}{ex:Asym(Lob):continuum}
Show that $\spc{T}$ has {}\emph{continuum degree} at any point;
that is, for any point $t\in \spc{T}$ the set of connected components of the complement $\spc{T}\backslash\{t\}$ has cardinality continuum.
\end{subthm}

\begin{subthm}{ex:Asym(Lob):others}
Prove \ref{SHORT.ex:Asym(Lob):metric-tree}--\ref{SHORT.ex:Asym(Lob):continuum} if $\spc{L}$ is Lobachevsky space and/or for the infinite 3-regular%
\footnote{that is, the degree of any vertex is 3.}
metric tree with unit edge length. 
\end{subthm}

\end{thm}




\section{Remarks}

A nonprincipal ultrafilter $\omega$ is called 
\emph{selective}\index{ultrafilter!selective ultrafilter}\index{selective ultrafilter} if for any partition of $\NN$ into sets $\{C_\alpha\}_{\alpha\in\IndexSet}$ such that $\omega(C_\alpha)\z=0$ for each $\alpha$, 
there is a set $S\subset \NN$ such that $\omega(S)=1$ and $S\cap C_\alpha$ is a one-point set for each $\alpha\in\IndexSet$.

The existence of a selective ultrafilter follows from the continuum hypothesis \cite{rudin}.

For a selective ultrafilter $\omega$, there is a stronger version of Proposition~\ref{prop:ultra/partial};
namely we can assume that the subsequence $(x_n)_{n\in S}$ can be chosen so that $\omega(S)=1$.
So, if needed, one may assume that the ultrafilter $\omega$ is chosen to be selective and use this stronger version of the proposition.


\chapter{Universal spaces}

This lecture is based on the discussion of Urysohn space in the book of Mikhael Gromov \cite{gromov-2007}.

\section{Embedding in a normed space}

Recall that a function $v\mapsto |v|$ on a vector space $\spc{V}$ is called \index{norm}\emph{norm} if it satisfies the following condition for any two vectors $v,w\in \spc{V}$ and a scalar $\alpha$:
\begin{itemize}
\item $|v|\ge 0$;
\item $|\alpha\cdot v|=|\alpha|\cdot |v|$;
\item $|v|+|w|\ge|v+w|$.
\end{itemize}

As an example, consider the space of real sequences equipped with \index{sup norm}\emph{sup norm} denoted by the $\ell^\infty$; that is, $\ell^\infty$-norm of $\bm{a}=a_1,a_2,\dots$ is defined by
\[|\bm{a}|_{\ell^\infty}=\sup_n\{\,|a_n|\,\}.\]


It is straightforward to check that for any normed space the function $(v,w)\mapsto |v-w|$ defines a metric on it.
Therefore, any normed space is an example of metric space (in fact, it is a geodesic space).
Often we do not distinguish between normed space and the corresponding metric space.\footnote{By Mazur--Ulam theorem, the metric remembers the linear structure of the space; a slick proof of this statement was given by Jussi V\"{a}is\"{a}l\"{a} \cite{vaisala}.}

The following lemma implies that any compact metric space is isometric to a subset of a fixed normed space.

Recall that 
\index{diameter}\emph{diameter} of a metric space $\spc{X}$ (briefly $\diam \spc{X}$) is defined as least upper bound on the distances between pairs of its points;
that is,
\[\diam \spc{X}=\sup\set{\dist{x}{y}{\spc{X}}}{x,y\in \spc{X}}.\]



\begin{thm}{Lemma}\label{lem:frechet}
Suppose $\spc{X}$ is a \index{bounded space}\emph{bounded} \index{separable space}\emph{separable} metric space;
that is, $\diam\spc{X}$ is finite and $\spc{X}$ contains a countable, dense set $\{w_n\}$.
Given $x\in \spc{X}$, set $a_n(x)=\dist{w_n}{x}{\spc{X}}$.
Then 
\[\iota\:x\mapsto (a_1(x), a_2(x),\dots)\]
defines a distance-preserving embedding $\iota\:\spc{X}\hookrightarrow \ell^\infty$.
\end{thm}

\parit{Proof.} 
By the triangle inequality 
\[|a_n(x)-a_n(y)|\le \dist{x}{y}{\spc{X}}.\eqlbl{eq:a-a=<dist}\]
Therefore, $\iota$ is \index{short map}\emph{short} (in other words, $\iota$ is distance non-increasing).

Again by triangle inequality we have 
\[|a_n(x)-a_n(y)|\ge \dist{x}{y}{\spc{X}}-2\cdot\dist{w_n}{x}{\spc{X}}.\]
Since the set $\{w_n\}$ is dense, we can choose $w_n$ arbitrarily close to $x$.
Whence the value $|a_n(x)-a_n(y)|$ can be chosen arbitrarily close to $\dist{x}{y}{\spc{X}}$.
In other words 
\[\sup_n\{\,\left|\dist{w_n}{x}{\spc{X}}-\dist{w_n}{y}{\spc{X}}\right|\,\}\ge \dist{x}{y}{\spc{X}}.\]
Hence 
\[\sup_n\{\,|a_n(x)-a_n(y)|\,\}\ge \dist{x}{y}{\spc{X}};\eqlbl{eq:a-a>=dist}\]
that is, $\iota$ is distance non-contracting.

Finally, observe that \ref{eq:a-a=<dist} and \ref{eq:a-a>=dist} imply the lemma.
\qeds

\begin{thm}{Exercise}\label{ex:compact-length}
Show that any compact metric space $\spc{K}$ is isometric to a subspace of a compact geodesic space. 
\end{thm}

The following exercise generalizes the lemma to arbitrary separable spaces.

\begin{thm}{Exercise}\label{ex:frechet}
Suppose $\{w_n\}$ is a countable, dense set in a metric space $\spc{X}$.
Choose $x_0\in \spc{X}$;
given $x\in \spc{X}$, set 
\[a_n(x)=\dist{w_n}{x}{\spc{X}}-\dist{w_n}{x_0}{\spc{X}}.\]
Show that $\iota\:x\mapsto (a_1(x), a_2(x),\dots)$ defines a distance-preserving embedding $\iota\:\spc{X}\hookrightarrow \ell^\infty$.
\end{thm}

The following lemma implies that {}\emph{any metric space is isometric to a subset of a normed vector space};
its proof is nearly identical to the proof of \ref{ex:frechet}.

\begin{thm}{Lemma}\label{lem:kuratowski}
Let $\spc{X}$ be arbitrary metric space.
Denote by $\ell^\infty(\spc{X})$ the space of all bounded functions on $\spc{X}$ equipped with sup-norm.

Then for any point $x_0\in \spc{X}$, the map $\iota\:\spc{X}\to \ell^\infty(\spc{X})$ defined by 
\[\iota\:x\mapsto (\distfun_x-\distfun_{x_0})\]
is distance-preserving.
\end{thm}



\section{Extension property}

If a metric space $\spc{X}$ is a subspace of a pseudometric space $\spc{X}'$, then we say that $\spc{X}'$ is an \index{extension}\emph{extension} of $\spc{X}$.
If in addition $\diam\spc{X}'\le d$, then we say that $\spc{X}'$ is a {}\emph{$d$-extension}.

If the complement $\spc{X}'\backslash \spc{X}$ contains a single point, say $p$, we say that $\spc{X}'$ is a \index{one-point extension}\emph{one-point extension} of $\spc{X}$.
In this case, to define metric on $\spc{X}'$, it is sufficient to specify the distance function from $p$; that is, a function $f\:\spc{X}\to\RR$ defined by 
\[f(x)=\dist{p}{x}{\spc{X}'}.\]

The function $f$ cannot be taken arbitrary --- the triangle inequality implies that 
\[f(x)+f(y)\ge \dist{x}{y}{\spc{X}}\ge |f(x)-f(y)|\]
for any $x,y\in \spc{X}$.
In particular, $f$ is a non-negative 1-Lipschitz function on $\spc{X}$.
For a $d$-extension, we need to assume in addition that $\diam\spc{X}\z\le d$ and $f(x)\le d$ for any $x\in \spc{X}$.

Any function $f$ of that type will be called \index{extension function}\emph{extension function}\label{page:extension function} or {}\emph{$d$-extension function} respectively.

\begin{thm}{Definition}\label{def:finite+1}
A metric space $\spc{U}$ meets the \index{extension property}\emph{extension property}  if for any finite subspace $\spc{F}\subset\spc{U}$ and any extension function $f\:\spc{F}\to\RR$ there is a point $p\in \spc{U}$ such that $\dist{p}{x}{}=f(x)$ for any $x\in \spc{F}$.

If we assume in addition that $\diam \spc{U}\le d$ and instead of extension functions we consider only $d$-extension functions, then we arrive at a definition of {}\emph{$d$-extension property}.

If in addition $\spc{U}$ is separable and complete, then it is called \index{Urysohn space}\emph{Urysohn space} or {}\emph{$d$-Urysohn space} respectively.
\end{thm}


\begin{thm}{Proposition}\label{prop:univeral-separable}
There is a separable metric space with the ($d$-) extension property (for any $d\ge 0$).
\end{thm}

\parit{Proof.}
Choose $d\ge 0$.
Let us construct a separable metric space with  the $d$-extension property.

Let $\spc{X}$ be a compact metric space such that $\diam\spc{X}\le d$.
Denote by $\spc{X}^d$ the space of all $d$-extension functions on $\spc{X}$ equipped with the metric defined by the sup-norm.
Note that the map $\spc{X} \to \spc{X}^d$ defined by $x\mapsto\distfun_x$ is a distance-preserving embedding,
so we can (and will) treat $\spc{X}$ as a subspace of $\spc{X}^d$, or, equivalently, $\spc{X}^d$ is an extension of $\spc{X}$.

Let us iterate this construction.
Start with a one-point space $\spc{X}_0$ and consider a sequence of spaces $(\spc{X}_n)$ defined by $\spc{X}_{n+1}\z=\spc{X}_n^d$.
Note that the sequence is nested;
that is, $\spc{X}_0\subset \spc{X}_1\subset\dots$
and the union
\[\spc{X}_\infty=\bigcup_n\spc{X}_n;\]
comes with metric such that
$\dist{x}{y}{\spc{X}_\infty} = \dist{x}{y}{\spc{X}_n}$
if $x,y\in\spc{X}_n$.

Note that if $\spc{X}$ is compact, then so is $\spc{X}^d$.
It follows that each space $\spc{X}_n$ is compact.
In particular, $\spc{X}_\infty$ is a countable union of compact spaces;
therefore $\spc{X}_\infty$ is separable.

Any finite subspace $\spc{F}$ of $\spc{X}_\infty$ lies in some $\spc{X}_n$ for $n<\infty$.
By construction, there is a point $p\in \spc{X}_{n+1}$ that meets the condition in \ref{def:finite+1} for any extension function $f\:\spc{F}\to\RR$.
That is, $\spc{X}_\infty$ has the $d$-extension property.

The construction of a separable metric space with the extension property requires only minor changes.
First, the sequence should be defined by $\spc{X}_{n+1}\z=\spc{X}_n^{d_n}$, where $d_n$ is an increasing sequence such that $d_n\to\infty$.
Second, the point $p$ should be taken in $\spc{X}_{n+k}$ for sufficiently large $k$, so that $d_{n+k}>\max\{f(x)\}$.
\qeds

\begin{thm}{Proposition}\label{prop:completion-univeral}
If a metric space $\spc{V}$ meets the ($d$-) extension property, then so does its completion.
\end{thm}

\parit{Proof.} 
Let us assume $\spc{V}$ meets the extension property.
We will show that its completion $\spc{U}$ meets the extension property as well.
The $d$-extension case can be proved along the same lines.

Note that $\spc{V}$ is a dense subset in a complete space $\spc{U}$.
Observe that $\spc{U}$ has the {}\emph{approximate extension property};
that is, if $\spc{F}\z\subset\spc{U}$ is a finite set, $\eps>0$, and $f\:\spc{F}\to \RR$ is an extension function, then
there exists $p\in \spc{U}$ such that
\[\dist{p}{x}{}\lg f(x)\pm\eps.\]
for any $x\in\spc{F}$.

Therefore, there is a sequence of points $p_n\in \spc{U}$ such that for any $x\in \spc{F}$, 
\[\dist{p_n}{x}{}\lg f(x)\pm\tfrac1{2^n}.\]

Moreover, we can assume that 
\[\dist{p_n}{p_{n+1}}{} < \tfrac1{2^n}\eqlbl{eq:|pn-pn|}\]
for all large $n$.
Indeed, consider the sets $\spc{F}_n=\spc{F}\cup\{p_n\}$ and the functions $f_n\:\spc{F}_n\to\RR$ defined by $f_n(x)=f(x)$ if $x\ne p_n$ and
\[f_n(p_n)=\max\set{\bigl|\dist{p_n}{x}{}- f(x)\bigr|}{x\in \spc{F}}.\]
Observe that $f_n$ is an extension function for large $n$ and
$f_n(p_n)\z<\tfrac1{2^n}$.
Therefore, applying the approximate extension property recursively we get~\ref{eq:|pn-pn|}.

By \ref{eq:|pn-pn|}, $(p_n)$ is a Cauchy sequence and its limit meets the condition in the definition of extension property (\ref{def:finite+1}).
\qeds

Note that \ref{prop:univeral-separable} and \ref{prop:completion-univeral} imply the following:

\begin{thm}{Theorem}\label{thm:urysohn-exists}
Urysohn space and $d$-Urysohn space for any $d>0$ exist.
\end{thm}

\section{Universality}

A metric space will be called \emph{universal} if it includes as a subspace an isometric copy of any separable metric space.
In \ref{ex:frechet}, we proved that $\ell^\infty$ is a universal space. 
The following proposition shows that an Urysohn space is universal as well.
Unlike $\ell^\infty$, Urysohn spaces are separable;
so it might be considered as a \emph{better} universal space.
Theorem \ref{thm:compact-homogeneous} will give another reason why Urysohn spaces are better.

\begin{thm}{Proposition}\label{prop:sep-in-urys}
An Urysohn space is universal.
That is, if $\spc{U}$ is an Urysohn space, then any separable metric space $\spc{S}$ admits a distance-preserving embedding $\spc{S}\hookrightarrow\spc{U}$.

Moreover, for any finite subspace $\spc{F}\subset \spc{S}$,
any distance-preserving embedding $\spc{F}\hookrightarrow \spc{U}$ can be extended to a distance-preserving embedding $\spc{S}\hookrightarrow\spc{U}$.

A $d$-Urysohn space is $d$-universal;
that is, the above statements hold provided that $\diam\spc{S}\le d$.  
\end{thm}

\parit{Proof.}
We will prove the second statement;
the first statement is its partial case for $\spc{F}=\emptyset$.

The required isometry will be denoted by $x\mapsto x'$.

Choose a dense sequence of points $s_1,s_2,\dotsc\in\spc{S}$.
We may assume that $\spc{F}=\{s_1,\dots,s_n\}$, so $s_i'\in \spc{U}$ are defined for $i\le n$.

The sequence $s_i'$ for $i>n$ can be defined recursively using the extension property in $\spc{U}$.
Namely, suppose that $s_1',\dots,s_{i-1}'$ are already defined.
Since $\spc{U}$ meets the extension property, there is a point $s_i'\in \spc{U}$ such that
\[\dist{s_i'}{s_j'}{\spc{U}}=\dist{s_i}{s_j}{\spc{S}}\]
for any $j<i$.

The constructed map $s_i\mapsto s_i'$ is distance-preserving.
Therefore it can be continuously extended to whole $\spc{S}$.
It remains to observe that the constructed map $\spc{S}\hookrightarrow\spc{U}$ is distance-preserving.
\qeds

\begin{thm}{Exercise}\label{ex:geodesics-urysohn}
Show that any two distinct points in an Urysohn space can be joined by an infinite number of geodesics.
\end{thm}

\begin{thm}{Exercise}\label{ex:compact-extension}
Modify the proofs of \ref{prop:completion-univeral} and \ref{prop:sep-in-urys} to prove the following theorem.
\end{thm}

\begin{thm}{Theorem}\label{thm:compact-extension}
Let $K$ be a compact set in a separable space $\spc{S}$.
Then any distance-preserving map from $K$ to an Urysohn space can be extended to 
a distance-preserving map on whole $\spc{S}$.
\end{thm}

\begin{thm}{Exercise}\label{ex:sc-urysohn}
Show that ($d$-) Urysohn space is simply connected.
\end{thm}

\section{Uniqueness and homogeneity}

\begin{thm}{Theorem}\label{thm:urysohn-unique}
Suppose $\spc{F}\subset \spc{U}$ and $\spc{F}'\subset \spc{U}'$ be finite isometric subspaces in a pair of ($d$-)Urysohn spaces $\spc{U}$ and $\spc{U}'$.
Then any isometry $\iota\:\spc{F}\leftrightarrow \spc{F}'$ can be extended to an isometry $\spc{U}\leftrightarrow \spc{U}'$.

In particular, ($d$-)Urysohn space is unique up to isometry.
\end{thm}

While \ref{prop:sep-in-urys} implies that there are distance-preserving maps $\spc{U}\to \spc{U}'$ and $\spc{U}'\to \spc{U}$,
it does not solely imply the existence of an isometry $\spc{U}\leftrightarrow \spc{U}'$.
Its construction uses the idea of \ref{prop:sep-in-urys}, but it is applied {}\emph{back-and-forth} to ensure that the obtained distance-preserving map is onto.


\parit{Proof.}
Choose dense sequences $a_1,a_2,\dots\in \spc{U}$ and $b'_1,b'_2,\dots\in \spc{U}'$.
We can assume that $\spc{F}=\{a_1,\dots,a_n\}$, $\spc{F}'=\{b_1',\dots,b_n'\}$ and $\iota(a_i)=b_i$ for $i\le n$.

The required isometry $\spc{U}\leftrightarrow \spc{U}'$ will be denoted by $u \leftrightarrow u'$.
Set $a'_i=b'_i$ if $i\le n$.

Let us define recursively $a_{n+1}',b_{n+1}, a_{n+2}', b_{n+2},\dots$ --- on the odd step we define the images of $a_{n+1},a_{n+2},\dots$ and on the even steps we define inverse images of $b'_{n+1},b'_{n+2},\dots$.
The same argument as in the proof of \ref{prop:sep-in-urys} shows that we can construct two sequences $a_1',a_2',\dots\in \spc{U}'$ and $b_1,b_2,\dots\in \spc{U}$ such that
\begin{align*}
\dist{a_i}{a_j}{\spc{U}}&=\dist{a_i'}{a_j'}{\spc{U}'}
\\
\dist{a_i}{b_j}{\spc{U}}&=\dist{a_i'}{b_j'}{\spc{U}'}
\\
\dist{b_i}{b_j}{\spc{U}}&=\dist{b_i'}{b_j'}{\spc{U}'}
\end{align*}
for all $i$ and $j$.

It remains to observe that the constructed distance-preserving bijection defined by $a_i\leftrightarrow a_i'$ and $b_i\leftrightarrow b_i'$ extends
continuously to an isometry $\spc{U}\leftrightarrow \spc{U}'$. 
\qeds

Observe that \ref{thm:urysohn-unique} implies that the Urysohn space (as well as the $d$-Urysohn space) is \index{homogeneous}\emph{finite-set homogeneous}; that is,
\begin{itemize}
 \item any distance-preserving map from a finite subset to the whole space can be extended to an isometry.
\end{itemize}

\begin{thm}{Open question}
Is there a {}\emph{noncomplete} finite-set homogeneous metric space that meets the extension property?
\end{thm}

This is a question of Pavel Urysohn; it appeared already in \cite[§$2(6)$]{urysohn} 
and reappeared in \cite[p. 83]{gromov-2007} with a missing keyword.
In fact, I do not see an example of a 1-point homogeneous space that meets the extension property.

Recall that $S_r(p)_{\spc{X}}$ denotes the sphere of radius $r$ centered at $p$ in a metric space $\spc{X}$;
that is, 
$$S_r(p)_{\spc{X}}=\set{x\in \spc{X}}{\dist{p}{x}{\spc{X}}=r}.$$

\begin{thm}{Exercise}\label{ex:sphere-in-urysohn}
Choose $d\in [0,\infty]$.
Denote by $\spc{U}_d$ the $d$-Urysohn space,
so $\spc{U}_\infty$ is the Urysohn space.

\begin{subthm}{ex:sphere-in-urysohn:sphere}
Assume that $L=S_r(p)_{\spc{U}_d}\ne \emptyset$.
Show that $L$ is isometric to $\spc{U}_{\ell}$; find $\ell$ in terms of $r$ and $d$.
\end{subthm}

\begin{subthm}{ex:sphere-in-urysohn:midpoint}
Let $\ell=\dist{p}{q}{\spc{U}_d}$.
Show that the subset $M\subset\spc{U}_d$ of midpoints between $p$ and $q$ is isometric to $\spc{U}_\ell$.
\end{subthm}

\begin{subthm}{ex:sphere-in-urysohn:homogeneous}
Show that $\spc{U}_d$ is \emph{not} countable-set homogeneous;
that is, there is a distance-preserving map from a countable subset of $\spc{U}_d$ to $\spc{U}_d$ that cannot be extended to an isometry of $\spc{U}_d$.
\end{subthm}
\end{thm}

In fact, the Urysohn space is compact-set homogeneous; more precisely the following theorem holds.

\begin{thm}{Theorem}\label{thm:compact-homogeneous}
Let $K$ be a compact set in a ($d$-)Urysohn space $\spc{U}$.
Then any distance-preserving map $K\to \spc{U}$ can be extended to an isometry of $\spc{U}$.
\end{thm}

A proof can be obtained by modifying the proofs of \ref{prop:completion-univeral} and \ref{thm:urysohn-unique}
the same way as it is done in \ref{ex:compact-extension}.

\begin{thm}{Exercise}\label{ex:homogeneous}
Which of the following metric spaces are 
1-point set homogeneous, finite set homogeneous, compact set homogeneous, countable homogeneous?

\begin{subthm}{ex:homogeneous:euclidean}
Euclidean plane,
\end{subthm}

\begin{subthm}{ex:homogeneous:hilbert}
 Hilbert space $\ell^2$,
\end{subthm}

\begin{subthm}{ex:homogeneous:ell-infty}
 $\ell^\infty$,
\end{subthm}

\begin{subthm}{ex:homogeneous:ell-1}
 $\ell^1$
\end{subthm}
\end{thm}


\section{Remarks}

The statement in \ref{ex:frechet} was proved by Maurice René Fréchet in the paper where he first defined metric spaces \cite{frechet};
its extension \ref{lem:kuratowski} was given by Kazimierz Kuratowski~\cite{kuratowski}.
The question about the existence of a separable universal space was posted by Maurice René Fréchet and answered by
Pavel Urysohn~\cite{urysohn}.

The idea of Urysohn's construction was reused in graph theory; it produces the so-called {}\emph{Rado graph},
also known as {}\emph{Erd\H{o}s–R\'enyi graph} or \emph{random graph}; a good survey on the subject is given by Peter Cameron~\cite{cameron}.

2021-04-13T02:21:25.000
2007
2007.09846
en
https://arxiv.org/abs/2007.09846
We discuss domestic affairs of metric spaces, keeping away from any extra structure. Topics include universal spaces, injective spaces, Hausdorff and Gromov--Hausdorff convergences, and ultralimits.
Metric Geometry (math.MG)
Pure metric geometry: introductory lectures
Qwen/Qwen-72B
1. YES
2. YES