Thread: Ultrametrics

I've been asked to show that a particular metric is actually an ultrametric. I'm a little lost, and I'll post what I have.

Here's the metric we're supposed to look at:

Let $\displaystyle X$ be any nonempty set. Define a metric $\displaystyle \mu : X \times X \to \mathbb{R}$ by letting $\displaystyle \mu (x,x) = 0$ and $\displaystyle \mu (x,y) = \mu (y,z)$ be any number in the interval $\displaystyle [1,2]$ when $\displaystyle x \neq y$.

And the problem is to show that this is an ultrametric, or that $\displaystyle \mu (x,z) \leq Max\[\mu (x,y), \mu (y,z)\]$ for all $\displaystyle x,y,z \in X$.

Here's my attempt at the proof:

First, since $\displaystyle \mu$ is a metric, we are given that $\displaystyle \mu (x,z) \leq \mu (x,y) + \mu (y,z)$. If $\displaystyle x = z$, then $\displaystyle \mu (x,z) = 0 \leq Max\[\mu (x,y), \mu (y,z)\]$. If $\displaystyle x \neq z$ and $\displaystyle x = y$ OR $\displaystyle y = z$, then

$\displaystyle \mu (x,z) \leq \mu (x,y) + \mu (y,z) = \mu (x,y) + 0 = Max\[\mu (x,y),\mu (y,z)\]$
or
$\displaystyle \mu (x,z) \leq \mu (x,y) + \mu (y,z) = 0 + \mu (y,z) = Max\[\mu (x,y), \mu (y,z)\]$

The only remaining case is when $\displaystyle x\neq y\neq z$.

I can't figure out the solution for this. It may be that I am taking the wrong approach. Any help is greatly appreciated.

Nothing?

If $\displaystyle x\neq y\neq z$ then by the definition of the metric $\displaystyle \mu(y,x) = \mu(x,z) = \mu(z,y) \in [1,2]$. Hence $\displaystyle \mu(x,y) = \mu(y,z) = \mu(x,z) = \max[\mu(x,y),\mu(y,z)]$.

Originally Posted by SlipEternal

If $\displaystyle x\neq y\neq z$ then by the definition of the metric $\displaystyle \mu(y,x) = \mu(x,z) = \mu(z,y) \in [1,2]$. Hence $\displaystyle \mu(x,y) = \mu(y,z) = \mu(x,z) = \max[\mu(x,y),\mu(y,z)]$.

I really appreciate your response. I'm just wondering how the definition of the metric implies that they are all equal... I looked at all of the properties of the metric that are in the definition I was given, and none of them outright imply this. The closest I can see is the property that $\displaystyle \mu (x,y) = \mu (y,x)$ for all $\displaystyle x,y \in X$, but that doesn't lead me straight to where you were.

That definition gives: $\displaystyle \mu(y,x) = \mu(x,z)$ since $\displaystyle y\neq x$. $\displaystyle \mu(x,z) = \mu(z,y)$ since $\displaystyle x \neq z$. $\displaystyle \mu(z,y) = \mu(y,x)$ since $\displaystyle z \neq y$.

Also, $\displaystyle \mu(y,x) = \mu(x,y)$ and $\displaystyle \mu(z,y) = \mu(y,z)$ because $\displaystyle \mu$ is a metric (so it is symmetric).

Put that all together, and you get that everything is equal.

Originally Posted by Aryth

Let $\displaystyle X$ be any nonempty set. Define a metric $\displaystyle \mu : X \times X \to \mathbb{R}$ by letting $\displaystyle \mu (x,x) = 0$ and $\displaystyle \mu (x,y) = \mu (y,z)$ be any number in the interval $\displaystyle [1,2]$ when $\displaystyle x \neq y$.

The bolded text is where I got those equalities, by the way.

Also, if that is not the case $\displaystyle \left( \mbox{if that was a typo, and it should have read }\mu(x,y) = \mu(y,x)\mbox{ instead of }\mu(x,y) = \mu(y,z)\right)$, then here is an example of a set $\displaystyle X$ where $\displaystyle \mu$ is not an ultrametric. Example:

$\displaystyle X = \left\{(0,0),(1,0),\left(0,\dfrac{5}{4}\right) \right\} \subset \mathbb{R}^2$

Let $\displaystyle \mu$ be the standard Euclidean metric, $\displaystyle x = (1,0), y = (0,0), z = \left(0,\dfrac{5}{4}\right)$.
$\displaystyle \mu(x,y) = 1\in [1,2]$, $\displaystyle \mu(y,z) = \dfrac{5}{4}\in [1,2]$ and $\displaystyle \mu(x,z) = \dfrac{3}{2}\in [1,2]$. Hence $\displaystyle \mu(x,z) > \max[\mu(x,y),\mu(y,z)]$.

I see now. I completely overlooked that fact. Thanks a lot for your help!