\documentclass{article}%
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2606}
%TCIDATA{CSTFile=40 LaTeX article.cst}
%TCIDATA{Created=Tuesday, June 06, 2006 14:02:17}
%TCIDATA{LastRevised=Wednesday, August 09, 2006 10:29:55}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{<META NAME="DocumentShell" CONTENT="Standard LaTeX\Blank - Standard LaTeX Article">}
%TCIDATA{Language=American English}
\newtheorem{theorem}{Theorem}
\newtheorem{acknowledgement}[theorem]{Acknowledgement}
\newtheorem{algorithm}[theorem]{Algorithm}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{case}[theorem]{Case}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conclusion}[theorem]{Conclusion}
\newtheorem{condition}[theorem]{Condition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{criterion}[theorem]{Criterion}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{exercise}[theorem]{Exercise}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{solution}[theorem]{Solution}
\newtheorem{summary}[theorem]{Summary}
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\begin{document}

\title{Project: The space of metric spaces}
\maketitle

\section{Hausdorff distance}

One can define a metric structure on $S,$ the closed subsets of a metric space
$\left(  X,d\right)  ,$ as follows. If $F,G$ are closed subsets of $X,$ then
\[
d_{H}\left(  F,G\right)  =\inf\left\{  \varepsilon:F\subset B_{\varepsilon
}\left(  G\right)  \text{ and }G\subset B_{\varepsilon}\left(  F\right)
\right\}
\]
where $B_{\varepsilon}\left(  F\right)  =\left\{  x\in X:d\left(  x,F\right)
<\varepsilon\right\}  $ and $d\left(  x,F\right)  =\inf\left\{  d\left(
x,y\right)  :y\in F\right\}  .$ 

\begin{enumerate}
\item Show that $d_{H}$ defines a metric on $S$. The metric $d_{H}$ is called
the Hausdorff metric. 

\item Show that if $X$ is compact, then $S$ with the metric topology generated
by $d_{H}$ is complete. (Hint: Let $A_{n}$ be a Cauchy sequence in $S.$ By
passing to a subsequence, assume that $d_{H}\left(  A_{n},A_{n+1}\right)
<1/2^{n}.$ Define $A$ to be the set of all points $x$ that are the limits of
sequences $x_{1},x_{2},\ldots$ such that $x_{i}\in A_{i}$ and $d\left(
x_{i},x_{i+1}\right)  <1/2^{i}.$ Show that $A_{i}\rightarrow\bar{A}.$

\item Show that if $X$ is compact, then so is the set of closed subsets of $X$
in the metric topology generated by $d_{H}$ is totally bounded. (Hint: Use
compactness to show that for any $\varepsilon,$ $X$ is covered by a finite set
of balls of radius less than $\varepsilon$ and show that every closed subset
is in the $\varepsilon$ ball of some subset of the set of centers of those balls.)
\end{enumerate}

Conclude that if $X$ is compact, then so is the set of closed subsets of $X$
in the metric topology generated by $d_{H}$ is complete.

\section{Gromov-Hausdorff distance}

Recall that if $\left(  X,d_{X}\right)  $ and $\left(  Y,d_{Y}\right)  $ are
metric spaces, an isometric embedding is an injective map $\Phi:X\rightarrow
Y$ such that $d_{Y}\left(  \Phi\left(  x\right)  ,\Phi\left(  x^{\prime
}\right)  \right)  =d_{X}\left(  x,x^{\prime}\right)  .$

We can define a metric on the set of compact metric spaces as follows. Given
$\left(  X,d_{X}\right)  $ and $\left(  Y,d_{Y}\right)  $ define the
Gromov-Hausdorff distance between them as
\[
d_{GH}\left(  X,Y\right)  =\inf\left\{  d_{H}\left(  \Phi\left(  X\right)
,\Psi\left(  Y\right)  \right)  \right\}
\]
where $d_{H}$ is the Hausdorff distance on the closed subsets of some metric
space $Z$ and the inf is taken over all isometric embeddings $\Phi
:X\rightarrow Z$ and $\Psi:Y\rightarrow Z$.

\begin{enumerate}
\item Show that $d_{GH}$ is a metric on the space of compact metric spaces
modulo isometries.

\item We can define a different metric $d_{GH}^{\prime}$ as follows. Define an
$\varepsilon$-approximate isometry to be a (not-necessarily continuous) map
$\phi:X\rightarrow Y$ such that $B_{\varepsilon}\left(  \phi\left(  X\right)
\right)  =Y$ and $\left\vert d_{Y}\left(  \phi\left(  x\right)  ,\phi\left(
x^{\prime}\right)  \right)  -d_{X}\left(  x,x^{\prime}\right)  \right\vert
<\varepsilon$ for all $x,x^{\prime}\in X.$ Define $d_{GH}^{\prime}$ as
\[
d_{GH}^{\prime}\left(  X,Y\right)  =\inf\left\{  \varepsilon:\text{there exist
}\varepsilon\text{-approx. isometries }X\rightarrow Y\text{ and }Y\rightarrow
X\right\}  .
\]
Show that $d_{GH}$ and $d_{GH}^{\prime}$ generate the same topology.

\item Show that the sequence of circles of radius $1/n$ converge to a point in
the Gromov-Hausdorff topology. This simple example illustrates why the
Gromov-Hausdorff topology is so interesting. It allows two spaces to be close
even if they are not homeomorphic.

\item Show that for any metric space $X$ and any $\varepsilon>0$ there is a
metric on a finite set of points $F$ such that $d_{GH}\left(  X,F\right)
<\varepsilon.$ Hence metrics on finite point sets are dense with respect to
the Gromov-Hausdorff topology. $F$ is called an $\varepsilon$-net.

\item For compact metric spaces $X$ and $\left\{  X_{n}\right\}
_{n=1}^{\infty}$, we have that $X_{n}\rightarrow X$ in the Gromov-Hausdorff
topology if and only if for every $\varepsilon>0$ there exists a finite
$\varepsilon$-net $S$ in $X$ and $\varepsilon$-nets $S_{n}$ in each $S$ such
that $S_{n}\rightarrow S$ in the Gromov-Hausdorff topology. Hence convergence
of metric spaces in Gromov-Hausdorff topology is equivalent to convergence of
$\varepsilon$-nets.

\item Theorem: Let $C$ be a collection of compact metric spaces such that (1)
there is a constant $D$ such that the diameter of $X$ is bounded by $D$ for
all $X\in C$ and (2) for every $\varepsilon>0$ there exists a natural number
$N=N\left(  \varepsilon\right)  $ such that for every $X\in C$ there is a set
of points $x_{1},\ldots,x_{N}\in X$ such that $X=%
%TCIMACRO{\dbigcup \limits_{i=1}^{N}}%
%BeginExpansion
{\displaystyle\bigcup\limits_{i=1}^{N}}
%EndExpansion
B\left(  x_{i},\varepsilon\right)  $ (note that these balls are not required
to be disjoint). Then $C$ is precompact in the Gromov-Hausdorff topology, i.e.
any sequence in $C$ has a subsequence which converges (though the limit may
not remain in $C$).

We step through this proof as follows: Consider a sequence $\left\{
X_{n}\right\}  _{n=1}^{\infty}$ of spaces in $C.$

\begin{enumerate}
\item Show that for each $k$ and $n,$ there exists a finite set of points
$x_{i}$ which form a $1/k$-net in $X_{n}.$ Now show there is a sequence
$\left\{  x_{i,n}\right\}  _{i=1}^{\infty}$ consisting of the the union of the
$x_{i}$ for $k=1,2,3,\ldots$ (here we have a different sequence for each $n$).
Show that $\left\{  x_{i,n}\right\}  _{i=1}^{\infty}$ is a countable, dense
subset of $X_{n}$ (recall a set is dense in $X$ if its closure is all of $X$)
and there exists $M\left(  k\right)  =M\left(  k-1\right)  +N\left(
1/k\right)  $ (take $M\left(  1\right)  =1$) independent of $n$ such that
$\left\{  x_{i,n}\right\}  _{i=1}^{M\left(  k\right)  }$ form a $1/k$-net.
(Hint: use condition (2) in the theorem.)

\item Show that there is a subsequence of $\left\{  X_{n}\right\}  $ such that
$\left\{  d\left(  x_{i,n},d_{j,n}\right)  \right\}  _{n=1}^{\infty}$
converges for all $i,j.$

\item Reindex the subsequence so that it is once again indexed by $n.$ Define
a metric space on the abstract countable set $\left\{  x_{i}\right\}
_{i=1}^{\infty}$ in the following way. Define $d\left(  x_{i},x_{j}\right)  $
by
\[
d\left(  x_{i},x_{j}\right)  =\lim_{n\rightarrow\infty}d\left(  x_{i,n}%
,x_{j,n}\right)  .
\]
This may not be a metric because $d\left(  x_{i},x_{j}\right)  $ may equal
zero when $i\neq j.$ Define the metric space by quotienting out by the
relation that $x_{i}\sim x_{j}$ if $d\left(  x_{i},x_{j}\right)  =0.$ Show
this is a metric space. We will denote this quotient space by $\tilde{X}$ and
elements in the quotient by $\tilde{x}_{i}$

\item For each $k,$ consider the sets $S^{k}=\left\{  \tilde{x}_{i}:1\leq
i\leq M\left(  k\right)  \right\}  $ and $S_{n}^{k}=\left\{  \tilde{x}%
_{i,n}:1\leq i\leq M\left(  k\right)  \right\}  .$ We know that $S_{n}^{k}$ is
a $1/k$-net. Show that for each $i$ there is a $j\leq M\left(  k\right)  $
such that $d\left(  x_{i,n},x_{j,n}\right)  <1/k$ for infinitely many $n.$
Conclude that $S^{n}$ is a $1/k$-net in $\tilde{X}.$

\item Show that $X_{n}$ converges to $\tilde{X}.$ Show that $\tilde{X}$ is
totally bounded, so its completion is compact and we are done. (We do not go
into the process of completion, but rest assured that every countable metric
space has a completion. It is defined as an equivalence class of Cauchy sequences.)
\end{enumerate}
\end{enumerate}

It is a corollary that the set of all Riemannian manifolds with Ricci
curvature uniformly bounded below and diameter uniformly bounded above are
precompact (the closure is compact) in the Gromov-Hausdorff topology.


\end{document}