Metric space

From Wikipedia, the free encyclopedia

In mathematics, a metric space is a set where a notion of distance (called a metric) between elements of the set is defined.

The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space. In fact, the notion of "metric" is a generalization of the Euclidean metric arising from the four long known properties of the Euclidean distance. The Euclidean metric defines the distance between two points as the length of the straight line connecting them.

The geometric properties of the space depends on the metric chosen, and by using a different metric we can construct interesting non-Euclidean geometries such as those used in the theory of general relativity.

A metric space also induces topological properties like open and closed sets which leads to the study of even more abstract topological spaces.

[edit] History

Maurice Fréchet introduced metric spaces in his work Sur quelques points du calcul fonctionnel, Rendic. Circ. Mat. Palermo 22 (1906) 1–74.

[edit] Definition

A metric space is an ordered pair (M,d) where M is a set (which some authors require to be non-empty) and d is a metric on M, that is, a function

$d : M \times M \rightarrow \mathbb{R}$

such that for any x, y and z in M

d(x, y) ≥ 0 (non-negativity)
d(x, y) = 0 if and only if x = y (identity of indiscernibles)
d(x, y) = d(y, x) (symmetry)
d(x, z) ≤ d(x, y) + d(y, z) (triangle inequality).

The first condition follows from the other three, since:

2d(x, y) = d(x, y) + d(y, x) ≥ d(x,x) = 0.

The function d is also called distance function or simply distance. Often d is omitted and one just writes M for a metric space if it is clear from the context what metric is used. Relaxing the second requirement, or removing the third or fourth, leads to the concepts of a pseudometric space, a quasimetric space, or a semimetric space. If the function takes values in the extended real number line R∪{∞}, but otherwise satisfies above conditions, then it is called an extended metric and the corresponding space is called an $\infty$ -metric space.

[edit] Examples of metric spaces

Ignoring mathematical details, for any system of roads and terrains the distance between two locations can be defined as the length of the shortest route connecting those locations. To be a metric there shouldn't be any one-way roads. The triangle inequality expresses the fact that detours aren't shortcuts. Many of the examples below can be seen as concrete versions of this general idea.
The real numbers with the distance function d(x, y) = |y − x| given by the absolute value, and more generally Euclidean n-space with the Euclidean distance, are complete metric spaces. The rational numbers with the same distance function are also a metric space, but are not complete.
Any normed vector space is a metric space by defining d(x, y) = ||y − x||, see also relation of norms and metrics. (If such a space is complete, we call it a Banach space). Examples:
- the Manhattan norm gives rise to the Manhattan distance, where the distance between any two points, or vectors, is the sum of the distances between corresponding coordinates.
- The maximum norm gives rise to the Chebyshev distance or chessboard distance, the minimal number of moves a chess king would take to travel from x to y.
The British Rail metric (also called the Post Office metric or the SNCF metric) on a normed vector space, given by d(x, y) = ||x|| + ||y|| for distinct points x and y, and d(x, x) = 0. More generally ||.|| can be replaced with a function f taking an arbitrary set S to non-negative reals and taking the value 0 at most once: then the metric is defined on S by d(x, y)=f(x)+f(y) for distinct points x and y, and d(x, x) = 0. The name alludes to the tendency of railway journeys (or letters) to proceed via London (or Paris) irrespective of their final destination.
If (M,d) is a metric space and X is a subset of M, then X becomes a metric space by restricting d to X×X.
The discrete metric, where d(x,y)=0 if x = y and d(x,y)=1 otherwise, is a simple but important example, and can be applied to all non-empty sets. This, in particular, shows that for any non-empty set, there is always a metric space associated to it. Using this metric, any point is an open ball, and therefore every subset is open and the space has the discrete topology.
The hyperbolic plane is a metric space.
If X is some set and M is a metric space, then the set of all bounded functions f : X → M (i.e. those functions whose image is a bounded subset of M) can be turned into a metric space by defining d(f, g) = sup_{x in X} d(f(x), g(x)) for any bounded functions f and g. If M is complete, then this space is complete as well.
If X is a topological (or metric) space and M is a metric space, then the set of all bounded continuous functions from X to M forms a metric space if we define the metric as above: d(f, g) = sup_{x in X} d(f(x), g(x)) for any bounded continuous functions f and g. If M is complete, then this space is complete as well.
If M is a connected Riemannian manifold, then we can turn M into a metric space by defining the distance of two points as the infimum of the lengths of the paths (continuously differentiable curves) connecting them.
If G is an undirected connected graph, then the set V of vertices of G can be turned into a metric space by defining d(x, y) to be the length of the shortest path connecting the vertices x and y.
The Levenshtein distance, also called character edit distance, is a measure of the dissimilarity between two strings u and v. The distance is the minimal number of character deletions, insertions, or substitutions required to transform u into v. This can be thought as a special case of shortest path metric in a graph.
Similarly, in 3D, the metrics on the surface of a polyhedron include the ordinary metric, and the distance over the surface; a third metric on the edges of a polyhedron is one where the "paths" are the edges. For example, the distance between opposite vertices of a unit cube is √3 (Euclidean metric), √5 (surface path), and 3 (edges path), respectively.
Given a metric space (X,d) and an increasing concave function f:[0,∞)→[0,∞) such that f(x)=0 if and only if x=0, then f o d is also a metric on X.
Given an injective function f from any set A to a metric space (X,d), d(f(x), f(y)) defines a metric on A.
Using T-theory, the tight span of a metric space is also a metric space. The tight span is useful in several types of analysis.
The set of all m by n matrices over some field is a metric space with respect to the rank distance d(X,Y) = rank(Y-X).
The Helly metric is used in game theory.

