Completeness (logic)

In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula having the property can be derived using that system, i.e. is one of its theorems; 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. Intuitively, a system is called complete in this particular sense, if it can derive every formula that is true. In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula having the property can be derived using that system, i.e. is one of its theorems; 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. Intuitively, a system is called complete in this particular sense, if it can derive every formula that is true. The property converse to completeness is called soundness: a system is sound with respect to a property (mostly semantical validity) if each of its theorems has that property. A formal language is expressively complete if it can express the subject matter for which it is intended. A set of logical connectives associated with a formal system is functionally complete if it can express all propositional functions. Semantic completeness is the converse of soundness for formal systems. A formal system is complete with respect to tautologousness or '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). That is, For example, Gödel's completeness theorem establishes semantic completeness for first-order logic. A formal system S 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: A formal system S is refutation-complete if it is able to derive false from every unsatisfiable set of formulas. That is, Every strongly complete system is also refutation-complete. Intuitively, strong completeness means that, given a formula set Γ {displaystyle Gamma } , it is possible to compute every semantical consequence φ {displaystyle varphi } of Γ {displaystyle Gamma } , while refutation-completeness means that, given a formula set Γ {displaystyle Gamma } and a formula φ {displaystyle varphi } , it is possible to check whether φ {displaystyle varphi } is a semantical consequence of Γ {displaystyle Gamma } .