converge.tex

%%!TEX root = the-converge.tex
\chapter{Space of spaces}

In this chapter we discuss the
Gromov--Hausdorff convergence of metric spaces.

%It seems that 
To the best of our knowledge, Hausdorff convergence of subsets of a fixed metric space was first introduced by Felix Hausdorff \cite{hausdorff}, 
and a couple of years later an equivalent definition was given by Wilhelm Blaschke \cite{blaschke}.
A further refinement of this definition was introduced by Zdeněk Frolík \cite{frolik}
and then rediscovered by Robert Wijsman \cite{wijsman}.
However this refinement was a step in the direction of the so-called {}\emph{closed convergence} introduced by Hausdorff in the original book. 
For that reason we call it Hausdorff convergence
instead of
\emph{Hausdorff--Blashcke--Frol\'{\i}k--Wijsman convergence}.

Gromov--Hausdorff convergence was first introduced by David Edwards \cite{edwards}
and rediscovered later by Michael Gromov \cite{gromov-polynomial-growth}.
It was an essential tool in Gromov's proof that any group of polynomial growth has  a nilpotent subgroup of finite index.
Other versions of convergence of metric spaces
were considered earlier, but each time
the definition was limited to very specific types of problems.

The definition of Gromov--Hausdorff convergence of metric spaces uses 
the notion of Hausdorff convergence.
Gromov--Hausdorff convergence means that a sequence of metric spaces admits a sequence of distance-preserving embeddings into a common ambient metric space so that their images converge in the Hausdorff sense.
Our definition of  Gromov--Hausdorff convergence and  Gromov--Hausdorff distance differ somewhat from the standard definition.

\section{Convergence of subsets}

Let $\spc{X}$ be a metric space and $A\subset \spc{X}$.
Recall that the distance from $A$ to a point $x$ in $\spc{X}$
is given by
$$\distfun Ax\df\inf\set{\dist{a}{x}{}}{a\in A}.$$
By this definition, we have $\distfun{\emptyset}x=\infty$ for any $x$.

\begin{thm}{Definition of Hausdorff convergence}\label{def:hausdorff-coverge}
Given a sequence of closed sets $A_n$ in a metric space $\spc{X}$, 
a closed set $A_\infty\subset \spc{X}$ is called the Hausdorff limit of $A_n$,
briefly $A_n\Hto A_\infty$, if 
$$\distfun{A_n}x\to\distfun{A_\infty}x\quad \text{as}\quad n\to\infty$$
for any fixed $x\in \spc{X}$.

In this case the, sequence of closed sets $A_n$ is said to be {}\emph{converging} or \index{Hausdorff convergence}\emph{converging in the sense of Hausdorff}.
\end{thm}

\begin{thm}{Selection theorem}
Let $A_n$ be a sequence of closed sets in a proper metric space $\spc{X}$.
Then $A_n$ has a converging subsequence in the sense of Hausdorff.
\end{thm}

\parit{Proof.}
Since $\spc{X}$ is proper,
we can choose a countable dense set $\{x_1,x_2, \dots\}$ in $\spc{X}$.

If the sequence $a_n=\distfun{A_n}x_\kay$ is unbounded for some $\kay$,
then we can pass to a subsequence of $A_n$ such that 
$\distfun{A_n}x_\kay\to \infty$ as $n\to\infty$ for \emph{any}~$\kay$.
The obtained sequence converges to the empty set.

Now suppose that $a_n=\distfun{A_n}x_\kay$ is bounded for each $\kay$. 
In this case, passing to a subsequence of $A_n$,
we can assume that $\distfun{A_n}x_\kay$ converges as $n\to\infty$ for any fixed $\kay$.

Note that for each $n$, the function $\distfun{A_n}\:\spc{X}\to\RR$ is 1-Lipschitz and nonnegative.
Therefore the sequence $\distfun{A_n}$ converges pointwise to a 1-Lipschitz nonnegative function $f\:\spc{X}\to\RR$.

Set $A_\infty=f^{-1}(0)$.
Since $f$ is 1-Lipschitz, 
$\distfun{A_\infty}y\ge f(y)$ for any $y\in \spc{X}$.
It remains to show that $\distfun{A_\infty}y\le f(y)$ for any $y$.

Assume the  contrary,
that is, $f(z)<R<\distfun{A_\infty}z$ for $z\in \spc{X}$ and $R>0$.
Then for any sufficiently large $n$ there is a point $z_n\in A_n$ such that
$\dist{x}{z_n}{}\le R$.
Since $\spc{X}$ is proper, we can pass to a partial limit $z_\infty$ of $z_n$ as $n\to\infty$.

Clearly  $f(z_\infty)=0$, that is, $z_\infty\in A_\infty$.
On the other hand, 
\[\distfun{A_\infty}y\le\dist{z_\infty}{y}{}\le R<\distfun{A_\infty}y,\] 
a contradiction.
\qeds

\section{Convergence of spaces}

\begin{thm}{Definition}\label{def:comp-metr}
Let $\set{\spc{X}_\alpha}{\alpha\in\IndexSet}$ be a set of metric spaces.
A metric space $\bm{X}$
is called a \index{common space}\emph{common space} of $\set{\spc{X}_\alpha}{\alpha\in\IndexSet}$ if its underlying set is formed by the disjoint union
$$\bigsqcup_{\alpha\in\IndexSet} \spc{X}_\alpha$$ 
and each inclusion $\iota_\alpha\:\spc{X}_\alpha\hookrightarrow\bm{X}$
is distance-preserving.
\end{thm}

\begin{thm}{Definition}\label{def:GH}
Let $\bm{X}$ be a common space for proper metric spaces
$\spc{X}_1,\spc{X}_2,\dots$, and $\spc{X}_\infty$.
Assume that $\spc{X}_n$ forms an open set in $\bm{X}$ for each $n<\infty$ and 
$\spc{X}_n\Hto \spc{X}_\infty$ in $\bm{X}$ as $n\to\infty$.

Then the topology $\GH$ of $\bm{X}$ is called a \index{Gromov--Hausdorff convergence}\emph{Gromov--Hausdorff convergence}
and we write $\spc{X}_n\GHto \spc{X}_\infty$ or $\spc{X}_n\xto{\GH} \spc{X}_\infty$;
the latter notation is used if we need to consider  the specific Gromov--Hausdorff convergence $\GH$.
The space $\spc{X}_\infty$ is called the {}\emph{limit space} of the sequence $\spc{X}_n$ along $\GH$.
\end{thm}

When we write $\spc{X}_n\GHto \spc{X}_\infty$, we mean that we made a choice of a Gromov--Hausdorff convergence.

Note that for a fixed sequence $\spc{X}_n$ of metric spaces, one may construct different Gromov--Hausdorff convergences, say $\spc{X}_n\xto{\GH} \spc{X}_\infty$ and $\spc{X}_n\xto{\GH'} \spc{X}_\infty'$,  and their limit spaces $\spc{X}_\infty$ and $\spc{X}_\infty'$ need not be isometric to each other. 
For example, for the constant sequence $\spc{X}_n\iso\RR_{\ge0}$, 
one may take $\spc{X}_\infty\iso\RR_{\ge0}$.
In this case, a point in the disjoint space $\bm{X}$ can be regarded as a pair $(x,n)\in \RR_{\ge0}\times (\ZZ_>\cup \{\infty\})$ 
and the metric on $\bm{X}$ can be defined by
$$\dist{(x,n)}{(y,m)}{\bm{X}}\df|\tfrac1n+\tfrac1m|+|x-y|,$$
where we assume that $0=\tfrac1\infty$.
On the other hand, one can take $\spc{X}_\infty'\iso\RR$,
and consider the metric
\begin{align*}
\dist{(x,n)}{(y,m)}{\bm{X}'}
&=|\tfrac1n-\tfrac1m|+|(x-n)-(y-m)|,
\\
\dist{(x,n)}{(y,\infty)}{\bm{X}'}
&=\tfrac1n+|(x-n)-y|,
\\
\dist{(x,\infty)}{(y,\infty)}{\bm{X}'}
&=|x-y|,
\end{align*}
where $n, m<\infty$.

\begin{thm}{Induced convergences}
Suppose $\spc{X}_n\xto{\GH}\spc{X}_\infty$
as in Definition \ref{def:GH},
and $\iota_n\:\spc{X}_n\hookrightarrow\bm{X}$, $\iota_\infty\:\spc{X}_\infty\hookrightarrow\bm{X}$ are the corresponding inclusions.

\begin{subthm}{}
A sequence of points $x_n\in\spc{X}_n$ converges to $x_\infty\in\spc{X}_\infty$ (briefly, $x_n\to x_\infty$ or $x_n\xto{\GH} x_\infty$) 
if $\dist{x_n}{x_\infty}{\bm{X}}\to 0$.
\end{subthm}

\begin{subthm}{}
A sequence of closed sets 
$\mathfrak{C}_n\subset \spc{X}_n$ 
converges to a closed  set 
$\mathfrak{C}_\infty\subset \spc{X}_\infty$ (briefly, $\mathfrak{C}_n\to \mathfrak{C}_\infty$ or $\mathfrak{C}_n\xto{\GH} \mathfrak{C}_\infty$)
if $\mathfrak{C}_n\Hto\mathfrak{C}_\infty$ as subsets of $\bm{X}$.
\end{subthm}

\begin{subthm}{}
A sequence of open sets $\Omega_n\subset \spc{X}_n$ 
converges to an open set $\Omega_\infty\subset \spc{X}_\infty$
(briefly, $\Omega_n\to \Omega_\infty$ 
or $\Omega_n\xto{\GH} \Omega_\infty$)
if the complements $\spc{X}_n\setminus \Omega_n$ converge to the complement $\spc{X}_\infty\setminus \Omega_\infty$ as closed sets.
\end{subthm}


\begin{subthm}{} Let $\spc{X}_n\xto{\GH} \spc{X}_\infty$ and $\spc{Y}_n\xto{\theta} \spc{Y}_\infty$. 
A sequence of submaps (where a submap is a map defined on a subset; see Section~\ref{sec:submaps}) $\map_n\:\spc{X}_n\subto \spc{Y}_n$ converges to a submap $\map_\infty\:\spc{X}_\infty\subto \spc{Y}_\infty$ if the following conditions hold
\begin{itemize}
\item $\Dom\map_n\to \Dom\map_\infty$ as a sequence of open sets.

\item for any $x_\infty\in \Dom \map_\infty$ and any sequence $x_n\in \spc{X}_n$ such that $x_n\to x_\infty$, we have
\[\spc{Y}_n\ni \map _n(x_n)\xto\theta \map_\infty(x_\infty)\in\spc{Y}_\infty\] 
as $n\to\infty$.
\end{itemize}
\end{subthm}

\begin{subthm}{} Given a sequence of measures $\mu_n$ on $\spc{X}_n$,
%denote by $\iota_n\#\mu_n$ the pushforward measures on $\bm{X}$. 
%V: I would suggest using the notation ${\iota_n}_\#\mu_n$, i.e. making $\#$  a subindex. That's a much more standard notation for pushforward. 
%A: in this case we get double index --- I do not like it. We may remove pushforward completely.
%S; I removed the notation
we say that $\mu_n$ weakly converges to a measure $\mu_\infty$ on $\spc{X}_\infty$ 
(briefly, $\mu_n\xto{}
\mu_\infty$ or $\mu_n\xto{\GH}
\mu_\infty$) 
if the push-forward measures of $\mu_n$
%$\iota_n\#\mu_n$ 
weakly converge to the push-forward measure of $\mu_\infty$.

In other words, 
if for any continuous function $\phi\:\bm{X}\to\RR$ with a compact support, we have 
\[\int\limits_{\spc{X}_n} 
\phi\circ\iota_n
\cdot
\mu_n
\to 
\int\limits_{\spc{X}_\infty}
\phi\circ\iota_\infty
\cdot\mu_\infty\]
as $n\to\infty$.
\end{subthm}
\end{thm}

\parbf{Liftings.}
Given a Gromov--Hausdorff convergence 
$\spc{X}_n\GHto \spc{X}_\infty$
and a point $p_\infty\in\spc{X}_\infty$, any sequence of points $p_n\in\spc{X}_n$ such that $p_n\GHto p_\infty$  will be called a \index{Gromov--Hausdorff convergence!lifting of a point}\emph{lifting} of $p_\infty$.
The point $p_n\in \spc{X}_n$ will be called a {}\emph{lifting} of $p_\infty$ to $\spc{X}_n$.
We will also say that $\distfun{p_n}{}{}\:\spc{X}_n\to \RR$ 
is a \index{Gromov--Hausdorff convergence!lifting of a distance function}\emph{lifting} 
of the distance function $\distfun{p_\infty}{}{}\:\spc{X_\infty}\to \RR$.
Clearly $\distfun{p_n}{}{}\GHto\distfun{p_\infty}{}{}$.

Note that liftings are not uniquely defined.

Similarly, we may refer to liftings of a point array
$\bm{p}_\infty\z =(p_\infty^1,p_\infty^2,\dots,p_\infty^\kay)$
and of the corresponding distance map 
$\distfun{\bm{p}_\infty}{}{}\:\spc{X}_\infty\to\RR^\kay$,
$$\distfun{\bm{p}_\infty}{}{}\:x\mapsto(\dist{p_\infty^1}{x}{},\dist{p_\infty^2}{x}{},\dots,\dist{p_\infty^k}{x}{}).$$

\section{Gromov's selection theorem}

\begin{thm}{Gromov's selection theorem}\label{thm:gromov-selection}
Let $\spc{X}_n$ be a sequence of proper metric spaces 
with marked points $x_n\in \spc{X}_n$.
Assume that for any $R>0$, $ \eps>0$, there is $N=N(R,\eps)\in\ZZ_{>0}$ 
such that for each $n$
the ball $\cBall[x_n,R]\subset \spc{X}_n$ admits a finite $\eps$-net with at most $N$ points.
Then a subsequence of $\spc{X}_n$ admits a Gromov--Hausdorff convergence 
such that the sequence of marked points $x_n\in\spc{X}_n$ 
%(sub)converges.
converges.
\end{thm}

\parit{Proof.}
By the main assumption, there is a sequence of integers $M_1\z<M_2<\dots$
such that in each space $\spc{X}_n$
there is a sequence of points $z_{i,n}\in\spc{X}_n$ for which  
\[\dist{z_{i,n}}{x_n}{\spc{X}_n}\le \kay+1\quad \text{if}\quad i\le M_\kay\]
and $\{z_{1,n},\dots,z_{M_\kay,n}\}$ is a $\tfrac1\kay$-net in $\cBall[x_n,\kay]_{\spc{X}_n}$.

Passing to a subsequence, we may assume that the sequence \[\ell_n=\dist{z_{i,n}}{z_{j,n}}{\spc{X}_n}\] 
converges for any $i$ and $j$.

Let us consider a countable set of points $\spc{W}=\{w_1,w_2,\dots\}$
equipped with the pseudometric defined by 
\[\dist{w_i}{w_j}{\spc{W}}
=
\lim_{n\to\infty}\dist{z_{i,n}}{z_{j,n}}{\spc{X}_n}.\]
Let $\hat{\spc{W}}$ be the metric space corresponding to $\spc{W}$.
Denote by
$\spc{X}_\infty$ the completion of $\hat{\spc{W}}$.

It remains to construct a metric on the disjoint union of \[\bm{X}=\spc{X}_\infty\sqcup\spc{X}_1\sqcup\spc{X}_2\sqcup\dots\] 
satisfying definitions \ref{def:comp-metr} and \ref{def:GH}.

Such a  metric can be defined as follows.
Fix a sequence $\eps_\kay\to0+$
and let $N_\kay$ be the minimal integer such that
\[\dist{w_i}{w_j}{\spc{W}}
\lege
\dist{z_{i,n}}{z_{j,n}}{\spc{X}_n}\pm\eps_\kay
\]
if $i,j\le N_\kay$ and $n\ge N_\kay$. 
Let us equip $\bm{X}$ with the maximal metric such that all the inclusions $\iota_n\:\spc{X}_n\to\bm X$  and $\iota_\infty\:\spc{X}_\infty\to\bm X$ are isometric and 
$
\dist{z_{i,n}}{w_i}{}\le \eps_\kay
$
for $i\le N_\kay$ and $n\ge N_\kay$.
It is easy to verify  that such a metric on $\bm X$ satisfies  \ref{def:comp-metr} and \ref{def:GH}.
\qeds

\section{Convergence of compact spaces.}

\begin{thm}{Definition}
Let $\spc{X}$ and $\spc{Y}$ be metric spaces.
A map $f\:\spc{X}\to\spc{Y}$
is called an \index{isometry!$\eps$-isometry}\emph{$\eps$-isometry}
if the following two conditions hold:
\begin{subthm}{}
$\Im f$ is an $\eps$-net in $\spc{Y}$.
\end{subthm}

\begin{subthm}{}
$\bigl|\dist{f(x)}{f(x')}{\spc{Y}}-\dist{x}{x'}{\spc{X}}\bigr|\le \eps$ for any $x,x'\in\spc{X}$.
\end{subthm}

\end{thm}

\begin{thm}{Lemma}\label{lem:almost-isom}
Let $\spc{X}_1,\spc{X}_2,\dots$, let $\spc{X}_\infty$ be metric spaces, and let $\eps_n\to\0+$ as $n\to\infty$.
Suppose that either 

\begin{subthm}{lem:almost-isom-a}
for each $n$ there is an $\eps_n$-isometry $f_n\:\spc{X}_n\to\spc{X}_\infty$, or
\end{subthm}

\begin{subthm}{lem:almost-isom-b}
for each $n$ there is an $\eps_n$-isometry $h_n\:\spc{X}_\infty\to\spc{X}_n$.
\end{subthm}

Then there is a Gromov--Hausdorff convergence $\spc{X}_n\GHto \spc{X}_\infty$.
\end{thm}


\parit{Proof.}
To prove part \ref{SHORT.lem:almost-isom-a} let us construct a common space $\bm{X}$ for the spaces $\spc{X}_1,\spc{X}_2,\dots$, and $\spc{X}_\infty$
by taking the metric $\rho$ on the disjoint union $\spc{X}_\infty\sqcup\spc{X}_1\sqcup\spc{X}_2\sqcup\dots$ that is defined the following way:
\begin{align*}
\rho(x_n,y_n)&=\dist{x_n}{y_n}{\spc{X}_n},\quad \rho(x_\infty,y_\infty)=\dist{x_\infty}{y_\infty}{\spc{X}_\infty},
\\
\rho(x_n,x_\infty)&=\inf\set{\dist{x_n}{y_n}{\spc{X}_n}+\eps_n+\dist{x_\infty}{f(y_n)}{\spc{X}_\infty}}{{y_n}\in \spc{X}_n},
\\
\rho(x_n,x_m)&=\inf\set{\rho(x_n,y_\infty)+\rho(x_m,y_\infty)}{y_\infty\in\spc{X}_\infty},
\end{align*}
where we assume that $x_m\in \spc{X}_m$, $x_n\in \spc{X}_n$, and $x_\infty\in \spc{X}_\infty$. 

It remains to observe that $\rho$ is indeed a metric and 
$\spc{X}_n\Hto \spc{X}_\infty$ in~$\bm{X}$.

The proof of the second part is analogous; one only needs to change one line in the definition of $\rho$ to the following:
\[\rho(x_n,x_\infty)=\inf\set{\dist{x_n}{h(y_\infty)}{\spc{X}_n}+\eps_n+\dist{x_\infty}{y_\infty}{\spc{X}_\infty}}{{y_\infty}\in \spc{X}_\infty}.\]
\qedsf

\begin{thm}{Definition}\label{def: inequality-of-spaces}
 Given two compact spaces $\spc{X}$ and $\spc{Y}$, we will write 
\begin{itemize}
\item $\spc{X}\le \spc{Y}$ if there is a noncontracting map $\map\:\spc{X}\to \spc{Y}$.
\item $\spc{X}\le \spc{Y}+\eps$ if there is a map $\map\:\spc{X}\to \spc{Y}$ such that for any $x,x'\in \spc{X}$ we have
\[\dist{x}{x'}{}\le \dist{\map(x)}{\map(x')}{}+\eps.\]
\end{itemize}

\end{thm}

\begin{thm}{Lemma}\label{lem:>=-isometry}
Let $\spc{X}$ and $\spc{Y}$ be two metric spaces, and let $\spc{X}$ be compact.
Then
\[
\spc{X}\ge\spc{Y}\ge\spc{X}
\quad\Longleftrightarrow\quad 
\spc{X}\iso\spc{Y}.
\]

\end{thm}

The following proof was suggested by Travis Morrison.

\parit{Proof.}
Let $f\: \spc{X} \to \spc{Y}$ 
and $g\: \spc{Y} \to \spc{X}$ be noncontracting mappings.
It is sufficient to prove that $h  = g\circ f\:\spc{X}\to \spc{X}$ is an isometry. 

Given any pair of points $x,y\in \spc{X}$, 
let $x_n\z=h^{\circ n}(x)$ and $y_n\z=h^{\circ n}(y)$.
Since $\spc{X}$ is compact, one can choose an increasing sequence of integers $n_\kay$
such that both sequences $x_{n_i}$ and $y_{n_i}$
converge.
In particular, both of these sequences  are 
%converging in itself;
Cauchy, 
that is,
\[
\dist{x_{n_i}}{x_{n_j}}{},\dist{y_{n_i}}{y_{n_j}}{}\to 0
\]
as $\min\{i,j\}\to\infty$.
Since $h$ is noncontracting, we have
\[
\dist{x}{x_{|n_i-n_j|}}{}\le \dist{x_{n_i}}{x_{n_j}}{}.
\]
It follows that  
there is a sequence $m_i\to\infty$ such that
\[
x_{m_i}\to x\quad \text{and}\quad y_{m_i}\to y\quad \text{as}\quad i\to\infty.
\eqlbl{eq:x_l->x}
\]

Let $\ell_n=\dist{x_n}{y_n}{}$.
Since $h$ is noncontracting, the sequence $\ell_n$ is nondecreasing.
On the other hand, 
from \ref{eq:x_l->x} it follows that $\ell_{m_i}\to\dist{x}{y}{}=\ell_0$ as $m_i\to\infty$;
that is, $\ell_n$ is a constant sequence.
In particular, $\ell_0=\ell_1$ for any $x$ and $y$ in $\spc{X}$,
so $h$ is a distance-preserving map.

Thus $h(\spc{X})$ is isometric to $\spc{X}$.
From \ref{eq:x_l->x}, $h(\spc{X})$ is everywhere dense.
Since $\spc{X}$ is compact, $h(\spc{X})=\spc{X}$.
\qeds




The \index{Gromov--Hausdorff distance}\emph{Gromov--Hausdorff distance} between isometry classes of compact metric spaces $\spc{X}$ and $\spc{Y}$, is defined by
\[\GHdist(\spc{X},\spc{Y})
\df
\inf\set{\eps>0}{\spc{X}\le \spc{Y}+\eps\ \text{and}\ \spc{Y}\le \spc{X}+\eps}.
\]
The Gromov--Hausdorff distance turns the set of all isometry classes of compact metric spaces into a metric space.
The following theorem shows that convergence in this space coincides with the Gromov--Hausdorff convergence defined above.

\begin{thm}{Theorem} Let $\spc{X}_1,\spc{X}_2,\dots$, and let $\spc{X}_\infty$ be compact metric spaces.
Then there is a convergence $\spc{X}_n\GHto \spc{X}_\infty$ if and only if
$\GHdist(\spc{X}_n,\spc{X}_\infty)\to 0$ as $n\to\infty$.

\end{thm}

\parit{Proof; if part.}
Suppose $a_n\:\spc{X}_\infty\to \spc{X}_n$
and $b_n\:\spc{X}_n\to \spc{X}_\infty$ are sequences of maps such that
\[\dist{a_n(x)}{a_n(y)}{\spc{X}_\infty}
\ge
\dist{x}{y}{\spc{X}_n}-\delta_n,\]
\[\dist{b_n(v)}{b_n(w)}{\spc{X}_n}
\ge
\dist{v}{w}{\spc{X}_\infty}-\delta_n\]
for any $x,y\in \spc{X}_n$, $v,w\in\spc{X}_\infty$, and a sequence $\delta_n\to0+$.

Fix $\eps>0$ and choose a maximal $\eps$-packing $\{x^1,x^2,\dots,x^\kay\}$ in $\spc{X}_\infty$ such that 
$\sum_{i<j}\dist{x^i}{x^j}{}$ is maximal.
Note that 
\[\dist{a_n\circ b_n(x^i)}{a_n\circ b_n(x^j)}{}\ge\dist{x^i}{x^j}{}-2\cdot\delta_n.\]
Since $\sum_{i<j}\dist{x^i}{x^j}{}$ is maximal, 
\[\dist{a_n\circ b_n(x^i)}{a_n\circ b_n(x^j)}{}\to\dist{x^i}{x^j}{}\]
for all $i$ and $j$ as $n\to\infty$.
For all large $n$,
we have $2\cdot\delta_n<\dist{x^i}{x^j}{}-\eps$,
and so 
\[\dist{b_n(x^i)}{b_n(x^j)}{\spc{X}_n}>\eps
\quad\text{and}\quad
\dist{a_n\circ b_n(x^i)}{a_n\circ b_n(x^j)}{\spc{X}_\infty}>\eps\] 
for all $i\ne j$.
Therefore for each large $n$, 
the set $\{a_n\circ b_n(x^i)\}$ is a maximal $\eps$-packing and hence an $\eps$-net in $\spc{X}_\infty$.

Since $\{a_n\circ b_n(x^i)\}$ is an $\eps$-net in $\spc{X}_\infty$, we have that 
for any $y_n\in\spc{X}_n$ there is $x^i$ such that $\dist{a_n\circ b_n(x^i)}{a_n(y_n)}{}<\eps$.
Thus $\dist{b_n(x^i)}{y_n}{}<\eps+\delta_n$, 
that is, $\{b_n(x^i)\}$ is a $(\eps+\delta_n)$-net in $\spc{X}_n$.

Given $y\in \spc{X}_n$, choose $x^i$ so that $\dist{b_n(x^i)}{y_n}{}<\eps+\delta_n$ and define $h_n(y)=a_n\circ b_n(x^i)$.
Observe that $h_n$ is a $3\cdot\eps$-isometry for all large $n$.
Since $\eps>0$ is arbitrary, there is a sequence of $\eps_n$-isometries $\spc{X}_n\to\spc{X}_\infty$ such that $\eps_n\to\0+$ as $n\to\infty$.
It remains to apply \ref{lem:almost-isom}.

\parit{Only-if part.}
Assume $\spc{X}_n\xto{\GH}\spc{X}_\infty$.
Fix $\eps>0$, and choose a maximal $\eps$-packing $\{x^1,x^2,\dots,x^\kay\}$ in $\spc{X}_\infty$.
For each $x^i$, 
choose a sequence $x^i_n\in\spc{X}_n$ 
such that $x^i_n\to x^i$.
Define a map $a_n\: \spc{X}_n\to\spc{X}_\infty$
%S: note addition of previous line 
such that $a_n(x^i_n)=x_n$.
Note that for all large $n$, we have $\dist{x^i_n}{x^j_n}{}>\eps$.
For each point $z\in \spc{X}_\infty$, choose $x^i$ so that $\dist{z}{x^i}{}<\eps$. 
Define a map $b_n\:\spc{X}_\infty\to\spc{X}_n$ by setting 
$b_n(z)=x^i_n$.
Observe that 
\[\dist{b_n(y)}{b_n(z)}{\spc{X}_n}+3\cdot\eps>\dist{y}{z}{\spc{X}_\infty}\]
for all large $n$.

In the same way we can construct a map $a_n\:\spc{X}_n\to\spc{X}_\infty$ such that 
\[\dist{a_n(y)}{a_n(z)}{\spc{X}_\infty}+3\cdot\eps>\dist{y}{z}{\spc{X}_n}.\]
Hence $\GHdist(\spc{X}_n,\spc{X}_\infty)\to 0$ as $n\to \infty$.
\qeds

The following theorem states that the isometry class of a Gromov--Hausdorff limit is uniquely defined if it is compact. 

\begin{thm}{Theorem}\label{thm:GH-compact}
Let $\spc{X}_1,\spc{X}_2,\dots$, and let $\spc{X}_\infty$ and $\bar{\spc{X}}_\infty$ be metric spaces
such that $\spc{X}_n\xto{\GH}\spc{X}_\infty$, 
$\spc{X}_n\xto{\bar\GH}\bar{\spc{X}}_\infty$.

Assume that $\bar{\spc{X}}_\infty$ is compact.
Then $\spc{X}_\infty\iso \bar{\spc{X}}_\infty$.
\end{thm}


\parit{Proof.}
For each point $x_\infty\in\spc{X}_\infty$,
choose  liftings $x_n\in\spc{X}_n$.

Choose a nonprincipal ultrafilter $\o$ on $\mathbb N$.
Define $\bar x_\infty\in \bar{\spc{X}}_\infty$ as the $\o$-limit of $x_n$ with respect to $\bar \tau$.
We claim that the map $x_\infty\to \bar x_\infty$ is an isometry.

Indeed, by the definition of Gromov--Hausdorff convergence, 
\[\dist{\bar x_\infty}{\bar y_\infty}{\bar{\spc{X}}_\infty}
=
\lim_{n\to\o}\dist{x_n}{y_n}{\spc{X}_n}
=
\dist{x_\infty}{y_\infty}{\spc{X}_\infty}.
\]
Thus the map $x_\infty\to\bar x_\infty$ gives a distance-preserving map
$\map\:\spc{X}_\infty\hookrightarrow\bar{\spc{X}}_\infty$.
In particular,  
$\spc{X}_\infty$ is compact.
Switching $\spc{X}_\infty$ and $\bar{\spc{X}}_\infty$ and applying the same argument, 
we get an isometric embedding 
$\bar{\spc{X}}_\infty\hookrightarrow\spc{X}_\infty$.
Now the result follows from Lemma~\ref{lem:>=-isometry}.
\qeds

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

\begin{thm}{Exercise}\label{ex:GH-proper-marked}
Let $\spc{X}_n$ be a sequence of metric spaces that admits 
two Gromov--Hausdorff convergences
$\GH$ and $\GH'$.
Assume 
$\spc{X}_n\xto{\GH}\spc{X}_\infty$ and $\spc{X}_n\xto{\GH'}\spc{X}_\infty'$.
Show that if $\spc{X}_\infty$ is proper and there is a sequence of points $x_n\in \spc{X}_n$ 
that converges in both
$\GH$ and $\GH'$, then $\spc{X}_\infty\iso\spc{X}_\infty'$.
\end{thm}

\sectionmark{Ultralimits revisited}
\section{Ultralimits revisited}

Recall that $\o$ denotes an ultrafilter of the set of natural numbers.

\begin{thm}{Theorem}\label{thm:ultra-GH}
Assume $\spc{X}_n$ is a sequence of complete metric spaces. 
Let $\spc{X}_n\to \spc{X}_\o$ as $n\to\o$,
and let $\spc{Y}_n$ 
be a sequence of subspaces of the $\spc{X}_n$ such that $\spc{Y}_n\GHto\spc{Y}_\infty$. 
Then there is a distance-preserving map 
$\iota:\spc{Y}_\infty\to \spc{X}_\o$.

Moreover:

\begin{subthm}{thm:ultra-GH:a}
If $\spc{X}_n\GHto \spc{X}_\infty$ 
and $\spc{X}_\infty$ is compact, then 
$\spc{X}_\infty$ is isometric to $\spc{X}_\o$.
\end{subthm}

\begin{subthm}{thm:ultra-GH:b}
If $\spc{X}_n\GHto \spc{X}_\infty$ 
and $\spc{X}_\infty$ is proper, then 
$\spc{X}_\infty$ is isometric to a metric component of $\spc{X}_\o$.
\end{subthm}

\end{thm}

\parit{Proof.} 
For each point $y_\infty\in \spc{Y}_\infty$ 
choose a lifting $y_n\in \spc{Y}_n$.
Pass to the $\o$-limit $y_\o\in \spc{X}_\o$ of $y_n$.
Clearly for any $y_\infty,z_\infty\in \spc{Y}_\infty$, 
we have 
\[\dist{y_\infty}{z_\infty}{\spc{Y}_\infty}=\dist{y_\o}{z_\o}{\spc{X}_\o};\] 
that is, the map $y_\infty\mapsto y_\o$ gives a distance-preserving map $\iota:\spc{Y}_\infty\to \spc{X}_\o$. 


\parit{\ref{SHORT.thm:ultra-GH:a}$+$\ref{SHORT.thm:ultra-GH:b}.}
Fix $x_\o\in \spc{X}_\o$.
Choose a sequence $x_n$ of points in $\spc{X}_n$,  
such that $x_n\to x_\o$ as $n\to\o$. 

Denote by $\bm{X}=\spc{X}_\infty\sqcup\spc{X}_1\sqcup\spc{X}_2\sqcup\dots$ the common space for the convergence $\spc{X}_n\GHto \spc{X}_\infty$,
as in the definition of Gromov--Hausdorff convergence.
Note that $x_n$ is a sequence of points in~$\bm{X}$.

If the $\o$-limit $x_\infty$ of $x_n$ in $\bm{X}$ exists, 
it must lie in $\spc{X}_\infty$. 

The point $x_\infty$, if defined, does not depend on the choice of $x_n$.
Indeed, if $y_n\in\spc{X}_n$ is another sequence such that $y_n\to x_\o$ as $n\to\o$, then 
\[
\dist{y_\infty}{x_\infty}{}=\lim_{n\to\o}\dist{y_n}{x_n}{}=0;
\]
therefore, $x_\infty=y_\infty$.


This way we obtain a map $\nu\:x_\o\to x_\infty$, defined on  $\Dom\nu \subset\spc{X}_\o$.
By construction of $\iota$, 
we have $\iota\circ\nu(x_\o)=x_\o$ for any $x_\o\in \Dom\nu$.

Finally note that if $\spc{X}_\infty$ is compact, then $\nu$ is defined on all of $\spc{X}_\o$;
this proves \ref{SHORT.thm:ultra-GH:a}.

If $\spc{X}_\infty$ is proper, choose any point $z_\infty\in \spc{X}_\infty$
and set $z_\o=\iota(z_\infty)$.
For any point $x_\o\in \spc{X}_\o$ at finite distance from $z_\o$,
for the sequence $x_n$ 
as above we have that $\dist{z_n}{x_n}{}$ is bounded for $\o$-almost all $n$.
Since $\spc{X}_\infty$ is proper, $\nu(x_\o)$ is defined;
in other words, $\nu$ is defined on the metric component of~$z_\o$.
Hence \ref{SHORT.thm:ultra-GH:b} follows.
\qeds