[edit] Open and closed sets, topology and convergence

Every metric space is a topological space in a natural manner, and therefore all definitions and theorems about topological spaces also apply to all metric spaces.

About any point x in a metric space M we define the open ball of radius r (>0) about x as the set

B(x; r) = {y in M : d(x,y) < r}.

These open balls generate a topology on M, making it a topological space.

Explicitly, a subset U of M is called open if to every x in U there exists an r>0 such that B(x; r) is contained in U. The complement of an open set is called closed. A neighborhood of the point x is any subset of M that contains an open ball about x as a subset.

A topological space which can arise in this way from a metric space is called a metrizable space; see the article on metrization theorems for further details.

A sequence (x_n) in a metric space M is said to converge to the limit x∈M iff for every r>0 there exists a natural number N such that d(x_n,x) < r for all n>N. Equivalently, one can use the general definition of convergence available in all topological spaces.

A subset A of the metric space M is closed if and only if every sequence in A that converges to a limit in M has its limit in A.

[edit] Types of metric spaces

[edit] Complete spaces

A metric space $M$ is said to be complete if every Cauchy sequence converges in $M$ . That is to say: if $d(x_n, x_m) \to 0$ as both n and m independently go to infinity, then there is some $y\in M$ with $d(x_n, y) \to 0$ .

Every Euclidean space is complete, as is every closed subset of a complete space. The rational numbers, using the absolute value metric d(x,y)=|x-y|, are not complete.

Every metric space has a unique completion, which is a complete space that contains the given space as a dense subset. For example, the real numbers are the completion of the rationals.

If X is a complete subset of the metric space M, then X is closed in M. Indeed, a space is complete if and only if it is closed in any containing metric space.

Every complete metric space is a Baire space.

[edit] Bounded and totally bounded spaces

A metric space M is called bounded if there exists some number r, such that d(x,y) ≤ r for all x and y in M. The smallest possible such r is called the diameter of M. The space M is called precompact or totally bounded if for every r > 0 there exist finitely many open balls of radius r whose union covers M. Since the set of the centres of these balls is finite, it has finite diameter, from which it follows (using the triangle inequality) that every totally bounded space is bounded. The converse does not hold, since any infinite set can be given the discrete metric (one of the examples above) under which it is bounded and yet not totally bounded.

