Metric on the set of non-empty finite subsets (Ex. 2.4 MTH 427/527)

Question

I am taking a course titled "Introduction to Topology I. General Topology" and stuck on the following exercise from the course notes:

Let $S$ be a set and $\mathcal F(S)$ denote the set of all non-empty finite subsets of $S$. For $A, B \in \mathcal F(S)$ define

\begin{equation*} \rho(A, B) = 1 - \frac{|A \cap B|}{|A \cup B|}, \end{equation*} where $|A|$ denotes the number of elements of the set $A$. Show that $\rho$ is a metric on $\mathcal F(S)$.

I can prove the positivity and symmetry properties, but cannot verify the triangle inequality. That is, if $A, B, C \in \mathcal F(S)$, how can we show that $\rho(A, B) + \rho(B, C) \geq \rho(A, C)$?

I tried to substitute the definition given above and manipulate the obtained expressions by rewriting the intersections and unions of sets, but could not get the desired result. Perhaps De Morgan's laws need to be used here, but I have no idea how yet.

Answer 1

After rearrangement we need to prove the following:

$\frac{|A \cap B |}{|A \cup B|} + \frac{|B \cap C|}{|B \cup C|} \leq 1 + \frac{|A \cap C| }{|A \cup C |}$

For notational purposes, define $a = |A \setminus (C\cup B)|, c = |C \setminus (A\cup B)|, d = |(A \cap C) \setminus B|.$ Further define $b_1 = |B \cap (A \setminus C)|, b_2 = |B \cap (C\setminus A)|, b_3 = |B \cap A \cap C|, b_4 = |B \setminus (A\cup C)|$. Then the above inequality can be expressed as

$\frac{b_1 + b_3}{a+d+b_1 + b_2 +b_3+ b_4} + \frac{b_2 + b_3}{c+d+b_1 +b_2+b_3 + b_4} \leq 1 + \frac{d+b_3}{a+c+d+b_1 +b_2 +b_3} $

So we need to prove validity of this algebraic expression. With the last notational definition of $b = b_1 + b_2 +b_3$ we get by inspection

$LHS = \frac{b-b_2}{a+d+b+b_4} + \frac{b-b_1}{c+d+b + b_4} \leq \frac{b-b_2}{a+d+b} + \frac{b-b_1}{c+d+b} = b[\frac{1}{a+d+b} + \frac{1}{c+d+b}] - \frac{b_1}{c+d+b} - \frac{b_2}{a+d+b}$

$RHS = 1 + \frac{d+b-(b_1 + b_2)}{a+c+d+b} =( 1+ \frac{d+b}{a+c+d+b}) - \frac{b_1}{a+c+d+b} - \frac{b_2}{a+c+d+b}$

Immediately we see that the negative parts obey the inequality. Hence check if the following holds:

$b(\frac{1}{a+d+b} + \frac{1}{c+d+b}) \leq 1 + \frac{d+b}{a+c+d+b} $

which is equivalent to

$b(2+ \frac{c}{a+d+b} + \frac{a}{c+d+b}) \leq 2(b+d) + c+a $

and we see that the last inequality is true since $\frac{b}{a+d+b} \leq 1, \frac{b}{c+d+b} \leq 1$. Therefore $LHS \leq RHS$ which is what we wanted to prove.

Answer 2

When skimming through the encyclopaedia of distances one finds that the authors call

\begin{equation} d(A,B) = \frac{|A \vartriangle B|}{|A \cup B|} = \frac{|A \setminus B| + |B \setminus A|}{|A \cup B|} = \frac{|A \cup B| - |A \cap B|}{|A \cup B|} \end{equation}

the "Tanimoto/ Steinhaus distance" which upon googling yields the wikipedia entry on the Jaccard index. Going through the references therein, it turns out in the past there have been articles/letters written, whose sole content was to prove the triangle inequality. One of the earlier such examples is somewhat similar to mine given above (algebraic and tedious) and even state "We have not yet found a simpler or more elegant proof of this theorem based on the theorems of set-algebra". But less than one year later, Geoffrey Gilbert, interpreting this as an ask for a simpler proof, gives a very nice short proof like follows:

For three sets $S_1, S_2, S_3$ he defines $V := S_1 \cap S_2 \cap S_3$, $U:= S_1 \cup S_2 \cup S_3$ and

$T_k := (S_k \setminus (S_i \cup S_j)) \cup ((S_i \cap S_j) \setminus V) \quad k\neq i, i\neq j, k\neq i \text{ and } i,j,k \in \{ 1,2,3\} $

By observation now (it helps to have the Venn diagram drawn out, as in the letter by Gilbert) for any $i,j$:

\begin{equation} \begin{split} \frac{|T_1| + |T_2| + |T_3|}{|U|} &= 1- \frac{|V|}{|U|} \geq 1- \frac{|S_i \cap S_j|}{|S_i \cup S_j|} = d(S_i, S_j) \\ &= \frac{|S_i \vartriangle S_j|}{|S_i \cup S_j|} \geq \frac{|T_i| + |T_j|}{|S_i \cup S_j|} \geq \frac{|T_i| + |T_j|}{|U|} \end{split} \end{equation}

Then the triangle inequality follows immediately

\begin{equation} d(S_1, S_2) + d(S_2, S_3) \geq \frac{|T_1| + 2|T_2| + |T_3|}{|U|} \geq \frac{|T_2|}{|U|} + d(S_1, S_3) \geq d(S_1, S_3). \end{equation}

So apparently the proof boils down to finding a convenient partition of the Venn diagram, i.e. having the idea of defining $T_k$ which partition the disjoint unions of the $S_i$ in a nice way.