Completeness - Logical Completeness

Logical Completeness

In logic, semantic completeness is the converse of soundness for formal systems. A formal system is "semantically complete" when all its tautologies are theorems, 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, Leon Henkin, and Emil Post all published proofs of completeness. (See History of the Church–Turing thesis.) A formal system is consistent if for all formulas φ of the system, the formulas φ and ¬φ (the negation of φ) are not both theorems of the system (that is, they cannot be both proved with the rules of the system).

• A formal system S is semantically complete or simply complete, if and only if every tautology of S is a theorem of S. That is, .

• A formal system S 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 S 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 S. 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 connectives is functionally complete if and only if 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 if and only if every sentence that has the property is a theorem.