Wikipedia defines the [Jaccard distance](https://en.wikipedia.org/wiki/Jaccard_index) between sets *A* and *B* as $$J\_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a [book](https://books.google.com/books?id=DGjbibiS-S0C&pg=PA38&dq=jaccard+similarity&as_brr=3&ei=iNGbS96kNYfIywTVjZ2cCg&cd=1#v=onepage&q=jaccard%20similarity&f=false) claiming that this is a metric. However, I couldn't find any explanation of why $J\_\delta$ obeys the triangle inequality. The naive approach of writing the inequality with seven variables (e.g., $x\_{001}$ thru $x\_{111}$, where $x\_{101}$ is the number of elements in $(A\cap C) \backslash B$) and trying to reduce it seems hopeless for pen and paper. In fact it also seems hopeless for Mathematica, which is trying to find a counterexample for 20 minutes and is still running. (It's supposed to say if there isn't any.)


Is there a simple argument showing that this is a distance? Somehow, it feels like the problem shouldn't be difficult and I'm missing something.



Is the Jaccard distance a distance?
The trick is to use a transform called the Steinhaus Transform. Given a metric $(X, d)$ and a fixed point $a \in X$, you can define a new distance $D'$ as
$$D'(x,y) = \frac{2D(x,y)}{D(x,a) + D(y,a) + D(x,y)}.$$
It's known that this transformation produces a metric from a metric. Now if you take as the base metric $D$ the symmetric difference between two sets and empty set as $a$, what you end up with is the Jaccard distance (which actually is known by many other names as well).


For more information and references, check out Ken Clarkson's survey [Nearest-neighbor searching and metric space dimensions](https://web.archive.org/web/20161027161008/http://kenclarkson.org/nn_survey/p.pdf) (Section 2.3).


