3
$\begingroup$

Let $A$ be a set and $F$ the set of finite subsets of $A$.
Define $d:F\times F\rightarrow\mathbb{R}$ with $d(X,Y)=\#(X\cup Y)\backslash(X\cap Y)$ with $\#$ the cardinality.

How do I prove that this is a metric?

The main thing I need to prove is the triangle inequality, or

$$\#(X\cup Z)\backslash(X\cap Z)\leq\#(X\cup Y)\backslash(X\cap Y)+\#(Y\cup Z)\backslash(Y\cap Z)$$

Graphically this can be made quite clear, but how can I show this formally?

$\endgroup$
1
  • $\begingroup$ Have you tried writing $d(X,Y)$ as $|X| + |Y| -2|X\cap Y|$? maybe that helps. $\endgroup$
    – Iacobus
    Feb 4, 2017 at 12:45

3 Answers 3

5
$\begingroup$

The operation that sends sets $A$ and $B$ to $(A \cup B) \setminus (A \cap B)$ is called the symmetric difference $A \triangle B$. So your metric is defined as $d(A,B) = |A \triangle B|$,where $|.|$ denotes cardinality.

Symmetric difference has some interesting properties, one of which is $(A \triangle B) \triangle (B \triangle C) = A \triangle C$, which implies that

$$ A \triangle C \subseteq (A \triangle B) \cup (B \triangle C)\text{ so }d(A, C) \le d(A,B) + d(B,C)$$

as a union has at most the sum of the elements of its components. So as an exercise you could try and prove the inclusion above yourself. There are probably answers doing exactly that on this site...

$\endgroup$
3
$\begingroup$

Assume you have an element $a\in (X\cup Z)\setminus(X\cap Z)$ then you have two cases: $a\in X$ or (exclusive) $a\in Z$. Assume that $a\in X$ (the other case is similar). Then for any $Y$ either

$a\in Y$ and then $a\in (Y\cup Z)\setminus(Y\cap Z)$ and you are done.

$a\not\in Y$ and then $a\in (X\cup Y)\setminus(X\cap Y)$ and you are done.

I think this should be enough to conclude

$\endgroup$
2
  • $\begingroup$ So since every $a\in(X\cup Z)\backslash(X\cap Z)$ is in one of the other two, it follows that the cardinality of $(X\cup Z)\backslash(X\cap Z)$ is less or equal than the other two combined? $\endgroup$
    – user413078
    Feb 4, 2017 at 12:53
  • $\begingroup$ Yes it is like this. $\endgroup$
    – Maczinga
    Feb 4, 2017 at 13:07
1
$\begingroup$

The existing solutions are quite elegant, but a more naïve approach is to draw a Venn diagram for $X,Y$ and $Z$ and think about which regions $d(X,Y)+d(Y,Z)-d(X,Z)$ counts elements for. Labelling the regions and doing some algebra, we find that most of the regions cancel out and we are left with $$d(X,Y)+d(Y,Z)-d(X,Z)=2\#((X\cap Z)\setminus(X\cap Y\cap Z))+2\#((X\cap Y)\cup (Y\cap Z))\geq 0.$$

$\endgroup$

You must log in to answer this question.