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.

From Wikipedia:

If $M$ is a metric space with metric $d$, and $\sim$ is an equivalence relation on $M$, then we can endow the quotient set $M/{\sim}$ with the following (pseudo)metric. Given two equivalence classes $[x]$ and $[y]$, we define $$ d'([x],[y]) = \inf\{d(p_1,q_1)+d(p_2,q_2)+\dotsb+d(p_{n},q_{n})\} $$ where the infimum is taken over all finite sequences $(p_1, p_2, \dots, p_n)$ and $(q_1, q_2, \dots, q_n)$ with $[p_1]=[x], [q_n]=[y], [q_i]=[p_{i+1}], i=1,2,\dots, n-1$. In general this will only define a pseudometric, i.e. $d'([x],[y])=0$ does not necessarily imply that $[x]=[y]$. However for nice equivalence relations (e.g., those given by gluing together polyhedra along faces), it is a metric.

  1. I wonder why the quotient metric is defined that way?
  2. Instead, how about using the distance between two subsets of the metric space $$ d'([x],[y]) = \inf\{d(p,q)\} $$ the infimum is taken over all $(p,q)$ such that $[p]=[x], [q]=[y]$?

Thanks and regards!

share|improve this question
    
In item $2$, did you mean $p$ and $q$? –  joriki Mar 16 '12 at 18:49
    
Whoops! Thanks! –  Tim Mar 16 '12 at 18:51

3 Answers 3

up vote 10 down vote accepted

This is to ensure the triangle inequality. In your proposal, it can happen that $[p]$ and $[q]$ have nearby representatives and $[q]$ and $[r]$ have nearby representatives, but the two representatives of $[q]$ involved are different, so this doesn't guarantee that $[p]$ and $[r]$ have nearby representatives, so the triangle inequality may be violated.

With the Wikipedia definition, on the other hand, it's straightforward to verify the triangle inequality, since any chain of points from $[p]$ to $[q]$ and any chain of points from $[q]$ to $[r]$ can be concatenated to form a chain of points from $[p]$ to $[r]$, so the triangle inequality follows from the individual triangle inequalities. In particular, in the above situation, we can "hop" from one representative of $[q]$ to the other without extra cost.

share|improve this answer
    
Do you really need the triangle inequality of $d$ to prove this? If I'm not mistaken $d'$ should be a pseudo metric even without this assumption. –  Jim Mar 29 at 12:42

Hopefully an example will show the problem:

Consider $X = \{ ±1, ±2, 1.1, 2.1 \}$ with $d(x,y)=|x-y|$ and $\sim\, = \{\{1,-1\},\{2,-2\},\{1.1,2.1\}\}$.

Then $$d([1],[2]) \leq d([1],[1.1]) + d([1.1],[2]),$$ but if we use any sort of infimum definition, then $$d([1],[1.1]) \leq |1-1.1| = 0.1$$ and $$d([1.1],[2])=d([2.1],[2]) \leq |2.1-2|=0.1,$$ so $$d([1],[2]) \leq 0.2 < |1-2|= 1$$

Using a supremum would have the odd effect that $d([1],[1])=d([1],[-1]) \geq 2$, so infimum seems natural, even if it is a little broken (only a pseudo-metric).

(Joriki's answer indicates the same example.)

share|improve this answer

Clearly, using the definition from Wikipedia, you always get a smaller or equal distance than under your proposal. If the definitions disagree and your approach is employed, the triangle inequality is violated. The definition you find in Wikipedia guarantees that the triangle inequality is valid. So I will give an example in which the triangle inequality is violated under your propsal.

Let $A=\{(0,x):x\in[0,1]\}$, $C=\{(1,x):x\in[0,1]\}$, and $B=\{(x,x):x\in(0,1)\}$. Let $X=A\cup B\cup C$ and endow it with the Euclidean metric. Partition $X$ into $A$, $B$, and $C$. One can make a path from $A$ to $C$ have lenght arbitrarily close to $0$, but $d(A,C)=1$ under your proposal.

share|improve this answer

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.