[Math] Metric and the triangle inequality

Question

Let $A,B$ be finite subsets of the natural numbers. If we let $d(A,B)=\sum_{x\in A\mathbin\Delta B} 2^{-x}$, where $A\mathbin\Delta B=(A\cup B)\setminus (A\cap B)$ is the symmetric difference between $A$ and $B$, does $d$ satisfy the triangle inequality? That is, if $A,B,C$ are finite, open subsets of the natural numbers, is $d(A,B)\leq d(A,C)+d(C,B)$? Or do we have to assume that the subsets are disjoint for the triangle inequality to be satisfied?

Answer 1

Martin provided one answer in the comments. Here’s another way to show that $d$ is a metric. For each $A\subseteq\Bbb N$ let $\chi_A$ be the indicator (or characteristic) function of $A$. Then

$$d(A,B)=\sum_{n\in\Bbb N}2^{-n}|\chi_A(n)-\chi_B(n)|\;$$

for any $A,B\subseteq\Bbb N$. (There’s no need to restrict oneself to finite subsets.) Hence

$$\begin{align*} d(A,B)&=\sum_{n\in\Bbb N}2^{-n}|\chi_A(n)-\chi_B(n)|\\ &\le\sum_{n\in\Bbb N}2^{-n}\Big(|\chi_A(n)-\chi_C(n)|+|\chi_C(n)-\chi_B(n)|\Big)\\ &=\sum_{n\in\Bbb N}2^{-n}|\chi_A(n)-\chi_C(n)|+\sum_{n\in\Bbb N}2^{-n}|\chi_C(n)-\chi_B(n)|\\ &=d(A,C)+d(C,B)\;. \end{align*}$$

This is actually just a special case of the proof that if $\{\langle X_n,d_n\rangle:n\in\Bbb N\}$ is a family of metric spaces such that each $d_n$ is bounded by $1$, and $X=\prod_{n\in\Bbb N}X_n$, then the function

$$d:X\times X\to\Bbb R:\langle x,y\rangle\mapsto\sum_{n\in\Bbb N}2^{-n}d_n(x_n,y_n)$$

satisfies the triangle inequality. (It is of course a metric on $X$.) Here each of the spaces $X_n$ is a copy of $\{0,1\}$ with the metric inherited from $\Bbb R$, and the map $A\mapsto\chi_A$ is an isometry.