mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...

and

metalogic Metalogic is the study of the metatheory of logic. Whereas ''logic'' studies how logical systems can be used to construct valid and sound arguments, metalogic studies the properties of logical systems.Harry GenslerIntroduction to Logic Routledge, 2 ...

, a

formal system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A for ...

is called complete with respect to a particular

property Property is a system of rights that gives people legal control of valuable things, and also refers to the valuable things themselves. Depending on the nature of the property, an owner of property may have the right to consume, alter, share, r ...

if every formula having the property can be derived using that system, i.e. is one of its

theorem In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of ...

s; otherwise the system is said to be incomplete. The term "complete" is also used without qualification, with differing meanings depending on the context, mostly referring to the property of semantical

validity Validity or Valid may refer to: Science/mathematics/statistics: * Validity (logic), a property of a logical argument * Scientific: ** Internal validity, the validity of causal inferences within scientific studies, usually based on experiments ...

. Intuitively, a system is called complete in this particular sense, if it can derive every formula that is true.

Other properties related to completeness

The property converse to completeness is called

soundness In logic or, more precisely, deductive reasoning, an argument is sound if it is both valid in form and its premises are true. Soundness also has a related meaning in mathematical logic, wherein logical systems are sound if and only if every formul ...

: a system is sound with respect to a property (mostly semantical validity) if each of its theorems has that property.

Forms of completeness

Expressive completeness

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of s ...

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

Functional completeness

A set of

logical connective In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...

s associated with a formal system is functionally complete if it can express all

propositional function In propositional calculus, a propositional function or a predicate is a sentence expressed in a way that would assume the value of true or false, except that within the sentence there is a variable (''x'') that is not defined or specified (thus bei ...

Semantic completeness

Semantic completeness is the converse of

for formal systems. A formal system is complete with respect to tautologousness or "semantically complete" when all its tautologies are

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 Interpretation may refer to: Culture * Aesthetic interpretation, an explanation of the meaning of a work of art * Allegorical interpretation, an approach that assumes a text should not be interpreted literally * Dramatic Interpretation, an event ...

of the language of the system that is consistent with the rules of the system). That is, ::

\models_ \varphi\ \to\ \vdash_ \varphi.

Hunter, Geoffrey, Metalogic: An Introduction to the Metatheory of Standard First-Order Logic, University of California Press, 1971 For example,

Gödel's completeness theorem Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic. The completeness theorem applies to any first-order theory: I ...

establishes semantic completeness for

first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quanti ...

Strong completeness

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

\Gamma\models_ \varphi \ \to\ \Gamma \vdash_ \varphi.

Refutation completeness

A formal system is refutation-complete if it is able to derive ''

false False or falsehood may refer to: * False (logic), the negation of truth in classical logic *Lie or falsehood, a type of deception in the form of an untruthful statement * false (Unix), a Unix command * ''False'' (album), a 1992 album by Gorefest * ...

'' from every unsatisfiable set of formulas. That is, ::

\Gamma \models_ \bot \to\ \Gamma \vdash_ \bot.

Every strongly complete system is also refutation-complete. Intuitively, strong completeness means that, given a formula set

\Gamma

, it is possible to ''compute'' every semantical consequence

\varphi

\Gamma

, while refutation-completeness means that, given a formula set

\Gamma

and a formula

\varphi

, it is possible to ''check'' whether

\varphi

is a semantical consequence of

\Gamma

. Examples of refutation-complete systems include: SLD resolution on Horn clauses, superposition on equational clausal first-order logic, Robinson's resolution on

clause In language, a clause is a constituent that comprises a semantic predicand (expressed or not) and a semantic predicate. A typical clause consists of a subject and a syntactic predicate, the latter typically a verb phrase composed of a verb wi ...

sets. Here: sect. 9.7, p.286 The latter is not strongly complete: e.g.

\ \models a \lor b

holds even in the propositional subset of first-order logic, but

a \lor b

cannot be derived from

\

by resolution. However,

\ \vdash \bot

can be derived.

Syntactical completeness

A formal system is syntactically complete or deductively complete or maximally complete if for each sentence (closed formula) φ of the language of the system either φ or ¬φ is a theorem of . This is also called negation completeness, and is stronger than semantic completeness. In another sense, a formal system is syntactically complete if and only if no unprovable sentence can be added to it without introducing an inconsistency.

Truth-functional propositional logic Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...

and

first-order predicate logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantif ...

are semantically complete, but not syntactically complete (for example, the propositional logic statement consisting of a single propositional variable A is not a theorem, and neither is its negation). Gödel's incompleteness theorem shows that any recursive system that is sufficiently powerful, such as

Peano arithmetic In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly ...

, cannot be both consistent and syntactically complete.

Structural completeness

In superintuitionistic and modal logics, a logic is structurally complete if every admissible rule is derivable.

References

{{Mathematical logic Mathematical logic Metalogic Model theory Proof theory