[Math] Showing the distance between sets is indeed a metric.

metric-spacesreal-analysis

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.

Best Answer

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.)

Related Question