completeness(redirected from Completeness (in logic))
Also found in: Dictionary, Thesaurus.
a property of a scientific theory that characterizes the sufficiency, for some specific purposes, of the theory’s expressive and/or deductive means.
One aspect of the concept of completeness is functional completeness. As applied to a natural language, it is the informal property by virtue of which the language can be used to formulate any meaningful message that may be required for a particular purpose. For example, the English language is functionally complete with respect to the purposes that Shakespeare had in mind in writing Hamlet —assuming Shakespeare succeeded in fully realizing his design. But any of the living languages into which Hamlet has been translated is also complete in the same sense. The translation is itself evidence of this functional completeness.
Similarly, in mathematics, a family of functions that belongs to some class of functions is complete with respect to this class and with respect to some fixed stock of permissible operations on the functions if any function of the class can be expressed in terms of functions of the given family by means of permissible operations. Thus, either of the functions sin x or cos x is a single-element class that is complete for all trigonometric functions with respect to the four arithmetic operations, squaring, and extraction of square roots. The three unit vectors along the coordinate axes form a complete class with respect to addition, subtraction, and multiplication by a real number for the set of all vectors of three-dimensional Euclidean space.
The concept of functional completeness plays an important role in mathematical logic. All binary logical operations of a propositional calculus can be expressed in terms of conjunction and negation, disjunction and negation, implication and negation, or even the single operation of alternative denial (Sheffer stroke function). In other words, these families of logical connectives are all functionally complete classes of the operations of the algebra of logic.
For logic and its applications to the deductive sciences, a no less significant role is played by the deductive completeness of axiomatic theories or, which is the same thing, of the systems of axioms on which the theories are based. The epithet “deductive” is usually omitted. Depending on the choice of the criterion for the sufficiency of the deductive means of a theory or formal calculus, some precise modification of the concept of deductive completeness is arrived at. In general, an axiomatic system is said to be (deductively) complete with respect to a given property or a given interpretation if all its formulas that have a given property or are true under the given interpretation are provable in it. This broad conception of deductive completeness, which is associated with the concept of truth, is obviously semantic, or meaning-oriented, in character. But in many cases the concept of deductive completeness can be defined in a purely syntactical, or formal, manner and can be made an object of study by meta-mathematical means. Such deductive completeness of a system is defined as follows: no formula that is unprovable in the system can be added to it as an axiom without making it inconsistent. This “absolute” completeness is in general stronger than semantic completeness; for example, predicate calculus, which is complete in the broad sense, is incomplete in the narrow.
Incomplete axiom systems that permit of essentially different and nonisomorphic interpretations—such as group theory in abstract algebra or the theory of topological spaces—are of particular interest because of the richness and diversity of their applications owing to the various ways of supplementing a theory by appending various axioms. Still more important is the result published by K. Gödel in 1931: for sufficiently complex axiomatic theories—including the formal arithmetic of natural numbers and, especially, axiomatic set theory—the requirements of deductive completeness and consistency are incompatible. This startling discovery opened up a new era in the development of mathematicallogic; led to the recognition of the fundamental limitedness of the axiomatic method, which plays an important role in mathematical logic; and stimulated a search for new and, in a sense, more flexible theories of logic and mathematical logic and for new deductive tools.
REFERENCESKleene, S. C. Vvedenie v metamatematiku. Moscow, 1957. Subsections 29, 32, 42, 72 (bibliography). (Translated from English.)
Novikov, P. S. Elementy matematicheskoi logiki. Moscow, 1959. Chapter 2, subsec. 10, ch. 3, subsec. 7, ch. 4, subsecs. 17, 19.