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.
 A: 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.)
A: 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)$$
A: 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.

