All Topics  
Completeness

 

 
   Email Print
   Bookmark   Link
 

 

Completeness
 
 
  Topics Completeness Topic Home

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

a class="link1" onMouseover='showByLink("m141192",this)' onMouseout='hide("m141192")'href="http://www.absoluteastronomy.com/topics/Logic">logic
Logic

Logic is the study of the principles of valid demonstration and inference. Logic is a branch of philosophy, a part of the classical Trivium . The word derives from Greek language ?????? , fem....
, semantic completeness is the converse
Contraposition

In traditional logic, contraposition is a form of immediate inference in which from a given proposition another is inferred having for its subject the contradictory of the original predicate , and in some cases involving a change of quality ....
 of soundness
Soundness

In mathematical logic, a logical system has the soundness property if and only if its inference rules prove only formula that are valid with respect to its semantics....
 for formal systems. A formal system is "semantically complete" when all tautologies
Tautology (logic)

In propositional logic, a tautology is a propositional formula that is true under any possible Valuation of its propositional variables. For example, the propositional formula is a tautology, because the statement is true for any valuation of A....
 are theorems whereas a formal system is "sound" when all theorems are tautologies. Kurt Gödel
Kurt Gödel

Kurt G?del was an Austrian-United States logician, mathematician and philosopher. One of the most significant logicians of all time, G?del made an immense impact upon scientific and philosophical thinking in the 20th century, a time when many, such as Bertrand Russell, A....
, Leon Henkin
Leon Henkin

Leon Henkin was a logician at the University of California, Berkeley. He was principally known for the "Henkin completeness proof": his version of the proof of the semantic completeness of standard systems of first-order logic....
, and Emil Post all published proofs of completeness.






Discussion
Ask a question about 'Completeness'
Start a new discussion about 'Completeness'
Answer questions from other users
Full Discussion Forum



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

Logic is the study of the principles of valid demonstration and inference. Logic is a branch of philosophy, a part of the classical Trivium . The word derives from Greek language ?????? , fem....
, semantic completeness is the converse
Contraposition

In traditional logic, contraposition is a form of immediate inference in which from a given proposition another is inferred having for its subject the contradictory of the original predicate , and in some cases involving a change of quality ....
 of soundness
Soundness

In mathematical logic, a logical system has the soundness property if and only if its inference rules prove only formula that are valid with respect to its semantics....
 for formal systems. A formal system is "semantically complete" when all tautologies
Tautology (logic)

In propositional logic, a tautology is a propositional formula that is true under any possible Valuation of its propositional variables. For example, the propositional formula is a tautology, because the statement is true for any valuation of A....
 are theorems whereas a formal system is "sound" when all theorems are tautologies. Kurt Gödel
Kurt Gödel

Kurt G?del was an Austrian-United States logician, mathematician and philosopher. One of the most significant logicians of all time, G?del made an immense impact upon scientific and philosophical thinking in the 20th century, a time when many, such as Bertrand Russell, A....
, Leon Henkin
Leon Henkin

Leon Henkin was a logician at the University of California, Berkeley. He was principally known for the "Henkin completeness proof": his version of the proof of the semantic completeness of standard systems of first-order logic....
, and Emil Post all published proofs of completeness. (See History of the Church–Turing thesis.) A system is consistent
Consistency

Consistency can refer to:* Consistency * Consistency , the psychological need to be consistent with prior acts and statements* "Consistency", an 1887 speech by Mark Twain...
 if a proof never exists for both P and not P.

  • For a formal system S in formal language L, S is semantically complete or simply complete, iff
    IFF

    IFF, Iff or iff can stand for:* Identification Friend or Foe, an electronic radio-based identification system utilizing transponders...
     every logically valid formula of L (every formula which is true under every interpretation of L) is a theorem of S. That is, .


  • A formal system S is strongly complete or complete in the strong sense iff for every set of premises T, any formula which semantically follows from T is derivable from T. That is, .


  • A formal system S is syntactically complete or deductively complete or maximally complete or simply complete iff for each formula A of the language of the system either A or ¬A is a theorem of S. This is also called negation completeness. In another sense, a formal system is syntactically complete iff 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 no recursive system that is sufficiently powerful, such as the Peano axioms
    Peano axioms

    In mathematical logic, the Peano axioms, also known as the Dedekind?Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian people mathematician Giuseppe Peano....
    , can be both consistent and complete.


  • A formal system is inconsistent iff every sentence is a theorem.


  • A system of logical connective
    Logical connective

    In logic, two sentences may be joined by means of a logical connective to form a compound sentence. The truth-value of the compound is uniquely determined by the truth-values of the simpler sentences....
    s is functionally complete
    Functional completeness

    In logic, a set S of logical connectives is functionally complete if every possible logical connective can be defined in terms of the members of S....
     iff it can express all propositional functions.


  • 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 iff every sentence that has the property
    Property (philosophy)

    In modern philosophy, mathematics, and logic, a property is an attribute of an Object ; thus a red object is said to have the property of redness....
     is a theorem.


