1

Hi I am trying to prove that the set of binary strings is a metric space. I define $S$ as the binary string (0/1). For two different strings I look at the metric space for the number of entries in which the two strings differ.

So $x=10000$ and $y=11000$ would be $1$ clearly. I am trying to prove the triangle inequality for a metric space on this but I am having trouble doing it vigorously enough. I want to show:

$$d(a,b)\le d(a,c)+d(b,c)$$

I said that $A,C$ differ by $K$ entries and $B,C$ differ by $J$ entries. I think that $A,B$ cannot differ by more than $K+J$ but I can't prove it can someone help me out?

Jean Marie
  • 81,803

1 Answers1

0

When you add any two members of same length, say $n$, some of the non-zero entries may become zero (due to the fact that string is binary). Therefore, given any two vectors, their sum has definitely fewer non-zero entries than the sum of their individual non-zero entries. In other words,

Given any $x$ an $y$ in the said domain,

$d(0,x)+d(0,y)\geq d(0,x+y)$.

Obviously,

$a+b=a+c+b+c$, since the string is binary and $c+c=\theta$.

So,

$d(0,a+b)\leq d(0,a+c)+d(0,b+c)$. Note that $d(0,a+b)=d(a,b)$. Therefore,

$d(a,b)\leq d(a,c)+d(b,c)$.

pmun
  • 1,344