given the function

$d:\{0,1\}^\Bbb N \times \{0,1\}^\Bbb N \rightarrow \Bbb R_0^+ $

$d(a,b):= \begin{Bmatrix} 0 &if&a=b\\\frac{1}{min\{k\in\Bbb N|a_k\neq b_k\}} & if & a\ne b \end{Bmatrix}$

Now we are given in the definition of d that d(a,b)=0 iff a=b and we also know that $\frac{1}{min\{k \in \Bbb N |a_k \neq b_k\}} >0$. So condition one is satisfied.

next if a=b then d(a,b)=0=d(b,a)

and if $a\neq b$ then $d(a,b)=\frac{1}{min\{k\in \Bbb N | a_k \neq b_k\}}=\frac{1}{min\{k \in \Bbb N | b_k \neq a_k\}}=d(b,a)$

But finally I don't think it satisfies the triangle inequality, because

$d(a,c)\leq d(a,b)+d(b,c)$ implies that $\frac{1}{min\{k\in \Bbb N | a_k \neq c_k\}}\leq\frac{1}{min\{q\in \Bbb N | a_q \neq b_q\}} + \frac{1}{min\{p\in \Bbb N | b_p \neq c_p\}} $

but if the minimum k was 1 , and the minimum p and q were say 4 then we would have $1 \leq 0.5$ which is not true ....is this correct ?

  • $\begingroup$ The minimum $p$ and $q$ cannot both be 4 when the minimum $k$ is 1. Do you see why? If not, try to give explicit examples of $a, b, c$ to see where your idea goes wrong. $\endgroup$ – Mees de Vries Aug 6 '18 at 14:09
  • $\begingroup$ @MeesdeVries we could say that a=n , b=1/n and c=1+n , then k =1 ,q= 2 and p=1. so then $d(a,c)\leq d(a,b)+d(b,c)$ I'm confused however as to how to show this generally ? $\endgroup$ – excalibirr Aug 6 '18 at 14:18

Let me prove the triangle inequality just in the special case that $a,b,c$ are all different from each other (the case where two of them are equal, or where all three are equal, is easy).

First let's evaluate the left hand side of the triangle inequality: let $K = \min\{k \in \mathbb N \mid a_k \ne c_k\}$, so $d(a,c)=\frac{1}{K}$.

Notice that $a_K \ne c_K$. As a consequence of this, it is not possible that both of the equations $a_K = b_K$ and $b_K = c_K$ are true: at least one of those two equations must be an inequality, $a_K \ne b_K$ or $b_K \ne c_K$. Therefore, at least one of the two numbers $Q = \min\{q \in \mathbb N \mid a_q \ne b_q\}$ or $P = \min\{p \in \mathbb N \mid b_p = c_p\}$ must be less than or equal to $K$.

It follows that $d(a,c)=\frac{1}{K}$ is less than or equal to at least one of the two numbers $\frac{1}{Q}$ or $\frac{1}{P}$, so $d(a,c)$ must be less than or equal to their sum $\frac{1}{Q} + \frac{1}{P}$, which proves that $$d(a,c) \le d(a,b) + d(b,c) $$


Let $a,c \in \{0,1\}^\mathbb N$. Suppose $a_{i} = c_i$ for all $i \leq l-1$ and $a_l \neq c_l$. Note that the inequality is obvious if $a=c$, since $d$ is non-negative.

Now let $b$ be any other sequence in $\{0,1\}^{\mathbb N}$. Then, since $a_l \neq c_l$, we see that either $b_l \neq a_l$ or $b_l \neq c_l$ must happen. Consequently, $d(a,b) \geq \frac 1l$ or $d(a,c) \geq \frac 1l$ must happen. By the fact that $d$ is non-negative, we get $d(a,b)+ d(b,c) \geq \frac 1l = d(a,c)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.