Skip to main content
added 49 characters in body
Source Link
darij grinberg
  • 33.8k
  • 4
  • 117
  • 253

Here is an elementary proof of the Steinhaus transform (from which said metricity follows as a special case, as noted in Suresh's answer).

Lemma. Let $p,q,r > 0$$p,q > 0$ and $r\geq 0$ such that $p \le q$. Then, $\frac{p}{q} \le \frac{p+r}{q+r}.$

Corollary. Let $d(x,y)$ be a metric. Then, for arbitrary (but fixed) $a$, the map $\delta$ defined by \begin{equation*} \delta(x,y) := \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)}, \end{equation*}\begin{equation*} \delta(x,y) := \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \end{equation*} (and $\delta(a,a)=0$) is a metric.

Proof. Only the triangle inequality for $\delta$ is nontrivial. Let $p=d(x,y)$, $q=d(x,y)+d(x,a)+d(y,a)$, and $r=d(x,z)+d(y,z)-d(x,y)$. Applying the lemma, we obtain \begin{eqnarray*} \delta(x,y) &=& \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \le \frac{2d(x,z)+2d(y,z)}{d(x,a)+d(y,a)+d(x,z)+d(y,z)}\\ &=& \frac{2d(x,z)}{d(x,a)+d(z,a)+d(x,z)+d(y,z)+d(y,a)-d(z,a)} + \frac{2d(y,z)}{d(y,a)+d(z,a)+d(y,z)+d(x,z)+d(x,a)-d(z,a)}\\ &\le& \delta(x,z)+\delta(y,z), \end{eqnarray*} where the last inequality again uses triangle inequality for $d$.

Here is an elementary proof of the Steinhaus transform (from which said metricity follows as a special case, as noted in Suresh's answer).

Lemma. Let $p,q,r > 0$ such that $p \le q$. Then, $\frac{p}{q} \le \frac{p+r}{q+r}.$

Corollary. Let $d(x,y)$ be a metric. Then, for arbitrary (but fixed) $a$, \begin{equation*} \delta(x,y) := \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)}, \end{equation*} is a metric.

Proof. Only the triangle inequality for $\delta$ is nontrivial. Let $p=d(x,y)$, $q=d(x,y)+d(x,a)+d(y,a)$, and $r=d(x,z)+d(y,z)-d(x,y)$. Applying the lemma, we obtain \begin{eqnarray*} \delta(x,y) &=& \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \le \frac{2d(x,z)+2d(y,z)}{d(x,a)+d(y,a)+d(x,z)+d(y,z)}\\ &=& \frac{2d(x,z)}{d(x,a)+d(z,a)+d(x,z)+d(y,z)+d(y,a)-d(z,a)} + \frac{2d(y,z)}{d(y,a)+d(z,a)+d(y,z)+d(x,z)+d(x,a)-d(z,a)}\\ &\le& \delta(x,z)+\delta(y,z), \end{eqnarray*} where the last inequality again uses triangle inequality for $d$.

Here is an elementary proof of the Steinhaus transform (from which said metricity follows as a special case, as noted in Suresh's answer).

Lemma. Let $p,q > 0$ and $r\geq 0$ such that $p \le q$. Then, $\frac{p}{q} \le \frac{p+r}{q+r}.$

Corollary. Let $d(x,y)$ be a metric. Then, for arbitrary (but fixed) $a$, the map $\delta$ defined by \begin{equation*} \delta(x,y) := \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \end{equation*} (and $\delta(a,a)=0$) is a metric.

Proof. Only the triangle inequality for $\delta$ is nontrivial. Let $p=d(x,y)$, $q=d(x,y)+d(x,a)+d(y,a)$, and $r=d(x,z)+d(y,z)-d(x,y)$. Applying the lemma, we obtain \begin{eqnarray*} \delta(x,y) &=& \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \le \frac{2d(x,z)+2d(y,z)}{d(x,a)+d(y,a)+d(x,z)+d(y,z)}\\ &=& \frac{2d(x,z)}{d(x,a)+d(z,a)+d(x,z)+d(y,z)+d(y,a)-d(z,a)} + \frac{2d(y,z)}{d(y,a)+d(z,a)+d(y,z)+d(x,z)+d(x,a)-d(z,a)}\\ &\le& \delta(x,z)+\delta(y,z), \end{eqnarray*} where the last inequality again uses triangle inequality for $d$.

Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

Here is an elementary proof of the Steinhaus transform (from which said metricity follows as a special case, as noted in Suresh's answer).

Lemma. Let $p,q,r > 0$ such that $p \le q$. Then, $\frac{p}{q} \le \frac{p+r}{q+r}.$

Corollary. Let $d(x,y)$ be a metric. Then, for arbitrary (but fixed) $a$, \begin{equation*} \delta(x,y) := \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)}, \end{equation*} is a metric.

Proof. Only the triangle inequality for $\delta$ is nontrivial. Let $p=d(x,y)$, $q=d(x,y)+d(x,a)+d(y,a)$, and $r=d(x,z)+d(y,z)-d(x,y)$. Applying the lemma, we obtain \begin{eqnarray*} \delta(x,y) &=& \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \le \frac{2d(x,z)+2d(y,z)}{d(x,a)+d(y,a)+d(x,z)+d(y,z)}\\ &=& \frac{2d(x,z)}{d(x,a)+d(z,a)+d(x,z)+d(y,z)+d(y,a)-d(z,a)} + \frac{2d(y,z)}{d(y,a)+d(z,a)+d(y,z)+d(x,z)+d(x,a)-d(z,a)}\\ &\le& \delta(x,z)+\delta(y,z), \end{eqnarray*} where the last inequality again uses triangle inequality for $d$.