ultrametric

Any metric $d:X\times X\to ℝ$ on a set $X$ must satisfy the triangle inequality:

$$(\forall x,y,z)\mathit{\hspace{1em}}d(x,z)\le d(x,y)+d(y,z)$$

An ultrametric must additionally satisfy a stronger version of the triangle inequality:

$$(\forall x,y,z)\mathit{\hspace{1em}}d(x,z)\le \max \{d(x,y),d(y,z)\}$$

Here is an example of an ultrametric on a space with 5 points, labelled $a,b,c,d,e$:

In the table above, an entry $n$ in the for element $x$ and the for element $y$ indicates that $d(x,y)=n$, where $d$ is the ultrametric. By symmetry of the ultrametric ($d(x,y)=d(y,x)$), the above table yields all values of $d(x,y)$ for all $x,y\in \{a,b,c,d,e\}$.

The ultrametric condition is equivalent to the ultrametric three point condition:

$$(\forall x,y,z)\mathit{\hspace{1em}}x,y,z\text{ can be renamed such that }d(x,z)\le d(x,y)=d(y,z)$$

Ultrametrics can be used to model bifurcating hierarchical systems.  The distance between nodes in a weight-balanced binary tree is an ultrametric. Similarly, an ultrametric can be modelled by a weight-balanced binary tree, although the choice of tree is not necessarily unique.  Tree models of ultrametrics are sometimes called ultrametric trees.

The metrics induced by non-Archimedean valuations are ultrametrics.

Title	ultrametric
Canonical name	Ultrametric
Date of creation	2013-03-22 13:28:28
Last modified on	2013-03-22 13:28:28
Owner	Koro (127)
Last modified by	Koro (127)
Numerical id	21
Author	Koro (127)
Entry type	Definition
Classification	msc 54E35
Related topic	MetricSpace
Related topic	Valuation
Related topic	UltrametricSpace