{{short description|Characteristic of some logical systems}} {{distinguish|Complete (complexity)}} 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 semantic validity. Intuitively, a system is called complete in this particular sense, if it can derive every formula that is true.
==Other properties related to completeness== {{main|Soundness|Consistency}} 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. <!---subtleties of sound/consistent distinction needn't be explained here--- Completeness, as a quality of logical systems, is closely related to consistency. 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). ---> <!---not a good example, since dealing with axioms rather than inference rules; the axioms are incomplete only if the inference rules need to be sound--- The axioms of Euclidean geometry without the parallel postulate are an example of an incomplete logical system. --->
== Forms of completeness == ===Expressive completeness=== A formal language is ''expressively complete'' if it can express the subject matter for which it is intended.
===Functional completeness=== {{main|Functional completeness}} A set of logical connectives associated with a formal system is ''functionally complete'' if it can express all propositional functions.
===Semantic completeness=== '''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, a formal system is semantically complete if:
::<math> \models_{\mathcal S} \varphi\ \implies\ \vdash_{\mathcal S} \varphi.</math><ref>{{Hunter 1996|p=94}}</ref>
For example, Gödel's completeness theorem establishes semantic completeness for first-order logic.
===Strong completeness=== A formal system {{mathcal|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:
::<math> \Gamma\models_{\mathcal S} \varphi \ \implies\ \Gamma \vdash_{\mathcal S} \varphi.</math>
===Refutation completeness=== A formal system {{mathcal|S}} is '''refutation complete''' if it is able to derive ''false'' from every unsatisfiable set of formulas. That is: ::<math> \Gamma \models_{\mathcal S} \bot\ \implies\ \Gamma \vdash_{\mathcal S} \bot.</math><ref>{{cite book| author=David A. Duffy| title=Principles of Automated Theorem Proving| year=1991| publisher=Wiley}} Here: sect. 2.2.3.1, p.33</ref>
Every strongly complete system is also refutation complete. Intuitively, strong completeness means that, given a formula set <math>\Gamma</math>, it is possible to ''compute'' every semantical consequence <math>\varphi</math> of <math>\Gamma</math>, while refutation completeness means that, given a formula set <math>\Gamma</math> and a formula <math>\varphi</math>, it is possible to ''check'' whether <math>\varphi</math> is a semantical consequence of <math>\Gamma</math>.
Examples of refutation-complete systems include: SLD resolution on Horn clauses, superposition on equational clausal first-order logic, and Robinson's resolution on clause sets.<ref>{{cite book| author=Stuart J. Russell, Peter Norvig| title=Artificial Intelligence: A Modern Approach| year=1995| publisher=Prentice Hall}} Here: sect. 9.7, p.286</ref> The latter is not strongly complete: e.g. <math> \{ a \} \models a \lor b</math> holds even in the propositional subset of first-order logic, but <math>a \lor b</math> cannot be derived from <math>\{ a \}</math> by resolution. However, <math>\{ a, \lnot (a \lor b) \} \vdash \bot</math> can be derived.
===Syntactical completeness=== {{main|Complete theory}} A formal system {{mathcal|S}} is ''syntactically complete'' or ''deductively complete'' or ''maximally complete'' or ''negation complete'' if for each sentence (closed formula) ''φ'' of the language of the system either ''φ'' or ¬''φ'' is a theorem of {{mathcal|S}}. Syntactical completeness is a stronger property than semantic completeness. If a formal system is syntactically complete, a corresponding formal theory is called complete if it is a consistent theory. Gödel's incompleteness theorem shows that any computable system that is sufficiently powerful, such as Peano arithmetic, cannot be both consistent and syntactically complete.
''Syntactical completeness'' can also refer to another unrelated concept, also called ''Post completeness'' or ''Hilbert–Post completeness''. In this 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 and first-order predicate logic 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).
===Structural completeness=== {{main|Admissible rule}}
In superintuitionistic and modal logics, a logic is ''structurally complete'' if every admissible rule is a derivable implication.
===Model completeness=== {{main|Model complete theory}} A theory is ''model complete'' if and only if every embedding of its models is an elementary embedding.
==References== {{reflist}}
{{Mathematical logic}}
Category:Mathematical logic Category:Metalogic Category:Model theory Category:Proof theory