# Showing the distance between sets is indeed a metric.

Let $(X,d)$ be a metric space, and let $A$ be a non-empty subset of $X$. Define the distance between a point and a set by the function $$d(x,A) = \inf_{z \in A}d(x,z).$$

Prove that for all $x,y \in X$, $$d(x,A) \leq d(x,y) + d(y,A).$$

Note that it is rather trivial to show that

1. $d(x,A) \geq 0$ for all $x \in X$ and $A \subseteq X$ (follows directly from non-negativity of a metric);
2. $d(x,A) = 0$ iff $x$ is in the closure of $A$; and
3. $d(x,A) = d(A,x)$ (by abuse of notation).

By proving the final property of the triangle inequality, we can conclude that the modified distance $d: X \times 2^X \to R$ and its mirrored version $d: 2^X \times X \to R$ forms a sort of pseudo-metric where $d(x,A) = 0$ does not define an equivalence relation.

If we were to modify this function further by first defining $d(x,A)$ to be substituted with $d({x},A)$, we can form a more general pseudo-metric space $(2^X, d:2^X \times 2^X \to R)$ via defining $$d(A,B) = \inf\{d(a,b) : a \in A, b \in B\}.$$ It should be noted that in this particular metric, $A = B$ means that $A$ and $B$ are not separated. That is, if $A'$ denotes the closure of $A$, then $A \subseteq B'$ and $B \subseteq A'$. Then we know that (and can verify 4)

1. $d(A,B) \geq 0$;
2. $d(A,B) > 0$ if and only if $A$ and $B$ are separated (i.e., $A$ is not in the closure of $B$, and $B$ is not in the closure of $A$);
3. $d(A,B) = d(B,A)$; and
4. $d(A,B) \leq d(A,C) + d(C,B)$, for all subsets $C \subseteq X$.

Note that since (2) does not define an equivalence relation on $2^X$, this particular function does not define an actual metric space.

-
I don't think it makes sense to call what you're describing a metric. When you say "$A=B$ means that $A$ and $B$ are not seperated" that doesn't really count, since "not being seperated" is definitely not an equivalence relation. You can say that you're looking for an analogue of the triangle inequality for set distance, but that's about it –  Logan Stokols Nov 14 '12 at 20:56

As pointed out in comments, the infimal distance between sets $d(A,B) = \inf\{d(a,b) : a \in A, b \in B\}$, is not a metric. It fails to satisfy even weaker requirements such as

• pseudo-metric (allowed to be zero between different elements)
• quasi-metric (triangle inequality relaxed to $f(A,C)\le K(d(A,B)+d(B,C))$

It's simply unusable as a metric. In contrast, the Hausdorff distance $d_H$ is a metric on the set of nonempty bounded closed subsets, works better. (If one drops "closed", $d_H$ is still a pseudo-metric. If one drops "bounded", it still satisfies the axioms of pseudo-metric but may be infinite sometimes.)

-

The answer I have found is based on the answer given for this question. Thus, we will generalise this concept to be proven by saying the distance between a point $x$ and a subset $A$ of $X$ forms a bijection with the set distance defined above with $d(x,A) = d(\{x\},A)$. Thus, we will abuse this notation for convenience in the following proof.

Let $a \in A$, $b \in B$, and $c \in C$ be arbitrary points of the subsets $A,B,C$ of $X$. By the inequality $$d(a,b) \leq d(a,c) + d(c,b),$$ we can take the infimum of the left side with respect to $b \in B$ to get $$\inf_{b \in B} d(a,b) = d(a,B) \leq d(a,b) \leq d(a,c) + d(c,b).$$ Since our choice of $b$ is independent of $d(a,B)$, we know that for all $b \in B$, $d(a,B) \leq d(a,c) + d(c,b)$. So, take the infimum of the right side with respect to $b \in B$ to get $$d(a,B) \leq d(a,c) + \inf_{b \in B} d(c,b) = d(a,c) + d(c,B).$$

It is at this point that the original proof is done (but for the special case that $A = \{x\}$ and $C = \{y\}$ where $x,y \in X$), but we will continue to prove the general case. Next, we take the infimum of the left side with respect to $a \in A$ to get $$\inf_{a \in A} d(a,B) = d(A,B) \leq d(A,B) \leq d(a,c) + d(c,B).$$ Once again, by independence of $a$ and $d(A,B)$, we can take the infimum of the right side with respect to $a \in A$ to get $$d(A,B) \leq \inf_{a \in A} d(a,c) + d(c,B) = d(c,A) + d(c,B).$$

Edit: Now that we're left with the inequality $$d(A,B) \leq d(c,A) + d(c,B),$$ we're stuck with the problem of proving we can continue to take infimums while still remaining valid.

-
Sure about this? Try for A the line of equation y = 0, for B the line of equation y = 1, and for C the line of equation x = 0. Then d(A,B) = 1 but d(A,C) = d(C,B) = 0. –  Did Nov 14 '12 at 21:22
The error seems to be in the last two lines. What you would get is that $d(A,B)\le\inf_{c\in C}(d(c,A)+d(c,B))$. However, it is not true that $\inf_{c\in C}(d(c,A)+d(c,B))\le\inf_{c\in C}d(c,A)+\inf_{c\in C}d(c,B)$. –  nonpop Nov 16 '12 at 9:40
Thanks for the input. Is there any way we can modify the pseudo-metric? Or can we only go as far as the $d(A,B) \leq d(A,\{c\}) + d(\{c\},B)$ inequality? –  Matt Nov 16 '12 at 18:43
Note that this is not a pseudo-metric since the triangle inequality doesn't hold. A pseudo-metric should satisfy all axioms of a metric except $d(A,B)=0\implies A=B$. For a metric between the compact subsets of $X$ there is the Hausdorff distance. –  nonpop Nov 18 '12 at 13:14