Proving a distance function

Question

Let $k$ be a natural number and $N_k$ be the set of all subsets with $k$ elements. For $X,Y\in N_k$ let $d(X,Y) = |(X\setminus Y) \cup (Y\setminus X)|$ (the number of elements in the union). How do I prove that $d: N_k \times N_k \rightarrow \mathbb{R}$ is a distance function on $N_k$?

Answer 1

We need to show that the four following properties hold for $d$ to be a metric:

1. If $X,Y \in N_k$ then $d(X,Y) \geq 0$:

This follows from the fact that the absolute value $|(X \setminus Y) \cup (Y \setminus X) | \geq 0$

---

2. $d(X,Y) = 0$ if and only if $X=Y$:

($\Rightarrow$) If $X=Y$ then $d(X,Y) = d(X,X) = | X \setminus X \cup X \setminus X| = | \, \emptyset \, | = 0$.

($\Leftarrow$) If $d(X,Y) = 0$ then $$| (X \setminus Y) \cup (Y \setminus X) | = 0 \Rightarrow |X \setminus Y| = | Y \setminus X| = 0 \, \, \,\text{ (why is this true??)}$$ So there does not exist $x \in X$ such that $x \notin Y$ or $y \in Y$ such that $ y \notin X$. So $X = Y$

---

3. if $X, Y \in N_k$ then $d(X,Y)=d(Y,X)$ :

Let $X,Y \in N_k$. Then $$d(X,Y) = |(X \setminus Y) \cup (Y \setminus X)| = | (Y \setminus X) \cup (X \setminus Y)| = d(Y,X)$$

---

4. if $X,Y,Z \in N_k$ then $d(X,Y) \leq d(X,Z) + d(Z,Y)$:

Here, it is (extremely) helpful to draw a venn diagram and do some colouring in to convince yourself!

We have $$X \setminus Y = ((Z \cap X) \setminus Y) \cup (X \setminus (Z \cup Y)) \subseteq (Z \setminus Y) \cup (X \setminus Z) $$ and $$ Y \setminus X = ((Z \cap Y) \setminus X) \cup (Y \setminus (Z \cup X)) \subseteq (Z \setminus X) \cup (Y \setminus Z) $$ So $( X \setminus Y) \cup (Y \setminus X) \subseteq (X \setminus Z) \cup (Z \setminus X) \cup (Z \setminus Y) \cup (Y \setminus Z) $ which gives us $ |(X \setminus Y) \cup (Y \setminus X)| \leq | (X\setminus Z) \cup (Z \setminus X) \cup (Z \setminus Y) \cup (Y \setminus Z)|$

Then \begin{align} d(X,Z) + d(Z,Y) & = |(X \setminus Z) \cup (Z \setminus X)| + |(Z \setminus Y) \cup (Y \setminus Z)|\\ & \geq |(X \setminus Z) \cup (Z \setminus X) \cup (Z \setminus Y) \cup (Y \setminus Z)|\\ & \geq |(X \setminus Y) \cup (Y \setminus X)|\\ & = d(X,Y) \end{align}