2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Is this the Hamming distance by the way? $\endgroup$ – ugur efem May 29 '16 at 19:16
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott May 29 '16 at 19:17
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\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.