30/04/2014

## Proof: the Hausdorff metric is finite under the boundedness assumption

Let $(E,\rho)$ be a metric space and $\mathcal{F}$ the family of non-empty, closed and bounded subsets of $E$. For any $X,Y\in\mathcal{F}$, define

$d(X, Y)=\max\{\sup\{\rho(x,Y):x\in X\},\sup\{\rho(y,X):y\in Y\}\},$

where $\rho(x,Y)$ denotes the distance of point $x\in X$ from set $Y$ and $\rho(y,X)$ is the distance of point $y\in Y$ from set $X$, that is

$\rho(x,Y)=\inf\{\rho(x,y):y\in Y\},~\rho(y,X)=\inf\{\rho(y,x):x\in X\}.$

It can be shown that $(\mathcal{F},d)$ is a metric space, and the metric $d$ is known as the Hausdorff metric. In order to prove that $d:\mathcal{F}\times\mathcal{F}\rightarrow \mathbb{R}$ is a metric, the following three properties of (the definition of) metric need to be shown:

1. $d(X,Y)=0\Leftrightarrow X=Y,$
2. $d(X,Y)=d(Y,X),$
3. $d(X,Y)\le d(X,Z)+d(Z,Y).$

Proofs of the validity of these three properties for the Hausdorff metric are readily available in several books of topology. However, the implicit assumption of finitness of the metric tends to receive less attention. To be precise, due to the general definition of a metric, the range of the Hausdorff metric must be the real line as opposed to the extended real line.

After struggling a bit with the proof of the finitness of the Hausdorff metric, I tried the google shortcut. It turned out that this blurred my vision even further, mostly encountering a comparison of assuming a compact metric space $(E,\rho)$ versus the assumption of a family of closed and bounded subsets (the latter is preferable by the way, since it poses a weaker assumption). After failing to find the solution the easy way via google, I resorted to my stubbornness and finally succeeded in proving that if the subsets in $\mathcal{F}$ are non-empty and bounded, then the Hausdorff metric is finite and therefore well-defined.

Although the proof is not so difficult (that’s easy to say after completing the proof and once the creative frustration is over), I decided to share it so that the next googl-er would find the e-shortcut I was looking for myself in the first place.

Proof.

Let $x\in X$ and $y\in Y$. Then, since

$\rho(X,Y)=\inf\{\rho(x,y):(x,y)\in X\times Y\}$,

it follows that for every $n\in\mathbb{N}$ there exist $z\in X$ and $w\in Y$ such that

$\rho(z,w)\le\rho(X,Y)+\frac{1}{n}.\ \ \ \ (1)$

Indeed, assume that (1) is not true. Then there exists $n_0\in\mathbb{N}$ such that for all $z\in X$ and $w\in Y$ it holds that

$\rho(z,w)>\rho(X,Y)+\frac{1}{n_0},$

whence

$\inf\{\rho(z,w):(z,w)\in X\times Y\}=\rho(X,Y)\ge \rho(X,Y)+\frac{1}{n_0}\Rightarrow\frac{1}{n_0}\le 0,$

so a contradiction has been reached, which means that (1) actually holds.

According to the triangle inequality of metric $\rho$,

$\rho(x,y)\le \rho(x,z)+\rho(z,w)+\rho(w,y).\ \ \ \ (2)$

It thus follows from (1) and (2) that for every $n\in\mathbb{N}$

$\rho(x,y)\le \delta(X)+\rho(X,Y)+\delta(Y)+\frac{1}{n}.\ \ \ \ (3)$

Note that (3) holds because the sets $X,~Y$ are bounded, which means that their respective diameters $\delta(X),~\delta(Y)$ satisfy

$\rho(x,z)\le\delta(X)=\sup\{\rho(q,q):q\in X\}<\infty,$

$\rho(w,y)\le\delta(Y)=\sup\{\rho(q,q):q\in Y\}<\infty.$

Since (3) holds for all $n\in\mathbb{N}$, it follows that

$\rho(x,y)\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (4)$

Indeed, assume that (4) is not true. Then it holds that

$\delta(X)+\rho(X,Y)+\delta(Y)<\rho(x,y),$

and, in combination with (3), it is deduced that for any $n\in\mathbb{N}$

$0<\rho(x,y)-(\delta(X)+\rho(X,Y)+\delta(Y))\le\frac{1}{n},$

which is a contradiction because it follows from the Archimedean property that there exists $n_0\in\mathbb{N}$ such that

$\frac{1}{n_0}<\rho(x,y)-(\delta(X)+\rho(X,Y)+\delta(Y)),$

hence (4) is true.

Recalling that

$\rho(x,Y)=\inf\{\rho(x,y):y\in Y\}\le\rho(x,y),$

it follows from (4) that for any $x\in X$

$\rho(x,Y)\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (5)$

Since (5) holds for any $x\in X$, it follows that the set $\{\rho(x,Y):y\in Y\}$ has an upper bound, therefore according to the completeness axiom for real numbers, $\{\rho(x,Y):y\in Y\}$ has a supremum. In particular,

$\sup\{\rho(x,Y):x\in X\}\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (6)$

By means of symmetry of (6), this also means that

$\sup\{\rho(y,X):y\in Y\}\le \delta(X)+\rho(X,Y)+\delta(Y),\ \ \ \ (7)$

which completes the proof.