Complete metric space
In mathematical analysis, a metric space (M, d) is said to be complete if every Cauchy sequence of points in M has a limit in M.
Intuitively, a space is complete if it "doesn't have any holes", if there aren't any "points missing". For instance, the rational numbers are not complete, because √ 2 is "missing". It is always possible to "fill all the holes", leading to the completion of a given space. This will be explained below.
Examples
The rational numbers Q, with the standard metric given by the absolute value, are not complete. Consider for instance the sequence defined by x1 = 1 and xn+1 = (xn + 2/xn) / 2. This is a Cauchy sequence of rational numbers, but it does not converge towards any rational limit; in fact, it converges towards the irrational number √2 (see square root).
The open interval (0,1), again with the absolute value metric, is not complete either: The sequence 1/2, 1/3, 1/4, 1/5, ... is Cauchy, but does not have a limit in the space.
The real numbers and the complex numbers with the metric given by the absolute value are complete, so is Euclidean space Rn and, more generally, all Banach spaces.
The p-adic numbers are complete for any prime number p.
If S is an arbitrary set, then the set SN of all sequences in S becomes a complete metric space if we define the distance between the sequences (xn) and (yn) to be 1/N where N is the smallest index for which xN ≠ yN; if there is no such index, then the two sequences are the same and we define their distance to be 0. This space is homeomorphic to the product of a countable number of copies of the discrete space S.
Some theorems
Every compact metric space is complete. In fact, a metric space is compact if and only if it is complete and totally bounded.
A subspace of a complete space is complete if and only if it is closed.
If X is some set, and M is a complete metric space, then the set B(X, M) consisting of all bounded function f : X -> M, with the metric d(f, g) = supx in Xd(f(x), g(x)), is a complete metric space.
If X is a topological space and M is a complete metric space, then the set Cb(X, M) consisting of all continuous bounded functions f : X -> M is a closed subspace of B(X, M) and hence also complete.
The Baire category theorem applies to complete spaces: the interior of a union of countably many nowhere dense subsets of a complete space is empty.
Completion
For any metric space (M, d), one can construct a complete metric space (M', d') which contains M as a dense subset and such that d(x, y) = d'(x, y) for all x and y in M. It has the following universal property: if N is any complete metric space and f : M -> N is any uniformly continuous map, then there exists a unique uniformly continuous map g : M' -> N which extends f. The space M' is essentially uniquely determined by this property, and is called the completion of M.
The completion of M can be constructed as a set of equivalence classes of Cauchy sequences in M. For any two Cauchy sequences (xn) and (yn) in M, we may define their distance as
- d'((xn), (yn)) = limn → ∞ d(xn, yn)
(This limit exists because the real numbers are complete.) This is not yet a metric, since two different Cauchy sequences may have the distance 0. But "having distance 0" is an equivalence relation on the set of all Cauchy sequences, and the set of equivalence classes turns into an metric space, the completion of M.
The standard construction of the real numbers is a special case of this (if one disregards the circularity inherent in the fact that the definition of metric spaces involves real numbers): the real numbers are the completion of the rational numbers using the ordinary absolute value to measure distances. By using different notions of distance on the rationals, one obtains different incomplete metric spaces, and their completions turn out to be the p-adic numbers.
If this completion procedure is applied to a normed vector space, one obtains a Banach space containing the original space as a dense subspace, and if it is applied to an inner product space, one obtains a Hilbert space containing the original space as a dense subspace.
Generalization and Caveats
Note that completeness is a property of the metric and not of the topology, meaning that a complete metric space can be homeomorphic to a non-complete one. An example is given by the real numbers, which are complete and homeomorphic to the open interval (0,1), which is not complete. Another example are the irrational numbers: they are not complete as a subspace of the real numbers with the usual metric (take any sequence of irrational numbers converging to a rational number). However, the irrational numbers are homeomorphic to the countable power of the natural numbers, which is a complete metric space as explained above in the examples section.
In topology one considers completely metrizable spaces, spaces for which there exists at least one complete metric inducing the given topology. Completely metrizable spaces can be characterized as those spaces which can be written as an intersection of countably many open subsets of some complete metric space Cech completeness, absolute G_delta spaces. The Baire category theorem applies to these spaces as well.
It is also possible to define the concept of completeness for uniform spaces using a generalization of sequences. A net (xα) in a uniform space X is a Cauchy net if for every entourage V there exists an α0 such that for all α, β > α0 we have (xα, xβ) in V. If every Cauchy net has a limit in X, then X is called complete. One can construct a completion for an arbitrary uniform space similar to the completion of metric spaces.
In complexity theory, a problem P is said to be complete for a complexity class C, under a given type of reduction, if P is in C, and every problem in C reduces to P using that reduction. For example, each problem in the class NP-Complete is complete for the class NP, under polynomial-time, many-one reduction.
In logic, a system of axioms is said to be complete if, for any statement P, a proof exists for P or for not P. A system is consistent if a proof never exists for both P and not P. Goedel's incompleteness theorem proved that no system as powerful as Peano's axioms can be both consistent and complete.
For the notion of completeness of lattices, see lattice.
For the notion of completeness of measures, see complete measure.