Problem: Let $\mathcal{F} (S)$ be the set of all finite subsets of a set $S$. Define a function
\[
d: \mathcal{F} (S) \times \mathcal{F} (S) \to \mathbb{R} , \quad d(A,B) = \#\left( \triangle (A,B) \right) ,
\]
where $\triangle(A,B) = (A \setminus B) \cup (B \setminus A)$, the symmetric difference of $A$ and $B$ and $\#$ denotes cardinality. Show that $d$ is a metric on $\mathcal{F} (S)$.
For the triangle's inequality, note that
\begin{align*}
A \setminus B & = \left[ (A\setminus B) \cap C \right] \cup \left[ (A \setminus B)\setminus C \right] \\
& \subseteq (C \setminus B) \cup (A\setminus C).
\end{align*}
Solution: Given that $A,B \in \mathcal{F} (S) $, we need to show that $d$ satisfies the following properties:
$d(A,B) \geq 0$ for $A,B \in \mathcal{F} (S) $;
$d(A,B) = 0 \iff A = B$;
$d(A,B) = d(B,A)$ for $A,B \in \mathcal{F} (S) $;
$d(A,B) \leq d(A,C) + d(C,B)$ for any $A,B,C\in \mathcal{F} (S) $.
We will verify each property one by one.
Since $\#\left( \triangle (A,B) \right) \geq 0$, so $d(A,B) \geq 0$.
If $d(A,B) = 0$, then $\#\left( \triangle (A,B) \right) = 0$ which implies $A\setminus B = \emptyset = B\setminus A$, and thus $A = B$. Conversely, if $A = B$, then $\triangle (A,B) = \emptyset $ and hence $d(A,B) = 0$.
By definition of symmetric difference, we have
\[
d(A,B) = d(B,A).
\]
We will show that $d(A,C) \leq d(A,B) + d(B,C)$ for any $A,B,C\in \mathcal{F} (S) $. At first note that
\begin{align*}
A \setminus B & = \left[ (A\setminus B) \cap C \right] \cup \left[ (A \setminus B)\setminus C \right] \\
& \subseteq (C \setminus B) \cup (A\setminus C).
\end{align*}
Similarly,
\[
B\setminus A \subseteq (C\setminus A) \cup (B\setminus C).
\]
So,
\begin{align*}
\triangle(A,B) & = (A\setminus B) \cup (B\setminus A) \\
& \subseteq \left[ (C\setminus B) \cup (A\setminus C) \right] \cup \left[ (C\setminus A) \cup (B\setminus C) \right] \\
& = (A\setminus C) \cup (C-_A) \cup (C\setminus B) \cup (B\setminus C) \\
& = \triangle(A,C) \cup \triangle(C,B).
\end{align*}
Hence, we have
\begin{align*}
d(A,B) & = \#\left( \triangle(A,B) \right) \\
& \leq \#\left( \triangle(A,C) \cup \triangle(C,B) \right) \\
& \leq \#\left( \triangle(A,C) \right) + \#\left( \triangle(C,B) \right) \\
& \leq d(A,C) + d(C,B).
\end{align*}
![$A \setminus B = \left[ (A\setminus B) \cap C \right] \cup \left[ (A \setminus B)\setminus C \right]$](../../../assets/img/prob-03-04-25_01.svg)