2

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.

darij grinberg
  • 17,777
Rame
  • 21

3 Answers3

2

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.

darij grinberg
  • 17,777
ugur efem
  • 585
2

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

Brian M. Scott
  • 616,228
1

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.

darij grinberg
  • 17,777