Problem: Let $X$ be a nonempty set and $\mathcal{F} (X)$ denote the set of all finite subsets of $X$. For any $A,B \in \mathcal{F} (X)$, let $\Delta (A,B)$ denote the symmetric difference of $A$ and $B$, that is
\[
\Delta (A, B) = (A \setminus B) \cup (B \setminus A).
\]
We define a map
\[
d : \mathcal{F}(X) \times \mathcal{F} (X),\ \ (A,B) \mapsto \#(\Delta (A,B)),
\]
where $\#(A)$ is the number of elements of the set $A$. Prove that $d$ is a metric on $\mathcal{F} (X)$.
Solution: We will verify all the properties for a metric.
-
Note that
\begin{align*}
d(A, B) = 0 & \iff \# (\Delta (A, B)) = 0\\
& \iff \# (( A\setminus B) \cup (B \setminus A)) = 0 \\
& \iff \# (A \setminus B) = 0 \text{ and } \# (B \setminus A) = 0 \\
& \iff A = B.
\end{align*}
-
Now we will check for symmetric properties. For any $A, B \in \mathcal{F} (X)$,
\begin{align*}
d(A, B) & = \# (\Delta (A, B)) \\
& = \# ((A \setminus B) \cup (B \setminus A)) \\
& = \# ((B \setminus A) \cup (A \setminus B)) \\
& = d(B, A).
\end{align*}
-
Finally, we will prove the triangle's inequality. Let $A, B, C \in \mathcal{F} (X)$. Then
\begin{align*}
A \setminus B & = ((A\setminus B) \cap C) \cup ((A\setminus B)\setminus C) \\
& \subseteq (C\setminus B) \cup (A\setminus C).
\end{align*}
Similarly,
\[
B\setminus A \subseteq (C\setminus A) \cup (B\setminus C).
\]
Thus, we have
\begin{align*}
\Delta (A,B) & = (A\setminus B) \cup (B\setminus A) \\
& \subseteq (C\setminus B) \cup (A\setminus C) \cup (C\setminus A) \cup (B\setminus C)\\
& = (A\setminus C) \cup (C\setminus A) \cup (C\setminus B) \cup (B\setminus C) \\
& = \Delta (A, C) \cup \Delta (C, B).
\end{align*}
Therefore,
\begin{align*}
d(A,B) & = \# (\Delta (A,B)) \\
& \leq \#(\Delta (A,B) \cup \Delta (C, B)) \\
& \leq \# (\Delta (A,C)) + \# (\Delta (C,B)) \\
& = d(A,C) + d(C,B).
\end{align*}
Thus, $d$ is a metric on $\mathcal{F} (X)$.