General Topology – Metric on Non-Empty Finite Subsets

elementary-set-theorygeneral-topologymetric-spaces

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.

Best Answer

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.

Related Question