Completeness
From Wikinfo
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.
- An ordered field is complete if every non-empty subset of it that has an upper bound within the field has a least upper bound within the field. Up to isomorphism there is only one complete ordered field: the field of real numbers.
- In functional analysis, a subset S of a topological vector space V is complete if its span is dense in V. If V is separable, it follows that any vector in V can be written as a (possibly infinite) linear combination of vectors from S. 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 (often just specified by a set of additional axioms used to formalize some theory within the underlying logic) 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 below for another notion of completeness in logic.
- 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 P, that follows sematically from a set of premises G, can be derived syntactically from these premisses within the calculus. Formally, G|=P implies G|-P. Especially, all tautologies of the logic can be proven. Even when working with classical logic, this is not equivalent to the notion of completeness introduced above (both a statement and its negation might not be tautologies wrt the logic). The reverse implication is called soundness.
- In computational 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.
References
- Adapted from the Wikipedia article, "Completeness" http://en.wikipedia.org/wiki/Completeness, used under the GNU Free Documentation License
