1
$\begingroup$

I am looking for a set $X$ and distance metric $d(x,y)$ which has

  • $d(x,x)=0$ for all $x$
  • (Positive) $d(x,y)>0$ for all $x \ne y$
  • (Symmetric) $d(x,y)=d(y,x)$ for all $x,y$

But not

  • (Triangle inequality) For all $(x,y,z) \in X, d(x,z) \leq d(x,y) + d(y,z)$.

I tried some small discrete sets with simple distance rules but no luck so far.

$\endgroup$
  • 3
    $\begingroup$ This may be overkill, but I do believe the $L^p$ spaces for $0 < p < 1$ do not have the triangle inequality. Here, the metric is induced by the usual norm on this space. That is, $d(f, g) = ||f - g||_p$. $\endgroup$ – Nicholas Roberts Sep 23 at 3:20
  • $\begingroup$ If you really mean strict inequality then this can be seen from just regular Euclidean distance by taking three points in a line (with $y$ being between $x$ and $z$). $\endgroup$ – Erick Wong Sep 23 at 3:45
  • $\begingroup$ @ErickWong I don't understand. Euclidean distances over $(1,10, 50)$ doesn't violate the triangle inequality, does it? $\endgroup$ – Hatshepsut Sep 23 at 3:48
  • $\begingroup$ @Hatshepsut It depends on whether you made a typo. The triangle inequality is indeed true for those distances, but what you wrote down is not the triangle inequality ($<$ vs $\le$). That can also be fairly called a “triangle” inequality since it can detect whether three points form a triangle (rather than lying in a line). $\endgroup$ – Erick Wong Sep 23 at 4:04
  • $\begingroup$ @ErickWong Ah, yes that was a typo, fixed now. $\endgroup$ – Hatshepsut Sep 23 at 4:05
3
$\begingroup$

I think you may take $X =\{a,b,c\}$ with

$$d(a,b)=3, d(b,c)=1, d(c,a)=1$$

and complete the remaining distances by $d(x,x)=0$ and $d(x,y)=d(y,x)$. This satisfies your properties, but

$$d(a,b) > d(a,c) + d(c,b)$$

$\endgroup$
6
$\begingroup$

By definition, a metric will satisfy the triangle inequality. What you are looking for is a semimetric.

It is easy to see that, for $p\in(0,1)$ the function $d\colon\mathbb{R}^n\times\mathbb{R}^n \to [0,\infty)$ defined as $$ d(x,y) = \lVert x-y\rVert_p = \left( \sum_{i=1}^n |x_i-y_i|^p \right)^{1/p} $$ is indeed a semimetric. (The triangle inequality is only satisfied for $p\geq 1$, for which $\lVert \cdot \rVert_p$ is a bona fide norm.)

$\endgroup$
  • $\begingroup$ I always thought a semimetric was one where $d(x,y)=0$ did not imply $x=y$. This way, a seminorm induces a semimetric. $\endgroup$ – Theoretical Economist Sep 23 at 4:29
  • 2
    $\begingroup$ It would make sense, I agree, @TheoreticalEconomist. (Unfortunately, it does not...) $\endgroup$ – Clement C. Sep 23 at 4:37
  • $\begingroup$ Now I know why I thought this: I actually learned it from a textbook. Which is a little odd, since the aforementioned book was otherwise pretty forthcoming when their notation / terminology is non-standard. TIL. $\endgroup$ – Theoretical Economist Sep 23 at 8:27
0
$\begingroup$

Let $\ X\ :=\ \mathbb R\ $ be the set of all reals. Define:

$$ \forall_{k\ n\in\mathbb Z}\quad \delta(k\ n)\ :=\ (k-n)^2 $$

Your axioms are satisfied for $\ \delta,\ $ while

$$ \delta(k\ m)+\delta(m\ n)\ <\ \delta(k\ n) $$

whenever $\ k<m<n\ $ (for $\ k\ m\ n\in\mathbb R$).

REMARK   Draw the three square of the above inequality ($(k-n)^2,\ $ etc.) and you'll clearly see that indeed the inequality holds.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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