Note that in the context of intervals in the space of real numbers and occasionally regions in a Euclidean space Rⁿ a bounded set is referred to as "a finite interval" or "finite region". However boundedness should not in general be confused with "finite", which refers to the number of elements, not to how far the set extends; finiteness implies boundedness, but not conversely.

[edit] Compact spaces

A metric space M is compact if every sequence in M has a subsequence that converges to a point in M. This is known as sequential compactness and, in metric spaces (but not in general topological spaces), is equivalent to the topological notions of countable compactness and compactness defined via open covers.

Examples of compact metric spaces include the closed interval [0,1] with the absolute value metric, all metric spaces with finitely many points, and the Cantor set. Every closed subset of a compact space is itself compact.

A metric space is compact if and only if it is complete and totally bounded. This is known as the Heine–Borel theorem. Note that compactness depends only on the topology, while boundedness depends on the metric.

Lebesgue's number lemma states that for every open cover of a compact metric space M, there exists a "Lebesgue number" δ such that every subset of M of diameter < δ is contained in some member of the cover.

Every compact metric space is second countable,^[1] and is a continuous image of the Cantor set. (The latter result is due to Pavel Alexandrov and Urysohn.)

[edit] Locally compact and proper spaces

A metric space is said to be locally compact if every point has a compact neighborhood. Euclidean spaces are locally compact, but infinite-dimensional Banach spaces are not.

A space is proper if every closed ball {y : d(x,y) ≤ r} is compact. Proper spaces are locally compact, but the converse is not true in general.

[edit] Connectedness

A metric space M is connected if the only subsets that are both open and closed are the empty set and M itself.

A metric space M is path connected if two any two points x, y in M there exists a continuous map f:[0,1]→M with f(0)=x and f(1)=y. Every path connected space is connected, but the converse is not true in general.

There are also local versions of these definitions: locally connected spaces and locally path connected spaces.

Simply connected spaces are those that, in a certain sense, do not have "holes".

[edit] Separable spaces

A metric space is separable space if it has a countable dense subset. Typical examples are the real numbers or any Euclidean space. For metric spaces (but not for general topological spaces) separability is equivalent to second countability and also to the Lindelöf property.

[edit] Types of maps between metric spaces

Suppose (M₁,d₁) and (M₂,d₂) are two metric spaces.

[edit] Continuous maps

The map f:M₁→M₂ is continuous if it has one (and therefore all) of the following equivalent properties:

general topological continuity

for every open set U in M₂, the preimage f^-1(U) is open in M₁

This is the general definition of continuity in topology.

sequential continuity

if (x_n) is a sequence in M₁ that converges to x in M₁, then the sequence (f(x_n)) converges to f(x) in M₂.

This is sequential continuity, due to Eduard Heine.

ε-δ definition

for every x in M₁ and every ε>0 there exists δ>0 such that

$d_1(x,y)<\delta \mbox{ implies } d_2(f(x),f(y))< \epsilon \quad\mbox{for all}\quad y\in M_1$

This uses the (ε, δ)-definition of limit, and is due to Augustin Louis Cauchy.

The image of every compact set under a continuous function is compact.

[edit] Uniformly continuous maps

The map f:M₁→M₂ is uniformly continuous if for every ε>0 there exists δ>0 such that

$d_1(x,y)<\delta \mbox{ implies } d_2(f(x),f(y))< \epsilon \quad\mbox{for all}\quad x,y\in M_1$

Every uniformly continuous map is continuous, but the converse is not true in general.

Uniformly continuous maps turn Cauchy sequences in M₁ into Cauchy sequences into M₂. Consequently, the image of every complete set under a uniformly continuous map is complete.

[edit] Lipschitz-continuous maps

