Completeness

# Completeness

Overview
In general, an object is complete if nothing needs to be added to it. This notion is made more specific in various fields.

In logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

, semantic completeness is the converse of soundness
Soundness
In mathematical logic, a logical system has the soundness property if and only if its inference rules prove only formulas that are valid with respect to its semantics. In most cases, this comes down to its rules having the property of preserving truth, but this is not the case in general. The word...

for formal systems. A formal system is "semantically complete" when all its tautologies
Tautology (logic)
In logic, a tautology is a formula which is true in every possible interpretation. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921; it had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternate sense...

are theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...

s, whereas a formal system is "sound" when all theorems are tautologies (that is, they are semantically valid formulas: formulas that are true under every interpretation of the language of the system that is consistent with the rules of the system).
Discussion

Encyclopedia
In general, an object is complete if nothing needs to be added to it. This notion is made more specific in various fields.

## Logical completeness

In logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...

, semantic completeness is the converse of soundness
Soundness
In mathematical logic, a logical system has the soundness property if and only if its inference rules prove only formulas that are valid with respect to its semantics. In most cases, this comes down to its rules having the property of preserving truth, but this is not the case in general. The word...

for formal systems. A formal system is "semantically complete" when all its tautologies
Tautology (logic)
In logic, a tautology is a formula which is true in every possible interpretation. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921; it had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternate sense...

are theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...

s, whereas a formal system is "sound" when all theorems are tautologies (that is, they are semantically valid formulas: formulas that are true under every interpretation of the language of the system that is consistent with the rules of the system). Kurt Gödel
Kurt Gödel
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...

, Leon Henkin
Leon Henkin
Leon Albert Henkin was a logician at the University of California, Berkeley. He was principally known for the "Henkin's completeness proof": his version of the proof of the semantic completeness of standard systems of first-order logic.-The completeness proof:Henkin's result was not novel; it had...

, and Emil Post all published proofs of completeness. (See History of the Church–Turing thesis.) A formal system is consistent
Consistency
Consistency can refer to:* Consistency , the psychological need to be consistent with prior acts and statements* "Consistency", an 1887 speech by Mark Twain...

if for all formulas φ of the system, the formulas φ and ¬φ (the negation
Negation
In logic and mathematics, negation, also called logical complement, is an operation on propositions, truth values, or semantic values more generally. Intuitively, the negation of a proposition is true when that proposition is false, and vice versa. In classical logic negation is normally identified...

of φ) are not both theorems of the system (that is, they cannot be both proved with the rules of the system).
• A formal system is semantically complete or simply complete, if and only if every tautology of is a theorem of . That is, .

• A formal system is strongly complete or complete in the strong sense if and only if for every set of premises Γ, any formula which semantically follows from Γ is derivable from Γ. That is, .

• A formal system is syntactically complete or deductively complete or maximally complete or simply complete if and only if for each formula φ of the language of the system either φ or ¬φ is a theorem of . This is also called negation completeness. In another sense, a formal system is syntactically complete if and only if no unprovable axiom can be added to it as an axiom without introducing an inconsistency. Truth-functional propositional logic and first-order predicate logic are semantically complete, but not syntactically complete (for example, the propositional logic statement consisting of a single variable "a" is not a theorem, and neither is its negation, but these are not tautologies). Gödel's incompleteness theorem shows that any recursive system that is sufficiently powerful, such as Peano arithmetic, cannot be both consistent and complete.

• A formal system is inconsistent if and only if every sentence is a theorem.

• A system of logical connective
Logical connective
In logic, a logical connective is a symbol or word used to connect two or more sentences in a grammatically valid way, such that the compound sentence produced has a truth value dependent on the respective truth values of the original sentences.Each logical connective can be expressed as a...

s is functionally complete if and only if it can express all propositional function
Propositional function
A propositional function in logic, is a statement expressed in a way that would assume the value of true or false, except that within the statement is a variable that is not defined or specified, which leaves the statement undetermined...

s.

• A language is expressively complete if it can express the subject matter for which it is intended.

• A formal system is complete with respect to a property if and only if every sentence that has the property
Property (philosophy)
In modern philosophy, logic, and mathematics a property is an attribute of an object; a red object is said to have the property of redness. The property may be considered a form of object in its own right, able to possess other properties. A property however differs from individual objects in that...

is a theorem.

## Mathematical completeness

In mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, "complete" is a term that takes on specific meanings in specific situations, and not every situation in which a type of "completion" occurs is called a "completion". See, for example, algebraically closed field
Algebraically closed field
In mathematics, a field F is said to be algebraically closed if every polynomial with one variable of degree at least 1, with coefficients in F, has a root in F.-Examples:...

or compactification
Compactification (mathematics)
In mathematics, compactification is the process or result of making a topological space compact. The methods of compactification are various, but each is a way of controlling points from "going off to infinity" by in some way adding "points at infinity" or preventing such an "escape".-An...

