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

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.

• Course numbers, course titles, and exercise numbers from course notes are note terribly useful as references for the rest of us, as every university and college likely has its own numbering scheme for courses and we don't have access to your course notes. I have removed these references, as they don't help us to understand the problem. If you can expand on where you are, or if you can link to the relevant course notes, that would likely be more helpful. Commented Dec 14, 2023 at 3:05

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.

• I have carefully followed your proof. It is correct, although it looks more tricky than I thought. Thank you for the help! Commented Dec 2, 2023 at 5:19
• your welcome... but I would really like to see a more elegant proof as well that is not as tedious as this one - especially as the proof does not really involve any inherently "topological arguments"... Commented Dec 10, 2023 at 4:16
• Here's a slight simplification. If for ease of reading we rename $b_4$ as $b,$ and define $$s=|A\cup B\cup C| = a+b+c+b_1+b_2+b_3+d,$$ the required inequality can be rewritten as $$\frac{b_1+b_3}{s-c}+\frac{b_2+b_3}{s-a}+\frac{s-d-b_3-b}{s-b}\leq2.$$ A proper fraction increases in value if its numerator and denominator are increased by equal amounts. Therefore $$LHS \leq \frac{(b_1+b_3+c)+(b_2+b_3+a)+(s-d-b_3)}s = 1 + \frac{a+c+b_1+b_2+b_3-d}s \leq 2,$$ as required. Commented Dec 11, 2023 at 19:40

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

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

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{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}$$$$

Then the triangle inequality follows immediately

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

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.

• Very nice! You get the bounty. (a) I have added the Venn diagram to make the answer more accessible. (b) I have fixed a minor mistake in the proof (please check the history and if you agree). (c) I would also suggest to write the equations with displaystyle so that the fractions become bigger (like $\dfrac{a}{b}$) and more readable (I didn't change this because I don't want to force a certain style on your answer). Commented Dec 10, 2023 at 18:39
• thank you ! I have also adjusted the formatting - it certainly does look better. I also left the penultimate inequality in the observation, b/c that is true for sure, but I would argue that looking at the diagram, the $T_i$'s are precisely defined, such that $S_i \triangle S_j = T_i \cup T_j$ no ? Commented Dec 14, 2023 at 2:53