Ultrametric space
|
|
In mathematics, an ultrametric space is a special kind of metric space. Sometimes the associated metric is also called non-Archimedean metric or super-metric. Although some of the theorems for ultrametric spaces may seem strange at a first glance, they appear naturally in many applications.
Important applications arise in the field of denotational semantics, where points represent a certain amount of information or knowledge. A contraction mapping may then be thought of as a way of approximating the final result of a computation (which can be guaranteed to exist by the Banach fixed point theorem). Similar ideas can be found in domain theory. Another important field of application is phylogenetic trees.
P-adic analysis makes heavy use of the ultrametric nature of the p-adic metric.
Formal definition
Formally, an ultrametric space is a set of points M with an associated distance function (also called a metric)
- d : M × M → R
where R is the set of real numbers), such that for all x, y, z in M, one has:
- d(x, y) = 0 iff x=y
- d(x, y) = d(y, x) (symmetry)
- d(x, z) ≤ max{d(x, y), d(y, z)} (strong triangle or ultrametric inequality).
Properties
From the above definition, one can conclude several typical properties of ultrametrics. For example, in an ultrametric space, for all x, y, z in M and r, s in R:
- Every triangle is isosceles, i.e. d(x,y) = d(y,z) or d(x,z) = d(y,z) or d(x,y) = d(z,x).
- Every point inside a ball is its center, i.e. if d(x,y) < r then B(x; r) = B(y; r).
- Intersecting balls are contained in each other, i.e. if B(x; r) ∩ B(y; s) is non-empty then either B(x; r) ⊆ B(y; s) or B(y; s) ⊆ B(x; r).
Here, the concept and notation of an (open) ball is the same as in the article about metric spaces, i.e.
- B(x; r) = { y ∈ M | d(x, y) < r } .
- Such balls are both, open and closed sets, for the induced topology. The same is true for closed balls, defined by replacing "<" by "≤".
- The set of all open balls with radius r and center in a closed ball of radius r > 0 forms a partition of the latter, and the mutual distance of two distinct open balls is again equal to r.
Proving these statements is an instructive exercise. 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
- Consider the set of words of arbitrary length (finite or infinite) over some alphabet Σ. Define the distance between two different words to be 2-n, where n is the first place at which the words differ. The resulting metric is an ultrametric.
- The p-adic numbers form a complete ultrametric space.de:Ultrametrik