Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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 Nov 14 '12 at 20:56
add comment

2 Answers

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

share|improve this answer
add comment

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.

share|improve this answer
1  
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
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.