2

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 ?

excalibirr
  • 2,795
  • 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. – Mees de Vries Aug 06 '18 at 14:09
  • @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 ? – excalibirr Aug 06 '18 at 14:18

1 Answers1

3

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

Lee Mosher
  • 120,280