Does $d(A,B) := \sum\limits_{n=0}^{\infty} \frac{1}{2^n}\cdot \frac{d_n(A,B)}{1+d_n(A,B)}$ define a metric $d$?

Question

Edit: I rephrased the question.

Suppose we have a set $X$ of objects $A,B,C\cdots$, which we wish to compare pairwise. Furthermore we are given a sequence of distinct finite sets $M_n$, $n\ge0$ a set $M := \cup_{i=0}^{\infty}M_i$ and to each object $A \in X$ a map $\phi_A:M \rightarrow \mathbb{N}$. We call the objects $A,B$ equivalent if $\phi_A(x) = \phi_B(x) $ for all $x \in M$. Then I would like to define for each $n\ge0$ a distance on the equivalence classes of objects: $d_n(A,B) := \max_{x \in M_n} | \phi_A(x) - \phi_B(x) |$. The problem with this definition is that if $0=d_n(A,B)$ then $\phi_A(x) = \phi_B(x)$ for all $x \in M_n$ but not necessarily for all $x \in M$, hence $A $ and $B$ might not be equivalent. Is the function defined below a metric on the equivalence classes of objects? $d(A,B) := \sum_{n=0}^{\infty} \frac{1}{2^n}\cdot \frac{d_n(A,B)}{1+d_n(A,B)}$?

Answer 1

Lemma: Suppose $d: X \times X \to [0, \infty)$ satisfies the triangle inequality: $d(x, z) \leq d(x, y) + d(y, z)$ for all $x, y, z \in X$. Then so does the function $d': X \times X \to [0, \infty)$ defined by $d'(x, y) = \frac{d(x,y)}{1 + d(x, y)}$.

Proof: define $\psi: [0, \infty) \to [0, \infty)$ by $\psi(s) = \frac{s}{1+s}$. It is easily checked that $\psi$ is monotone increasing and $\psi(r + s) \leq \psi(r) + \psi(s)$ for all $r, s \geq 0$. Hence

$$d'(x, z) = \psi(d(x, z)) \leq \psi(d(x, y) + d(y, z)) \leq \psi(d(x, y)) + \psi(d(y, z)) = d'(x, y) + d'(y, z). \Box$$

Of course we also have $d'(x, y) = d'(y, x)$ if $d(x, y) = d(y, x)$, and $d'(x, x) = 0$ if $d(x, x) = 0$. And we note of course that $d'(x, y)$ is bounded above by $1$.

Lemma: If $d_1, d_2, d_3, \ldots: X \times X \to [0, \infty)$ is a family of functions satisfying the triangle inequality and all bounded above by $1$, then $\delta = \sum_{n \geq 1} \frac1{2^n} d_n$ also satisfies the triangle inequality (and is bounded above by $1$).

The proof is obvious. Similarly, if all these functions $d_n$ are symmetric, then so is $\delta$.

So really the only thing left to check is that $d(a, b) = 0$ (where $d$ is defined in the problem statement and corresponds to $\delta$ in the argument above) implies $a \sim b$. But clearly if $d_n(a, b) > 0$ for some $n$, then $d(a, b) > 0$. The contrapositive is that $d(a, b) = 0$ implies $d_n(a, b) = 0$ for all $n$. This means that for each $n$, we have $\phi_a(x) = \phi_b(x)$ for every $x \in M_n$. Hence $\phi_a(x) = \phi_b(x)$ for every $x \in \bigcup_n M_n$. Thus $a \sim b$.