PROFILPELAJAR.COM

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.

Other properties related to completeness

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.

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

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:

\models _{\mathcal {S}}\varphi \ \to \ \vdash _{\mathcal {S}}\varphi .

^[1]

For example, Gödel's completeness theorem establishes semantic completeness for first-order logic.

Strong completeness

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:

\Gamma \models _{\mathcal {S}}\varphi \ \to \ \Gamma \vdash _{\mathcal {S}}\varphi .

Refutation-completeness

A formal system S is refutation-complete if it is able to derive false from every unsatisfiable set of formulas. That is:

\Gamma \models _{\mathcal {S}}\bot \to \ \Gamma \vdash _{\mathcal {S}}\bot .

^[2]

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$ of $\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 sets.^[3] The latter is not strongly complete: e.g. $\{a\}\models a\lor b$ holds even in the propositional subset of first-order logic, but $a\lor b$ cannot be derived from $\{a\}$ by resolution. However, $\{a,\lnot (a\lor b)\}\vdash \bot$ can be derived.

Syntactical completeness

A formal system 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 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).^{[citation needed]}

Structural completeness

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

Model completeness

A theory is model complete if and only if every embedding of its models is an elementary embedding.

References

^ Hunter, Geoffrey (1996) [1971]. Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press (published 1973). p. 94. ISBN 9780520023567. OCLC 36312727. (accessible to patrons with print disabilities)
^ David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley. Here: sect. 2.2.3.1, p.33
^ Stuart J. Russell, Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall. Here: sect. 9.7, p.286

[1] Hunter, Geoffrey (1996) [1971]. Metalogic: An Introduction to the Metatheory of Standard First-Order Logic. University of California Press (published 1973). p. 94. ISBN 9780520023567. OCLC 36312727. (accessible to patrons with print disabilities)

[2] David A. Duffy (1991). Principles of Automated Theorem Proving. Wiley. Here: sect. 2.2.3.1, p.33

[3] Stuart J. Russell, Peter Norvig (1995). Artificial Intelligence: A Modern Approach. Prentice Hall. Here: sect. 9.7, p.286

[1]

[2]

[3]

PROFILPELAJAR.COM

Completeness (logic)

Other properties related to completeness

Forms of completeness

Expressive completeness

Functional completeness

Semantic completeness

Strong completeness

Refutation-completeness

Syntactical completeness

Structural completeness

Model completeness

References

Read other articles:

Feeding frenzy

Hakuhō period

Saad Hariri

Viroid

Centenary Square, Parramatta

Particle physics and representation theory

Dahshur

哈萨克斯坦总统

مهارات الدراسة

List of Atlas launches (1957–1959)

Bank of Bahrain and Kuwait

Lega Nazionale B 1983-1984

23 січня

Желивскего

John Shurna

Burnt Prairie

نظام عد ثماني

Vladimir Orel

Queen Ethelburga's Collegiate

Transformateur électrique