.
• The completeness of the real numbers
Completeness of the real numbers
Intuitively, completeness implies that there are not any “gaps” or “missing points” in the real number line. This contrasts with the rational numbers, whose corresponding number line has a “gap” at each irrational value...

is one of the defining properties of the real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

system. It may be described equivalently as either the completeness of R as metric space or as a partially ordered set (see below).

• A metric space
Metric space
In mathematics, a metric space is a set where a notion of distance 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...

is complete if every Cauchy sequence
Cauchy sequence
In mathematics, a Cauchy sequence , named after Augustin-Louis Cauchy, is a sequence whose elements become arbitrarily close to each other as the sequence progresses...

in it converges
Limit of a sequence
The limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...

. See Complete metric space.

• A uniform space
Uniform space
In the mathematical field of topology, a uniform space is a set with a uniform structure. Uniform spaces are topological spaces with additional structure which is used to define uniform properties such as completeness, uniform continuity and uniform convergence.The conceptual difference between...

is complete if every Cauchy net
Cauchy net
In mathematics, a Cauchy net generalizes the notion of Cauchy sequence to nets defined on uniform spaces.A net is a Cauchy net if for every entourage V there exists γ such that for all α, β ≥ γ, is a member of V. More generally, in a Cauchy space, a net is Cauchy if the filter generated by the...

in it converges (or equivalently every Cauchy filter in it converges).

• In functional analysis
Functional analysis
Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure and the linear operators acting upon these spaces and respecting these structures in a suitable sense...

, a subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...

S of a topological vector space
Topological vector space
In mathematics, a topological vector space is one of the basic structures investigated in functional analysis...

V is complete if its span is dense in V. In the particular case of Hilbert space
Hilbert space
The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions...

s (or more generally, inner product space
Inner product space
In mathematics, an inner product space is a vector space with an additional structure called an inner product. This additional structure associates each pair of vectors in the space with a scalar quantity known as the inner product of the vectors...

s), an orthonormal basis
Orthonormal basis
In mathematics, particularly linear algebra, an orthonormal basis for inner product space V with finite dimension is a basis for V whose vectors are orthonormal. For example, the standard basis for a Euclidean space Rn is an orthonormal basis, where the relevant inner product is the dot product of...

is a set that is both complete and orthonormal.

• A measure space
Measure (mathematics)
In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...

is complete if every subset of every null set
Null set
In mathematics, a null set is a set that is negligible in some sense. For different applications, the meaning of "negligible" varies. In measure theory, any set of measure 0 is called a null set...

is measurable. See complete measure
Complete measure
In mathematics, a complete measure is a measure space in which every subset of every null set is measurable...

.

• In commutative algebra
Commutative algebra
Commutative algebra is the branch of abstract algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number theory build on commutative algebra...

, a commutative ring can be completed at an ideal (in the topology defined by the powers of the ideal). See Completion (ring theory)
Completion (ring theory)
In abstract algebra, a completion is any of several related functors on rings and modules that result in complete topological rings and modules. Completion is similar to localization, and together they are among the most basic tools in analysing commutative rings. Complete commutative rings have...

.

• More generally, any topological group
Topological group
In mathematics, a topological group is a group G together with a topology on G such that the group's binary operation and the group's inverse function are continuous functions with respect to the topology. A topological group is a mathematical object with both an algebraic structure and a...

can be completed at a decreasing sequence of open subgroups.

• In statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....

, a statistic
Statistic
A statistic is a single measure of some attribute of a sample . It is calculated by applying a function to the values of the items comprising the sample which are known together as a set of data.More formally, statistical theory defines a statistic as a function of a sample where the function...

is called complete if it does not allow an unbiased estimator of zero. See completeness (statistics)
Completeness (statistics)
In statistics, completeness is a property of a statistic in relation to a model for a set of observed data. In essence, it is a condition which ensures that the parameters of the probability distribution representing the model can all be estimated on the basis of the statistic: it ensures that the...

.

• In graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, a complete graph
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...

is an undirected graph in which every pair of vertices has exactly one edge connecting them.

• In category theory
Category theory
Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

, a category C is complete
Complete category
In mathematics, a complete category is a category in which all small limits exist. That is, a category C is complete if every diagram F : J → C where J is small has a limit in C. Dually, a cocomplete category is one in which all small colimits exist...

if every diagram
Diagram (category theory)
In category theory, a branch of mathematics, a diagram is the categorical analogue of an indexed family in set theory. The primary difference is that in the categorical setting one has morphisms. An indexed family of sets is a collection of sets, indexed by a fixed set; equivalently, a function...

from a small category to C has a limit
Limit (category theory)
In category theory, a branch of mathematics, the abstract notion of a limit captures the essential properties of universal constructions such as products and inverse limits....

; it is cocomplete if every such functor has a colimit.

• In order theory
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...

and related fields such as lattice
Lattice (order)
In mathematics, a lattice is a partially ordered set in which any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain axiomatic identities...

