# Distance between sets (a triangle-type inequality)

1. Nov 26, 2011

### Identity

I've been reading a book called Superfractals, and I'm having trouble with a particular proof:

Definitions:

The distance from a point $x \in X$ to a set $B \in \mathbb{H}(X)$ (where $\mathbb{H}(X)$ is the space of nonempty compact subsets of $X$ is:
$$D_B(x):=\mbox{min}\lbrace d(x,b):b \in B\rbrace$$
The distance from $A \in \mathbb{H}(X)$ to $B \in \mathbb{H}(X)$ is:
$$D_B(A):=\mbox{max}\lbrace D_B(a):a \in A\rbrace$$
for all $A,B \in \mathbb{H}(X)$.
The proof is to show that $D_B(A) \leq D_B(C)+D_C(A)$. The proof goes:
$$\begin{array}{rcl}D_B(a) &=&\mbox{min}_{b \in B}d(a,b) \\ &\leq& \mbox{min}_{b \in B}(d(a,c)+d(c,b))\\ &=&d(a,c)+\mbox{min}_{b \in B}d(c,b)\\ \end{array}$$
Then
$$D_B(a) \leq \mbox{min}_{c \in C}d(a,c)+\mbox{max}_{c \in C}\mbox{min}_{b \in B}d(c,b)$$

How do we reach this last step?

2. Nov 27, 2011

### micromass

First of all, we notice that

$$\min_{b\in B}~d(c,b) \leq \max_{x\in C}~\min_{b\in B}~d(c,b)$$

So

$$D_B(a)\leq d(a,c)+\mbox{min}_{b \in B}d(c,b)\leq d(a,c)+\mbox{max}_{c \in C}\mbox{min}_{b \in B}d(c,b)$$

For notational issues, let $S=\mbox{max}_{c \in C}\mbox{min}_{b \in B}d(c,b)$ this is just a number.

So we have proven that

$$D_B(a)\leq d(a,c)+S$$

But this holds for ALL c. So it must also hold for any particular c. So it must also hold for the c that minimizes d(a,c). So

$$D_B(a)\leq \min_{c\in C}~d(a,c)+S$$

3. Nov 29, 2011

### Identity

Thnks micromass :)