# Show that $d(\overline{x},\overline{y}) = 2^{-m}$ defines a metric.

Show that in the space of one-sided sequences, $$X=\{\overline{x}= (x_n)_{n \in \mathbb{N}}\ ; x_n \in \mathbb{R} \}$$, the function $$d(\overline{x},\overline{y}) = 2^{-m}$$

where $$m$$ is the biggest value where $$x_j=y_j$$ for every $$1\leq j < m$$ defines a metric.

I would like to know how I show triangle inequality, but I don´t understand what could be the value of $$m$$ in a sequence, because if I take $$e_1=\{1,0,0, \ldots \}$$ and $$e_2=\{0,1,0,\ldots \}$$, what is the value of $$m$$?

• In your example, $m = 1$. Think of $m-1$ as the last index on which your two sequences $\overline{x}$ and $\overline{y}$ are completely the same up to that point.
– JKL
May 3, 2022 at 21:19
• In your example, $m = 0$: $e_1$ and $e_2$ have no initial subsequence in common. (I take $0$ to be a natural number, if $0$ isn't a natural number for you, it will be $m = 1$.) Note also that the definition should say that you take the $d(x, y)$ to be $0$ when $x$ and $y$ are equal (when in a sense $m$ comes out to be $\infty$). May 3, 2022 at 21:22
• $$d(\overline{x},\overline{y})=\max_m\{2^{-m}\mathbb{1}(|\overline{x}(m)-\overline{y}(m)|>0)\}$$ $\mathbb{1}(|\overline{x}(m)-\overline{y}(m)|>0)\leq \mathbb{1}(|\overline{x}(m)-\overline{z}(m)|>0)+ \mathbb{1}(|\overline{z}(m)-\overline{y}(m)|>0)$ May 3, 2022 at 22:34

First, we should define that $$m = \infty$$ if $$\bar x = \bar y$$ and $$2^{-\infty} := 0$$.

$$\bar x = \bar y \implies d(\bar x, \bar y) = 0$$ is clear then.

To show $$d(\bar x, \bar y) = 0 \implies \bar x = \bar y$$ we assume that $$d(\bar x, \bar y) = 0$$ holds, i.e. $$2^{-m} = 0$$. We therefore get $$m = \infty$$ and thus $$\bar x = \bar y.$$

For the triangle inequality we need to show that $$d(\bar x, \bar z) \leq d(\bar x, \bar y) + d(\bar y, \bar z)$$, i.e. $$2^{-m_{xz}} \leq 2^{-m_{xy}} + 2^{-m_{yz}}$$.

Notice that $$m_{xz} \geq \min\{m_{xy}, m_{yz}\}$$ because if the first $$m_{xy} - 1$$ elements of $$\bar x$$ and $$\bar y$$ are the same and also the first $$m_{yz} - 1$$ elements of $$\bar y$$ and $$\bar z$$ are the same, then at least the first $$\min\{m_{xy}, m_{yz}\}-1$$ elements of $$\bar x$$ and $$\bar z$$ must be the same.

We then get $$2^{-m_{xz}} \leq 2^{-\min\{m_{xy}, m_{yz}\}}$$ and because $$2^a \geq 0$$ for $$a \in -\mathbb{N} \cup \{-\infty\}$$ we get $$2^{-m_{xz}} \leq 2^{-\min\{m_{xy}, m_{yz}\}} \leq 2^{-\min\{m_{xy}, m_{yz}\}} + 2^{-\max\{m_{xy}, m_{yz}\}} = 2^{-m_{xy}} + 2^{-m_{yz}},$$

which is what we wanted to show.

Edit: In your example $$m = 1$$, as JKL pointed out, because $$e_{11} \neq e_{21}$$ and hence the largest $$m$$ such that $$e_{1j} = e_{2j}$$ holds for all $$1 \leq j \lt m$$ is $$m = 1$$ because then as a constraint for $$j$$ we have $$1 \leq j \lt 1$$, which is false for every $$j \in \mathbb{N}$$.