Given a number K>0, the map f:M₁→M₂ is K-Lipschitz continuous if

$d_2(f(x),f(y))\leq K d_1(x,y)\quad\mbox{for all}\quad x,y\in M_1$

Every Lipschitz-continuous map is uniformly continuous, but the converse is not true in general.

[edit] Isometries

The map f:M₁→M₂ is an isometry if

$d_2(f(x),f(y))=d_1(x,y)\quad\mbox{for all}\quad x,y\in M_1$

Isometries are always injective; the image of a compact or complete set under an isometry is compact or complete, respectively. However, if the isometry is not surjective, then the image of a closed (or open) set need not be closed (or open).

[edit] Notions of metric space equivalence

Given two metric spaces (M₁, d₁) and (M₂, d₂):

They are called homeomorphic (topologically isomorphic) if there exists a homeomorphism between them (i.e., a bijection continuous in both directions).

They are called uniformic (uniformly isomorphic) if there exists a uniform isomorphism between them (i.e., a bijection uniformly continuous in both directions)

They are called isometric if there exists a bijective isometry between them. In this case, the two metric spaces are essentially identical.

[edit] Topological properties

Metric spaces are paracompact^[2] Hausdorff spaces^[3] and hence normal (indeed they are perfectly normal). An important consequence is that every metric space admits partitions of unity and that every continuous real-valued function defined on a closed subset of a metric space can be extended to a continuous map on the whole space (Tietze extension theorem). It is also true that every real-valued Lipschitz-continuous map defined on a subset of a metric space can be extended to a Lipschitz-continuous map on the whole space.

Metric spaces are first countable since one can use balls with rational radius as a neighborhood base.

The metric topology on a metric space M is the coarsest topology on M relative to which the metric d is a continuous map from the product of M with itself to the non-negative real numbers.

[edit] Distance between points and sets; Hausdorff distance and Gromov metric

A simple way to construct a function separating a point from a closed set (as required for a completely regular space) is to consider the distance between the point and the set. If (M,d) is a metric space, S is a subset of M and x is a point of M, we define the distance from x to S as

d(x,S) = inf {d(x,s) : s ∈ S}

Then d(x, S) = 0 if and only if x belongs to the closure of S. Furthermore, we have the following generalization of the triangle inequality:

d(x,S) ≤ d(x,y) + d(y,S)

which in particular shows that the map $x\mapsto d(x,S)$ is continuous.

Given two subsets S and T of M, we define their Hausdorff distance to be

d_H(S,T) = max { sup {d(s,T) : s ∈ S}, sup {d(t,S) : t ∈ T} }

In general, the Hausdorff distance d_H(S,T) can be infinite. Two sets are close to each other in the Hausdorff distance if every element of either set is close to some element of the other set.

The Hausdorff distance d_H turns the set K(M) of all non-empty compact subsets of M into a metric space. One can show that K(M) is complete if M is complete. (A different notion of convergence of compact subsets is given by the Kuratowski convergence.)

One can then define the Gromov-Hausdorff distance between any two metric spaces by considering the minimal Hausdorff distance of isometrically embedded versions of the two spaces. Using this distance, the set of all (isometry classes of) compact metric spaces becomes a metric space in its own right.

[edit] Product metric spaces

If $(M_1,d_1),\ldots,(M_n,d_n)$ are metric spaces, and N is the Euclidean norm on Rⁿ, then $\Big(M_1\times \ldots \times M_n, N(d_1,\ldots,d_n)\Big)$ is a metric space, where the product metric is defined by

$N(d_1,...,d_n)\Big((x_1,\ldots,x_n),(y_1,\ldots,y_n)\Big) = N\Big(d_1(x_1,y_1),\ldots,d_n(x_n,y_n)\Big)$ ,

and the induced topology agrees with the product topology. By the equivalence of norms in finite dimensions, an equivalent metric is obtained if N is the taxicab norm, a p-norm, the max norm, or any other norm which is non-decreasing as the coordinates of a positive n-tuple increase (yielding the triangle inequality).