and domain theory
Domain theory
Domain theory is a branch of mathematics that studies special kinds of partially ordered sets commonly called domains. Consequently, domain theory can be considered as a branch of order theory. The field has major applications in computer science, where it is used to specify denotational...

, completeness
Completeness (order theory)
In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set . A special use of the term refers to complete partial orders or complete lattices...

generally refers to the existence of certain suprema
Supremum
In mathematics, given a subset S of a totally or partially ordered set T, the supremum of S, if it exists, is the least element of T that is greater than or equal to every element of S. Consequently, the supremum is also referred to as the least upper bound . If the supremum exists, it is unique...

or infima
Infimum
In mathematics, the infimum of a subset S of some partially ordered set T is the greatest element of T that is less than or equal to all elements of S. Consequently the term greatest lower bound is also commonly used...

of some partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation that indicates that, for certain pairs of elements in the...

. Notable special usages of the term include the concepts of complete Boolean algebra
Complete Boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...

, complete lattice
Complete lattice
In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum and an infimum . Complete lattices appear in many applications in mathematics and computer science...

, and complete partial order
Complete partial order
In mathematics, directed complete partial orders and ω-complete partial orders are special classes of partially ordered sets, characterized by particular completeness properties...

(cpo). Furthermore, an ordered field
Ordered field
In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Historically, the axiomatization of an ordered field was abstracted gradually from the real numbers, by mathematicians including David Hilbert, Otto Hölder and...

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, which should be compared to the (slightly different) order-theoretical notion of bounded completeness. Up to
Up to
In mathematics, the phrase "up to x" means "disregarding a possible difference in  x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...

isomorphism
Isomorphism
In abstract algebra, an isomorphism is a mapping between objects that shows a relationship between two properties or operations.  If there exists an isomorphism between two structures, the two structures are said to be isomorphic.  In a certain sense, isomorphic structures are...

there is only one complete ordered field: the field of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...

s (but note that this complete ordered field, which is also a lattice, is not a complete lattice).

• In algebraic geometry
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...

, an algebraic variety
Algebraic variety
In mathematics, an algebraic variety is the set of solutions of a system of polynomial equations. Algebraic varieties are one of the central objects of study in algebraic geometry...

is complete if it satisfies an analog of compactness
Compact space
In mathematics, specifically general topology and metric topology, a compact space is an abstract mathematical space whose topology has the compactness property, which has many important implications not valid in general spaces...

. See complete algebraic variety
Complete algebraic variety
In mathematics, in particular in algebraic geometry, a complete algebraic variety is an algebraic variety X, such that for any variety Y the projection morphismis a closed map, i.e. maps closed sets onto closed sets....

.

• In quantum mechanics
Quantum mechanics
Quantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...

, a complete set of commuting operators (or CSCO) is one whose eigenvalues are sufficient to specify the physical state of a system.

## Computing

• In algorithms, the notion of completeness refers to the ability of the algorithm to find a solution if one exists, and if not, to report that no solution is possible.
• In computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...

, a problem P is complete
Complete (complexity)
In computational complexity theory, a computational problem is complete for a complexity class if it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class...

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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

is complete for the class NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...

, under polynomial-time, many-one reduction.
• In computing
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...

, a data-entry field can autocomplete
Autocomplete
Autocomplete is a feature provided by many web browsers, e-mail programs, search engine interfaces, source code editors, database query tools, word processors, and command line interpreters. Autocomplete involves the program predicting a word or phrase that the user wants to type in without the...

the entered data based on the prefix typed into the field; that capability is known as autocompletion.
• In software testing, completeness has for goal the functional verification of call graph (between software item) and control graph (inside each software item).
• The concept of completeness is found in knowledge base
Knowledge base
A knowledge base is a special kind of database for knowledge management. A Knowledge Base provides a means for information to be collected, organised, shared, searched and utilised.-Types:...

theory.

## Economics, finance, and industry

• Complete market
Complete market
In economics, a complete market is one in which the complete set of possible gambles on future states-of-the-world can be constructed with existing assets without friction. Every agent is able to exchange every good, directly or indirectly, with every other agent without transaction costs...

s versus incomplete markets
Incomplete markets
In economics, incomplete markets refers to markets in which the number of Arrow–Debreu securities is less than the number of states of nature...

• In auditing, completeness is one of the financial statement assertions that have to be ensured. For example, auditing classes of transactions. Rental expense which includes 12-month or 52-week payments should be all booked according to the terms agreed in the tenancy agreement.
• Oil or gas well completion
Completion (oil and gas wells)
In petroleum production, completion is the process of making a well ready for production . This principally involves preparing the bottom of the hole to the required specifications, running in the production tubing and its associated down hole tools as well as perforating and stimulating as...

, the process of making a well ready for production.

## Botany

• A complete flower is a flower with both male and female reproductive structures as well as petals and sepals. See Sexual reproduction in plants.