Violating the triangle inequality

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.

• 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$. – Nicholas Roberts Sep 23 at 3:20
• 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$). – Erick Wong Sep 23 at 3:45
• @ErickWong I don't understand. Euclidean distances over $(1,10, 50)$ doesn't violate the triangle inequality, does it? – Hatshepsut Sep 23 at 3:48
• @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). – Erick Wong Sep 23 at 4:04
• @ErickWong Ah, yes that was a typo, fixed now. – Hatshepsut Sep 23 at 4:05

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

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

• I always thought a semimetric was one where $d(x,y)=0$ did not imply $x=y$. This way, a seminorm induces a semimetric. – Theoretical Economist Sep 23 at 4:29
• It would make sense, I agree, @TheoreticalEconomist. (Unfortunately, it does not...) – Clement C. Sep 23 at 4:37
• 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. – Theoretical Economist Sep 23 at 8:27

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