Similarly, a countable product of metric spaces can be obtained using the following metric

$d(x,y)=\sum_{i=1}^\infty \frac1{2^i}\frac{d_i(x_i,y_i)}{1+d_i(x_i,y_i)}$ .

An uncountable product of metric spaces is, in general, not metrizable. For example, $\mathbf{R}^\mathbf{R}$ is not first-countable space (thus cannot be metrizable).

[edit] Continuity of distance

It is worth noting that in the case of a single space $(M, d)$ , the distance map $d:M\times M \rightarrow R^+$ (from the definition) is uniformly continuous with respect to any of the above product metrics $N (d, d)$ (and in particular, continuous with respect to the product topology of $M\times M$ ).

[edit] Quotient metric spaces

If M is a metric space with metric d, and ~ is an equivalence relation on M, then we can endow the quotient set M/~ with the following (pseudo)metric. Given two equivalence classes [x] and [y], we define

$d'([x],[y]) = \inf\{d(p_1,q_1)+d(p_2,q_2)+...+d(p_{n},q_{n})\}$

where the infimum is taken over all finite sequences $(p_1, p_2, \dots, p_n)$ and $(q_1, q_2, \dots, q_n)$ with $[p 1] = [x]$ , $[q n] = [y]$ , $[q_i]=[p_{i+1}], i=1,2,\dots n-1$ . In general this will only define a pseudometric, i.e. $d'([x],[y]) = 0$ does not necessarily imply that [x]=[y]. However for nice equivalence relations (e.g., those given by gluing together polyhedra along faces), it is a metric. Moreover if M is a compact space, then the induced topology on M/~ is the quotient topology.

The quotient metric d is characterized by the following universal property. If $f:(M,d)\longrightarrow(X,\delta)$ is a metric map between metric spaces (that is, $\delta(f(x),f(y))\le d(x,y)$ for all x, y) satisfying f(x)=f(y) whenever $x\sim y,$ then the induced function $\overline{f}:M/\sim\longrightarrow X$ , given by $\overline{f}([x])=f(x)$ , is a metric map $\overline{f}:(M/\sim,d')\longrightarrow (X,\delta).$

A topological space is sequential if and only if it is a quotient of a metric space.^[4]

[edit] See also

[edit] Notes

^ PlanetMath: a compact metric space is second countable
^ Rudin, Mary Ellen. A new proof that metric spaces are paracompact. Proceedings of the American Mathematical Society, Vol. 20, No. 2. (Feb., 1969), p. 603.
^ metric spaces are Hausdorff on PlanetMath
^ Goreham, Anthony. Sequential convergence in Topological Spaces. Honours' Dissertation, Queen's College, Oxford (April, 2001), p. 14

[edit] Sources

Victor Bryant, Metric Spaces: Iteration and Application, Cambridge University Press, 1985, ISBN 0-521-31897-1.
Dmitri Burago, Yu D Burago, Sergei Ivanov, A Course in Metric Geometry, American Mathematical Society, 2001, ISBN 0-8218-2129-6.
Mícheál Ó Searcóid, Metric Spaces, Springer Undergraduate Mathematics Series, 2006, ISBN 1-84628-369-8.
Eric W. Weisstein, Product Metric at MathWorld.

[edit] External links

Far and near — several examples of distance functions at cut-the-knot

[0] PlanetMath: a compact metric space is second countable

[1] Rudin, Mary Ellen. A new proof that metric spaces are paracompact. Proceedings of the American Mathematical Society, Vol. 20, No. 2. (Feb., 1969), p. 603.

[2] tric spaces are Hausdorff on PlanetMath

[3] Goreham, Anthony. Sequential convergence in Topological Spaces. Honours' Dissertation, Queen's College, Oxford (April, 2001), p. 14

[1]

[2]

[3]

[4]