Metric on finite sets of natural numbers

84 Views Asked by At

I was reading this question and I had a go at proving that $d^J$ is a metric. That is, if $X,Y\subset\mathbb{N}$ are finite, define $$d^J(X,Y)=1-\frac{|X\cap Y|}{|X|+|Y|-|X\cap Y|}=1-\frac{|X\cap Y|}{|X\cup Y|}.$$ I got stuck proving the triangle inequality.

If $X,Y,Z\subset\mathbb{N}$ are finite, we must show $$d(X,Y)+d(Y,Z)=2-\frac{|X\cap Y|}{|X\cup Y|}-\frac{|Y\cap Z|}{|Y\cup Z|}\geq 1-\frac{|X\cap Z|}{|X\cup Z}=d(X,Z),$$ or $$1+\frac{|X\cap Z|}{|X\cup Z|}\geq \frac{|X\cap Y||Y\cup Z|+|X\cup Y||Y\cap Z|}{|X\cup Y||Y\cup Z|}$$ or $$|X\cup Y||Y\cup Z||X\cup Z|+|X\cap Z||X\cup Y||Y\cup Z|\geq |X\cap Y||Y\cup Z||X\cup Z|+|X\cup Y||Y\cap Z||X\cup Z|,$$ which doesn't seem easy to prove.

I then tried writing $|X\cup Y|=|X|+|Y|-|X\cap Y|$ etc., but this produces something even more complicated.

How can I prove the triangle inequality for this metric?

1

There are 1 best solutions below

0
On BEST ANSWER

Claim $1$: $\delta(X,Y):=|X\cup Y|-|X\cap Y|$ is a metric.

Claim $2$: For any metric $\delta$, $d(X,Y):=\frac{2\delta(X,Y)}{\delta(X,A)+\delta(Y,A)+\delta(X,Y)}$ is a metric.

Claim $3$: With $\delta$ as in Claim $1$ and $A=\varnothing$, we have $\frac{2\delta(X,Y)}{\delta(X,A)+\delta(Y,A)+\delta(X,Y)}=d^J(X,Y)$.

Therefore, by Claims $1,2$ and $3$, $d^J$ is a metric.


Proof of Claim $1$:

We have $\delta(X,X)=|X|-|X|=0$ and $|X\cup Y|\geq|X\cap Y|$ for all $X,Y$ so $\delta\geq 0$. Moreover, $\delta$ is symmetric and satisfies the triangle inequality since $$\delta(X,Y)+\delta(Y,Z)-\delta(X,Z)=2(|(X\cap Z)\setminus(X\cap Y\cap Z)|+|Y\setminus((X\cap Y)\cup(Y\cap Z))|)\geq 0.$$ The equality here can be checked by drawing a Venn diagram and labelling the regions.


Proof of Claim $2$:

We have $d(X,Y)=0$ iff $\delta(X,Y)=0$ iff $X=Y$, and $d$ is symmetric and it is clear $d\geq 0$.

For the triangle inequality, note that if $0<a\leq b$ and $c>0$ then $\frac{a}{b}\leq\frac{a+c}{b+c}\leq\frac{a+2c}{b+c}$. Then let $a=2\delta(X,Y), b=\delta(X,A)+\delta(Y,A)+\delta(X,Y)$ and $c=\delta(X,Z)+\delta(Y,Z)-\delta(X,Y)\geq 0$ by the triangle inequality for $\delta$. Hence $$d(X,Y)\leq \frac{2\delta(X,Z)+2\delta(Y,Z)}{\delta(X,A)+\delta(Y,A)+\delta(X,Z)+\delta(Y,Z)}.$$ Now adding and subtracting $\delta(Z,A)$ in the denominator, and splitting up the fraction, gives $$d(X,Y)\leq\frac{2\delta(X,Z)}{\delta(X,A)+\delta(Z,A)+\delta(X,Z)-\delta(Z,A)+\delta(Y,A)+\delta(Y,Z)}+\frac{2\delta(Y,Z)}{\delta(Y,A)+\delta(Z,A)+\delta(Y,Z)-\delta(Z,A)+\delta(X,A)+\delta(X,Z)}$$ Now we apply the triangle inequality for $\delta$ to get that $\delta(Y,Z)+\delta(Y,A)-\delta(Z,A)\geq 0$ (and likewise for $X$ in place of $Y$), so the two fractions are less than or equal to $d(X,Z)$ and $d(Y,Z)$ respectively, which proves Claim $2$.


Proof of Claim $3$:

$$\frac{2\delta(X,Y)}{\delta(X,A)+\delta(Y,A)+\delta(X,Y)}=\frac{|X\cup Y|-|X\cap Y|}{\frac{1}{2}\left(|X|+|Y|+|X\cup Y|-|X\cap Y|\right)}=\frac{|X\cup Y|-|X\cap Y|}{\frac{1}{2}\left(|X\cup Y|+|X\cap Y|+|X\cup Y|-|X\cap Y|\right)}=\frac{|X\cup Y|-|X\cap Y|}{|X\cup Y|}=d^J(X,Y).$$