Ultrametric space

In mathematics, an ultrametric space is a metric space in which the triangle inequality is strengthened to d(x,z)≤max⁡{d(x,y),d(y,z)} for all x, y, and z. Sometimes the associated metric is also called a non-Archimedean metric or super-metric.

Formal definition

An ultrametric on a set M is a real-valued function

d:M×M→ℝ

(where ℝ denotes the real numbers), such that for all x,y,z∈M:

  1. d(x,y)≥0 with equality if and only if x=y (non-degeneracy)
  2. d(x,y)=d(y,x) (symmetry)
  3. d(x,z)≤max⁡{d(x,y),d(y,z)} (strong triangle inequality or ultrametric inequality).

An ultrametric space is a pair (M,d) consisting of a set M together with an ultrametric d on M, which is called the space's associated distance function (also called a metric).

If d satisfies all of the conditions but the "if and only if" in condition 1 is weakened to "if", then d is called an ultrapseudometric on M. An ultrapseudometric space is a pair (M,d) consisting of a set M and an ultrapseudometric d on M.

In the case when M is an Abelian group (written additively) and d is generated by a length function ‖⋅‖ (so that d(x,y)=‖x−y‖), the last property can be made stronger using the Krull sharpening to:

‖x+y‖≤max⁡{‖x‖,‖y‖} with equality if ‖x‖≠‖y‖.

We want to prove that if ‖x+y‖≤max⁡{‖x‖,‖y‖}, then the equality occurs if ‖x‖≠‖y‖. Without loss of generality, let us assume that ‖x‖>‖y‖. This implies that ‖x+y‖≤‖x‖. But we can also compute ‖x‖=‖(x+y)−y‖≤max⁡{‖x+y‖,‖y‖}. Now, the value of max⁡{‖x+y‖,‖y‖} cannot be ‖y‖, for if that is the case, we have ‖x‖≤‖y‖ contrary to the initial assumption. Thus, max⁡{‖x+y‖,‖y‖}=‖x+y‖, and ‖x‖≤‖x+y‖. Using the initial inequality, we have ‖x‖≤‖x+y‖≤‖x‖ and therefore ‖x+y‖=‖x‖.

Properties

In the triangle on the right, the two bottom points x and y violate the condition d(x, y) ≤ max{d(x, z), d(y, z)}.

From the above definition, one can conclude several typical properties of ultrametrics. For example, for all x,y,z∈M, at least one of the three equalities d(x,y)=d(y,z) or d(x,z)=d(y,z) or d(x,y)=d(z,x) holds. That is, every triple of points in the space forms an isosceles triangle, so the whole space is an isosceles set.

Defining the (open) ball of radius r>0 centred at x∈M as B(x;r):={y∈M∣d(x,y)<r}, we have the following properties:

Proving these statements is an instructive exercise. All directly derive from the ultrametric triangle inequality. Note that, by the second statement, a ball may have several center points that have non-zero distance. The intuition behind such seemingly strange effects is that, due to the strong triangle inequality, distances in ultrametrics do not add up.

Examples

Applications