# Ultrametric example

Can anybody give an example for ultrametric space? i.e., in the metric space definition, instead of triangle inequality, we have strong triangle inequality, namely $$d(x,y) \leq \max \left\{d(x,z),d(z,y)\right\}$$ for all $$x,y,z$$.

A trivial example is the discrete metric. I want some non trivial example.

For a very trivial example, let $X$ be any set, and let $d$ be the discrete metric on $X$; $d(x,y)=0$ if $x=y$, and $d(x,y)=1$ otherwise. Clearly this $d$ is an ultrametric, and it generates the discrete topology.

For a much more interesting example, let $D=\{0,1\}$ with the discrete topology, and let $X=D^{\Bbb N}$, the Cartesian product of countably infinitely many copies of $D$. Elements of $X$ are sequences $x=\langle x_n:n\in\Bbb N\rangle$ such that each $x_n$ is either $0$ or $1$. (This space is homeomorphic to the well-known middle-thirds Cantor set.)

For distinct $x,y\in X$ let $\delta(x,y)=\min\{n\in\Bbb N:x_n\ne y_n\}$, the first index at which $x$ and $y$ disagree. We can define a metric $d$ on $X$ by setting

$$d(x,y)=\begin{cases} 0,&\text{if }x=y\\ 2^{-\delta(x,y)},&\text{otherwise}\;. \end{cases}$$

In words, $d$ ‘says’ that if $x$ and $y$ agree on their first $n$ terms, then $d(x,y)$ is at most $\frac1{2^n}$.

It’s clear that $d$ is symmetric and separates points. Now let $x,y,z\in X$; we want to show that

$$d(x,y)\le\max\{d(x,z),d(z,y)\}\;.$$

This is clear if $x=z$, $y=z$, or $x=y$, so assume that the three points are distinct. Let $k=\delta(x,z)$ and $\ell=\delta(z,y)$, and without loss of generality assume that $k\le\ell$. Then $x_n=z_n=y_n$ for each $n<k$, so $\delta(x,y)\ge k$, and therefore

$$d(x,y)=2^{-\delta(x,y)}\le 2^{-k}=\max\left\{2^{-k},2^{-\ell}\right\}=\max\{d(x,z),d(z,y)\}\;,$$

and $d$ is an ultrametric.

I’ll leave it as an exercise, if you’re interested, to show that $d$ generates the product topology on $X$.

• Is this the Hamming distance by the way? – ugur efem May 29 '16 at 19:16
• @ugurefem: No, the Hamming distance is defined only for finite binary sequences (of the same length) and is the number of positions in which two sequences disagree. – Brian M. Scott May 29 '16 at 19:17

This is an old question, but here is an example that has helped me a lot in visualizing ultrametric spaces.

Consider the taxonomic hierarchy of organisms. Let $$X$$ be the set of all organisms, and let $$d : X \times X \to \mathbb{R}_+$$ be a distance function such that $$d\left(x,y\right)$$ gets smaller as $$x$$ and $$y$$ get more and more similar. For example:

• $$d\left(x,y\right) = 0$$ if $$x = y$$;

• $$d\left(x,y\right) = 1$$ if $$x$$ and $$y$$ belong to the same species but are distinct;

• $$d\left(x,y\right) = 2$$ if $$x$$ and $$y$$ belong to the same genus but not to the same species;

• $$d\left(x,y\right) = 3$$ if $$x$$ and $$y$$ belong to the same family but not to the same genus;

etc.

Then, $$\left(X, d\right)$$ is an ultrametric space.

First observe that any nonzero rational number in $$\mathbb Q$$ has a unique factorization into prime numbers (allowing negative exponents of course). Next, let $$p$$ be a prime and for any $$\frac{a}{b}\in\mathbb Q$$ define $$v_p\left(\frac{a}{b}\right)$$ to be the exponent of the prime $$p$$ in the factorization of $$\frac{a}{b}$$, and $$v_p(0)=\infty$$. Now let $$\epsilon<1$$ be positive, and define $$d_p(r,s) = \epsilon^{v_p(r-s)}$$.

This is known as the $$p$$-adic norm on $$\mathbb Q$$, you can check it is an ultrametric.