Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book 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.

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 (Section 2.3).
