Proving a distance function 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$?
 A: We need to show that the four following properties hold for $d$ to be a metric:


*

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



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



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



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