Problem 2

Exercise 6.1 (Metric for Closed Sets)   Suppose $(X,d)$ is a bounded metric space. Let

$$d(x,A) := \inf\{d(x,a) \;\vert\; a\in A\}.$$ (6.1)

And define

$$d_H(A,B) := \inf\{\epsilon>0 \;\vert\; A \subseteq N_\epsilon(B) B \subseteq N_\epsilon(A) \}$$ (6.2)

where

$$N_\epsilon(A) := \{x \in X \;\vert\; d(x,A) < \epsilon\}.$$ (6.3)

Show that $d_H$ is a distance function on the space of all closed subsets in $X$.

Proof. To see that zero distance implies equality, suppose $d_H(A,B)=0$. Select $\epsilon>0$ such that $A \subseteq N_\epsilon(B)$ and $B \subseteq N_\epsilon(A)$. Sending $\epsilon\to 0$, $N_\epsilon(B)\to B$ by closure and similarly $N_\epsilon(A)\to A$. The inclusions then indicate that $A\subseteq B$ and $B\subseteq A$, so that $A=B$.

For symmetry, statements around a logical `and' may be commuted, so that

$$d_H(A,B) = \inf\{\epsilon>0 \;\vert\; A \subseteq N_\epsilon(B) B \subseteq N_\epsilon(A) \}$$ (6.4)

$$= \inf\{\epsilon>0 \;\vert\; B \subseteq N_\epsilon(A) A \subseteq N_\epsilon(B) \} = d_H(B,A)$$ (6.5)

For the triangle inequality, we will prove the estimate

$$d_H(A,C) \leq d_H(A,B) + d_H(B,C).$$ (6.6)

Let $\epsilon>0$ satisfy

$$A \subseteq N_\epsilon(B)$$ (6.7)

$$B \subseteq N_\epsilon(A)$$ (6.8)

and $\epsilon'>0$ satisfy

$$B \subseteq N_{\epsilon'}(C)$$ (6.9)

$$C \subseteq N_{\epsilon'}(B)$$ (6.10)

The $N$ operator acts convexly, so

$$A \subseteq N_\epsilon(B) \subseteq N_\epsilon(N_{\epsilon'}(C)) \subseteq N_{\epsilon+\epsilon'}(C).$$ (6.11)

Therefore, $A\subseteq N_{\epsilon+\epsilon'}(C)$. For the reverse inclusion, note that

$$C \subseteq N_{\epsilon'}(B) \subseteq N_{\epsilon'}(N_{\epsilon}(A)) \subseteq N_{\epsilon'+\epsilon}(A)$$ (6.12)

so that $C\subseteq N_{\epsilon'+\epsilon}(A)$. Therefore,

$$d_H(A,C) \leq \epsilon + \epsilon'.$$ (6.13)

Taking the infimum over the indicated $\epsilon$ and $\epsilon'$ yields

$$d_H(A,C) \leq d_H(A,B) + d_H(B,C).$$ (6.14)

$\qedsymbol$