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$?

  • 1
    $\begingroup$ 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. $\endgroup$
    – JKL
    May 3, 2022 at 21:19
  • 1
    $\begingroup$ 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$). $\endgroup$
    – Rob Arthan
    May 3, 2022 at 21:22
  • 1
    $\begingroup$ $$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)$ $\endgroup$
    – Mittens
    May 3, 2022 at 22:34

1 Answer 1


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}$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .