1
$\begingroup$

The discrete metric $d_0$ can take two values $0$ and $1$. Can a metric function $d_X$ on a set $X$ attain exactly three distinct values?

Going through the route of actually finding a metric instead of disproving one exists, I tried finding a metric which has values $0$, $a$ and $b$. But by trying to define it in a similar way as the discrete metric, I had a hard time finding one that could satisfy the three requirements to be a metric.

Disproving it on the other hand sounds pretty easy tho, by just taking $x, y, z \in X$, I set the two values to random distances like $d_X(x, y) = a = d_X(y,x)$ , $d_X(x, z) = b = d_X(z, x)$ and finally $d_X(y, z) = c = d_X(z, y)$, with $c$ being either $a$ or $b$. Applying this to the triangle inequality gives us.

$d_X(x, z) \leq d_X(x, y) + d_X(y,z)$
$d_X(x, y) \leq d_X(x, z) + d_X(z,y)$
$d_X(y, z) \leq d_X(y, x) + d_X(x,z)$

Which gives us the linear inequalities:

$b \leq a + c$
$a \leq b + c$
$c \leq a + b$

This cannot hold if $c$ is either $a$ or $b$. Is this proof correct? And more importantly, isn't there a better proof, because this sounds like a very inefficient proof.

$\endgroup$
  • $\begingroup$ Your proof does not work. Once you say that $x \in X$, but then you say $x=a$ or $x=b$ (meaning that $x \in \Bbb{R}_{\ge 0}$), so you are contradicting yourself if $X$ and $\Bbb{R}_{\ge 0}$ are disjoint. Another thing you say is "this cannot hold if $x$ is either $a$ or $b$": this is not correct, because you are not considering the case $a=b=x$ or the case $x=a=2b$. $\endgroup$ – Crostul Jun 13 '17 at 10:25
  • $\begingroup$ I did consider those cases $a = b = x$, but that case ends up with a metric that does not have exactly three distinct values. And yeah I now realize I used the letter $x$ for two different things, I'll edit that in the question by using $c$ to show the difference. $\endgroup$ – TSpoon Jun 13 '17 at 11:56
  • $\begingroup$ Your other case does hold tho, can't believe I looked over that, thanks for the critique and your answer. $\endgroup$ – TSpoon Jun 13 '17 at 12:04
4
$\begingroup$

Let $X$ be any set with a partition into two nonempty disjoint subsets $A$ and $B$: $$X=A \cup B \ \ \ \wedge \ \ \ A \cap B = \emptyset$$ Define $$d_X(x,y) = \begin{cases} 0 & \mbox{if }x=y \\ 1 & \mbox{if } x,y \in A \\ 1 & \mbox{if } x,y \in B \\ 2 & \mbox{otherwise} \end{cases}$$

This is a distance defined on $X$ with only three values.

$\endgroup$
  • $\begingroup$ Interesting, can your argument be easily generalized to metrics taking $n$ values? $\endgroup$ – Surb Jun 13 '17 at 10:28
  • 1
    $\begingroup$ Yes of course. You have to consider a partition of $X$ into $n$ classes $A_1, \dots , A_n$. Then define $d(x_i, x_j)= |i-j|+1$ where $x_i \in A_i$ and $x_j \in A_j$. $\endgroup$ – Crostul Jun 13 '17 at 10:33
2
$\begingroup$

I believe the space of 3 points $\{x,y,z\}$ with the metric $d:=\begin{cases} d(x,y)=1\\ d(x,z)=2\\ d(y,z)=1\\ \end{cases}$

satisfies the requirement too.

$\endgroup$

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.