Proving that $d((x_n),(y_n)) := 2 ^{−\min \{n \in \mathbb{N}: x_n \neq y_n \} }$ defines a metric on $S$, $S$ being the set of $0-1$ sequence.. Mm currently struggling to prove the statement in the title. I'm aware of how a metric is defined but i have no clue how to prove this.
Here is the whole problem, but better readable:
Let $S := \{0,1\}^{\mathbb{N}} $ the set of $0-1$ sequences.
Prove that $d((x_n),(y_n)) := 2 ^{−\min \{n \in \mathbb{N}: x_n \neq y_n \} }$ defines a metric on S.
Found nothing that could help to solve this problem on the internet.
I'd be very thankfull for help on this topic :)
Best regards
 A: Welcome to MSE!:~)
To make the definition rigorous you need to define what happens to $d(,)$ when $\forall n ,x_n=y_n$ (same sequence). Let's assume in that case you set $\min \{n \in \mathbb{N}: x_n \neq y_n \} =\infty$, and we understand $2^{-\infty}=0$. (this is sloppy, but it should be solved at the definition.)
If that's the case then we got

*

*Identity $d((x_n),(x_n))=0$ we get this for free from definition above.


*Symmetry, this is also obvious, since $\neq$ is symmetric $d((y_n),(x_n))= 2 ^{−\min \{n \in \mathbb{N}: x_n \neq y_n \} }
=d((x_n),(y_n))$


*Triangle inequality. Assume $(x_n),(y_n),(z_n)$, prove $d((z_n),(x_n))\leq d((y_n),(x_n))+d((y_n),(z_n))$
First, if two sequences match $(y_n)=(x_n)$ or $(y_n)=(z_n)$, then using the already proved symmetry and identity, the triangle inequality holds.
Otherwise, let $p=\min \{n \in \mathbb{N}: x_n \neq y_n \}$, $q=\min \{n \in \mathbb{N}: z_n \neq y_n \}$, $p,q$ are finite integers. $(x_n),(y_n)$ match in their first $p-1$ "digits", $(z_n),(y_n)$ match in their first $q-1$ "digits"
Without loss of generality, let $p\leq q$. Then, $\forall n\leq p-1, x_n=y_n=z_n$.
Thus the first "digit" $(z_n),(x_n)$ differs is at least at $p$ $$\min \{n \in \mathbb{N}: x_n \neq z_n \}\geq p$$
Thus
$$
d((z_n),(x_n))\leq2^{-p} < 2^{-p} + 2^{-q}=d((y_n),(x_n))+d((y_n),(z_n))
$$
Thus we proved triangle inequality.
We prove that $d$ is a metric with the 3 conditions in the definition.