Mathematical completeness

In mathematics
Mathematics

Mathematics is the study of quantity, structure, space, change, and related topics of pattern and form. Mathematicians seek out patterns whether found in numbers, space, natural science, computers, imaginary abstractions, or elsewhere....
, "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 in one variable of degree at least 1, with coefficients in F, has a root in F....
 or compactification
Compactification (mathematics)

In mathematics, compactification is the process or result of enlarging a topological space to make it compact space. 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"....
.

  • 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....
     (or 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 property such as complete space, uniform continuity and uniform convergence....
    ) is complete if every Cauchy sequence
    Cauchy sequence

    In mathematics, a Cauchy sequence, named after Augustin Cauchy, is a sequence whose elements become arbitrarily close to each other as the sequence progresses....
     in it converges
    Limit (mathematics)

    In mathematics, the concept of a "limit" is used to describe the behavior of a Function as its argument or input either "gets close" to some point, or as the argument becomes arbitrarily large; or the behavior of a sequence's elements as their index increases indefinitely....
    . See complete space
    Complete space

    In mathematical analysis, a metric space M is said to be complete if every Cauchy sequence of points in M has a limit that is also in M or alternatively if every Cauchy sequence in M converges in M....
    .


  • In functional analysis
    Functional analysis

    Functional analysis is the branch of mathematics, and specifically of mathematical analysis, concerned with the study of vector spaces and operators acting upon them....
    , 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. Notice that A and B may coincide....
     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. As the name suggests the space blends a topology with the algebraic concept of a 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
    Linear combination

    In mathematics, linear combinations are a concept central to linear algebra and related fields of mathematics.Most of this article deals with linear combinations in the context of a vector space over a field , with some generalisations given at the end of the article....
     of vectors from S. In the particular case of Hilbert space
    Hilbert space

    The mathematics concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra from the two-dimensional plane and three-dimensional space to infinite-dimensional spaces....
    s (or more generally, inner product space
    Inner product space

    In mathematics, an inner product space is a vector space with the additional Mathematical structure of 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, an orthonormal basis of an inner product space V , is a set of mutually orthogonality vectors of magnitude 1 that span the space when infinite linear combinations are allowed....
     is a set that is both complete and orthonormal.


  • A measure space
    Measure (mathematics)

    In mathematics, more specifically in measure theory, 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....
     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 in which every subset of every null set is measurable . More formally, is complete if and only if...
    .


  • In commutative algebra
    Commutative algebra

    Commutative algebra is the branch of abstract algebra that studies commutative rings, their ideal , and module 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 commutative algebra, the term completion refers to several related functors on topological rings and modules. Completion is similar to localization of a ring, and together they are among the most basic tools in analysing commutative rings....
    .


  • More generally, any topological group
    Topological group

    In mathematics, a topological group is a group G together with a topological space on G such that the group's binary operation and the group's inverse function are continuous function ....
     can be completed at a decreasing sequence of open subgroups.


  • In statistics
    Statistics

    Statistics is a Mathematics pertaining to the collection, analysis, interpretation or explanation, and presentation of data. It also provides tools for prediction and forecasting based on data....
    , a statistic
    Statistic

    A statistic is the result of applying a function to a Data set.More formally, statistical theory defines a statistic as a function of a sample where the function itself is independent of the sample's distribution: the term is used both for the function and for the value of the function on a given sample....
     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 for which the statistic optimally obtains information about the unknown parameters characterizing the distribution of the underlying data....
    .


  • In graph theory
    Graph theory

    In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
    , a complete graph
    Complete graph

    In graph theory, a complete graph is a simple graph in which every pair of distinct vertex is connected by an edge . The complete graph on n vertices has n vertices and n/2 edges, and is denoted by ....
     is an undirected graph in which every pair of vertices has exactly one edge connecting them.


  • In category theory
    Category theory

    In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from set s and function s to objects linked in diagrams by morphisms or arrows....
    , a category C is complete
    Complete category

    In mathematics, a complete category is a category in which all small limit s exist. That is, a category C is complete if every diagram F : J → C where J is small category has a limit in C....
     if every diagram
    Diagram (category theory)

    In category theory, a branch of mathematics, a diagram is the categorical analogue of a indexed family in set theory. The primary difference is that in the categorical setting one has morphisms as well: an indexed family of sets is a collection of sets, indexed by a fixed set , while a diagram is a collection of objects and morphisms, indexed...
     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 product 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 that studies various kinds of binary relations that capture the intuitive notion of ordering, providing a framework for saying when one thing is "less than" or "precedes" another....
     and related fields such as lattice
    Lattice (order)

    In mathematics, a lattice is a partially ordered set in which subsets of any two elements have a unique supremum and an infimum . Lattices can also be characterized as algebraic structures satisfying certain Axiom identity ....
     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....
    , completeness
    Completeness (order theory)

    In the mathematics area of order theory, completeness properties assert the existence of certain infimum or supremum of a given partially ordered set ....
     generally refers to the existence of certain suprema
    Supremum

    In mathematics, given a subset S of a partially ordered set T, the supremum of S, if it exists, is the greatest element of T that is greater than or equal to each element of S....
     or infima
    Infimum

    In mathematics the infimum of a subset of some set is the greatest element, not necessarily in the subset, that is less than or equal to all elements of the subset....
     of some partially ordered set
    Partially ordered set

    In mathematics, especially order theory, a partially ordered set formalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set ....
    . 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. These orders, called dcpo and cpo for short, are characterized by particular completeness ....
     (cpo). Furthermore, an ordered field
    Ordered field

    In mathematics, an ordered field is a field together with a total ordering of its elements that agrees in a certain sense with the field operations....
     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 xxxx" indicates that members of an equivalence class are to be regarded as a single entity for some purpose. "xxxx" describes a property or process which transforms an element into one from the same equivalence class, i.e....
     isomorphism
    Isomorphism

    In abstract algebra, an isomorphism is a bijection map f such that both f and its inverse function f −1 are homomorphisms, i.e., structure-preserving mappings....
     there is only one complete ordered field: the field of real number
    Real number

    In mathematics, the real numbers may be described informally in several different ways. The real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339...., where the digits co...
    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, as the name suggests, combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry....
    , an algebraic variety
    Algebraic variety

    In mathematics, an algebraic variety is essentially a set of points where a polynomial or set of polynomials attain a value of zero. Algebraic varieties are one of the central objects of study in classical algebraic geometry....
     is complete if it satisfies an analog of compactness
    Compact space

    In mathematics, a topological space is called compact if each of its open covers has a finite set subcover.Note: Some authors such as Nicolas Bourbaki use the term "quasi-compact" for this instead, and reserve the term "compact" for topological spaces that are both Hausdorff spaces and "quasi-compact"....
    . 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 morphism...
    .


Computing

  • In algorithms, the notion of completeness refers to the ability of the algorithm to find a solution if one exists, and if not, reports that no solution is possible.
  • In computational complexity theory
    Computational complexity theory

    Computational complexity theory, as a branch of the theory of computation in computer science, investigates the problems related to the Computational resource required for the execution of algorithms , and the inherent difficulty in providing efficient algorithms for specific computational problems....
    , 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 problems having two properties:* Any given solution to the problem can be verified quickly ; the set of problems with this property is called NP ....
     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 algorithm Polynomial time"....
    , under polynomial-time
    Polynomial time

    In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, , is no greater than a polynomial function of the problem size, n....
    , many-one reduction.
  • In computing
    Computing

    Computing is usually defined as the activity of using and developing computer technology, computer hardware and computer software. It is the computer-specific part of information technology....
    , a data-entry field can autocomplete
    Autocomplete

    Autocomplete is a feature provided by many source code text editors, word processors, and web browsers. Autocomplete involves the program predicting a word or phrase that the user wants to type in without the user actually typing it in completely....
     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).


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....
  • 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 Oil 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 jewellery and perforating and stimulating as required....
    , the process of making a well ready for production.