Completeness
In mathematics and related technical fields, a mathematical object is complete if nothing needs to be added to it. This is made precise in various ways, several of which have a related notion of completion.
- Metric spaces or uniform spaces are said to be complete if every Cauchy sequence in them converges. See Complete space.
- In functional analysis, a subset S of a topological vector space V is complete if its span is dense in V. In the particular case of Hilbert spaces (or more generally, inner product spaces), an orthonormal basis is a set that is both complete and orthonormal.
- A measure space is complete if every subset of every null set is measurable. See Complete measure.
- In statistics, a statistic is called complete if it does not allow an unbiased estimator of zero. See Completeness (statistics).
- In graph theory, a complete graph is an undirected graph where every pair of vertices has exactly one edge connecting them.
- In category theory, a category C is called complete if every functor from a small category to C has a limit; it is called cocomplete if every such functor has a colimit.
- In logic, a formal calculus 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. Gödel's incompleteness theorem proved that no system as powerful as the Peano axioms can be both consistent and complete. See also the point below for a more general usage from this area.
- In proof theory and related fields of mathematical logic, a formal calculus is said to be complete with respect to a certain logic (i.e. wrt its semantics), if every statement, that is a tautology of this logic, can be syntactically proven within the calculus. When working with classical logic, this is equivalent to the notion of completeness introduced above. The reverse statement is called soundness.
- 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.