Prove: $d(x,y)=\frac{1}{\min\{i\in \mathbb{N}:x_i\neq y_i\}}$ is a metric

Question

Let $K$ be a nonempty set and $X$ a collection of sequences which their elements are from $k$

Let $d:X\times X\to [0,\infty)$ be defined as follow:

$$ d(x,y)= \begin{cases} 0,& x=y\\ \dfrac{1}{\min\{i\in \mathbb{N}:x_i\neq y_i\}},& x\neq y\\ \end{cases} $$

Prove this is a metric.

It is easy to see that

a. it is nonnegative and equal to zero iff $x=y$

b. it is symmetric

for the triangle inequality, if we have $x,y,z$ and there are two which are equal, WLOG all will be equal.

how can I proceed in the case where $x\neq y \neq z$, if we take: $x=(0,1,x,...,y,x)$ , $y=(2,...,2,y,2)$, $z=(3,1,z,...,z,y,z)$

It seems that $d(x,z)\geq d(x,y)+d(y,z)$.

Another try:

Let assume that $d(x,z)=\frac{1}{i}$ then we have $4$ options:

$d(x,y)\leq \frac{1}{i}$ or $d(x,y)\geq \frac{1}{i}$ and $d(y,z)\leq \frac{1}{i}$ or $d(y,z)\geq \frac{1}{i}$

for all options the triangle inequality holds, as there is an element which is bigger then $\frac{1}{i}$ and for both $d(x,y)\leq \frac{1}{i}$ and $d(y,z)\leq \frac{1}{i}$ then $d(x,z)=\frac{1}{i}\leq d(x,y)+d(y,z)\leq \frac{2}{i}$

Answer 1

Hint for triangle inequality: Show that $$ d(x,z)\leq \max\{d(x,y), d(y,z)\} $$ and then prove the triangle inequality from there.

Answer 2

if $x=z$, then $d(x,z)=0$, since $d$ is nonnegative, we have

$$d(x,z) \le d(x,y) + d(y,z).$$

If $x \ne z$, suppose $d(x,z)=\frac1i$.

• Suppose $d(x,y)= \frac1j$ where $j\le i$, then we have $\frac1i \le \frac1j$, that is $$d(x,z)\le d(x,y) \le d(x,y) + d(y,z).$$

• Suppose $d(x,y)=\frac1j$ where $j>i$ , in particular the first $i$ positions of $y$ is identical to the first $i$ positions of $x$. Hence the $i$-th position of $y$ is different from the $i$-th position of $z$. Hence $d(y,z)=\frac1i$. Hence $$d(x,z) \le d(y,z)\le d(x,y)+d(y,z).$$

• Suppose $d(x,y)=0$, then $x=y$, hence $d(y,z)=d(x,z)=\frac1i$ and we get the same conclusion.

Answer 3

Let $x,y,z \in X$. If $x_i \ne z_i$, then necessarily $x_i \ne y_i$ or $y_i \ne z_i$ because otherwise we would have $x_i = y_i = z_i$.

Therefore, if $i = \min\{j : x_j \ne z_j\}$, we have $\min\{j : x_j \ne y_j\} \le i$ or $\min\{j : y_j \ne z_j\}\le i$.

Hence $d(x,y) \ge \frac1i$ or $d(y,z) \ge \frac1i$. In either case we have $$d(x,y) + d(y,z) \ge \frac1i +0 = d(x,y)$$

Answer 4

To show the triangle inequality for this metric, fix a sequence $\{y_n\}$. Now, define two sequences $\{x_n\}$ and $\{z_n\}$ where

---

only the first $i$ terms of $\{x_n\}$ and $\{y_n\}$ are equal.

only the first $j$ terms of $\{z_n\}$ and $\{y_n\}$ are equal.

Without lose of generality and by respecting the symmetry assume that $i<j$. Therefore at least $i$ terms and at most $j$ terms of all three sequences are equal. More over: $$ d(x,y)={1\over i} \\ d(z,y)={1\over j} $$ and $${1\over j}\le d(x,z)\le{1\over i}$$therefore$$d(x,z)\le{1\over i}\le{1\over i}+{1\over j}=d(x,y)+d(y,z)$$and the proof is complete $\blacksquare$